数据结构 习题与解答.ppt

《数据结构 习题与解答.ppt》由会员分享，可在线阅读，更多相关《数据结构 习题与解答.ppt（66页珍藏版）》请在三一文库上搜索。

1、 数据结构习题 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 第六章 树和二叉树 第七章图 第八章 动态存储管理 第九章 查找 第十章 内部排序 第十一章 外部排序 1 1 1.1 简述下列术语:数据结构、存储结构、数据类型和抽象 数据类型. 1.2 若n为正整数，计算下列式子的时间复杂度。 （1）for(i=0; in*n; i+) int x=0; x+; （2）for(i=0; in; i+) for(i=0; inext=S; (2)P-next=P-next-next; (3)P-next=S-next; (4)s-next=P-next; (5)

2、S-next=L; (6)S-next=NULL; (7)Q=P; (8)while(P-next!=Q)P=P-next; (9)while(P-next!=NULL)P=P-next; (10)P=Q; (11)P=L; (12)L=S; (13)L=P; 4 4 2.2已知L是带表头结点的非空单链表，且P结点既不是首元 结点，也不是尾元结点，试从下列提供的答案中选择合适 的语句序列. a.删除P结点的直接后继结点的语句序列_11.3_.14_ c.删除P结点的语句序列是_ 10.12.7.3.14_ d.删除首元结点的语句序列是_12.11.3.14 e.删除尾元结点的语句序列是_9.1

3、1.3.14_ (1) P=P-next, (2) P-next=P; (3) P-next =P-next-next; (4) P =P-next-next; (5) while( P! = NULL)P = P-next. (6) while (Q-next != NULL)(P=Q, Q=Q-next; (7) while(P-next !=Q)P=P-next ; (8) while(P-next-next !=Q)P = P-next ; (9) while(P-next-next!= NULL)P = P-next ; (10)Q=P, (11) Q = P-next; (12)

4、P=L; (13) L= L-next; (14) free(Q); 5 5 2.3对单链表中元素按插入方法排序的C语言描述算法如下， 其中L为链表头结点指针。请填充算法中标出的空白处，完 成其功能。 typedefstructnode intdata;structnode*next; linknode,*link; voidInsertsort(linkL) linkp,q,r,u; p=L-next;(1)_; while(2)_) r=L;q=L-next; while(3)_q=q-next; u=p-next;(4)_;(5)_; p=u; 6 6 2.4设顺序表va中的数据元素递增

5、有序。试写一算法，将x插入 到顺序表的适当位置上，以保持该表的有序性. 2.5假设有两个元素值递增有序排列的线性表A和B,均以单链表 作存储结构,请编写算法将A表和B表归并成一个按元素值递增 有序(即非递增有序,允许表中含有值相同的元素)排列的线性 表C,并要求利用原表(即A表和B表)的结点空间构造C表. 7 7 答案： 2.1a4-1;b7-11-8-4-1;c5-12;d9-16 2.2a11-3-14;b10-12-7-3-14;c12-11-3-14; d11-3-14 2.3(1)L-next=null置空链表,然后将原链表结点逐个插入到有 序表中 (2)p!=null当链表尚未到尾

6、，p为工作指针 (3)q!=null查p结点在链表中的插入位置，这时q是工作指 针。 (4)p-next=r-next将p结点链入链表中 (5)r-next=pr是q的前驱，u是下个待插入结点的指针。 8 8 2.4 StatusInsert_SqList(SqList va.length+; for(i=va.length-1;va.elemxi-) va.elemi+1=va.elem; va.elemi+1=x; returnOK; /Insert_SqList 9 9 2.5voidreverse_merge(LinkListpb=B-next;pre=NULL;/pa和pb分别指向A

7、,B的当 前元素 while(pa|pb) if(pa-datadata|!pb) pc=pa;q=pa-next;pa-next=pre;pa=q;/将A的元素插入新表 else pc=pb;q=pb-next;pb-next=pre;pb=q;/将B的元素插入新表 pre=pc; C=A;A-next=pc;/构造新表头 /reverse_merge 分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入 新表的头部pc处,最后处理A或B的剩余元素 1010 3.1 若按教科书3.1.1节中图3. 1(b)所示铁道进行车厢调度(注意:两侧铁道 均为单向行驶道).则请回答 (1)如果进

8、站的车厢序列为123,则可能得到的出站车厢序列是什么? (2)如果进站的车厢序列为123456.则能否得到435612和135426的出站序 列，并请说明为什么不能得到或者如何得到(即写出以s表示进栈和以 X，表示出栈的栈操作序列)。 3.2 若以1234作为双端队列的输人序列，试分别求出满足以下条件的输 出序 (1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到 的输出序列， (2)能由输出受限的双端队列得到，但不能由轴入受限的双端队列得到 的输出序列 (3)既不能由输入受限的双端队列得到，也不能由输出受限的双端队列 得到的输出序列 11 3.3假设以带头结点的循环链表表示队列，

9、并且只设一个指针指 向队尾元素结 点(注意不设头指针)，试编写相应的队列初始化、入队列和出 队列的算法。 3.4 12 3.5假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空， 入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的 序列为合法序列，否则称为非法序列 （1）下面所示的序列中哪些是合法的？ A. IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否 合法。若合法，返回true，否则返回false（假定被判定的操作序列已存 入一维数组中） 13 3.6 用一个数组S（设大小为MA

10、X）作为两个堆栈的共享空 间。请说明共享方法，栈满/栈空的判断条件，并用C或 PASCAL设计公用的入栈操作push（i，x），其中i为0或1 ，用于表示栈号，x为入栈值。 3.7 简述下列程序段的功能。 PROCalgo(VARS:stack;k:integer); VART:stack;temp:integer; WHILENOTempty(S)DO temp:=POP(S);IFtempkTHENPUSH(T,temp); WHILENOTempty(T)DO temp:=POP(T);PUSH(S,temp) 14 答案: 3.1(1) 123,132,213,231,321 (2)可

11、以得到135426，不可能得到435612,因为4356，出栈说明12已 在栈中，则1不可能在2之前出栈. 3.2 (1) 4132; (2) 4213; (3) 4231. 15 3.3 voidInitCiQueue(CiQueue Q-next=Q; /InitCiQueue voidEnCiQueue(CiQueue p-data=x; p-next=Q-next;/直接把p加在Q的后面 Q-next=p; Q=p;/修改尾指针 StatusDeCiQueue(CiQueue/队列已空 p=Q-next-next; x=p-data; Q-next-next=p-next; free(

12、p); returnOK; /DeCiQueue 16 3.4 StatusF_recursive(intn,int if(n=0)s=n+1; else F_recurve(n/2,r); s=n*r; returnOK; /F_recursive nStatusF_nonrecursive(intn,ints)/非递归算法 if(nj)printf(“序列非法n”)；exit(0); i+;/不论Ai是I或O，指针i均后移。 if(j!=k)printf(“序列非法n”)；return(false); elseprintf(“序列合法n”)；return(true); /算法结束。 算法讨

13、论在入栈出栈序列（即由I和O组成的字符串）的任一位置，入栈 次数（I的个数）都必须大于等于出栈次数（即O的个数），否则视作非 法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串 的结束标记0），入栈次数必须等于出栈次数（题目中要求栈的初态和终 态都为空），否则视为非法序列。 18 3.6两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶 相邻时为栈满。设共享数组为SMAX，则一个栈顶指针为-1，另一个栈顶 指针为MAX时，栈为空。 用C写的入栈操作push（i，x）如下： constMAX=共享栈可能达到的最大容量 typedefstructnode elemtypesM

14、AX； int top2； anode； anodeds; int push(int i,elemtypex) /ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享 其空间。i的值为0或1，x为类型为elemtype的元素。本算法将x压入 栈中。如压栈成功，返回1；否则，返回0。 if（ds.top1-ds.top0=1）printf（“栈满n”）；return（0）； switch（i） case0：ds.s+ds.topi=x；break； case1：ds.s-ds.topi=x； return（1）；/入栈成功。 19 3.7本程序段查找栈S中有无整数为k的元素，

15、如有，则删除。采用 的办法使用另一个栈T。在S栈元素退栈时，若退栈元素不是整 数k，则压入T栈。遇整数k，k不入T栈，然后将T栈元素全部退 栈，并依次压入栈S中，实现了在S中删除整数k的目的。若S中 无整数k，则在S退成空栈后，再将T栈元素退栈，并依次压入S 栈。直至T栈空。这后一种情况下S栈内容操作前后不变。 20 4.1下列程序判断字符串s是否对称，对称则返回1，否则返 回0；如f(abba)返回1，f(abab)返回0； intf(1)_) inti=0,j=0; while(sj)(2)_; for(j-;i=j 4.2xyxyxywwy 4.314；4；STUDENT；O；3；0；I

16、AMAWORKER； AGOODSTUDENT 2323 4.4 2424 4.5charStrCompare(Stringtypes,Stringtypet)/串的比较 ,st时返回正数,s=t时返回0,st时返回负数 for(i=1;i=s0 elseif(is0)return-ti; elseif(it0)returnsi; elsereturnsi-ti; /StrCompare 2525 5.1判断题 a. 数组不适合作为任何二叉树的存储结构。（ ） b. 从逻辑结构上看，n维数组的每个元素均属于n个向量。（ ） c. 数组是同类型值的集合。（ ） d. 数组可看成线性结构的一种推广

17、，因此与线性表一样，可以 对它进行插入，删除等操作。（ ） e. 二维以上的数组其实是一种特殊的广义表。（ ） f. 广义表的取表尾运算，其结果通常是个表，但有时也可是个 单元素值。（ ） g. 若一个广义表的表头为空表，则此广义表亦为空表。（ ） 2626 5.2 设有三对角矩阵 ,将其三条对角线上的元素逐行地存 于数组B3n-2中，使得Bk= ，求: (1)用 i , j表示k的下标变换公式; (2)用k表示 i, j的下标变换公式. 5.3 按教科书5.5节中图5.8所示结点结构，画出下列广义表的存 储结构图. (1)(),a, (b,c)，( )，d), (e) (2) (a), b)

18、,( ),d), (e, f) 5.4求下列广义表操作的结果 2727 (1) GetHead(p,h.w); (2) GetTeil(b,k.p,h); (3) GetHead(a,b),(c,d); (4) GetTeil(a,b),(c,d); (5) GetHeadGetTail(a,b),(c.d), (6) GetTailGetHead(a,b),(c,d); (7) GetHeadGetTailGetHead(a,b),(c.d); (8) GetTailGetHeadGetTail(a,b),(c,d). 注意: 是函数的符号。 5.5 广义表的结点结构如下:(TAG,DATA

19、,LINK)。其中LINK为指 向表 中下一元素的指针;TAG为标志域；DATA为数据域， 具体含义如下: TAG=0表示该结点为原子结点，DATA为其数 据；TAG=1表示该结点为一个子表，DATA为指向该子表的指 针。 （1）说明下列算法A的功能(注:算法中p,t,m,n,r,q为指针;算 法中的NIL对应图中的) 2828 PROCEDUREA(p,t) BEGIN q:=NIL; WHILEpNILDO BEGIN IFp.TAG0THEN BEGIN m:=p.DATA; A(m,n); p.DATA:=n; END; r:=p.LINK; p.LINK:=q; q:=p; p:=r

20、 END; t:=q; END. （2）对于 p所指的广义表,画出执行算法A后的表结构以及p，t的值: 2929 答案: 5.1a.错误。对于完全二叉树，用一维数组作存储结构是效率 高的（存储密度大）。 b.正确 c.错误。数组是具有相同性质的数据元素的集合，数据元素 不仅有值，还有下标。因此，可以说数祖是元素值和下标 构成的偶对的有穷集合。 d.错误。数组在维数和界偶确定后，其元素个数已经确定 ，不能进行插入和删除运算。 e.正确 f.错误。广义表的取表尾运算，是非空广义表除去表头元素 ，剩余元素组成的表，不可能是原子。 g.错误。广义表的表头就是广义表的第一个元素。只有非 空广义表才能取表

21、头。 3030 5.2 (1) k=2(i-1)+j-1, (l i-j |=1) (2) i=(k+1) / 3+1, (0=k=2) . (3)其第k-1个儿子的编号为 p*k.所以， 如果它有儿子. 则其第i个儿子的编号为 P*k+(i-(k-1); (4) (p-1)%k 0时，该结点 有右兄弟， 其右兄弟的编号为 p+1. 3838 6.7 A BH D C F E G K L J I 39 6.8哈夫曼编码方案的带权路径长度为2.61.而等长编码的路径长度 为3.显然前者可大大提高通信信道的利用率，提高报文发送速度 或/和节省存储空间.下面给出两种编码的对照表及哈夫曼树的逻 辑结构

22、. 40 7.1已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到 的序列为abecd，则采用的是_遍历方法。 7.2如下为拓扑排序的C程序， v（1）列出对右图执行该程序后的输出结果。 v（2）在程序空白处填上适当语句。 vvoidtopsort(hdnodesgraph,intn) vinti,j,k,top;node_pointerptr; vtop=-1; vfor(i=0;in;i+) vif(!graphi.count)graphi.count=top;top=i; vf

23、or(i=0;ilink) k=ptr-vertex;graphk.count-; if(3)_)graphk.count=top;top=k; V1 V2 V3 V4 V5 V6 41 7.3已知以二维数组表示的图的邻接矩阵如下图所示，试分别画 出自顶点1出发进行遍历所得的深度优先生成树和广度优先生 成树. 42 7.4请对图的无向带权图， (1)写出它的邻接矩阵，并按普里姆算法求其最小生成树; (2)写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树. 43 7.5试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路 径，写出执行算法过程中各步的状态。 44 7.6画出左图所示的无

24、向图的邻接多重表，使得其中每个无向边 结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边 的链接顺序，为它所邻接到的顶点序号由小到大的顺序。列出深 度优先和广度优先搜索谊历该图所得顶点序列和边的序列。 45 答案: v7.1深度优先 v v7.2（1）V1V4V3V6V2V5(尽管图以邻接表为存储结构，但因没规 定邻接点的排列，所以结果是不唯一的。本答案是按邻接点升序排列 给出的。) v（2）top=-1 vtop=graphj.count vgraphk.count=0 46 答案： 7.3 47 7.4 7.5 48 7.6 49 8.1 起始地址为480,大小为8的块,其伙伴块的起

25、始地址是_;若块 大小为32,则其伙伴块的起始地址为_。 8.2 二进制地址为011011110000，大小为（4）10和（16）10块的伙伴 地址分别为：_、_。 8.3 设内存中可利用空间已连成一个单链表，对用户的存储空间需求， 一般有哪三种分配策略？ 5050 8.4设两个大小分别为100和200的空闲块依次顺序链接成可利用空间 表。设分配一块时，该块的剩余部分在可利用空间表中保持原链接 状态，试分别给出满足下列条件的申请序列 (1)最佳适配策略能够满足全部申请而首次适配策略不能; (2)首次适配策略能够满足全部申请而最佳适配策略不能. 8.5考虑边界标志法的两种策略(最佳适配和首次适配

26、): (1)数据结构的主要区别是什么? (2)分配算法的主要区别是什么? (3)回收算法的主要区别是什么? 8.6已知一个大小为512字的内存，假设先后有6个用户提出大小分别 为23,45,52,100,11和19的分配请求，此后大小为45,52和11的占用 块顺序被释放.假设以伙伴系统实现动态存储管理， (1)画出可利用空间表的初始状态; (2)画出6个用户进入之后的链表状态以及每个用户所得存储块的起 始地址; (3)画出在回收三个用户释放的存储块之后的链表状态。 5151 答案: 8.1（1）480+8=488（480 %16=0 ） （2）480-32=448 8.2（1）0110111

27、10100 （2）011011100000 8.3首次拟合法；从链表头指针开始查找，找到第一个所需空间的 结点即分配。 最佳拟合法：链表结点大小增序排列，找到第一个所需空间的结点 即分配。 最差拟合法：链表结点大小逆序排列，总从第一个结点开始分配，将 分配后结点所剩空间插入到链表适当位置。 首次拟合法适合事先不知道请求分配和释放信息的情况,分配时需查询 ,释放时插在表头。 最佳拟合法适用于请求分配内存大小范围较宽的 系统,释放时容易产生存储量很小难以利用的内存碎片,同时保留那些 很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需 查询。 最差拟合法适合请求分配内存大小范围较窄的系统,

28、分配时不 查询,回收时查询,以便插入适当位置。 5252 8.4可以举出多种实例序列。如下为其中一例。 (1) 110,80,100 (2) 110.80.90,20 8.5(1)最佳适配策略下空闲块要按由小到大的顺序链接，可以不作成循 环表.空闲块表头指针恒指最小空困块。首次分配则力求使各种大小的 块在循环表中均匀分布，所以经常移动头指针; (2)无本质区别; (3)最佳适配策略下(合并后)插人链表时必须保持表的有序性. 5353 8.6 (1)只有一个大小为的 块； (2)有大小为 ， 和 的块各一块. (3)有大小为 和 的块各两块， 的块1块。 5454 9.1假设按下述递归方法进行顺

29、序表的查找:若表长=10,则进行顺序查 找，否则进行折半查找。试画出对表长n=50的顺序表进行上述查找 时，描述该查找的判定树，并求出在等概率情况下查找成功的平均 查找长度。 9.2顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最 多为_次；当使用监视哨时，若查找失败，则比较关键字的次 数为_。 9.3在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半 ）法查找关键码值20，需做的关键码比较次数为_. 9.4在有序表A1.12中，采用二分查找算法查等于A12的元素，所比 较的元素下标依次为_。 5555 9.5下列算法为斐波那契查找的算法: 5

30、656 9.6试从空树开始，画出按以下次序向2-3树即3阶B-树中 插入关链码的建树过程;20,30,50,52,60,68,70.如果此 后删除50和68，画出每一步执行后2-3树的状态. 5757 答案： 9.1 9.2nn+19.349.46,9,11,12 5858 9.5 5959 9.6 6060 10.1 10.2不难看出，对长度为，的记录序列进行快速排序时，所需进 行的比较次数依赖于这n个元素的初始排列。 (1)n=7时在最好情况下需进行多少次比较?请说明理由。 (2)对，=7给出一个最好情况的初始排列实例. 10.3 6161 10.4下面是冒泡排序算法，请阅读并完成该程序，

31、并回答以下问题： PROCEDUREbubblesort(r,n) BEGIN i:=1;m:=n-1;flag:=1; WHILE(irj+1.keyTHEN BEGINflag:=(4)_;t:=rj;rj:=rj+1;rj+1:=t END; i:=i+1;m:=m-1 END; END. （1）请在上面横线上填上适当的语句，完成该算法程序。 （2）设计标志flag的作用是什么？ （3）该算法结点的最大比较次数和最大移动次数是多少？ （4）该分类算法稳定吗？ 6262 答案： 10.1 10.2 10.3 6363 10.4 (1)横线内容:m101 (2)flag起标志作用。若未发生交

32、换，表明待排序列已有序，无 需进行下趟排序。 (3)最大比较次数n(n-1)/2，最大移动次数3n(n-1)/2 (4)稳定 6464 11.1假设某文件经内部排序得到100个初始归并段.试问: (1)若要使多路归并三趟完成排序，则应取归并的路数至少为多少? (2)假若操作系统耍求一个程序同时可用的输入、输出文件的总致不 超过13.则按多路归并至少需几趟可完成排序?如果限定这个趟数? 则可取的最低路数是多少? 11.2假设一次1/O的物理块大小为150，每次可对750个记录进行内部 排序，那么，对含有150000个记录的磁盘文件进行4-路平衡归并排 序时，需进行多少次I/O? 11.3“败者树”中的“败者指的是什么?若利用败者树求k个数中的最大值 ，在某次比较中得到ab，那么谁是败者?“败者树”与“堆”有何区别? 6565 答案： 6666