【正文】 7. 二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（ ）根結(jié)點(diǎn)的值。return(1)。} } r[i]=x。 r[j]%2==0) j=j1。 sum(btlchild,s)。 入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)時不需要考慮棧溢出的情況。 用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。 若一個葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點(diǎn)。 對鏈表進(jìn)行插入和刪除操作時不必移動鏈表中結(jié)點(diǎn)。7． 7． 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_________排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇________排序。 (A) 小于等于m的最大奇數(shù) (B) 小于等于m的最大素?cái)?shù) (C) 小于等于m的最大偶數(shù) (D) 小于等于m的最大合數(shù)9．設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（ ）個。一、選擇題(30分)1．下列程序段的時間復(fù)雜度為（ ）。padjvertex=j。for(i=0。int adjvertex。count){ if(bt!=0) {count++。 t=(bitree *)malloc(sizeof(bitree))，bstinsert(trchild,k)3. 3.一、選擇題1．C 2．C 3．C 4．B 5．B6．C 7．B 8．C 9．A 10．A 設(shè)連通圖G中有n個頂點(diǎn)e條邊，則對應(yīng)的最小生成樹上有___________條邊。7． 7．tlchild=trchild=0。 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹中插入一個新結(jié)點(diǎn)，請?jiān)谙聞澗€處填上正確的內(nèi)容。 向二叉排序樹中插入一個結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹的高度。（ ）5. 5. struct node *lchild,*rchild。else { for(i=start1,j=0。 s=p。 if(head==0 ||headnext==0) return。 設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。3. 3.i=i+1。void quickpass(struct record r[], int s, int t, int amp。10. 10.9. 9.8. 8.7. 7.6. 6.5. 5.4. 4.3. 3.2. 2.三、填空題(30分)1. 1.（ ）4．完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。 (A) top=top+1。 (A) n (B) n1 (C) 2n (D) 2n13．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（ ）。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，804．（ ）二叉排序樹可以得到一個從小到大的有序序列。 (B) top=top1。（ ）5．哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。i){ int j=t。} while (____________________) i=i+1。 ij amp。 for(q=head。} if(s!=q){t=sdata。 istart+count1。}bitree。（ ）6. 6. 如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點(diǎn)的出度為零。 稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。typedef struct node{int data。}else if (tdatak) bstinsert(tlchild,k)。 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點(diǎn)中的兩個指針域分別為llink和rlink）。10． 10．二、判斷題1．對 2．錯 3．對 4．錯 5．錯6．對 7．對 8．對 9．對 10．對 (49，13，27，50，76，38，65，97)2. 2. n110. 10. countnode(btlchild,count)。 struct node1 *nextarc。i=n1。pnextarc=g[i].firstarc。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．設(shè)順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動（ ）個元素。 (A) 4 (B) 5 (C) 6 (D) 7，則該完全無向圖中有（ ）條邊。 對一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為__________，在整個排序過程中最多需要進(jìn)行__________趟排序才可以完成。6． 6．三、判斷題(20分)1． 1．( )3． 3．( )5． 5．( )7． 7．( )9． 9． sum(btrchild,s)。 if (ij) {r[i]=r[j]。}3． 3．}數(shù)據(jù)結(jié)構(gòu)試卷（十四） (A) (B) (C) = (D) !=8. 設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（ ）。2. 2. 快速排序算法的平均時間復(fù)雜度為____________，直接插入排序算法的平均時間復(fù)雜度為___________。 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結(jié)果為______________________。bt){scanf(“%c”,amp。createbitree(btrchild)。} lklist。if(i==1)head=q=p。2． 2．三、算法設(shè)計(jì)題1. 1. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。}。 else snext=ha。void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j1]。 單選題（每題 2 分，共20分）1. 1. D. HL=p。 若需要利用形參直接訪問實(shí)參時，應(yīng)將形參變量說明為（ ）參數(shù)。2. 2.3. 3.4. 4.5. 5.W中第6 行的元素和第4 列的元素共占用＿_(dá)______＿個字節(jié)。其余類推，則A[ i ]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用________________________排序。四、 四、 while (++i=x) if (n%i==0) break。 InitQueue(Q)。 if(!visited[j]) { coutj39。 算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。六、 六、3. 3. DFS：????… BFS：???…? 4. 4. 拓樸排序?yàn)椋?4 3 6 5 7 2 1 四、 四、 編寫算法（8分）ElemType DeleFront(LNode * amp。} 棧和隊(duì)列的共同特點(diǎn)是( )。5. 5.在這種存儲結(jié)構(gòu)中，n個結(jié)點(diǎn)的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。 對于一個具有n個頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_______個和________個。 AOV網(wǎng)是一種___________________的圖。 在一個具有n個頂點(diǎn)的無向完全圖中，包含有________條邊，在一個具有n個頂點(diǎn)的有向完全圖中，包含有________條邊。 假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為________，整個堆排序過程的時間復(fù)雜度為________。 運(yùn)算題（每題 6 分，共24分）1. 1. A 0 1 2 3 4 5 6 7 data 閱讀算法（每題7分，共14分）1. 1.五、 五、 }//if} 填空題（每空1分，共26分）1. 1. O(n)3. 3. 1 3 4 X * + 2 Y * 3 / 5. 5. e 2e7. 7. n(n1)/2 n(n1)9. 9. 線性表為：（78，50，40，60，34，90）2. 2. 用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4.//i為計(jì)數(shù)器 while(p!=NULL) { if (Pdata==x) i++。 s→link=p。 棧的插入和刪除操作在（ ）進(jìn)行。datanext圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時四、 四、鄰接表表示時 在對m階的B_樹插入元素的過程中，每向一個結(jié)點(diǎn)插入一個索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于______個，則必須把它分裂為_______個結(jié)點(diǎn)。 假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J））），則樹中所含的結(jié)點(diǎn)數(shù)為_________個，樹的深度為_________,樹的度為________, 結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為________,孩子結(jié)點(diǎn)為_______________ 。 用具有n個元素的一維數(shù)組存儲一個循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的___________，該循環(huán)隊(duì)列的最大長度為__________。 一種抽象數(shù)據(jù)類型包括______________和_____________兩個部分。 s→link =p。A n B n/2 C (n+1)/2 D (n1)/2 在一個單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個s所指的結(jié)點(diǎn),則執(zhí)行( )。 }//while, 出循環(huán)時i中的值即為x結(jié)點(diǎn)個數(shù) return i。 算法填空（共8分）二叉搜索樹的查找——遞歸算法:bool Find(BTreeNode* BST,ElemTypeamp。 已知一個圖的頂點(diǎn)集V和邊集E分別為： V={1,2,3,4,5,6,7}。 圖10請畫出圖10的鄰接矩陣和鄰接表。40next357204 樹最適合用來表示( )。數(shù)據(jù)結(jié)構(gòu)（十六）一、exit(1)。 快速 歸并三、 三、 2i+1 2i+2 (i1)/211. 11. 單選題（每題2分，共20分） 二、 二、 編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。