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

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

ID:2285329

大小:93.00 KB

页数:8页

时间:2017-11-15

复习题2011春夜大(带答案)(1)_第1页
复习题2011春夜大(带答案)(1)_第2页
复习题2011春夜大(带答案)(1)_第3页
复习题2011春夜大(带答案)(1)_第4页
复习题2011春夜大(带答案)(1)_第5页
资源描述:

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

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

2、.选择题1.带表头的单向链表head为空的判断条件是(B)。A.head==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.已知一株二叉树的

3、先根遍历顺序和中根遍历顺序分别是a、b、d、e、f、c和d、e、f、b、a、c,则该二叉树的后根遍历顺序是:(C)A.e、f、d、b、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.从源点到

4、汇点的最短路径D.从源点到汇点的最长路径9.折半查找要求表中的元素必须按照关键字(C)排列。A.升序B.降序C.升序或降序D.任意顺序10.一组记录的关键字为(48,83,58,43,45,88),则利用堆排序的方法建立的初始堆为(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)一.判断题.正确的在括号内画V,错误的在括号内画X1.所谓数据的逻辑结构指的是数据元素之间的逻辑关系

5、。(对)。2.线性表的链式存储,表中元素的逻辑顺序与物理顺序一定相同。(错)3.若BT是一株二叉树,则BT中至少有一个叶结点。(对)4.若将一株树转换成二叉树,则该二叉树的根结点一定没有右子树。(对)5.无向图的邻接矩阵中各元素之和与图中边的条数相等。(错)6.完全二叉树中,若一个结点没有左儿子,则该结点一定是叶。(对)7.哈夫曼树中不存在度为1的结点。(对)8.有向图的邻接矩阵一定不是对称的。(错)9.在堆中,以任何结点为根的子树仍然是堆。(对)10.在AOE网中,关键路径是唯一的。(错)二.简答题

6、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;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.44

7、1.二叉查找树的问题(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)画出在该二叉查找树中删除关键字14后得到的二叉查找树。答案:五.算法设计1.设计一个将实数数组A[n]中所有的负数移到所有非负数

8、之前的算法。主要思路:设置两个游标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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。