数据结构试卷及答案.docx

《数据结构试卷及答案.docx》由会员分享，可在线阅读，更多相关《数据结构试卷及答案.docx（11页珍藏版）》请在优知文库上搜索。

1、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的完全二叉树结

2、点个数小于或等于深度相同的满二叉树。A.(DdX三)B.C.D.(M)13、假设一棵二叉树具有10个度为2的结点，5个度为1的结点，那么度为0的结点个数是()A.9B.IlC.15D.不确定14、设森林F中有三棵树，第，第二，第三棵树的结点个数分别为Ml,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是()A.MlB.Ml+M2C.M3D.M2+M315、在下面的程序段中，对X的赋值语句的频度为1).FORi:=lTOnDOFORji=ITOnDOx:=x+l;A.O(2n)B.0(n)C.O(n2)D.O(log2n)16、一个n个顶点的连通无向图，其边的个数至少为().A.n-

3、1B.nC.n+1D.nlogn；17、二叉树的第I层上最多含有结点数为()A.2lB.2,-lC.2,D.2,-l18、以下排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆19、二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8,列下标j的范围从1到10。假设A按行存放，元素A8,5的起始地址与A按列存放时的元素()的起始地址一致。A.A8,5B.A3,10C.A5.8D.A0,920、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，那么选择好的()方法是散列文件的关键。A.散列函数B.除余

4、法中的质数C.冲突处理D.散列函数和冲突处理题号二三四总分核分人得分考前须知:得分评卷人期末考试数据结构A卷、单项选择题(请将正确答案的字母填写在每题对应的括号内，每题1分，共20分)1、下面关于串的表达中，哪一个是不正确的？()A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储2、设无向图的顶点个数为n,那么该图最多有()条边。A.n-lB.n(n-1)/2C.n(n+1)/2D.03、以下数据结构中，()是非线性数据结构。A.树B.字符串C.队列D.栈4、下面关于线性表的表达中，错误的选项是哪一个？()都A.线性表采用顺

5、序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。5、假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear,那么当前队列中的元素个数为1A.(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.C. p-next=s; p-next=s-next;

6、D.7、设栈的输入序列是1, 2, 3, 4,那么(A. 2, 4, 3 B. 2, L 3, 4s-next=p-next; p-next=s;p-next=s-next; p-next=s;)不可能是其出栈序列。C. 1, 4, 3, 2 D. 4, 3, 1, 28、广义表(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)9、栈和队都是()下表给定了这六大城市之间的交通里程:世界六大城市交通里程表(单位:百公里)PeNPaLTMPe109828121124N1095855108

7、32Pa825839792L815539589T211089795113M124329289113(1)画出这六大城市的交通网络图：(2)画出该交通网络图按权值递增的顺序来构造的最小(代价)生成树。4、假设用于通信的电文由字符集(a,b,c,d,e,f,g,h中的字母构成。它们在电文中出现的频度分别为7,19,2,6,32,3,21,10)。要求：(1)请为这8个字母设计哈夫曼编码，并画出对应的哈夫曼树；(2)计算该哈夫曼树的最小加权路径长度WPL。5、对给定的一组关键字：49,38,65,97,76,13,27,49,55,4.=命;1、算法是由假设干条得分评卷人二、判断题，在正确的题后括号

8、内打“J”，在错误的题后括号内打“X”(每题1分，共10分)指令组成的有穷序列，而一个程序不一定满足有穷性。()2、顺序存储方式只能用于存储线性结构。()3、对任何数据结构链式存储结构一定优于顺序存储结构。()4、有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵。()5、所有二叉树的度均为2。()6、满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。()7、循环链表不是线性表。()8、文件是记录的集合，文件上的操作主要有两类：检索和维护。()9、线性表的特点是每个元素都有一个前驱和一个后维。()IOs按中序遍历二叉排序树所得到中序序列是一个递增有序序列。()1、i棵树边的集合为：

9、得分评卷人三、应用题第1、4、6题每题IO分，第2、3题每题8分，第5题9分，共55分)(I.M),(I,N),(E,I),(B,E),(B.D),(A,B),(GJ),(GK),(C,G),(C,F),(H,L),(C,H),(A,C)用树形表示法画出此树，并答复以下问题：(1)哪个是此树的根结点？哪些是叶子结点？(2)树的度数和树的深度是多少？(3)写出结点G的双亲、祖先、孩子？(4)写出结点E的子孙、兄弟和结点E所在的层次？2、一棵二叉树的中序遍历序列和后序遍历序列分别为EBlFJAGDH和EIJFBGHDA。耍求：(1)画出这棵二叉树：(2)写出这棵二叉树的前序遍历序列。3、世界六大城

10、市为:北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M),得分评卷入1带四、算法设计题（第1题7分，第2题8分，共15分）头结点的动态单链表L中的结点是按整数值递增排列，试写一算法将值为X的结点插入链表L中，使L仍然有序。单链表的描述如下：typedefintdatatype;typedefstructnodedatatypedata;structnode*ncxt;Jlinklist:2、试写出递归的二分杳找（折半查找）算法。分别写出希尔排序(增量为5,3,1)、起泡排序和归并排序的前3趟排序结果。6、设散列表长度为13,即其地址空间为0-12,散列函数H(k)=K

11、mod13,对关键字序列(19,14,23,OL68,20,84,27,55,11,10,79。要求：(1)画出用线性探查法解决冲突时构造的散列表(哈希表)。(2)设每个记录的查找概率相等，计算杳找成功的平均查找长度(ASLSUCC)以及杳找不成功的平均查找长度(ASLUnSUCC)。黄淮学院2006-2007年第二学期计科系数据结构期末试卷（八）评分标准及标准答案(1)该二叉树为：(2)该二叉树前序序列:Abefijdgh一、选择题，共20个小题，每题1分，共20分；此题为单项选择题，多项选择或错选均不能得分。标准答案如下：题号1234567891011121314151617181920答

12、案BBABABDCCCCDBDCACCBD二、判断题(在正确的题后括号内打“J”，在错误的题后括号内打“X”，共10个小题,每题1分，共10分)。标准答案如下：题号12345678910答案XXXXXX三、应用题(共计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。28分(1)六大城市的交通网络图(2)最小生成树6个顶点和5条边的集合如下：V(G)=Pe,N,Pa,L,T,M)E(G)=(L,Pa,3),(Pe,T

13、,21),(MN32),(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=26159分希尔排序（增量为5,2,1）的前3趟排序结果:第1趟结果：1327495544938659776第2趟结果：4271349385549659776第3趟结果：4132738494955657697起泡排序的前3趟排序结果:第I趟结果：4493865977613274955第2趟结果：4134938659776274955第3趟结果：4132749386597764955归并排序（二路归并）的前3趟排序结果：第1趟结果：3849659713762749455第2趟结果：3849659713274976455第3趟结果：132738494965769