《中学信息学《数据结构》习题及参考答案.pdf》由会员分享，可在线阅读，更多相关《中学信息学《数据结构》习题及参考答案.pdf（178页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、云南财经大学信息学院 数据结构习题及参考答案 数据结构课程建设小组第 1 章绪 论基础知识题1.1 简述下列术语：数据、数据元素、数据对象、存储结构、数据类型、和抽象数据类型。1.2 试描述数据结构和抽象类型的概念与程序设计语言中数据类型概念的区别。1.3 设有数据结构(D,R),其中D=d 1 ,d 2,d 3,d 4 ,R=r ,r=(d 1 ,1 2),(d 2,d 3),(d 3,d 4)。试按图论中的画法惯例画出其逻辑结构图。1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子，分母均为自然数其分母不零的分数)。1.5 试画出与下列程序段等价的框图
2、(1)prod uc t：1 ;i=l;while(i=n)prod uc t *=i;i+；)(2)i=0 ;do i+while(i!=n)&(a i!=x);(3)swith case xy:z=y-x;break;case x=y:z=a b s(x*y);b re a k;d efu lt:z=(x-y)/a b s(x)*a b s(y);)1.6 在程序设计中，常用下列三种不同的出错处理方式：(1)用e x it语句终止执行并报告错误；(2)以函数的返回值区别正取返回或错误返回；(3)设置一个整型变量的函数参数以区别正取返回或错误返回；试讨论这三种方法各自的优点1.7 在程序设计
3、中，可采用下列三种方法实现输出和输入：(1)通 过scan f和p r in tf语句；(2)通过函数的参数显示传递；(3)通过全局变量隐式传递。试讨论这三种方法的优缺点。1.8 设n为正整数。试确定下列各程序段中前置以记号的语句的频度：(1)i =1;k=0;W hile(i=n-1)k+=1 0*I ;1+;)(2)i=l;k=O;do(i=n-1)k+=1 0*1;i+；while(I =n-1);(3)i =1；k=0;While(i=n-1)i+；k +=1 0*i;)(4)k=0;for(i =1 ;i=n;i+)for(j=i;j=n;j+)k+;)(5)for(i =1 ;i=
4、n;i+)for(j=i;j=n;j+)for(k=1 ;k=j;k+)x+=d e lt a;)(6)i=l;j=0;While(i+j j)j+;else i+;)(7)x=n;y=o;while(x=(y+l)*(y+1)y+;)(8)x=91;y=1 0 0;while(y 0)if(x 1 0 0)x-=1 0;y-else x+;)1.9 假 设n为2的乘骞，并且n 2,试求下列算法的时间复杂度及变量c ount的值(以的函数形式表示)。int T ime(int n)Count=0;x=2;While(x a r r s i z e 或对某个k(l W kW n)使 k!.2 k
5、 m a xi n t 时，应按出错处理，注意选择你认为较好的出错处理方法。1.2 0 试编写算法求一元多项式的值 的 值 P x o)并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本 题 的 输 入 为 a j (i=0,1,n)x0和 n,输 出 为 P n(xo)。第 2章 线 性 表基础知识题2.1 描述以下三个概念的区别，头指针，头结点，首元结点(第一个元素结点)。2.2 填空题。(1)在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素与 有关。(2)顺 序 表 中 逻 辑 上 相 邻 的 元 素 的 物 理 位 置 紧邻。单
6、链表中逻辑的元素物理位置 紧邻。(3)在单链表中，除了首元结点外，任一结点的存储位置由 _ _ _ _ _ _ _ _ _ _ _ _ 揖示。(4)在单链表中设置头结点的作用是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _-o2.3 在什么情况下用顺序表比链表好？一2.4 对 以 卜单链表分别执行卜列各程序段，并画出结果意图。(1)Q=P-next;(2)L=P-next;(3)R-data=R-data;(4)R-data=P-next-data;(5)P-next-next-next-data=P-data;(6)T=P;While(T!=NULL)T-data
7、=T-data*2;T=T-next;(7)T=Pwhile(T-next!=NULL)T-data=T-data*2;T=T-next;2.5 画出执行下列各行语句后各指针及链表的示意图。L=(LinKList)malloc(sizeof(L Node);P=L;for(i=l;inext=(LinKList)malloc(sizeof(LNode);P=P-next;P-data=i*2-1;)P-next=NULL;for(i=4;i=4;i-;)Ins_LinkList(L,i+1 ,i*2);for(i=l；Inext=S;(2)P-next=P-next-next;(3)P-nex
8、t=S-next;(4)S-next=P-next;(5)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;(H)P=L;(12)L=S(13)L=P;2.7 已知L 是带头结点的非空单链表，且 P 结点既不是首结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列是a.删除P 结点的直接后继结点的语句序列是b.删除P 结点的直接后继结点的语句序列是c.删除P 结点的语句序列是 _ _ _ _ _ _ _ _ _ _ _ _d.删除首元结点的语
9、句序列回 一e.删除尾元结点的语句序列是-.(1)P=P-mext;(2)P-next=P;(3)P-next=P;(4)S-next=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;(1 l)Q=P-next;(12)P=L;(13)L=L-next;(14)free(Q);2.8 已知P
10、结点是某双向链表的中间结点，试从下列提供的答案中选择合适的合适语序序列。a.在 P 结点后插入S 结点的语句序列是-b.在 P 结点前插入S 结点的语句序列是-c.删除P 结点的直接后继结点的语句序列是d.删除P 结点的直接前驱结点的语句序列是e.删除P 结点的语句序列是 _ _ _ _ _ _ _ _ _ _ _ _(1)P-next=P-next-next;(2)P-priou=P-priou-priou;(3)P-next=S;(4)P-priou=S;(5)S-next=P;(6)S-priou=P;(7)S-next=P-next;(8)S-priou=P-priou;(9)P-pr
11、iou-next=P-next;(10)P-priou-next=P;(1 l)P-next-priou=P;(12)P-priou-next=S;(13)P-priou-next=S;(14)P-next-priou=P-priou;(15)Q=P-next;(16)Q=P-priou;(17)Free(p);(18)Free(Q);2.9 简述以下算法的功能。(1)Status A(Linked List L)/L是无表头结点的单链表If(L&L-next)Q=L;L=L-next;P=L;While(P-next)P=P-next;P-next=Q;Q-next=NULL;)return
12、 OK;/A(2)Void BB(Lnode*s,Lodes*q)p=s；while(p-next!=q)q=p-next;p-next=s;/BBvoid AA(Lnode*pa,Lnode*pb)/p a和 pb分别是指向单循环链表的类型定义如下：BB(pa,pb);BB(pb,pa);/AA算法设计题本章算法设计题涉及的顺序表和线性表的类型定义如下：#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct LnodeElem Type data;typedef struct Elem Type*elem;存储空间基址
13、intlength;当前长度intlistsize;当前分配的存储容量 SqList;/顺序表类型Struct Lnode*next;Lnode,*LinkList;线性链表类型2.10 指出以下算法中的错误和低效(既费时D 之处，并将它改写成一个既正确又高效的算法。Status DeleteK(SqList&a,inti,int k)本过程从顺序存储结构的线性表中a 中删除第i 个元素起的k 个元素if(i,lllka.length)return INFEASIBLE 参数不合法else for(count=l;count=i+1 ;j-)a.elemfj-l=a.elemfj;a.leng
14、th;)return OK;/DeleteK2.22 设顺序表中的数据元素递增有序。试写一算法，将插入到顺序表的适当位置上，以保持该表的有序性。2.12 设A=(a,.a)B=(b，,b”)均为顺序表，A 和 B，分别为A 和 B 中同前缀为(x,y,y,z),在两表中除最大共同前缀后的子表分别为A，=(x,z)和B，=(y,x,x,z)若 A，=B，=空表，贝 ljA=B；若 A，=空表，而 夕 中空表，或者两者均不为空表，且 A，的首元小于B，的首元，则 A B o 试写一个比较A,B 大小的算法(请注意：在算法中，不要破坏原表A 与 B,并且也不一定先求得A，和 B，才进行比较)2.13
15、 试写一算法在带头结点的单链表结构上的实现线性表操作LOCATE(L,X)。2.14 试写一算法在带头结点的单链表结构上的实现线性表操作LENGTH(L)2.15 已知指针h a 和 h b 分别指向两个单链表的头结点，并且已知两个链表的长度分别为m 和 n试写一算法将这两个链表连接在 起(即令其中 个表的首元结点连在另 个表的最后一个结点之后)，假设指针he指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。2.16 已知指针la和 1b分别指向两个无头结点单链表的首元结点。下列算法是从表 la 中删除自第i 个元素起共len个元素后，将它们插入到表
16、1b中第i 个元素之前，试问此算法是否正确？若有错，则请改正之。Status Dlete AndInsertSub(Linked la,LinkedList lb,int i,int j,int len(If(i 0llj0lllen0)return INFEASIBLE;p=la;k=l;while(knext;k+;q=p；while(knext;k+;s=lb;k=l;while(knext;k+;s-next=p;q-next=s-next;return OK;/Delete AndlnsertSub2.1 7 试写一算法，在无头结点的动态单链表上实现线性表操作I N S E R T
17、（L,i,b）,并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.1 8 同2.1 7题要求，试写一算法，实现线性表操作D E L E T E （L,i）。2.1 9 已知线性表中的元素以值递增有序排列，并以单链表作存储结构，试写出高效算法，删除表中所有值大于m i n k且小于m a x k的元素，（若表中存在这样的元素）同时释放被删除结点空间，并分析你的算法的时间复杂度（注意：m i n k和m a x k是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）2.2 0 同2.1 9题条件，试写出高效算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不
18、相同），同时释放被删除结点空间，并分析你的算法的时间复杂度。2.2 1 试写一算法，实现顺序表的就地逆置，即利用原表中的存储空间将线性表（a.,.an）逆 置 为（an,2.2 2 是写一算法，对单链表实现就地逆置。2.2 3 设线性表A=（a.,B=（b.b,）,试写一个按下列规则合并A,B为线性表C的算法，即使得C=（a,b i.am.b m ,bm+i.b n）当 m）当 mn 时。线性表A,B,C均以单链表作存储结构，且C表利用A表 利B表中的结点空间构成，注意：单链表的长度值m和n均未显示存储。2.2 4 假设有两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构，请编写算
19、法将A表 和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C,并要求利用原表（即A表 和B表）的结点空间构造C表。2.2 5 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同,表中的元素各不相同），现要求另辟空间构成个线性表C,其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列，试对顺序表编写求C的算法。2.2 6 对2.2 5题。试对单链表编写求C的算法2.2 7 对2.2 5题的条件作以下两点修改，对顺序表重新编写求得C的算法。（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；（2）利
20、用A表空间存放表C。2.2 8 对2.2 5题的条件作以下两点修改，对顺序表重新编写求得C的算法。（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；（2）利用原表（A表或B表）中的结点构造C,并释放A表中的无用节点空间。2.2 9 已知A,B和C为三个递增有序的线性表C,现要求对A表中作如下操作：删除那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作算法，并分析你的算法的时间复杂度，（注意；题中没有特别指明同一表中的元素各不相同）。2.3 0 要求同2.2 9题，试对单链表编写算法，请释放A表中的无用结点空间。2.3 1 假设某个单向循环
21、链表的长度大于1,且表中即无头结点也无头指针。已 知s为指向链表中的某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱节点。2.3 2 已知有个单向循环链表，其每一个结点中含三个域：p r e,d a t a和n ex t,其中d a t a为数据域，n ex t为指向后继结点的指针域，p r e也为指针域，但它的值为空（N U L L）,试编写算法将此单向循环链表双向循环链表，即使p r e成为指向前驱结点的指针域。2.3 3 已知由一个线性链表表示的线性表中含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线
22、性表中均只含一类字符。在2.3 4至2.2 6题中，“异或指针双向链表”类型X o r L i n k ed L i s t和指针异域函数X o r P定义为：t y p ed ef s t r u c t X o r N o d ec h a r d a t a;s t r u c t X o r N o d e L R P t r;X o r N o d e,*X o r P i n t er;t y p ed ef s t r u c t 无头结点的异或指针双向链表X o r P o i n t er L ef t,R i g ht;/分别指向链表的左端和右端J X o r P o in
23、 t e d L is t;X o r P o in t e r X o r P(X o r P o in t e r p,X o r P in t e r q);指针异域函数X o r P返回指针p和q的 异 或(XOR)值2.3 4 假设在算法描述语言中引入指针的二元运算“异或”(用 表 示)，若a和b为指针，则的运算结果仍为原指针类型，利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域:d a t a域和L R P t r域,其中L R P t r域存放该结点的左邻与右邻节点指针(不存在时为NULL)的异域。若设指针L。L e f t指向链表中的最左结点，L.R ight指向链
24、表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。2.3 5 采用2.3 4题所述的存储结构，写 出 在 第i个结点之前插入一个结点的算法。2.3 6 采用2.3 4题所述的存储结构，写出删除在第i个结点的算法。2.3 7 设以带头结点的双向循环链表表示的线性表L=(a,试写一时间复杂度为O(n)的 算 法,将L改造为L=(a,a s a n.a&,a 2)。2.3 8 设有一个双向循环链表，每个结点除有p r e,d a t a和n e x t三个域外，还增设了一个访问频度域f r e q。在链表被起用之前，频度域f r e p的值
25、均为初始化为零，而每当对链表进行一次LOCA TE(L,x)的操作后，被访问的结点(即元素值等于x的结点)中的频度域f r e p的值便增1,同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCA TE操作的算法。在2.3 9至2.4 0题中，稀疏多项式采用的顺序存储结构S q P o l y定义为t y p e d e f s t r u c t in t c o e f;in t e x p P o l y T e r m;t y p e d e f s t r u c t P o l y T e r m
26、 *d a t a;in t l a s t;S q P o l y;2.3 9 已知稀疏多项式 P n(X)=C ix +.+C 2 x e m 其中 n=em em.i.e(=0,C j#0(i=l,2,.m),ml。试采用存储同多项式数m成正比的顺序存储结构，编写求P。(x0)的 算 法(X。为给定值)，并分析你的算法的时间复杂度。2.4 0 采用2.3 9题给定的条件和存储结构，编写求P (x)=P,(x)-Pn 2(x)的 算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。在2.41至2.42题中，稀疏多项式采用的循环链表存储结构LinkedPoly定义为typede
27、f struct PolyNodePoly Term data;Struct PolyNode*next;Poly Node,*PolyLink;typedef Poly link LinkedPoly;2.41 试以循环链表作为稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。2.42 试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使两个多项式中各自仅含有奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表第三章栈和队列基础知识题3 若 教 科 书3.1.1节中图3.1(b)所示铁道进行车厢调度
28、(注意：两侧铁道均为单向行驶道)，则请回答：(1)如果进站的车厢序列为123。则可能得到的出站车厢序列是什么？(2)如果进站的车厢序列为123456,则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到(即写出以 S 表示进栈和以 X 表示出栈的栈操作序列)。3.2 简述栈和线性表的差别。3.3 写 出 卜 列程序段的输出结果(栈的元素类型SelemType为char)。Void main()Stack S;Char x,y;InitStack(S);x=,c,;y=k;Push(S,x);Push(S,a);Push(S,y);Pop(S,x);Push(S/f
29、);Push(S,x);Pop(S,x);Push(S,s);While(!StackEmpty(S)Pop(S,y);printf(y);Print(x);)3.4 简述以卜算法的功能(栈的元素类型SelemType为int)。(1)status algol(Stack S)int i,n,A256;n=0;while(!StackEmpty(S)n+;Pop(S,An);for(i=l;i=n:i+)Push(S,Ai);)(2)status algo2(Stack S,int e)Stack T;int d;InitStack(T);While(!StackEmpty(S)Pop(S,d
30、);if(d!=e)Push(T,d);)while(!StackEmpty(T)Pop(T,d);Push(S,d);)3.5假设以S和X分别表示入栈和出栈的操作，则初态和终态均为栈空的入栈和出栈的操作序列可以表示为仅由S和X组成的序列，称可以操作的序列为合法序列(例如,SXSX为合法序列，SXSX为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法(栈操作)序列(对同输入序列)不可能得到相同的输出元素(注意：在此指的是元素实体，而不是值)序列。3.6 试证明：若借助栈由输入序列12.n 得到的输出序列为P 1 p2 p3 pn(它是输入序列的一个排列)，则
31、在输出序列中不可能出现这样的情形:存在着ijk使 用 pk1)printf(i);)3.10 试将下列递归过程改写为非递归过程。Void test(int&sum)int x;scanf(x);if(x=0)sum=0;else test(sum);sum+=x;printf(sum);)3.11 简述队列和栈这两种数据类型的相同点和差异处。3.12 写出以下程序段的输出结果(队列中的元素类型QelemType为 char)。Void main()Queue Q;InitQueue(Q);Char x=,e,y=,c,;EnQueue(Q,h,);EnQueue(Q,r,);EnQueue(Q
32、,y);DeQueue(Q,h);EnQueue(Q,x)；DeQueue(Q,h,);EnQueue(Q/a,);While(!QueueEmpty(Q)DeQueue(Q,y);Printf(y);)printf(x);)3.13 简述以下算法的功能(栈和队列的元素类型均为int)。void algo 3(Queue&Q)Stack S;int d;While(!QueueEmpty(s)DeQueue(Q,d);Push(S,d);w h i l e (!S t a c k E m p t y(s)P op(S,d);E n Q u e u e(Q,d);)3.14若 以1 2 3 4作
33、为双端队列的输入序列，试分别求出满足以下条件的输出序歹I；(1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；(2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；(3)既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列；算法设计3.1 5 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈t w s的三个操作：初始化 in is t a c k (t w s)、入栈 p u s h(t w s,i,s)和出栈 p op (t w s,i)的算法,其中
34、 i 为 0 或 1。用以分别指示设在数组的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么优缺点。3.1 6 假使如题3.1所述火车调度站的入口处有n节硬席或软席车厢(分别以H和S表示)等待调度，输入对这n节车厢进行调度的操作(即入栈或出栈操作)序列，以使所有的软席车厢都被调整到硬席车厢之前。3.1 7 试写一个算法，识别依次读入的一个以 为结束符的字符序列是否为形如 序列1&序歹I2模式的字符序列。其中序列1和序列2中不包含字符，&，且序歹I J 2是序列1的逆序列。例如，a+b&b+a 是属于该模式的字符序列，而 1+2&2-1 则不是。3.1 8 试写出一
35、个判别表达式中开、闭括号是否配对出现的算法。3.1 9 假设一个算术表达式中可以包含三种符号；圆括号“(”和“)”、方括号和“”和花括号“”和 且 这 三 种 括 号 可 按 任 意 的 次 序 嵌 套 使 用(in：.)o编写判别给定表达式所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。3.2 0 假 设 以 二 维 数 组 为 表 示 一 个 图 象 区 域,g i,j表示该区域中点(i,j)所具有颜色，其值为从0到k的整数.编写算法置换点(i jo)所在区域的颜色，约 定 和(i(J o)同色的上、下、左、右的邻结点为同色区域的点。3.2 1 假设表达式由单字
36、母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。3.2 2 如题3.2 1的假设条件，试编写一算法，对逆波兰式表示的表达式求值。3.2 3 如题3.2 1试写一算法。判断给定的非空后缀表达式是否为正确的逆波兰式(即后缀表达式)，如果是，则将它转化为波兰式(既前缀表达式)。3.2 4 试编写如下定义的递归函数的递归算法，并根据算法画出求g(5,2)时栈的变化过程。MO m=0,n=()3.2 5 试写出递归函数F (u)的递归算法，并消除递归:3.2 6 求解平方根的迭代函数定义如下；其中，P 是 A的近似平方根，e是结果误差，试写出相应的递归函数
37、算法，并消除递归。3.2 7 已知A c ke n n a n 函数定义如下：（I）写出递归算法；（2）写出非递归算法，（3）根据非递归算法，画出求a km （2,1）时栈的变化过程。3.2 8 假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。3.2 9 如果希望循环队列中的元素都能得到利用，则需要设置一个标志域ta g,并以 ta g的值为0或 1 来区分，尾指针和头指针相同时的队列状态是“空”还 是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（
38、如当循环队列较小而队列中每个元素占的空间较多时，哪一种方法较好）。3.3 0 假设将循环队列定义为：以域变量r e a r 和 l e n gth分别指示循环队列中对尾元素的位置和内含元素的个数，试给出此循环队列的对满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回对头元素）。3.3 1 假设称正读和反读都相同的字符序列为“回文”，例如，a b b a 和 a b c b a 是回文，b c d e 和 a b a b a 则不是回文，试 写 一 个 算 法 判 别 读 入 的 一 个 以 为 结 束 符的字符序列是否是“回文”。3.3 2 试利用循环队列编写求k 阶斐波那契序列
39、中前n+1 项，（f 0 ,f1,.fn）的算法，要求满足:f n W m a x 而 f e m a x,其中m a x 为某个约定的常数。（注意：本题所用循环队列的容量仅为k,则在算法执行结束时，留在循环队列中的元素应是所求k 阶斐波那契序列中的最后k 项f n-k+l，.f n）o3.3 3 在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每一个原始表示一个待处理表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作亚优先原则，若一个新提交的作业的预计执行时间小于对头和对尾作业的平均时间，则插入在对头，否则插入在对尾。3.3 4 假设在教科书
40、3.4.1 节中图3.9 所示，铁道转轨网的输入端有n节车厢：硬座、硬卧、和 软 卧（分别以P,H和 S表示）等待调度，要求这三种车厢在输出端铁道上的排队次序为：硬 座 在 前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符 E 和 D 表示对双端队列的头端进行入队列和出队列的操作；以字符A 表示对双端队列的尾端进行入队列的操作。第4章 串基础知识题4.1 简述空串和空格串4.2 对于教科书4.1 节所述串的各个基本操作，讨论是否可由其他基本操作构造而得？如何构造？4.3 设$=*1 AM A STUDENT,t=GOOD,q=,WOR
41、KER,.求：StrLength(s),StrLength(t),SubString(s,8,7),SubString。,2)，Index。,A),Index(s,I),Replace(s,STUDENT,q),Concat(SubString(s,6,2),Concat(t,SubString(s,7,8).4.4 已知下列字符串a=THIS,f=A SAMPLE,c=GOOD,d=NE,b=，s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2),t=Replac(f,SubString(f,3,6),c),u=Concat
42、(SubString(c,3 1 ),d),g=,IS,v=Concat(s,Concat(b,Concat(t,Concat(b,u),试问：s,t,v,StrLenglh(s),Index(v,g),Index(u,g)各是什么?4.5 试问执行以下函数会产生怎样的输出结果？Void demonstrate()StrAssignCs/THIS IS A BOOK);Replace(s,SubString(s,3,7),),ESE ARE);StrAssign(t,Concat(s,S);StrAssign(u；XYXYXYXYXYXY,);StrAssign(v,SubSting(u,6,
43、3)；StrAssign(w,W,);Printf(4t=,t,v=,v/u=,Replace(u,v,w,);/demonstrate4.6 已知；5=丫+*：=，(*+2)*丫八试利用|联接、求子串和置换等基本运算，将 s转化为to4.7 令=aaab,t=abcabaa,u=abcaabbabcabaacbacba.。试分别求出它们的 next函数值和nextrval函数值。4.8 已知主串 s=ABADABBAABADABBADADA,模式串 pa仁 ADABBADADA,写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程4.9 在以链表存储串值时，存储密度是结点大小和
44、串长的函数假设每个字符占一个字节，每个指针占4 个字节，每个结点的大小为4 的整数倍。已知串长的分布函数为f(1)且，求结点大小为4 k,串长为1时的存储密度d(4k,D(用公式表示)。算法设计题在编写4.10至 4.14题的算法时，请采用StringType数据类型；StringType是串的一个抽象数据类型，它包含以下五种基本操作：Void Str Assign(StringType&t,StringType s)将s 的值赋给t。s 的实际参数可以是串变量或者串常量(如abed)。ini SlringCompare(StringType s,StringType t)比较S和 t。若 s
45、t,返回值 0,若$=匕返回值=0；若 s e t,返回值 0。int StrLength(StringType s)返回s 中的元素个数，即该串的长度。StringType Concat(StringType s,StringType t)返回由s 和 t 联接而成的新串StringType SubString(StringType s,int start,int len)当 lWstart StrLength(s)且 0nin1!e);(2 L2=(j(oruiigc);(5)L5=(1applc)M(fx:ar.txinaiia)joningc):(6)L6=(Ucar),lxinaii
46、a)j()ninge;(7 L7=(applej pearl banana)rangc);5.12 按教舁3 5.65节中IB 5.8所示结点结构廊出下列广义我的存储结构周,并求它的深度.1)().aj(b.cH)4d)X(c)2)(&)*b)(d).(u.f)5.13-3 已如以卜各图为义我的存传站构留，其靖点结构和5.12 相 图我示的广义表.(1)PB-I n FF1(2)5J4 巳如等差数列的第 项为 a l,公 2 为 d.试写 故列前的 和 S分0)的递灯定义.5J5写出求给证集合的好处的递打定义.5 8 3 试利用C 语；中的增量运年“+”和双运 算“一一”山阳个率负簸数a 和
47、b相加的递归定义.5 7已知哌序表L 含有n 个1 8 1 t 试分别以函数形式.，川 I 卜列运。的递归算法：1)求我中的最大景致：2)求我中的最小径效：3)求我中的n 个候效之和：4)求我中的R个候数之枳,12.0为I时.Q的值或F,和为的值可雷略不印.5.2）3催设稀疏矩阵A和B一一三元敷组岫序.示作为存”构.试写出矩牌相加1算法.兄设三元组衣C存放结聚矩阵.5.22 假 设 东 数 斑/A和B均以三元数组岫序代示作为存储结构.试写出清足以F条件的矩阵相加的算法，假收三元组顺序及A的空间足够J、,将中阵B加到处0 A I.不用加A.B之外的附加空间.你的算法使古达到O（1+的时fB JK
48、杂度？为中mM 分别为A,B矩阵中非零的数目.5.23：2 1绡 版 序 表 的种变型是.从，.卜 打 ，到：出；我,另设 个行起始向h i.其施个分n是二元数组购序衣的个卜标位.指示该行中第 个二岁无需亦：元组就序表中的起始位置，皮 漏 写个算法.由矩阵元京的卜,标慎可 求知阵元宙，试讨论这种方法和1元顺序衣相比有什么优献点.524三元二顺序我的另 椁变型足，不存矩阵元东的可,列F标,再存在非零元在建阵中取行力!中时才I列的事序号，WffiLOC （0.0）=1.1=1.时按教科书案g节，I（5-2）计 笄 出 的 值.试 写算法,由矩阵元#的下标值,i,j.求元求的例.5.25：，.由格稀
49、如 的#零元东U行为I1,的“!字”广 推数IH V中.Ji川：堆数州B&小A中的相应兀京是否为零元素（以。和I分别衣示零元泰和季零元素）.例如nfffl V=(15.22.-6.9)和I 0B=0 II 00 10 0 次示0 0试痂写 算法,实现上述衣示法中实现矩阵相加的运和.并分析你的算法时间杂度.5.26 试编。个以三元组形式,出用卜字旌衣衣示的稀疏如冏中卜 元本及族F标的算法.5.27 试按教科书5J.2节中定义的十字燧衣存储我示编写将幅/矩阵B加到枯成如阵A上的算法.5.28 诚按教科书5 3 2节中给出的m元多项式的表示力法.写 f求m元多项式中第变元的偏导数的算法.529采用软
50、舁书5.6节中给出的n元多项式的果示力法，写 个 求n元多项式楸加算法.530 以 卜 我 尾.的 分 析 力 法犷，文我的深度的递归。.SJ1山试按教舁书5 5节510标示结点结构蛤写复制广义友的通VI算法5.32 试修写判g个广义费是否相%的递归算法533试漏考递UI算法.输出广义我所行原广项及我所在的层次.5.3L U试蛤写递归笄法.逆转广义我中的故组元.例如：格广义表a.(b.c).(),(d),e).f)逆转为，(f.c.(d).(),(c.b).a).535假设广义我按如卜”符串赛示.(ai ai.&)0共中&或为生字母衣示的原产,或为广义我：=0时.为只含有空格符的至衣().试按