专升本《数据结构》
一、 (共75题,共150分)
1. 数据的基本单位是()。 (2分)
A.数据元素 B.记录 C.数据对象 D.数据项 标准答案:A
2. ()是数据的不可分割的最小单位。 (2分)
A.数据对象 B.数据元素 C.数据类型 D.数据项 标准答案:D
3. 算法的空间复杂度是对算法()的度量。 (2分) A.时间效率 B.空间效率 C.可读性 D.健壮性 标准答案:B
4. ()是限制了数据元素的内部结构仅为一个字符的线性表。 (2分) A.栈 B.队列 C.串 D.数组 标准答案:B
5. 串的长度是指串中所含()的个数。 (2分)
A.不同字符 B.不同字母 C.相同字符 D.所有字符 标准答案:D
6. 采用带头结点双向链表存储的线性表,在删除一个元素时,需要修改指针()次。 (2分) A.1 B.2 C.3 D.4 标准答案:B
7. 线性表的顺序存储结构是一种()的存储结构。 (2分) A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 标准答案:B
8. 数组a[1..m]采用顺序存储,a[1]和a[m]地址分别为1024和1150,每个元素占2字节,则m是()。 (2分)
A.64 B.32 C.16 D.8 标准答案:A
9. 深度为h的二叉树,第h层最多有()个结点。 (2分) A.h B.2h-1 C.2h-1 D.2h 标准答案:C
10. m个结点的二叉树,其对应的二叉链表共有()个非空链域。 (2分) A.m B.m+1 C.2m D.m-1 标准答案:B
11. 下面叙述错误的是()。 (2分)
A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象 C.有向图的邻接矩阵一定是对称的
D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的
1 第1页共4页标准答案:C
12. 以下与数据的存储结构无关的术语是()。 (2分) A.循环队列 B.双向链表 C.哈希表 D.数组 标准答案:D
13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为()。 (2分) A.O(1) B.O(log n) C.O(n) D.O(n2) 标准答案:A
14. 在具有k个度数为2的二叉树中,必有()个叶子结点。 (2分) A.k B.k-1 C.2k D.k+1 标准答案:D
15. 在关键字序列(10,20,30,40,50)中,采用折半法查找20,关键字之间比较需要()次。 (2分)
A.1 B.2 C.3 D.4 标准答案:C
16. 16某二叉树的后序遍历序列和和中序遍历序列均为abcd,该二叉树的前序遍历序列是()。 (2分)
A.abcd B.dcba C.acbd D.dbca 标准答案:B
17. n个顶点的无向连通图的生成树,至少有()个边。 (2分) A.n(n-1) B.n(n-1)/2 C.2n D.n-1 标准答案:D
18. 可以采用()这种数据结构,实现二叉树的层次遍历运算。 (2分) A.队列 B.树 C.栈 D.集合 标准答案:A
19. 假设以数组A[0..n-1]存放循环队列的元素,其头指针front指向队头元素、尾指针rear指向队尾元素一个,则在少用一个元素空间的前提下,队列空的判定条件为()。 (2分) A.rear= =front B.(front+1)%n= =rear C.rear+1= =front D.(rear+1)%n= =front 标准答案:A
20. 序列(21,19,37,5,2)经冒泡排序法由小到大排序,第一趟后所得结果为()。 (2分) A.(19,21,37,5,2) B.(19,21,5,2,37) C.(19,21,5,37,2) D.(19,21,2,5,37) 标准答案:B
21. 二叉链表适合作为()的存储结构。 (2分) A.队列 B.二叉树 C.树 D.森林 标准答案:B,C,D
22. 设哈希(Hash)函数为H(k)= k % 17,其中k为关键字,关键字()是同义词。 (2分) A.44,5,15 B.28,45,62 C.6,57,125 D.201,31,48 标准答案:B,C,D
23. 下列各项键值()序列不是堆的。 (2分)
A.{94,68,23,16,5 B.{94,23,68,5,16 C.{94,23,16,68,5 D.{94,16,68,23,5 标准答案:C,D
24. 在下列排序方法中,()的空间复杂度为O(n)。其中,n为参加排序的元素个数。 (2分) A.选择排序 B.快速排序 C.归并排序 D.冒泡排序 标准答案:B,C
25. 十字链表适合于()选作存储结构。 (2分) A.队列 B.稀疏矩阵
C.边或弧数较少的图 D.二叉树 标准答案:B,C
26. 基于数据的逻辑关系,数据的逻辑结构划分为()基本结构。 (2分) A.6类 B.5类 C.4类 D.3类 标准答案:C
27. ()不是算法具有的5个特性之一。 (2分)
A.有穷性 B.确定性 C.可行性 D.正确性 标准答案:D
28. 算法的时间复杂度是对算法()的度量。 (2分) A.时间效率 B.空间效率 C.可读性 D.健壮性 标准答案:A
29. 线性表若采用链式存储结构时,要求结点的存储单元地址()。 (2分) A.必须是连续的 B.部分地址必须是连续的 C.必须是不连续的 D.连续或不连续都可以 标准答案:D
30. 二维数组通常采用顺序存储,其优点是()。 (2分) A.便于增加存储空间 B.防止下标溢出
C.避免数据元素的移动 D.便于依据下标进行随机存取 标准答案:D
31. 采用顺序存储的线性表,若表长为n,在第i号元素之后插入一个元素时,需要移动()个元素。 (2分)
A.i+1 B.i C.n-i D.n-i+1 标准答案:C
32. 若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为_________。 (2分) A.1、4、3、2 B.3、4、1、2 C.4、3、2、1 D.2、3、4、1 标准答案:B
33. 数组a[1..256]采用顺序存储,a的首地址为10,每个元素占2字节,则a[21]的地址是()。 (2分)
A.10 B.30 C.50 D.70 标准答案:C
34. 深度为h的完全二叉树至少有()个叶子结点。 (2分) A.2(h-1)+1 B.2(h-2)+1 C.2h-1 D.2h-2
2 第2页共4页标准答案:D
35. 若二叉树对应的二叉链表共有m个非空链域,则该二叉树有()个结点的二叉树。 (2分) A.m B.m-1 C.m+1 D.2m 标准答案:B
36. 下面叙述错误的是()。 (2分)
A.单链表是借助指针表示数据元素之间的逻辑关系 B.在顺序栈的入栈操作过程中可能发生上溢现象
C.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的 D.无向图的邻接矩阵一定是对称的 标准答案:C
37. 以下()术语与数据的存储结构无关 (2分) A.栈 B.哈希表 C.线索树 D.双向链表 标准答案:A
38. 在一个长度为n的链式队列中入队实现算法的时间复杂度为()。 (2分) A.O(1) B.O(log n) C.O(n) D.O(n2) 标准答案:A
39. 队列的出队操作是指()操作。 (2分)
A.队尾删除 B.队头删除 C.队尾插入 D.队头插入 标准答案:B
40. 在关键字序列(10,15,20,25,30)中采用折半法查找25,依次与()关键字进行了比较。 (2分)
A.30,25 B.20,25 C.20,30,25 D.25 标准答案:B
41. 16某二叉树的前序遍历序列和和中序遍历序列分别为abcd和bcad,该二叉树的后序遍历序列是()。 (2分)
A.cbda B.dcba C.abcd D.dcba 标准答案:A
42. 所占用的存储空间大小仅与图的顶点个数相关的存储结构是()。 (2分) A.邻接表 B.逆邻接表 C.十字链表 D.邻接矩阵 标准答案:D
43. 可以采用()这种数据结构,实现图的深度优先遍历运算。 (2分) A.队列 B.树 C.栈 D.集合 标准答案:C
44. 线性表采用带头结点单链表实现,head为头指针,则判断表空的条件为()。 (2分) A.head== NULL B.head!=NULL
C.head->next==NULL D.head->next !=NULL 标准答案:C
45. 在关键字序列(35,10,15,20,25)中采用最低位优先排序(LSD)基数排序,第一趟之后所得结果为()。 (2分)
A.10,20,15,25,35 B.10,20,35,15,25
C.20,10,35,25,15 D.20,10,35,15,25 标准答案:B
46. 下列逻辑结构中,()为线性结构。 (2分) A.栈 B.队列 C.串 D.二叉树 标准答案:A,B,C
47. 深度为3的二叉树可能的结点个数是()。 (2分) A.1 B.2 C.3 D.4 标准答案:A,B
48. 下列各项键值()序列是大顶堆的。 (2分)
A.{23,68,94,16,5 B.{94,68,23,16,5 C.{94,23,68,16,5 D.{94,16,68,23,5 标准答案:B,C
49. 下列()是限制了插入和删除操作的特殊线性表。 (2分) A.栈 B.队列 C.串 D.数组 标准答案:A,B
50. 对一棵二叉排序树,用()方法进行遍历,不一定得到各结点键值的有序序列。 (2分) A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历 标准答案:A,C,D
51. 数据的最小单位是()。 (2分)
A.数据元素 B.记录 C.数据对象 D.数据项 标准答案:D
52. 算法是对某一类问题求解步骤的有限序列。其中,()是算法具有的5个特性之一。 (2分) A.有穷性 B.正确性 C.可读性 D.健壮性 标准答案:A
53. ()是数据的逻辑结构。 (2分)
A.顺序表 B.链表 C.线性表 D.十字链表 标准答案:C
54. ()是限制了插入和删除操作在一端进行的线性表。 (2分) A.栈 B.队列 C.串 D.数组 标准答案:A
55. ()是限制了插入和删除操作分别在两端进行的线性表。 (2分) A.栈 B.队列 C.串 D.数组 标准答案:B
56. 用链表表示线性表的优点是()。 (2分) A.便于插入和删除 B.便于随机存取
C.花费的存储空间较顺序存储少
D.数据元素的物理顺序与逻辑顺序相同 标准答案:A
57. 若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为()。 (2分)
3 第3页共4页A.1、4、3、2 B.2、3、4、1 C.4、3、2、1 D.3、4、1、2 标准答案:D
58. 串下列关于串的叙述中,正确的是()。 (2分) A.2个串的长度相等,则2个串相等 B.空串至少包一个空格
C.替换操作可以实现字符的删除 D.一个串的长度至少是1 标准答案:C
59. 深度为h的二叉树,第h层至少有()个结点。 (2分) A.0 B.1 C.8 D.16 标准答案:B
60. 假设n≥0,在程序段{y=0;while((y+1)*(y+1)A.n B.[] C.n2
标准答案:C
61. 下面叙述错误的是()。 (2分)
A.在集合{1,2,3,4,5中元素1是2的直接前驱 B.二叉排序树的中序遍历序列一定是有序的 C.有3个结点的不同形态二叉树的数目为5
D.哈夫曼树中所有结点的孩子数目只可能为2或者为0 标准答案:A
62. 以下数据结构中,()是线性结构。 (2分) A.广义表 B.二叉树 C.稀疏矩阵 D.串 标准答案:D
63. 在一个长度为n的顺序表中删除一个元素的算法的时间复杂度为()。 (2分) A.O(1) B.O(log n) C.O(n) D.O(n2) 标准答案:C
64. 如果一个huffman树含有n个叶子,则该树必有()的结点。 (2分) A.n+1 B.2n+1 C.2n D.2n-1 标准答案:D
65. 在关键字序列(10,15,20,25,30)中,采用折半法查找25,关键字之间比较需要()次。 (2分)
A.1 B.2 C.3 D.4 标准答案:B
66. 16某二叉树的前序遍历序列和和中序遍历序列均为abcd,该二叉树的后序遍历序列是()。(2分)
A.abcd B.dcba C.acbd D.dbca 标准答案:B
67. m个顶点的有向完全图有()个弧。 (2分) A.m(m-1)/2 B.m+1 C.m D.m(m-1) 标准答案:D
68. 下列各项键值()序列不是堆的。 (2分)
A.{94,68,23,16,5 B.{94,23,68,5,16 C.{94,23,68,16,5 D.{94,16,68,23,5 标准答案:D
69. 设单链表中指针p指向结点A,q指向新元素结点,若要A之后插入一个新元素,则所需修改指针的操作为()。 (2分) A.p->next=q,q->next=p->next B.q->next=p->next,p->next=q C.p->next=q->next,q->next=p D.p->next=p,q->next=p->next 标准答案:B
70. 在关键字序列(149,138,165,197,176,113,127)中采用最低位优先排序(LSD)基数排序,第一趟之后所得结果为()。 (2分) A.149,138,165,197,176,113,127 B.128,149,165,197,113,176,127 C.128,149,165,197,113,127,176 D.113,127,138,149,165,176,197 标准答案:B
71. 下列术语表示的数据中,()是同义语。 (2分) A.结点 B.数据元素 C.顶点 D.数据项 标准答案:A,B,C
72. 对于采用链式结构的队列,()运算的实现算法的时间复杂度为O(1)。 (2分) A.入队 B.出队 C.求队长 D.队清空 标准答案:A,B
73. 在n个数据元素中进行查找,()方法的最坏时间复杂度为O(n)。 (2分) A.顺序查找 B.折半查找
C.二叉排序树查找 D.斐波那契查找 标准答案:A,C
74. 下列是二叉树4种常见的遍历方法。其中,()属于深度优先遍历。 (2分) A.前序遍历 B.中序遍历 C.后序遍历 D.层序遍历 标准答案:A,B,C
75. 下列()哈希函数构造方法所得的哈希函数,使得查找时间复杂度通常不能到达O(1)。 (2分)
A.直接定地法 B.数字分析法 C.平方取中法 D.折叠法 标准答案:B,C,D
4 第4页共4页
专升本《数据结构》-试卷-答案
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)