数据结构

第二章线性表一、选择题（1）两个有序线性表分别具有n个元素与m个元素且n≤m，现将其归并成一个有序表，其最少的比较次数是（A）。A．nB．mC．n−1D．m+n（2）非空的循环单链表head的尾结点（由p所指向）满足（C）。A．p-next==NULLB．p==NULLC．p-next==headD．p==head（3）在带头结点的单链表中查找x应选择的程序体是（ABC）。注：C最优A．node*p=head-next;while(p&&p-info!=x)p=p-next;if(p-info==x)returnpelsereturnNULL;B．node*p=head;while(p&&p-info!=x)p=p-next;returnp;C．node*p=head-next;while(p&&p-info!=x)p=p-next;returnp;D．node*p=head;while(p-info!=x)p=p-next;returnp;（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以（5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B）。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)（6）在一个长度为n的顺序表中删除第i个元素（1=i=n）时，需向前移动（A）个元素。A．n−iB．n−i+1C．n−i−1D．i（7）若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（A）。A．O(n)B．O(1)C．O(n2)D．O(n3)（8）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（B）。A．O(n)B．O(n2)C．O(n3)D．O(n×log2n)（9）下面哪个术语与数据的存储结构无关（D）。A．顺序表B．链表C．散列表D．队列（10）在一个单链表中，若删除p所指结点的后续结点，则执行（A）。A．p-next=p-next-next;B．p=p-next;p-next=p-next-next;C．p-next=p-next;D．p=p-next-next;（11）在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。A．s-next=p;p-next=s;B．s-next=p-next;p-next=s;C．s-next=p-next;p=s;D．p-next=s;s-next=p;二、设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。答案：voidinvent(Lnode*head){Lnode*p,*q;if(!head-next)returnERROR;p=head-next;q=p-next;p-next=NULL;while(q){p=q;q=q-next;p-next=head-next;head-next=p;}}三、设计一个算法，求一个带头结点单链表中的结点个数。答案：intL(head){node*head;intn=0;node*p;p=head;while(p!=NULL){p=p-next;n++;}return(n);}四、已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序。答案：voidInsert_sq(Sqlistva[],ElemTypex){inti,j,n;n=length(va[]);if(x=va[n-1])va[n]=x;else{i=0;while(xva[i])i++;for(j=n-1;j=i;j--)va[j+1]=va[j];va[i]=x;}n++;}或StatusInsert_SqList(SqList&va,intx){if(va.length+1va.listsize)returnERROR;va.length++;for(i=va.length-1;va.elem[i]x&&i=0;i--)(6分)va.elem[i+1]=va.elem[i];（2分）va.elem[i+1]=x;（2分）returnOK;}//Insert_SqList五、假设递增有序链表A、B分别表示一个集合，设计算法以求解C=A∩B，并分析算法的时间复杂度。LinkListunion(LinkListA,LinkListB){LinkListC,p,q,s,r;p=A-next;q=B-next;C=A;r=C;while(p&&q){if(p-data==q-data){r-next=p;r=p;p=p-next;q=q-next;}elseif(p-dataq-data)p=p-next;elseq=q-next;}r-next=NULLfree(B);returnC;}六、假设顺序表L中的元素按从小到大的次序排列，设计算法以删除表中重复的元素,并要求时间尽可能少。要求：（1）对顺序表（1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9）模拟执行本算法，并统计移动元素的次数。（2）分析算法的时间性能。将元素分成两个部分：已经处理元素和待处理元素。已经处理部分返回L中，用下标i指示最后一个元素，初始化i=0。待处理部分用下标j指示第一个元素，初始化j=1.左边下标小于i的元素已经处理好重复，等于i是当前正在处理的元素，将data[i]与data[j]进行比较，会出现下列情况：①data[i]==data[j]，说明j指示的是i的重复元素，继续处理j的下一个元素，即执行j++。②data[i]data[j]，说明j指示元素与i的元素不同，如果i+1!=j，将j元素复制到i+1，即：L.data[i+1]=L.data[j]，再执行j++，i++；若i+1==j，说明j是i的直接后继，无需复制，直接执行i++，j++。循环执行上述操作，直到表尾。修改L的长度为i+1。voidDeleteRepeatData(seqList&L){inti,j;//分别指向已处理部分最后元素和未处理部分第一个元素，皆为数组下标if(L.listLen2)return;//少于2个元素，直接退出i=0;//初始化i指向第一个元素j=1;//j指向第二个元素while(jL.listLen){if(L.data[i]==L.data[j])//j为重复元素，j后移j++;else//因为L递增，所以剩下情况即L.data[i]L.data[j]，j为目标元素{//如果j==i+1，说明j紧随i，无需移动元素，直接i++、j++即可if((i+1)!=j)L.data[i+1]=L.data[j];//j元素复制到i+1i++;//无论那种情况，都需要同时后移i、jj++;}}L.listLen=i+1;//修改表的实际长度}（2）算法的时间复杂度O(n)。第三章栈和队列一、选择题（1）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S的容量至少应该为（C）。A．6B．4C．3D．2（2）设栈的输入序列为1、2、3…n，若输出序列的第一个元素为n，则第i个输出的元素为（B）。A．不确定B．n−i+1C．ID．n−i（3）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行插入操作时（D）。A．仅修改队头指针B．仅修改队尾指针C．队头、队尾指针都要修改D．队头,队尾指针都可能要修改（4）队列是一种特殊的线性表，其特殊性在于（C）。A．插入和删除在表的不同位置执行B．插入和删除在表的两端位置执行C．插入和删除分别在表的两端执行D．插入和删除都在表的某一端执行（5）栈是一种特殊的线性表，具有（B）性质。A．先进先出B．先进后出C．后进后出D．顺序进出（6）顺序循环队列中（数组的大小为n），队头指示front指向队列的第1个元素，队尾指示rear指向队列最后元素的后1个位置，则循环队列中存放了n−1个元素，即循环队列满的条件为（B）。A．(rear+1)%n=front−1B．(rear+1)%n=frontC．(rear)%n=frontD．rear+1=front（7）顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（D）。A．5和1B．2和4C．1和5D．4和2二、写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);}结果：kac三、简述以下算法的功能（栈和队列的元素类型均为int）。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}队列里的元素逆序四、如果对循环队列采用设置运算标志的方法来区分队列的满和空的状态，试给出对应的各运算的实现。//将x插入至队尾if(Q.rear==Q.front&&Q.tag==1)returnfalse;Q.elem[Q.rear]=x;Q.rear=(Q.rear+1)%M;if(Q.rear==Q.front)Q.tag=1;returntrue;//删除队头元素if(Q.front==Q.rear&&Q.tag==0)returnfalse;x=Q.elem[Q.front];Q.front=(Q.front+1)%M;if(Q.front==Q.rear)Q.tag=0;returntrue;}五、对一个栈的输入序列a1,a2,a3,…,an，称由此栈依次出栈后所得到的元素序列为栈的合法输出序列。例如，假设栈S的一个输入序列为1,2,3,4,5，则可得到多个输出序列。例如，1,2,3,4,5就是一个合法的输出序列，同理，5,4,3,2,1和3,2,1,4,5也分别是其合法的输出序列。分别求解下列问题：（1）判断序列1,3,4,5,2是否是合法的输出序列。合法（2）对输入序列1,2,3,4,5，求出其所有的合法的输出序列。（提示：用公式计算）根据公式，图章节的前一页的公式，c(2n,n)-c(2n,n+1)排列组合知识。从而保证不会写漏。算法实现，感兴趣同学可以看：第四章串一、选择题1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（C）。A.连接B.求子串C.模式匹配D.判断子串2、已知串S=’aaab’，则next数组值为（A）。A.0123B.1123C.1231D.12113、串与普通的线性表相比较，它的特殊性体现在（C）。A.顺序的存储结构B.链式存储结构C.数据元素是一个字符D.数据元素任意4、设串长为n，模式串长为m，则KMP算法所需的附加空间为（A）。A.O(m)B.O(n)C.O(m*n)D.O(nlog2m)5、空串和空格串（B）。A.相同B.不相同C.可能相同D.无法确定6、与线性表相比，串的插入和删除操作的特点是（A）。A.通常以串整体作为操作对象B.需要更多的辅助空间C.算法的时间复杂度较高D.涉及移动的元素更多7、设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作