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

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

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

（共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[l]和a[m]地

址分别为1024和1150,每个元素占2字节，则

m是。。（2分）

A.64

B.32

C.16

D.8

★检查答案标准答案：A

9.深度为h的二叉树，第h层最多有（）个结

点。（2分）

A.h

B.2h-l

C.2h-l

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(logn)

C.0(n)

D.0(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某二叉树的后序遍历序列和和中序遍历

序列均为abed,该二叉树的前序遍历序列是()。

(2分)

A.abed

B.deba

C.aebd

D.dbea

★检查答案标准答案：B

17.n个顶点的无向连通图的生成树，至少有

()个边。(2分)

A.n(n-l)

B.n(n-l)/2

C.2n

D.n-1

★检查答案标准答案：D

18.可以采用()这种数据结构，实现二叉树的

层次遍历运算。(2分)

A.队列

B.树

C.栈

D.集合

★检查答案标准答案：A

19.假设以数组A[O..n-口存放循环队列的元

素，其头指针front指向队头元素、尾指针rear

指向队尾元素一个，则在少用一个元素空间的前

提下，队列空的判定条件为()。(2分)

A.rear==front

B.(front+1)%n==rear

C.rear+l==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.在下列排序方法中，()的空间复杂度为

0(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［l..256］采用顺序存储，a的首地址

为10,每个元素占2字节,则aE21］的地址是（）。

（2分）

A.10

B.30

C.50

D.70

★检查答案标准答案：C

34.深度为h的完全二叉树至少有（）个叶子结

点。（2分）

A.2（h-1）+1

B.2（h-2）+l

C.2h-l

D.2h-2

★检查答案标准答案：D

35.若二叉树对应的二叉链表共有m个非空链

域，则该二叉树有（）个结点的二叉树。（2

分）

A.m

B.m-l

C.m+1

D.2m

★检查答案标准答案：B

36.下面叙述错误的是（）。（2分）

A.单链表是借助指针表示数据元素之间的逻辑

关系

B.在顺序栈的入栈操作过程中可能发生上溢现

象

C.具有相同的叶子个数和具有相同的叶子权值

的赫夫曼树是唯一的

D.无向图的邻接矩阵一定是对称的

★检查答案标准答案：C

37.以下()术语与数据的存储结构无关(2

分)

A.栈

B.哈希表

C.线索树

D.双向链表

★检查答案标准答案：A

38.在一个长度为n的链式队列中入队实现算

法的时间复杂度为()。(2分)

A.0⑴

B・O(logn)

C.O(n)

D.0(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某二叉树的前序遍历序列和和中序遍历

序列分别为abed和bead,该二叉树的后序遍历

序列是。。（2分）

A.cbda

B.dcba

C.abed

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）基数排序，第一趟之后

所得结果为O。（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.下列各项键值（）序列是大顶堆的。

分）

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.对一棵二叉排序树，用（）方法进行遍历,

不一定得到各结点键值的有序序列O（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分）

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.假设在程序段

{y=0;while（（y+1）*（y+1）<=n）@y++;中，标记@

的语句实际执行的次数是。。其中，［x］表示对

X取整运算。（2分）

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.0⑴

B・O（logn）

C.O（n）

D.0(n2)

★检查答案标准答案：C

64.如果一个huffman树含有n个叶子，则该树

必有。的结点。(2分)

A.n+1

B.2n+l

C.2n

D.2n-l

★检查答案标准答案：D

65.在关键字序列(10,15,20,25,30)中，采用

折半法查找25,关键字之间比较需要。次。(2

分)

A.1

B.2

C.3

D.4

★检查答案标准答案：B

66.16某二叉树的前序遍历序列和和中序遍历

序列均为abed,该二叉树的后序遍历序列是()。

(2分)

A.abed

B・deba

C.aebd

D.dbea

★检查答案标准答案：B

67.m个顶点的有向完全图有()个弧。(2分)

A.m(m-l)/2

B.m+1

C.m

D.m(m-l)

★检查答案标准答案：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