资源描述：
《综合练习一及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、综合练习题一一、判断题：（正确打V,错误打X并改正）1、哈希文件是一种直接存取文件。（）2、线性结构的数据可以采用顺序存储，也可以采用链式存储。非线性结构的数据只能采用链式存储。（）3、栈和队列逻辑都是线性结构，串逻辑上不是线性结构。（）4、从双向循环链表中任何一个结点出发，查找该结点的前驱和后继都很方便。（）5、对于无向连通图，从图中的任何一个顶点出发，都可以遍历图中的所有顶点。（）6、序列｛101,88,49,75,33,39,43｝构成最大堆。（）7、二叉树的中序和后序遍历序列可以唯一确定一颗二叉树。（）o8
2、、在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的增序排列存放，则可得到最小的平均搜索长度。（）二、简答题1、将n阶对称矩阵按上三角压缩存储在一维数组A中，请分析A中应包含多少个数据元素（需要推导过程）？2、队列可以用循环单链表来实现，故可以只设置头指针或者只设置一个尾指针,请问哪一个种方案更合适？请从算法的时间复杂度分析为什么？3、请简述顺序存储结构的优点和不足。三、分析题1、为了方便访问树中任何一个结点的孩子结点和双亲结点，设计应采用的存彳诸结构，并画岀此树的存储示意图。2、设哈希表为
3、HT[7],哈希函数为H(key)=key%7,按下列关键码序列｛1,17,15,45,22,12,41｝构造哈希表。(1)画出采用链表法解决冲突的哈希表；(2)计算等概率下搜索成功时的平均搜索长度。3、假设系统在某通信中只使用6种字符，其出现概率分别为0.03,0.06,0.07,0.08,0.29,0.47,现需要对通信文本文件进行压缩。(1)画出相应的Huffman树(约定左子树权值小于右子树)；(2)设计出每个字符的Huffman编码(左为0右为1);(3)简述译码的过程。4、待排序的关键码序列为｛56,7
4、,18,33,29,1,20,25｝,分别写出使用下列排序方法第一趟排序后的结果。(1)直接选择排序；(2)二路归并排序；(3)冒泡排序；(4)直接插入排序。5、画岀下网的所有最小生成树。四、算法设计题1、阅读下面顺序表的算法：constintMeixListSizc二200;//设定表可容纳的元素最大个数templateclassSeqList{Tdata[MaxListSize];intsize;//当前表的大小public:voidTnsert(constT&item,intpos);temp
5、late〈classT>voidSeqList〈T>::Insert(constT&item,intpos)//把item插入到第pos位之前{inti;if(){cout<<”顺序表已满！”;exit(0);}辻(pos<0
6、
7、)//检查参数的合法性{cout«w参数越界！”;exit(0);}for(i=size;i>pos;i--)();//数据移位()；〃插入数据sizc++;//表长增1}<1)补充完成算法Insert()；(2)计算算法Insert()的时间复杂度；(3)若不需要考虑数据固有的顺序，如何
8、使算法的效率达到0(1)?2、补充算法，完成链式堆栈的入栈操作。templateclassLinStack//定义链式堆栈类模板StackNode*top;//T为栈中元素类型，top指向栈顶intsize;//栈当前大小public:voidPush(constT&item);//入栈}；template〈classT>voidLinStack::Push(constT&item)//新元素入栈{//构造新结点newNodc,ncwNode的数据域为data,next域为topStac
9、kNode*newNode二()StackNode(item,top);()；//把新结点作栈顶()；//栈大小增加1综合练习题一参考答案一、判断题：（正确打V,错误打X并改正）1、（J）2、（X,非线性结构的数据可以采用顺序存储，也可以采用链式存储）3、（x,串逻辑上也是线性结构）4、（J）5、（J）6、（J）7、（V）8、（x,按降序排列）二、简答题1、答:数据元素个数为:n+（n-l）+…+2+1二n*（n+l）/22、答：只设置一个尾指针更合适。只设置一个尾指针，出队列和入队列的时间复杂度都是0
10、（1）;只设置头指针，出队列时间复杂度是0（n）,入队列的时间复杂度是0（n）o3、答：优点:设计简单;可随机存取数据元素；不足:存储容量需要预先确定；为保证数据的原有顺序，插入和删除数据需要移动数据元素。三、分析题1、答：应采用双亲孩子表示法。存储示意图：序号dataparent2、答:下标datalink(2)平均搜索长度二(1*4+2*2+3*1)/7
