2020年广西桂林理工大学数据结构及程序设计考研真题A卷

2020年广西桂林理工大学数据结构及程序设计考研真题A

卷

一、分析以下所给程序段的时间复杂度。 （10分）

for (i=1；i

for (j=0；j<=(2*n)；j++) x++；}

二、设有一个10X10的对称矩阵A[10][10]，采用按行压缩存储的方式存放于一个一维数

组B[]中，则数组B[]的容量有多大？若设A[0][0]为第一个元素，存放于B[0]，且数组A[][]的每一个数组元素在数组B[]中占一个数组元素位置，则A[8][5]在数组B[]中的地址是多少？ （10分）

三、已知一棵二叉树的先序序列的结果是ABCDEFGHI，中序序列的结果是BCAEDGHFI，试画

出这棵二叉树。 （10分）

四、己知一个以二维数组表示的图的邻接矩阵如下所示,试画出从顶点V1出发进行遍历所

得的一个深度优先生成树。 （10分）

V1 V2 V3 V4 V5 V6 V1 0 0 0 0 0 1 V2 0 0 0 0 0 1 V3 0 1 0 0 0 0 V4 0 0 1 0 0 0 V5 0 0 0 1 0 0 V6 0 0 0 0 1 0 V7 1 1 0 0 0 0 V8 0 0 1 0 0 0 V9 1 0 0 1 0 0 V10 0 0 0 0 1 0

V7 V8 V9 V10

0 1 0 1

0 0 0 0

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

0 0 1 0

0 0 0 0

0 1 0 0

1 0 0 0

五、使用普里姆（Prim）算法构造出如下图所示的图G的一棵最小生成树。 （10分） C 8 9 5 B D 8 6 10 4 F

20 6

A E

12 图G:一个无向图

六、试证明有n0个叶子的哈夫曼树共有2n0-1个结点。 （10分）

七、设待排序的排序列为{36，80，45，66，22，9，16，36}，试分别写出按下列排序方法

进行排序时的变化过程（即每趟排序后的结果）。（1）直接插入排序；（2）冒泡排序；（3）直接选择排序。 （15分）

八、设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函

数： H(Key)=Key MOD 13， 采用开放地址法的线性探测再散列方法解决冲突，试在0～18的散列地址空间中对该关键字序列构造哈希表。 （15分）

九、设给定权集W={4，5，6，7，10，12，18}，试构造出关于W的哈夫曼树，并求出其加

权路径长度WPL。 （15分）

十、编写一个算法计算一棵二叉树t的高度过程。 （15分）

十一、编写一个算法（命名为QueueToStack）从一个队列创建一个栈，使队列的头为栈顶，

队列尾为栈底，算法的最后的要求使队列保持不变。 （15分）

十二、有50个学生，每个学生有3门功课成绩，从键盘输入这50个学生的学号、姓名及

3门功课成绩，计算出每人平均成绩，并用所有数据包括平均成绩建立在一个磁盘文件“stud”中。 （15分）