【正文】 return NULL。( )7．哈希表的查找效率主要取決于哈希建表時所選取的哈希函數(shù)和處理沖突的方法。8．設(shè)鍵值序列為{k1，k2，…，kn}，建堆和排序全過程共需進行____________次堆調(diào)整。 4．快速排序為什么是不穩(wěn)定的排序?試舉例說明。6．下面程序段的時間復(fù)雜度為( )。( )5．即使某排序算法是不穩(wěn)定的，但該方法仍有實際應(yīng)用價值。四、應(yīng)用題(20分)1．依次輸入集合{20，13，22，5，16，3，48，24}中的鍵值，得到一棵二叉排序樹，試畫出該二叉排序樹并求出在等概率下成功查找的平均查找長度。j++)for(k=0。 pnextprior=s。 3．假定對線性表R[059]進行分塊查找，共分10塊，每塊長度等于6。2．已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫出這棵二叉樹。 (A)3 (B)4 (C)5 (D)68．設(shè)一棵二叉樹共有50個葉子結(jié)點(終端結(jié)點)，則共有( )個度為2的結(jié)點 (A)25 (B)49 (C)50 (D)51二、填空題(每題2分，共16分)1．一個算法，如果不論問題規(guī)模大小，運行所需時間都一樣，則該算法的時間復(fù)雜度是_____________。( )四、簡答題(共38分)1．排序(1)寫出線性表(26，45，12，z0，30，5，15，29，16，2，18)采用基數(shù)排序后，第一趟結(jié)束時的結(jié)果。return 1。 s[i]!=0amp。 (A) front==rear (B) (rear+1)%MAXSIZE==front (C) frontrear==1 (D) rear%MAXSIZE==front6．設(shè)有1000個元素，用折半查找時，最小比較次數(shù)為( )。 6．如果一個有向圖有5個頂點，則最多有___________________條弧。 /* 等于隊尾元素的下標(biāo)加1 */}QUEUE。 k++) if(aelem[k]==x) break。 *rchild。（ ）2．快速排序法在最好的情況下的時間復(fù)雜度是O(n)。(5分)2．(1)給出右圖所示樹的后序遍歷結(jié)果。 i) { for(j=1。}3．下列算法是輸出一顆二叉樹的第i層的所有結(jié)點的值，假定根結(jié)點是第1層。 (A)102 (B)105 (C)106 (D)1082．森林轉(zhuǎn)換為二叉樹后，從根結(jié)點開始一直沿著右子樹下去，一共有4個結(jié)點，表明( )。8．一個無序的順序表不能采用折半查找法進行查找。(4分)5．用Kruskal算法(一條邊一條邊地加入生成樹)求右下圖的最小生成樹。}}return head。}SQ。 (A)單鏈表 (B)雙向鏈表 (C)單循環(huán)鏈表 (D)順序表2．串的長度是( )。( )6．一棵二叉樹的中序遍歷序列與該二叉樹轉(zhuǎn)換成森林的后序遍歷序列相同。3．已知一有向圖如下圖所示，試畫出從A點出發(fā)的深度優(yōu)先生成樹。 ／* 下標(biāo)初始化，A、B、C的下標(biāo)都從1開始 */ while(i= amp。struct node *left。 /* 遞歸調(diào)用 */ p(w1)。 ／* 找不到該元素 *／}2．以下算法將元素遞增排列的順序存儲線性表A和B的元素的交集存人線性表C中。 7．具有M個頂點的連通圖至少有___________條邊，而具有M個頂點的強連通圖則至少有_____________條邊。( ) 2．已知指針p指向鏈表L中的某結(jié)點，執(zhí)行語句p＝p一＞next不會刪除該鏈表中的結(jié)點。 (7分)typedef struct LinkNode{int data。}3．以下算法是將線性表L中所有負數(shù)元素刪除，返回被刪除的元素個數(shù)。 pfnext!=p。(5分) 3．假設(shè)字符a，b，c，d，e，寫出a，b，c，d，e，f的Huffman編碼。( )5．二叉樹的先序遍歷不可能與中序遍歷相同。(7分)typedef struct { int elem[100]。for(p=head。完成程序。6．一個數(shù)組的長度為20，用于存放一個循環(huán)隊列，則隊列最多只能有__________個元素。 (A) O(n) (B) O(n2) (C) O(log2n) (D) O(nlog2n)7．如果一棵樹有10個葉子結(jié)點，則該樹總共至少有( )個結(jié)點。 printf(%d, pdata)。 int ins(SQ *a, int x, int y) { int k,i。完成以下程序。2．已知某算法的執(zhí)行時間為(n+n2)/2+log2 (2n+1)，n 為問題規(guī)模，則該算法的時間復(fù)雜度是________________。模擬試題7一、選擇題(每小題1分，共8分)1．如果樹的結(jié)點A有4個兄弟，而且B為A的雙親，則B的度為( )。 return 。 /* 棧頂元素的下標(biāo) */}STACK。4．Huffman樹沒有度為1的結(jié)點。 (A)5 (B)6 (C)7 (D)8 4．具有20個結(jié)點的二叉樹，其深度最大為( )。( )9．按中序遍歷一棵二叉排序樹所得到的中序遍歷序列是一個遞增序列10．進棧操作push(x，s)作用子鏈接棧時，無需判滿。 (A)1 (B)2 (C)3 (D)413．在順序存儲的線性表R[029]上進行順序查找的平均查找長度為(①)，進行二分查找的平均查找長度為(②)，講行分塊查找（設(shè)分為5塊)的平均查找長度為(③) ①(A)15 (B)15．5 (C)16 (D)20 ②(A)4 (B)62／15 (C)64／15 (D)25／6 ③(A)6 (B)11 (C)5 (D)6．514．在所有排序方法中，關(guān)健碼的比較次數(shù)與記錄的初始排列無關(guān)的是( )。 snext=pnext。for(i=0。5．設(shè)鏈值序列為{K1,K2,…,Kn}，用篩選法建堆必須從第__________個元素開始篩選。 (B)p＝p一＞next (C)p＝p一＞next一＞next (D)P一＞next＝p二、判斷題(10分)1．具有線性序關(guān)系的集合中，若a，b是集合中的任意兩個元素，則必有ab的關(guān)系。( )模擬試題4一、選擇題(20分)1．n個頂點的無向圖的鄰接表中結(jié)點總數(shù)最多有( )個。 }while(________________)。4．設(shè)有一個空棧，現(xiàn)輸入序列為l，2，3，4，5，經(jīng)過Push，Push，Pop，Push，Pop，Push，Pop，Push后，輸出序列為__________________ 。( )3．設(shè)有兩個串p和q．其中q是p的子串，把q在p中首次出現(xiàn)的位置作為q在p中的位置的算法稱為匹配。5．模式中“ababbabbab”的前綴函數(shù)為________________。( )8．不論adt棧是用數(shù)組實現(xiàn)，還是用指針實現(xiàn)，Pop(s)與Push(x,s)的時間復(fù)雜度均O(n)。 9．已知一棵二叉樹的中序遍歷結(jié)果為DBHEAFICG，后序遍歷結(jié)果為DHEBIFGCA，畫出該二又樹___________________。 (A)‘BCQR’ (B)‘BCDEF’ (C)‘BCDEFG’ (D)‘BCDEFEF’ 8．設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第1個元素，其存儲地址為1，每個元素占用1個地址空間，則a85的地址為( )。3．給定一個整數(shù)集合{3，5，6，9，12}，畫出其對應(yīng)的一棵Huffman樹__________4．在雙向循環(huán)鏈表中，在指針p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作為________________5．下面為樸素的模式匹配算法，請在算法的下劃線處填上正確的子句int index(s,t)string *s，*t。（4分） 4．何謂隊列的“假溢”現(xiàn)象？如何解決?(4分)四、算法設(shè)計(38分) 1．試寫出求二又樹結(jié)點數(shù)目的算法。 (A)必須是連續(xù)的 (B)部分地址必須是連續(xù)的 (c)一定是不連續(xù)的 (D)連續(xù)與否均可以3．設(shè)循環(huán)隊列Q[l…n—1]的首尾指針為f和r，當(dāng)插入元素時尾指針r加1，首指針F總是指在隊列中第一個元素的前一個位置，則隊列中元素計數(shù)為( )。 else while( t!=NULL){ if(tkey==k) _________________。（ ）8．因為算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。9．在下面冒泡排序算法中填入適當(dāng)內(nèi)容，使該算法在發(fā)現(xiàn)有序時能及時停止。四、算法設(shè)計(30分)1．有一個帶頭結(jié)點的單鏈表，編寫在值為x的結(jié)點之后插入m個結(jié)點的算法。s=s0。( )6．連通分量是無向圖中的極小連通子圖。(5分)2．設(shè)下圖所示的二叉樹是由森林轉(zhuǎn)換而成的，試將它還原為森林。kn。 sprior=p。若假定查找索引表和塊均用順序查找法，則查找每一個元素的平均查找時間為___________。3．假設(shè)用于通信的電文僅有8個字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10，試為這8個字母設(shè)計哈夫曼編碼。2．巳知某算法的執(zhí)行時間為(n+n2)/2+log2 (2n+1)，n為問題規(guī)模，則該算法的時間復(fù)雜度是_____________。(4分)(2)線性表采用簡單選擇排序算法對線性表(26，15，12，16，5，30)進行排序，進行交換的第一對元素是哪兩個元素，在什么情況下，第一趟不需要進行元素的交換?(6分)2．(1)給出下圖所示的二叉樹后序遍歷的結(jié)果。}2．以下程序是在二叉排序樹T中找出值最大的元素，返回其地址，如果空樹返回NULL。amp。 (A)0 (B)1 (C)10 (D)5007．將一個元素進入隊列的時間復(fù)雜度是( )。 7．采用快速排序法進行排序時，如果_________________，排序效率會大大降低。Leavequeue(QUEUE *Q, int *e){ if(__________________) return 0。 if(k==alength) k。}Node。( )3．進棧、出棧操作的時間復(fù)雜度是0(n)。(4分) (2)采用孩子兄弟法將該樹轉(zhuǎn)換為一棵二叉樹。 ji。(5分)Typedef struct LinkNode{ int data。 (A)森林有4棵樹 (B)森林的最大深度為4 (c)森林的第一棵樹有4層 (D)森林有4個結(jié)點3．在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為( )。( )三、填空題(每題2分，共16分) 1．在一個長度為n的順序表中插入一個元素，平均需移動____________個元素，時間復(fù)雜度是____________。(1)寫出各條邊加入生成樹的次序(用權(quán)值表示)。}2．已知數(shù)組r有n個元素，并已經(jīng)由小到大排序。int deln(SQ *L){／* 算法思路是，對每個元素做以下循環(huán)，如果第i個元素大于等于0，且前面有c個小于0的元素，則將它前移c個位置*／int i，c。 (A)串中不同字母的個數(shù) (B)串中不同字符的個數(shù) (c)串中所含字符的個數(shù)，且大于0 (D)串中所含字符的個數(shù)3．?dāng)?shù)組A[1..5，1..6]的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[5，5]的地址為( )。（ ）7．用Prim算法和Kruskal算法求最小生成樹的代價不一定相同。 4．以(1，3，6，7，9，15，22)為權(quán)值，構(gòu)造一棵Huffman樹，并求出其WPL。amp。struct node *right } *BTree。 p(w1)。 ／* 將查找區(qū)間定為右半邊 *／}__________________。 6．右圖中v3的入度和出度分別為__________________。正確的打√，錯誤的打x) 1．線性表的惟一存儲形式就是鏈表。(8分)2．已知單鏈表結(jié)點數(shù)據(jù)結(jié)構(gòu)如下，編寫算法，刪除單鏈表的表首結(jié)點與表尾結(jié)點。}return 1。}else{ for(pf=head。(5分) 2．給出右圖所示樹的先序遍歷的結(jié)果。（ ）4．直接插入排序時，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無關(guān)。如果順序表中的元素少于10個，則刪完為止。q= ________________ 。(4分)五、程序填空題(共15分)1．以下是采用冒泡排序法對數(shù)組a進行排序。