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，c，f,e，b，d

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

2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（　　）。

A.N    B.2N-1    C.2N   D.N-1

3、以下数据结构中，（　　）是非线性数据结构。

A.树 字符串 队 栈

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

A.仅修改队头指针

B.仅修改队尾指针

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

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

5、动态存储管理系统中，通常可有（　　）种不同的分配策略。

A.1     B.2    C.3      D.4

6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（　　）。

A．i＝1，j＝0  B．i＝5，j＝0．i＝5，j＝2．i＝6，j＝2

7、下列关于无向连通图特性的叙述中，正确的是（　　）。

Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1

A．只有Ⅰ．只有Ⅱ  C．Ⅰ和Ⅱ．Ⅰ和Ⅲ

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

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

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

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

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

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

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

10、下列二叉排序树中查找效率最高的是（　　）。

A.平衡二叉树

B.二叉查找树

C.没有左子树的二叉排序树

D.没有右子树的二叉排序树

二、填空题

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

12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

13、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。也可以按______检索；按______检索又可以有 ______检索和______检索。

14、外排序的基本操作过程是______和______。

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

16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

17、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V， SUBSTR（S，INDEX（S，t），LEN（t）+1））； ASSIGN（m，’ww’），求REPLACE（S，V，m）=______。

18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。

三、判断题

19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（　　）

20、倒排文件的目的是为了多关键字查找。（　　）

21、数组不适合作为任何二叉树的存储结构。（　　）

22、广义表（（（a，b，c），d，e，f））的长度是4。（　　）

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

24、对于有n个结点的二叉树，其高度为log2n。（　　）

25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（　　）

26、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（　　）

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

28、无环有向图才能进行拓扑排序。（　　）

四、简答题

29、下面程序段的时间复杂度是什么？

30、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。

31、已知一个带有表头结点的单链表，结点结构为

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：

（1）描述算法的基本设计思想。

（2）描述算法的详细实现步骤。

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C＋＋或JAVA语言实现），关键之处请给出简要注释。

五、算法设计题

32、设记录R[i]的关键字为R[i]。KEY（1≤i≤k），树结点T[i]（1≤i≤K-1）指向败者记录，T[0]为全胜记录下标。写一算法产生对应上述R[f]（1≤f≤k）的败者树，要求除R[1..k]和Tr[0..k-1]以外，只用O（1）辅助空间。

33、写出一个递归算法来实现字符串逆序存储。

34、设T是一棵满二叉树，写一个把T的后序遍历序列转换为前序遍历序列的递归算法。

35、已知二叉树采用二叉链表存储，设计算法以输出二叉树T中根结点到每个叶结点的路径。

参

一、选择题

1、【答案】D

2、【答案】A

3、【答案】A

4、【答案】C

5、【答案】C

6、【答案】C 

7、【答案】A

8、【答案】D

9、【答案】C

10、【答案】A

二、填空题

11、【答案】480+8=488；480-32=448

12、【答案】a+1；n%10

【解析】通过递归算法，首先找到最高位的值，将其放到str对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

13、【答案】关键字；记录号；记录号；顺序；直接

14、【答案】生成有序归并段（顺串）；归并

15、【答案】分配和释放存储空间；重组；对插入的记录@

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

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

17、【答案】’xyxyxywwy’

18、【答案】

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同一层上的条件是

三、判断题

19、【答案】×

20、【答案】√

21、【答案】×

22、【答案】×

23、【答案】×

24、【答案】×

25、【答案】×

26、【答案】√

27、【答案】√

28、【答案】√

四、简答题

29、答：赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O（m*n）。

30、答：森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。

（3）旋转（以最左边树的根为轴，顺时针向下旋转45度）。

所以由上面三棵树转换得到的二叉树如图所示：

31、答：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。

（2）算法的详细实现步骤

① count＝0，p和q指向链表表头结点的下一个结点。

②若p为空，转⑤。

③若count等于k，则q指向下一个结点；否则，count＝count＋1。

④ p指向下一个结点，转步骤②。

⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0。

⑥算法结束。

（3）算法实现

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：算法如下：

35、答：算法如下：