数据结构练综合练习及答案

《数据结构练综合练习及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、综合练习题一一、简答题1、简述算法及其特性和其复杂性的度量标准。2、简述数据的逻辑结构的种类。3、简述排序算法的稳定性并列举三种以上稳定的排序算法。4、简述在顺序表的第i个元素的位置上插入数据x的算法思想。5、己知完全二叉树有80个结点，试问其深度及度为2的结点数目。6、简述算法的基本概念及其分析的主要内容7、简述堆栈和队列的运算特性。8、堆栈的入栈序列为a,b,c,d,e问可否得到相应的出栈序列abcde和edcba9、简述在顺序表的第i个元素的位置上删除数据x的算法思想。二、分析计算题1、计算下列算法中带@记号的语句的频度及算法的时间复杂度。(1)s二0;for(i=0;i

2、++)for(j=0;j=i;j-)sum+=2;@(3)i=l;while(i<=n)i=i*3;@2、请给出下图所示的二叉树的先序遍历、中序遍历和后序遍历的结果。3、已知某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,试确定该二叉树的具体形态，并写岀其后序遍历结果。4、有七个带权结点，其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点构造一棵霍夫曼树，并计算出带权路径长度WPL和相应结点的霍夫曼编码。5、试给出下图所示的无向图的深度优先遍历

3、和广度优先遍历的结果。baec〔6、试给出下图所示的有向图的邻接表存储结构。7、下图所示的矩阵是一个无向网。请⑴设计该无向网的邻接矩阵(2)求出该网的所有最小生成树o11,给定的关键码序列为19,14,01,68,20,84,27,55,11,29,33,35。试画出用线性探测法解决冲突时所构造的哈希表并计算在等概率下搜索成功的平均搜索长度。9、写出对数据记录(54,38,96,23,15,72,60,45,83)用起泡法排序及直接插入排序两种方法进行排序时的数据变化过程(只需写岀每一趟的排序结果)。10、已知数据序列为16,25,35,48,23,40,79,82,36,72,请将其

4、构造成为一个最大堆和一个最小堆。三、算法设计HiS1、以下算法是在带头节点的单链表L中第i个位置之前插入元素e,阅读算法,填写空口处。StatusListInsert(LinkList&L,inti,Elemtypee){p=L;i=0;while(p&&j

5、

6、j>i-l)returnERROR;//i不合法;//生成新节点;//插入L中returnOK;}2、阅读下面的算法程序，补上空格处的语句：typedefstruct{Elemtype*elem;〃数据元素存储空间基址，建表时按实际长度分配,0号单元留空intlength;〃表长度}SS

7、Table;//静态查找表的顺序存储结构intSearch_Bin(SSTableSt,KeyTypekey)}//关键字从小到大排好low=1;high=St.length;while(low<=high){mid=(low+high)/2;ifEQ(key,St.elem[mid].key)return;//EQ表示第一个参数值与第二个相等elseifLT(key,St.elem

8、mid.keyI)；//LT表示第一个参数值比第二个小else;}return0;}//Search_Bin