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，f B.a，c，f,e，b，d C.a，e，b，c，f, d D.a，e，d，f，c，b
2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A.13 B.33 C.18 D.40
3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A.单链表 B.双向链表 C.单循环链表 D.顺序表
4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（ ）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front
D.（rear-1）MOD n=front
5、已知串S='aaab'，其next数组值为（ ）。 A.0123 B.1123 C.1231 D.1211
6、下列选项中，不能构成折半查找中关键字比较序列的是（ ）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450
7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（ ）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1） 8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆
9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（ ）个叶子。
A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2
10、对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是： A.05，46，13，55，94，17，42 B.05，13，17，42，46，55.94 C.42，13，94，05，55，46，17 D.05，13，46，55，17，42，94
二、填空题
11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 12、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。
13、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。
14、一个算法具有5个特性： ______、______、______、有零个或多个输入、有一个或多个输出。
15、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。
16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时， top[2]为______，栈满时为______。 17、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。
18、设广义表L=（（），（）），则head（L）是______； tail（L）是______；L的长度是______；深度是______。
三、判断题
19、文件系统采用索引结构是为了节省存储空间。（ ）
20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（ ）
21、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若 ai=n（1≤i≤n）则有：ai>ai+1>…>an。（ ）
22、在链队列中，即使不设置尾指针也能进行入队操作。（ ） 23、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ） 24、二叉树是一般树的特殊情形。（ ）
25、为了很方便地插入和删除数据，可以使用双向链表存放数据。 （ ）
26、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）
27、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）
28、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ）
四、简答题
29、请写出应填入下列叙述中（ ）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。
（ ）排序的结果为：12，13，15，18，20，60 （ ）排序的结果为：13，15，18，12，20，60 （ ）排序的结果为：13，15，20，18，12，60 （ ）排序的结果为：12，13，20，18，15，60
30、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
（1） 归并排序，每归并一次书写一个次序。 （2） 快速排序，每划分一次书写一个次序。
（3） 堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
31、已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
要求：
（1）写出图G的邻接矩阵A。
（2）画出有向带权图G。求图G的关键路径，并计算该关键路径的长度。
五、算法设计题
32、请编写完整的程序。如果矩阵A中存在这样的一个元素A[i，j]满足条件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。
33、已知P是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表（a1，a2，…，an-1，an）改造为（a1，a2，…， an-1，an，an-1，…，a2，a1）。
34、（1）试分别找出满足下列条件的所有二叉树：（a）前序序列和中序序列相同：（b）前序序列和后序序列相同；（c）中序序列和后序序列相同。（2）已知非空二叉树的结点结构为（lchild，data，rchild），设计算法：从右向左依次将所有叶子的数据值放到向量（假定向量的空间大于叶子的总个数）中。
35、叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。（179，208，93，306，55，859，984，9，271，33）
参
一、选择题
1、【答案】D 2、【答案】B 3、【答案】D 4、【答案】B 5、【答案】A 6、【答案】A 7、【答案】A 8、【答案】D 9、【答案】D 10、【答案】C
二、填空题
11、【答案】n（n-1）/2 12、【答案】
（1）L->next=NULL //置空链表，然后将原链表结点逐个插入到有序表中 （1） p!=NULL //当链表尚未到尾，p为工作指针
（2） q!=NULL //查P结点在链表中的插入位置，这时q是工作指针 （4）p->next=r->next //将P结点链入链表中
（5）r->next=p //r是q的前驱，u是下个待插入结点的指针 13、【答案】逻辑结构；物理结构；操作（运算）；算法 14、【答案】有穷性；确定性；可行性
15、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p
16、【答案】0；n+1；top[1]+1=top[2] 17、【答案】
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。 18、【答案】（）；（（））；2；2
三、判断题
19、【答案】× 20、【答案】× 21、【答案】× 22、【答案】√ 23、【答案】× 24、【答案】× 25、【答案】√ 26、【答案】× 27、【答案】√ 28、【答案】√
四、简答题
29、答：①快速排序 ②起泡排序 ③直接插入排序 ④堆排序 30、答：（1）2一路归并第一趟：18，29，25，47，12，58，10，51。 第二趟：18，25，29，47，10，12，51，58。 第三趟：10，12，18，25，29，47，51，58。
（2）快速排序第一趟：10，18，25，12，29，58，51，47。 第二趟：10，18，25，12，29，47，51，88。 第三趟：10，12，18，25，29，47，51，88。
（3）堆排序
建大堆：58，47，51，29，18，12，25，10。
① 51，47，25，29，18，12，10，58。 ② 47，29，25，10，18，12，51，58。 ③ 29，18，25，10，12，47，51，58。 ④ 25，18，12，10，29，47，51，58。 ⑤ 18，10，12，25，29，47，51，58。 ⑥ 12，10，18，25，29，47，51，58。 ⑦ 10，12，18，25，29，47，51，58。
31、答：（1）由题可以画出待定上三角矩阵的结构图如下（图中？为待定元素）：
可以看出，第一行至第五行主对角线上方的元素分别为5，4，3，2，1 个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：
将各元素填入各行即得邻接矩阵：
（2）根据第一步所得矩阵A容易做出有向带权图G，如下：
（3）关键路径为0-＞1-＞2-＞3-＞5（如下图所示粗线表示），长度为4＋5＋4＋3＝16。
五、算法设计题
32、答：算法如下：
33、答：算法如下：
34、答：（1）满足条件的二叉树如下：
（a）
的二叉树。
若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树
（b）
若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
（c）
的二叉树。
若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树
（2）算法如下：
35、答：算法如下：
