专升本《数据结构》模拟题试卷
一. （共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.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的
★检查答案标准答案：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
★检查答案标准答案：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