复习题2011春夜大(带答案)(1)

《复习题2011春夜大(带答案)(1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、复习题(1)一.填空题1．抽象数据型是数学模式和定义在设个模式上的基本操作的总称。2．举出线性表的三种存储结构顺序表示、链式表示和游标表示。3.一个队列的入队序列是a、b、c、d，则队列的输出序列为__abcd______。4.栈结构通常采用的两种存储结构是___顺序结构___和___链式结构__。5．对二叉树遍历的三种基本顺序是先序顺序、中序顺序和后序顺序。6．举出图的两种存储结构邻接表和邻接矩阵。7.采用散列技术实现散列表时，需要考虑的两个主要问题是：构造__散列函数___和解决_解决冲突__。二.选择题1.带表头的单向链表head为空的判断条件是（B）。A．h

2、ead==NULLB．head-->next==NULLC．head-->next==headD．Head!=NULL2．栈操作的原则是（B）。A．先进先出B．后进先出C．栈顶插入D．栈顶删除3.高度为5的二叉树，最多含有（B）个结点。A．16B．31C．32D．634．非空二叉树的左右链表示法中，非空链域与空链域之间的数量关系是（A）。A．前者比后者少2个B．前者比后者多2个C．前者比后者少1个D．前者比后者多1个5．已知一株二叉树的先根遍历顺序和中根遍历顺序分别是a、b、d、e、f、c和d、e、f、b、a、c，则该二叉树的后根遍历顺序是：(C)A.e、f、d、b

3、、c、aB.d、f、b、e、c、aC.f、e、d、b、c、aD.d、f、e、b、c、a6．任何一株二叉树的叶结点在先根、中根和后根遍历序列中的相对次序（A）。A.不发生改变B.发生改变C.不能确定D.以上都不对7．在无向图的邻接表表示法中，一条边（i，j）在邻接表中出现（C）次。A．0B．1C．2D．38．关键路径是AOE网中的（D）。A.最短回路B.最长回路C.从源点到汇点的最短路径D.从源点到汇点的最长路径9．折半查找要求表中的元素必须按照关键字（C）排列。A．升序B．降序C．升序或降序D．任意顺序10.一组记录的关键字为（48，83，58，43，45，88），

4、则利用堆排序的方法建立的初始堆为（C）。A．（43、45、58、83、88、48）B．（45、58、83、48、88、43）C．（43、45、48、58、83、88）D．（43、48、58、83、45、88）一.判断题.正确的在括号内画Ｖ，错误的在括号内画Ｘ1．所谓数据的逻辑结构指的是数据元素之间的逻辑关系。(对)。2．线性表的链式存储，表中元素的逻辑顺序与物理顺序一定相同。（错）3．若BT是一株二叉树，则BT中至少有一个叶结点。（对）4．若将一株树转换成二叉树，则该二叉树的根结点一定没有右子树。（对）5．无向图的邻接矩阵中各元素之和与图中边的条数相等。（错）6．完

5、全二叉树中，若一个结点没有左儿子，则该结点一定是叶。（对）7．哈夫曼树中不存在度为1的结点。（对）8．有向图的邻接矩阵一定不是对称的。（错）9．在堆中，以任何结点为根的子树仍然是堆。（对）10．在AOE网中，关键路径是唯一的。（错）二.简答题1．假设某通讯系统在通信联络中只能出现A，B，C，D，E，F六种字符,其出现的概率分别是0.07，0.09，0.12，0.22，0.23，0.27，设计该通讯系统的Huffman编码。要求：(1)按左子树根结点的权不大于右子树根结点的权的次序画出相应的Huffman树；(1)给出各字符的相应编码；答案：A:1110;B:1111

6、;C:110;D00;E:01;F:10;(2)计算编码的平均长度。答案：平均长度=4*0.07+4.0.09+3*0.12+2*0.22+2*0.23+2*0.27=2.441．二叉查找树的问题(1)画出从空的二叉查找树开始，将下列关键字按下述顺序逐个插入后建立的二叉查找树。9，14，12，5，18，7，1，15，3，16答案：(2)写出该二叉查找树的中根顺序遍历结果。答案：1，3，5，7，9，12，14，15，16，18.(3)在该二叉查找树中，查找给定关键字k=15的过程需将k=15依次与哪些关键字进行比较。答案：9，14，18，15.(1)画出在该二叉查找树

7、中删除关键字14后得到的二叉查找树。答案：五．算法设计1.设计一个将实数数组A[n]中所有的负数移到所有非负数之前的算法。主要思路：设置两个游标i和j，其中i=1,j=n；当A[i]为非负数，A[j]为负数，则交换A[i]和A[j];否则A[i]为负数，i++；A[j]为非负数，j--，直到i==j。算法如下：voidAdjustA(intA[],intn){inti=1,j=n;while(i!=j){while(A[i])<0)i++;while(A[j]>=0)j--;if(i