2022年《数据结构》习题集 .pdf

1 绪论一、选择题：1、下列算法的时间复杂度是（）for(i=0;i n;i+ +) ci=i ；AO（1）BO（n）CO（ log2n）DO（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、从逻辑上可以把数据结构分为（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 30 页 - - - - - - - - - 1 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+ +) aij=i*j；AO（m2）BO（n2）CO（mn）DO（ 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、基于某种逻辑结构之上的运算，其实现是惟一的。（）参考答案（绪论）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 30 页 - - - - - - - - - 2 一、选择题1 2 3 4 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;jnext=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、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）A（ 1）B（ log2n）CO（n）DO（n2）解析： 单就插入运算而言，算法时间复杂度为（1） ，但要将指针定位到链表末尾，指针移动的时间复杂度为O（ n） ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 30 页 - - - - - - - - - 3 4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）A顺序表B用头指针表示的单循环链表C用尾指针表示的单循环链表D单链表解析： 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1) 。若用头指针来表示该链表，则查找终端结点的时间为O(n) 。5、线性表是（）A一个有限序列，可以为空B一个有限序列，不能为空C一个无限序列，可以为空D一个无限序列，不能为空6、在 n 个结点的双链表的某个结点前插入一个结点的时间复杂度是（）AO（n）BO（1）CO（log2n）DO（n2）7、线性表采用链式存储时，结点的地址（）A必须是连续的B必须是不连续的C连续与否均可D必须有相等的间隔8、在单链表中，增加头结点的目的是（）A使单链表至少有一结点B标志表中首结点位置C方便运算的实现D说明单链表是线性表的链式存储实现9、带头结点的单链表head为空的判定条件是（）Ahead = NULL ；Bhead - next = NULL ；Chead - next = head；Dhead ! = NULL ；10、在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（）A（ 1）B（ n）C（ n2）D（ log2n）11、下列有关线性表的叙述中，正确的是（）A线性表中的元素之间是线性关系B线性表中至少有一个元素C线性表中任何一个元素有且仅有一个直接前趋D线性表中任何一个元素有且仅有一个直接后继12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（）A直接前趋B直接后继C开始结点D终端结点13、将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是（） 。An B.2n-1 C.2n D.n-1 14、链表不具有的特点是（） 。A随机访问B不必事先估计存储空间C插入删除时不需移动元素D所需的空间与线性表成正比15、在一个单链表中，已知q 所指结点是p 所指结点的直接前趋，若在p，q 之间插入s结点，则执行的操作是（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 30 页 - - - - - - - - - 4 As-next=p-next;p-next=s; B q-next=s;s-next=p; Cp-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 个元素的前趋元素， 则采用（）存储方式最节省时间。A 顺序表B单链表C双向链表D单循环链表19、两个指针P 和 Q，分别指向单链表的两个元素，P所指元素是Q 所指元素的前驱的条件是（） 。AP-next=Q BQ-next=P CP=Q DP-next=Q-next 20、链表不具有的特点是（） 。A可随机访问任一元素B插入、删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比21、下面关于线性表的叙述中，错误的是（） 。A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作C线性表采用链接存储，不必占用一片连续的存储单元D线性表采用链接存储，便于进行插入和删除操作22、在 n 个结点的顺序表中，算法的时间复杂度是O(1)的操作是（） 。A访问第 i 个结点（ 1i n）和求第i 个结点的直接前趋（2i n）B在第 i 个结点后插入一个新结点（1i n）C删除第i 个结点（ 1i n）D将 n 个结点从小到大排序23、在一个单链表中，若删除p 指向结点的后继结点，则执行的操作为（） 。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); 二、填空题：1、在双链表中要删除已知结点*p，其时间复杂度为（） 。2、在仅有尾指针R 指示的单循环链表R 中，在表尾插入一个结点S 的语句序列是（） 。3、在带头结点的双链表中，指针所指结点是开始结点的条件是（） 。4、在具有n 个结点的双链表中做插入、删除运算，平均时间复杂度为（） 。5、在一个长度为n 的顺序表中第i 个元素（ 1 i n）之前插入一个元素时，需向后名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 30 页 - - - - - - - - - 5 移动（）个元素。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、线性表采用顺序存储，必须占用一片连续的存储单元。（）四、程序设计题数据结构的数据类型定义如下：顺序存储：typedef struct int *base; int length; int listsize; sqlist; 链式存储：typedef 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、用 链式 存储结构实现线性表的就地逆置算法，即将（a1,a2, ai,an）逆置为（an,ai,a2,a1）; 7、使用顺序存储结构分别实现A=A B 和 A=A B 运算；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 30 页 - - - - - - - - - 6 参考答案（线性表）一、选择题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)） 。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-datanext;/指针定位p-next=x; x-next=p-next; 2、用尾插入法建立带头结点的单链表。请参考教材“数据结构-清华大学严尉敏著评p29-p30”; 3、用头插入法建立带头结点的单链表。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 30 页 - - - - - - - - - 7 请参考教材“数据结构-清华大学严尉敏著评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) 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;irear=(qrear+1)%maxsize; 20、栈和队列都是（） 。A限制存取点的线性结构B限制存取点的非线性结构C顺序存储的线性结构D链式存储的线性结构21、实现递归调用属于（）的应用。A队列B栈C 数组D树二、填空题：1、循环队列用数组datam存放其元素值，已知其头、尾指针分别是front 和 rear，则当前队列中元素的个数是（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 30 页 - - - - - - - - - 11 2、栈顶的位置是随着（）操作而变化的。3、假设以S 和 X 分别表示进栈和退栈操作，则对输入序列a，b，c，d， e 进行一系列栈操作 SSXSXSSXXX 之后，得到的输出序列为（） 。4、队列的队尾位置随着（）而变化。5、在（）的情况下，链队列的出队操作需要修改尾指针。6、从栈顶指针为top 的链栈中删除一个结点，并将被删除的结点的值保存在x 中，其操作步骤为（） ；top=top-next;。7、用数组Am 来存放循环队列q 的元素，且它的头、尾指针分别为front和 rear ，队列满足条件 (q.rear+1)%m=q.front,则队列中当前的元素个数为（） 。8、顺序栈s 存储在数组s-datamax中，对s 进行出栈操作，执行的语句序列是（） 。9、以下运算实现在循环队列中的初始化操作void initqueue(seqqueue *q)q-front=0;( ); 三、判断题：1、循环队列中无上溢现象。（）2、循环队列只有下溢，没有上溢。（）3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢”。 （）4、顺序队列和循环队列的队满和队空的条件是一样的。（）5、为解决队列“假满”问题，可以采用循环数组实现队列存储。（）6、队列是后进先出表。（）7、栈是后进先出表。（）四、应用题：1、 设有一个栈， 元素进栈的次序为A，B，C，D，E，写出下列出栈序列的操作序列。（1）CBADE （2）ACBED ，其中 I 为进栈操作，O 为出栈操作。2、如果编号为1、2、3 的三辆列车进入一个栈式结构的站台，那么可能得到的三辆列车出站序列有哪些？不可能出现的序列是什么？五、程序设计题：1、写出循环队列入队操作的函数。参考答案（栈和队列）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 30 页 - - - - - - - - - 12 一、选择题1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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、循环队列用数组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 的链栈中删除一个结点，并将被删除的结点的值保存在x 中，其操作步骤为（ x=top-data） 。7、用数组Am 来存放循环队列q 的元素，且它的头、尾指针分别为front和 rear ，队列满足条件 (q.rear+1)%m=q.front,则队列中当前的元素个数为（0） 。8、顺序栈s 存储在数组s-datamax中，对s 进行出栈操作，执行的语句序列是（stop- ） 。9、以下运算实现在循环队列中的初始化操作void initqueue(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)IOIIOOIIOO 2、如果编号为1、2、3 的三辆列车顺序进入一个栈式结构的站台，那么可能得到的三辆名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 30 页 - - - - - - - - - 13 列车出站序列有哪些？不可能出现的序列是什么？参考答案：可能得到的三辆列车出站序列有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 2S1=“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） 0posStrLength(S)+1 且 1=len=StrLength(S)-pos+1 B） 0posStrLength(S)+1 且 0=len=StrLength(S)-pos-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. 任意个字母的序列名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 30 页 - - - - - - - - - 14 C不少于一个字符的序列D. 有限个字符的序列答： D 7 串的长度是 ( )。A串中不同字母的个数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 若某串的长度小于一个常数，则采用( )存储方式最为节省空间。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)基本操作，若ST，返回值 _ 。答： 0 5在串顺序存储结构中，实现串操作的原操作为_ 。答：字符序列的复制6串与线性表在逻辑结构上极为相似，区别仅在于_ ；在基本操作上差别很大，线性表的基本操作大多数以_ 作为操作对象，而串的基本操作通常以作为操作对象。答：串的数据对象约束为字符集“单个元素”“串的整体”名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 30 页 - - - - - - - - - 15 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 , * ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 30 页 - - - - - - - - - 16 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。解： int StrCompare(SStrType s,SStrType t) int n=s.length, m=t.length, i,j,tag; i=0; j=0; while(in &jt.strj) tag=1; /* 说明 st,退出比较 */ return tag; else tag=-1; /* 说明 sm) tag=1; /* 若串 t 只和串 s的前 m 个字符相等则st*/ else if(nm) tag=-1;/* 若串 s 只和串 t 的前 n 个字符相等则st*/ return tag; 2输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计此文本中单词的个数。(题源：宁正元，C 版题解， p44， 4.2_12) 提示：要统计单词的个数先要解决如何判断一个单词，应该从输入行的开头一个字符一个字符地去辨别。假定把一个文本行放在数组r 中，那么就相当于从r0 开始逐个检查数组元素，当经过若干个空格符之后，找到第一个字母就是一个单词的开头，此时利用一个统计计数器进行累加1 运算，在此之后若连续读到的是非空格符，则这些字符属于刚统计到的那个单词，因此不应将计数器累加1，下一次计数应该是在读到一个或几个空格后再遇到非空格字符之时进行。因此，统计一个单词时不仅要满足当前所检查的这个字符是非空格，而且要满足所检查的前一个字符是空格。解： int count(r) char r80; char prec,nowc; int num,j; prec=? ; num=0; for(j=0;j80;j+) nowc=rj; if(nowc!=? )&(prec=? ) num+; prec=nowc; return num; /*count*/ 3编写算法，求串s所含不同字符的总数和每种字符的个数。(题源：严蔚敏，C 版习题集， p29，4.18) 解： typedef struct char ch; int num; mytype; void StrAnalyze(Stringtype S) / 统计串 S中字符的种类和个数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 30 页 - - - - - - - - - 18 mytype TMAXSIZE; /用结构数组T 存储统计结果for(i=1;i1）的父结点是（）A2i B不存在C2i+1 D? i/2?2、有 m 个叶结点的哈夫曼树所具有的结点数为（）Am Bm+1 C2m D2m - 1 3、下列陈述中正确的（）A二叉树是度为2 的有序树B二叉树中结点只有一个孩子时无左右之分C二叉树中必有度为2 的结点D二叉树中最多只有两棵子树，并且有左右之分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 30 页 - - - - - - - - - 20 4、以二叉链表作为二叉树的存储结构，在具有个结点的二叉链表中(n0)，空链域的个数为（）A2n - 1 Bn - 1 Cn + 1D2n + 1 5、将一棵有100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49 的结点的左孩子编号为（）A99 B98 C50 D48 6、在一棵具有五层的满二叉树中，结点总数为（）A31 B32 C33 D16 7、在一棵二叉树中，第5 层上的结点数最多为（）A8 B15 C16 D32 8、由二叉树的（）遍历，可以惟一确定一棵二叉树A前序和后序B前序和中序C后序D中序9、具有 35 个结点的完全二叉树的深度为（） 。A .5 B.6C.7 D.8 10、已知一棵二叉树的先序遍历序列为EFHIGJK ，中序遍历序列为HFIEJGK ，则该二叉树根的右子树的根是（） 。AE B. F C. G D. J 11、由 4 个结点构造出的不同的二叉树个数共有（） 。A8 B. 10 C12D14 解析：141412)(CC（解释：最多有4 层，最少有3 层。若有4 层，从第二层开始，均有两个位置可选；若有3 层，第 3 层上有 4 个位置可选）12、在完全二叉树中，如果一个结点是叶子结点，则它没有（） 。A .左孩子结点B. 右孩子结点C.左、右孩子结点D.左、右孩子结点和兄弟结点13、深度为6 的二叉树最多有（）个结点。A64 B63C 32 D31 14、二叉树使用二叉链表存储，若p 指针指向二叉树的一个结点，当p-lchild=NULL时，则（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 30 页 - - - - - - - - - 21 A p 结点左孩子为空Bp 结点有右孩子C p 结点右孩子为空Dp 结点有左孩子15、 在具有 n 个结点的完全二叉树中，若结点 i 有左孩子，则结点 i 的左孩子编号为 （） 。A2iB不存在C 2i+1 D2i-1 16、 将含 100 个结点的完全二叉树从根这一层开始，按从上到下从左到右依次对结点编号，根结点的编号为。编号为50 的结点 X的双亲的编号为（） 。A25B48 C100 D无法确定17、三个结点可以构成（）种不同形状的二叉树。A 2 C3 D5 18、若由树转化得到的二叉树是非空的二叉树，则二叉树形状是（） 。A根结点无右子树的二叉树B根结点无左子树的二叉树C根结点可能有左子树和右子树D各结点只有一个孩子的二叉树19、哈夫曼树是访问叶结点的带权