资源描述
1. 以下与数据的存储结构无关的术语是( c )C、哈希表 2. 一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( B ) B、1083. 假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是( C )C、headnext= =head 4. 若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是( D )D、2,3,5,1,6,45. 下列关键字序列中,构成小根堆的是( A )A、12,21,49,33,81,56,69,41 6. 下列数据结构中,不属于二叉树的是( A )A、B树 7. 用顺序存储的方法来存储一棵二叉树,存放在一维数组A1.N中,若结点Ai有右孩子,则其右孩子是( C )。 C、A2i+1 8. 设树T的高度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1,则T中叶子数为( D ) D、 89. 有数据53,30,37,12,45,24,96,从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,则应选择下面哪个序列输入( B )B、37,24,12,30,53,45,9610. 对下面有向图给出了四种可能的拓扑序列,其中错误的是( C )C、5,1,6,3,4,2 11. m阶B-树中所有非终端(除根之外)结点中的关键字个数必须大于或等于( B ) B、m/2-112. 散列文件也称为( C ) B 、索引文件13. 数据结构是( D )D、相互之间存在一种或多种特定关系的数据元素的集合14. 从逻辑关系来看,数据元素的直接前驱为0个或1个的数据结构只能是( C )C、线性结构和树型结构 15. 设p为指向双向循环链表中某个结点的指针,p所指向的结点的两个链域分别用pllink和prlink表示,则同样表示p指针所指向结点的表达式是( D ) D、pllinkrlink16. 若栈采用顺序存储方式存储,现两栈共享空间V1.m,topi代表第i个栈( i =1,2)栈顶,栈1的底在v1,栈2的底在Vm,则栈满的条件是( B )B、 top1+1=top2 17. 若一棵二叉树有11个叶子结点,则该二叉树中度为2的结点个数是( A )A、1018. 树的先根序列等同于与该树对应的二叉树的( A )A、先序序列19. 下面关于哈希(Hash,杂凑)查找的说法正确的是( C )C、不存在特别好与坏的哈希函数,要视情况而定20. 下列序列中,( D )是执行第一趟快速排序后所得的序列。 D、 68,11,69,23,18 93,7321. 下列关键字序列中,构成小根堆的是( D )D、 (15,28,46,37,84,58,62,41)22. ISAM文件和VASM文件属于( C ) C、索引顺序文件 23. 下面程序段的时间复杂度为( C )for (i=0; im; i+)for (j=0; jnext=s-next;s-next=p; 25. 为便于判别有向图中是否存在回路,可借助于( D )D、拓扑排序算法26. 若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是( D )D、SSSXXSXX27. 设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是( B )B、3 28. 假设以数组Am存放循环队列的元素。已知队列的长度为length,指针rear指向队尾元素的下一个存储位置,则队头元素所在的存储位 置为( B )。B、(rear-length+m)%m 29. 在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为( D )。D、rear-next=s;rear=s;30. 对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )D、25和5131. 采用二叉链表存储的n个结点的二叉树,共有空指针( A )个。A、n+132. 连通网的最小生成树是其所有生成树中( D )D、边的权值之和最小的生成树33. 对记录序列(314,298,508,123,486,145)依次按个位和十位进行两趟基数排序之后所得结果为( B ) B、508,314,123,145,486,29834. 任何一个无向连通图的最小生成树( C )。C、一棵或多棵 35. 无向图的邻接矩阵是一个( C ) C、对称矩阵 36. 设无向图G-=(V,E)和G=(V,E),如G为G的生成树,则下列说法中不正确的是( B )。B、G为G 连通分量37. 以v1为起始结点对下图进行深度优先遍历,正确的遍历序列是( D )D、 v1,v2,v5,v6,v7,v3,v438. 下面几个符号串编码集合中,不是前缀编码的是( B )B、0,1,00,1139. 希尔排序的增量序列必须是(B )。B、递减的 40. 采用起泡排序法对n个关键字进行升序排序,若要使排序过程中比较关键字的次数最多,则初始时的序列应满足条件( D ) D、关键字从大到小排列41. 在下列内部排序中( A )是不稳定的。A、希尔排序42. 分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( C )。A、(100,80, 90, 60, 120,110,130) 43. 在查找过程中,冲突指的是( C )。C、不同键值对应相同的存储地址44. 对有14个元素的有序表A1.14作二分查找,查找元素A4时的被比较元素依次为( D )。D、A7,A3,A5,A445. 以v1为起始结点对下图进行广度度优先遍历,正确的遍历序列是( A )A、 v1,v2,v3,v4,v5,v6,v7二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分)1. 数据的物理结构包括 数据元素 的存储和 数据之间关系 的存储。2. 若一个算法中的语句频度之和为T(n)=1921n+4nlogn,则算法的时间复杂度为 nlogn 。 3. 下面程序段的时间复杂度是 。 i=1; while (inext-next=L 17. 边 种不同的拓扑序列。18. 从空树起,依次插入关键字1l,27,35,48,52,66和73构造所得的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度为 384 。19. 带头结点的双循环链表L中只有一个元素结点的条件是 队列 。 20. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 边稠密 、边稀疏 的数目正相关。21. 已知一棵完全二叉树中共有768结点,则该树中共有 5 个叶子结点。22. 实现图的广度优先搜索,除了一个标志数组标志已访问的图的结点外,还需要 8、64 存放被访问的结点以实现遍历。23. Prim(普里姆)算法适用于求 2h-1 的网的最小生成树;kruskal(克鲁斯卡尔)算法适用于求 2h-1 的网的最小生成树。24. 对长度为20的有序表进行二分查找的判定树的高度为 n-1 。25. 设一棵完全二叉树有128个结点,则该完全二叉树的深度为 n ,有_ 个叶子结点。26. 高度为h的完全二叉树中最少有 栈 个结点,最多有 个结点。27. 设连通图G中有n个顶点e条边,则对应的最小生成树上有 3 条边。28. 构造n个结点的强连通图,至少有 O(n2) 条弧。29. 表达式求值是 (42,13,94,55,05,46,17) 应用的一个典型例子。30. 设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈的容量至少应该是 。31. 快速排序算法在最差的情况下其时间复杂度是 。32. 对序列55,46,13,05,94,17,42进行基数排序,第一趟排序后的结果是 。三、应用题(本大题共5小题,每小题6分,共30分)1. 已知二叉树的先序遍历序列ABCDEFGH,中序遍历序列为CBEDFAGH,画出二叉树。答案:二叉树形态 2. 如图请给出邻接表、邻接矩阵及逆邻接表。V1V3V2V4参考答案如下:(1)邻接表:(注意边表中邻接点域的值是顶点的序号,这里顶点的序号是顶点的下标值-1) vertex firstedge next (2)逆邻接表:(3)3. 由字符集s,t,a,e,I及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100,请根据该哈夫曼树进行译码,写出原来的电文。答案:原来的电文为:eatst4. 请画出下图所示的树所对应的二叉树,并写出对应二叉树的先序遍历和中序遍历。12345678答案:12345678先序遍历为:12345687 中序遍历为:348675215. 设散列表为HT13, 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。答案:使用散列函数 H(key) = key mod 13,有H(12) = 12, H(23) = 10,H(45) = 6,H(57) = 5,H(20) = 7,H(03) = 3,H(78) = 0,H(31) = 5,H(15) = 2,H(36) = 10.利用线性探查法造表: 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1)搜索成功的平均搜索长度为ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 6. 已知带权图G如图所示,画出图G的一棵最小生成树。答:7. 假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成,这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,请为这8个字母设计哈夫曼编码。哈夫曼编码为:a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000注意:答案不唯一8. 试用权集合12,4,5,6,1,2构造哈夫曼树,并计算哈夫曼树的带权路径长度。WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=699. 画出与如图所示森林对应的二叉树。答:10. 已知一个散列表如下图所示:3520334859 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法,探查序列为: hi=(h(key)+*h1(key)%m =0,1,,m-1其中: h1(key)=key%11+1回答下列问题:(1)对表中关键字35,20,33和48进行查找时,所需进行的比较次数各为多少?(2)该散列表在等概率查找时查找成功的平均查找长度为多少?答:()对关键字35、20、33和48进行查找的比较次数为、;()平均查找长度11. 请画出与下列二叉树对应的森林。答:12. 对于给定结点的关键字集合K=5,7,3,1,9,6,4,8,2,10,(1)试构造一棵二叉排序树;(2)求等概率情况下的平均查找长度ASL。答:74312596108(2)ASL=(1*1+2*2+3*4+4*3)/10=2.913. 给出下图对应的邻接矩阵,并给出A,B,C三个顶点的出度与入度 答案: 邻接矩阵为: A B C D E F其中顶点A的入度为2,出度为1;其中顶点B的入度为2,出度为2;其中顶点C的入度为1,出度为3;14. 已知图5.32如下所示,求从顶点a到其余各顶点的最短路径。(给出求解过程)543223356abdfce答:终点最短路径求解过程b6 (a,b)5 (a,c,b)c3 (a,c)d6 (a,c,d)6 (a,c,d)e7 (a,c,e)7 (a,c,e)7 (a,c,e)f9 (a,c,d,f)9 (a,c,d,f)vjcbdefSa,ca,c,ba,c,da,c,ea,c,d,f15. 阅读下列算法,并回答问题:(1)假设串由合法的英文字母和空格组成,并以0作结束符。设串s=”Iamastudent”(表示空格符),写出f30(s)的返回值;(2)简述算法f30的功能。int f30 (char*s)答案:(1) 4(2)算法功能:统计单词的个数。16. 阅读下列函数,并回答问题:(1)假设队列q中的元素为(a,b,c,d,e),其中“a”为队头元素。写出执行函数调用Conv(&q)后的队列q;(2)简述算法Conv的功能。答案:(1) e,d,c,b,a(2) 将队列里的值反转17. 阅读下列函数,并回答问题:已知整形数组L1.8中的元素依次为(19,18,15,17,16,13,12,10),阅读下列函数,并写出执行函数调用sort(L, 8)时,对L进行的头两趟(pass分别为0和1)处理结果。答案:(1)第一趟(pass = 0)19 15 18 16 17 12 13 10(2)第二趟(pass = 1)19 15 16 18 12 17 10 13keynext18. 已知带头结点的单链表中的关键字为整数,为提高查找效率,需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m,散列函数为Hash(key)=key%m。链表的结点结构为: 。请在空缺处填入适当内容,使其成为一个完整算法。void f33 (LinkList L, LinkList H, int m)答案:(1) NULL (2)p-next=Hj p=q19. 下列函数的功能是,对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操作:将所有在Lb表中存在而La表中不存在的结点插入到La中,其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容,使其成为一个完整的算法。答案:(1)pre-next=pb (2)pre-next=pa (3)pre-next=pb20. 阅读算法f30,并回答问题:下列算法为有向图拓扑排序,请在空缺处填入合适的内容,使其成为一个完整的算法。答案:(1)top=-1 (2)top=graphj.count (3)graphk.count=021. 阅读算法f31,并回答问题:下列算法功能为在数组a的前n(n=1)个元素中找出第k(1=kai+1,将二者交换;以后重复上述二趟过程,直至整个数组有序。请在空缺处填入合适的内容,使其成为一个完整的算法。答案: (1)ai=t (2)(i=2;inext) return ERROR; p=head-next; q=p-next; p-next =NULL; while(q) p=q; q=q-next; p-next=head-next; head-next=p; 2. 编写一个函数,要求借助一个栈把一个数组中的数据元素逆置。其中,栈类型为SeqStack,可以直接使用InitStack(SeqStack*)、Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函数。参考答案:void Inverse(ElemType arr,int n)SeqStack *s;int i;InitStack(&s);for(i=0;in;i+) /数组元素依次入栈Push(s,arri);for(i=0;ileft); num2=twochild1(b-right);if ( b-left!=NULL&b-right!=NULL) return (num1+num2+1); else return (num1+num2); 4. 假设以带双亲指针的二叉链表作为二叉树的存储结构,其结点结构的类型说明如下所示:typedef char DataType;typedef struct node DataType data; struct node *lchild, *rchild; /左右孩子指针 struct node *parent; /指向双亲的指针 BinTNode;typedef BinTNode *BinTree;若px为指向非空二叉树中某个结点的指针,可借助该结构求得px所指结点在二叉树的中序序列中的后继。(1)就后继的不同情况,简要叙述实现求后继操作的方法;参考答案:(1)分两种情况讨论当*px的右子树不为空时,则从*px的右孩子开始,沿其左孩子往下查找,直到找到一个没有左孩子的节点为止,则该结点为*px在中序序列中的后继;当*px的右孩子为空时,则沿*px的双亲指针链向上查找,直至找到其左子树中包含*px的最年轻祖先,则该祖先结点为*px在中序序列中的后继。(2)编写算法求px所指结点的中序序列后继,并在算法语句中加注注释。(2)BinTree f34(BinTree px)BinTree q=px-rchild;if(q!=NULL)/沿左孩子往下查找px=q;while(px-lchild!=NULL)px=px-lchild;else/沿双亲指针链向上查找while(px!=NULL & px-rchild=q)q=px;px=px-parent;return px;/返回所找到的中序序列后继结点的指针 /或者无后继结点时返回空指针5. 已有邻接表表示的有向图,请编程判断从第u顶点至第v顶点是否有简单路径,若有则印出该路径上的顶点。参考答案: void AllSPdfs(AdjList g,vertype u,vertype v) /求有向图g中顶点u到顶点v的所有简单路径,初始调用形式:AllSPdfs(g,u,v)int top=0,s; s+top=u; visitedu=1; while (top0 | p) p=gstop.firstarc; /第一个邻接点。 while (p!=null & visitedp-adjvex=1) p=p-next; /下一个访问邻接点表。 if (p=null) top-; /退栈。 else i=p-adjvex; /取邻接点(编号)。 if (i=v) /找到从u到v的一条简单路径,输出。 for (k=1;knext; return degree;7. 编写算法实现对给定的二叉树是否为二叉排序树的判别。设二叉树以二叉链表存储表示。(要求写出二叉链表的类型定义)参考答案:/二叉树的二叉链表表示typedef struct BINTREENODE ElemType data;struct BINTREENODE *lchild, rchild; BinNode,*BinTree /答对给2分int BsBtr(BinTree t, BinTree pre, int flag) /判别给定的二叉树是否为二叉排序树pre =NULL; flag=TRUE; if (t & flag) BSBtr(t-lchild, pre, flag); if (pre = = NULL) flag=TRUE;pre=t; else if(pre-key key) /比较t 与中序直接前驱pre的大小 flag=TRUE; pre=t; /pre与t有序 else flag=FALSE; /pre与t无序 /if BSBtr(t-rchild,pre,flag); /BSBtr 17
展开阅读全文