数据结构-基于C++语言（微课版） 习题及答案 王想实

绪论习题一、填空题计算机识别、存储和加工处理的对象统称为数据。数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。数据结构以不同视角，可以分为逻辑结构和物理结构两种结构。数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。数据结构是指数据及其相互之间的关系的集合。当结点之间存在M对N(M:N)的联系时，称这种关系为网状结构。当结点之间存在1对N(1:N)的联系时，称这种结构为层次结构。从数据结构的观点，数据通常可分为三个层次，即数据、数据元素和数据对象。数据物理结构被分为顺序存储、链式存储、散列存储和索引存储四种。算法是对求解问题的一种描述，是指令的有限序列。对算法从时间和空间两方面进行度量，分别称为时间复杂度和空间复杂度分析。算法效率的度量可以分为事先估算法和事后统计法。若一个算法中的语句频度之和为T(n)=4n2+3nlog2n，则算法的时间复杂度为O(n2)。若一个算法中的语句频度之和为T(n)=4n2+3n+2n，则算法的时间复杂度为O(2n)。程序for(i=1,t=1,s=0;i<=n;i++){t=t*i;s=s+t;}的时间复杂度为O(n)。当输入不合法数据时，应能作适当处理，不致引起严重后果，是指算法的健壮性特性。二、选择题数据结构通常是研究数据的(A)及它们之间的相互关系。A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为(A)。A．顺序存储结构B．链式存储结构C．逻辑结构D．物理结构链式存储结构所占存储空间(A)。A．分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的指针。B．只有一部分，存放结点的值。C．只有一部分，存储表示结点间关系的指针。D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素线性表采用链式存储时，其地址(D)。A．必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以与数据元素本身的形式、内容、相对位置、个数无关的是数据的(C)。A．存储结构

B．存储实现C．逻辑结构

D．运算实现在数据结构中，从逻辑上可以把数据结构划分成(C)。A．动态结构和静态结构

B．紧凑结构和非紧凑结构C．线性结构和非线性结构

D．内部结构和外部结构通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着(B)。A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等在数据结构中，与所使用的计算机无关的是(C)。A．物理结构B．存储结构C．逻辑结构D．逻辑和存储结构算法的时间复杂度与(B)有关。A.计算机硬件性能B.问题规模C.内存芯片的有关参数D.编译程序质量算法分析的两个主要方面是(A)。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性数据结构的定义为(D，S)，其中D是(B)的集合。A. 算法    B.数据元素   C. 数据操作   D. 逻辑结构下面程序段的时间复杂度为(C)。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n) D.O(m+n)下面程序段的时间复杂度为(C)。s=0;for(i=1;i<=n;i++){for(j=n;j>=n-1;j--) s=s+1;}A．O(n)B．O(nlog2n)C．O(n2)D．O(n3/2)下列时间复杂度中最坏的是(D)。A．O(1)B．O(n)C．O((log2n)D．O(n2)下面是关于两个矩阵加法的算法实现，其时间复杂度是(D)。for(i=0;i<n;i++)for(j=0;i<n;j++)c[i][j]=a[i][j]+b[i][j];A．O(1)B．O(n)C．O(log2n)D．O(n2)三、简答题说明数据、数据元素、数据项之间的关系。答：数据是信息的载体，它是能够被计算机识别、存储和加工处理的对象。数据元素是数据结构中讨论的基本单位，是数据集合中的个体。一个数据元素可由若干个数据项组成，多个数据项构成数据元素，每一个数据项都是不可再分割的。解释数据结构、逻辑结构、存储结构之间的联系与区别。答：数据结构从不同视角可以划分为逻辑结构与存储结构，逻辑结构指的是数据间的关系，它又分为线性结构和非线性结构,而存储结构是逻辑结构的存储映像。这两者并不冲突，一个指的是数据之间的关系，而另一个指这种关系在计算机中的表示形式。算法的特性有哪些？答：有穷性、确定性、可行性、输入和输出。简述数据结构上的基本操作主要有哪些。答：

查找、插入、删除、更新和输出。简述时间复杂度和空间复杂度主要与哪些因素有关。答：时间复杂度与算法本身的性质即算法中控制结构和原操作有关，算法本身的性质又包括其涉及的问题规模。同时算法还有与选择的何种算法策略有关。空间复杂度与所处理数据结点的大小和个数有关，同时与算法在某次执行中处理的特定数据的大小和规模有关。当一个算法被转换成程序并在计算机上执行时，其运行所需要的时间一般取决于哪些因素？答：因素有算法选用何种策略、问题的规模、程序设计的语言、编译程序所产生的机器代码的质量和机器执行指令的速度。四、算法分析题分析下面语句段执行的时间复杂度。for(i=1;i<=n;i++)for(j=1;j<=n;j++)s++;答：时间复杂度为：O(n2)。分析下面语句段执行的时间复杂度。for(i=1;i<=n;i++)for(j=1;j<=i;j++)s++;答：时间复杂度为：O(n2)。分析下面语句段执行的时间复杂度。i=1;k=0;while(i<=n-1){k+=10*i;i++;答：时间复杂度为：O(n)。}分析下面语句段执行的时间复杂度。for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;答：时间复杂度为：O(n3)。线性表习题填空题顺序表是指逻辑上相邻的元素在物理位置上相邻。线性表中结点间的关系是1:1关系。顺序表中提取任意位置的元素，不需要从头到尾查找，因为顺序表具有随机定位的特点。线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储结构。顺序表中访问某个数值的元素，其时间复杂度均为O(1)。在长度为n的顺序表中，插入一个结点，其平均移动元素的个数为n/2。在长度为n的顺序表中，删除结点的时间复杂度为O(n)。如果线性表需要频繁进行数据的插入与删除操作，则适合链式存储结构。链表相对于顺序表的优点是插入、删除方便，不需要移动数据元素。在双向链表中要删除已知结点p，其时间复杂度为O(1)。在单向链表中要在已知结点p之后插入一个新结点，其时间复杂度为O(1)。在单向链表中要在已知结点p之前插入一个新结点，其时间复杂度为O(n)。在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。在单链表中设置头结点的作用是便于链表上操作的统一性。双向循环链表中，在p所指的结点之后插入指针f所指的结点，其操作为f->rear=p->rear;f->front=p;f->rear->front=f;p->rear=f。选择题线性表采用链式存储时，其地址(D)。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是(B)。A.当前结点所在的地址域B.指针域C.空指针域D.空闲域单向链表的存储密度(C)。A.大于1B.等于1C.小于1D.不能确定已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为(A)。A.B+(i-1)×mB.B+i×mC.B-i×mD.B+(i+1)×m不带头结点的单链表head为空的判断条件是(A)。A.head==NULLB.head>next==NULLC.head->data==NULLD.head!=NULL设front，rear分别为循环双向链表结点的左指针和右指针，则指针p所指的元素是双循环链表head的尾元素的条件是(D)。A.p==headB.p->front==headC.p==NULLD.p->rear==head在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行(A)。A.s->next=p;q->next=s；B.p->next=s->next；s->next=p；C.p->next=s->next；s->next=p；D.p->next=s；p->next=s；两个指针p和q，分别指向单向链表的两个元素，p是q的前驱条件是(B)。A．p->next==q->nextB.p->next==qC.q->next==pD.p==q用链表存储的线性表，其优点是(C)。A．便于随机存取B．花费的存储空间比顺序表少C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同一个单链表中，若删除p所指结点的后继结点，则执行(A)。A.p=p->next->next；B.p=p->next；p->next=p->next->next；C.p->next=p；D.p=p->next->next；在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是(A)。A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)B.在第i个结点后插入一个新结点(1≤i≤n)C.删除第i个结点(1≤i≤n)D.将n个结点从小到大排序用链表表示线性表的优点是(B)。A.便于随机存取B.便于进行插入和删除操作C.占用的存储空间较顺序表少D.元素的物理顺序与逻辑顺序相同下面关于线性表的叙述中，错误的是(B)。A.线性表采用顺序存储必须占用一片连续的存储单元B.线性表采用顺序存储便于进行插入和删除操作C.线性表采用链式存储不必占用一片连续的存储单元D.线性表采用链式存储便于进行插入和删除操作在下列链表中不能从当前结点出发访问到其余各结点的是(C)。A.双向链表B.单循环链表C.单向链表D.双向循环链表在顺序表中，只要知道(D)，就可以求出任一结点的存储地址。A.任意位置结点地址B.结点大小C.向量大小D.基地址和结点大小简答题线性表有两种存储结构：一是顺序表，二是链表，简述它们各自的优缺点。答：顺序表的存储结构是使用连续的存储空间存储数据元素，优点是随机访问速度快，可以通过下标直接访问元素，缺点是插入和删除操作需要移动大量元素，空间利用率低。链表的存储结构是使用指针将数据元素链接在一起，优点是插入和删除操作方便高效，不需要移动大量元素，缺点是访问元素需要遍历链表，时间复杂度较高。试描述头指针，头结点开始结点的区别，并说明头指针和头结点的作用。答：头指针是指向链表头部的指针变量，用来记录链表的起始位置。头结点是在链表头部之前增加的一个结点，用来存储一些附加信息，如链表长度等。头指针的作用是用来操作链表的各种操作，而头结点的作用是为链表的操作提供方便，可以避免一些特殊情况的处理。何时选用顺序表，何时选用链表作为线性表的存储结构为宜?答：选择顺序表还是链表作为线性表的存储结构，取决于实际需求。当线性表的长度固定且需要频繁随机访问元素时，使用顺序表更合适。当线性表的长度不固定且需要频繁插入、删除操作时，使用链表更合适。另外，顺序表的存储需要连续的存储空间，而链表的存储可以灵活利用存储空间。在单链表，双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少?答：如果仅知道指针p指向某个结点，不知道头指针，是无法直接删除结点p的，因为无法找到待删除结点的前一个结点。需要知道头指针才能进行删除操作。时间复杂度为O(n)，其中n为链表的长度，需要遍历整个链表来找到待删除结点的前一个结点。在顺序表中插入和删除个结点需要平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在顺序表中插入和删除一个结点，平均分别需要移动n/2和(n-1)/2个结点，其中n为顺序表的长度。具体的移动次数取决于插入或删除操作的位置和顺序表中元素的个数。插入操作需要移动插入位置之后的元素，删除操作需要移动删除位置之后的元素。算法设计题已知顺序表L，写一算法将其倒置，例如倒置前为3,6,2,1,7,9，倒置后为9,7,1,2,6,3。答：参照算法2-20链表倒置的算法，只需要在遍历顺序表过程中将顺序表中的元素按照前后位置交换即可。设有带头结点的单向链表，head为指向头结点的指针。设计算法：实现在值为key的结点前插入值为y的结点。若值为key结点不存在，则将值为y的结点插在链表的最后，作为尾结点。答：voidinsertNode(ListNode*head,intkey,inty){ListNode*prev=head;ListNode*curr=head->next;//遍历链表，找到值为key的结点或链表的最后一个结点while(curr!=null&&curr->data!=key){prev=curr;curr=curr->next;}//创建新的结点ListNode*newNode=newListNode(y);newNode->next=curr;//在值为key的结点前插入新的结点prev->next=newNode;//如果curr为空，说明key不存在，将新结点插在链表的最后if(curr==NULL){prev->next=newNode;}}编写算法，删除单链表的表头结点与表尾结点。答：参考算法2-14链表中删除指定值的结点的算法。写出函数用于删除元素递增排列的带头结点单链表L中值大于min且小于max的所有元素，并给出其时间复杂度。答：voiddeleteRange(ListNode*head,intmin,intmax){ListNode*prev=head;ListNode*curr=head->next;while(curr!=null){if(curr->val>min&&curr->val<max){prev->next=curr->next;deletecurr;curr=prev->next;}else{prev=curr;curr=curr->next;}}}设单向链表中结点按有序链接，设计算法：删除链表中值相同的结点，使之只保留一个。答：参考算法2-21链表删除重复结点的算法。对给定的带头结点的单链表L，编写一个删除L中值为key的结点的直接前驱结点的算法。答：参考2-14链表中删除指定值的结点的算法。有两个循环单链表，链头指针分别为head1和head2，编写一个函数将链表head1链接到链表head2，链接后的链表仍是循环链表。答：voidlinkCircularLists(ListNode*head1,ListNode*head2){ListNode*curr1=head1->next;ListNode*curr2=head2->next;while(curr1->next!=head1){curr1=curr1->next;}while(curr2->next!=head2){curr2=curr2->next;}curr1->next=head2;curr2->next=head1;}有一个由整数构成的单链表长度为n，试编写算法，将单链表分解成两个，一个只由奇数构成，另一个只由偶数构成。答：voidsplitOddEven(ListNode*head,ListNode**oddHead,ListNode**evenHead){ListNode*oddTail=null;ListNode*evenTail=null;ListNode*curr=head;while(curr!=null){if(curr->data%2==0){//当前节点的值为偶数if(*evenHead==null){//如果evenHead为空，说明是第一个偶数节点*evenHead=curr;evenTail=curr;}else{//否则，将当前偶数节点链接到偶数链表的末尾evenTail->next=curr;evenTail=curr;}}else{//当前节点的值为奇数if(*oddHead==null){//如果oddHead为空，说明是第一个奇数节点*oddHead=curr;oddTail=curr;}else{//否则，将当前奇数节点链接到奇数链表的末尾oddTail->next=curr;oddTail=curr;}}curr=curr->next;}//将奇数链表和偶数链表的末尾设置为null，表示链表的结束if(oddTail!=null){oddTail->next=null;}if(evenTail!=null){evenTail->next=null;}}设带头结点的单向链表，将链表中所有的偶数结点删除。答：参照算法2-21链表删除重复结点的算法。设某单链表中，存在多个结点其数据值均为key，试编写一算法统计该类结点的个数。答：参照图2-9查找结点的算法，只需要将链表遍历到尾部即可，遍历的过程中进行统计结点的个数。若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。答：参考2-14链表中删除指定值的结点的算法。不同的是，不仅需要查找到P结点的前驱结点q，同时还需要查找q结点的前驱结点s，便于删除q结点后，调整链表，也就是设置s的后继结点变为p。试写一算法，将两个有序表合并为一个有序表。答：参考2-17有序表合并的算法。栈习题填空题在栈结构中，允许插入、删除的一端称为栈顶。栈是一种先进后出线性表。在有n个元素的栈中，进栈操作时间复杂度为O(1)。若进栈的次序是A,B,C,D,E，执行3次出栈操作以后，栈顶元素为B。三个元素6,8,4顺序进栈，执行两次Pop(s，x)运算后，x的值是8。设有编号为1,2,3,4的四辆列车，顺序开入栈式结构的站台，则可能的出栈序列有14种。一个栈的输入序列是1,2,3,..,n，输出序列的第一个元素是n，则第i个输出元素为i。在顺序栈中，当栈顶指针的值为-1时，表示空栈。已知顺序栈s，在对s进栈操作之前首先要判断栈满。在顺序栈中，当有元素入栈时，首先栈顶指针加1，然后元素再入栈。在顺序栈中，删除元素，需要将栈顶指针减1。已知中缀表达式，求它的后缀表达式，是栈的典型应用。在一个链式栈中，若栈顶指针等于NULL则为空栈；向栈顶指针为top的链栈中插入结点时，应该先判断top是否为空。向一个栈顶指针为top的链栈中，插入一个新结点p时，应执行p->next=top和top=p的语句。从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。向一个栈顶指针为top的链栈中，删除结点，应执行s=top和top=top->next的语句。8+7-6/2+3^2-5的后缀表达式是87+62/-32^+5-。选择题常用于函数调用的数据结构是(A)。A．栈 B．队列C．链表 D．数组在栈中进行插入和删除操作的位置是(A)。A．栈顶B．任意位置C．栈底D．与元素有关设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为(B)。A．3,2,5,6,4,1B．1,5,4,6,2,3C．2,4,3,5,1,6D．4,5,3,6,2,1如果以链表作为栈的存储结构，则出栈操作时(B)。A．必须判别栈是否满B．必须判别栈是否为空C．必须判别栈元素类型D．栈不做任何判别顺序栈存储空间的实现使用(B)存储元素。A．链表B．数组C．循环链表D．变量一个顺序栈一旦被声明，其占用空间的大小(A)。A．已固定B．不固定C．可以改变D．动态变化链栈与顺序栈相比，有一个比较明显的优点是(B)。A． 插入操作更加方便B．通常不会出现栈满的情况C．不会出现栈空的情况D．删除操作更加方便从栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列(D)语句。A．x=top;top->next;B．top=top->next;x=top->dataC．x=top->data;D．x=top->data;top=top->next在一个栈顶指针为HS的链栈中，将一个s指针所指的结点入栈，应执行下列(C)语句。A．HS->next=sB．s->next=HS->next;HS->next=s;C．s->next=HS;HS=s;D．.s->next=HS=HS->next4个元素按A,B,C,D顺序进栈s，执行两次Pop(s，x)运算后，栈顶元素的值是(B)。A．AB．BC．CD．D元素A,B,C,D依次进栈以后，栈底元素是(A)。A．AB．BC．CD．D经过InitStack(s)，Push(s，a)，Push(s，b)Pob(s)的运算后，再执行ReadTop(s)的值是(A)。A．aB．bC．1D．0经过下列栈的运算后，x的值是(B)。InitStack(s)（初始化栈）；Push(s，a)；Push(s，b)；ReadTop(s)；Pob(s，x)；A． aB．bC．1D．0经过下列栈的运算后，EmptySeque(s)的值是(C)。InitStack(s)；Push(s，a)；Push(s，b)；Pop(s，x)；Pop(s，x)；A．aB．bC．1D．0向顺序栈中输入元素时(B)。A．先存入元素，后移动栈顶指针B．先移动栈顶指针，后存入元素C．谁先谁后无关紧要D．同时进行初始化一个空间大小为5的顺序栈s后，s->top的值是(B)。A．0B．-1C．不再改变D．动态变化设有一个入栈的次序A,B,C,D,E的序列，则栈不可能的输出序列是(C)。A．EDCBAB．DECBAC．DCEABD．ABCDE设有一个顺序栈s，元素A,B,C,D,E,F依次进栈，如果6个元素出栈的顺序是B,D,C,F,E,A，则栈的容量至少应是(A)。A．3B．4C．5D．6综合应用题在栈的输入端元素的输入顺序为1,2,3,4,5,6，进栈过程中可以退栈，则退栈时能否排成序列3,2,5,6,4,1和1,5,4,6,2,3，若能，写出进栈、退栈过程；若不能，简述理由。采用用push(x)表示x进栈，pop(x)表示x退栈。答：push(1)，push(2)，push(3)，pop(3)，pop(2)，push(4)，push(5)，pop(5)，push(6)，pop(6)，pop(4)，pop(1)。所以可以得到序列3,2,5,6,4,1。push(1)，pop(1)，push(2)，push(3)，push(4)，push(5)，pop(5)，pop(4)，push(6)，pop(6)，，下一个出栈的是3，而不是2，所以不能得到序列1,5,4,6,2,3。给出表达式“84*32+-”的求值过程以及结果。答：创建一个空栈。从左到右遍历后缀表达式：遇到操作数8，将其压入栈中：栈=[8]遇到操作数4，将其压入栈中：栈=[8,4]遇到操作符*，从栈中弹出两个操作数4和8，计算8*4=32，并将结果32压入栈中：栈=[32]遇到操作数3，将其压入栈中：栈=[32,3]遇到操作数2，将其压入栈中：栈=[32,3,2]遇到操作符+，从栈中弹出两个操作数2和3，计算2+3=5，并将结果5压入栈中：栈=[32,5]遇到操作符-，从栈中弹出两个操作数5和32，计算32-5=27，并将结果27压入栈中：栈=[27]遍历完后缀表达式后，栈中的唯一元素27即为表达式的求值结果。因此，给定后缀表达式“84*32+-”的求值结果为27。编写一个算法，检查字符串“（x=0）[x=1](x++)[x=x-5](x=0)）“中的方括号和圆括号是否配对，若能够全部配对则返回1，否则返回0。答：intcheckParentheses(){stack<char>parenthesesStack;boolisBalanced=true;strings="(x=0)[x=1](x++)[x=x-5](x=0)";for(charc:s){if(c=='('||c=='['){parenthesesStack.push(c);}elseif(c==')'||c==']'){if(parenthesesStack.empty()){isBalanced=false;break;}else{chartop=parenthesesStack.top();parenthesesStack.pop();if((c==')'&&top!='(')||(c==']'&&top!='[')){isBalanced=false;break;}}}}if(!parenthesesStack.empty()){isBalanced=false;}returnisBalanced?1:0;}编写一算法将中缀表达式转换为后缀表达式。答：参考3-13表达式求值算法中将中缀表达式转换为后缀表达式的算法。编写一算法求解后缀表达式的值。答：参考3-13表达式求值算法。队列习题填空题队列是一种特殊，只允许在端点操作的线性表。在队列中存取数据应遵循的原则是先进先出。栈和队列的区别仅在于插入和删除位置不相同。队列在逻辑结构上属线性结构。队列允许插入的一端称为队尾，允许删除的一端称为队首。顺序队列中在出队操作时，首先要判断队列是否为空。顺序队列中入队操作时，首先需要判断队列是否为满。顺序存储的队列如果不采用循环方式，则会出现假溢出问题。循环队列的队头指针为front，队尾指针为rear，则队列中共有（rear－front＋N）％N个元素。循环队列的队头指针为front，队尾指针为rear，则队空的条件为front=rear。链队列q为空的条件是q->front=q->rear。在具有n个单元且采用顺序存储的循环队列中，队满时共有n-1个元素。若front和rear分别表示循环队列q的头指针和尾指针，m表示该队列的最大容量，则循环队列为空的条件(rear－front＋m)％m==0。对带头结点的链队列q，判定队列中只有一个数据元素的条件是q->front->next=q->rear。设循环队列的容量为100（序号0～99），现经过一系列的入队和出队的运算后，front=13，rear=39，则循环队列中还有26个元素。选择题队列是限定在(D)进行操作的线性表。A．中间者B.队首C.队尾D.端点在链队列中执行入队操作，(D)。A．需判别队列是否空 B．需判别队列是否满C．限制链表头p进行 D．限制在链表尾p进行在一个顺序存储的循环队列中，队首指针指向队首元素的(A)。A．前一个位置B．后一个位置C．队首元素位置D．任意位置一个循环队列一旦说明，其占用空间的大小(A)。A．固定B．可以变动C．不能固定D．动态变化顺序队列占用的空间(A)。A.必须连续B．不必连续C.不能连续D.可以不连续容量为10个元素的顺序循环队列用数组data来存储，则data数组的下标范围是(B)。A．0～10B．0～9C．1～9D．1～104个元素按A,B,C,D顺序连续入队列q，执行3次QutQueue(q)操作后，再执行EmptyQueue(q)；后的值是(A)。A．0B．1C．2D．3在链队列中，结点的结构：data为数据域，next为指针域，rear和front分别指向队尾和队首，则在链队列中出队后的结点由指针s所指，则应执行下列(C)操作。A．s=front->next;front->next=sB．front->next=sC．s=front;front=front->nextD．s->next=front;front=s若进队列的序列为A,B,C,D，则出队的序列是(C)。A．B,C,D,AB．A,C,B,DC．A,B,C,DD．C,B,D,A若用一个大小为10数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为(B)。A.5和1B.4和2C.2和4D.1和5简答题试举出几个生活中的例子，其操作规律符合队列的操作特征。答：银行柜台办理业务：在银行柜台，顾客按照先来后到的顺序等待办理业务。每个顾客办理完业务后，下一个顾客才能进入柜台。这也符合队列的先进先出的特性。打印队列：当我们在打印多个文件时，打印任务会按照提交的顺序排队等待执行。打印机会先处理队列中的第一个任务，然后才会处理后面的任务。这也是队列的典型应用场景。汽车排队进入收费站：在高速公路的收费站，汽车会按照到达的顺序排队等待进入收费站。每个汽车依次从队列中进入收费站，然后交费离开。这也是队列的一个应用场景。简单描述队列、队头、队尾、空队列、链队列和循环队列的概念。答：队列（Queue）是一种具有先进先出（FIFO）特性的线性数据结构。它类似于现实生活中的排队，新元素被添加到队列的一端，称为队尾（rear），而已存在的元素从队列的另一端被移除，称为队头（front）。队头（Front）是队列中的第一个元素，它是队列的入口。当元素被添加到队列的时候，它成为新的队尾。当元素从队列中被移除的时候，队头会向后移动。队尾（Rear）是队列中的最后一个元素，它是队列的出口。当元素被添加到队列的时候，队尾会向后移动。当元素从队列中被移除的时候，队尾保持不变。空队列（EmptyQueue）是指没有任何元素的队列。在空队列中，队头和队尾指向同一个位置，即没有任何元素进入或离开队列。链队列（LinkedQueue）是使用链表实现的队列。每个节点都包含一个数据元素和一个指向下一个节点的指针。链队列可以动态地增加或删除节点，因此没有固定的大小限制。循环队列（CircularQueue）是使用数组实现的队列。它通过循环利用数组空间来避免队列满时无法继续添加元素的问题。在循环队列中，队头和队尾可以在数组的开头和结尾之间循环移动。线性表、栈、队列有什么区别与联系？答：线性表是一种线性的数据结构，数据元素按照一定的顺序排列。栈和队列是特殊的线性表。栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。操作特性：线性表可以在任意位置插入和删除元素。栈只能在栈顶进行插入和删除操作，而且只能访问栈顶的元素。队列只能在队尾插入元素，在队头删除元素，不能访问队列中间的元素。使用场景：线性表适用于需要随机访问和灵活操作元素的场景。栈适用于需要按照后进先出的顺序访问元素的场景，比如函数调用、表达式求值等。队列适用于需要按照先进先出的顺序访问元素的场景，比如排队、任务调度等。什么是顺序队列的上溢现象？什么是顺序队列的假溢出现象？答：顺序队列的上溢现象：当队列满时，再进行入队操作就会导致上溢现象。也就是说，队列已经没有空闲空间可以存储新元素了，但是仍然有新元素要入队。这种情况下，如果继续进行入队操作，就会导致数据的丢失或覆盖，因为新的元素无法被正确地存储到队列中。顺序队列的假溢出现象：假溢出现象是指队列中存在空闲空间，但由于前面的元素出队时，没有正确地更新队头指针，导致队列判断为满的状态。也就是说，队列实际上还有空间可以存储新元素，但由于队头指针没有及时更新，导致无法进行入队操作。循环队列的优点是什么，如何判别循环队列的空和满。答：顺序队列的上溢现象：当队列满时，再进行入队操作就会导致上溢现象。也就是说，队列已经没有空闲空间可以存储新元素了，但是仍然有新元素要入队。这种情况下，如果继续进行入队操作，就会导致数据的丢失或覆盖，因为新的元素无法被正确地存储到队列中。顺序队列的假溢出现象：假溢出现象是指队列中存在空闲空间，但由于前面的元素出队时，没有正确地更新队头指针，导致队列判断为满的状态。也就是说，队列实际上还有空间可以存储新元素，但由于队头指针没有及时更新，导致无法进行入队操作。算法设计题设用一维数组data[n]表示一个队列，实现入队与出队的操作算法。答：参考算法4-(1~4)队列基本算法实现。编写算法，利用两个栈s1，s2模拟一个队列的入队、出队和判断队列空的运算。答：#defineMAX_SIZE100typedefstruct{intdata[MAX_SIZE];inttop;}Stack;voidinitStack(Stack*s){s->top=-1;}boolisStackEmpty(Stack*s){returns->top==-1;}boolisStackFull(Stack*s){returns->top==MAX_SIZE-1;}voidpush(Stack*s,intitem){if(isStackFull(s)){cout<<"Stackisfull!"<<endl;return;}s->top++;s->data[s->top]=item;}intpop(Stack*s){if(isStackEmpty(s)){cout<<"Stackisempty!”<<endl";return-1;}intitem=s->data[s->top];s->top--;returnitem;}typedefstruct{Stacks1;//用于入队操作的栈Stacks2;//用于出队操作的栈}Queue;voidinitQueue(Queue*q){initStack(&q->s1);initStack(&q->s2);}voidenqueue(Queue*q,intitem){push(&q->s1,item);//将元素入栈s1}intdequeue(Queue*q){if(isStackEmpty(&q->s1)&&isStackEmpty(&q->s2)){//如果栈s1和栈s2都为空，则队列为空cout<<"Queueisempty!"<<endl;return-1;}if(isStackEmpty(&q->s2)){//如果栈s2为空，则将栈s1中的元素依次出栈并入栈s2while(!isStackEmpty(&q->s1)){intitem=pop(&q->s1);push(&q->s2,item);}}intfront=pop(&q->s2);//将s2的栈顶元素出栈并返回returnfront;}boolisQueueEmpty(Queue*q){returnisStackEmpty(&q->s1)&&isStackEmpty(&q->s2);//当s1和s2都为空时，队列为空}设一个循环队列q，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，编写相应的入队算法和出队算法。答：#defineMAX_SIZE5typedefstruct{intdata[MAX_SIZE];intfront;intcount;}CircularQueue;voidinitQueue(CircularQueue*q){q->front=0;q->count=0;}boolisQueueEmpty(CircularQueue*q){returnq->count==0;}boolisQueueFull(CircularQueue*q){returnq->count==MAX_SIZE;}voidenqueue(CircularQueue*q,intitem){if(isQueueFull(q)){cout<<"Queueisfull!"<<endl;return;}intrear=(q->front+q->count)%MAX_SIZE;//计算队尾元素的下标q->data[rear]=item;//将元素放入队尾q->count++;//计数器加1}intdequeue(CircularQueue*q){if(isQueueEmpty(q)){cout<<"Queueisempty!"<<endl;return-1;}intitem=q->data[q->front];//取出队头元素q->front=(q->front+1)%MAX_SIZE;//头指针向后移动一位q->count--;//计数器减1returnitem;}已知q是一个非空队列，s是一个空栈。试设计一个算法，利用栈和队列的基本运算，将队列q中的全部元素逆置存放。答：#defineMAX_SIZE100typedefstruct{intdata[MAX_SIZE];intfront;intrear;intcount;}Queue;typedefstruct{intdata[MAX_SIZE];inttop;}Stack;voidinitQueue(Queue*q){q->front=0;q->rear=-1;q->count=0;}boolisQueueEmpty(Queue*q){returnq->count==0;}boolisQueueFull(Queue*q){returnq->count==MAX_SIZE;}voidenqueue(Queue*q,intitem){if(isQueueFull(q)){cout<<"Queueisfull!"<<endl;return;}q->rear=(q->rear+1)%MAX_SIZE;//计算队尾元素的下标q->data[q->rear]=item;//将元素放入队尾q->count++;//计数器加1}intdequeue(Queue*q){if(isQueueEmpty(q)){cout<<"Queueisempty!"<<endl;return-1;}intitem=q->data[q->front];//取出队头元素q->front=(q->front+1)%MAX_SIZE;//头指针向后移动一位q->count--;//计数器减1returnitem;}voidinitStack(Stack*s){s->top=-1;}boolisStackEmpty(Stack*s){returns->top==-1;}boolisStackFull(Stack*s){returns->top==MAX_SIZE-1;}voidpush(Stack*s,intitem){if(isStackFull(s)){cout<<"Stackisfull!"<<endl;return;}s->top++;//栈顶指针加1s->data[s->top]=item;//将元素放入栈顶}intpop(Stack*s){if(isStackEmpty(s)){cout<<"Stackisempty!"<<endl;return-1;}intitem=s->data[s->top];//取出栈顶元素s->top--;//栈顶指针减1returnitem;}voidreverseQueue(Queue*q){Stacks;initStack(&s);while(!isQueueEmpty(q)){intitem=dequeue(q);push(&s,item);}while(!isStackEmpty(&s)){intitem=pop(&s);enqueue(q,item);}}设循环队列q，只设置头指针和为指针，设计算法求循环队列中当前元素的个数。答：#defineMAX_SIZE100typedefstruct{intdata[MAX_SIZE];intfront;intrear;}Queue;voidinitQueue(Queue*q){q->front=0;q->rear=-1;}boolisQueueEmpty(Queue*q){returnq->rear<q->front;}intgetCurrentSize(Queue*q){if(isQueueEmpty(q)){return0;}intsize;if(q->rear>=q->front){size=q->rear-q->front+1;}else{size=q->rear+MAX_SIZE-q->front+1;}returnsize;}串与数组习题填空题在计算机软件系统中，有两种处理字符长度的方法，一是可变长度处理，二是固定长度处理。如果s=＂thisisthefirststring＂，sub=＂the＂，stringdex(s，sub)是8。已知字符串s1=＂abcdefghijklmnopqrstuvw＂，由如下运算可得到串s2=Concat(Sub(s1，19，3)，Sub(s1，4，2)，sub(s1，14，1)，Sub(s1，20，1))，则s2tuvefov。两个串相等的充要条件是长度相等，对应位置的字符也相等。s=＂xiaotech＂所含子串的个数是37。一个10×10的下三角矩阵A采用行优先压缩存储后，如果首元素a[0][0]是第一个元素，那么a[4][2]是第13个元素。两个矩阵Amn，Bnp相乘，其时间复杂度为O(m*n*p)。两个矩阵Amn，Bmn相加，其时间复杂度为O(m*n)。稀疏矩阵采用的压缩存储方法是三元组表示法。二维数组A[11][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则A[10][10]的地址为1140。选择题串的逻辑结构与(A)的逻辑结构不同。A．线性表B．队列C．栈D．树设有二维数组A[50][60]，其元素长度为1个字节，按列优先顺序存储，首元素A[0][0]的地址为200，则元素A[10][20]的存储地址为()。A．820 B．720 C．1210 D．1410一个100×100的下三角形矩阵a采用行优先压缩存储后，如果首元素a[0][0]是第一个元素，那么a[4][2]是第(A)元素。A．13 B．401 C．402 D．403串的长度是(D)。A．串中不同字符的个数B．串中不同字母的个数

C．串中所含字符的个数n(n>0)D．串中所含字符的个数n(n≥0)设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址为100，每个元素占1个地址空间，则a[3][2]的地址为(D)。A．102 B．105 C．106 D．108设有两个串p和q，求q在p中的首次出现的位置的运算称作(B)。A．连接B．模式匹配C．求子串D．求串长假设有60行70列的二维数组a以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[31，57]的存储地址为(A)。A．16902B.16904C.14454D.答案A,B,C均不对下面关于串的叙述中，(B)是不正确的？A．串是字符的有限序列

B．空串是由空格构成的串

C．模式匹配是串的一种重要运算

D．串既可以采用顺序存储，也可以采用链式存储C++语言对数组元素的存放方式通常采用(A)。A．按行为主的存储结构 B．按列为主的存储结构C．按行或列为主的存储结构 D．具体存储结构无法确定二维数组A[n][m］以列优先顺序存储，数组A中每个元素占用1个字节，A［1］［1］为首元素，其地址为0，则元素A[i][j]的地址为(B)。A．(j-1)×m+(j-1) B．(j-1)×n+(i-1)C．(j-1)×n+i D．j×n+i简答题简述下列每对术语的区别。空串和空格串。答：空串是指一个没有任何字符的字符串，长度为0。空格串是指只包含空格字符的字符串，长度大于等于1串变量和串常量。答：串变量是在程序中定义的一个变量，用来存储字符串的值。可以通过赋值操作来改变串变量的值。串常量是在程序中直接指定的一个字符串值，不可修改。通常用引号括起来表示，例如“hello”。主串和子串。答：主串是指一个完整的字符串，可以包含子串。子串是主串中的一个连续的字符序列。变量的名字和串变量的值。答：串变量的名字是程序中定义的标识符，用来表示一个存储字符串值的变量。串变量的值是存储在该变量中的字符串值。可以通过赋值操作来改变串变量的值。设有二维数组A（6×8），每个元素占6个字节存储，顺序存放，A的起地址为1000，计算：（1）数组A的体积（即存储量）；（2）数组的最后一个元素A的起地址；（3）按行优先存放时，元素a14的地址是多少；（4）按列优先存放时，元素a47的地址。答：存储容量为：（1）6*8*6=1288。（2）1000+(6*8-1)*6=2282（3）1000+（8+4）*6=1072（4）1000+（6*7+4）*6=1276算法设计题写一个算法来实现字符串逆序存储，要求不另设串存储空间。答：参考第二章顺表表的逆置算法。设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出-1。答：参考法5-4Brute-Force模式匹配算法编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。答：voidcountFrequency(conststd::string&input){unordered_map<char,int>frequency;//统计字符频度for(charc:input){c=toupper(c);//将字符转换为大写字母if(isalnum(c)){//只处理字母和数字字符frequency[c]++;}}//将结果存入文件ofstreamfile("result.txt");if(!file){cout<<"无法打开文件。\n";return;}file<<"字符\t频度\n";for(charc='A';c<='Z';c++){file<<c<<"\t"<<frequency[c]<<"\n";}for(charc='0';c<='9';c++){file<<c<<"\t"<<frequency[c]<<"\n";}cout<<"结果已保存到result.txt文件中。\n";}}试编写算法实现将字符串s中所有值为c的字符换成值为d的字符。答：参考算法5-7文本匹配算法。试编写算法实现将字符串s中所有值为s1的子串替换成值为s2的子串。答：参考算法5-7文本匹配算法。从串s中删除其值等于c的所有字符。答：参考第二章删除重复元素的算法。试编写算法实现将字符串s中所有值为s1的子串删除。答：voiddeleteSubstring(char*s,constchar*s1){ints1Len=strlen(s1);char*p=s;while((p=strstr(p,s1))!=NULL){memmove(p,p+s1Len,strlen(p+s1Len)+1);}}树与二叉树习题一、填空题一个结点所拥有的子树数称为该结点的度。度为零的结点称为叶子结点。对于二叉树来说，第i层上至多有2i-1个结点。56个结点的完全二叉树有28个叶子结点。深度为8的二叉树最多有255个结点。有8个结点的二叉树最大深度为8。前序为A，B，C且后序C，B，A的二叉树共有4种。已知完全二叉树的第8层有8个结点，则其叶结点数是68。中序为A，B，C且后序C，B，A的二叉树共有1种。树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为左子树和右子树。由一个二叉树的前序序列和后序列不能确定这个二叉树。有30个结点的完全二叉树，编号为11的结点的父结点的编号是5。哈夫曼树是带权路径长度最短的二叉树。由树转换二叉树时，其二叉树没有右子树。采用二叉链表存储的20个结点的二叉树，一共有21个空指针域。若用链表存储一个二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有___2n____个指针域，其中有n-1个指针域是存放了地址，有n+1个指针是空指针。中序遍历二叉排序树所得到的序列是有序序列（填有序或无序）。设哈夫曼树中共有99个结点，则该树中有50个叶子结点；若采用二叉链表作为存储结构，则该树中有100个空指针域。设一个二叉树中有50个度数为0的结点，21个度数为1的结点，则该二叉树总的结点个数为120个。设某二叉树有100个结点，则该二叉树的深度最小为7，最大为100。选择题树最适合用来表示(D)。A.无序数据元素B.无关系数据元素C.元素间多种联系的数据D.元素间有分支的层次关系在一个具有五层的满二叉树中，结点的个数为(B)。A.16B.31C.32D.33具有64个结点的完全二叉树的深度为(C)。A.5B.6C.7D.8任何一个二叉树的叶结点在前序、中序、后序遍历序列中的相对次序(A)。A.不发生改变B.发生改变C.不能确定D.以上都不对A，B为一个二叉树上的两个结点，在中序遍历时，A在B前的条件是(C)。A.A在B右方B.A是B祖先C.A在B左方D.A是B子孙二叉树的叶结点个数比度为2的结点的个数(C)。A.无关B.相等C.多一个D.少一个一个二叉树的后序遍历序列为ADBEC，中序遍历序列为AEBDC，则前序遍历序列为(D)。A.DCBEAB.AECDBC.AEDBCD.CEABD将一个有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为(C)。A.46B.47C.90D.91二叉树按某种顺序线索化后，任一结点不一定有指向其前驱和后继的线索，这种说法(A)。A.正确B.错误C.不确定D.都有可能下列陈述正确的是(A)。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树必有度为2的结点D.二叉树中最多只有两个子树，且有左右子树之分用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是(B)。A.32B.33C.34D.15在树结构中，若结点B有4个兄弟，A是B的父亲结点，则A的度为(C)。A.3B.4C.5D.6依据给定的权值，构造的哈夫曼是唯一的。这种说法(B)。A.正确B.错误C.不确定D.都有可能哈夫曼树中无度为1的结点，这种说法(A)。A．正确B．错误C．不确定D．都有可能线索二叉树中无空指针存在，这种说法(B)。A.正确B.错误C.不确定D.都有可能一个二叉树的前序序列和后序序列正好相反，则该二叉树一定是(C)的二叉树A．空或只有一个结点B．任一结点无左子树C．高度等于其结点数D．任一结点无右子树引入二叉线索树的目的是(A)A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便地进行插入与删除C．为了提高空间利用率D．为了向上查找双亲结点线索二叉树是一种(C)结构。A．逻辑B．存储结构C．为了能方便地找到双亲D．使二叉树的遍历结果唯一二叉树在线索后，仍不能有效求解的问题是(A)。A．先序线索二叉树中求先序后继B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近(A)。A．正确B．错误C．不确定D．都有可能三、简答题描述树与二叉树的区别与联系。答：区别：结构：树是由节点和边组成的非线性结构，每个节点可以有多个子节点。而二叉树是一种特殊的树结构，每个节点最多只有两个子节点，分别称为左子节点和右子节点。子节点个数：树的节点可以有任意多个子节点，而二叉树的节点最多只有两个子节点。排列方式：树的子节点之间没有顺序关系，可以以任意方式排列。而二叉树的左子节点和右子节点有固定的顺序关系，左子节点在前，右子节点在后。联系：结构关系：二叉树是树的一种特殊情况，可以看作是每个节点最多只有两个子节点的树。因此，二叉树也是树的一种特殊结构。数据表示：树和二叉树都可以用多种方式进行表示，常见的表示方法有顺序存储和链