2022年兰州交通大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年兰州交通大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）

一、选择题

1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（ ）。

A.5 B.6 C.8 D.9

2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（ ）。

A.j=r[j].next B.j=j+l C.j=j->next D.j=r[j]->next

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

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

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

4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。

A.仅修改队头指针

B.仅修改队尾指针

C.队头、队尾指针都可能要修改

D.队头、队尾指针都要修改

5、已知串S='aaab'，其next数组值为（ ）。

A.0123 B.1123 C.1231 D.1211

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（ ）。

A．只有e B．有e、b C．有e、c D．无法确定

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、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（ ）个叶子。

A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2

9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为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、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。

12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。

13、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。

14、文件可按其记录的类型不同而分成两类，即______和______文件。

15、索引顺序文件既可以顺序存取，也可以______存取。 16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

17、模式串P=‘abaabcac’的next函数值序列为______。

18、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B 中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始）

三、判断题

19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）

20、直接访问文件也能顺序访问，只是一般效率不高。（ ） 21、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ）

22、串是一种数据对象和操作都特殊的线性表。（ ）

23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）

24、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）

25、数据元素是数据的最小单位。（ ）

26、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）

27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）

28、B-树中所有结点的平衡因子都为零。（ ）

四、简答题

29、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’

（1）计算模式p的nextval函数值。

（2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

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、写一算法找出n个数的最大值和最小值，要求最坏条件下的元素比较次数为

33、已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

34、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A～Z这26个字母和0～9这10个数字）。

35、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注：向量d可视为循环表），其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分二路插入。编写实现2-路插入排序算法。

参考答案

一、选择题

1、【答案】A

2、【答案】A

3、【答案】B

4、【答案】C

5、【答案】A

6、【答案】A

7、【答案】A

8、【答案】D

9、【答案】C

10、【答案】C

二、填空题

11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@

12、【答案】起泡；快速

13、【答案】逻辑结构；物理结构；操作（运算）；算法

14、【答案】操作系统文件；数据库

15、【答案】随机

16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1

【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

17、【答案】01122312

18、【答案】93 三、判断题

19、【答案】×

20、【答案】×

21、【答案】√

22、【答案】√

23、【答案】√

24、【答案】×

25、【答案】×

26、【答案】×

27、【答案】√

28、【答案】√

四、简答题

29、答：（1）p的nextval函数值为0110132（p的next函数值为0111232）。

（2）利用KMP（改进的nextval）算法，每趟匹配过程如下：

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 个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：