2022年兰州交通大学计算机科学与技术专业《数据结构与算法》科目期末试.pdf

2022年兰州交通大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

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

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

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

A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next

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

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

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

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

A.仅修改队头指针

B.仅修改队尾指针

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

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

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

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

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

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

7、循环队列放在一维数组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）

8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中
有（）个叶子。

A.lognB.（n－1）/2C.logn+1D.（n＋1）/2
22

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、设目