第二章线性表一、选择题（1）两个有序线性表分别具有 n 个元素与 m 个元素且n≤m，现将其归并成一个有序表，其最少的比较次数是（A）。

A．n B．m C．n−1 D．m+n（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head（3）在带头结点的单链表中查找 x 应选择的程序体是（ABC ）。

注：C最优A．node *p=head->next; while (p && p->info!=x) p=p->next;if (p->info==x)return p else return NULL;B．node *p=head; while (p&& p->info!=x) p=p->next; return p;C．node *p=head->next;while (p&&p->info!=x) p=p->next; return p;D．node *p=head; while (p->info!=x) p=p->next ; return p;（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−i B．n−i+1 C．n−i−1 D．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;二、设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。

答案：void invent(Lnode *head){Lnode *p,*q;if(!head->next) return ERROR;p=head->next; q=p->next; p->next =NULL;while(q){p=q; q=q->next; p->next=head->next; head->next=p;}}三、设计一个算法，求一个带头结点单链表中的结点个数。

答案：int L(head){node * head;int n=0;node *p;p=head;while(p!=NULL){ p=p->next;n++;}return(n);}四、已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为 x 的结点，使顺序表中的结点仍然是从小到大有序。

答案：void Insert_sq(Sqlist va[], ElemType x){int i, j, n;n=length(va[]);if(x>=va[n-1])va[n]=x;else{i=0;while(x>va[i]) i++;for(j=n-1;j>=i;j--)va[j+1]=va[j];va[i]=x; }n++;}或Status Insert_SqList(SqList &va,int x){if(va.length+1>va.listsize) return ERROR;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分）return OK;}//Insert_SqList五、假设递增有序链表A、B分别表示一个集合，设计算法以求解C= A∩B，并分析算法的时间复杂度。

LinkList union(LinkList A,LinkList B){ LinkList C, 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;}else if (p->data<q->data)p=p->next;else q=q->next;}r->next= NULLfree(B);return C;}六、假设顺序表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。

void DeleteRepeatData(seqList & L){int i,j; //分别指向已处理部分最后元素和未处理部分第一个元素，皆为数组下标if(L.listLen<2)return; //少于2个元素，直接退出i=0; //初始化i指向第一个元素j=1; //j指向第二个元素while(j<L.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．6 B．4 C．3 D．2（2）设栈的输入序列为 1、2、3… n，若输出序列的第一个元素为 n，则第 i 个输出的元素为（B ）。

A．不确定 B．n−i+1 C．I D．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−1 B．(rear+1)%n=frontC．(rear)%n=front D．rear+1=front（7）顺序循环队列中（数组的大小为 6），队头指示 front 和队尾指示 rear 的值分别为 3和 0，当从队列中删除 1 个元素，再插入 2 个元素后，front 和 rear 的值分别为（D ）。

A．5 和 1 B．2 和 4 C．1 和 5 D．4 和 2二、写出下列程序段的输出结果（栈的元素类型SElem Type为char）。

void main( ){Stack S;char x,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);} 结果：k a c三、简述以下算法的功能（栈和队列的元素类型均为int）。

void algo3(Queue &Q){Stack S; int d;InitStack(S);while(!QueueEmpty(Q)){DeQueue (Q,d); Push(S,d);};while(!StackEmpty(S)){Pop(S,d); EnQueue (Q,d);}} 队列里的元素逆序四、如果对循环队列采用设置运算标志的方法来区分队列的满和空的状态，试给出对应的各运算的实现。