数 据 结 构B 期末试卷
二 三 四 五 六
班级 学号 姓名 得分
题号 分数 一 一、解答题：（共82分）
1、下列程序段或函数的时间复杂度。（10%）
（1） for (int k=0;k for (int j=0;j （3） int Prime(int n) （4）k=1; x=0; { int k=2 , x=(int)sqrt(n) ; do { while (k<=x) { x++; k*=2; if (n % k= =0) break; } k++; } while (k if (k>x) return 1; else return 0; } 2、有A、B、C、D四个元素依次入栈，即入栈序列唯一，问共能得到多少种出栈序列？能否得到以下四种出栈序列：ABCD、BDAC、CBDA、DBAC。对能得到的序列，请写出Push、Pop序列；对不能得到的序列，请说明理由。（6%） 3、矩阵Am*n以行优先方式从1000H处开始存放，元素类型未知，已知：A[2][3]存放在1011H处，A[1][1]存放在1005H处，求元素A[2][0]的存放位置。（6%） 4、根据下图所示的树回答问题：（共13%） （1）画出该树等效的二叉树。 （3%） 等效的二叉树 A B C D E F G H I J K L （2）、写出对该树进行先序、后序遍历的结点序列。（4%） （3）用带右链的先序表示法来存储此树，填写下表。（6%） 下标 0 1 2 3 4 5 6 7 8 sibling ltag element 9 10 11 5、假设用于通讯的电文仅由 {ABCDEFGH} 8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。请画出哈夫曼树并在树中标明编码情况，给出这8个字母的哈夫曼编码，最后求出WPL。（9%） 6、对下图，要求：（共13%） 1 6 3 5 7 4 4 5 7 3 4 5 2 5 5 8 8 3 5 6 6 （1）画出它的邻接表。（3%） （2）写出从顶点1到顶点8的四条路径长度为3的简单路径。（2%） （3）分别写出从顶点1出发根据（1）所示的邻接表用深度优先搜索和广度优先搜索遍历图得到的顶点序列。（4%） （4）求出它的一棵最小代价生成树(方法任选)，其代价是多少？你所求出的最小代价生成树是唯一的吗？（4%）