学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有.pdf

2022年安徽信息工程学院计算机科学与技术专业《数据结构与算法》

科目期末试卷A（有答案）

一、选择题

1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放
在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入选择B.希尔C.二路D.归并

2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串树B.广义C.表栈D.

3、链表不具有的特点是（）。

A.插入、删除不需要移动元素可随机B.访问任一元素

C.不必事先估计存储空间所需空D.间与线性长度成正比

4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列
中的元素数是（）。

A.（rear-front+m）%m

B.rear-front+1

C.rear-front-1

D.rear-front

5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，
<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，
<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7

C.V1，V3，V5，V2，V6，V7，D.V1V2，V5，V3，V4，V6，V7

6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字
3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28
C．3，8，12，5，20，15，22，28，19

D．3，12，5，8，28，20，15，22，19

7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三
次进行退栈操作，则不可能得到的出栈序列是（）。

8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩
子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子

B.在树T中，X一定无右兄弟

C.在树T中，X一定是叶结点

D.在树T中，X一定有左兄弟

9、有关二叉树下列说法正确的是（）。

A.二叉树的度为2

B.一棵二叉树的度可以小于2

C.二叉树中至少有一个结点的度为2

D.二叉树中任何一个结点的度都为2

10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第
一个记录为基准得到的一次划分结果为（）。

A.（38，40，46，56，79，84）（B.40，38，46，79，56，84）

C.（40，38，46，56，79，84）（D.40，38，46，84，56，79）

二、填空题

11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。
12、阅读下列程序，指出其功能，并写出空格处应填上的语句。

13、VSAM系统是由______、______、______构成的。

14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，
试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

15、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并
能较快地______进行查找。

16、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址
2000开始连续存放在主内存里，主内存字长为16位，那么

（1）存放该数组至少需要的单元数是______。

（2）存放数组的第8列的所有元素至少需要的单元数______。

（3）数组按列存储时，元素A[5，8]的起始地址是______。

17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。
18、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点
为______。

三、判断题

19、文件系统采用索引结构是为了节省存储空间。（）

20、倒排文件是对次关键字建立索引。（）

21、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若ai=n（1≤i≤n）则有：
ai>ai+1>…>an。（）

22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法
的时间复杂性为O（i）。（）

23、二叉树是一般树的特殊情形。（）

24、任何二叉树的后序线索