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

1、習(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é)點的操作是：(A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;(B) p->right=s; p-&

2、gt;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) abcde4. 判斷一個

3、循環(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)%m5. 數(shù)組Ai×j（1i8， 1 j 10）中每個元素的長度為3，從首地址LOCA開始，按行主存放，則元素A85的存儲地址為：(A) LOCA +141(B) LOCA +144(C) LOCA +222(D) LOCA +225二、填空題1. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D,R)，其中D是 的有限集合，R是D上 的有限集合。2. 數(shù)據(jù)邏輯結(jié)構(gòu)包括 、

4、 、 和 四種類型。3. 數(shù)組的第一個元素的存儲地址是100，每個元素的長度為2，則第50個元素的地址是 。4. 向一個長度為n的順序表的第i（1in+1）個元素之前插入一個元素，需向后移動 個元素。5. 設(shè)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,SubSt

5、ring(s,7,8)= ；三、 解答題1. 假設(shè)n為2的乘冪，并且n>2，是求下列算法的時間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）。int Time(int n) count=0; x=2; while(x<n/2) x*=2; count+; return(count)/Time2. 寫出稀疏矩陣 對應(yīng)的三元組表。3. 寫出教材P96頁上圖5.4(b)中三對角矩陣壓縮存儲時的下表變換公式。四、算法閱讀題1.指出以下算法中的錯誤和低效之處，并將它改寫為一個正確且高效的算法。Status DeleteK(SqList& a, int i, int k) /本過程從

6、順序表a中刪除第i個元素起的k個元素 if ( ) return INFEASIBLE;/參數(shù)不合法 else for (count=1; count<k; count+) /刪除一個元素 a.length-; return OK; /DeleteK 2. 簡述以下算法的功能。Status A (LinkedList L) /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; retu

7、rn OK; /A3. 簡述以下算法的功能。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); 五、算法設(shè)計題1. 試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表 (a1,a2,an) 逆置為 (an,an-1,a1)。2. 試寫一算法，對單鏈表實現(xiàn)就地逆置。3. 設(shè)有一個雙向鏈表，每個結(jié)點中除有 pre,data和next三個域外，還

8、增設(shè)了一個訪問頻度域freq。在鏈表被啟用之前，頻度域freq的值均初始化為0，而每當(dāng)對鏈表進(jìn)行一次Locate(L,x)操作后，被訪問結(jié)點（即元素值等于x的結(jié)點）的頻度域freq的值便增1，同時調(diào)整鏈表中結(jié)點之間的順序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結(jié)點總是靠近表頭結(jié)點。試編寫符合上述要求的Locate(L,x)操作的算法。4. 假設(shè)將循環(huán)隊列定義為：以變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試給出此循環(huán)隊列的隊滿條件，并寫出相應(yīng)的入隊和出隊的算法（在出隊的算法中要返回隊頭元素）。5. 編寫算法，求串s中所含不同字符的總數(shù)和每

9、種字符的個數(shù)。6. 編寫算法，從串s中刪除所有和串t相同的子串。7. 編寫算法，將線性表(a1,a2,an,b1,b2,bm)變?yōu)?b1,b2,bm,a1,a2,an)。習(xí)題課 一、選擇題1. 下列是完全二叉樹的是： (A) (C) (B) (D) 2. 下列二叉樹中序遍歷結(jié)果是：(A) abcdgef (B) dfebagc (C) dbaefcg (D) defbagc 3. 具有3個結(jié)點的二叉樹有： (A) 3種(B) 4種(C) 5種(D) 6種4. 從頂點a出發(fā)深度優(yōu)先遍歷下圖，可能的輸出序列是：(A) abdecf(B) abcdef(C) adcfeb(D) adecfb5.在有

10、序表1,4,8,15,31,46,62,69,78,80,82,99中折半查找關(guān)鍵字82，需比較的次數(shù)：(A) 2(B) 3(C) 4(D) 5二、填空題1. 深度為k的完全二叉樹至少有 個結(jié)點；至多有 個結(jié)點。2.一棵二叉樹，第i（i1）層最多有 個結(jié)點。3.N個頂點的連通圖至少 條邊。4.已知有向圖G用鄰接矩陣表示，則刪除所有從頂點i為弧尾的邊的方法是 5.長度為n的線性表，若進(jìn)行順序查找，則時間復(fù)雜度為 ；若進(jìn)行折半查找，則時間復(fù)雜度為 三、解答題1. 畫出具有三個結(jié)點的所有二叉樹。2. 畫出下列二叉樹的中序線索二叉樹（線索用虛線表示）。3. 為以集合5,4,18,6,12,7,10為權(quán)

11、值的結(jié)點構(gòu)造赫夫曼樹，并求其帶權(quán)路徑長度。4. 將下列樹轉(zhuǎn)換成二叉樹5. 寫出下圖的鄰接矩陣，并求其最小生成樹。6. 已知鄰接表如下所示，求其拓?fù)渑判颉?. 給定序列37,50,42,18,48,12,56,30,23 ，構(gòu)造二叉排序樹。當(dāng)刪除37后，畫出新的二叉排序樹。用該序列構(gòu)造平衡二叉樹。當(dāng)刪除37后，畫出新的平衡二叉樹。8. 給定關(guān)鍵字37,50,42,18,48,12,56,30,23，采用哈希函數(shù)H(key)=key MOD 13，采用現(xiàn)行探測再散列方法解決沖突，構(gòu)造哈希表，表長18。9. 下列關(guān)鍵字序列26,5,77,1,61,11,59,15用直接插入排序按升序排列，請寫出每一

12、趟排序結(jié)果。10. 下列關(guān)鍵字序列26,5,77,1,61,11,59,15用希爾排序按升序排列，請寫出每一趟排序結(jié)果。（d=5,3,1）。11. 下列關(guān)鍵字序列26,5,77,1,61,11,59,15用快速排序按升序排列，請寫出每一趟排序結(jié)果。12.下列關(guān)鍵字序列26,5,77,1,61,11,59,15用堆排序按升序排列，請寫出每一趟排序結(jié)果。13.下列關(guān)鍵字序列26,5,77,1,61,11,59,15用簡單選擇排序按升序排列，請寫出每一趟排序結(jié)果。14.下列關(guān)鍵字序列26,5,77,1,61,11,59,15用2路歸并排序按升序排列，請寫出每一趟排序結(jié)果。五、算法閱讀題1.下面程序?qū)?/p>

13、現(xiàn)二分查找算法 。請在空白處填寫適當(dāng)內(nèi)容，使該程序功能完整。Typedef struct KeyType key； InfoType otherinfo； SeqListN+1；int BinSearch(SeqList R, int n，KeyType K)  int low=1，high=n； while (    (1)    ) mid=(low+high)/2； if (    (2)    ) return mid； if (Rmid.key>K) high=mid-1； else     (3)    ； return 0；  /BinSearch 2. 已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，其類型定義如下： typedef struct NodeType DataType data; struct NodeType *lchild,*rchild; BinTNode,*BinTree;簡述算法f32的功能。BinTree f32(BinTree bt1) BinTree bt2; if(bt1=NULL) bt2=NULL; else bt2=(BinTNo