2022年长春工程学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdf

2022年长春工程学院计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，

e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是

（）。

A.a，b，e，c，d，fB.a，c，f,e，b，d

C.a，e，b，c，f,dD.a，e，d，f，c，b

2、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)

3、单链表中，增加一个头结点是为了（）。

A.使单链表至少有一个结点B.标识表结点中首结点的位置

C.方便运算的实现D.说明单链表是线性表的链式存储

4、已知有向图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，V7D.V1，V2，V5，V3，V4，V6，V7

5、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，

下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modM

B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）

C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modM

D．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）

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

A．根结点最多有m棵子树B．所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接

8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间

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

A.二叉树的度为2

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

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

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

10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果

为（）。

A.（2，5，12，16）26（60，32，72）

B.（5，16，2，12）28（60，32，72）

C.（2，16，12，5）28（60，32，72）

D.（5，16，2，12）28（32，60，72）

二、填空题

11、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步

长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据

的排列次序______。

12、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则

其伙伴块的起始地址为______。

13、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），