《数据结构》习题集

《《数据结构》习题集》由会员分享，可在线阅读，更多相关《《数据结构》习题集（28页珍藏版）》请在装配图网上搜索。

1、真诚为您提供优质参考资料，若有不当之处，请指正。 1 绪论 一、选择题： 1、下列算法的时间复杂度是（ ） for(i=0;i

2、结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链式存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储

3、结点信息外，还建立附加的索引表来标识结点的XXX。散列存储方法：就是根据结点的关键字直接计算出该结点的存储XXX。数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元XXX可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。 3、以下哪一个术语与数据的存储结构无关？（ ）。 A.顺序表 B.链表 C.散列表 D.队列 4、

4、算法在发生非法操作时可以做出处理的特性称为（ ）。 A．正确性 B．易读性 C．健壮性 D．高效性 5、逻辑结构是指数据元素的（ ）。 A．关联方式 B．存储方式 C．结构 D．数据项 6、研究数据结构就是研究（ ）。 A．数据的逻辑结构 B．数据的存储结构 C．数据的逻辑结构和存储结构 D．数据的逻辑结构、存储结构及其数据的运算 7、从逻辑上可以把数据结构分为（ ）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部

5、结构 8、以下有关数据的叙述中错误的是（ ）。 A．计算机能够处理的数据包括整数、实数、字符、声音、图像等 B．数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式 C．数据存储结构的实现依赖于计算机语言 D．数据的运算是定义在数据的逻辑结构上的 9、数据的基本单位是（ ）。 A.数据结构 B.数据元素 C.数据项 D.文件 10、下列算法的时间复杂度是（ ） for(i=0;i

6、;j+ +) a[i][j]=i*j； A．O（m2） B．O（n2） C．O（mn） D．O（m+n） 11、算法分析的两个主要方面是（ ）。 A．正确性和简明性 B．数据复杂性和程序复杂性 C．可读性和可维护性 D．时间复杂性和空间复杂性 二、填空题： 1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（　 　　）和（ ）。 2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（　　　　　　　）无关，是独立于计算机的。 3、(

7、 )结构与数据元素本身的内容和形式无关。 4、程序段“for(i=1;i<=n;i++) {k++; for(j=1;j<=n;j++) x=x+k;}”的时间复杂度为( )。 5、数据的存储结构（物理结构）可以用（ ）、（ ）、（ ）及散列存储等四种存储方法表示。 三、 判断题： 1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （ ） 2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。 （ 　） 3、线性表的链接

8、存储，表中元素的逻辑顺序与物理顺序一定相同。 （ ） 4、数据的机内表示称为数据的存储结构。 （ ） 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（ ） 6、数据元素是数据的最小单位。 （ ） 7、基于某种逻辑结构之上的运算，其实现是惟一的。 （ ） 参考答案（绪论） 一、选择题 1 2 3 4

9、 5 6 7 8 9 10 11 B D D C A D C B A C D 二、填空题 1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（存储结构）和（运算）。 2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（　　　　　　　）无关，是独立于计算机的。 3、(逻辑)结构与数据元素本身的内容和形式无关。 4、程序段“for(i=1;i<=n;i++) {k++; for(j=1;j<=n;j++) x=x+k;}”的时间复杂度为(O(n2))。 5、数据的存储结构（物理结构）可以用

10、（顺序）、（链式）、（索引）及散列存储等四种存储方法表示。 三、判断题 1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （） 2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。 （） 3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 （ √） 4、数据的机内表示称为数据的存储结构。 （√） 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（）

11、 6、数据元素是数据的最小单位。 （） 7、基于某种逻辑结构之上的运算，其实现是惟一的。 （） 2 线性表 一、 选择题： 1、在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）。 A．n B．n/2 C．n/3 D．n/4 2、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（ ） A．S->next=P->next;P

12、->next=S B．P->next=S->next;S->next=P； C．P->next=P;P->next=S； D．P->next=S;S->next=P； 3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（ ） A．Ｏ（1） B．Ｏ（log2n） C．O（n） D．O（n2） 解析：单就插入运算而言，算法时间复杂度为Ｏ（1），但要将指针定位到链表末尾，指针移动的时间复杂度为O（n）； 4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ）

13、 A．顺序表 B．用头指针表示的单循环链表 C．用尾指针表示的单循环链表 D．单链表 解析：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 5、线性表是（ ） A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以

14、为空 D．一个无限序列，不能为空 6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（ ） A．O（n） B．O（1） C．O（log2n） D．O（n2） 7、线性表采用链式存储时，结点的XXX（ ） A．必须是连续的 B．必须是不连续的 C．连续与否均可 D．必须有相等的间隔 8、在单链表中，增加头结点的目的是（ ） A．使单链表至少有一结点 B．标志表中首结点位置 C．方便运算的实现 D．说明单链表是线性表的

15、链式存储实现 9、带头结点的单链表head为空的判定条件是（ ） A．head = NULL； B．head - > next = NULL； C．head - > next = head； D．head ! = NULL； 10、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（ ） A．Ｏ（1） B．Ｏ（n） C．Ｏ（n2） D．Ｏ（log2n） 11、下列有关线性表的叙述中，正确的是（ ） A．线性表中的元素之间是线性关系 B．

16、线性表中至少有一个元素 C．线性表中任何一个元素有且仅有一个直接前趋 D．线性表中任何一个元素有且仅有一个直接后继 12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（ ） A．直接前趋 B．直接后继 C．开始结点 D．终端结点 13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 A．n B.2n-1 C.2n D.n-1 14、链表不具有的特点是（ ）。 A．随机访问 　　　　

17、B．不必事先估计存储空间 C．插入删除时不需移动元素 D．所需的空间与线性表成正比 15、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（ ）。 A．s->next=p->next;p->next=s; B．q->next=s;s->next=p; C．p->next=s->next;s->next=p;　 D．p->next=s;s->next=q; 16、链表具有的特点是（ ）。 A．可随机访问任一元素 B．插入、删除需要移动元素 C．不必事先估计存储空间 D．存储空间是静态分配的

18、 17、一个顺序表一旦说明，其中可用空间大小（ ） A．已固定 B．可以改变 C．不能固定 D．动态变化 18、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。 A． 顺序表 B．单链表 C．双向链表 D．单循环链表 19、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素的前驱的条件是（ ）。 A．P->next==Q B．Q->next==P C．P==Q D．P->next==Q->next 20、链表不具有的特点是（ ）。 A．可随机访问任一元素

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

20、除第i个结点（1≤i≤n） D．将n个结点从小到大排序 23、在一个单链表中，若删除p指向结点的后继结点，则执行的操作为（ ）。 A．q=p->next;p->next=p->next->next;free(q); B．p=p->next;q=p->next;p=q->next;free(q); C．q=p->next->next;p=p->next;free(q); D．p=p->next->next;q=p->next;free(q); 二、 填空题： 1、在双链表中要删除已知结点*p，其时间复杂度为（　　　　　）。 2、在仅有尾指针R指示的单循环链表R中，在

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

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

23、 三、 判断题 1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（ ） 2、顺序存储的线性表可以随机存取。 （ ） 3、线性表采用顺序存储，必须占用一片连续的存储单元。 （ ） 四、 程序设计题 数据结构的数据类型定义如下： 顺序存储： typedef struct { int *base; int length; int listsize; }sqlist; 链式存储： typ

24、edef struct LinkList {int data; struct LinkList *next; }Node,*LinkList; 1、已知带头结点的单链表head中的结点是按整数值递增排序的，写一算法将值为x的结点插入到表head中，使head仍然有序。 2、用尾插法建立带头结点的单链表。 3、用头插法建立带头结点的单链表。 4、对给定的单链表L，编写一个删除L中值为x的结点的直接前趋结点算法。 5、用顺序存储结构实现线性表的就地逆置算法，即将（a1,a2, …ai,…an）逆置为（an,…,ai,…a2,a1）; 6、用

25、链式存储结构实现线性表的就地逆置算法，即将（a1,a2, …ai,…an）逆置为（an,…,ai,…a2,a1）; 7、使用顺序存储结构分别实现A=A∪B和A=A∩B运算； 参考答案（线性表） 一、选择题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 B A B C A B C C B B A B B A B C B A A A B A A 二、填空题 1、在双链表中要删除已知结点*p，其时间复杂度为（O(1

26、)）。 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->p

27、rior;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->next; L=L->next; free(q);）。 三

28、、判断题 1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（） 2、顺序存储的线性表可以随机存取。 （√） 3、线性表采用顺序存储，必须占用一片连续的存储单元。 （√） 四、程序设计题 1、已知带头结点的单链表head中的结点是按整数值递增排序的，写一算法将值为x的结点插入到表head中，使head仍然有序。 P=head->next; While(p->next!=NULL&&p->datanext;//指针定位 p->next=x;

29、x->next=p->next; 2、用尾插入法建立带头结点的单链表。 请参考教材“数据结构-清华大学严尉敏著评p29-p30”; 3、用头插入法建立带头结点的单链表。 请参考教材“数据结构-清华大学严尉敏著评p29-p30”; 4、对给定的单链表L，编写一个删除L中值为x的结点的直接前趋结点算法。 //算法思路：先判断L中是否存在值为x的结点，若不存在，返回错误（-1）；若存在，用一指针p定位到值为x的第一结点,用另一个指针q定位到值为x的第一结点的前驱结点，然后实施删除操作；重点语句为： p=L->next;//p指向第一个结点 whili(p->data!

30、=x&&p->next!=NULL) p=p->next; if(p= =NULL) ruturn 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

31、 { sqlist.base[i]sqlist.base[sqlist.length-i];//第i个元素和第length-i元素交换存储 } 6、用链式存储结构实现线性表的就地逆置算法(不带头结点的单链表)，即将（a1,a2, …ai,…an）逆置为（an,…,ai,…a2,a1）; 参考答案： Node *fun(Node *h)//h指向单链表的第一个结点 { Node *p,*q,*r; P=h; If(p==NULL) Return NULL; q=pnext;//q

32、指针指向第二个结点 pnext=NULL; while(q) { r=qnext；//第一次循环时，r指向第三个结点 qnext=p;//第二个结点的NEXT指向第一个结点 p=q;//p总是指向逆置后的第一个结点 q=r;//q总是指向剩余单链表的第一个结点，为将其作为逆置单链表的第一个结点作准备 } return p; } 两外，解决本体还有另外一种思路，将结点数据域拷贝到一个一维数组中，然后反过来填充单链表结点的数据域。 7、使用顺

33、序存储结构分别实现A=A∪B和A=A∩B运算； 请参考清华大学出版社出版，严尉敏编著《数据结构C语言版》P20例2-1； 3 栈和队列 一、 选择题： 1、循环队列是空队列的条件是（ ） A．Q . rear = = Q . front B．（Q . rear + 1）%maxsize = = Q .front C．Q . rear = = 0 D．Q. front = = 0 2、链栈与顺序栈相比，比较明显的优点是（ ） A．通常不会出现栈满的情况 B．通常不会出现栈空的情况 C．插入操作更加

34、方便 D．删除操作更加方便 [分析]不管是链栈还是顺序栈，其插入、删除操作都是在栈顶进行的，都比较方便，所以不可能选C)，D)。对链栈来讲，当栈中没有元素而又要执行出栈操作时，就会出现栈空现象，故B)也是不正确的。只要内存足够大，链栈上就不会出现栈满现象。而对顺序栈来讲，由于其大小是事先确定好的，因此可能会出现栈满现象。所以A)是正确的。 3、若一个栈的输入序列是１，２，３，……，n，输出序列的第一个元素是ｎ，则第ｉ个输出元素是（ ） A．n - i B．n – i + 1 C．i D．不确定 4、栈与一般线性表的区别

35、主要在（ ） A．元素个数 B．元素类型 C．逻辑结构 D．插入、删除元素的位置 5、一个链栈的栈顶指针是top，则执行出栈操作时（栈非空），用x保存被删除结点，则执行（ ） A．x = top; top = top next； B．x = topdata； C．top = top next;x = top data； D．x = top data;top = top next； [分析]栈顶元素出栈后，应该从栈底位置即第一个结点开始重新定位，执行语句是：q=base ; while(qnex

36、t!=top) q=qnext; free(top); top=q; 6、对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（ ） A．1，2，3 B．3，2，1 C．3，1，2 D．2，1，3 [分析] 每个元素进栈后立即出栈，结果是答案A；三个元素全部进栈后再出栈，得到答案B；1和2进栈后出栈，然后3入栈后出栈，得到答案D；而C答案不可能的原因是：3出栈后，说明1、2还在栈中，1出栈后2还在栈中，说明2的入栈次序在1之前。 7、在链接队列执行入队操作（　 ） A．需判别队是否空 B

37、．需判别队是否满 C．限制在链表头p进行 D．限制在链表尾p进行 8、以下不属于栈的基本运算是（ ）。 A．删除栈顶元素 B．删除栈底元素 C．判断栈是否为空 D．将栈置为空栈 9、一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ ）。 A．e,d,c,b,a　 B．d,e,c,b,a C．d,c,e,a,b 　　 D．a,b,c,d,e 10、设计一个判别表达式中左、右括号是否配对出现的算法，采用（

38、 ）数据结构最佳。 A．线性表的顺序存储结构　 B．栈 C．队列　　　　 D．线性表的链式存储结构 11、循环队列的特点之一是不会产生（ ）。 A．上溢出 B．下溢出 C．队满 D．假溢出 12、设数组Data[n]作为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句为（ ）。 A．rear=(rear+1)%(n+1) B．front=(front+1)% n C．rear=(rear+1)% n

39、 D．front=(front+1)%(n+1) 13、栈是限定在（ ）处进行插入或删除操作的线性表。 A．端点 B．栈底 C．栈顶 D．中间 14、容量是10的循环队列的队头位置qfront为2，队列中的数据元素个数为5，则队的第一个数据元素的位置是（ ） A．2 B．7 C．1 D．0 [分析] (front-rear+10)%10=5,并且front和rear的取值范围均是0—9，所以只有（7-2+10）%10=5。 15、循环队列的出队操作是（ ） A． qfront=(qfront+1)%max

40、size; B．qfront=qfront+1; C．qrear=(qrear+1)%maxsize; D．qrear=qrear+1; 16、当循环队列q是满队列时，存放队列元素的数组data有n个元素，则data中存放（ ）个数据元素。 A．n B. n-1 C. n-2 D.0 [分析] 容量为maxsize的循环队列最多只能存放maxsize-1个数据元素，当队列满时，队尾指针再往前走一步就追上队头指针，即(rear+1)% maxsize=front； 17、以下哪一个不是队列的基本运算（ ）。 A．

41、从队尾插入一个新元素 B．从队列中删除第i个元素 C．判断一个队列是否为空 D．读取队头元素的值 18、在一个链队列中，若f , r分别为队首、队尾指针，则插入s所指结点的操作为（ ）。 A．fnext=s;f=s B．rnext=s;r=s; C．snext=r;r=s; D．snext=f;f=s 19、循环队列的入队操作应为（ ）。 A．qrear=qrear+1;qdata[qrear]=x; B．qdata[qrear++]=x; C．qrear=(qrear+1)%m

42、axsize; qdata[qrear]=x; D．qdata[qrear]=x;q->rear=(qrear+1)%maxsize; 20、栈和队列都是（ ）。 A．限制存取点的线性结构 B．限制存取点的非线性结构 C．顺序存储的线性结构 D．链式存储的线性结构 21、实现递归调用属于（ ）的应用。 A．队列 B．栈 C． 数组 D．树 二、 填空题： 1、循环队列用数组data[m]存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中元素的个数是（　　　　　　　　　　　　

43、）。 2、栈顶的位置是随着（　　　　　　　）操作而变化的。 3、假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（　　　　　　　　）。 4、队列的队尾位置随着（　　　　　）而变化。 5、在（　　　　 　　　）的情况下，链队列的出队操作需要修改尾指针。 6、从栈顶指针为top的链栈中删除一个结点，并将被删除的结点的值保存在x中，其操作步骤为（ ）；top=top->next;。 7、用数组A[m]来存放循环队列q的元素，且它的头、尾指针分别为front和rear，队列满足条件(q.

44、rear+1)%m==q.front,则队列中当前的元素个数为（ ）。 8、顺序栈s存储在数组s->data[max]中，对s进行出栈操作，执行的语句序列是（ ）。 9、以下运算实现在循环队列中的初始化操作 void initqueue(seqqueue *q){q->front=0;( );} 三、 判断题： 1、循环队列中无上溢现象。 （ ） 2、循环队列只有下溢，没有

45、上溢。 （ ） 3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢”。 （ ） 4、顺序队列和循环队列的队满和队空的条件是一样的。 （ ） 5、为解决队列“假满”问题，可以采用循环数组实现队列存储。　 （ ） 6、队列是后进先出表。 （ ） 7、栈是后进先出表。

46、 （ ） 四、 应用题： 1、 设有一个栈，元素进栈的次序为A，B，C，D，E，写出下列出栈序列的操作序列。（1）CBADE（2）ACBED，其中I为进栈操作，O为出栈操作。 2、如果编号为1、2、3的三辆列车进入一个栈式结构的站台，那么可能得到的三辆列车出站序列有哪些？不可能出现的序列是什么？ 五、 程序设计题： 1、写出循环队列入队操作的函数。 参考答案（栈和队列） 一、选择题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

47、16 17 18 19 20 21 A A B D B C D B C B D C C B A B B B C A B 二、填空题 1、循环队列用数组data[m]存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中元素的个数是（(rear-front+maxsize）%maxsize）。 2、栈顶的位置是随着（入栈和出栈）操作而变化的。 3、假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（bceda）。 4、队列的队尾位置随着（入队

48、列操作变化）而变化。 5、在（链队列为空）的情况下，链队列的出队操作需要修改尾指针。 分析：Q.rear=h; 6、从栈顶指针为top的链栈中删除一个结点，并将被删除的结点的值保存在x中，其操作步骤为（x=top->data）。 7、用数组A[m]来存放循环队列q的元素，且它的头、尾指针分别为front和rear，队列满足条件(q.rear+1)%m==q.front,则队列中当前的元素个数为（0）。 8、顺序栈s存储在数组s->data[max]中，对s进行出栈操作，执行的语句序列是（stop--）。 9、以下运算实现在循环队列中的初始化操作 void initqueue

49、(seqqueue *q){q->front=0;( qbase=(qelemtype *)malloc(maxsize*sizeof(qelemtype)); qrear=0;);} 三、判断题 1、循环队列中无上溢现象。 （） 2、循环队列只有下溢，没有上溢。 （） 3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢”。 （） 4、顺序队列和循环队列的队满和队空的条件是一样的。

50、 （） 5、为解决队列“假满”问题，可以采用循环队列实现队列存储。　 （√） 6、队列是后进先出的线性表。 （） 7、栈是后进先出表。 （√） 四、应用题 1、设有一个栈，元素进栈的次序为A，B，C，D，E，写出下列出栈序列的操作序列。（1）CBADE（2）ACBED，其中I为进栈操作，O为出栈操作。 参考答案：（1）IIIOOOIOIO (2)IO

51、IIOOIIOO 2、如果编号为1、2、3的三辆列车顺序进入一个栈式结构的站台，那么可能得到的三辆列车出站序列有哪些？不可能出现的序列是什么？ 参考答案：可能得到的三辆列车出站序列有1，2，3； 1，3，2；2，1，3；2，1，3；2，3，1；其他3个数字的另外1个排列不可能出现，即3，1，2。 五、程序设计题 1、写出循环队列入队操作的函数。 请参考清华大学出版社严蔚敏编著的《数据结构C语言版》p65。 4 串和数组（含参考答案） 一、单选题 1．下列那些为空串（ ） A）S=“ ” B）S=“” C）S=“φ” D）S=“θ” 答案：B 2

52、．S1=“ABCD”，S2=“CD”则S2在S3中的位置是（ ） A）1 B）2 C）3 D）4 答案：C 3．假设S=“abcaabcaaabca”，T=“bca”，Index (S,T,3) 的结果是（ ） A）2 B）6 C）11 D）0 答案：B 4．在串中，对于SubString(&Sub,S,pos,len)基本操作，pos和len的约束条件是（ ） A）0

53、os-1 C）1<=pos<=StrLength(S) 且0<=len<=StrLength(S)-pos+1 D）1<=pos<=StrLength(S) 且1<=len<=StrLength(S)-pos-1 答案：C 5．串是一种特殊的线性表，其特殊性体现在( )。 A．可以顺序存储 B. 数据元素是一个字符 C．可以链接存储 D. 数据元素可以是多个字符 答：B 6．串是( )。 A．少于一个字母的序列 B. 任意个字母的序列 C．不少于一个字符的序列 D. 有限个字符的序列 答：D 7． 串的长度是( )。 A．

54、串中不同字母的个数 B. 串中不同字符的个数 C．串中所含的字符的个数 D. 串中所含字符的个数，且大于0 答：C 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))的结果是( )。 A．BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答：D 9． 若某串的长度小于一个常数，则采用( )存储方式最

55、为节省空间。 A．链式 B. 堆结构 C. 顺序表 答：C 二、填空题： 1．串是每个结点仅由一个字符组成的____________________。 答：线性表 2．在串中，SubString (“student”,5,0) 的结果是____________________。 答：“” 3．假设S=“abcaabcaaabca”，T=“bca”，V=“x”，Replace (S,T,V)结果是____________________。 答：“axaxaax” 4．在串中，对于StrCompare(S,T)基本操作，若S

56、_________________。 答：<0 5．在串顺序存储结构中，实现串操作的原操作为____________________。 答：字符序列的复制 6．串与线性表在逻辑结构上极为相似，区别仅在于____________________ ；在基本操作上差别很大，线性表的基本操作大多数以____________________ 作为操作对象，而串的基本操作通常以 作为操作对象。 答：串的数据对象约束为字符集 “单个元素” “串的整体” 7．两个串相等的充分必要条件是____________________ 且____________________ 。

57、答：两个串的串长相等 各个对应位置的字符都相等 8．空串是指____________________，空格串是指_______________________。 答：不含任何字符的串 仅含空格字符的串 三、判断题 1．空串是由空白字符组成的串（ FALSE ） 2．串的定长顺序结构是用一组XXX连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。(TRUE ) 3．串的堆分配存储表示是用一组XXX连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。（TRUE ） 4．串中S

58、trInsert(&S,pos,T)基本操作是最小的操作子集（FALSE） 5．串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。(FALSE) (错：子串是主串中连续的字符构成的有限序列) (题源：胡元义，C版数据结构课程辅导与习题解析，p80，4.2.1(判断题)_1) 6．如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。(FALSE) ( 错：是否连续是关键) (题源：陈明，C版实用数据结构基础，p109，(判断题)_2) 7．串类型的最小操作子集不能利用其他串操作来实现，反之，其他串操

59、作（除串清除ClearString和串销毁DestroyString外）均可在最小操作子集上实现。(TRUE) (题源：根据教材p72自编) 四、简答题 1．已知串s=‘(xyz)*’，t=‘(x+z)*y’，试利用串的基本运算将s串转化为t串，t串转化为s串。 (题源：宁正元，C版题解，p40，4.2_3) 答：concat ( replace (substring (sub,s,1,5),‘y’,‘+’), replace (substring (sub,s,6,1),‘*’，‘*y’)) concat(replace(substring(sub,t,1,5),‘

60、+’,‘y’),replace(substring(sub,t,6,2),‘*y’,‘*’)) 2．串是字符组成的，长度为1的串和字符是否概念相同？为什么？ (题源：朱战立，C版题解，p86，4.2.1(典型题解)_2) 答：由于字符的长度固定为1，长度概念可以隐含，所以存储时只需存储该字符即可；而长度为1的串其长度概念不能隐含，必须显示地表示出来，所以存储时要同时存储该字符和值为1的长度值。 五、算法设计题 1．设串s和串t采用顺序存储结构，编写函数实现串s和串t的比较操作，要求比较结果包括大于、小于和等于三种情况。 (题源：朱战立，C版题解，p87，4.2.1

61、(典型题解)_7) 提示 算法思想：循环逐个比较两个串，一旦两个串的某个字符比较不相等则说明两个串不相等，此时进一步比较这两个不相等字符的大于和小于情况来决定串s和串t比较的大于和小于情况；当串s的n个字符和串t的m个字符比较全部相等时，还需进一步判断此时串s或串t是否还有剩余字符没有比较，来决定串s和串t比较的大于和小于情况；若所有字符比较均相等，并且串s的字符个数n和串t的字符个数m也相等时，说明串s等于串t。当串s大于串t时函数返回1，当串s小于串t时函数返回-1，当串s等于串t时函数返回 0。 解：int StrCompare(SStrType s,SStrType t)

62、{ int n=s.length, m=t.length, i,j,tag; i=0; j=0; while(it.str[j]) { tag=1; /*说明s>t,退出比较*/ return tag; } else { tag=-1; /*说明s

63、 else if(n>m) tag=1; /*若串t只和串s的前m个字符相等则s>t*/ else if(n

64、，此时利用一个统计计数器进行累加1运算，在此之后若连续读到的是非空格符，则这些字符属于刚统计到的那个单词，因此不应将计数器累加1，下一次计数应该是在读到一个或几个空格后再遇到非空格字符之时进行。因此，统计一个单词时不仅要满足当前所检查的这个字符是非空格，而且要满足所检查的前一个字符是空格。 解：int count(r) char r[80]; { char prec,nowc; int num,j; prec=‘ ’; num=0; for(j=0;j<80;j++) { nowc=r[j]; if((nowc!=‘ ’)&&(prec==‘ ’))

65、 num++; prec=nowc; } return num; }/*count*/ 3．编写算法，求串s所含不同字符的总数和每种字符的个数。 (题源：严蔚敏，C版习题集，p29，4.18) 解：typedef struct{ char ch; int num; }mytype; void StrAnalyze(Stringtype S) //统计串S中字符的种类和个数 { mytype T[MAXSIZE]; //用结构数组T存储统计结果 for(i=1;i<=S[0];i++) { c=S;j=0; while(

66、T[j].ch && T[j].ch!=c) j++; //在结构数组T中逐元素查找当前字符c是否已记录过. //当循环停止时，再看是什么原因造成的停止。 if(T[j].ch) T[j].num++; //循环停止时T[j].ch不等于NULL,说明是由于T[j].ch=c所致 //若是 T[j].ch =c所致则说明字符c在串s中已经出现过 //故将其个数加1. else T[j]={c,1}; //否则为首次出现，将其出现次数记为1. }//for for(j=0;T[j].ch;j++) //打印每个字符在串s中的出现次数。 printf(“%c: %d\n”,T[j].num); }//StrAnalyze 5 数组和广义表 （收集整理题目） 一、 单项选择题 1. 常对数组进行的两种基本操作是____。 A. 建立与删除 B. 索引和修改 C. 对数据元素的存取和修改 D. 查