数据结构期末复习题答案10826.pdf

《数据结构期末复习题答案10826.pdf》由会员分享，可在线阅读，更多相关《数据结构期末复习题答案10826.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-.z.1.以下与数据的存储构造无关的术语是 c C、哈希表 2.一个向量第一个元素的存储地址是 100，每个元素的长度为 2，那么第 5 个元素的地址是 B B、108 3.假设带头结点的单向循环链表的头指针为 head,那么该链表为空的判定条件是C C、headnext=head 4.假设进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进展，那么不可能出现的出栈序列是 D D、2，3，5，1，6，4 5.以下关键字序列中，构成小根堆的是 A A、12，21，49，33，81，56，69，41 6.以下数据构造中，不属于二叉树的是 A A、B 树 7.用顺序存储的方法来存储一棵二叉树

2、，存放在一维数组 A1.N中，假设结点 Ai有右孩子，那么其右孩子是 C 。C、A2i+1 8.设树 T 的高度为 4，其中度为 1、2、3、4 的结点个数分别为 4、2、1、1，那么 T 中叶子数为 D D、8 9.有数据53，30，37，12，45，24，96，从空二叉树开场逐个插入数据来形成二叉排序树，假设希望高度最小，那么应选择下面哪个序列输入 B B、37，24，12，30，53，45，96 10.对下面有向图给出了四种可能的拓扑序列，其中错误的选项是 C C、5，1，6，3，4，2 11.m 阶 B-树中所有非终端除根之外结点中的关键字个数必须大于或等于(B )B、m/2-1 12

3、.散列文件也称为(C )B、索引文件 13.数据构造是 D D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看，数据元素的直接前驱为 0 个或 1 个的数据构造只能是 C C、线性构造和树型构造 15.设 p 为指向双向循环链表中某个结点的指针，p 所指向的结点的两个链域分别用 pllink 和 prlink 表示，那么同样表示 p-.z.指针所指向结点的表达式是 D D、pllinkrlink 16.假设栈采用顺序存储方式存储，现两栈共享空间 V1.m，topi代表第 i 个栈(i=1,2)栈顶，栈 1 的底在 v1，栈 2 的底在Vm，那么栈满的条件是 B B、top

4、1+1=top2 17.假设一棵二叉树有 11 个叶子结点，那么该二叉树中度为 2 的结点个数是 A A、10 18.树的先根序列等同于与该树对应的二叉树的 A A、先序序列 19.下面关于哈希(Hash，杂凑)查找的说确的是(C )C、不存在特别好与坏的哈希函数，要视情况而定 20.以下序列中，D 是执行第一趟快速排序后所得的序列。D、68，11，69，23，18 93，73 21.以下关键字序列中，构成小根堆的是(D )D、(15，28，46，37，84，58，62，41)22.ISAM 文件和 VASM 文件属于(C )C、索引顺序文件 23.下面程序段的时间复杂度为 C for(i=0

5、;im;i+)for(j=0;jnext=s-next；s-next=p；25.为便于判别有向图中是否存在回路，可借助于 D D、拓扑排序算法 26.假设以 S 和 X 分别表示进栈和退栈操作，那么对初始状态为空的栈可以进展的栈操作系列是 D D、SSS*S*27.设有一顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次进栈，如果 6 个元素出栈的顺序是 s2,s3,s4,s6,s5,s1,那么栈的容量至少应该是(B )-.z.B、3 28.假设以数组 Am存放循环队列的元素。队列的长度为 length，指针 rear 指向队尾元素的下一个存储位置，那么队头元素所在的存储位置为B。B、

6、(rear-length+m)%m 29.在一个链队列中，front 和 rear 分别为头指针和尾指针，那么插入一个结点 s 的操作为 D 。D、rear-next=s;rear=s;30.对于哈希函数 H(key)=key%13,被称为同义词的关键字是 D D、25 和 51 31.采用二叉链表存储的 n 个结点的二叉树，共有空指针 A 个。A、n+1 32.连通网的最小生成树是其所有生成树中 D D、边的权值之和最小的生成树 33.对记录序列(314，298，508，123，486，145)依次按个位和十位进展两趟基数排序之后所得结果为 B B、508，314，123，145，486，2

7、98 34.任何一个无向连通图的最小生成树(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，v4 38.下面几个符号串编码集合中，不是前缀编码的是 B B、0,1,00,11 39.希尔排序的增量序列必须是B 。B、递减的 40.采用起泡排序法对 n 个关键字进展升序排序，假设要使排序过程中比拟关键字的次数最多，那么初始时的

8、序列应满足条件 D D、关键字从大到小排列 41.在以下部排序中(A)是不稳定的。-.z.A、希尔排序 42.分别以以下序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C )。A、100，80，90，60，120，110，130 43.在查找过程中，冲突指的是 C 。C、不同键值对应一样的存储地址 44.对有 14 个元素的有序表 A1.14作二分查找，查找元素 A4时的被比拟元素依次为 D 。D、A7，A3，A5，A4 45.以 v1 为起始结点对以下图进展广度度优先遍历，正确的遍历序列是 A A、v1，v2，v3，v4，v5，v6，v7 二、填空题(本大题共 10 小题，每题 2

9、 分，假设有两个空格，每个空格 1 分，共 20 分)1.数据的物理构造包括 数据元素 的存储和数据之间关系的存储。2.假设一个算法中的语句频度之和为 T(n)=1921n+4nlogn,那么算法的时间复杂度为 nlogn。3.下面程序段的时间复杂度是 nlog3。i=1；while(inext-next=L 17.边 种不同的拓扑序列。18.从空树起，依次插入关键字 1l，27，35，48，52，66 和 73 构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为 384。19.带头结点的双循环链表 L 中只有一个元素结点的条件是 队列 。20.求最小生成树的克鲁斯卡尔(K

10、ruskal)算法耗用的时间与图中边稠密、边稀疏 的数目正相关。21.一棵完全二叉树中共有 768 结点，那么该树中共有 5 个叶子结点。22.实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要 8、64 存放被访问的结点以实现遍历。23.Prim普里姆算法适用于求 2h-1的网的最小生成树；kruskal克鲁斯卡尔算法适用于求 2h-1 的网的最小生成树。24.对长度为 20 的有序表进展二分查找的判定树的高度为 n-1。25.设一棵完全二叉树有 128 个结点，那么该完全二叉树的深度为 n ，有_个叶子结点。26.高度为 h 的完全二叉树中最少有栈个结点，最多有个结点。2

11、7.设连通图 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进展基数排序，第一趟排序后的结果是。三、应用题本大题共

12、5 小题，每题 6 分，共 30 分 1.二叉树的先序遍历序列 ABCDEFGH，中序遍历序列为 CBEDFAGH，画出二叉树。答案：二叉树形态 2.如图请给出邻接表、邻接矩阵及逆邻接表。-.z.参考答案如下：1邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1)vertex firstedge next 2逆邻接表：3 3.由字符集s，t，a，e，I及其在电文中出现的频度构建的哈夫曼树如下图。某段电文的哈夫曼编码为 0，请根据该哈夫曼树进展译码，写出原来的电文。答案：原来的电文为：eatst 4.请画出以下图所示的树所对应的二叉树，并写出对应二叉树的先序遍历和中序

13、遍历。答案：先序遍历为：12345687 中序遍历为：34867521 5.设散列表为 HT13,散列函数为 H(key)=key%13。用闭散列法解决冲突,对以下关键码序列 12,23,45,57,20,03,78,31,15,36 造表。采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的平均搜索长度。1 2 3 4 5 6 7 8 V1 V3 V2 V4 1 2 3 4 5 6 7 8-.z.答案：使用散列函数 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

14、(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=110(1+1+1+1+1+1+4+1+2+1)=1410 6.带权图 G 如下图，画出图 G 的一棵最小生成树。答：7.假 设 用 于 通 信 的 电 文 由 字 符 集 a,b,c,d,e,f,g,h 中 的 字 母 构 成，这 8 个 字 母 在 电 文 中 出 现 的 概 率 分 别 为0.07,0.1

15、9,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=69 9.画出与如下图森林对应的二叉树。答：10.一个散列表如以下图所示：35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为 h(key)=key%13,处理冲突

16、的方法为双重散列法，探查序列为：hi=(h(key)+i*h1(key)%m i=0,1,，m-1-.z.其中：h1(key)=key%11+1 答复以下问题：1对表中关键字 35，20，33 和 48 进展查找时，所需进展的比拟次数各为多少？2该散列表在等概率查找时查找成功的平均查找长度为多少？答：对关键字 35、20、33 和 48 进展查找的比拟次数为、；平均查找长度ASL 321 12595 11.请画出与以下二叉树对应的森林。答：12.对于给定结点的关键字集合 K=5，7，3，1，9，6，4，8，2，10，1试构造一棵二叉排序树；2求等概率情况下的平均查找长度 ASL。答：2ASL=

17、(1*1+2*2+3*4+4*3)/10=2.9 13.给出以下图对应的邻接矩阵，并给出 A，B，C 三个顶点的出度与入度 答案:邻接矩阵为：A B C D E F 其中顶点 A 的入度为 2，出度为 1；其中顶点 B 的入度为 2，出度为 2；其中顶点 C 的入度为 1，出度为 3；14.图 5.32 如下所示，求从顶点 a 到其余各顶点的最短路径。给出求解过程 7 4 3 1 2 5 9 6 10 8 5 4 3 2 2 3 3 5 6 a b d f c e-.z.答：终点 最短路径求解过程 b 6(a,b)5(a,c,b)c 3(a,c)d 6(a,c,d)6(a,c,d)e 7(a,

18、c,e)7(a,c,e)7(a,c,e)f 9(a,c,d,f)9(a,c,d,f)vj c b d e f S a,c a,c,b a,c,d a,c,e a,c,d,f 15.阅读以下算法，并答复以下问题：1假设串由合法的英文字母和空格组成，并以0作完毕符。设串 s=I am a student(表示空格符)，写出 f30s的返回值；2简述算法 f30 的功能。int f30(char*s)答案：(1)4(2)算法功能：统计单词的个数。16.阅读以下函数,并答复以下问题：1假设队列 q 中的元素为(a,b,c,d,e),其中a为队头元素。写出执行函数调用 Conv(&q)后的队列 q；2简

19、述算法 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 2第二趟pass=1 18.带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为 m，散列函数为 Hash(key)=key%m。链表的结点构造为：。请在空缺处填入适当容，使其成为一个完整算法。void f3

20、3(LinkList L,LinkList H,int m)答案：（1）NULL 2p-next=Hj p=q 19.以下函数的功能是，对以带头结点的单链表作为存储构造的两个递增有序表表中不存在值一样的数据元素进展如下操作：将所有在 Lb 表中存在而 La 表中不存在的结点插入到 La 中，其中 La 和 Lb 分别为两个链表的头指针。请在空缺处key next-.z.填入适宜容，使其成为一个完整的算法。答案：1pre-next=pb 2pre-next=pa 3pre-next=pb 20.阅读算法 f30，并答复以下问题：以下算法为有向图拓扑排序,请在空缺处填入适宜的容，使其成为一个完整的

21、算法。答案：(1top=-1 2top=graphj.count 3graphk.count=0 21.阅读算法 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.编写一个函数，要求借助一个栈把一个数

22、组中的数据元素逆置。其中，栈类型为 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);-.z.for(i=0;ileft);num2=twochild1(b-right);if(b-left!=NULL&b-right!=NULL)return(num1+num

23、2+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)就后继的不同情况，简要表达实现求后继操作的方

24、法；参考答案：1分两种情况讨论 当*px 的右子树不为空时，那么从*px 的右孩子开场，沿其左孩子往下查找，直到找到一个没有左孩子的节点为止，那么该结点为*px 在中序序列中的后继；当*px 的右孩子为空时，那么沿*px 的双亲指针链向上查找，直至找到其左子树中包含*px 的最年轻祖先，那么该祖先结点为*px 在中序序列中的后继。(2)编写算法求 px 所指结点的中序序列后继，并在算法语句中加注注释。2BinTree f34(BinTree px)BinTree q=px-rchild;if(q!=NULL)/沿左孩子往下查找 px=q;-.z.while(px-lchild!=NULL)px

25、=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=

26、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;-.z.return degree;7.编写算法实现对给定的二叉树是否为二叉排序树的判别。设二叉树以二叉链表存储表示。要求写出二叉链表的类型定义 参考答案：/二叉树的二叉链表表示 typedef struct BINTREENODE ElemT

27、ype 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