2022年数据结构习题 .pdf

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

1、学习必备欢迎下载第一章绪论一、填空题1 数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_ 是数据的基本单位； _ 是数据的最小单位。 通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为_ 。2 数据结构进行形式化定义时， 可以从逻辑上认为数据结构DS 是_ 的集合 D 和 D 上_ 的集合 R 所构成的二元组： DS=（D，R） 。3 已知某数据结构的二元组形式表示为：A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r ，r=，。则此数据结构属于 _ 结构。4 一个算法的时间复杂度

2、通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时， 则表示为 _ ； 成正比关系时，则表示为_ ； 成对数关系时，则表示为 _ ；成平方关系时，则表示为 _ 。5 数据结构的逻辑结构包括 _ 、树型结构和图型结构三种类型，其中树型结构和图型结构合称为_ ；数据结构的存储结构主要包括 _ 和_ 两种类型。6 线性结构的特点是： 第一个结点 _ 前驱结点，其余结点有且仅有 _ 个前驱结点；最后一个结点_ 后继结点，其余每个结点有且仅有_ 个后继结点。7 树型结构的特点是：根结点没有_ 结点，其余每个结点有且仅有_个前驱结点；叶子结点_ 后继结点，其余结点可以有 _ 个后

3、继结点。8 图型结构的特点是：每个结点可以有_ 个前驱结点和后继结点。9 程序段 for（i=1，s=0；sn；i+） s=s+i；的时间复杂度为 _ 。10 常见的时间复杂度有常数阶O(1)、对数阶 O(log2n)、线性阶 O(n)、平方阶 O(n2)、线性对数阶 O(nlog2n)、立方阶 O(n3)、指数阶 O(2n)等等，这些数量阶之间的大小关系为_ 。二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。1.A=（K，R） ，其中：K=a，b，c，d，e，f，g，h，R=r ，r=，。2.B=（K，R） ，其中：K=a，b，c，d，e，f，g，h，R=r ，r

4、=，。3.C=（K，R） ，其中：K= a，b，c，d，e ，R=r ，r=，。4.D=（K，R） ，其中： K=48 ，25，64，57，82，36，75，R=r1，r2，r1=，；r2=，。5.E=（K，R） ，其中： K=1，2，3，4，5，6，7 ，R=r ，r=，。三、指出下列各函数的功能并求出其时间复杂度。1.void prime(int n) int i; for(i=2;isqrt(n) printf(“ yes ” ); else printf(“ no” ); 2.long sum1(int n) 精选学习资料 - - - - - - - - - 名师归纳总结 - - -

5、- - - -第 1 页，共 33 页学习必备欢迎下载long sum,w,i; for(sum=0,i=1;i=n;i+) w=1; for(j=1;j=i;j+) w=wi; sum=sum+w; return(sum); 3.long sum2(int n) long sum,w,i; for(sum=0, w=1,i=1;i=n;i+) w=wi; sum=sum+w; return(sum); 4.void sort(int r ,int n) int i,j; for(i=1; in;i+) for(j=0;jrj+1) temp=rj;rj=rj+1;rj+1=temp; 补充：

6、0.分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是_ 0. N2 _。for (i=0;in;i+) for (j=0;jn; j+) Aij=0; 1 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是 _ N3 _。s=0; for (i=0;in;i+) for (j=0;jn;j+) for (k=0;kn;k+) s=s+Bijk; sum=s; 2 分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是 _根号 N _。i=s=0; while (sn) i+; s+=i; /s=s+i 3。 分析下面算法（程序段）给出最大语句频度，该算法的时

7、间复杂度是 _ log(N)_。i=1; while (i=n) i=i*2; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 33 页学习必备欢迎下载第一章参考答案一、填空题1 数据元素，数据项，结构2 数据，关系3 树型4 O(1)，O(n)，O(log2n)，O(n2) 5 线性结构，非线性结构，顺序结构，链式结构6 无，一，无，一7 前驱，一，无，任意8 任意9 O(n1/2) 分析：设程序段中的循环体执行k 次，则有不等式111kikiini成立，解此不等式得到不等式2/14/122/34/12nkn，因此)()(nOknf。

8、10 O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n) 二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。1 线性结构2 树型结构3 图型结构4 图型结构分析：数据结构 D 中的关系集合 R 有两个关系 r1和 r2。如果只考虑关系 r1，则为线性结构； 如果只考虑关系 r2，则为树型结构；如果把关系r1和 r2联合起来考虑，则为图型结构。5 图型结构分析：若用图形来表示则可以看出r 是 E 上的对称关系，为了简化起见，我们通常把和这两个有序偶对用一个无序偶对 (x，y)或(y，x)来代替。在用图形表示时， 我们把 x 结点和 y 结点

9、之间两条相反的弧用一条无向边来代替。三、指出下列各函数的功能并求出其时间复杂度。1 函数的功能是判断 n是否是一个素数，其时间复杂度为O(n1/2)。分析：函数 prime 中出现的库函数 sqrt为平方根函数，因此)(1)(nOnnf。2 函数的计算nii1!的值，其时间复杂度为O(n2)。3 函数的计算nii1!的值，其时间复杂度为O(n)。4 函数的功能是对数组r 中的 n 个元素进行冒泡排序，其时间复杂度为O(n2)。分析：)(2/ )1()()(211nOnninnfni。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 33

10、页学习必备欢迎下载第二章线性表一、填空题1 设长度为 n 的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动_ 个元素，删除一个元素时平均需要移动_ 个元素。2 在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要_ 移动一个位置。3 在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要_ 移动一个位置。4 线性表的链式存储结构中，元素之间的线性关系是通过结点中的_ 来实现的。5 线性表的顺序存储结构中逻辑上相邻的元素，物理位置 _ 相邻；线性表的链式存储结构中逻辑上相邻的元素，物理位置 _ 相邻。6 已知单链表的长度为 n，则在给定值为 x 的结点

11、后插入一个新结点的时间复杂度为_ 。7 已知单链表的长度为 n，则删除给定值为 x 的结点的时间复杂度为 _ 。8 在单链表中设置头结点的作用是 _。9 双向链表中每个结点含有两个指针域，其中一个指针域指向 _结点，另一个指针域指向 _ 结点。10 在长度为 n 的线性表中顺序查找某个结点值为X 的时间复杂度为 _ 。二、选择题1在长度为 n 的顺序线性表中删除第i 个元素(1=inext=p p=p-next p=p-next-next p-next=p-next-next 4设指针 q 指向单链表中结点 A，指针 p 指向单链表中结点 A 的后继结点 B，指针 s 指向被插入的结点 X，则

12、在结点 A 和结点 B 之间插入结点 X 的操作为（） 。 s-next=p-next； p-next=s； q-next=s ； s-next=p； p-next=s-next； s-next=p； p-next=s ； s-next=q；5在长度为 n 的顺序线性表中的第i 个元素(1=irlink=s； s-llink=p； p-rlink-llink=s； s-rlink=p-rlink； s-llink=p； s-rlink=p-rlink； p-rlink=s； p-rlink-llink=s； p-rlink=s； p-rlink-llink=s； s-llink=p； s-rl

13、ink-p-rlink； s-llink=p； s-rlink=p-rlink； p-rlink-llink=s； p-rlink=s；8指针 p指向双向链表中的结点A，则删除结点 A 的操作是（） 。 p-llink-rlink=p-rlink ； p-rlink-llink=p-llink ； p-rlink-llink=p-rlink ； p-llink-llink=p-llink ； p-llink-rlink=p-llink ； p-rlink-llink=p-rlink ； p-rlink-rlink=p-rlink ； p-rlink-rlink=p-rlink ；9线性表采用链

14、式存储结构时，要求存储单元的地址（） 。 必须是连续的 部分地址必须是连续的 一定是不连续的 连续不连续都可以10设 head为单链表的头指针，则不带头结点的单链表为空的判定条件是（） 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 33 页学习必备欢迎下载 head=NULL head-next=NULL head-next=head head!=NULL 11设 head为单链表的头指针，则带头结点的单链表为空的判定条件是（） 。 head=NULL head-next=NULL head-next=head head!=NULL

15、 12设 head和 tail 分别为单向循环链表的头指针和尾指针，则下列等式成立的是（） 。 head=tail head-next=tail tail-next=head head-next=tail-next 三、算法设计题顺序存储结构的类型定义： typedef struct int am; int n; sqlist; 链式存储结构的类型定义： typedef struct node int data; struct node *next; lklist; 1.建立一个有 n 个结点的单链表，要求从尾部进行插入。2.建立一个有 n 个结点的单链表，要求从头部进行插入。3.用顺序存储结

16、构实现线性表就地逆置算法，即在原表的存储空间内将线性表 （a1，a2，an）逆置为(an，an-1， a1)。4.用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表 （a1，a2，an）逆置为(an，an-1， a1)。5.已知集合 A、B，求集合 C=AB 算法，要求集合 A、B 和 C 均用采用顺序存储结构表示。6.已知集合 A、B，求集合 C=AB 算法，要求集合 A、B 和 C 均用采用链式存储结构表示。7.设计在带有头结点的单向链表中删除值为X 的结点算法。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 33

17、页学习必备欢迎下载第二章参考答案一、填空题1 n/2，(n-1)/2 分析： 当在顺序线性表中的第i（1=i=n+1）个位置之前插入一个新元素时， 从第 i 个元素起向后的 n+1-i个 元 素 均 要 向 后 移 动 一 个 位 置 。 因 此 在 等 概 率 情 况 下 ， 插 入 操 作 中 元 素 的 平 均 移 动 次 数 为112)1(11)(nininnnf；当在顺序线性表中删除第i（1=ileft）和指向后继结点的指针 （p-right） ，然后再分别表示出前驱结点中的右指针域 （p-left-right）和后继结点的左指针域 （p-right-left） ，最后分别修改前驱结

18、点中的右指针域和后继结点的左指针域。9 (4) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 33 页学习必备欢迎下载10 (1) 11 (2) 12 (3) 三、算法设计题1.建立一个有 n 个结点的单链表，要求从尾部进行插入。分析：本题的算法思想是设置指针变量q 始终指向当前链表中的最后一个结点，新生成的结点直接在尾部进行插入。这种设置指针变量q 的方法使得操作比较简单，否则每次在尾部插入新结点时需要用一个临时指针变量从链表头部移到链表尾部。void createlklistfromtail (lklist *&head ) in

19、t i; lklist *p,*q; for (i=1,head=0;idata);p-next=0; if(i=1)head=q=p;else q-next=p;q=p; 提示：以下形式参数表中出现在形式参数名前加符号“&”的现象，这种现象在我们常见的Turbo C 2.0版本中不能使用，但在 Borland C 3.1及其以后版本中可以使用，它的作用是使得对形式参数的修改可以影响到对应的实在参数。以后算法设计题中经常用到。2.建立一个有 n 个结点的单链表，要求从头部进行插入。void createlklistfromhead (lklist *&head ) int i; lklist

20、*p,*q; for (i=1,q=head=0;idata); p-next=head; head=p; 提示：不断从头部插入新结点的方法来构造单向链表比不断从尾部插入新结点的方法来构造单向链表稍微操作简单一些。但顺序打印从尾部插入建立的单向链表所得到的序列与建立单向链表输入的序列一样，而顺序打印从头部插入建立的单向链表所得到的序列与建立单向链表输入的序列正好相反。3.用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表 （a1，a2，an）逆置为(an，an-1， a1)。void invertsqlist(sqlist &list) int i,temp,n=list.n;

21、 for(i=1;inext; q-next=0; while(p!=0)q=p; p=p-next; q-next=head; head=q; 5.已知集合 A、B，求集合 C=AB 算法，要求集合 A、B 和 C 均用采用顺序存储结构表示。分析：本题的算法思想是顺序取出集合A 中的元素 Ai ，然后再在集合 B 中从前向后进行顺序查找， 如果找到等于该元素的结点则将其放入集合C 中，否则什么也不做。本题算法思想同样适用于其后的第6 题。void intersectionsqlist(sqlist lista, sqlist listb,sqlist &listc) int i,j; for

22、(listc.n=0,i=0;i=lista.n-1; i+) for(j=0;j=listb.n-1; j+) if (listb.aj=lista.ai) break; if(jnext) for(q=listb;q!=0;q=q-next) if (p-data=q-data) break; if(q!=0) s=(lklist *)malloc(sizeof(lklist); s-data=p-data; s-next=listc; listc=s; 7.设计在带有头结点的单向链表中删除值为X 的结点算法。分析：本题的算法思想是首先在单链表中查找值为x 的结点，如果单链表为空或在单链表

23、中找不到值为x的结点则给出相应的提示信息，否则进行删除操作。为了便于删除操作的实现而设置指针变量p 指向被删除的结点，指针变量 q 始终指向其前驱结点。void deletelklist(lklist *&head, int x) lklist *q,*p; if (head-next=0) printf(“ This linklist is emptyn” );else for(q=head,p=head-next; p!=0; q=p, p=p-next) if (p-data=x) break; if (p=0) printf(“ Not found %d in this linklis

24、tn” ,x); else q-next=p-next; free(p); 提示：在链表中引入头结点后可以消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。具体涉及到本题中，如果没有引入头结点，则在找到值为x 的结点后要区分该结点是第一个结点还是其它结点，而引入头结点后，则这两种情况就可以统一处理。如果本题中的单链表没有带头结点，则需要将上述黑体中的代码改为代码if (p=head) head=p-next; else q-next=p-next;。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 3

25、3 页学习必备欢迎下载第三章栈和队列一、填空题1.线性表、栈和队列从逻辑上来说都是_ 结构。可以在线性表的 _位置插入和删除元素；对于栈只能在 _ 插入和删除元素；对于队列只能在_ 插入元素和在 _ 删除元素。2.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈， 所以又把栈称为 _ 表；队列的插入和删除运算分别在队列的两端进行，进行插入的一端叫做_ ，进行删除的一端叫做_ ，先进队的元素必定先出队，所以又把队列称为_ 表。3.假设用向量S1：m来存储顺序栈，指针top 指向当前栈顶的位置。则当栈为空时满足的条件是_ ；当栈为满时满足的条件是 _ 。4.设有一个空栈， 现有输入序列 1

26、、2、3、4、5，经过 push、push 、pop、push 、pop、push 、push 、pop、pop、pop后，输出序列为 _ 。5.在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front 指向实际队头元素的 _前一个位置_ ，尾指针 rear指向当前实际队尾元素的 _所在位置 _ 。若该顺序循环队列有m个存储单元，则队列满时共有 _ 个元素。6.设有一个顺序循环队列如上题中的约定，则该队列满的条件是_ ，队列空的条件是 _ 。7.不论是顺序栈（队列）还是链式栈（队列） ，插入（删除）运算的时间复杂度均为_ 。8.系统在函数调用前自动把调用后的_ 压入堆栈；当函数

27、调用结束后，系统又自动作退栈处理，并将程序执行流程无条件转移到所保存的_ 处继续执行。二、选择题1设栈的输入序列是 1、2、3、 n，输出序列的第一个元素是n，则第 i 个输出元素是（） 。 n-i n-i-1 n-i+1 不确定2设元素进栈次序为 A、B、C、D、E，则下列不可能的出栈序列是（） 。 ABCDE BCDEA EABCD EDCBA 3设用一维数组 sm表示栈的存储空间，用top 指向当前栈顶元素（其初始值为 -1） ，则进行出栈时的操作序列是（） 。 x=sop； x=stop；top=0； x=stop；top=top-1； x=stop；top=top+1；4设指针 hs

28、 指向栈顶，指针 s指向插入的结点 A，则插入结点 A 时的操作为（） 。 hs-next=s ； s-next=hs ； hs=s ； s-next=hs-next ； hs-next=s ； s-next=hs ； hs=hs-next ；5设用一维数组 sm表示栈的存储空间，用top 指向当前栈顶元素（其初始值为 -1） ，则进行入栈时的操作序列是（） 。 stop =x； top=top+1；stop=x； top=top-1；stop=x； stop=x；top=top+1；6 设 front是链式队列的头指针，rear是链式队列的尾指针， s指向插入的结点 A， 则插入结点 A 的

29、操作为 （） 。 front-next=s； front=s； s-next=rear ； rear=s ； rear-next=s ； rear=s ； s-next=front； front=s；7设 front 是链式队列的头指针， rear是链式队列的尾指针，则删除队头元素的操作为（） 。 front=front-next； rear=rear-next ； rear=front-next ； front=rear-next ；8对于一个具有 m 个存储单元的顺序循环队列，设front为队头指针， rear为队尾指针，则该队列中队列元素的个数计算公式为（） 。 rear-front f

30、ront-rear (rear-front)%m (rear-front+m)%m 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 33 页学习必备欢迎下载9 设用一维数组 qm作为顺序循环队列的存储空间， front 指向队头元素的前一个位置， rear指向队尾元素的当前位置，则入队列的操作序列为（） 。 qrear =x；rear=rear+1 ； qrear=x；rear=rear-1 ； rear=(rear+1)%m ；qrear =x； rear=(rear-1)%m ；qrear=x；10 设用一维数组 qm作为顺序循环队

31、列的存储空间， front 指向队头元素的前一个位置， rear指向队尾元素的当前位置，则出队列的操作序列为（） 。 x=qfront ；front=front+1；front=(front+1)%m；x=qfront； x=qfront ；front=front-1；front=(front-1)%m；x=qfront；三、算法设计题1 设有两个顺序栈 S1 和 S2 共享一个存储区 S0：m-1，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。2 设计算法判断表达式中的圆括号是否配对出现。3 设用一个单向循环链表来表示队列（也称循

32、环队列） ，该队列只设一个队尾指针rear ，不设队头指针 front，要求设计出该队列的入队列和出队列操作。4 假设以一个一维向量 q0：m-1作为顺序循环队列的存储空间，同时设变量rear和 len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。5 将数字 1、2、 n 按顺时针方向排列成环形，按顺时针方向从1 开始计数，计满时则输出该位置上的数字并从环中删除该数字，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止，要求设计一个算法完成此功能。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -

33、 -第 10 页，共 33 页学习必备欢迎下载第三章参考答案一、填空题1 线性，任何，栈顶，队尾，队头2 先进后出（ FILO） ，队尾，队头，先进先出（ FIFO）3 top=0，top=m 4 23541 5 前一个位置，所在位置，m-1 分析：在顺序循环队列中约定头指针front和尾指针 rear所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1 个。6 (rear+1)%m=front ，rear=front 7 O(1) 8 返回地址，返回地址二、选择题1.(3) 分析： 设栈的输入序列是 1、 2、 3、 、 n， 输出

34、序列的第一个元素是n， 则输出序列必定是 n、 n-1、 n-2、 、1，因此第 i 个输出元素是 n+1-i。2.(3) 3.(3) 4.(2) 5.(2) 6.(3) 7.(1) 8.(4) 分 析 ： 顺 序 循 环 队 列 中 的 元 素 个 数 =frontrearmfrontrearfrontrearfrontrear， 整 理 合 并 可 写 成(rear-front+m)%m。9.(3) 10.(2) 三、算法设计题1.设有两个顺序栈 S1 和 S2共享一个存储区 S0：m-1，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出

35、栈操作。分析：本题算法思想是引入形式参数flag，当形式参数 flag 的值为 1 时表示对栈 1 进行操作，flag 的值为 2时表示对栈 2进行操作。typedef struct int sm; int top1; int top2; sqstack; void push(sqstack &stack , int x,int flag) if (stack.top1+1=stack.top2) printf(“ stack is fulln” );else if (flag=1) stack.top1+; stack.sstack.top1=x; else if(flag=2)stack.

36、top2- ; stack.sstack.top2=x;else printf(“ input errorn” ); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 33 页学习必备欢迎下载void pop(sqstack &stack , int &y, int flag) if (flag=1) if(stack.top1=m) printf(“ emptyn” ); else y=stack.sstack.top2;stack.top2+; else printf(“ input errorn” ); 2.设计算法判断表达式中的

37、圆括号是否配对出现。分析：本题的算法思想是顺序扫描表达式，当扫描到左圆括号时进栈而扫描到右圆括号时出栈，如果扫描到右圆括号时不能出栈或扫描表达式结束时栈中仍有左圆括号则意味表达式中圆括号不匹配，否则表达式中圆括号匹配。typedef struct int sm; int top; sqstack; int matchbracket() char ch; sqstack stack; stack.top= -1; do ch=getchar(); if (ch= ( ) stack.top=stack.top+1; stack.sstack.top=ch; else if (ch= ) )if

38、(stack.top0) return(0); else stack.top=stack.top-1; while(ch!= # );if (stack.topdata=x; if (rear=0) rear=p; rear-next=rear;else p-next=rear-next; rear-next=p; rear=p; void outlkqueue(lklist *rear, int *y) lklist *p; if (rear=0) printf(“ queue is emptyn” );else if rear-next=rear y=rear-data; rear=0;

39、else p=rear-next; y=p-data; rear-next=p-next; free(p); 4.假设以一个一维向量 q0：m-1作为顺序循环队列的存储空间， 同时设变量 rear和 len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。分析：本题中出队列的算法思路是设置一个临时变量front指向当前队列中队头元素的实际位置， 考虑到表达式 queue.rear+1-queue.len 的值可能为负，因此设置front的值为 (queue.rear+1-queue.len+m)%m。typedef struct int qm;

40、 int rear; int len; sqqueue; void insqqueue(sqqueue &queue, int x) if (queue.len=m) printf(“ queue is fulln” );精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 33 页学习必备欢迎下载else queue.rear=(queue.rear+1)%m; queue.qqueue.rear=x;queue.len+; void outsqqueue(sqqueue &queue, int *y) int front; if (qu

41、eue.len=0) printf(“ queue is emptyln” );else front=queue.rear+1-queue.len+m%m; y=queue.qqueue.front;queue.len-; 5.编写一个算法解决约瑟夫（ Josephus ）环问题。其问题是：设有n 个人围坐在一张圆桌周围，现从第一个人开始从 1 报数，报到 k 的人出离开圆桌，接着从下一个人从1 开始重新报数，以此类推，直到他们都离开圆桌，求出他们离开圆桌的先后顺序。分析：本题的算法思路是设置变量sum 和 num，其中变量sum表示当前已经离开圆桌的人数个数，变量num表示当前的报数。voi

42、d Josephus( int n, int k) int i,num,sum,r100; for(i=0;in; i+) ri=i; for(sum=num=i=0; sumn; i=(i+1)%n) if (ri!=-1) num+; if (num % k=0) printf(%dt,i); num=0;sum+; ri= -1; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 33 页学习必备欢迎下载第四章字符串和数组一、填空题1.设字符串 S1=“ ABCDEF ” ，S2=“ PQRS ”，则运算 S=CONCAT(SUB

43、(S1，2，LEN(S2)，SUB(S1，LEN(S2)，2)的结果为 S=_ 。2.判断两个字符串相等的充要条件是_。3.下列程序段实现子串 t在主串 s中位置的算法，要求在下划线处填上正确语句。int index(char s , char t ) i=j=0; while(istrlen(s) & j=j）的地址为_。7.设有 n 行 n 列的三对角矩阵 A，每个数组元素占 L 个字节的存储单元， 按照从上到下从左到右的顺序将三条对角线上的元素存放在3n-2个连续的存储单元中，已知 A00 的地址为 1000， 则三对角线上元素 Aij的地址为 _ 。8.已知稀疏矩阵 A=0000510

44、000030200，则 A 的三元组表为 _ 。二、算法设计题1.设用顺序存储结构存储字符串S1和 S2，要求设计一个函数完成对两个字符串的比较。若 S1S2时则返回正数；若 S1=S2时则返回 0；若 S1S2时则返回正数；若 S1=S2时则返回 0；若 S1S2时则返回负数。int comparestring(char s1 , char s2 ) int i; for(i=0;s1i!=0;i+) if (s1i!=s2i) break; return(s1i-s2i); 2.用顺序存储结构实现在字符串S中删除所有其值等于ch（假设 ch= A ）的字符的算法。void deletest

45、ring(char s ,char ch) int i=0,j; while(si!=0) if (si=ch) for(j=i+1; sj!=0; j+) sj-1=sj; sj-1=0;else i+; 3.设计一个算法判断字符串S中的字符是否关于中心对称。typedef struct char sm; int top; sqstack; int stringsymmetry(char s ) int i; sqstack stack; stack.top= -1; for(i=0;si!=0;i+) stack.top+; stack.sstack.top=si; for(i=0;si!

46、=0;i+) if (si=stack.sstack.top) stack.top=stack.top-1; else return(0); return(1); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 33 页学习必备欢迎下载第五章树一、填空题1.设一棵树的二元组形式表示为T=（D，R） ，其中 D=A ，B，C，D，E，F，G，R=(A ，B)，(A，C)，(A，D)， (B， E)， (C， F)， (C， G)， 则该树的度数为 _ ， 树的深度为 _ ， 叶子结点的个数为 _ ，分支结点的个数为 _ ，C 结点的双亲

47、结点为 _ ，C 结点的孩子结点为 _ 。2.二叉树有 _ 种不同形态。3.对于一棵具有n 个结点的二叉树，当它为一棵_二叉树时具有最小高度，其最小高度为_ 。4.一棵深度为k 的满二叉树的结点总数为_ ；一棵深度为k 的完全二叉树的结点总数最少有_ 个，最多有 _ 个。5.已知一棵二叉树中度数为0的结点个数为 n0，度数为 1的结点数为 n1，则该树中度数为 2的结点数为 n2，则 n0=_ 。6.一棵树中度数为 1 的结点数为 n1，度数为 2 的结点数为 n2，度数为 m 的结点度为 nm，则该树中度数为 0 的结点数为 _ 个。7.已知一棵二叉树的顺序存储结构表示为ABCDEF（其中字

48、符表示空结点） ，则其前序序列为_ ，中序序列为 _ ，后序序列为 _ 。8.按照从上到下、 从左到右的顺序对有 n个结点的完全二叉树从1开始顺序编号，则编号为 i （i!=1 且 2i+1data=bt1-data; copybitree(bt1-lchild,bt2-lchild);copybitree(bt1-rchild,bt2-rchild); 2.设计判断两个二叉树是否等价的算法。int judgebitree(bitree *bt1,bitree *bt2) if (bt1=0 & bt2=0) return(1); else if (bt1=0&bt2!=0 | bt1!=0&

49、bt2=0 |bt1-data!=bt2-data) return(0); else return(judgebitree(bt1-lchild,bt2-lchild)*judgebitree(bt1-rchild,bt2-rchild); 3.设计层次遍历二叉树中所有结点的算法。分析：本题的算法思想是设置一个顺序循环队列，队列中的单元用来存储二叉树上结点的指针。先将二叉树上的根指针入队列，在队列非空的情况下取出队头元素访问所指向的结点且将该结点中的左右指针域入队列。void levelorder(bitree *bt) struct int front,rear; bitree *qm;qu

50、eue; bitree *p=bt; queue.rear=queue.front=0; if(bt!=0) queue.rear=(queue.rear+1)%m; queue.qqueue.rear=p; while (!(queue.front=queue.rear) queue.front=(queue.front+1)%m; p=queue.qqueue.front; visitnode(p); if(p-lchild!=0)queue.rear=(queue.rear+1)%m; queue.qqueue.rear=p-lchild; if(p-rchild!=0)queue.re