數據結構試題及答案免費-文庫吧

【正文】 p指向雙向鏈表中的第一個結點，則指針變量p和指針變量head之間的關系是p=_________和head=__________（設結點中的兩個指針域分別為llink和rlink）。5． 5． 設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。6． 6． 完全二叉樹中第5層上最少有__________個結點，最多有_________個結點。7． 7． 設有向圖中不存在有向邊Vi,Vj，則其對應的鄰接矩陣A中的數組元素A[i][j]的值等于____________。8． 8． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結束后的結果為_____________________________。9． 9． 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有___________條邊。10． 10． 設有一組初始記錄關鍵字序列為(50，16，23，68，94，70，73)，則將它們調整成初始堆只需把16與___________相互交換即可。四、算法設計題(20分)1. 1. 設計一個在鏈式存儲結構上統計二叉樹中結點個數的算法。2. 2. 設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。數據結構試卷（12）參考答案一、選擇題1．C 2．C 3．C 4．B 5．B6．C 7．B 8．C 9．A 10．A二、判斷題1．對 2．錯 3．對 4．錯 5．錯6．對 7．對 8．對 9．對 10．對三、填空題1. 1. (49，13，27，50，76，38，65，97)2. 2. t=(bitree *)malloc(sizeof(bitree))，bstinsert(trchild,k)3. 3. pnext=s4. 4. headrlink，pllink5. 5. CABD6. 6. 1，167. 7. 08. 8. (13，27，38，50，76，49，65，97)9. 9. n110. 10. 50四、算法設計題1. 1. 設計一個在鏈式存儲結構上統計二叉樹中結點個數的算法。void countnode(bitree *bt,int amp。count){ if(bt!=0) {count++。 countnode(btlchild,count)。 countnode(btrchild,count)。}}2. 2. 設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。typedef struct {int vertex[m]。 int edge[m][m]。}gadjmatrix。typedef struct node1{int info。int adjvertex。 struct node1 *nextarc。}glinklistnode。typedef struct node2{int vertexinfo。glinklistnode *firstarc。}glinkheadnode。void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){int i,j。 glinklistnode *p。for(i=0。i=n1。i++) g2[i].firstarc=0。for(i=0。i=n1。i++) for(j=0。j=n1。j++)if ([i][j]==1){p=(glinklistnode *)malloc(sizeof(glinklistnode))。padjvertex=j。pnextarc=g[i].firstarc。 g[i].firstarc=p。p=(glinklistnode *)malloc(sizeof(glinklistnode))。padjvertex=i。pnextarc=g[j].firstarc。 g[j].firstarc=p。}}數據結構試卷（13）一、選擇題(30分)1．下列程序段的時間復雜度為（ ）。for(i=0； im； i++) for(j=0； jt； j++) c[i][j]=0；for(i=0； im； i++) for(j=0； jt； j++) for(k=0； kn； k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]； (A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)2．設順序線性表中有n個數據元素，則刪除表中第i個元素需要移動（ ）個元素。 (A) ni (B) n+l i (C) n1i (D) i3．設F是由TT2和T3三棵樹組成的森林，與F對應的二叉樹為B，TT2和T3的結點數分別為NN2和N3，則二叉樹B的根結點的左子樹的結點數為（ ）。 (A) N11 (B) N21 (C) N2+N3 (D) N1+N34．利用直接插入排序法的思想建立一個有序線性表的時間復雜度為（ ）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)5．設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為（ ）。 (A) pright=s； sleft=p； prightleft=s； sright=pright； (B) sleft=p；sright=pright；pright=s； prightleft=s； (C) pright=s； prightleft=s； sleft=p； sright=pright； (D) sleft=p；sright=pright；prightleft=s； pright=s；6．下列各種排序算法中平均時間復雜度為O(n2)是（ ）。 (A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序7．設輸入序列…、n經過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（ ）。 (A) ni (B) n1i (C) n+l i (D) 不能確定8．設散列表中有m個存儲單元，散列函數H(key)= key % p，則p最好選擇（ ）。 (A) 小于等于m的最大奇數 (B) 小于等于m的最大素數 (C) 小于等于m的最大偶數 (D) 小于等于m的最大合數9．設在一棵度數為3的樹中，度數為3的結點數有2個，度數為2的結點數有1個，度數為1的結點數有2個，那么度數為0的結點數有（ ）個。 (A) 4 (B) 5 (C) 6 (D) 7，則該完全無向圖中有（ ）條邊。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) (n1)/2，則順序查找的平均比較次數為（ ）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n1)/2(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經過（ ）次比較。 (A) 1 (B) 2 (C) 3 (D) 4，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（ ）。 (A) 6 (B) 11 (C) 5 (D) ={1，2，2，3，3，4，1，4}，則下列屬于該有向圖G的一種拓撲排序序列的是（ ）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為（ ）。 (A) 4 (B) 5 (C) 6 (D) 7二、填空題(30分)1． 1． 設指針p指向單鏈表中結點A，指針s指向被插入的結點X，則在結點A的前面插入結點X時的操作序列為：1) snext=___________；2) pnext=s；3) t=pdata；4) pdata=___________；5) sdata=t；2． 2． 設某棵完全二叉樹中有100個結點，則該二叉樹中有______________個葉子結點。3． 3． 設某順序循環隊列中有m個元素，且規定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環隊列中最多存儲_______隊列元素。4． 4． 對一組初始關鍵字序列（40，50，95，20，15，70，60，45，10）進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數為__________，在整個排序過程中最多需要進行__________趟排序才可以完成。5． 5． 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選擇_________排序，如果從節省存儲空間的角度來考慮則最好選擇________排序。6． 6． 設一組初始記錄關鍵字序列為(20，12，42，31，18，14，28)，則根據這些記錄關鍵字構造的二叉排序樹的平均查找長度是_______________________________。7． 7． 設一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。8． 8． 設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為13210，根據這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的高度為________________。9． 9． 設一組記錄關鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_______________________。10． 10． 設無向圖G（如右圖所示），則其最小生成樹上所有邊的權值之和為_________________。三、判斷題(20分)1． 1． 有向圖的鄰接表和逆鄰接表中表結點的個數不一定相等。( )2． 2． 對鏈表進行插入和刪除操作時不必移動鏈表中結點。( )3． 3． 子串“ABC”在主串“AABCABCD”中的位置為2。( )4． 4． 若一個葉子結點是某二叉樹的中序遍歷序列的最后一個結點，則它必是該二叉樹的先序遍歷序列中的最后一個結點。( )5． 5． 希爾排序算法的時間復雜度為O(n2)。( )6． 6． 用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數無關而與圖中邊數有關。( )7． 7． 中序遍歷一棵二叉排序樹可以得到一個有序的序列。( )8． 8． 入棧操作和入隊列操作在鏈式存儲結構上實現時不需要考慮棧溢出的情況。( )9． 9． 順序表查找指的是在順序存儲結構上進行查找。（ ）10． 10．堆是完全二叉樹，完全二叉樹不一定是堆。（ ）五、算法設計題(20分)1． 1． 設計計算二叉樹中所有結點值之和的算法。2． 2． 設計將所有奇數移到所有偶數之前的算法。3． 3． 設計判斷單鏈表中元素是否是遞增的算法。數據結構試卷（13）參考答案一、選擇題1．A 2．A 3．A 4．C 5．D6．D 7．C 8．B 9．C 10．A11．C 12．C 13．D 14．A 15．A二、填空題1. 1. pnext，sdata2. 2. 503. 3. m14. 4. 6，85. 5. 快速，堆6. 6. 19/77. 7. CBDA8. 8. 69. 9. (24，65，33，80，70，56，48)10. 10. 8三、判斷題1．錯 2．對 3．對 4．對 5．錯6．錯 7．對 8．對 9．錯 10．對四、算法設計題1． 1． 設計計算二叉樹中所有結點值之和的算法。void sum(bitree *bt,int amp。s){ if(bt!=0) {s=s+btdata。 sum(btlchild,s)。 sum(btrchild,s)。} }2． 2． 設計將所有奇數移到所有偶數之前的算法。void quickpass(int r[], int s, int t){ int i=s,j=t,x=r[s]。 while(ij){ while (ij amp。amp。 r[j]%2==0) j=j1。 if (ij) {r[i]=r[j]。i=i+1。} while (ij amp。amp。 r[i]%2==1) i=i+1。 if (ij) {r[j]=r[i]。j=j1。} } r[i]=x。}3． 3． 設計判斷單鏈表中元素是否是遞增的算法。int isriselk(lklist *head){if(head==0||headnext==0) return(1)。elsefor(q=head,p=headnext。 p!=0。 q=p,p=pnext)if(qdatapdata) return(0)。return(1)。}數據結構試卷（十四）一、選擇題(24分)1．下列程序段的時間復雜度為（ ）。i=0，s=0； while (sn) {s=s+i；i++；} (A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)2．設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（ ）存儲方式最節省運算時間。 (A) 單向鏈表 (B) 單向循環鏈表(C) 雙向鏈表 (D)