数据结构试卷A 附答案.docVIP

计算机学院2010-2011学年第一学期 《数据结构》试卷（A卷）（考试时间：100分钟） 专业： 班级： 序号： 姓名： 题 号 一 二 三 四 总分 题 分 20 20 50 10 得 分 阅卷人 注意：所有答案都必须写在答题纸上！！！ 二简答题： 1 哈夫曼编码 假设用于通信的电文仅由8个字母：A B C D E F G H组成，字母在电文中出现的频率分 别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。并计算其带权路径长度。 2请对下图的无向带权图：写出它的邻接矩阵，并按普里姆算法求其最小生成树 3 利用先序和中序生成一个树 给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树T ， 并给出其后序遍历序列 。 4 森林和二叉树的转换 画出和下列二叉树相应的森林 5 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 ； 初始步长为4的希尔（shell）排序一趟的结果是 ； 二路归并排序一趟扫描的结果是 ； 快速排序一趟扫描的结果是 ； 堆排序初始建堆的结果是 。 三程序题 编写算法判别给定二叉树是否为完全二叉树 1 先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32 （100） （40） （60） 19 21 32 （28） （11） 7 10 6 （5） 2 3 0 1 0 1 0 1 0 1 0 1 0 1 21 32 1 0 1 0 1 10 6 1 2 3 编码为：A :1100 B:00 C:11110 D:1110 E:10 F: 11111 G:01 H:1101 2 请对下图的无向带权图：写出它的邻接矩阵，并按普里姆算法求其最小生成树 解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!邻接矩阵为： 3 4 D D A F I G C E B H 其后续序列为：BHECIGFAD 5 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ； 初始步长为4的希尔（shell）排序一趟的结果是 P A C S Q H F X R D M Y ； 二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ； 堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。 四算法 答：int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 { InitQueue(Q); flag=0; EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) { { DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else { EnQueue(Q,p-lchild); EnQueue(Q,p-rchild); //不管孩子是否为空,都入队列 } }//while return 1; }//IsFull_Bitree