2017数据结构期末考试试题及答案

1、第第 页共23页4、图深度优先序列广度优先序列邻接矩阵表示时0,1,2,8,3,4,5,6,7,90,1,4,2,7,3,8,6,5,9邻接表表示时0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5四、阅读算法，回答问题（每小题8分，共16分）3、此二叉树的后序遍历结果是:EDCBIHJGFA1、该算法的输入结果是：3491304563782、该算法的功能是：交换二叉树的左右子树的递归算法五、算法填空，在画有横线的地方填写合适的内容(10分)是：(low+high)/2;是：Binsch(A,low,mid-1,K);是：Binsch(A,mid+1,high,K);

2、是：-1;六、编写算法(10分)根据编程情况，酌情给分。Lnode*P=HL;HL=NULL;While(p!=null)Lnode*q=p;P=pTnext;qfnext=HL;HL=q;数据结构期末考试试题及答案3一、单项选择题1对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为()。(A)、正确性(B)可行性(C)健壮性(D)输入性设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为()。for(i=n-1;i=0;i-)for(j=0;jnext;p-next=Q.rear-next;、p=Q-next;Q-next=p-next;9.Huffman树的带权路径

3、长度WPL等于(A)、(A)、除根结点之外的所有结点权值之和(B)、所有结点权值之和(C)、各叶子结点的带权路径长度之和(D)(C)、各叶子结点的带权路径长度之和(D)、根结点的值10.线索二叉链表是利用()域存储后继结点的地址。(A)、Ichild(B)、data(C)、rchild(D)、root二、填空题1.逻辑结构决定了算法的，而存储结构决定了算法的。2栈和队列都是一种的线性表，栈的插入和删除只能在进行。3.线性表(a.,a2a)的顺序存储结构中，设每个单元的长度为L,元素a的存储地址i2nLOC(a)为4.已知一双向链表如下(4.已知一双向链表如下(指针域名为next和prior):

4、现将p所指的结点插入到x和y结点之间，其操作步骤为：TOC o 1-5 h z，个结点无向完全图的的边数为已知一有向无环图如下：n个结点的生成树的边数为。已知一有向无环图如下：任意写出二种拓扑排序序列：已知二叉树的中序遍历序列为BCA后序遍历序列为CBA则该二叉树的先序遍历序列为，层序遍历序列为。三、应用题1.设散列函数H(k)=k%13,设关键字系列为22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。(6分)构造HASH表。分别求查找成功和不成功时的平均查找长度。2.给定表(19,14,22,15,20,21,56,10).(8分)按元素在表中的次序，建立一棵二叉排序

5、树对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列(3)画出对(2)中的遍历序列进行折半查找过程的判定树。已知二个稀疏矩阵A和B的压缩存储三元组表如下:ABijVijV13-525224633725241342-152-9529558写出A-B压缩存储的三兀组表。(5分)4.已知一维数组中的数据为(18,12,25,53,18_),试写出插入排序(升序)过程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)5.已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有过程)ABCDEFA651B653C572D15764E366F246(1)求从顶点A开始的最小生成树。（

6、2）分别画出以A为起点的DFS生成树和BFS生成树。6.已知数据六个字母及在通信中出现频率如下表:ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作（7分，要有过程）。（1）画出对应的Huffman树。（2）计算带权路径长度WPL（3）求A、BC、D、E、F的Huffman编码。7.已知有如下的有向网:AEB6246CD27.已知有如下的有向网:AEB6246CD2求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）四、设计题（30分，每题10分，用C语言写出算法，做在答题纸上）1.已知线性表（ai5a2,-,a）以顺

7、序存储结构为存储结构，其类型定义如下：12n#defineLIST_INIT_SIZE100顺序表初始分配容量typedefstructElemtype*elem;/顺序存储空间基址intlength;/当前长度（存储元素个数）SqList;设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：StatusListDelete(Sqlist&L,Elemtypex)2设顺序栈如左图所示。其中结点定义如下:typedefstructElemtype*base;/栈底指针Elemtype*top;/栈顶指针Stack;base设计算法，将栈顶元素

8、出栈并存入e中.base3.设二叉链树的类型定义如下：typedefintElemtype;typedefstructnodeElemtypedata;structnode*lchild,*rchild;BinNode,*BinTree;试写出求该二叉树叶子结点数的算法：StatusCountLeaves(BinTree&root,int&n)/nisthenumberofleaves试题3答案一、选择题（每题1分）1.C2、D3、A4、D5、C6、D7、A8、B9、C10、C二、填空题1设计、实现2.特殊、栈顶3.LOC(a1)+(i-1)*Lp_next=q_next;q_next-pri

9、or=p;q_next=p;p_prior=q;n(n-1)/2、n-1ADCBFEG、ABCDEFFGABC、ABC三、应用题1.（1）Hash表（4分）地址0123456789101112关键安：132164572282412探测次数171231311（2）查找成功的平均查找长度：（1分）（5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找长度：（1分）（2+1+9+8+7+6+5+4+3+2+1）/13=2.（1）、构造（3分）21(2)、1014151920212256(2分)、(3分3、（5分，每行0.5）ijv13-524633741342-152185584初始关

10、键字：1812255318、第一趟：12-18255318第二趟：1218255318第三趟:1218255318第四趟：121818-2553（4分）O（n2）（1分）。5、7分（1）4分A（2）4分6、（1）3分TOC o 1-5 h z（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*2仁（1分）（3）A:010B:011C:110D:111E：00F;10（3分）7、A-B:（A、B）1分A-C:（A、D、C）2分A-D:（A、D）1分A-E:（A、D、E）2分四、设计题(30分)1、(10分)StatusListDelete(Sqlist&L,ElemTypex)inti,j;for(i=0;ilength;i+)if(L-elemi=x)break;if(i=L-length)returnERROR;for(j=i;jlengthi_1;j+)L-elemj=L-elemj+1;L-length-;(8分)平均时间复杂度：(2分)设元素个数记为n,则平均时间复杂度为：1(ni)ni12、(10分)voidpop(Stack&S,Elemtyp