数据结构习题Exercises-I

习题课Ⅰ选择题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√LOCA+(10*(8-1)+(5-1))*3填空题1.数据结构被形式地定义为(D,R)，其中D是

的有限集合，R是D上

的有限集合。2.数据逻辑结构包括

、

、

和

四种类型。3.数组的第一个元素的存储地址是100，每个元素的长度为2，则第50个元素的地址是

。数据元素关系线性结构集合树形结构4.向一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动

个元素。图状结构LOC50=100+(50-1)*2=198198n-i+15.设s='I

AMASTUDENT'，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)))=

；14'STUDENT'3'IAMAWORKER''AGOODSTUDENT'解答题1.假设n为2的乘幂，并且n>2，是求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。int

Time(intn){count=0;x=2;

while(x<n/2){x*=2;count++;}

return(count)}//Timex=2count+1=n/2count=log2n-2O(log2n)2.写出稀疏矩阵对应的三元组表。ijv01381212233-13345mu=4,nu=4,tu=43.写出教材P96页上图5.4(b)中三对角矩阵压缩存储时的下表变换公式。算法阅读题1.指出以下算法中的错误和低效之处，并将它改写为一个正确且高效的算法。StatusDeleteK(SqList&a,inti,intk){//本过程从顺序表a中删除第i个元素起的k个元素

if()returnINFEASIBLE;//参数不合法

elsefor(count=1;count<k;count++){//删除一个元素

a.length--;}returnOK;}//DeleteK

i<1||k<0||i+k>a.lengthfor(j=a.length;j>=i+1;j--)a.elem[j-1]=a.elem[j];i<1||k<0||i+k>a.lengthfor(j=a.length;j>=i+1;j--)a.elem[j-1]=a.elem[j];正确的参数值：0<i<=a.length

且0<=k<=a.length-1元素前移次序错误。每次删除一个元素太低效。2.简述以下算法的功能。StatusA(LinkedListL){//L是无表头结点的单链表

if(L&&L->next){q=L;L=L->next;p=L;while(p->next)p=p->next;p->next=q;q->next=NULL;}returnOK;}//A//至少有一个结点//p指向第二个结点//移动p到表尾//q指向第一个结点//断开q所指结点与其后继的链接//p所指结点的后继变为q所指结点//L指针后移一个结点将链表中第一个结点变为最后一个结点。3.简述以下算法的功能。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);}}将队Q中的元素逆置。算法设计题1.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。思想：将a1与an交换；a2与an-1交换；依此类推。for(i=1,j=0;i<j;i++,j--){t=a[i];a[i]=a[j];a[j]=t}2.试写一算法，对单链表实现就地逆置。思想：将单链表中的头结点与第一个元素结点断开，即令头结点的指针域为空，先形成一个空表。然后，将原链表中各结点依次插入这个空表的头部，即令每个插入的结点成为第一个元素结点。3.设有一个双向链表，每个结点中除有pre,data和next三个域外，还增设了一个访问频度域freq。在链表被启用之前，频度域freq的值均初始化为0，而每当对链表进行一次Locate(L,x)操作后，被访问结点（即元素值等于x的结点）的频度域freq的值便增1，同时调整链表中结点之间的顺序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate(L,x)操作的算法。算法核心部分：步骤1：从表头开始顺序查找x；步骤2：当找到x时，将其freq域增1；否则，返回ERRO，算法终止。步骤3：从x开始，逆序与各结点的freq域比较，当x的freq域值小于某结点的freq域值时，便将x插入到该结点的后面，并返回OK，算法终止。4.假设将循环队列定义为：以变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队和出队的算法（在出队的算法中要返回队头元素）。设队列最大长度为M，则队满条件为：

Q.length==M入队：Q.base[(Q.rear+1)%M]=e;Q.length+=1出队：e=Q.base[(Q.rear+M-Q.length+1)%M];

Q.length-=15.编写算法，求串s中所含不同字符的总数和每种字符的个数。6.编写算法，从串s中删除所有和串t相同的子