山东某大学《数据结构与算法(二)》期末考试复习题及参考答案

山东师范大学成人教育期末考试复习题

一.单选题

1.具有n个结点的连通图至少有（）条边。

A.n-1

B.n

C.n（n-l）/2

D.2n

参考答案：A

2.在长度为n的顺序表的第i个位置上插入一个元素（Bi"+1）,元素的移动次数为：（）。

A.n-i+1

B.n-i

C.i

D.i-1

参考答案：A

3.具有10个叶子结点的二叉树中有（）个度为2的结点。

A.8

B.9

C.10

D.11

参考答案：B

4.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A.43467

B.1

C.2

D.4

参考答案：B

5.设有一个栈，元素依次进栈的顺序为A、B、C、D、E,下列（）是不可能的出栈序列。

A.A,B,C,D,E

B.B,C,D,E,A

C.E,A,B,C,D

D.E,D,C,B,A

参考答案：c

6.在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。

A.希尔排序

B.冒泡排序

C.直接插入排序

D.直接选择排序

参考答案：D

7.栈和队列的共同点是（）。

A.都是先进后出

B.都是先进先出

C.只允许在端点处插入和删除元素

D.没有共同点

参考答案：C

8.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列

为()。

A.q=p-u003enext；p-u003edata=q-u003edata；p-u003enext=q-u003enext；free(q)；

B.q=p-u003enext；q-uOO3edata=p-uOO3edata；p-uOO3enext=q-uOO3enext；free(q)；

C.q=p-u003enext；p-u003enext=q-u003enext；free(q)；

D.q=p-u003enext；p-uOO3edata=q-uOO3edata；free(q)；

参考答案：A

9.对于一个具有N个顶点的图，若用邻接矩阵表示，则该矩阵的大小为()。

A.N

B.(N-1)2

C.(N+1)2

D.N2

参考答案：D

10.链表不具备的特点是。。

A.可随机访问任一结点

B.插入删除不需要移动元素

C.不必事先估计存储空间

D.所需空间与其长度成正比

参考答案：A

11.有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100),当折半查

找值为82的结点时，()次比较后查找成功。

A.11

B.5

C.4

D.8

参考答案：C

12.采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为()。

A.O(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

参考答案：D

13.在线索化树中，每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息，

还是线索化信息，若0标识树结构信息，1标识线索，对应叶结点的左右链域，应标识为()o

A.0

B.1

C.10

D.11

参考答案：D

14.对一个满二叉树，m个叶子，n个结点，深度为h,则()。

A.n=h+m

B.h+m=2n

C.m=h-1

D.n=2h-1

参考答案：D

15.以下说法正确的是()。

A.数据项是数据的基本单位

B.数据元素是数据的最小单位

C.数据结构是带结构的数据项的集合

D.一些表面上很不相同的数据可以有相同的逻辑结构

参考答案：D

16.直接选择排序的时间复杂度为()。(n为元素个数)

A.O(n)

B.O(log2n)

C.O(nlog2n)

D.0(n2)

参考答案：D

17.查找效率最高的二叉排序树是()。

A.所有结点的左子树都为空的二叉排序树

B.所有结点的右子树都为空的二叉排序树

C.平衡二叉树

D.没有左子树的二叉排序树

参考答案：C

18.一个非空广义表的表头()。

A.不可能是子表

B.只能是子表

C.只能是原子

D.可以是子表或原子

参考答案：D

19.数据结构在计算机内存中的表示是指()。

A.数据的存储结构

B.数据结构

C.数据的逻辑结构

D.数据元素之间的关系

参考答案：A

20.串是一种特殊的线性表，其特殊性体现在().

A.可以顺序存储

B.数据元素是一个字符

C.可以链式存储

D.数据元素可以是多个字符

参考答案：B

21.下面关于B树和B+树的叙述中，不正确的结论是()o

A.B树和B+树都能有效的支持顺序查找

B.B树和B+树都能有效的支持随机查找

C.B树和B+树都是平衡的多叉树

D.B树和B+树都可用于文件索引结构

参考答案：A

22.在以下的叙述中，正确的是（）。

A.线性表的顺序存储结构优于链表存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

参考答案：B

23.若不带头结点的单链表的头指针为head,则该链表为空的判定条件是（）。

A.head=='

B.head-u003enext=='

C.head!='

D.head-u003enext==head

参考答案：A

24.采用邻接表存储的图的深度优先遍历算法类似于二叉树的。。

A.先序遍历

B.中序遍历

C.后序遍历

D.按层遍历

参考答案：A

25.串s="DataStructure”中长度为3的子串的数目是（）。

A.9

B.11

C.12

D.14

参考答案：C

26.在循环双链表的p所指的结点之前插入s所指结点的操作是（）。

A.p-u003eprior=s；s-u003enext=p；p-u003eprior-u003enext=s；s-u003eprior=p-u003eprior

B.p-u003eprior=s；p-u003eprior-u003enext=s；s-uOO3enext=p；s-u003eprior=p-u003eprior

C.s-uOO3enext=p；s-u003eprior=p-u003eprior；p-u003eprior=s；p-u003eprior-u003enext=s

D.s-uOO3enext=p；s-u003eprior=p-u003eprior；p-u003eprior-u003enext=s；p-u003eprior=s

参考答案：D

27.数组A[0...4,-1…-3,5…刀中含有的元素个数是（）,,

A.55

B.45

C.36

D.16

参考答案：B

28.设一组初始记录关键字序列（5,2,6,3,8）,以第一个记录关键字5为基准进行一趟快

速排序的结果为（）。

A.2,3,5,8,6

B.3,2,5,8,6

C.3,2,5,6,8

D.2,3,6,5,8

参考答案：C

已知一个图如图所示，由该图行到的一种拓朴序列为（）。

B.vlv2v3v4v5v6

C.vlv4v2v3v6v5

D.vlv2v4v6v3v5

参考答案：A

30.引起循环队列队头位置发生变化的操作是（）。

A.出队

B.入队

C.取队头元素

D.取队尾元素

参考答案：A

31.串的长度是指（）。

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

参考答案：B

32.对一个算法的评价，不包括如下（）方面的内容.

A.健壮性和可读性

B.并行性

C.正确性

D.时空复杂度

参考答案：B

33.字符串通常采用的两种存储方式是（）。

A.散列存储和索引存储

B.索引存储和链式存储

C.顺序存储和链式存储

D.散列存储和顺序存储

参考答案：C

34.递归通常选用的存储结构是（）。

A.栈

B.线性表

C.队列

D.二叉排序树

参考答案：A

35.下面程序的时间复杂为()ofor(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j++)t=t*j；

s=s+t；}

A.O(n)

B.O(n2)

C.0(n3)

D.O(n4)

参考答案：B

36.设二维数组A[l?m,l?n]按行存储在数组B中，则二维数组元素在一维数组B中的下

标为()。

A.n*(i-l)+j

B.n*(i-l)+j-l

D.j*m+i-l

参考答案：A

37.下面关于线性表的叙述中，错误的是()。

A.线性表采用顺序存储,必须占用一片连续的存储单元

B.线性表采用顺序存储,便于进行插入和删除操作

C.线性表采用链式存储,不必占用一片连续的存储单元

D.线性表采用链式存储,便于进行插入和删除操作

参考答案：B

38.在以下的叙述中，正确的是()。

A.线性表的顺序存储结构优于链表存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

参考答案：B

39.非空的循环单链表head的尾结点(由p所指向)满足()。

A.p-u003enext=='

B.p=='

C.p-u003enext==head

D.p==head

参考答案：C

40.若串S='software’,其子串的数目是()。

A.8

B.37

C.36

D.9

参考答案：B

41.在决定选取何种存储结构时，一般不考虑()。

A.各结点的值如何

B.结点个数的多少

C.对数据有哪些运算

D.所用的编程语言实现这种结构是否方便

参考答案：A

42.对于线性表<7,34,55,25,64,46,20,10）进行散列存储时，若选用H（K）=K%9

作为散列函数，则散列地址为1的元素有（）个，

A.1

B.2

C.3

D.4

参考答案：D

43.以下说法错误的是（）。

A.散列法存储的思想是由关键字值决定数据的存储地址

B.散列表的结点中只包含数据元素自身的信息，不包含指针

C.负载因子是散列表的一个重要参数，它反映了散列表的饱满程度

D.散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。

参考答案：B

44.线性表的顺序存储结构是一种（）。

A.随机存取的存储结构

B.顺序存取的存储结构

C.索引存取的存储结构

D.Hash存取的存储结构

参考答案：A

45.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若

p->nextfnext=head,贝ij（）。

A.p指向头结点

B.p指向尾结点

C.*p的直接后继是头结点

D.*P的直接后继是尾结点

参考答案：D

46.允许对队列进行的操作有（）。

A.对队列中的元素排序

B.取出最近进队的元素

C.在队头元素之前插入元素

D.删除队头元素

参考答案：D

47.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执

行出队操作后其头指针front值为（）。

A.front=front+1

B.front=（front+l）%（m-l）

C.front=（front-l）%m

D.front=（front+l）%m

参考答案：D

48.在数据结构中，与所使用的计算机无关的是数据的（）结构。

A.逻辑

B.存储

C.逻辑和存储

D.物理

参考答案：A

49.与单链表相比，双链表的优点之一是()o

A.插入、删除操作更简单

B.可以进行随机访问

C.可以省略表头指针或表尾指针

D.顺序访问相邻结点更灵活

参考答案：D

50.对矩阵进行压缩存储是为了()。

A.方便运算

B.方便存储

C.提高运算速度

D.减少存储空间

参考答案：D

已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为

(，一

51.

A.acefbd

B.acbdfe

C.acbdef

D.acdbfe

参考答案：c

52.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是()

A.(e,f)

B.((e.f))

c.(f)

D.()

参考答案：B

53.设某二叉树中度数为0的结点数为N0,度数为1的结点数为NL度数为2的结点数为

N2,则下列等式成立的是()。

A.NO=N1+1

B.N0=NI+N2

C.N0=N2+l

D.NO=2N1+I

参考答案：C

54.在下述论述中，正确的是()。①只有一个结点的二叉树的度为0；②二叉树的度为2；

③二叉树的左右子树可任意交换；④深度为K的顺序二叉树的结点个数小于或等于深度

相同的满二叉树。

A.①②③

B.②③④

C.②④

D.①④

参考答案：D

55.在数据结构中，从逻辑上可以把数据结构分为（）。

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.线性结构和非线性结构

D.内部结构和外部结构

参考答案：C

56.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（

A.4

B.5

C.8

D.9

参考答案：C

57.设有两个串p和q,求q在p中首次出现的位置的运算称为（）。

A.连接

B.模式匹配

C.求子串

D.求串长

参考答案：B

58.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（）。

A.单链表

B.静态链表

C.线性链表

D.顺序存储结构

参考答案：B

59.稀疏矩阵一般的压缩存储方式有两种，即（）。

A.二维数组和三维数组

B,三元组和散列

C.三元组和十字链表

D.散列和十字链表

参考答案：C

60.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入

已排序序列的正确位置上的方法，称为（）。

A.希尔排序

B.冒泡排序

C.插入排序

D.选择排序

参考答案：C

二.判断题

请选择正确的答案。

61.对任何数据结构链式存储结构一定优于顺序存储结构。（）

参考答案：错误

62.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右

孩子的值。()

参考答案：错误

63.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()

参考答案：错误

64.强连通图的各顶点间均可达。()

参考答案：正确

65.拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。()

参考答案：错误

66.散列法存储的思想是由关键字值决定数据的存储地址。()

参考答案：正确

67.对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。

()

参考答案：错误

68.在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次

序仍然保持不变，称这种排序为稳定排序。()

参考答案：正确

69.冒泡排序算法关键字比较的次数与记录的初始排列次序无关。()

参考答案：错误

70.队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。()

参考答案：错误

单选题

1.直接选择排序的时间复杂度为()。(n为元素个数)

A.O(n)

B.O(log2n)

C.O(nlog2n)

D.O(n2)

参考答案：D

2.设有两个串p和q,求q在p中首次出现的位置的运算称为()»

A.连接

B.模式匹配

C.求子串

D.求串长

参考答案：B

3.与单链表相比，双链表的优点之一是（）。

A.插入、删除操作更简单

B.可以进行随机访问

C.可以省略表头指针或表尾指针

D.顺序访问相邻结点更灵活

参考答案：D

4.在下述论述中，正确的是（）。①只有一个结点的二叉树的度为0；②二叉树的度为2；

③二叉树的左右子树可任意交换；④深度为K的顺序二叉树的结点个数小于或等于深度

相同的满二叉树。

A.①②③

B.②③④

C.②④

D.①④

参考答案：D

5.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（）。

A.4

B.5

C.8

D.9

参考答案：C

6.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行

出队操作后其头指针front值为（）。

A.front=front+1

B.front=(front+l)%(m-l)

C.front=(front-l)%m

D.front=(front+l)%m

参考答案：D

7.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（）。

A.单链表

B.静态链表

C.线性链表

D.顺序存储结构

参考答案：B

8.在数据结构中，从逻辑上可以把数据结构分为（）。

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.线性结构和非线性结构

D.内部结构和外部结构

参考答案：C

9.下面关于线性表的叙述中，错误的是（）。

A.线性表采用顺序存储，必须占用一片连续的存储单元

B.线性表采用顺序存储，便于进行插入和删除操作

C.线性表采用链式存储，不必占用一片连续的存储单元

D.线性表采用链式存储，便于进行插入和删除操作

参考答案：B

10.数组A[0…4,・1…-3,5…刀中含有的元素个数是()。

A.55

B.45

C.36

D.16

参考答案：B

11.在数据结构中，与所使用的计算机无关的是数据的()结构。

A.逻辑

B.存储

C.逻辑和存储

D.物理

参考答案：A

12.在线索化树中，每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息，

还是线索化信息，若0标识树结构信息，1标识线索，对应叶结点的左右链域，应标识为()°

A.0

B.1

C.10

D.11

参考答案：D

13.设某二叉树中度数为0的结点数为N0,度数为1的结点数为NI,度数为2的结点数为

N2,则下列等式成立的是()。

A.NO=N1+1

B.N0=NI+N2

C.N0=N2+l

D.NO=2N1+I

参考答案：C

14.线性表的顺序存储结构是一种()。

A.随机存取的存储结构

B.顺序存取的存储结构

C.索引存取的存储结构

D.Hash存取的存储结构

参考答案：A

15.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记

录的一趟快速排序结束后的结果为()。

A.10,15,14,18,20,36,40,21

B.10,15,14,18,20,40,36,21

C.10,15,14,20,18,40,36,21

D.15,10,14,18,20,36,40,21

参考答案:A

16.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是()o

A.edcba

B.decba

C.dceab

D.abcde

参考答案：c

17.广义表（（a）,a）的表头是C,表尾是（）。

A.a

B.（）

C.（a）

D.（（a））

参考答案：C

18.字符串通常采用的两种存储方式是（）。

A.散列存储和索引存储

B.索引存储和链式存储

C.顺序存储和链式存储

D.散列存储和顺序存储

参考答案：C

19.设二维数组A［l?m,l?n］按行存储在数组B中，则二维数组元素A［川在一维数组B中的下

标为（）。

A.n*（i-l）+j

B.n*（i-l）+j-l

C.i*（j-1）

D.j*m+i-l

参考答案：A

20.允许对队列进行的操作有（）。

A.对队列中的元素排序

B.取出最近进队的元素

C.在队头元素之前插入元素

D.删除队头元素

参考答案；D

21.在决定选取何种存储结构时，一般不考虑（）。

A.各结点的值如何

B.结点个数的多少

C.对数据有哪些运算

D.所用的编程语言实现这种结构是否方便

参考答案：A

22.在长度为n的顺序表的第i个位置上插入一个元素（lSiVn+l）,元素的移动次数为：（）。

A.n-i+1

B.n-i

C.i

D.i-1

参考答案：A

23.串是一种特殊的线性表，其特殊性体现在（）。

A.可以顺序存储

B.数据元素是一个字符

C.可以链式存储

D.数据元素可以是多个字符

参考答案：B

24.对矩阵进行压缩存储是为了（）。

A.方便运算

B.方便存储

C.提高运算速度

D.减少存储空间

参考答案：D

25.串s="DataStructure”中长度为3的子串的数目是（）。

A.9

B.11

C.12

D.14

参考答案：C

26.下面关于B树和B+树的叙述中，不正确的结论是（）1,

A.B树和B+树都能有效的支持顺序查找

B.B树和B+树都能有效的支持随机查找

C.B树和B+树都是平衡的多叉树

D.B树和B+树都可用于文件索引结构

参考答案：A

27.在以下的叙述中，正确的是（）。

A.线性表的顺序存储结构优于链表存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

参考答案：B

28.对于线性表（7,34,55,25,64,46,20,10）进行散列存储时，若选用H（K）=K%9

作为散列函数，则散列地址为1的元素有（）个，

A.1

B.2

C.3

D.4

参考答案：D

29.在以下的叙述中，正确的是（）。

A.线性表的顺序存储结构优于链表存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

参考答案：B

30.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A.43467

B.1

C.2

D.4

参考答案：B

31.递归通常选用的存储结构是（）。

A.栈

B.线性表

C.队列

D.二叉排序树

参考答案：A

32.对一个算法的评价，不包括如下（）方面的内容。

A.健壮性和可读性

B.并行性

C.正确性

D.时空复杂度

参考答案：B

33.串的长度是指（）。

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

参考答案：B

34.非空的循环单链表head的尾结点（由p所指向）满足（）。

A.p-uOO3enext=='

B.p==*

C.p-uOO3enext==head

D.p==head

参考答案：c

35.数据结构在计算机内存中的表示是指（）。

A.数据的存储结构

B.数据结构

C.数据的逻辑结构

D.数据元素之间的关系

参考答案：A

36.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若

p玲next玲next=head,贝！I（）＜）

A.p指向头结点

B.p指向尾结点

C.*p的直接后继是头结点

D.*P的直接后继是尾结点

参考答案：D

37.在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。

A.希尔排序

B.冒泡排序

C.直接插入排序

D.直接选择排序

参考答案：D

38.稀疏矩阵一般的压缩存储方式有两种，即()。

A.二维数组和三维数组

B,三元组和散列

C.三元组和十字链表

D.散列和十字链表

参考答案：C

39.若串S=&>ftware',其子串的数目是()。

A.8

B.37

C.36

D.9

参考答案：B

40.对于一个具有N个顶点的图，若用邻接矩阵表示，则该矩阵的大小为()。

A.N

B.(N-1)2

C.(N+1)2

D.N2

参考答案：D

41.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列

为()。

A.q=p-u003enext；p-uOO3edata=q-uOO3edata；p-uOO3enext=q-uOO3enext；free(q)；

B.q=p-u003enext；q-uOO3edata=p-uOO3edata；p-u003enext=q-u003enext；free(q)；

C.q=p-u003enext；p-u003enext=q-u003enext；free(q)；

D.q=p-u003enext；p-uOO3edata=q-uOO3edata；free(q)；

参考答案：A

42.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入

已排序序列的正确位置上的方法，称为()。

A.希尔排序

B.冒泡排序

C.插入排序

D.选择排序

参考答案：C

43.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快

速排序的结果为()。

A.2,3,5,8,6

B.3,2,5,8,6

C.3,2,5,6,8

D.2,3,6.5,8

参考答案：C

44.具有10个叶子结点的二叉树中有()个度为2的结点。

A.8

B.9

C.10

D.ll

参考答案：B

45.采用邻接表存储的图的深度优先遍历算法类似于二叉树的()o

A.先序遍历

B.中序遍历

C.后序遍历

D.按层遍历

参考答案：A

46.具有n个结点的连通图至少有()条边。

A.n-1

B.n

C.n(n-l)/2

D.2n

参考答案：A

47.若不带头结点的单链表的头指针为head,则该链表为空的判定条件是()。

A.head=='

B.head-u003enext=='

C.head!='

D.head-uOO3enext==head

参考答案：A

48.对一个满二叉树，m个叶子，n个结点，深度为h,贝|()。

A.n=h+m

B.h+m=2n

C.m=h-1

D.n=2h-l

参考答案：D

49.栈和队列的共同点是()。

A.都是先进后出

B.都是先进先出

C.只允许在端点处插入和删除元素

D.没有共同点

参考答案：C

50.以下说法错误的是()。

A.散列法存储的思想是由关键字值决定数据的存储地址

B.散列表的结点中只包含数据元素自身的信息，不包含指针

C.负载因子是散列表的一个重要参数，它反映了散列表的饱满程度

D.散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。

参考答案：B

51.在循环双链表的p所指的结点之前插入s所指结点的操作是()。

A.p-u003eprior=s；s-u003enext=p；p-u003eprior-u003enext=s；s-u003eprior=p-u003eprior

B.p-u003eprior=s；p-u003eprior-u003enext=s；s-u003enext=p；s-u003eprior=p-u003eprior

C.s-u003enext=p；s-u003eprior=p-u003eprior；p-u003eprior=s；p-u003eprior-u003enext=s

D.s-u003enext=p；s-u003eprior=p-u003eprior；p-u003eprior-u003enext=s；p-u003eprior=s

参考答案：D

52.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是()

A.(e,f)

B.((e，f))

c.(f)

D.()

参考答案：B

53.下面程序的时间复杂为()。for(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j++)t=t*j；

s=s+t；}

A.O(n)

B.O(n2)

C.0(n3)

D.O(n4)

参考答案：B

54.以下说法正确的是()。

A.数据项是数据的基本单位

B.数据元素是数据的最小单位

C.数据结构是带结构的数据项的集合

D.一些表面上很不相同的数据可以有相同的逻辑结构

参考答案：D

己知一个图如图所示，由该图行到的一种拓朴序列为()。,

A.vlv4v6v2v5v3

B.vlv2v3v4v5v6

C.vlv4v2v3v6v5

D.vlv2v4v6v3v5

参考答案：A

56.采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为()o

A.0(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

参考答案：D

57.设有一个栈，元素依次进栈的顺序为A、B、C、D、E,下列()是不可能的出栈序列。

A.A,B,C,D,E

B.B,C,D,E,A

C.E,A,B,C»D

D.E,D,C,B,A

参考答案：c

58.链表不具备的特点是()。

A.可随机访问任一结点

B.插入删除不需要移动元素

C.不必事先估计存储空间

D.所需空间与其长度成正比

参考答案：A

59.查找效率最高的二叉排序树是()。

A.所有结点的左子树都为空的二叉排序树

B.所有结点的右子树都为空的二叉排序树

C.平衡二叉树

D.没有左子树的二叉排序树

参考答案：C

60.有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100),当折半查

找值为82的结点时，()次比较后查找成功。

A.11

B.5

C.4

D.8

参考答案：C

二.判断题

请选择正确的答案。

61.一个广义表的表头总是一个广义表。()

参考答案：错误

62.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右

孩子的值。()

参考答案：错误

63.强连通图的各顶点间均可达。()

参考答案：正确

64.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。()

参考答案：错误

65.直接选择排序算法在最好情况下的时间复杂度为O(n)。()

参考答案：错误

66.在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次

序仍然保持不变，称这种排序为稳定排序。()

参考答案：正确

67.循环链表不是线性表。()

参考答案：错误

68.散列法存储的思想是由关键字值决定数据的存储地址。()

参考答案：正确

69.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()

参考答案：错误

70.具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。()

参考答案：正确

单选题

1.数组A0..4,5...7］中含有的元素个数是().

A.55

B.45

C.36

D.16

参考答案：B

2.稀疏矩阵一般的压缩存储方式有两种，即()。

A.二维数组和三维数组

B.三元组和散列

C.三元组和十字链表

D.散列和十字链表

参考答案：C

3.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。

A.43467

B.1

C.2

D.4

参考答案：B

4.下面程序的时间复杂为()ofor(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j++)t=t*j；

s=s+t；}

A.O(n)

B.O(n2)

C.O(n3)

D.O(n4)

参考答案：B

5.在下述论述中，正确的是()。①只有一个结点的二叉树的度为0;②二叉树的度为2；

③二叉树的左右子树可任意交换；④深度为K的顺序二叉树的结点个数小于或等于深度

相同的满二叉树。

A.①②③

B.②③④

C.②④

D.①④

参考答案：D

6.串是一种特殊的线性表，其特殊性体现在()。

A.可以顺序存储

B.数据元素是一个字符

C.可以链式存储

D.数据元素可以是多个字符

参考答案：B

7.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选用H(K)=K%9

作为散列函数，则散列地址为1的元素有()个，

A.1

B.2

C.3

D.4

参考答案：D

8.下面关于B树和B+树的叙述中，不正确的结论是()«

A.B树和B+树都能有效的支持顺序查找

B.B树和B+树都能有效的支持随机查找

C.B树和B+树都是平衡的多叉树

D.B树和B+树都可用于文件索引结构

参考答案：A

9.一个非空广义表的表头()。

A.不可能是子表

B.只能是子表

C.只能是原子

D.可以是子表或原子

参考答案：D

10.查找效率最高的二叉排序树是()。

A.所有结点的左子树都为空的二叉排序树

B.所有结点的右子树都为空的二叉排序树

C.平衡二叉树

D.没有左子树的二叉排序树

参考答案：C

已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为

(),"

11.

A.acefbd

B.acbdfe

C.acbdef

D.acdbfe

参考答案：c

12.对一个算法的评价，不包括如下（）方面的内容。

A.健壮性和可读性

B.并行性

C.正确性

D.时空复杂度

参考答案：B

13.栈和队列的共同点是（）。

A.都是先进后出

B.都是先进先出

C.只允许在端点处插入和删除元素

D.没有共同点

参考答案：C

14.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入

己排序序列的正确位置上的方法，称为（）。

A.希尔排序

B.冒泡排序

C插入排序

D.选择排序

参考答案：C

15.在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。

A.希尔排序

B.冒泡排序

C.直接插入排序

D.直接选择排序

参考答案；D

16.允许对队列进行的操作有（）。

A.对队列中的元素排序

B.取出最近进队的元素

C.在队头元素之前插入元素

D.删除队头元素

参考答案：D

17.在决定选取何种存储结构时，一般不考虑（）。

A.各结点的值如何

B.结点个数的多少

C.对数据有哪些运算

D.所用的编程语言实现这种结构是否方便

参考答案：A

18.对一个满二叉树，m个叶子，n个结点，深度为h,则（）。

A.n=h+m

B.h+m=2n

C.m=h-1

D.n=2h-1

参考答案：D

19.对广义表1=心力),仁可,9用)执行操作12讣向1(1_))的结果是()

A.(e,f)

B.((e，f))

c.(f)

D.()

参考答案：B

20.以下说法错误的是()。

A.散列法存储的思想是由关键字值决定数据的存储地址

B.散列表的结点中只包含数据元素自身的信息，不包含指针

C.负载因子是散列表的一个重要参数，它反映了散列表的饱满程度

D.散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。

参考答案：B

21.设有两个串p和q,求q在p中首次出现的位置的运算称为()。

A.连接

B.模式匹配

C.求子串

D.求串长

参考答案：B

22.递归通常选用的存储结构是()。

A.栈

B.线性表

C.队列

D.二叉排序树

参考答案：A

23.数据结构在计算机内存中的表示是指()o

A.数据的存储结构

B.数据结构

C.数据的逻辑结构

D.数据元素之间的关系

参考答案：A

24.具有10个叶子结点的二叉树中有()个度为2的结点。

A.8

B.9

C.10

D.11

参考答案：B

25.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记

录的一趟快速排序结束后的结果为()。

A.10,15,14,18,20,36,40,21

B.10,15,14,18,20,40,36,21

C.10,15,14,20,18,40,36,21

D.15,10,14,18,20,36,40,21

参考答案：A

26.引起循环队列队头位置发生变化的操作是()。

A.出队

B.入队

C.取队头元素

D.取队尾元素

参考答案：A

27.在循环双链表的p所指的结点之前插入s所指结点的操作是()。

A.p-u003eprior=s；s-u003enext=p；p-u003eprior-u003enext=s；s-u003eprior=p-u003eprior

B.p-u003eprior=s；p-u003eprior-u003enext=s；s-u003enext=p；s-u003eprior=p-u003eprior

C.s-u003enext=p；s-u003eprior=p-u003eprior；p-u003eprior=s；p-u003eprior-u003enext=s

D.s-u003enext=p：s-u003eprior=p-u003eprior；p-u003eprior-u003enext=s；p-u003eprior=s

参考答案：D

28.广义表((a),a)的表头是C,表尾是()。

A.a

B.()

C.(a)

D.((a))

参考答案：C

29.串并〃DataStructure”中长度为3的子串的数目是()0

A.9

B.11

C.12

D.14

参考答案：C

30.有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100),当折半查

找值为82的结点时，()次比较后查找成功。

A.11

B.5

C.4

D.8

参考答案：C

3L设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快

速排序的结果为()。

A.2,3,5,8,6

B.3,2,5,8,6

C.3,2,5,6,8

D.2,3,6,5,8

参考答案：C

32.具有n个结点的连通图至少有()条边。

A.n-1

B.n

C.n(n-l)/2

D.2n

参考答案：A

33.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若

p->next玲next=head,则(),

A.p指向头结点

B.p指向尾结点

C.*p的直接后继是头结点

D.*P的直接后继是尾结点

参考答案：D

34.采用邻接表存储的图的深度优先遍历算法类似于二叉树的。。

A.先序遍历

B.中序遍历

C.后序遍历

D.按层遍历

参考答案：A

35.链表不具备的特点是。。

A.可随机访问任一结点

B.插入删除不需要移动元素

C.不必事先估计存储空间

D.所需空间与其长度成正比

参考答案：A

36.直接选择排序的时间复杂度为()。(n为元素个数)

A.O(n)

B.O(log2n)

C.O(nlog2n)

D.0(n2)

参考答案：D

37.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为()o

A.4

B.5

C.8

D.9

参考答案：C

38.串的长度是指()。

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

参考答案：B

39.在数据结构中，从逻辑上可以把数据结构分为()o

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.线性结构和非线性结构

D.内部结构和外部结构

参考答案：C

40.若不带头结点的单链表的头指针为head,则该链表为空的判定条件是（）。

A.head==*

B.head-u003enext=='

C.head!='

D.head-u003enext==head

参考答案：A

4L需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（）。

A.单链表

B.静态链表

C.线性链表

D.顺序存储结构

参考答案：B

42.

A.vlv4v6v2v5v3

B.vlv2v3v4v5v6

C.vlv4v2v3v6v5

D.vlv2v4v6v3v5

参考答案：A

43.设有一个栈，元素依次进栈的顺序为A、B、C、D、E,下列（）是不可能的出栈序列。

A.A,B,C,D,E

B.B,C,D,E,A

C.E,A,B,C,D

D.E,D,C,B,A

参考答案：C

44.在以下的叙述中，正确的是（）。

A.线性表的顺序存储结构优于链表存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

参考答案：B

45.以下说法正确的是（）。

A.数据项是数据的基本单位

B.数据元素是数据的最小单位

C.数据结构是带结构的数据项的集合

D.一些表面上很不相同的数据可以有相同的逻辑结构

参考答案：D

46.非空的循环单链表head的尾结点（由p所指向）满足（）»

A.p-uOO3enext=='

B.p=='

C.p-uOO3enext==head

D.p==head

参考答案：C

47.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。

A.edcba

B.decba

C.dceab

D.abcde

参考答案：c

48.在以下的叙述中，正确的是（）。

A.线性表的顺序存储结构优于链表存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

参考答案：B

49.若串S=，software，，其子串的数目是（）。

A.8

B.37

C.36

D.9

参考答案：B

50.在数据结构中，与所使用的计算机无关的是数据的（）结构。

A.逻辑

B.存储

C.逻辑和存储

D.物理

参考答案：A

51.下面关于线性表的叙述中，错误的是（）。

A.线性表采用顺序存储,必须占用一片连续的存储单元

B.线性表采用顺序存储,便于进行插入和删除操作

C.线性表采用链式存储,不必占用一片连续的存储单元

D.线性表采用链式存储,便于进行插入和删除操作

参考答案：B

52.对矩阵进行压缩存储是为了（）。

A.方便运算

B.方便存储

C.提高运算速度

D.减少存储空间

参考答案：D

53.字符串通常采用的两种存储方式是（）。

A.散列存储和索引存储

B.索引存储和链式存储

C.顺序存储和链式存储

D.散列存储和顺序存储

参考答案：C

54.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执

行出队操作后其头指针front值为()。

A.front=front+1

B.front=(front+l)%(m-l)

C.front=(front-l)%m

D.front=(front+l)%m

参考答案：D

55.对于一个具有N个顶点的图，若用邻接矩阵表示，则该矩阵的大小为()。

A.N

B.(N-1)2

C.(N+1)2

D.N2

参考答案：D

56.采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为()。

A.0(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

参考答案：D

57.线性表的顺序存储结构是一种()。

A.随机存取的存储结构

B.顺序存取的存储结构

C.索引存取的存储结构

D.Hash存取的存储结构

参考答案；A

58.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列

为()。

A.q=p-u003enext；p-u003edata=q-u003edata；p-u003enext=q-u003enext；free(q)；

B.q=p-u003enext；q-u003edata=p-u003edata；p-u003enext=q-u003enext；free(q)；

C.q=p-u003enext；p-uOO3enext=q-uOO3enext；free(q)；

D.q=p-u003enext；p-u003edata=q-u003edata；free(q)；

参考答案：A

59.设某二叉树中度数为0的结点数为NO,度数为1的结点数为NI,度数为2的结点数为

N2,则下列等式成立的是()。

A.NO=N1+1

B.N0=NI+N2

C.N0=N2+l

D.NO=2N1+I

参考答案：C

60.设二维数组A[l?m,l?n]按行存储在数组B中，则二维数组元素A[i,j]在一维数组B中的下

标为()。

A.n*(i-l)+j

B.n*(i-l)+j-l

C.i*(j-1)

D.j*m+i-l

参考答案：A

二.判断题

请选择正确的答案。

61.空串和空白串是相同的。()

参考答案：错误

62.散列法存储的思想是由关键字值决定数据的存储地址。()

参考答案：正确

63.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右

孩子的值。()

参考答案：错误

64.拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。()

参考答案：错误

65.对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个

顶点。()

参考答案：错误

66.广义表(((a),b),c)的表头是((a),b),表尾是(c)。()

参考答案：正确

67.一个广义表的表头总是一个广义表。()

参考答案：错误

68.在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次

序仍然保持不变，称这种排序为稳定排序。()

参考答案：正确

69.直接选择排序算法在最好情况下的时间复杂度为0(n)。()

参考答案：错误

70.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。()

参考答案：错误

单选题

1.若串S=，software，，其子串的数目是()。

A.8

B.37

C.36

D.9

参考答案：B

2.在数据结构中，与所使用的计算机无关的是数据的()结构。

A.逻辑

B.存储

C.逻辑和存储

D.物理

参考答案：A

3.递归通常选用的存储结构是()。

A.栈

B.线性表

C.队列

D.二叉排序树

参考答案：A

4.在数据结构中，从逻辑上可以把数据结构分为()»

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.线性结构和非线性结构

D.内部结构和外部结构

参考答案：C

5.稀疏矩阵一般的压缩存储方式有两种，即()。

A.二维数组和三维数组

B.三元组和散列

C,三元组和十字链表

D.散列和十字链表

参考答案：C

6.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是()

A.(e,f)

B.((e，f))

c.(f)

D.()

参考答案：B

7.设二维数组A[l?m,l?n]按行存储在数组B中，则二维数组元素A[i,j]在一维数组B中的下标

为()。

A.n*(i-l)+j

B.n*(i-l)+j-l

C.i*(j-1)

D.j*m+i-l

参考答案：A

8.引起循环队列队头位置发生变化的操作是()。

A.出队

B.入队

C.取队头元素

D.取队尾元素

参考答案：A

9.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录

的一趟快速排序结束后的结果为()。

A.10,15,14,18,20,36,40,21

B.10,15,14,18,20,40,36,21

C.10,15,14,20,18,40,36,21

D.15,10,14,18,20,36,40,21

参考答案：A

10.设有两个串P和q,求q在p中首次出现的位置的运算称为Oo

A.连接

B.模式匹配

C.求子串

D.求串长

参考答案：B

11.直接选择排序的时间复杂度为()。(n为元素个数)

A.O(n)

B.O(log2n)

C.O(nlog2n)

D.O(n2)

参考答案：D

12.在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是()。

A.希尔排序

B.冒泡排序

C.直接插入排序

D.直接选择排序

参考答案：D

13.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执

行出队操作后其头指针front值为()。

A.front=front+1

B.front=(front+l)%(m-l)

C.front=(front-l)%m

D.front=(front+l)%m

参考答案：D

14.允许对队列进行的操作有()。

A.对队列中的元素排序

B.取出最近进队的元素

C.在队头元素之前插入元素

D.删除队头元素

参考答案：D

15.串s="DataStructure”中长度为3的子串的数目是()。

A.9

B.ll

C.12

D.14

参考答案：C

16.在循环双链表的p所指的结点之前插入s所指结点的操作是()o

A.p-u003eprior=s；s-u003enext=p；p-u003eprior-u003enext=s；s-u003eprior=p-u003eprior

B.p-u003eprior=s；p-u003eprior-u003enext=s；s-uOO3enext=p；s-u003eprior=p-u003eprior

C.s-uOO3enext=p；s-u003eprior=p-u003eprior；p-u003eprior=s；p-u003eprior-u003enext=s

D.s-uOO3enext=p；s-u003eprior=p-u003eprior；p-u003eprior-u003enext=s；p-u003eprior=s

参考答案：D

17.下面关于线性表的叙述中，错误的是()o

A.线性表采用顺序存储，必须占用一片连续的存储单元

B.线性表采用顺序存储，便于进行插入和删除操作

C.线性表采用链式存储，不必占用一片连续的存储单元

D.线性表采用链式存储，便于进行插入和删除操作

参考答案：B

18.设某二叉树中度数为0的结点数为NO,度数为1的结点数为NI,度数为2的结点数为

N2,则下列等式成立的是()。

A.NO=N1+1

B.N0=NI+N2

C.NO=N2+1

D.NO=2N1+I

参考答案：c

19.在以下的叙述中，正确的是()。

A.线性表的顺序存储结构优于链表存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

参考答案：B

20.在一个有向图中，所有顶点的入度