搜索
本试卷共6页第1页本试卷共6页第2页《数据结构》期末考试一、单项选择题（请将正确答案的字母填写在每题对应的括号内，每小题1分，共20分）1、下面关于串的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2、设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．03、以下数据结构中，（）是非线性数据结构。A．树B．字符串C．队列D．栈4、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m6、在单链表指针为p的结点之后插入指针为s的结点,正确的操作是（）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;7、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A．1，2，4，3B．2，1，3，4C．1，4，3，2D．4，3，1，2，8、广义表（a,(b,c),d,e）的表头和表尾分别为（）。A．a和(b,c),d,eB．（a）和(b,c),d,eC．a和((b,c)，d,e)D．(a)和((b,c)，d,e)二、判断题，在正确的题后括号内打“√”，在错误的题后括号内打“×”（每小题1分，共10分）9、栈和队都是（）A．顺序存储的线性结构B．链式存储的非线性结构C．限制存取点的线性结构D．限制存取点的非线性结构10、从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构11、下列四个序列中，哪一个是堆（）。A．75,65,30,15,25,45,20,10B．75,65,45,10,30,25,20,15C．75,45,65,30,15,25,20,10D．75,45,65,10,25,30,20,1512、在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④13、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定14、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M315、在下面的程序段中，对x的赋值语句的频度为（）。FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)16、一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn；17、二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-118、下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A．选择B．冒泡C．归并D．堆19、二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10。若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地址一致。A．A[8,5]B．A[3,10]C．A[5,8]D．A[0,9]20、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。A．散列函数B．除余法中的质数C．冲突处理D．散列函数和冲突处理1、算法是由若干条指令组成的有穷序列，而一个程序不一定满足有穷性。（）2、顺序存储方式只能用于存储线性结构。()3、对任何数据结构链式存储结构一定优于顺序存储结构。()4、有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵。（）5、所有二叉树的度均为2。（）6、满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。（）本试卷共6页第3页本试卷共6页第4页7、循环链表不是线性表。()8、文件是记录的集合，文件上的操作主要有两类：检索和维护。（）9、线性表的特点是每个元素都有一个前驱和一个后继。()10、按中序遍历二叉排序树所得到中序序列是一个递增有序序列。（）三、应用题（第1、4、6题每题10分，第2、3题每题8分，第5题9分，共55分）1、已知一棵树边的集合为：{(I,M),(I,N),(E,I),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,L),(C,H),(A,C)}用树形表示法画出此树，并回答下列问题：（1）哪个是此树的根结点？哪些是叶子结点？（2）树的度数和树的深度是多少？（3）写出结点G的双亲、祖先、孩子？（4）写出结点E的子孙、兄弟和结点E所在的层次？2、已知一棵二叉树的中序遍历序列和后序遍历序列分别为EBIFJAGDH和EIJFBGHDA。要求：（1）画出这棵二叉树；（2）写出这棵二叉树的前序遍历序列。3、已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M),下表给定了这六大城市之间的交通里程:世界六大城市交通里程表(单位:百公里)（1）画出这六大城市的交通网络图;（2）画出该交通网络图按权值递增的顺序来构造的最小(代价)生成树。4、假设用于通信的电文由字符集{a,b,c,d,e,f,g，h}中的字母构成。它们在电文中出现的频度分别为{7,19,2,6,32,3,21,10}。要求：（1)请为这8个字母设计哈夫曼编码，并画出对应的哈夫曼树；（2）计算该哈夫曼树的最小加权路径长度WPL。PeNPaLTMPe109828121124N109585510832Pa825839792L815539589T211089795113M124329289113姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………封…………………线…………………………本试卷共6页第5页本试卷共6页第6页5、对给定的一组关键字：49，38，65，97，76，13，27，49，55，4分别写出希尔排序（增量为5，3，1）、起泡排序和归并排序的前3趟排序结果。6、设散列表长度为13，即其地址空间为0-12，散列函数H(k)=Kmod13,对关键字序列{19，14，23，01，68，20，84，27，55，11，10，79}。要求：（1）画出用线性探查法解决冲突时构造的散列表（哈希表）。（2）设每个记录的查找概率相等，计算查找成功的平均查找长度（ASLsucc）以及查找不成功的平均查找长度(ASLunsucc)。四、算法设计题（第1题7分，第2题8分，共15分）1、已知带头结点的动态单链表L中的结点是按整数值递增排列，试写一算法将值为X的结点插入链表L中，使L仍然有序。单链表的描述如下：typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;2、试写出递归的二分查找（折半查找）算法。4《数据结构》期末试卷答案一、选择题，共20个小题，每小题1分，共20分；本题为单项选择题，多选或错选均不能得分。标准答案如下：题号1234567891011121314151617181920答案BBABABDCCCCDBDCACCBD二、判断题（在正确的题后括号内打“√”，在错误的题后括号内打“×”，共10个小题，每小题1分，共10分）。标准答案如下：题号12345678910答案√××××√×√×√三、应用题（共计55分）1、………………………………………………………………………………..10分（1）根结点为A叶子结点为：D，F，J，K，L，M，N（2）树的度为3；树的深度为5。（3）结点G的双亲为C结点G祖先为C，A结点G孩子为J，K（4）结点E的子孙为I，M，N结点E的兄弟为D结点E所在的层次为3。2、……………………………………………………………………..8分（1）该二叉树为：（2）该二叉树前序序列：ABEFIJDGH3、…………………………………………………………………..8分（1）六大城市的交通网络图JIHGFEDBA姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………封…………………线…………………………5（2）最小生成树6个顶点和5条边的集合如下：V(G)={Pe,N,Pa,L,T,M}E(G)={(L,Pa,3),(Pe,T,21),(M,N,32),(L,N,55),(L,Pe,81)}4、………………………………………………………………………………..10分（1)对应的哈夫曼树这8个字母a,b,c,d,e,f,g，h的哈夫曼编码分别为：1010，00，10000，1001，11，10001，01，1011（2）其最小的加权路径长度：WPL=19*2+21*2+32*2+6*4+7*4+10*4+2*5+3*5=38+42+64+24+28+40+10+15=261100406019212832111756710231138995929733210855581242181109PeTLMNPa8265、………………………………………………………………………………..9分希尔排序（增量为5，2，1）的前3趟排序结果：第1趟结果：1327495544938659776第2趟结果：4271349385549659776第3趟结果：4132738494955657697起泡排序的前3趟排序结果：第1趟结果：4493865977613274955第2趟结果：4134938659776274955第3趟结果：4132749386597764955归并排序（二路归并）的前3趟排序结果：第1趟结果：3849659713762749455第2趟结果：3849659713274976455第3趟结果：13273849496576974556、………………………………………………………………………………..10分（1）用线性探查法解决冲突时所构造的散列表：（2）在等概率情况下，这种方法的查找成功及查找不成功的平均查找长度（ASL）分别为：ASLsucc=1+2+1+4+3+1+1+3+9+1+1+3）/12=30/12=5/2=2.5ASLunsucc=(1+13+12+11+10+9+8+7+6+5+4+3+2)/13=7四、算法设计（第1题7分，第2题8分，共计15分）1、linklist*insert(linklist*h,datatypex)/*h是递增有序单链表的头指针，X为待插入元素*/{linklist*p,*s;p=h;while(p-next!=NULL&&p-next-datax){p=p-next;}ifp-next==NUll{s=malloc(sizeof(linklist));s-data=x;s-next=NULL;p-next=s;}else{s=malloc(sizeof(linklist));s-data=x;s-n