专升本《数据结构》模拟题试卷

1、专升本数据结构模拟题试卷一 . （共 75 题,共 150 分）1. 数据的基本单位是（） 。 （2 分）A. 数据元素B. 记录C.数据对象D. 数据项检查答案标准答案： A2. （）是数据的不可分割的最小单位。（2 分）A. 数据对象B. 数据元素C.数据类型D. 数据项检查答案标准答案： D3. 算法的空间复杂度是对算法（）的度量。（2 分）A. 时间效率B. 空间效率C.可读性D. 健壮性检查答案标准答案： B4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2 分）A. 栈B. 队列C.串D. 数组检查答案标准答案： B5. 串的长度是指串中所含（）的个数。（2 分）A.

2、不同字符B. 不同字母C.相同字符D. 所有字符检查答案标准答案： D6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（ 2分）A.1B.2C.3D.4检查答案标准答案：B7. 线性表的顺序存储结构是一种（）的存储结构。（2分）A. 顺序存取B. 随机存取C.索引存取D.Hash 存取检查答案标准答案：B8. 数组 a1.m 采用顺序存储，a1和 am 地址分别为1024 和 1150，每个元素占2 字节，则m 是（）。 （ 2 分）A.64B.32C.16D.8检查答案标准答案：A9. 深度为 h 的二叉树，第 h 层最多有（）个结点。（2分）A.hB.2h-1

3、C.2h-1D.2h检查答案标准答案：C10. m 个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分）A.mB.m+1C.2mD.m-1检查答案标准答案：B11. 下面叙述错误的是（） 。 （ 2 分）A. 顺序表是借助物理单元相邻表示数据元素之间的逻辑关系B. 对于空队列进行出队操作过程中发生下溢现象C.有向图的邻接矩阵一定是对称的D. 具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的检查答案标准答案： C12. 以下与数据的存储结构无关的术语是（）。 （2 分）A. 循环队列B. 双向链表D. 数组检查答案标准答案： D13. 在一个长度为n 的链式栈中出栈实现算法的时

4、间复杂度为（）。 （ 2 分）A.O(1)B.O(log n)C.O(n)D.O(n2)检查答案标准答案：A14. 在具有 k 个度数为2 的二叉树中，必有（）个叶子结点。（ 2 分）A.kB.k-1C.2kD.k+1检查答案标准答案：D15. 在关键字序列（ 10,20,30,40,50 ）中，采用折半法查找 20，关键字之间比较需要（）次。（2 分）A.1B.2C.3D.4检查答案标准答案：C16. 16 某二叉树的后序遍历序列和和中序遍历序列均为（）。 （2 分）abcd，该二叉树的前序遍历序列是A.abcdB.dcbaC.acbdD.dbca检查答案标准答案：B17. n 个顶点的无向

5、连通图的生成树，至少有（）个边。（2 分）A.n(n-1)B.n(n-1)/2C.2nD.n-1检查答案标准答案：D18. 可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2 分）A. 队列B. 树D. 集合检查答案标准答案： A19. 假设以数组 A 0.n-1 存放循环队列的元素， 其头指针 front 指向队头元素、 尾指针 rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为（）。 （ 2 分）A.rear= =frontB.(front+1) n= =rearC.rear+1= =frontD.(rear+1) n= =front检查答案标准答案：A20.

6、 序列（ 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)检查答案标准答案：B21. 二叉链表适合作为（）的存储结构。（2 分）A. 队列B. 二叉树D. 森林检查答案标准答案： B,C,D22. 设哈希 (Hash)函数为 H(k)= k % 17, 其中 k 为关键字，关键字()是同义词。（ 2 分）A.44,5,15B.28,45,62C.6,57,125D.201,31,48检查答案标准

7、答案：B,C,D23. 下列各项键值（）序列不是堆的。（2 分）A.94 ， 68，23， 16， 5B.94 ， 23， 68， 5， 16C.94 ， 23， 16， 68， 5D.94 ， 16，68， 23， 5检查答案标准答案：C,D24. 在下列排序方法中， （）的空间复杂度为 O(n) 。其中， n 为参加排序的元素个数。 （ 2 分）A. 选择排序B. 快速排序D. 冒泡排序检查答案标准答案： B,C25. 十字链表适合于（）选作存储结构。（2 分）A. 队列B. 稀疏矩阵D. 二叉树检查答案标准答案： B,C26. 基于数据的逻辑关系，数据的逻辑结构划分为（）基本结构。（2

8、分）A.6 类B.5 类C.4 类D.3 类检查答案标准答案：C27. （）不是算法具有的 5 个特性之一。 （ 2 分） A. 有穷性B. 确定性D. 正确性检查答案标准答案： D28. 算法的时间复杂度是对算法（）的度量。（2 分）A. 时间效率B. 空间效率D. 健壮性检查答案标准答案： A29. 线性表若采用链式存储结构时，要求结点的存储单元地址（）。 （ 2 分）A. 必须是连续的B. 部分地址必须是连续的D. 连续或不连续都可以检查答案标准答案： D30. 二维数组通常采用顺序存储，其优点是（）。 （ 2 分）A. 便于增加存储空间B. 防止下标溢出D. 便于依据下标进行随机存取检

9、查答案标准答案： D31. 采用顺序存储的线性表，若表长为 n，在第 i 号元素之后插入一个元素时，需要移动（）个元素。 （ 2 分）A.i+1B.iC.n-iD.n-i+1检查答案标准答案：C32. 若已知一个栈的入栈序列是A.1 、4、3、2B.3 、 4、1、 2C.4、 3、2、 1D.2、3、4、11、 2、 3、 4，其出栈序列不可能为_。 （ 2 分）检查答案标准答案：B33. 数组 a1.256 采用顺序存储， a 的首地址为 10，每个元素占 2 字节，则 a21 的地址是（）。（2 分）A.10B.30C.50D.70检查答案标准答案：C34. 深度为 h 的完全二叉树至少

10、有（）个叶子结点。（2 分）A.2(h-1)+1B.2(h-2)+1C.2h-1D.2h-2检查答案标准答案：D35. 若二叉树对应的二叉链表共有m 个非空链域，则该二叉树有（）个结点的二叉树。（ 2分）A.mB.m-1C.m+1D.2m检查答案标准答案：B36. 下面叙述错误的是（） 。 （ 2 分）A. 单链表是借助指针表示数据元素之间的逻辑关系B. 在顺序栈的入栈操作过程中可能发生上溢现象D. 无向图的邻接矩阵一定是对称的检查答案标准答案： C37. 以下（）术语与数据的存储结构无关（2 分）A. 栈B. 哈希表D. 双向链表检查答案标准答案： A38. 在一个长度为n 的链式队列中入队

11、实现算法的时间复杂度为（）。 （ 2 分）A.O(1)B.O(log n)C.O(n)D.O(n2)检查答案标准答案：A39. 队列的出队操作是指（）操作。（2 分）A. 队尾删除B. 队头删除C.队尾插入D. 队头插入检查答案标准答案： B40. 在关键字序列（ 10,15,20,25,30 ）中采用折半法查找 25，依次与（）关键字进行了比较。（2 分）A.30,25B.20,25C.20， 30， 25D.25检查答案标准答案：B41. 16 某二叉树的前序遍历序列和和中序遍历序列分别为abcd 和 bcad，该二叉树的后序遍历序列是（） 。 （ 2 分）A.cbdaB.dcbaC.ab

12、cdD.dcba检查答案标准答案：A42. 所占用的存储空间大小仅与图的顶点个数相关的存储结构是（）。 （ 2 分）A. 邻接表B. 逆邻接表C.十字链表D. 邻接矩阵检查答案标准答案： D43. 可以采用（）这种数据结构，实现图的深度优先遍历运算。（ 2 分）A. 队列B. 树D. 集合检查答案标准答案： C44. 线性表采用带头结点单链表实现，head 为头指针，则判断表空的条件为（）。 （ 2 分）A.head= NULLB.head!=NULLC.head->next=NULLD.head->next !=NULL检查答案标准答案：C45. 在关键字序列（ 35， 10，

13、15，20， 25）中采用最低位优先排序 (LSD) 基数排序，第一趟之后所得结果为（） 。 （ 2 分）A.10 ，20， 15，25， 35B.10 ， 20， 35， 15， 25C.20， 10， 35， 25， 15D.20 ，10， 35，15， 25检查答案标准答案：B46. 下列逻辑结构中， （）为线性结构。（2 分）A. 栈B. 队列D. 二叉树检查答案标准答案： A,B,C47. 深度为 3 的二叉树可能的结点个数是（） 。 （2 分）A.1B.2C.3D.4检查答案标准答案：A,B48. 下列各项键值（）序列是大顶堆的。（2 分）A.23 ， 68，94， 16， 5B.

14、94 ， 68， 23， 16， 5C.94 ， 23， 68， 16， 5D.94 ， 16，68， 23， 5检查答案标准答案：B,C49. 下列（）是限制了插入和删除操作的特殊线性表。（2 分）A. 栈B. 队列D. 数组检查答案标准答案： A,B50. 对一棵二叉排序树，用（）方法进行遍历，不一定得到各结点键值的有序序列。（ 2分）A. 先根遍历B. 中根遍历D. 层次遍历检查答案标准答案： A,C,D51. 数据的最小单位是（） 。 （ 2 分）A. 数据元素B. 记录D. 数据项检查答案标准答案： D52. 算法是对某一类问题求解步骤的有限序列。其中，（）是算法具有的5 个特性之一

15、。（ 2分）A. 有穷性B. 正确性D. 健壮性检查答案标准答案： A53. （）是数据的逻辑结构。（2 分）A. 顺序表B. 链表D. 十字链表检查答案标准答案： C54. （）是限制了插入和删除操作在一端进行的线性表。（2 分）A. 栈B. 队列D. 数组检查答案标准答案： A55. （）是限制了插入和删除操作分别在两端进行的线性表。（2 分）A. 栈B. 队列D. 数组检查答案标准答案： B56. 用链表表示线性表的优点是（） 。 （2 分）A. 便于插入和删除B. 便于随机存取D. 数据元素的物理顺序与逻辑顺序相同检查答案标准答案： A57. 若已知一个栈的入栈序列是1、 2、 3、

16、4，其出栈序列不可能为（） 。 （2 分）A.1 、4、3、2B.2 、 3、4、 1C.4、 3、2、 1D.3、4、1、2检查答案标准答案：D58. 串下列关于串的叙述中，正确的是（） 。 （ 2 分）A.2 个串的长度相等，则2 个串相等B. 空串至少包一个空格C.替换操作可以实现字符的删除D. 一个串的长度至少是1检查答案标准答案：C59. 深度为 h 的二叉树，第 h 层至少有（）个结点。（2 分）A.0B.1C.8D.16检查答案标准答案：B60. 假设 n 0，在程序段y=0;while(y+1)*(y+1)<=n)次数是（）。其中， x 表示对 x 取整运算。（2 分）y

17、+; 中，标记 的语句实际执行的A.nB.C.n2检查答案标准答案：C61. 下面叙述错误的是（） 。 （ 2 分）A. 在集合 1 ，2， 3， 4， 5 中元素 1 是 2 的直接前驱B. 二叉排序树的中序遍历序列一定是有序的C.有 3 个结点的不同形态二叉树的数目为5D. 哈夫曼树中所有结点的孩子数目只可能为2 或者为0检查答案标准答案：A62. 以下数据结构中， （）是线性结构。（2 分）A. 广义表B. 二叉树D. 串检查答案标准答案： D63. 在一个长度为n 的顺序表中删除一个元素的算法的时间复杂度为（）。 （ 2 分）A.O(1)B.O(log n)C.O(n)D.O(n2)检

18、查答案标准答案：C64. 如果一个 huffman 树含有 n 个叶子，则该树必有（）的结点。（2 分）A.n+1B.2n+1C.2nD.2n-1检查答案标准答案：D65. 在关键字序列（ 10,15,20,25,30 ）中，采用折半法查找 25，关键字之间比较需要（）次。（2 分）A.1B.2C.3D.4检查答案标准答案：B66. 16 某二叉树的前序遍历序列和和中序遍历序列均为（）。 （2 分）abcd，该二叉树的后序遍历序列是A.abcdB.dcbaC.acbdD.dbca检查答案标准答案：B67. m 个顶点的有向完全图有（）个弧。（2 分）A.m(m-1)/2B.m+1C.mD.m(

19、m-1)检查答案标准答案：D68. 下列各项键值（）序列不是堆的。（2 分）A.94 ， 68，23， 16， 5B.94 ， 23， 68， 5， 16C.94 ， 23， 68， 16， 5D.94 ， 16，68， 23， 5检查答案标准答案：D69. 设单链表中指针 p 指向结点 A ，q 指向新元素结点，若要需修改指针的操作为（） 。 （2 分）A 之后插入一个新元素，则所A.p->next=q，q->next=p->nextB.q->next=p->next C.p->next=q->next， p->next=q， q->next=pD.p->next=p，q