数据结构复习题2013新版

1、数据结构各章复习资料数据结构复习参考题资料 计算机科学与技术专业2013.7第一章 绪论一、选择题:1、在数据结构的讨论中把数据结构从逻辑上分为( C )。A、内部结构与外部结构 B、静态结构与动态结构C、线性结构与非线性结构 D、紧凑结构与非紧凑结构2、下面程序段的时间复杂度为( C )。 for(int i=0;i<m;i+) for(int j=0;j<n;j+) aij=i*j;A、O(m2) B、O(n2) C、O(m*n) D、O(m+n) 3、执行下面程序段时，执行S语句的次数为( D )。 for(int i=1;i<=n;i+) for(int j=1; j

2、<=i;j+) S;A、n2 B、n2/2 C、n(n+1) D、n(n+1)/2、某算法的时间代价为T（n）=100n+10nLog2n+n2+10，其时间复杂度为（C）。A、O（n） B、O(nlog2n) C、 O(n2) D 、O(1)二、填空题、数据结构的抽象数据类型ADT可用三元组表示（D，S，P），其中D是（数据对象），S是( 关系集 )，P是( 操作集 )。、数据的基本单位是( 数据元素 ),最小单位是( 数据项 )。3、一个算法的时间复杂性通常用它的( T（n）=O(F(n) )形式表示，当一个算法的时间复杂性与问题的规模n大小无关时，则表示为( O(1) )；成正比时

3、，则表示为( O(n) ) ；成对数关系时，则表示为(O(log2n) )；成平方关系时，则表示为( O(n2) )。4、我们常常称数据的逻辑结构为数据结构，数据的逻辑结构有两类：(线性结构)， (非线性结构 )。5、一个算法应该具有(有穷性)、(确定性)、(可行性 )、( 零个或多个输入 )、(一个或多个输出 )五个特征。6、数据结构中的逻辑结构具体分为四种分别是（线性结构）（树型结构）（图或网型结构）（集合）。7、数据结构中的存储结构具体分为二种分别是（顺序存储结构）（链式存储结构）。三、简答题1、比较顺序存储结构和链式存储结构的优缺点？参考答案：1）顺序表的特点是逻辑上相邻的数据元素，物

4、理存储位置也相邻，并且，顺序表的存储空间需要预先分配。它的优点是：（1）方法简单，各种高级语言中都有数组，容易实现。（2）不用为表示节点间的逻辑关系而增加额外的存储开销。（3）顺序表具有按元素序号随机访问的特点。缺点：（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。2）在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。链表的最大特点是：插入、删除运算方便。缺点：（1）要占用额外的存

5、储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。（2）链表不是一种随机存储结构，不能随机存取元素。3）顺序表与链表的优缺点切好相反，那么在实践应用中怎样选取存储结构呢？通常有以下几点考虑：（1）顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。然而，链表的动态分配则可以克服这个缺点。链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以

6、再程序运行时随时地动态分配空间，不需要时还可以动态回收。因此，当线性表的长度变化较大或者难以估计其存储规模时，宜采用动态链表作为存储结构。但在链表中，除数据域外海需要在每个节点上附加指针。如果节点的数据占据的空间小，则链表的结构性开销就占去了整个存储空间的大部分。当顺序表被填满时，则没有结构开销。在这种情况下，顺序表的空间效率更高。由于设置指针域额外地开销了一定的存储空间，从存储密度的角度来讲，链表的存储密度小于1.因此，当线性表的长度变化不大而且事先容易确定其大小时，为节省存储空间，则采用顺序表作为存储结构比较适宜。（2）基于运算的考虑（时间）顺序存储是一种随机存取的结构，而链表则是一种顺序

7、存取结构，因此它们对各种操作有完全不同的算法和时间复杂度。例如，要查找线性表中的第i个元素，对于顺序表可以直接计算出a(i)的的地址，不用去查找，其时间复杂度为0(1).而链表必须从链表头开始，依次向后查找，平均需要0(n)的时间。所以，如果经常做的运算是按序号访问数据元素，显然顺表优于链表。反之，在顺序表中做插入，删除时平均移动表中一半的元素，当数据元素的信息量较大而且表比较长时，这一点是不应忽视的；在链表中作插入、删除，虽然要找插入位置，但操作是比较操作，从这个角度考虑显然后者优于前者。（3）基于环境的考虑（语言）顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的。相对来讲

8、前者简单些，也用户考虑的一个因素。总之，两种存储结构各有长短，选择哪一种由实际问题中的主要因素决定。通常“较稳定”的线性表，即主要操作是查找操作的线性表，适于选择顺序存储；而频繁做插入删除运算的（即动态性比较强）的线性表适宜选择链式存储。2、评价一个算法的好坏的标准是什么？由于针对一个问题可能会有不同的算法去解决，不同的算法思路不同，有的执行速度很慢，效率低；有的执行速度很快，效率自然会很高。这样也就出现了算法的“好”与“坏”之分，如何衡量一个算法的好坏，通常要从以下几个方面来分析。1）正确性算法能满足具体问题的需求，即对任何合法的输入算法都会得出正确的结果。2）可读性算法创建后由人来阅读、理

9、解、使用以及修改。所以可读性的好坏直接影响到算法的好坏。如果一个算法涉及的想法很多，就会给阅读的人造成困难，那么这个算法就不能得到更好的交流和推广，更不便于对算法进行修改、扩展和维护。所以要提高算法的可读性，就要做到简明易懂。3）健壮性一个程序完成后，运行该程序的用户对程序的理解各有不同，并不能保证每一个人都能按照要求进行输入，健壮性就是指对非法输入的抵抗能力，当输入的数据非法时，算法能识别并做出处理，而不会因为输入的错误产生错误动作或造成瘫痪。4）时间复杂度与空间复杂度时间复杂度简单地说就是算法运行所需要的时间。不同的算法具有不同的时间复杂度，当一个程序较小时感觉不到时间复杂度的重要性，当一

10、个程序特别大时便会察觉到时间复杂度的重要性。所以如何写出更高速的算法一直是算法不断改进的目标。空间复杂度是指算法运行所需的存储空间，随着计算机硬件的发展，空间复杂度已经显得不再那么重要。第二章 线性表一、选择题1线性表是( A ) 。A、 一个有限序列，可以为空； B、一个有限序列，不能为空； C、一个无限序列，可以为空； D、一个无序序列，不能为空。 2对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A）个元素。A、 n/2 B、（n+1）/2 C、（n -1）/2 D、 n 3线性表采用链式存储时，其地址( D ) 。A、必须是连续

11、的 B、部分地址必须是连续的 C、一定是不连续的 D、连续与否均可以 4用链表表示线性表的优点是（ C ）。A、便于随机存取 B、花费的存储空间较顺序存储少C、便于插入和删除 D、数据元素的物理顺序与逻辑顺序相同5、某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表6、循环链表的主要优点是( D ) 。A、不在需要头指针了B、已知某个结点的位置后，能够容易找到他的直接前趋C、在进行插入、删除运算时，能更好的保证链表不断开D、从表中的任意结点出发都能扫描到整个链表7、下面

12、关于线性表的叙述错误的是( B )。A、线性表采用顺序存储，必须占用一片地址连续的单元；B、线性表采用顺序存储，便于进行插入和删除操作；C、线性表采用链式存储，不必占用一片地址连续的单元；D、线性表采用链式存储，便于进行插入和删除操作；8、单链表中，增加一个头结点的目的是为了（ C ）。A、使单链表至少有一个结点 B、标识表结点中首结点的位置C、方便运算的实现 D、说明单链表是线性表的链式存储9、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表10、若

13、某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（B ）存储方式最节省运算时间。A、 单链表 B、顺序表 C、 双链表 D、单循环链表11、链表不具有的特点是（ A ）。、可随机访问任一元素 、插入删除不需要移动元素、不必事先估计存储空间 、所需空间与线性表长度成正比12、在一个有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂性为( B ) 。A、O(1)  B、O(n) C、O(n2) D、O(log2n)13、在一个单链表HL中，若要向表头插入一个自由指针p指向的结点，则执行（ D ）。A、 HL=p;p->next=HL; B、 p->

14、next=HL; HL=p;C、 p->next=HL; p=HL; D、 p->next=HL->next;HL->next=p;14、在一个单链表HL中，若要在指针q所指结点的后面插入一个自由指针p所指向的结点，则执行（ D ）。A 、q->next=p->next;p->next=q; B、 p->next=q->next;q=p;C 、q->next=p->next;p->next=p D、 p->next=q->next;q->next=p;15、在一个单链表HL中，若要删除由指针q所指向结点的

15、后继结点，则执行（ D ）。A、 p=q->next;p->next=q->next; B、 p=q->next;q->next=p;C、 p=q->next;p->next=q; D、 q->next=q->next->next;16、给定有n个元素的向量，建立一个有序的单链表的时间复杂度为（ C ）。A、O（1） B、O（n） C、O(n2) D、O(nlog2n)17、不带头结点的单链表first为空的判定条件是（ A ）。A、first=NULL B、first->next=NULL C、first->next=f

16、irst D、first!=NULL18、在非空的循环双链表中q所指的结点前插入一个由p所指结点的过程依次为：p->next=q; p->prior=q->prior; q->prior=p;和（ C ）。A、q->next=p 、q->prior->next=p 、p->prior->next=p 、p->next->prior=p19、线性表的链式存储结构与顺序存储结构相比优点是( D )。A、所有的操作算法实现简单 B、便于随机存储C、不便于插入与删除 D、便于利用零散的存储空间20、在双向链表存储结构中,删除P所指向的结

17、点时须修改指针( A )。A、P->next->prior=P->prior P->prior->next=P->nextB、P->next=P->next->next P->next->prior=PC、P->prior->next=P P->prior=P->prior->priorD、P->prior=P->next->next P->next=P->prior->prior21、向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（B

18、）个元素。A、8 B、63.5 C、63 D、722、在一个长度为n的顺序存储的线性表中，向第i个元素(1in+1)之前插入一个新元素时，需要从年向前依次移（B ）个元素。 A、n-i B、n-i+1 C、n-i-1 D、i二、填空题1、带头结点的单链表H为空的条件是( H->next=NULL )。2、非空单循环链表L中*p是尾结点的条件是( p->next=L )。3、在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s->next=( p->next );和p->next=( f )的操作。4、在一个单链表中p所指结点之前插入一个由指针s所指结点，

19、可执行以下操作：s->next=( p->next );p->next=s;t=p->data;p->data=( s->dada );s->data=( t );5在顺序表中做插入操作时首先检查( 插入位置是否合理 )。6、顺序表、链表分别通过( 存储的相对位置 )、( 指针)体现元素的逻辑关系。7、线性链表中指针的作用是(表示逻辑关系)。8、在顺序表中，插入或者删除一个元素，需要平均移动(一半 )个元素，具体移动的元素个数与(插入与删除的位置有关)有关。9、顺序表中逻辑上相邻的元素的物理位置(一定)紧邻。单链表中逻辑上相邻的元素的物理位置(不一定

20、)紧邻。10、在单链表中，除了首元结点外，任一结点的存储位置由(前趋结点的指针域 )指示。11、有一个单链表（不同结点的data域可能相等），其头指针为head,编写一算法计算数据域为x的结点的个数，请填空。 int count(LinkList head ,ElemType x) Node *p; int n=0; ( p=head->next ); While (p!=NULL) if( (p->data=x) ) n+; ( p=p->next ); return n;12、单链表的逆置，请填空void insert(LikList L)Node *p,*q,*r; p

21、=head; ( q=p->next或q=head->next ); while(q!=NULL) r=q->next; ( q->next=p ); p=q; q=r; head->next=NULL;head=p; 三、判断题1、双循环链表中，任一结点的后继指针均指向其逻辑后继。 (F)2、线性表的逻辑顺序与存储顺序总是一致的。(F)3、顺序存储的线性表可以按序号随机存取。(T)4、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 (F)5、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是

22、属于同一数据对象。(T)6、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(F)7、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。(T)8、线性表的链式存储结构优于顺序存储结构。(F)9、在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。(T)10、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。(T)11、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(F)四、操作题1、下面算法调用方式为unknown（rear）；说明该算法的功能，若输入数据为ABCDE回车，

23、画出该算法所得到的存储结构。void unknown(LinkList &rear ) LinkList head，s； DataType ch； rear=head=(ListNode *)malloc(sizeof(ListNode)； head->next=head； printf("输入数据以回车键结束！n")； while(ch=getchar()!='n') s=(LNode *)malloc(sizeof(LNode)； s->data=ch； s->next=rear->next； rear->next=

24、s； rear=rear->next； rear->next=head->next；free（head）； EDCBA参考答案： rear2、下面算法调用方式为Unknown（root）；说明该算法的功能，若输入数据为AB#CD#EF#回车，画出该算法所得到的存储结构。 void Unknown(BiTree &T) char ch； if（ch=getchar（）='#'） T=NULL； elseT=(BiTree)malloc(sizeof(BiTNode)；T->data=ch； Unknown(T->lchild)； Unknow

25、n(T->rchild)； 参考答案: F E D C B A root 3、已知线性链表元素为字符（A，B，C，D，E，F），说明下面算法的功能，并画出该算法处理后所得到的存储结构。void Unknown(LinkList &head)/head为链表的表头指针 LinkList p，s； p=head->next；while(p->next) s=p->next； if（s->data%2=1）p=p->next；else p->next=s->next; free（s）； /end of while 参考答案:将单链表中ASCII

26、码为偶数的结点删除。4、设单链表的结点的结构为ListNode=(data,link)，阅读下面的函数，指出它所实现的功能是什么。 Int unknown(ListNode *Ha) Int n=0; ListNode *p=Ha->link; While(p) n+; p=p->next; Return (n);参考答案:计算单链表的长度或计算单链表的结点的个数。5、假定p1和p2是两个单链表的表头指针，用来表示两个集合，单键表中的结点包括值域data和指向后继的结点的指针域link，试根据下面的算法指出算法的功能。 int SS(ListNode *p1,ListNode *p

27、2) ListNode r; while(p2!=NULL) r=p1; while(r!=NULL) if(p2->data=r->data) break; r=r->link;if(r=NULL) return 0;P2=p2->link;return 1;参考答案:判断P2单链表所代表的集合是否为P1单链表所代表的集合的子集，若是则返回1，否则返回0。五、算法题、已知两个单向链表A=(a，b，c)；B=(d，e，f)，设计算法void MergeList（LinkList &A，LinkList B），实现将两个链表合并为一个单向链表A=(d，e，f，c，

28、b，a)，其中A，B为两个链表的表头指针，小写字母为表中元素。void merger(LinkList *A ,LinkList B)参考答案:void MergrList(LIstList &A,LinkList B) for (R=B;R->next;R=R->next); P=A->nextwhile(P) S=P;P=P->next; S->next=R->next; R->next=S; A=B;、假定在一个带头结点的单链表L中所有结点的值按递增顺序排列，试写下面的函数，功能是删除表L跌所有的值大于等于min，同时小于等于max的结点

29、。 单链表的结构定义如下：void rangeDelete(ListNode *L,ElemType min,ElemType max)参考答案： void rangeDelete(ListNode *L,ElemType min,ElemType max) listNode *q=L,*p=L->next; while(p!=NULL) if(p->data>=min&&p->data<=max) q->next=p->next;free(p);p=q->next;else q=p;p=p->next;3、线性顺序表及链表

30、就地逆置算法.int revSqList(SqList *L) int revLinkList(LinkList L)参考答案:int revSqList(SqList *L) int i; ElemType temp; for(i=0;i<L->length/2;i+) temp=L->elemi; L->elemi=L->elemL->length-1-i; L->elemL->length-1-i=temp; return OK;int revLinkList(LinkList L) LinkList P,Q; P=L->next;

31、if(L->next&&P->next) Q=P->next; P->next=NULL; while (Q) P=Q; Q=Q->next; P->next=L->next; L->next=P; return OK;4、设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递增有序的单链表C，并要求辅助空间为O(1)。LinkList MergeList_L(LinkList La,LinkList Lb) 参考答案: LinkList MergeList_L(LinkList La,LinkList

32、 Lb) LinkList Lc,pa,pb,pc; pa=La->next; pb=Lb->next; Lc=pc=La; while(pa&&pb) if (pa->data<=pb->data)pc->next=pa;pc=pa;pa=pa->next;else pc->next=pb;pc=pb;pb=pb->next; pc->next=pa?pa:pb; free(Lb); return La;5、已知一个的链表A，表中元素为整数，设计算法把表中的所有的负整数排列在所有非负整数之后。 void Divide

33、（LinkList *A）参考答案: void Divide（LinkList *A） P=A->next;q=A; while(p) if(p->data>=0) q->next=p->next; p->next=A->next; A->next=p; P=q->next;else q=p;p=p->next;第三章 栈与队列一、选择题1、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列(C)。A、 1，3，2，4 B、2，3，4，1 C、 4，3，1，2 D、3，4，2，12、将一个递归算法改为对应的非递归

34、算法时，通常需要使用（ A ）。A、 栈 B、 队列 C、 循环队列 D、优先队列3、若用数组S1.n作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（ C ）。A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/24、 在一个具有n个单元的顺序栈中，假设栈底是存储地址的低端，现在我们以top 作为栈顶指针，则作退栈操作时，top的变化是( A )。A、top =top -1 B、top = top +

35、1 C、top 不变  D、top不确定5、 链栈和顺序栈相比较，有一个明显的特点是( A )。A、链栈通常不会出现栈满的情况B、链栈通常不会出现栈空的情况C、链栈的插入操作更加方便D、链栈的删除操作更加方便。6、 在一个链队中，假设f和r分别为队首和队尾指针，删除一个结点的运算是( C )。A、r = f >nextB、r = r >nextC、f = f >next D、f = r >next7、 向一个栈顶指针为top的链栈中插入一个s 所指结点时，其操作步骤是( B )。A、top >next = sB、s >next = top

36、 ; top = s;C、s >next =top >next; top >next = s;D、s >next =top ; top = top >next8、栈的插入与删除操作在 （ A ） 进行。A、 栈顶 B 、栈底 C、 任意位置 D、 指定位置9、当利用大小为N的数组顺序存储一个队列时，该队列的最大长度为 （ B ）。A、 N-2 B 、N-1 C、 N D、 N+110、假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空指针的条件为（D ）。A、f+1=r B、 r+1=f C、 f=0 D、 f=r11、在系统实现递归调用时需利用递归工作记录

37、保存（ C ），当递归调用结束时通过它将控制转到上层调用程序。A、调用地址 B、递归入口 C、返回地址 D、递归出口12、设栈的输入序列是1,2,3,4n若输出序列的第一个元素是n,则第i个输出元素( B)。A、不确定 B、n-i+1 C、i D、n-i二、填空题1、已知顺序存储的循环队列中，front，rear分别为队头、队尾指针，MAX为队列中存储单元的最大个数，若当队列中仅有一个空闲单元时视为队满，则队满条件为(rear+1)%MAX=front )；一般情况下，队列中元素个数可表示为( (rear-front+MAX)%MAX )。2、已知元素入栈先后为ABCDE，若C为第一个出栈元素

38、，则下一个出栈的元素可能是( B 、D 、 E )。3、已知仅设尾指针的单循环链表rear（指针域为next）表示队列，链表前端为队头，则结点*s入队的语句依次为( s->next=rear->next )；( rear->next=s )；rear=rear->next；4、已知仅设尾指针rear的无头结点的单循环链表（指针域为next）表示栈，链表前端为栈顶，则结点*new进栈的语句依次为(new->next=rear->next )；( rear->next=new )；(rear=new);5、 在对栈的操作中，其插入和删除都是在栈的( 同一端

39、 )进行的，所以导致后进栈的元素必定先被删除，也就是说，栈的修改是按照( 后进先出 )的原则进行的，所以栈又称为( LIFO )表。 6、 在队列的操作中，其插入和删除工作是在表的两端进行的，它允许在表的一端进行插入，一端进行删除，则允许插入的一端称为(队尾 )，允许删除的一端称为( 队首 )，先进入队列的成员必定先离开队列，所以队列又称为( FIFO )表。 7、向一个栈顶找针为HS的链栈中插入一个S所指的结点时，则执行( S->next=HS;HS=S； )。8、在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为( 0 )，当对队列进行

40、插入和删除的操作后，如果头指针和尾指针相等时，队列为( 空 )。9、 向栈中压入元素的操作是(压栈 )。对栈进行出栈时的操作是( 出栈 )。10、在具有n个存储单元的队列中，队满时队中共有( n-1 )个元素。11、假设有一个顺序栈A，其中元素a1,a2,a3,a4,a5,a6依次进栈，如果已知六个元素出栈的顺序是a2,a3,a4,a6,a5,a1,则此栈容量至少应该为( 3 )。12、 线性表、栈和队列都是( 线性结构 )结构，可以在线性表的( 任意 )位置上插入和删除。13、判断单链表是否对称，对称返回1，否则返回0，请填空。 int xyz(LinkList L) Node *p,*q;

41、 int n1,n,i,x; Stack s; P=L->next; q=p; n=0; while(q!=NULL) n+; q=q->next;n1=( n/2 ); for(i=1;i<=n1;i+) push(s,p->data); ( p=p->next );if( (n%2!=0) ) p=p->next; while(p!=NULL) pop(s,x); if (p->data!=x) break; ( p=p->next );if ( p=NULL 或!p ) return 1; else return 0;三、判断题1、栈与队列

42、都是限制存取点的表，只是它们的存取特征不一样。(T)2、在链队列中，即使不设置尾指针也能进行入队操作。(T)3、递归调用算法与相同的功能的非递归算法相比，主要问题在于重复计算太多，而且本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。(T)4、链式栈与顺序栈的相比，一个明显的优点是通常不会出现栈满的情况。(T)四、操作题1、写出下列程序的运行结果。 main()Stack S; char x,y; S.InitStack(); X=c;y=k; S.Push(x);S.Push(a);S.Push(y); S.Pop(S,x);S.Push(t);S.Push(s); w

43、hile(!S.IsEmpty() S.Pop(S,x); printf(“%c”,x);printf(“%c”,y);参考答案：stack2、请写出下列算法的功能。 Void unknown(Queue &Q) Stack S; int d; S.InitStack(); while(!Q.IsEmpty()Q.DeQueue(d);S.Push(d);while(!S.IsEmpty()S.Pop(d);Q.EnQueue(d);参考答案：利用栈，将队列中的元素逆置。五、算法题1、请分别写出在循环队列上进行插入与删除操作的算法。 循环队列的结构定义如下：Struct CyclicQ

44、ueueElemType elemM /M为已定义过的整型常量，表示队列的长度 Int rear,front;/rear指向队尾元素的后一个位置，front指向队头元素 Int tag;/当front=rear且tag=0时，队列空。当front=rear且tag=1，队列满。;Bool EnCQueue(CyclicQueue *Q ,ElemType x)Bool DelCQueue(CyclicQueue *Q,ElemType x)参考答案：Bool EnCQueue(CyclicQueue *Q ,ElemType x)if(Q->rear=Q->front&&a

45、mp;Q->tag=1) return false; Q->elemQ->rear=x; Q->rear=(Q->reat+1)%M; if(Q->rear=Q.front) Q.tag=1; Return true;Bool DelCQueue(CyclicQueue *Q,ElemType x)if(Q->front=Q->rear&&Q->tag=0) return false; x=Q->elemQ->front; Q->front=(Q->front+1)%M; if(Q->front

46、=Q->rear) Q.tag=0; return true;2、 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是回文，“ashgash”不是回文。是写一个算法判断读入的一个以为结束符的字符序列是否为回文。参考答案：int Ishuiwen(char *s) SqStack T; int i,l; char c; InitStack(T); l=(int)strlen(s); for(i=0;i<l/2;i+) Push(T,si); while(!StackEmpty(T) Pop(T,&c); if(c!=sl-i) re

47、turn ERROR; i-; return OK; 第五章 数组与广义表一、选择题1、设一个广义表的A=（a），其表尾为（ C ）。A、a B、( ) C、( ) D、(a)2、设有一个N*N的对称矩阵A，将其下三角部分存入一个一维数组B中，A00存入B0中，那么第i行的对角元素Aii存入于B中的（ ）处。A、（i+3）*i/2 B、(i+1)*i/2 C、(2N-i+1)*i/2 D、(2N-i-1)*i/23、广义表( (A , B, E, F , G)的表尾是( B )。A、(B, E , F, G) B、( )C、（A，B， E，F，G) D、不存在4、 广义表（( ) ，( ）,

48、(a , b, c) , (e , d)）的表头是( C )，表尾是( D )。A、(e , d )B、( ( ) ) C、( ( ) , ( ) ) D、（a , b , c ）,( e , d)）5、 对广义表( (a),(b) )进行下面的操作head(head()后的结果是( A )。A、a B、(a) C、( ) D、不确定6、 广义表(A,B,E,F,G)的表尾是( A )。A、(B, E , F, G) B、( ) C、（A，B， E，F，G) D、（G）7、设有一个二维数Amn,假设A00存放位置在644(10),A22存放位置在676(10),每个元素占一个空间，则A45在（

49、C）位置，(10)表明用10进数表示。A、692(10) B、626(10) C、709(10) D、724(10)8. 二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（D）个字节；M的第8列和第5行共占（A）个字节；若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的（ B）元素的起始地址一致。（1） A、90 B、180 C、240 D、540（2） A、108 B、114 C、54 D、60（3） A、M85 B、M310 C、M58 D、M099. 二维数组M的元素是4个字符（每个字符占一

50、个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素（B）的起始地址相同。 A、m24 B、M34 C、M35 D、M4410. 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（C），若该数组按行存放时，元素A85的起始地址是（C），若该数组按列存放时，元素A85的起始地址是（B）。（1） A、80 B、100 C、240 D、270（2） A、SA+141 B、SA+144 C、SA+222 D、SA+225（3） A、SA+14

51、1 B、SA+180 C、SA+222 D、SA+225二、填空题1、设广义表A=(a,(b),c),（(d)）,(e,f)，则表长为( 3 )；表头，表尾运算分别用H（A），T（A）表示，则表示原子e的表达式为( H(H(T(T(A) )。2、一个向量的第一个元素存储地址是100，每个元素的长度为2，则第五个元素的地址(108)。3、广义表中元素既可以是单原子，也可以是(广义表)广义表两个基本操作是(取表头)、(取表尾)。4、若设一个N*N的矩阵A的开始存储地址LOC（0，0）及元素所占的存储单元数d已知，按行优先存储时任意一个矩阵元素aij的存储地址为（ LOG(0,0)+(i*n+j)*d ）。5、广义表的深度定义为广义表的括号的（ 重数 ）。6、一棵树的广义表的表示