数据结构复习试卷(二)

一．简述下列术语（14分）

线性表，栈，文件，关键路径，无向完全图，内部排序，哈希表

二．简答题：静态查找表和动态查找表有何不同？（8分）

三．依次写入某堆栈的数据分别为：7，3，6，2和5，画出该堆栈的示意图，并解答下列问题： （10分）

1．编写一个算法，实现整型变量x的进栈操作；

2．编写一个算法，实现将队头元素出栈给整型变量y的操作。

四．依次进入某循环队列的数据为9，12，4，6 和8，请画出该循环队列示意图，并解答下列问题：（10分）

1．编写一个算法，实现整型变量x的进队操作；

2．编写一个算法，实现将队头元素出队给整型变量y的操作。

五．对于给定的一组权值W={7，2，8，4，16，3，9}，请构造出哈夫曼树（最优二叉树），并计算出其带权路径长度。（10分）

六．请简述冒泡排序的基本思想；并对于下列给定数据：{18，3，23，38，65，97，76，13，27，22}，指出使用冒泡排序后第一趟排序的结果（12分）

七．请简述折半查找的查找过程，编写一个在有序表中折半查找给定关键字记录的算法（10分）。

八．编写一个算法，统计出一个带表头结点的单向链表中数据元素的个数。（6分）

九．请根据如图所示的二叉树，回答下列问题：（10分）

1．该二叉树的二叉链表形式；

2．该二叉树的叶子节点个数；

3．该二叉树的中序遍历序列；

4．该二叉树的后序遍历序列；

5．将该二叉树转换成森林。

十．请根据给出的网络（带有权值的无向图），回答下列问题：（10分）

1．该图的邻接表形式；

2．该图从顶点1出发的深度优先搜索序列；

3．该图从顶点1 出发的广度优先搜索序列；

4．该图的一棵最小代价生成树。