数据结构与算法设计期末考试试卷

试卷（A卷）

《数据结构与算法设计》试卷

开课单位：计算机学院，考试形式：闭卷，允许带入场

身题序一二三四五六七八总分

眇

送

得分

世

评卷人

I.基本概念部分（第9小题10分,其余每小题6分，共70分）

1在右边空白处画出下面的BST中删除值为22的结点以后的BST的形状。

奈

般

(郛

.

蹴.

.

和.

.

.

郛.

.

蔚.

.

.

囹.

.

).

.

.

笨.

.

赭

——2请画出向下面所示的最小堆中插入一个元素值14以后的堆的形状。

点

亳

和652632

《数据结构与算法设计》试卷第1页共8页

3给出下图所示的树的前序遍历序列。

4下面给出了某二叉树的前序和中序访问序列，请画出该二叉树的形状。

前序序列：2354568920766790784531

中序序列：5654208976239078674531

《数据结构与算法设计》试卷第2页共8页

5下图所示是双链表结点的删除过程，在fence结点后面删除一个值为23的结

点，已知fence->next是指向fence的后继结点，fence->prev是指向fence的

前驱结点，Itmp是一个值为NULL的链表结点指针，请把这一删除过程用代码表

示出来：

这一过程的代码:

6给出下图从结点C开始的深度优先搜索树，并按搜到的顺序标上序号。

姓名:学号:系另U：年级专业：

（密封线内不答题）

密封......................线

S

澄

3

同

处

.

0

©

0

7画出下图以相邻矩阵表示法时的相邻矩阵。

8画出下图的最小支撑树。

《数据结构与算法设计》试卷第4页共8页

ABCDEF

A

B

C

D

E

F

9下图是一个表示课程之间优先关系的有向图，根据你在数据结构课程中所学的

拓扑排序的有关知识，给出该图的拓扑排序序列。(此小题10分)

10设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任

何次序夹入其中，请回答下有问题：

(1)若入栈次序为push(l),pop(),push(2),push(3),pop(),pop(),push(4),

pop(),则出栈的数字序列是什么？

(2)能否得到出栈序列423和432?并说明为什么不能得到或如何得到。

姓名：—学号：系别：年级专业:

（密封线内不答题）

密...................................封.............................线...........................

S

澄

5

同

处

8

疔

11假设用于通信的电文是由字符集㈤卜勒必^力口力中的字符构成，这9

个字符在电文中出现的概率分别为

{0.26,0.10,0.02,0.06,0.16,0.03,0.12,0.07,0.18}。

请画出对应的Huffman树（按左子树根结点的权小于等于右子树根结点的权的次

序构造）。

《数据结构与算法设计》试卷第6页共8页

II.综合应用部分（每小题1（）分，共30分）

1设有一个链表（u“U2,…，u„）,试编写一个函数将这个链表原地逆置，即链

表为（u,„...»U2,U.）,并要求算法的空间复杂度为0（1）。（带头结点的实现）

2设指针p指向单链表的首结点，指针x指向单链表中的任意一个结点，写出在

x前插入一个结点1的算法。（不带头结点的实现）

《数据结构与算法设计》试卷第7页共8页

一

黑

版

(邦

.

蹴.

.