数据结构习题集

1绪论一、选择题：1、下列算法的时间复杂度是（）for(i=0;i<n;i++)c[i]=i；A．O（1）B．O（n）C．O（log2n）D．O（nlog2n）2、数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（）A．索引存储方法B．顺序存储方法C．链式存储方法D．散列存储方法解析：数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链式存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。3、以下哪一个术语与数据的存储结构无关？（）。A.顺序表B.链表C.散列表D.队列4、算法在发生非法操作时可以做出处理的特性称为（）。A．正确性 B．易读性 C．健壮性 D．高效性5、逻辑结构是指数据元素的（）。A．关联方式 B．存储方式 C．结构 D．数据项6、研究数据结构就是研究（）。A．数据的逻辑结构 B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其数据的运算7、从逻辑上可以把数据结构分为（）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构8、以下有关数据的叙述中错误的是（）。A．计算机能够处理的数据包括整数、实数、字符、声音、图像等B．数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式C．数据存储结构的实现依赖于计算机语言D．数据的运算是定义在数据的逻辑结构上的9、数据的基本单位是（）。A.数据结构B.数据元素C.数据项D.文件10、下列算法的时间复杂度是（）for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j；A．O（m2）B．O（n2）C．O（m×n）D．O（m+n）11、算法分析的两个主要方面是（）。A．正确性和简明性 B．数据复杂性和程序复杂性C．可读性和可维护性 D．时间复杂性和空间复杂性二、填空题：1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（）和（）。2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（）无关，是独立于计算机的。3、()结构与数据元素本身的内容和形式无关。4、程序段“for(i=1;i<=n;i++){k++;for(j=1;j<=n;j++)x=x+k;}”的时间复杂度为()。5、数据的存储结构（物理结构）可以用（）、（）、（）及散列存储等四种存储方法表示。判断题：1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。（）2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。（）3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（）4、数据的机内表示称为数据的存储结构。（）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（）6、数据元素是数据的最小单位。（）7、基于某种逻辑结构之上的运算，其实现是惟一的。（）参考答案（绪论）一、选择题1234567891011BDDCADCBACD二、填空题1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（存储结构）和（运算）。2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（）无关，是独立于计算机的。3、(逻辑)结构与数据元素本身的内容和形式无关。4、程序段“for(i=1;i<=n;i++){k++;for(j=1;j<=n;j++)x=x+k;}”的时间复杂度为(O(n2))。5、数据的存储结构（物理结构）可以用（顺序）、（链式）、（索引）及散列存储等四种存储方法表示。三、判断题1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。（×）2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。（×）3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（√）4、数据的机内表示称为数据的存储结构。（√）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×）6、数据元素是数据的最小单位。（×）7、基于某种逻辑结构之上的运算，其实现是惟一的。（×）2线性表选择题：1、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）。A．nB．n/2C．n/3D．n/42、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（）A．S->next=P->next;P->next=SB．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、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）A．顺序表B．用头指针表示的单循环链表C．用尾指针表示的单循环链表D．单链表解析：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。5、线性表是（）A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（）A．O（n）B．O（1）C．O（log2n）D．O（n2）7、线性表采用链式存储时，结点的地址（）A．必须是连续的B．必须是不连续的C．连续与否均可D．必须有相等的间隔8、在单链表中，增加头结点的目的是（）A．使单链表至少有一结点B．标志表中首结点位置C．方便运算的实现D．说明单链表是线性表的链式存储实现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．线性表中至少有一个元素C．线性表中任何一个元素有且仅有一个直接前趋D．线性表中任何一个元素有且仅有一个直接后继12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（）A．直接前趋B．直接后继C．开始结点D．终端结点13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。A．nB.2n-1C.2nD14、链表不具有的特点是（）。A．随机访问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．存储空间是静态分配的17、一个顺序表一旦说明，其中可用空间大小（）A．已固定 B．可以改变 C．不能固定 D．动态变化18、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。顺序表 B．单链表 C．双向链表 D．单循环链表19、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素的前驱的条件是（）。A．P->next==Q B．Q->next==PC．P==Q D．P->next==Q->next20、链表不具有的特点是（）。A．可随机访问任一元素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．删除第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中，在表尾插入一个结点S的语句序列是（）。3、在带头结点的双链表Ｌ中，指针Ｐ所指结点是开始结点的条件是（）。4、在具有n个结点的双链表中做插入、删除运算，平均时间复杂度为（）。5、在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动（）个元素。6、在双循环链表中，若要在指针p所指结点之前插入指针s所指的结点，则需执行下列语句：s->prior=p->prior;p->prior->next=s;()和p->prior=s;。7、已知指针p指向双向链表中的一个结点（非首结点、非尾结点），则将结点s插入在p结点的直接后继位置的语句是（）s->prior=p；s->next->prior=s；p->next=s;8、已知带表头结点的单链表L，指针p指向L链表中的一个结点（非首结点、非尾结点），则删除结点p的直接后继结点的语句是（）；删除首结点的语句是（）。判断题1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（）2、顺序存储的线性表可以随机存取。（）3、线性表采用顺序存储，必须占用一片连续的存储单元。（）程序设计题数据结构的数据类型定义如下：顺序存储：typedefstruct{int*base;intlength;intlistsize;}sqlist;链式存储：typedefstructLinkList{intdata;structLinkList*next;}Node,*LinkList;1、已知带头结点的单链表head中的结点是按整数值递增排序的，写一算法将值为x的结点插入到表head中，使head仍然有序。2、用尾插法建立带头结点的单链表。3、用头插法建立带头结点的单链表。4、对给定的单链表L，编写一个删除L中值为x的结点的直接前趋结点算法。5、用顺序存储结构实现线性表的就地逆置算法，即将（a1,a2,…ai,…an）逆置为（an,…,ai,…a2,a1）;6、用链式存储结构实现线性表的就地逆置算法，即将（a1,a2,…ai,…an）逆置为（an,…,ai,…a2,a1）;7、使用顺序存储结构分别实现A=A∪B和A=A∩B运算；参考答案（线性表）一、选择题1234567891011121314151617181920212223BABCABCCBBABBABCBAAABAA二、填空题1、在双链表中要删除已知结点*p，其时间复杂度为（O(1)）。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->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->next;L=L->next;free(q);）。三、判断题1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（×）2、顺序存储的线性表可以随机存取。（√）3、线性表采用顺序存储，必须占用一片连续的存储单元。（√）四、程序设计题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、用尾插入法建立带头结点的单链表。请参考教材“数据结构-清华大学严尉敏著评p29-p30”;3、用头插入法建立带头结点的单链表。请参考教材“数据结构-清华大学严尉敏著评p29-p30”;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)ruturnerror;//不存在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.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)ReturnNULL;q=pnext;//q指针指向第二个结点pnext=NULL;while(q){r=qnext；//第一次循环时，r指向第三个结点qnext=p;//第二个结点的NEXT指向第一个结点p=q;//p总是指向逆置后的第一个结点q=r;//q总是指向剩余单链表的第一个结点，为将其作为逆置单链表的第一个结点作准备}returnp;}两外，解决本体还有另外一种思路，将结点数据域拷贝到一个一维数组中，然后反过来填充单链表结点的数据域。7、使用顺序存储结构分别实现A=A∪B和A=A∩B运算；请参考清华大学出版社出版，严尉敏编著《数据结构C语言版》P20例2-1；栈和队列选择题：1、循环队列是空队列的条件是（）A．Q.rear==Q.frontB．（Q.rear+1）%maxsize==Q.frontC．Q.rear==0D．Q.front==02、链栈与顺序栈相比，比较明显的优点是（）A．通常不会出现栈满的情况B．通常不会出现栈空的情况

C．插入操作更加方便D．删除操作更加方便[分析]不管是链栈还是顺序栈，其插入、删除操作都是在栈顶进行的，都比较方便，所以不可能选C)，D)。对链栈来讲，当栈中没有元素而又要执行出栈操作时，就会出现栈空现象，故B)也是不正确的。只要内存足够大，链栈上就不会出现栈满现象。而对顺序栈来讲，由于其大小是事先确定好的，因此可能会出现栈满现象。所以A)是正确的。3、若一个栈的输入序列是１，２，３，……，n，输出序列的第一个元素是ｎ，则第ｉ个输出元素是（）A．n-iB．n–i+1C．iD．不确定4、栈与一般线性表的区别主要在（）A．元素个数B．元素类型C．逻辑结构D．插入、删除元素的位置5、一个链栈的栈顶指针是top，则执行出栈操作时（栈非空），用x保存被删除结点，则执行（）A．x=top;top=topnext；B．x=topdata；C．top=topnext;x=topdata；D．x=topdata;top=topnext；[分析]栈顶元素出栈后，应该从栈底位置即第一个结点开始重新定位，执行语句是：q=base;while(qnext!=top)q=qnext;free(top);top=q;6、对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（）A．1，2，3B．3，2，1C．3，1，2D．2，1，3[分析]每个元素进栈后立即出栈，结果是答案A；三个元素全部进栈后再出栈，得到答案B；1和2进栈后出栈，然后3入栈后出栈，得到答案D；而C答案不可能的原因是：3出栈后，说明1、2还在栈中，1出栈后2还在栈中，说明2的入栈次序在1之前。7、在链接队列执行入队操作（）A．需判别队是否空B．需判别队是否满C．限制在链表头p进行D．限制在链表尾p进行8、以下不属于栈的基本运算是（）。A．删除栈顶元素B．删除栈底元素C．判断栈是否为空D．将栈置为空栈9、一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）。A．e,d,c,b,aB．d,e,c,b,aC．d,c,e,a,bD．a,b,c,d,e10、设计一个判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。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)%nC．rear=(rear+1)%nD．front=(front+1)%(n+1)13、栈是限定在（）处进行插入或删除操作的线性表。A．端点 B．栈底 C．栈顶 D．中间14、容量是10的循环队列的队头位置qfront为2，队列中的数据元素个数为5，则队的第一个数据元素的位置是（）A．2 B．7 C．1 D．[分析](front-rear+10)%10=5,并且front和rear的取值范围均是0—9，所以只有（7-2+10）%10=5。15、循环队列的出队操作是（）A． qfront=(qfront+1)%maxsize; 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.[分析]容量为maxsize的循环队列最多只能存放maxsize-1个数据元素，当队列满时，队尾指针再往前走一步就追上队头指针，即(rear+1)%maxsize=front；17、以下哪一个不是队列的基本运算（）。A．从队尾插入一个新元素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=s19、循环队列的入队操作应为（）。A．qrear=qrear+1;qdata[qrear]=x; B．qdata[qrear++]=x;C．qrear=(qrear+1)%maxsize;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，则当前队列中元素的个数是（）。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.rear+1)%m==q.front,则队列中当前的元素个数为（）。8、顺序栈s存储在数组s->data[max]中，对s进行出栈操作，执行的语句序列是（）。9、以下运算实现在循环队列中的初始化操作voidinitqueue(seqqueue*q){q->front=0;();}判断题：1、循环队列中无上溢现象。（）2、循环队列只有下溢，没有上溢。（）3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢”。（）4、顺序队列和循环队列的队满和队空的条件是一样的。（）5、为解决队列“假满”问题，可以采用循环数组实现队列存储。（）6、队列是后进先出表。（）7、栈是后进先出表。（）应用题：设有一个栈，元素进栈的次序为A，B，C，D，E，写出下列出栈序列的操作序列。（1）CBADE（2）ACBED，其中I为进栈操作，O为出栈操作。2、如果编号为1、2、3的三辆列车进入一个栈式结构的站台，那么可能得到的三辆列车出站序列有哪些？不可能出现的序列是什么？程序设计题：1、写出循环队列入队操作的函数。参考答案（栈和队列）一、选择题123456789101112131415161718192021AABDBCDBCBDCCBABBBCAB二、填空题1、循环队列用数组data[m]存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中元素的个数是（(rear-front+maxsize）%maxsize）。2、栈顶的位置是随着（入栈和出栈）操作而变化的。3、假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（bceda）。4、队列的队尾位置随着（入队列操作变化）而变化。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、以下运算实现在循环队列中的初始化操作voidinitqueue(seqqueue*q){q->front=0;(qbase=(qelemtype*)malloc(maxsize*sizeof(qelemtype));qrear=0;);}三、判断题1、循环队列中无上溢现象。（×）2、循环队列只有下溢，没有上溢。（×）3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢”。（×）4、顺序队列和循环队列的队满和队空的条件是一样的。（×）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个数字的另外1个排列不可能出现，即3，1，2。五、程序设计题1、写出循环队列入队操作的函数。请参考清华大学出版社严蔚敏编著的《数据结构C语言版》p65。串和数组（含参考答案）一、单选题1．下列那些为空串（）A）S=“”B）S=“”C）S=“φ”D）S=“θ”答案：B2．S1=“ABCD”，S2=“CD”则S2在S3中的位置是（）A）1B）2C）3D）4答案：C3．假设S=“abcaabcaaabca”，T=“bca”，Index(S,T,3)的结果是（）A）2B）6C）11D）0答案：B4．在串中，对于SubString(&Sub,S,pos,len)基本操作，pos和len的约束条件是（）A）0<pos<StrLength(S)+1且1<=len<=StrLength(S)-pos+1B）0<pos<StrLength(S)+1且0<=len<=StrLength(S)-pos-1C）1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1D）1<=pos<=StrLength(S)且1<=len<=StrLength(S)-pos-1答案：C5．串是一种特殊的线性表，其特殊性体现在()。A．可以顺序存储B.数据元素是一个字符C．可以链接存储D.数据元素可以是多个字符答：B6．串是()。A．少于一个字母的序列B.任意个字母的序列C．不少于一个字符的序列D.有限个字符的序列答：D7．串的长度是()。A．串中不同字母的个数B.串中不同字符的个数C．串中所含的字符的个数D.串中所含字符的个数，且大于0答：C8．设有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．BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF答：D9．若某串的长度小于一个常数，则采用()存储方式最为节省空间。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<T，返回值____________________。答：<05．在串顺序存储结构中，实现串操作的原操作为____________________。答：字符序列的复制6．串与线性表在逻辑结构上极为相似，区别仅在于____________________；在基本操作上差别很大，线性表的基本操作大多数以____________________作为操作对象，而串的基本操作通常以作为操作对象。答：串的数据对象约束为字符集“单个元素”“串的整体”7．两个串相等的充分必要条件是____________________且____________________。答：两个串的串长相等各个对应位置的字符都相等8．空串是指____________________，空格串是指_______________________。答：不含任何字符的串仅含空格字符的串三、判断题1．空串是由空白字符组成的串（FALSE）2．串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。(TRUE)3．串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。（TRUE）4．串中StrInsert(&S,pos,T)基本操作是最小的操作子集（FALSE）5．串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。(FALSE)(错：子串是主串中连续的字符构成的有限序列)(题源：胡元义，C版数据结构课程辅导与习题解析，p80，4.2.1(判断题)_1)6．如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。(FALSE)(错：是否连续是关键)(题源：陈明，C版实用数据结构基础，p109，(判断题)_2)7．串类型的最小操作子集不能利用其他串操作来实现，反之，其他串操作（除串清除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),‘+’,‘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(典型题解)_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。解：intStrCompare(SStrTypes,SStrTypet){intn=s.length,m=t.length,i,j,tag;i=0;j=0;while(i<n&&j<m){if(s.str==t.str[j])/*继续比较下一个字符*/{i++;j++;}elseif(s.str>t.str[j]){tag=1;/*说明s>t,退出比较*/returntag;}else{tag=-1;/*说明s<t，退出比较*/returntag;}}if(n==m)tag=0;/*若所有字符比较均相等则tag=0*/elseif(n>m)tag=1;/*若串t只和串s的前m个字符相等则s>t*/elseif(n<m)tag=-1;/*若串s只和串t的前n个字符相等则s<t*/returntag;}2．输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计此文本中单词的个数。(题源：宁正元，C版题解，p44，4.2_12)提示：要统计单词的个数先要解决如何判断一个单词，应该从输入行的开头一个字符一个字符地去辨别。假定把一个文本行放在数组r中，那么就相当于从r[0]开始逐个检查数组元素，当经过若干个空格符之后，找到第一个字母就是一个单词的开头，此时利用一个统计计数器进行累加1运算，在此之后若连续读到的是非空格符，则这些字符属于刚统计到的那个单词，因此不应将计数器累加1，下一次计数应该是在读到一个或几个空格后再遇到非空格字符之时进行。因此，统计一个单词时不仅要满足当前所检查的这个字符是非空格，而且要满足所检查的前一个字符是空格。解：intcount(r)charr[80];{charprec,nowc;intnum,j;prec=‘’;num=0;for(j=0;j<80;j++){nowc=r[j];if((nowc!=‘’)&&(prec==‘’))num++;prec=nowc;}returnnum;}/*count*/3．编写算法，求串s所含不同字符的总数和每种字符的个数。(题源：严蔚敏，C版习题集，p29，4.18)解：typedefstruct{charch;intnum;}mytype;voidStrAnalyze(StringtypeS)//统计串S中字符的种类和个数{mytypeT[MAXSIZE];//用结构数组T存储统计结果for(i=1;i<=S[0];i++){c=S;j=0;while(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.elseT[j]={c,1};//否则为首次出现，将其出现次数记为1.}//forfor(j=0;T[j].ch;j++)//打印每个字符在串s中的出现次数。printf(“%c:%d\n”,T[j].num);}//StrAnalyze数组和广义表树和二叉树选择题：1、在具有n个结点的完全二叉树中，结点i（i>1）的父结点是（）A．2iB．不存在C．2i+1D．⌊i/2⌋2、有m个叶结点的哈夫曼树所具有的结点数为（）A．mB．m+1C．2mD．2m-13、下列陈述中正确的（）A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，并且有左右之分4、以二叉链表作为二叉树的存储结构，在具有ｎ个结点的二叉链表中(n>0)，空链域的个数为（）A．2n-1B．n-1C．n+1D．5、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）A．99B．98C．50D．486、在一棵具有五层的满二叉树中，结点总数为（）A．31B．32C．33D．167、在一棵二叉树中，第5层上的结点数最多为（）A．8B．15C．16D．8、由二叉树的（）遍历，可以惟一确定一棵二叉树A．前序和后序B．前序和中序C．后序D．中序9、具有35个结点的完全二叉树的深度为（）。A.5B.6C.7D.810、已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是（）。A．EB.FC.GD.J11、由4个结点构造出的不同的二叉树个数共有（）。A．8B.10C．12解析：（解释：最多有4层，最少有3层。若有4层，从第二层开始，均有两个位置可选；若有3层，第3层上有4个位置可选）12、在完全二叉树中，如果一个结点是叶子结点，则它没有（）。A.左孩子结点B.右孩子结点C.左、右孩子结点D.左、右孩子结点和兄弟结点13、深度为6的二叉树最多有（）个结点。A．64 B．63 C．32 D．14、二叉树使用二叉链表存储，若p指针指向二叉树的一个结点，当p->lchild=NULL时，则（）。p结点左孩子为空 B．p结点有右孩子p结点右孩子为空 D．p结点有左孩子15、在具有n个结点的完全二叉树中，若结点i有左孩子，则结点i的左孩子编号为（）。A．2i B．不存在 C．2i+1 D．2i-116、将含100个结点的完全二叉树从根这一层开始，按从上到下从左到右依次对结点编号，根结点的编号为１。编号为50的结点X的双亲的编号为（）。A．25B．48C．10017、三个结点可以构成（）种不同形状的二叉树。１ Ｂ．2 C．3 D．518、若由树转化得到的二叉树是非空的二叉树，则二叉树形状是（）。A．根结点无右子树的二叉树 B．根结点无左子树的二叉树C．根结点可能有左子树和右子树 D．各结点只有一个孩子的二叉树19、哈夫曼树是访问叶结点的带权路径长度（）的二叉树。A．最短 B．最长 C．可变 D．不定20、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。A．空或只有一个结点 B．高度等于其结点数C．任一结点无左孩子 D．任一结点无右孩子填空题：1、12个结点的完全二叉树的叶结点有（5）个。2、在任何一棵二叉树中，度为０的结点n0和度为２的结点n2之间的关系是（n0=n2+1。3、已知完全二叉树的第4层有4个结点，则其叶子结点数是（11）。4、10个结点的完全二叉树的叶结点有（3）个。5、深度为6的二叉树最多有（63）个结点。6、一个二叉树中，度为2的结点有3个，则叶结点有（4）个。7、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的（第一）个结点。8、下图为某树的静态双亲表示，则结点D、E的双亲结点分别为（B）和（C）。A-1B0C0D1E2012349、具有m个叶结点的哈夫曼树共有（2m-1）个结点。10、二叉树通常有（顺序）存储结构和（链式）存储结构两种。11、二叉树在二叉链表表示方式下，p指向二叉树的根结点，经运算s=p；while(s->rchild)s=s->rchild后，s指针指向（根或最右）结点。判断题：1、完全二叉树中，若一个结点没有左孩子，则它必须是叶子。（TRUE）2、由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（FALSE）3、一般在哈夫曼树中，权值越大的叶子离根结点越近。（TRUE）4、二叉树中任何一个结点的度都是2。（FALSE）5、一棵哈夫曼树中不存在度为1的结点。（TRUE）解析：n=n0+n1+n2;2n0-1=n;n0=n2+1;可推出不存在n1;6、若一个二叉树的叶结点是先根遍历序列的最后一个结点，则它必是中根遍历的序列中的最后一个结点。（FALSE）7、中序遍历二叉排序树的结点不能得到排好序的结点序列。（FALSE）8、完全二叉树一定是满二叉树。（FALSE）9、由二叉树的前序和中序遍历序列可以推导出此二叉树的后序遍历序列。（TRUE）10、满二叉树一定是完全二叉树。（TRUE）11、完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（FALSE）应用题：1、对给定的一组权值W=｛5，2，9，11，8，3，7｝，试构造相应的哈夫曼树，并计算它的带权路径长度。参考答案：带权路径长度=11*1+9*2+8*3+7*3+5*3+3*4+2*42、已知一棵二叉树的前序序列和中序序列分别如下，请画出该二叉树。前序序列：ABDGJKLHCEIF中序序列：BGJLKDHAEICF解析：前序序列：ABDGJKLHCEIF中序序列：BGJLKDHAEICF找到根后，可确定左子树结点和右子树结点，然后递归进行即可；3、试找出分别满足下列条件的所有二叉树。（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同。解答：只有空树或只有根结点的二叉树，同时满足上述三个条件；4、设有一组结点，其权值W=｛1，4，9，16，25，36，49，64，81，100｝，画出由这些结点所构成的哈夫曼树，并计算带权路径长度。解析：参考第一题；5、画出下图所示森林经转换后所对应的二叉树。eq\o\ac(○,A)eq\o\ac(○,B)eq\o\ac(○,C)eq\o\ac(○,D)eq\o\ac(○,E)eq\o\ac(○,F)eq\o\ac(○,J)eq\o\ac(○,G)