HNSY数据结构习题集

1、注：答案可能有误， 仅供参考 绪论一、选择题：1、下列算法的时间复杂度是（ B ） for(i=0;i<n;i+ +) ci=i； AO（1） BO（n） CO（log2n） DO（nlog2n）2、数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（ D ） A索引存储方法 B顺序存储方法 C链式存储方法 D散列存储方法 3、以下哪一个术语与数据的存储结构无关？（ D ）。A.顺序表 B.链表C.散列表 D.队列4、算法在发生非法操作时可以做出处理的特性称为（ C ）。A正确性B易读性C健壮性D高效性5、逻辑结构是指数据元素的（ A ）。A关联方式 B

2、存储方式C结构D数据项6、研究数据结构就是研究（ D ）。A数据的逻辑结构B数据的存储结构C数据的逻辑结构和存储结构D数据的逻辑结构、存储结构及其数据的运算7、从逻辑上可以把数据结构分为（ C ）。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构8、以下有关数据的叙述中错误的是（ B ）。A计算机能够处理的数据包括整数、实数、字符、声音、图像等B数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式C数据存储结构的实现依赖于计算机语言D数据的运算是定义在数据的逻辑结构上的9、数据的基本单位是（ B ）。A.数据结构 B.数据元素C.数据项

3、D.文件10、下列算法的时间复杂度是（ C ） for(i=0;i<m;i+ +) for(j=0;j<n;j+ +) aij=i*j； AO（m2） BO（n2） CO（m×n） DO（m+n）11、算法分析的两个主要方面是（ D ）。A正确性和简明性 B数据复杂性和程序复杂性C可读性和可维护性D时间复杂性和空间复杂性12、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ B ）。A存储结构 B逻辑结构 C算法 D操作13、下列叙述中正确的是( D )。 A一个逻辑数据结构只能有一种存储结构B数据的逻辑结构属于线性结构，存储结构属于非线性结构 C一个逻辑数据结

4、构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率二、填空题：1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（存储结构）和（ 运算 ）。2、( 逻辑 )结构与数据元素本身的内容和形式无关。 3、程序段“for(i=1;i<=n;i+) k+; for(j=1;j<=n;j+) x=x+k;”的时间复杂度为( O(n2) )。4、数据的存储结构（物理结构）可以用（顺序）、（链式）、（索引）及散列存储等四种存储方法表示。5、数据结构是一门研究非数值计算

5、的程序设计问题中计算机的（ 操作对象 ）以及它们之间的（ 关系 ）和运算等的学科。6、数据结构被形式地定义为（D, R），其中D是（ 数据元素 ） 的有限集合，R是D上的（ 关系 ）有限集合。7、数据结构包括数据的（ 逻辑结构 ）、数据的 （存储结构 ）和数据的（ 运算 ） 这三个方面的内容。8、数据结构按逻辑结构可分为两大类，它们分别是 （线性结构 ） 和 （ 非线性结构 ） 。9、线性结构中元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中元素之间存在（多对多）关系。10、在线性结构中，（第一个结点 ）没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结

6、点 （ 没有 ） 后续结点，其余每个结点有且只有1个后续结点。）11、在树形结构中，树根结点没有 （前驱 ）结点，其余每个结点有且只有（ 1 ）个前驱结点；叶子结点没有（ 后续 ）结点，其余每个结点的后续结点数可以任意多个。12、在图形结构中，每个结点的前驱结点数和后续结点数可以（ 任意多个 ） 。13、对于给定的n个元素,可以构造出的逻辑结构有（ 集合，线性表，树，图 ）四种。14、顺序映象的特点是借助元素在存储器中的（ 相对位置 ）来表示数据元素之间的逻辑关系。非顺序映象的特点是借助是指示元素存储地址的（ 指针 ）表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定（ 逻辑结构 ），而

7、算法的实现依赖于采用的（ 存储结构 ）。15、数据类型是一组（ 性质相同 ）的值集合以及定义在这个值集合上的一组操作的总称。16、数据对象是（ 性质相同的）数据元素的集合，是数据的一个子集。三、 判断题：1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （×）2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。 （×）3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 （ ）4、数据的机内表示称为数据的存储结构。 （）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6、数据元素是数据的最小单位。

8、（×）7、基于某种逻辑结构之上的运算，其实现是惟一的。 （×）2 线性表一、 选择题：1、在表长为n的顺序表上做插入运算，平均要移动的结点数为（ B ）。 An Bn/2 Cn/3 Dn/42、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（ A ） AS->next=P->next;P->next=S BP->next=S->next;S->next=P； CP->next=P;P->next=S； DP->next=S;S->next=P；3、在已知头指针的单链表中，要在其尾部插入一新

9、结点，其算法所需的时间复杂度为（ B ） A（1） B（log2n） CO（n） DO（n2） 解析：单就插入运算而言，算法时间复杂度为（1），但要将指针定位到链表末尾，指针移动的时间复杂度为O（n）；4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ C ） A顺序表 B用头指针表示的单循环链表 C用尾指针表示的单循环链表 D单链表 解析：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找

10、时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。5、线性表是（ A ） A一个有限序列，可以为空 B一个有限序列，不能为空 C一个无限序列，可以为空 D一个无限序列，不能为空6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（ B ） AO（n） BO（1） CO（log2n） DO（n2）7、线性表采用链式存储时，结点的地址（ C ） A必须是连续的 B必须是不连续的 C连续与否均可 D必须有相等的间隔8、在单链表中，增加头结点的目的是（ C ） A使单链表至少有一结点 B标志表中首结点位置 C方便运算的实现 D说明单链表是线性表的链式存储实现9、带头结点

11、的单链表head为空的判定条件是（ B ） Ahead = NULL； Bhead - > next = NULL； Chead - > next = head； Dhead ! = NULL；10、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（ B ） A（1） B（n） C（n2） D（log2n）11、下列有关线性表的叙述中，正确的是（ A ） A线性表中的元素之间是线性关系 B线性表中至少有一个元素 C线性表中任何一个元素有且仅有一个直接前趋 D线性表中任何一个元素有且仅有一个直接后继12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是

12、指针域，它指向该结点的（ B ） A直接前趋 B直接后继 C开始结点 D终端结点13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ B ）。An B.2n-1 C.2n D.n-114、链表不具有的特点是（ A ）。A随机访问 B不必事先估计存储空间C插入删除时不需移动元素 D所需的空间与线性表成正比15、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（ B ）。 As->next=p->next;p->next=s; Bq->next=s;s->next=p;Cp->next=s->

13、next;s->next=p; Dp->next=s;s->next=q;16、链表具有的特点是（ C ）。A可随机访问任一元素B插入、删除需要移动元素C不必事先估计存储空间D存储空间是静态分配的17、一个顺序表一旦说明，其中可用空间大小（ B ）A已固定B可以改变C不能固定D动态变化18、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ A ）存储方式最节省时间。A 顺序表B单链表C双向链表D单循环链表19、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素的前驱的条件是（ A ）。AP->next=QBQ->next=PC

14、P=QDP->next=Q->next20、链表不具有的特点是（ A ）。A可随机访问任一元素 B插入、删除不需要移动元素C不必事先估计存储空间 D所需空间与线性表长度成正比21、下面关于线性表的叙述中，错误的是（ B ）。A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作C线性表采用链接存储，不必占用一片连续的存储单元D线性表采用链接存储，便于进行插入和删除操作22、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ A ）。A访问第i个结点（1in）和求第i个结点的直接前趋（2in）B在第i个结点后插入一个新结点（1in）C删除

15、第i个结点（1in）D将n个结点从小到大排序23、在一个单链表中，若删除p指向结点的后继结点，则执行的操作为（ A ）。Aq=p->next;p->next=p->next->next;free(q);Bp=p->next;q=p->next;p=q->next;free(q);Cq=p->next->next;p=p->next;free(q);Dp=p->next->next;q=p->next;free(q);24、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储

16、方式是（D）。A单链表 B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表25、求循环链表中当前结点的后继和前驱的时间复杂度分别是（C）。A O(n)和O(1)BO(1)和O(1)CO(1)和O(n)DO(n)和O(n)26、求单链表中当前结点的后继和前驱的时间复杂度分别是（C）。A O（n）和O（1）BO（1）和O（1）CO（1）和O（n）DO(n)和O（n）27、非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（A）。A rear->next= =headBrear->next->next= =headChead->next= =rea

17、rDhead->next->next= =rear28、从一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动的元素的个数是（A）。An-iBn-i+1Cn-i-1Di29、用链表表示线性表的优点是（ D ）。A 便于随机存取 B花费的存储空间比顺序表少 C数据元素的物理顺序与逻辑顺序相同 D便于插入与删除30、链表不具有的特点是（ B ） 。A 插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比31、采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（ D ）。A n Bn/2 C(n-1)/2 D(n+1)/

18、232、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ C ）。A O(1) BO(n) CO(m) DO(m+n)33、若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( A )。A head=NULL Bhead->next=NULLChead!=NULLDhead->next=head34、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A 单链表 B仅有头指针的单循环链表C双链表 D仅有尾指针的单循环链表二、 填空题：1、在双链表中要删除已知结点*p，其时间复杂度为（O(1)

19、）。2、在仅有尾指针R指示的单循环链表R中，在表尾插入一个结点S的语句序列是（P=R; while(P->next!=NULL) P=P->next; P->next=S; S->next=NULL;）。3、在带头结点的双链表中，指针所指结点是开始结点的条件是（P= =L）。4、在具有n个结点的双链表中做插入、删除运算，平均时间复杂度为（O(1)）。5、在一个长度为n的顺序表中第i个元素（1 i n）之前插入一个元素时，需向后移动（n-i+1）个元素。6、在双循环链表中，若要在指针p所指结点之前插入指针s所指的结点，则需执行下列语句：s->prior=p->

20、prior;p->prior->next=s;( s->next=p; )和p->prior=s;。7、已知指针p指向双向链表中的一个结点（非首结点、非尾结点），则将结点s插入在p结点的直接后继位置的语句是（p->next=s;）s->prior=p；s->next->prior=s；p->next=s;8、已知带表头结点的单链表L，指针p指向L链表中的一个结点（非首结点、非尾结点），则删除结点p的直接后继结点的语句是（q=p->next; p->next=q->next; free(q);）；删除首结点的语句是（q=L-

21、>next; L=L->next; free(q);）。9、在顺序表中插入或删除一个元素，需要平均移动（ 约表中一半 ）元素，具体移动的元素个数与（ 元素所在位置 ）有关。10、在双向循环链表L中，指针P所指向结点为尾结点的条件是（_p->next=head_ _）。11、在带有头结点的单链表中L中，第一个元素结点的指针是（ L->next ）。12、在一个带头节点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=（ p->next->next ）。13、设单链表的结点结构为(data,next)，next为指针域，已知

22、指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句: （ py->next=px->next; px->next=py ）。三、 判断题1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（×）2、顺序存储的线性表可以随机存取。 （）3、线性表采用顺序存储，必须占用一片连续的存储单元。 （）四、 程序设计题数据结构的数据类型定义如下： 顺序存储： typedef struct int *base; int length; sqlist; 链式存储： typedef struct

23、 LinkList int data; struct LinkList *next; Node,*LinkList; 1、已知带头结点的单链表head中的结点是按整数值递增排序的，写一算法将值为x的结点插入到表head中，使head仍然有序。P=head->next;While(p->next!=NULL&&p->data<x) p=p->next;/指针定位p->next=x;x->next=p->next;2、用尾插入法建立带头结点的单链表。LinkList Creat_LinkList2() /tail insert met

24、hodLinkList H=(LinkList)malloc(sizeof(LNode);H->next=NULL;LNode *s,*r=H;int x;printf("尾插法创建链表，请输入链表中各结点的值，以-1结束："); scanf("%d",&x);while(x!=-1)s=(LinkList)malloc(sizeof(LNode);s->data=x;s->next=r->next;r->next=s;r=s;scanf("%d",&x);return H; /教材“数据

25、结构与算法p26”;3、用头插入法建立带头结点的单链表。LinkList Creat_LinkList1() /head insert methodLinkList H=(LinkList)malloc(sizeof(LNode);H->next=NULL;LNode *s;int x;printf("头插法创建链表，请输入链表中各结点的值，以-1结束："); scanf("%d",&x);while(x!=-1)s=(LinkList)malloc(sizeof(LNode);s->data=x;s->next=H->n

26、ext;H->next=s;scanf("%d",&x);return H;/教材“数据结构与算法p25”;4、对给定的单链表L，编写一个删除L中值为x的结点的直接前趋结点算法。/算法思路：先判断L中是否存在值为x的结点，若不存在，返回错误（-1）；若存在，用一指针p定位到值为x的第一结点,用另一个指针q定位到值为x的第一结点的前驱结点，然后实施删除操作；重点语句为：p=L->next;/p指向第一个结点whili(p->data!=x&&p->next!=NULL) p=p->next;if(p= =NULL) rut

27、urn error;/不存在else p=L->next; while(p->next->next->data!=x) p=p->next; q=p->next; p->next=p->next->next; free(q);5、用顺序存储结构实现线性表的就地逆置算法，即将（a1,a2, ai,an）逆置为（an,ai,a2,a1）;注：重点语句： for(i=0;i<sqlist.length/2;i+) sqlist.baseißàsqlist.basesqlist.length-i;/第i个元素和第lengt

28、h-i元素交换存储6、用链式存储结构实现线性表的就地逆置算法(带头结点的单链表)，即将（a1,a2, ai,an）逆置为（an,ai,a2,a1）;参考答案：void Reverse(LinkList H)LNode *p,*q;p=H->next;H->next=NULL;while(p)q=p;p=p->next;q->next=H->next;H->next=q; 注：该代码在教材 数据结构与算法p297、阅读算法并根据输入数据画出链表。linklist createlistr1( ) char ch; linklist head=(listnode*

29、)malloc(sizeof(listnode); listnode *p，*r； r=head; while(ch=getchar( )!=n) p=(listnode*)malloc(sizeof(listnode); while (p) p=(listnode*)malloc(sizeof(listnode); p>data=ch; r>next=p; r=p; r>next=NULL; return(head);输入数据为：text8text head（注：尾插法创建链表）8、阅读下面的程序，说明程序的具体功能。typedef int elementypetypede

30、f struct node elemtype data;strunct node *next;linklist;void function( linklist *head, elemtype x ) linklist *q, *p;q=head;p=q-next;while (p !=NULL) && (p->data != x ) q=p; p=p->next; if (q=NULL) printf (“there is no this node :n”);else q ->next =p ->next ; free (p); 该程序的功能是：在带头结

31、点的单链表中，删除单链表中值为z的数据元素。9、从带头结点的链表L中删除重复的元素,并使剩余元素间的相应次序保持不变.要求本算法的空间复杂记度为O(1)。void ListDelete_LSameNode(LinkList &L)LinkList p,q,prev,curr;p=L->next;while(p)prev=p;curr=prev->next;while(curr) if(curr->data=p->data) prev->next=curr->next;free(curr);curr=prev->next;else prev=cu

32、rr;curr=curr->next;p=p->next;3 栈和队列一、 选择题：1、循环队列是空队列的条件是（ A ） AQ . rear = = Q . front B（Q . rear + 1）%maxsize = = Q .front CQ . rear = = 0 DQ. front = = 02、链栈与顺序栈相比，比较明显的优点是（ A ） A通常不会出现栈满的情况 B通常不会出现栈空的情况C插入操作更加方便 D删除操作更加方便分析不管是链栈还是顺序栈，其插入、删除操作都是在栈顶进行的，都比较方便，所以不可能选C)，D)。对链栈来讲，当栈中没有元素而又要执行出栈操作时

33、，就会出现栈空现象，故B)也是不正确的。只要内存足够大，链栈上就不会出现栈满现象。而对顺序栈来讲，由于其大小是事先确定好的，因此可能会出现栈满现象。所以A)是正确的。3、若一个栈的输入序列是，n，输出序列的第一个元素是，则第个输出元素是（ B ） An - i Bn i + 1 Ci D不确定4、栈与一般线性表的区别主要在（ D ） A元素个数 B元素类型 C逻辑结构 D插入、删除元素的位置5、一个链栈的栈顶指针是top，则执行出栈操作时（栈非空），用x保存被删除结点，则执行（ B ） Ax = top; top = top ànext； Bx = topàdata； Ct

34、op = top ànext;x = top à data； Dx = topà data;top = topà next；分析栈顶元素出栈后，应该从栈底位置即第一个结点开始重新定位，执行语句是：q=base ; while(qànext!=top) q=qànext; free(top); top=q;6、对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（ C ） A1，2，3 B3，2，1 C3，1，2 D2，1，3分析 每个元素进栈后立即出栈，结果是答案A；三个元素全部进栈后再出栈，得到答案B；1和2进栈后出栈，

35、然后3入栈后出栈，得到答案D；而C答案不可能的原因是：3出栈后，说明1、2还在栈中，1出栈后2还在栈中，说明2的入栈次序在1之前。7、在链接队列执行入队操作（D ） A需判别队是否空 B需判别队是否满 C限制在链表头p进行 D限制在链表尾p进行8、以下不属于栈的基本运算是（ B ）。 A删除栈顶元素 B删除栈底元素C判断栈是否为空 D将栈置为空栈9、一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）。Ae,d,c,b,a Bd,e,c,b,a Cd,c,e,a,b Da,b,c,d,e10、设计一个判别表达式中左、右括号是否配对出现的算法，采用（ B ）数据结构最佳。A线

36、性表的顺序存储结构 B栈 C队列 D线性表的链式存储结构11、循环队列的特点之一是不会产生（ D ）。 A上溢出 B下溢出 C队满 D假溢出12、设数组Datan作为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句为（ C ）。Arear=(rear+1)%(n+1) Bfront=(front+1)% n Crear=(rear+1)% n Dfront=(front+1)%(n+1)13、栈是限定在（ C ）处进行插入或删除操作的线性表。A端点 B栈底 C栈顶 D中间14、容量是10的循环队列的队头位置qàfront为2，队列中的数据元素个数为

37、5，则队的第一个数据元素的位置是（ B ）A2B7C1D0分析 (front-rear+10)%10=5,并且front和rear的取值范围均是09，所以只有（7-2+10）%10=5。 15、循环队列的出队操作是（ A ）Aqàfront=(qàfront+1)%maxsize; Bqàfront=qàfront+1;Cqàrear=(qàrear+1)%maxsize; Dqàrear=qàrear+1;16、当循环队列q是满队列时，存放队列元素的数组data有n个元素，则data中存放（ B ）个数据元素。A

38、nB. n-1C. n-2D.0分析 容量为maxsize的循环队列最多只能存放maxsize-1个数据元素，当队列满时，队尾指针再往前走一步就追上队头指针，即(rear+1)% maxsize=front；17、以下哪一个不是队列的基本运算（ B ）。A从队尾插入一个新元素 B从队列中删除第i个元素C判断一个队列是否为空 D读取队头元素的值18、在一个链队列中，若f , r分别为队首、队尾指针，则插入s所指结点的操作为（ B ）。Afànext=s;f=sBrànext=s;r=s;Csànext=r;r=s; Dsànext=f;f=s19、循环队列

39、的入队操作应为（ C ）。Aqàrear=qàrear+1;qàdataqàrear=x;Bqàdataqàrear+=x;Cqàrear=(qàrear+1)%maxsize; qàdataqàrear=x;Dqàdataqàrear=x;q->rear=(qàrear+1)%maxsize;20、栈和队列都是（ A ）。A限制存取点的线性结构 B限制存取点的非线性结构C顺序存储的线性结构 D链式存储的线性结构21、实现递归调用属于（ B ）的应用。A队列

40、B栈 C 数组 D树22、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（D）。As.elemtop=e；s.top=s.top+1；Bs.elemtop+1=e；s.top=s.top+1； Cs.top=s.top+1；s.elemtop+1=e；Ds.top=s.top+1；s.elemtop=e； 23、循环队列sq中，用数组elem0··25存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数

41、为（C）。A 8 B16 C17 D1824、链式栈与顺序栈相比，一个比较明显的优点是（ B ）。A 插入操作更加方便 B通常不会出现栈满的情况C不会出现栈空的情况 D删除操作更加方便25、若已知一个栈的入栈序列是1,2,3,4n，其输出序列为p1,p2,p3,pn，若p1= =n,则pi为（ C ）。A i Bn= =i Cn-i+1 D不确定26、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( D )。A 2，4，3，1，5，6 B3，2，4，1，6，5C4，3，2，1，5，6 D2，3，5，1，6，427、对于栈操作数据的原则是（ B ）。A 先

42、进先出 B后进先出 C后进后出 D不分顺序28、栈和队列的共同点是（ C ）。A 都是先进先出 B都是先进后出 C只允许在端点处插入和删除元素 D没有共同点29、一个队列的入队序列是1，2，3，4，则队列的输出序列是（ B ）。A 4,3,2,1 B1,2,3,4 C1,4,3,2 D3,2,4,130、引起循环队列队头位置发生变化的操作是( A )。A 出队B入队 C取队头元素 D取队尾元素31、设以数组Am存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。A(rear-front+m)%m B）rear-front+1C）(front-rear+

43、m)%m D）(rear-front)%m二、 填空题： 1、循环队列用数组datam存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中元素的个数是（(rear-front+maxsize）%maxsize）。2、栈顶的位置是随着（入栈和出栈）操作而变化的。3、假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（bceda）。4、队列的队尾位置随着（入队列操作变化）而变化。5、在（链队列为空）的情况下，链队列的出队操作需要修改尾指针。 分析：Q.rear=h;6、从栈顶指针为top的链栈中删除一个结点

44、，并将被删除的结点的值保存在x中，其操作步骤为（x=top->data）。7、用数组Am来存放循环队列q的元素，且它的头、尾指针分别为front和rear，队列满足条件(q.rear+1)%m=q.front,则队列中当前的元素个数为（0）。8、顺序栈s存储在数组s->datamax中，对s进行出栈操作，执行的语句序列是（sàtop-）。9、以下运算实现在循环队列中的初始化操作void initqueue(seqqueue *q)q->front=0;( qàbase=(qelemtype *)malloc(maxsize*sizeof(qelemtype

45、); qàrear=0;);10、对于栈操作数据的原则是（ 后进先出 ）。11、一个链栈的栈顶指针用top表示，当p所指向的结点进栈时，执行的操作为（ p->next=top;top=p; ）。12、一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为（ top=top->next ）。13、设以数组Am存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ (rear-front+m)%m ）。14、若已知一个栈的入栈序列是1,2,3,4n，其输出序列为p1,p2,p3,pn，若p1= =n,则pi为（ n-i+1 ）。 15、（

46、 队列 ）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。16、用P表示入栈操作，D表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的P和D的操作串为（_ PDPPDPDD _） 。17、在具有n个单元的循环队列中，队满共有（ n-1 ）个元素。18、循环队列的引入，目的是为了克服（ 假溢出 ）。三、 判断题：1、循环队列中无上溢现象。 （×）2、循环队列只有下溢，没有上溢。 （×）3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢”。 （×）4、顺序队列和循环队列的队满和队空的条件是一样的。 （&#

47、215;）5、为解决队列“假满”问题，可以采用循环队列实现队列存储。 （）6、队列是后进先出的线性表。 （×）7、栈是后进先出表。 （）四、 应用题：1、设有一个栈，元素进栈的次序为A，B，C，D，E，写出下列出栈序列的操作序列。（1）CBADE（2）ACBED，其中I为进栈操作，O为出栈操作。参考答案：（1）IIIOOOIOIO (2)IOIIOOIIOO2、如果编号为1、2、3的三辆列车顺序进入一个栈式结构的站台，那么可能得到的三辆列车出站序列有哪些？不可能出现的序列是什么？参考答案：可能得到的三辆列车出站序列有1，2，3； 1，3，2；2，1，3；2，1，3；2，3，1；其他3

48、个数字的另外1个排列不可能出现，即3，1，2。五、 程序设计题：1、写出循环队列入队操作的函数。请参考教材“数据结构与算法p61”;4 串和数组一、单选题 1下列那些为空串（ B ） AS=“ ” BS=“” CS=“” DS=“” 2S1=“ABCD”，S2=“CD”则S2在S3中的位置是（ C ） A1 B2 C3 D4 3假设S=“abcaabcaaabca”，T=“bca”，Index (S,T,3) 的结果是（ B ） A 2 B6 C11 D0 4在串中，对于SubString(&Sub,S,pos,len)基本操作，pos和len的约束条件是（C ） A0<pos&

49、lt;StrLength(S)+1且1<=len<=StrLength(S)-pos+1 B0<pos<StrLength(S)+1且0<=len<=StrLength(S)-pos-1 C1<=pos<=StrLength(S) 且0<=len<=StrLength(S)-pos+1 D1<=pos<=StrLength(S) 且1<=len<=StrLength(S)-pos-1 5串是一种特殊的线性表，其特殊性体现在( B )。 A可以顺序存储 B. 数据元素是一个字符 C可以链接存储 D. 数据元素可以

50、是多个字符 6串是( D )。 A少于一个字母的序列 B. 任意个字母的序列 C不少于一个字符的序列 D. 有限个字符的序列 7 串的长度是( C )。 A串中不同字母的个数 B. 串中不同字符的个数 C串中所含的字符的个数 D. 串中所含字符的个数，且大于0 8 设有S1=ABCDEFG，S2=PQRST，函数con(x，y)返回x和y串的连接串，subs(i，j)返回串S的从序号I的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2)，subs(S1，len(S2)，2)的结果是( D )。 ABCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 9 若某串的长度小于一个常数，则采用( C )存储方式最为节省空间。 A链式 B. 堆结构 C. 顺序表 二、填空题： 1串是