数据结构期末考试及答案

一、单选题

1、逻辑上通常可以将数据结构分为 ( )

A.初等结构和组合结构

B.顺序结构和链式结构

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

D.动态结构和静态结构

正确答案：C

2、如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。

A.栈

B. 队列

C.图

D.树

正确答案：D

3、在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1)，元素的移动次数为：（）

A.n-i

B.i-1

C.n-i+1

D.i

正确答案：C

4、在非空线性链表中由p所指结点的后面插入一个由q所指的结点，应依次执行（ ）

A.q->next=p；p->next=q；

B.p->next=q；q->next=p；

C.q->next=p->next；p->next=q；

D.q->next=p->next；p=q；

正确答案：C

5、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）

A.2，3，5，6，1，4

B.1，4，6，5，2，3

C.5，4，3，2，1，6

D.3，2，5，4，1，6

正确答案：D

6、设栈S和队列Q初始均为空，若6个元素入栈的顺序为1、2、3、4、5、6，一个元素出栈以后立即入队列Q，若6个元素出队的顺序为2、4、3、6、5、1，则栈S的容量至少为（）

A.3

B.5

C.4

D.2

正确答案：A

7、在计算机内实现递归算法时所需的辅助数据结构是（ ） A.队列

B.栈

C.图

D.树

正确答案：B

8、循环队列存储在数组A[0..m-1],则出队时的操作为（ ）

A.front=(front mod m)+1

B.ront=(front+1)mod m

C.front=front+1

D.front=(front+1)mod (m-1)

正确答案：B

9、若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（)

A.SXXSXSSX

B.SSSXXSXX

C.SXSSXXXX

D.SXSXXSSX

正确答案：B

10、在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是 （）

A.(front+1)%m==rear

B.(rear+1)%m==front C.front==rear

D.rear+1==front

正确答案：B

11、在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）

A.n/4

B.n

C.n/3

D.n/2

正确答案：D

12、元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（ ）

A.E，D，C，B，A

B.A，B，C，D，E

C.E，A，B，C，D

D.B，C，D，E，A

正确答案：C

13、下述二叉树中，（ ）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。

A.AVL树

B.哈夫曼树

C.二叉排序树

D.堆

正确答案：B 14、若用邻接矩阵表示一个有向图，则其中每一行包含的″1″的个数为( )

A.图中连通分量的数目

B.图中每个顶点的入度

C.图中每个顶点的出度

D.图中弧的条数

正确答案：C

15、具有6个顶点的无向图至少应该有（ ）条边才能确保是一个连通图

A.8

B.7

C.6

D.5

正确答案：D

16、下面（）方法可以判断出一个有向图中是否有环（回路）

A.拓扑排序

B.深度优先遍历

C.最短路径

D.关键路径

正确答案：A

17、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）

A.后序遍历 B.先序遍历

C.按层次遍历

D.中序遍历

正确答案：B

18、对线性表进行二分查找时，要求线性表必须是（ ）

A.以顺序表存储

B.以顺序方式存储，且结点按关键字有序排列

C.以链式方式存储，其结点按关键字有序排列

D.以链式方式存储

正确答案：B

19、由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）

A.23

B.46

C.44

D.37

正确答案：C

20、快速排序方法在（ ）情况下最不利于发挥其长处。

A.要排序的数据个数为奇数

B.要排序的数据已基本有序

C.要排序的数据中含有多个相同值

D.要排序的数据量太大 正确答案：B

21、一组记录的排列码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为（ ）

A.84,79,56,46,40,38

B.84,79,56,38,40,46

C.84,56,79,40,46,38

D.79,46,56,38,40,84

正确答案：B

22、下列陈述中正确的是（）

A.二叉树中最多只有两棵子树，并且有左右之分

B.二叉树中必有度为2的结点

C.二叉树是度为2的有序树

D.二叉树中结点只有一个孩子时无左右之分

正确答案：A

23、树的先根序列等同于与该树对应的二叉树的（）

A.中序序列

B.先序序列

C.层序序列

D.后序序列

正确答案：B

24、以下有关广义表的表述中，正确的是（ ）

A.不能为空表 B.不能递归定义

C.至少有一个元素是子表

D.由0个或多个原子或子表构成的有限序列

正确答案：D

25、下列各项键值序列中不是堆的为（ ）

A.{5，23，16，73，94，72，71，68}

B.{5，23，16，68，94，72，71，73}

C.{5，23，16，68，73，71，72，94}

D.{5，16，23，68，94，72，71，73}

正确答案：A

26、线性表采用链式存储结构时，要求内存中可用存储单元的地址( )

A.必须是连续的

B.连续和不连续都可以

C.一定是不连续的

D.必须是部分连续的

正确答案：B

27、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )

A.用尾指针表示的单循环链表

B.单链表

C.顺序表 D.用头指针表示的单循环链表

正确答案：A

28、线性表是n个具有相同类型（ ）的有限序列(n>=0)。

A.字符

B.数据元素

C.数据项

D.表元素

正确答案：B

29、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）

A.定位

B.插入

C.排序

D.删除

正确答案：A

30、设无向图的邻接表如图所示，则该图的边数为（ ）

A.5

B.20

C.4 D.10

正确答案：A

31、链表中逻辑上相邻的元素其物理地址（ ）相邻

A.其它

B.不一定

C.一定不

D.必定

正确答案：B

32、图中结点e的度是（ ）

A.4

B.3

C.5

D.2

正确答案：A

33、有一个有序表为（1,3,9,12,32,41,45,62,75,77,82,95,100），当二分查找值为82的结点时，（）次比较后查找成功。

A.8 B.2

C.4

D.1

正确答案：C

34、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）

A.2倍

B.1/2

C.4倍

D.1倍

正确答案：D

35、下列叙述中不符合m阶B树定义要求的是（ ）

A.各结点内关键字均升序或降序排列

B.叶结点之间通过指针链接

C.所有叶结点都在同一层上

D.根结点最多有m个子树

正确答案：B

二、判断题

1、广义表是由零或多个原子或子表所组成的有限序列，所以广义表可能为空表。

正确答案：√

2、用树的前序遍历和中序遍历可以导出树的后序遍历。 正确答案：√

3、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应特殊处理。

正确答案：×

4、将一棵树转换成二叉树后，根结点没有左子树。

正确答案：×

5、在n个结点的无向图中，若边数〉n-1，则该图必是连通图。

正确答案：×

6、一个图的广度优先遍历生成树是唯一的

正确答案：×

7、对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的顺序是一样的.

正确答案：√

8、负载因子（装填因子）是散列表的一个重要参数，它反映散列表的装满程度。

正确答案：√

9、对一个堆，按二叉树层次进行遍历可以得到一个有序序列。

正确答案：×

10、对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是O()。

正确答案：√

11、线性表采用链表存储时，结点和结点内部的存储空间可以是不连