数据结构习题Exercises-I.pptVIP

习题课 Ⅰ 选择题 1. 设有以下三个函数： f(n)=21n4+n2+1000, g(n)=15n4+500n3, h(n)=5000n3.5+nlogn 下列断言正确的有： (A) f(n)是O(g(n)) (B) h(n)是O(f(n)) (C) g(n)是O(h(n)) (D) h(n)是O(n3.5) (E) h(n)是O(nlogn) 2. 在循环链表的p指针所指结点之后插入s指针所指结点的操作是： p-right=s; s-left=p; p-right-left=s; s-right=p-right; (B) p-right=s; p-right-left=s; s-left=p; s-right=p-right; (C) s-left=p; s-right=p-right; p-right=s; p-right-left=s; (D) s-left=p; s-right=p-right; p-right-left=s; p-right=s; 3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是： (A) edcba (B) decba (C) dceab (D) abcde 4. 判断一个循环队列Q（最多可容m个元素）为满队列的条件是： (A) Q.front == Q.rear (B) Q.front != Q.rear (C) Q.front == (Q.rear+1)%m (D) Q.front != (Q.rear+1)%m 5. 数组Ai×j（1≤i≤8， 1≤ j ≤10）中每个元素的长度为3，从首地址LOCA开始，按行主存放，则元素A[8][5]的存储地址为： (A) LOCA +141 (B) LOCA +144 (C) LOCA +222 (D) LOCA +225 填空题 1. 数据结构被形式地定义为(D,R)，其中D是 的有限集合，R是D上 的有限 集合。 5. 设s=I AM A STUDENT，t=GOOD，q=WORKER，则： StrLength(s)= ； SubString(s,8,7)= ； Index(s, A)= ； Replace(s, STUDENT,q)= ； Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))= ； 解答题 1. 假设n为2的乘幂，并且n2，是求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。 int Time(int n) { count=0; x=2; while(xn/2) { x*=2; count++; } return(count) }//Time 2. 写出稀疏矩阵 对应的三元组表。 3. 写出教材P96页上图5.4(b)中三对角矩阵压缩存储时的下表变换公式。 算法阅读题 1. 指出以下算法中的错误和低效之处，并将它改写为一个正确且高效的算法。 2. 简述以下算法的功能。 Status A (LinkedList L) { //L是无表头结点的单链表 if (L L-next) { q=L; L=L-next; p=L; while (p-next) p=p-next; p-next=q; q-next=NULL; } return OK; } //A 3. 简述以下算法的功能。 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); } } 算法设计题 1. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表 (a1,a2,…,an) 逆置为 (an,an-1,