數(shù)據(jù)結(jié)構(gòu)習(xí)題Exercises-I

習(xí)題課Ⅰ選擇題1.設(shè)有以下三個函數(shù)：

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.在循環(huán)鏈表的p指針?biāo)附Y(jié)點之后插入s指針?biāo)附Y(jié)點的操作是：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√棧的特點是先進后出，每次出棧元素一定為棧頂元素。因此，此題中，通過出棧元素可判斷出棧內(nèi)現(xiàn)有元素是哪些，以及哪些元素尚未入棧。對于棧內(nèi)元素來說，先入棧的不可能比后入棧的早出來。4.判斷一個循環(huán)隊列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.數(shù)組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.數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D,R)，其中D是

的有限集合，R是D上

的有限集合。2.數(shù)據(jù)邏輯結(jié)構(gòu)包括

、

、

和

四種類型。3.數(shù)組的第一個元素的存儲地址是100，每個元素的長度為2，則第50個元素的地址是

。數(shù)據(jù)元素關(guān)系線性結(jié)構(gòu)集合樹形結(jié)構(gòu)4.向一個長度為n的順序表的第i（1≤i≤n+1）個元素之前插入一個元素，需向后移動

個元素。圖狀結(jié)構(gòu)LOC50=100+(50-1)*2=198198n-i+15.設(shè)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.假設(shè)n為2的乘冪，并且n>2，是求下列算法的時間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）。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.寫出稀疏矩陣對應(yīng)的三元組表。ijv01381212233-13345mu=4,nu=4,tu=43.寫出教材P96頁上圖5.4(b)中三對角矩陣壓縮存儲時的下表變換公式。算法閱讀題1.指出以下算法中的錯誤和低效之處，并將它改寫為一個正確且高效的算法。StatusDeleteK(SqList&a,inti,intk){//本過程從順序表a中刪除第i個元素起的k個元素

if()returnINFEASIBLE;//參數(shù)不合法

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];正確的參數(shù)值：0<i<=a.length

且0<=k<=a.length-1元素前移次序錯誤。每次刪除一個元素太低效。2.簡述以下算法的功能。StatusA(LinkedListL){//L是無表頭結(jié)點的單鏈表

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//至少有一個結(jié)點//p指向第二個結(jié)點//移動p到表尾//q指向第一個結(jié)點//斷開q所指結(jié)點與其后繼的鏈接//p所指結(jié)點的后繼變?yōu)閝所指結(jié)點//L指針后移一個結(jié)點將鏈表中第一個結(jié)點變?yōu)樽詈笠粋€結(jié)點。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中的元素逆置。算法設(shè)計題1.試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表(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.試寫一算法，對單鏈表實現(xiàn)就地逆置。思想：將單鏈表中的頭結(jié)點與第一個元素結(jié)點斷開，即令頭結(jié)點的指針域為空，先形成一個空表。然后，將原鏈表中各結(jié)點依次插入這個空表的頭部，即令每個插入的結(jié)點成為第一個元素結(jié)點。3.設(shè)有一個雙向鏈表，每個結(jié)點中除有pre,data和next三個域外，還增設(shè)了一個訪問頻度域freq。在鏈表被啟用之前，頻度域freq的值均初始化為0，而每當(dāng)對鏈表進行一次Locate(L,x)操作后，被訪問結(jié)點（即元素值等于x的結(jié)點）的頻度域freq的值便增1，同時調(diào)整鏈表中結(jié)點之間的順序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結(jié)點總是靠近表頭結(jié)點。試編寫符合上述要求的Locate(L,x)操作的算法。算法核心部分：步驟1：從表頭開始順序查找x；步驟2：當(dāng)找到x時，將其freq域增1；否則，返回ERRO，算法終止。步驟3：從x開始，逆序與各結(jié)點的freq域比較，當(dāng)x的freq域值小于某結(jié)點的freq域值時，便將x插入到該結(jié)點的后面，并返回OK，算法終止。4.假設(shè)將循環(huán)隊列定義為：以變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試給出此循環(huán)隊列的隊滿條件，并寫出相應(yīng)的入隊和出隊的算法（在出隊的算法中要返回隊頭元素）。設(shè)隊列最大長度為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中所含不同字符的總數(shù)和每種字符的個數(shù)。6.編寫算法，從串s中刪除所有和串t相同的子