《2020年广西桂林理工大学数据结构及程序设计考研真题A卷.doc》由会员分享，可在线阅读，更多相关《2020年广西桂林理工大学数据结构及程序设计考研真题A卷.doc（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2020年广西桂林理工大学数据结构及程序设计考研真题A卷一、分析以下所给程序段的时间复杂度。 （10分）for (i=1；in；i+) y=y+1；for (j=0；j=(2*n)；j+)x+；二、设有一个10X10的对称矩阵A1010，采用按行压缩存储的方式存放于一个一维数组B中，则数组B的容量有多大？若设A00为第一个元素，存放于B0，且数组A的每一个数组元素在数组B中占一个数组元素位置，则A85在数组B中的地址是多少？ （10分）三、已知一棵二叉树的先序序列的结果是ABCDEFGHI，中序序列的结果是BCAEDGHFI，试画出这棵二叉树。 （10分）四、 己知一个以二维数组表示的图的邻接
2、矩阵如下所示,试画出从顶点V1出发进行遍历所得的一个深度优先生成树。 （10分）V1V2V3V4V5V6V7V8V9V10V10000001010V20010001000V30001000100V40000100010V50000010001V61100000000V70010000001V81001000010V90000101000V101000010000五、使用普里姆（Prim）算法构造出如下图所示的图G的一棵最小生成树。 （10分） C 8 9 B D 5 8 6 F 10 4 20 6 A E 12图G:一个无向图六、试证明有n0个叶子的哈夫曼树共有2n0-1个结点。 （10分）七
3、、设待排序的排序列为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， 采用开放地址法的线性探测再散列方法解决冲突，试在018的散列地址空间中对该关键字序列构造哈希表。 （15分）九、设给定权集W=4，5，6，7，10，12，18，试构造出关于W的哈夫曼树，并求出其加权路径长度WPL。 （15分）十、编写一个算法计算一棵二叉树t的高度过程。 （15分）十一、编写一个算法（命名为QueueToStack）从一个队列创建一个栈，使队列的头为栈顶，队列尾为栈底，算法的最后的要求使队列保持不变。 （15分）十二、有50个学生，每个学生有3门功课成绩，从键盘输入这50个学生的学号、姓名及3门功课成绩，计算出每人平均成绩，并用所有数据包括平均成绩建立在一个磁盘文件“stud”中。 （15分）