数据结构期中复习题.pdf

《数据结构期中复习题.pdf》由会员分享，可在线阅读，更多相关《数据结构期中复习题.pdf（21页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第 一 章 线 性 表一、单项选择题1.对于数据结构下列结论不正确的是()A.相同的逻辑结构，对应的存储结构也必相同B.数据结构由逻辑结构、存储结构和基本操作3个方面组成C.数据存储结构就是数据逻辑结构的机内的实现D.对数据基本操作的实现与存储结构有关2 .下面算法的时间复杂度是()i n t y=0;w h i le(n =(y+l)*(y+l)y+;)A.O(n)B.O(n2)C.O(l)D.O(Jn)3 .若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是()A.i 0 B.i Wn C.lWi Wn D.lWi Wn+14 .若长度为n的非空线性表采

2、用顺序存储结构，删除表的第i个数据元素，i的合法值应该是()。A.i 0 B.i Wn C.lWi Wn D.lWi Wn+15.若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，需要移动表中()个数据元素A.n-i B.n+i C.n-i+1 D.n-i-16.若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动表 中()个数据元素A.i B.n+i C.n-i+1 D.n-i-17.采用顺序存储结构的线性表的插入算法中，当n个空间已满时，可申请再增加分配m个空间。若申请失败，则说明系统没有()可分配的存储空间。A.m个 B.m个连续的 C.n+m个

3、D.n+m个连续的8.线性链表中各链结点之间的地址()。A.必须连续 B.一定不连续 C.部分地址必须连续 D,连续与否无所谓9.给定n个数据元素，逐个输入这些元素，建立一个有序单链表的时间复杂度是()oA.O(l)B.O(n)C.O(n2)D.O(n lo g n)10 .线 性 表(aba2,-,an)以链接方式存储时，访问第i个位置元素的时间复杂度为()A.O B.O(l)C.O(n)D.O(i-l)11.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()。A.O(l)B.O(n)C.O(m)D.O(m+n)12.将两个各有n l个n 2个元素的有序表(递增)归并成一个

4、有序表，仍保持其递增顺序，则最少的比较次数是()。A.n l B.n 2 C.n l+n 2-l D.m i n(n l,n 2)13.已知L是带头结点的单链表，结点p既不是首结点(第一个结点)，也不是尾结点，删除p结点的直接后继结点的语句序列是()A.p=p-n e xt;B.p-n e xt=p;C.p-n e xl=p-n e xt-n e xt;D.p=p-n e xt-n e xt;14.设双向链表中结点的结构为（prior,data,next）,在双向链表中删除指针p 所指的结点时需要修改指针（）A.p-prior-next=p-next;p-next-prior=p-prior;

5、B.p-prior=p-prior-prior;p-prior-next=p;C.p-next-prior=p;p-next=p-next-next;D.p-next=p-prior-prior;p-prior=p-next-next;15.设双向循环链表中结点的结构为（prior,data,next）,且不带表头结点。若想在指针p所指结点之后插入指针s 所指结点，则应执行下列哪一个操作（）。A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C.

6、s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;16.下面关于线性表的叙述中，错误的是哪一个（）。A.线性表采用顺序存储,B.线性表采用顺序存储,C.线性表采用链接存储,D.线性表采用链接存储,必须占用一片连续的存储单元便于进行插入和删除操作不必占用一片连续的存储单元便于插入和删除操作17.以下关于链式存储结构的叙述中，（）是不正确的。A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不必相邻C.可以通过计算直

7、接确定第i 个结点的存储地址D.插入、删除运算操作方便，不必移动结点18.如某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利 用（）存储方式最节省时间。A.顺序表C.带头结点的双循环链表B.双链表D.单循环链表19.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除一个元素，则采用（A.B.C.D.）存储方式最节省运算时间单链表仅有头指针的单循环链表双链表仅有尾指针的单循环链表20.设线性表非空，采用下列（）所描述的链表可以在0（1）时间内在表尾插入一个新结点。A.带表头结点的单链表，一个链表指针指向表头结点B.带表头结点的单循环链表，一个链表指针指向表头

8、结点C.不带表头结点的单链表，一个链表指针指向表的第一个结点D.不带表头结点的单循环链表，一个链表指针指向表的第一个结点2 1 .线性表的静态链表存储结构与顺序存储结构相比优点是()。A.所有的操作算法实现简单 B.便于随机存储C.便于插入和删除 D.便于利用零散的存储空间2 2 .下面说法正确的是()A.集合与线性表的区别在于是否按关键排序B.对于任何数据结构，链式存储结构一定优于顺序存储结构C.链表中的头结点仅起到标识作用D.在单链表中设置头结点的作用主要是使插入和删除等操作统一，在第一个元素之前插元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。二、综合应用题1 .

9、线性表(a l,a 2,a 3,a 4)采用顺序存储，每个元素都是整数，试设计算法用最少时间把所有值为负数的 元 素 移 到 全 部 正 数 值 元 素 前 边 的 算 法。例(-X,-X,X,X)O2 .线性表(a l,a 2,a 3,a n)中元素递增有序按顺序存储，要求设计算法完成下述功能：(1)用最少时间在表中查找数值为x的元素；(2)若找到将其与后继元素位置相交换；(3)若找不到将其插入表中并使表中元素仍递增有序3 .已知一个带有头结点的单链表，假设该链表只给出了头指针L,在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点(k 为正整数)，若查找成功

10、，算法输出该结点的d a t a 域的值，并返回0。要求：(1)描述算法的基本设计思想；(2)描述算法的详细实现步骤；(3)根据设计思想和实现步骤，采用程序设计语言描述算法，关键之处请给出简要注4 .假设一个单循环链表，其结点含有三个域(p r e,d a t a,n e x t)。其中d a t a 为数据域；p r e 为指针域，它的值为空指针；n e x t 为指针域，它指向后继结点。请设计算法，将此表改成双向链表。5 .试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法、函数原型如下：v o i d d e l e t e(L i n k L i s t&L);6 .设计个

11、算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链结点。函数原型如下：v o i d d e l i n s e r t(L i n k L i s t&L);7 .编写一个算法来交换单链表中指针p 所指结点与其后继结点，h ead 是该链表的头指针，p指向该链表中某一结点。8 .假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值非递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。9 .编写一个算法，设有两个无头结点的单链表，头指针分别为h a、h b,两个链表的数据都按递增

12、序存放。要求将h b归并到h a表中，且归并后h a仍递增序，在归并中对于h a表中已有的数据若h b 中的这部分也有，则 h b 中的这部分数据不归并到h a中，h b 的链表在算法中不允许破坏。1 0 .已知L I、L 2 分别为两个单循环链表的头结点指针，m、n分别为L I、L 2 表中数据结点个数。要求设计一个算法，用最快速度将两表合并成一个带头结点的单循环链表。1 1 .已知不带头结点的线性表l i s t,链表中结点构造为(d at a,n ex t),其中d at a为数据域，n ex t 为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使

13、用除该链表以外的任何链接点空间。1 2 .已知线性表第一个链接点指针为l i s t,请写一算法，将该链表分解为两个有头结点的循环链表，并将两个循环链表的长度分别存放在各自头结点的数据域中。其中，线性表中序号为奇数的元素分解到第个循环链表中，序号为偶数的元素分解到第二个循环链表中。（要求用最少的时间和最少的空间）1 3 .设键盘输入n 个英语单词，输入格式为n,wl,w2,wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单链表，实现：（1）如果单词重复出现，则只在链表上保留一个；（2）除 满 足（1）的要求外，链表结点还应有一个频度域，记录该单词重复出现的次数，然后输出出现次数最多的

14、前k （k ne x t=x B.x-ne x t=t op-ne x t;t op-ne x t=x;C.x-ne x t=t op;t op=x;D.x-ne x t=t op;t op=t op-ne x t;1 0.由两个栈共享一个向量空间的好处是()。A.减少存取时间，降低上溢发生的几率 B.节省存储空间，降低上溢发生的几率C.减少存取时间，降低下溢发生的几率 D.节省存储空间，降低下溢发生的几率1 1.若栈采用顺序存储方式存储，现两栈共享空间代表第i 个 栈(i=l,2)的栈顶，栈 1 的底在V l ,栈 2的底在V m ,则栈满的条件是()。A.t op 2 -t op l =0

15、;B.t op l +l=t op 2 ;C.t op l +t op 2 =m;D.t op l =t op 2 ;1 2 .设计个判别表达式中左、右括号是否匹配的算法，采 用()数据结构最佳。A.线性表的顺序存储结构 B.队列C.线性表的链式存储结构 D.栈1 3 .表达式a*(b+c)-d 的后缀表达式是()。A.a b e d *+-B.a b c +*d -C.a b c *+d -D.-+*a b e d1 4 .表达式3*2 7 4+2*2-6*3)-5求值过程中，当扫描到6时，操作数对象栈和运算符栈分别为()，其中.表示幕乘。A.3 2 4 1 1;(*(+*-B.3 2 8;

16、(*-C.3 2 4 2 2 ；(*-(-D.3 2 8 ;(*-(-1 5.单循环链表表示的列队长度为n,若只设头指针，则入队的时间复杂度为()。A.0(n)B.0(1)C.0(n*n)D.0(nlogn)16.设栈S和列队Q的初始状态为空，元素A,8,&口,邑入6一次进栈5,一个元素出栈后即进入队列Q,若七个元素出队列的顺序为及,&忑 ,6,则栈$的容量至少应该是()。A.2 B.3 C.4 D.717.若元素abcdef依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是()A.dcebfa B.cbdaef C.dbcaef D.afedcb18

17、.循环队列存储在数组A0.m中，则入队时的操作为().A.rear=rear+l B.rear=(rear+1)MOD(m-1)C.rear=(rear+1)MOD m D.rear=(rear+1)MOD(m+1)19.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别是。和3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是()。A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 120.最大容量为n的循环队列，队尾指针为rear,队头指针为front,则队空的条件是()。A.(rear+1)MOD n=front B.rear=fro

18、ntC.rear+l=front;D.(rear-1)MOD n=front21.循环队列用数组A0.m-1存放其元素值，已知其队头指针front指向队头元素，队尾指针rear指向队尾元素，则当前队列的元素个数是()。A.(rear-front+m)MOD n=front B.rear-front+1C.rear+l=front D.(rear-front+m-1)MOD m22.用链式方式存储的队列，在进行删除运算时()。A.仅修改头指针 B.仅修改尾指针C.头、尾指针都要修改 D.头、尾指针可能都要修改23.已知二维数组AL.4,L.6采用行序为主序方式存储，每个元素占用3个存储单元，并且

19、All的存储地址为1200,元素A24的存储地址是()。A.1221 B.1227 C.1239 D.125724.已知二维数组Al.4,1.6采用列序为主序方式存储，每个元素占用4个存储单元，并且A34的存储地址为1234,元素All的存储地址是()。A.1178 B.1290 C.1278 D.119025.C语言中定义的整数一维数组a50和二维数组b10 5具有相同的首元素地址，即&(a0)=&(b0 0)，在以列序为主序时，a18的地址和()相同。A.bl7 B.bl 8 C.b8l D.b7l26.对一些特殊的矩阵采用压缩存储的目的主要是为了()。A.表达变得简单 B.对矩阵元素的存

20、取变得简单C.去掉矩阵中的多余元素 D.减少不必要的存储空间开销27.按照压缩储存的思想，对于具有t个非零元素的m*n阶稀疏矩阵，可以采用三元组表储存方法储存，但t满 足()关系是，这样做才有意义。A.tm*n B.t(m*n)/3 C.tv=(m*n)/3-l D.t(m*n)/3-l二、综合应用题1、试证明：若借助栈由输入顺序1,2,.n得到输出序列为pl,p2,pn(它是输入序列的一个 排 列),则在输出序列中不可能出现这样的情形：存在着ijk,使PjPkPi。2、在一个算法中需要建立多个堆栈时可以选用下列三种方法之一，试问：着三种方案之间相比较各有什么优缺点？(1)、分别用多个顺序表储

21、存空间建立多个独立的堆栈；(2)、多个堆栈共享一个顺序储存空间；(3)、分别建立多个独立的链接堆栈。3、数组8,-2.6,0.6 以行为主序存储，设第一个元素的首地址时7 8,每个元素的长度为4,试求元素A 4,2,3 的存储地址。4.假设按低下标优先存储整型数组A-3.8,3.5,-4.0,0.7 时，第一个元素的字节存储地址 是 1 0 0,每个整数占4 个字节，问元素A 0,4,-2,5 的存储地址是什么？5.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域:ch和 next,其中ch域为字符类型。设栈已定义：InitStack(

22、S),Push(S,e),StackEmpty(S),GetTop(S,e),Pop(S,e)分别为栈初始化,入栈，判断栈空，获得栈顶元素，出栈等操作。6.在 数 组 中 有 n 个数据，试建立个带有头结点的循环链表，头指针为h,要求链中数据从小到大排列，重复的数据在链中只保存一个。7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。8.设整数序列al,a 2,，a n,给出求解最大值的递归程序。9、编写一个过程，对一个m*n的矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。第一章线性表一、选择题1.A 选 项 A 错误的原因

23、是相同的逻辑可以用不同的存储结构来实现，例如线性表可以用顺序存储结构来实现2.D 本体中每次循环将y 的值加1,然后比较n 与(y+1)(y+1)大小，所以总共要进行册次比较3.D 在线性表的第1 至 第 n 个位置插入一个数据元素显然是允许的，紧挨在线性表的最后那个数据元素的后面插入一个数据元素也是允许的，因此，i 的合法值应该是1 f 7 1 +14.C 只有删除非空线性表的第1 至 第 n 个元素才是可能的，因此，i 的合法值应该是1 /n e x t p r i o r=s；要出现在P n e x t=s；之后。选项A.B.C 均造成p r i o r 指向其自身16.B线性表采用顺序

24、存储，便于进行查找操作，不便于进行插入和删除操作17.C选项C 错误的原因是链式存储结构的地址不一定是连续的，所以不能通过计算直接确定地i 个结点的存储地址18.A只有顺序表才能存取任一指定序号的元素，其他存储方式都需要遍历才能到达相应元素。顺序表同样可以在末尾进行插入和删除元素19.D本题显然应该在选项B 和选项D 中选择正确答案，考虑到需要在最后一个元素之后插入和删除第一个元素，所以最好可以直接得到链表尾指针。如果需要只有头指针，必须遍历所有89p-next=q-next;q-next=p;)/p 的后继指向原p 后继的后继原p 后继的后继指针指向p)算法结束8【分析】因为两链表已按元素值

25、递增次序排列，将其合并时，均从第一个结点起进行比较,将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值非递增次序排列。故在合并的同时，将该链表结点逆置，可采用头插法建立结果链表。【算法如下】void Union(LinkList&la,LinkList&lb)/*la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值非递增次序排列的单链表*/pa=la-next;pb=lb-next;la-next=null;/pa,pa分别是链表la和 1b的工作指针匕作结果链表的头指针，先将结果链表初始化为空while(pa!=null&

26、pb!=null)if(pa-datadata)r=pa-next;pa-next=la-next;la-next=pa;当两个链表均不为空时将p a的后继结点暂存于r将p a的结点链于结果表中，同时逆置pa=r;)/恢复p a为当前待比较结点else r=pb-next;将p b 的后继结点暂存于rpb-next=la-next;将pb结点链于结果表中，同时逆置la-next=pb;pb=r;恢复pb为当前待比较结点)while(pa!=null)将la表的剩余部分链入结果表，并逆置r=pa-next;pa-next=la-next;la-next=pa;pa=r;)while(pb!=nu

27、ll)将1b表的剩余部分链入结果表，并逆置i-=pb-next;pb-next=la-next;la-next=pb;pb=r;)算法结束上面两个链表均不为空的表达式也可简写为while(pa&pb),两递增有序表合并成非递增有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。9【分析】本 题 与“将两个按元素值递增次序排列的线性表，归并为；一个按元素值非递增次序排列的单链表”问题类似，不同之处在于：一是链表无头结点，为处理

28、方便，给加上头结点，处理结束再删除之；二是数据相同的结点，不合并到结果链表中；三是hb链表不能被破坏，即将hb 的结点合并到结果链表时，要生成新结点；【算法如下】void Union(LinkList&ha,LinkList&hb)/*ha,hb是两个无头结点的按数据域值递增有序的单链表，本算法将h b 中并不出现在h a 中的数据合并到h a中，合并中不能破坏hb链表*/LinkList la;la=(LinkList)malloc(sizeof(LNode);la-next=ha;pa=ha;pb=hb;pre=la;while(pa&pb)if(pa-datadata)pre-next=

29、pa;pa=pa-next;申请头结点，以便操作/pa是 ha链表的工作指针/pb是 hb链表的工作指针/pre指向当前待合并结点的前驱处理h a中数据else if(pa-datapb-data)r=(LinkList)malloc(sizeof(Lnode);处理h b 中数据申请空间r-data=pb-data;pre-next=r;pre=r;将新结点链入结果链表pb=pb-next;i/hb链表中工作指针后移)else 处理 pa-data=pb-datapre-next=pa;pre=pa;pa=pa-next;两结点数据相等时，只将h a的数据链入pb=pb-next;)if(p

30、a!=null)pre-next=pa;不要hb 的相等数据将两链表中剩余部分链入结果链表else pre-next=pb;free la;算法结束释放头结点，ha、hb指针未被破坏10【分析】单循环链表L1和 L2数据结点个数分别为m 和 n,将二者合成一个单循环链表时，需要将一个单循环链表的结点(从第一元素结点到最后一个结点)插入到另单循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并”，因此应找结点个数少的链表差其尾结点。【算法如下】void Union(LinkList&Ll,LinkList&L2,int m,int n(/*L1和 L 2 分别是两个单循环链表的头结点的指

31、针，m 和 n 分别是L1和 L 2的长度。本算法最快速度将L 1和 L2合并成一个单循环链表*、if(m0llno)printf(表长输入错误n);exit 0;)if(mvn)若m next!=L 1 )p=p-next;查最后一个元素的结点p-next=L2-next;将L1单循环链表的元素结点插入到L 2的 第 个 元素结点钱L2-next=L 1 -next!=L2)p=-P-next;查最后个元素的结点p-next=L l-next;Ll-next=L2-next;将 L 2的元素结点插入到单循环链表L 1的第一元素结点前Free L 2;/释放无用头结点)算法结束1 1【分析】本

32、题实质上是一个排序问题，要求“不得使用除该链表结点以外的任何链接点空间”。链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。【算法如下】LinkList ListSort(LindList&list)/*list是不带头结点的线性链表，本算法将该链表按结点数据域的值，从小到大重新链接*/p=list-next;/p是工作指针，指向待排序的当前元素list-next=null;假定第一个元素有序，即链表中现在只有一个结点while(p!=null)r=p-next;/r 是 p 的后继q=list;if(q-d

33、atap-data)/处理待排序p 的结点比第一个元素小的情况p-next=list;list=p;链表指针指向最小的元素)else(查找元素最小值的结点while(q-next!=null&q-next-datadata)q=q-next;p-next=q-next;将当前排序结点链入有序链表中q-next=p;)P=r;/p指向下个待排序结点)算法结束算法时间复杂度的分析与用顺序表存储结构时的情况相同。但顺序储存结构将第i(i l)个元素插入到前面第1 至第i-1个元素的有序表时，是将第i 个元素先与第i-1个元素比较。而在链表最佳情况均是和第一元素比较。两种存储结构下最佳和最差情况的比较

34、次数相同，在链表情况下，不移动元素，而是修改结点指针。另外，本题中线性链表list不带头结点，而且要求“不得使用除链表以外的任何链结点空间”，所以处理复杂，需要考虑当前结点元素值比有序链表第一结点的元素值还小的情况，这时需要修改链表指针list。如 果 list是头结点指针，则相应处理要简单些，其算法如下：LinkList LinkListSort(LinkList&list)P=list-next;p 指向第一元素结点List-next=null;有序链表初始化为空While(p!=null)r=p-next;保存后继q=list;while(q-next!=nun&q-next-datad

35、ata)q=q-next;p-next=q-next;q-next=p;q=r;)算法结束12.【分析】将一个单链表分解为两个带有头结点的循环链表，这是道典型的链表分解的算法设计题。本题的实质是构造单循环链表，即首先要分别构造两个单循环链表的表头结点，然后从原单链表第一个结点开始，在遍历单链表的过程中，将符合要求的结点插入到各自的单循环链表中。注意不要因结点插入新建链表而使原链表断链。另外，题目并未要求链表有序，插入采用“头插法”或“尾插法”均可。【算法如下】Void split(LiskList&List,LiskList LiskList&list2)*List是无头节点的单链表第个节点的

36、指针，本算法将链表List分解成带头节点的两个循环链表*/Listl=(LinkList)maIloc(sizeof(LNode);List2=(LinkList)malloc(sizeof(LNode);/简历两个链表的头节点p=list;q=list;r=list2;len 1=0;len2=0;mark=1;while(p!=null)if(mark=l)q-next=p;q=q-next;lenl+;mark=2;分解原链表处理序号为奇数的节点elser-next=p;r=r-next;len2+;mark=1;/处理序号为偶数的节点)listl-data=lenl;Iist2-dat

37、a=len2;q-next=listl;r-lnext=list2;/将两个链表的长度分别存放在各自头节点的数据域中将两个链表置为单循环链表/算法结束算法中对List链表中每个节点只处理一次，时间复杂度0(n)，只增加了必须的两个表头节点，符 合 题 目“用最少的时间和最少的空间”的要求。1 3.(分析)本体链表节点的数据域存放英文单词，可用字符数组表示，单词重复出现时，链表中只保留一个，单词是否相等的判断使用strcmp函数，节点中增设频度域，统计单词重复出现的次数。Typedef struct node Int freq;Char wordmaxsize;Struct node*next;

38、node,*LinkList;(算法如下)(1)LinkList creat()/建立有n(n 0)个单词的单向链表，若单词重复出现，则只在链表中保留一个LinkList la;/申请头节点la=(LinkList)malloc(sizeof(node);/链表初始化la-next=null;for(i=l;inext;pre邛；While(p!=null)If(strcmp(p-data,a)=O)p-freq+;Break;)elsepre=p;p=p-next;)if(p=null)/建立n 个节点的链表/a 是与链表中节点数据域同等长度的字符数组/p 是工作指针，pre是前驱指针单词重

39、复出现，频度增1/指针后移该单词没出现过，应插入p=(LinkList)malloc(sizeof(node);strcopy(p-data,a);p-freq=1;p-next=null;/将新节点插入到链表最后pre-next=p;)/结束for循环return la;/算法结束(2)Void CreatOut()/*建 立 有n个单链表的单项链表，重复单词只在链表中保留一个，最后输出频度最高的k个 单 词*/LinkList la;申请头节点la=(LinkList)malloc(sizeof(node);la-next=null;for(i=l;inext;pre=p;while(p!

40、=null)if(strcmp(p-data,a)=O)p-freq+;pre-next=p-next;pre=la;q=la-next;while(q-freqp-freq)pre=q;q=q-next;)pre-next=p;p-next=q;/链表初始化/建 立n个节点的链表/a是与链表中节点数据域同等长度的字符数组 p是工作指针，pre是指针前驱单词重复出现，频 度 增1先将节点p从链表上摘下，再按频度域值插入到合适位置将P结点插入到合适位置elsepre=p;p=p-next;/指针后移if(p=null)p=(LinkList)malloc(sizeof(node);strcopy

41、(p-data,a);p-freq=l;p-next=null;pre-next=p;)该单词没出现过，应插入到链表最后/新结点插入/结 束for循环建表int k,i=0;scanf(“输入要输出的单词的个数才,&1next;while(p&ifreq);p=p-next;)if(!p)printf(给出的d 值太大n”,k);算法结束第二章栈与队列一、选择题1.【答案】C栈和队列都是特殊的线性表。栈将插入和删除操作限制在表的一端进行，而队列将插入和删除操作分别限制在表的两端进行。它们的共同点是只允许在表的端点处进行插入和删除操作。2 .【答案】C若某栈的输入序列为1，2,3,4,按照出栈操

42、作的原则，不可能得到出栈序列4,3,1,2。这是由于出栈序列的第个元素为4,则必须首先一次将1,2,3,4进栈，然后将此时的栈顶元素4出栈，此时新的栈顶元素为3,继续将3出栈(注意，此时的出栈序列为4,3),按照题目的要求，出栈序列的下一个元素应该是1,而此时新的栈顶元素为2,而不是1,因此，得不到元素1,导致不能够得到序列4,3,1,2 3 .【答案】A本题主要考察的内容有两个：C语言关于标识符的规定和栈的先进先出的特性。标识符的第一 个字符必须是大小写英文字符或者下划线，而不能是数字。按照上述规定n l 一三个字符符合规定的标识符有n l _,n,n,_ n l 四种形式。字符按照n l

43、_ 的顺序进栈，根据栈的先进先出的特性，输出的顺序只能出现三种形式：第一种输出n l _ 的实现：n 进栈再出栈，1 进栈再出栈，_ 进栈再出栈：第二种输出n _ l 的实现：n 进栈再出栈，I 进栈一进栈，一出栈1 出栈；第三种输出n的实现：n 进 栈 1 出栈一进栈，一出栈1 出栈门出栈。而输出_ n l 的情况不可能实现。4 .【答案】C每次栈输出后，栈顶元素依次减1,所以i 个元素输出后栈顶元素为n-i,而输出元素为n-i+U5.【答案】D本题主要考查一个进栈序列对应多个出栈序列的问题。题目实际上是求当n最后一个进栈而第 k 个出栈的情况，在 n 之后出栈的书可能是第几个进栈的。对题目

44、中的输入序列，可以让所以元素一次全部进栈，然后一次全部出栈，此时n是最后一个进栈而第一个出栈。此外，也可以让一个数进栈后马上进栈，此时n是最后一个进栈最后一个出栈。还可以让若干数进栈，然后一次出栈，再让最后若干个数进栈并出栈，重复这样的操作直至所有数都进栈并出栈-次。因此，在 n之前入栈而在n之后出栈的数是不固定的。6.【答案】C这里需要注意的是：a.b,c 这 3个字母不定要全部集进栈以后再出栈，为此就有了多种排列的可能。本题如果按照正向思维来解的话，要考虑各种进栈出栈的可能性，这样很容易漏解，而且思维比较乱。可以逆向思维解此题，3 个字母最多的排列个数也就是3*2*1=6 种可能情况一一考

45、虑是否符合进栈出栈的场景，这样比较清晰得得到答案。(1)出栈序列为a,b,c:a进栈，a出栈，b 进栈，b出栈，c 进栈，c出栈。(2)出栈序列为a,c,b:a 进栈，a出栈，b进栈，c出栈，c 进栈，b出栈。(3)出栈序列为b,c,a:a 进栈，b 进栈，b出栈，c 进栈，c出栈，a出栈。(4)出栈序列为b,a,c:a 进栈，a出栈，b进栈，b出栈，c 进栈，c出栈。(5)出栈序列为c,a,b:不可能的序列。(6)出栈序列为c,b,a:a进栈，a进栈，c 进栈，c出栈，b进栈，a出栈。7.【答案】C一般情况下，设计一个递归问题的非递归算法需要设置栈结构。8.【答案】C调用函数时，系统将会为调

46、用者构造一个由参数和返回地址组成的活动记录，并将记录压入系统提供的栈中，若被调用函数有局部变量，也要压入栈中。9.【答案】C本题主要考查链栈的进栈操作。10.b 两个栈共享一个向量空间的好处主要是节省存储空间，另外也可以降低上溢发生的几率。11.B 两个栈共享个空间的时候，由于栈底是固定的且有两个，所以栈底一定的是该空间的两端，然后数据存放在中间。所以栈满的条件是两个栈顶相邻，也就是to p【1】+1=top【2】。12.d 很容易想到用栈来表示，将左括号逐一入栈，如果得到右括号则出栈，在扫描结束时，如果栈为空，则表明括号匹配。13.b 对于选择题，可以将后缀表达式转变为后缀表达式的算法，以

47、abc+*d-为例，将其转换成中缀表达式的过程如下：从左向右扫描，遇到的第一个操作符是+,前面最靠近的操作数是b e,应该是b+C;此刻将b+c作为一个操作数，继续扫描得到操作符是*,前面最靠近的操作数是a 和(b+c),则得到a*(b+c)；此时a*(b+c)是一个操作数，继续扫描得到操作符一,前面的操作数为a*(b+c)和 d,最终得到a*(b+c)d14.d 本题中容易得带在扫描到6 时，4+2*2已经完全独立计算出得8,所以操作数对象栈为3,2,8；至于操作符，选 项 b 和 d 在 前 差 一 个“(”，但实际上6 之前为如果没有“(”，则由于“人”优先级较高，必须先计算2人 8,不

48、符合题意，所以应该选do15.a 队列的入队操作是把新增的节点插入到当前队列的队尾处。根据题目假设该队列只有头指针，没有尾指针。因此，要到达队尾，必须从头指针依次遍历到队尾，再将新增结点插入队尾，完成入队操作。遍历的过程需要经过n 步，因此入队的时间复杂度是o(n)16.b 根据题目可知，七个元素出队列的顺序为bdefeag,则七个元素入队列的顺序为bdefeag,七个元素出栈的顺序也为bdefeag,而入栈顺序为abedefg。根据栈的进栈和出栈操作的特点，其操作过程为ab 进栈，b 出栈，cd进栈，c 出栈，e f进栈，f 出栈，e出栈，a 出栈，g 进栈，g 出栈。可见，栈 s 的容量至

49、少为3.17.d 解法一：四个选项所给序列中出现长度大于等于3 的连续逆序子序列，即为不符合要求的出栈序列。解法二：根据题目可知，四项所给序列的进出操作序列分别为：a.PUSH PUSH PUSH PUSH POP POP PUSH POP POP PUSH POP POPb.PUSH PUSH PUSH POP POP PUSH POP POP PUSH POP PUSH POPc.PUSH PUSH POP PUSH POP POP PUSH POP PUSH PUSH POP POPd.PUSH POP PUSH PUSH PUSH PUSH PUSH POP POP POP POP P

50、OP18.d 数组a 包含m+1个元素。19.b 删除最后一个元素后，front+1；加入两个元素后，rear+2.20.b 循环队列的初始状态以及对空的条件的头指针和尾指针重叠。21.c 队尾指针rear指向队尾元素，并非指向对我饿哦元素的下一个位置。当 rearfront时，队列的元素个数是rear-front+1；当 rear front时，队列的元素个数是rear-front+m+1 22.D 在有头结点的链队列的出队操作中，一般只需要修改队头指针，但当队列中只有一个结点时，该结点即使队头也是队尾，故删去此结点时也需要修改尾指针，使其指向头结点，且删去此结点后队列变空。23.B 对于二