【正文】 法排序后，第一趟結(jié)束時的結(jié)果。(5分) (2)根據(jù)該二叉排序樹，查找數(shù)7，需要比較哪幾個數(shù)?(5分)五、程序填空題(共15分)1．已知QUEUE表示循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)，函數(shù)1eavequeue是將隊首元素的值放人變量e，然后刪除隊首元素，操作成功返回1，否則返回0。 Qfront= ______________。}SQ。 ik。 pnext=pnextnext。如果是(包括空表)，返回1，不是則返回0。 (A)5 (B)6 (C)7 (D)96．已知某算法的執(zhí)行時間為(n+n2)/2+log2 (n+2)，n 為問題規(guī)模，則該算法的時間復(fù)雜度是( )。( )5．一個有序的單鏈表不能采用折半查找法進行查找。 5．如果指針p指向一棵二叉樹的一個結(jié)點，則判斷p沒有左孩子的邏輯表達式為____________。(1)畫出該有向圖的鄰接鏈表。(4分)五、程序填空題(共15分)1．以下是采用冒泡排序法對數(shù)組a進行排序。a[j]=a[j+1]。q= ________________ 。}Node。如果順序表中的元素少于10個，則刪完為止。(A)插入排序 (B)冒泡排序 (c)快速排序 (D)歸并排序5．設(shè)一數(shù)列的順序為1，2，3，4，5，通過棧結(jié)構(gòu)不可能排成的順序數(shù)列為( )。（ ）4．直接插入排序時，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無關(guān)。3．具有26個結(jié)點的完全二叉樹的深度為____________。(5分) 2．給出右圖所示樹的先序遍歷的結(jié)果。(4分)五、程序填空題(共15分)1．已知單鏈表的表首指針為head，下面的函數(shù)delete是從單鏈表中刪除指針為p的結(jié)點，并返回新的表首指針。}else{ for(pf=head。完成下面程序。}return 1。 iLlength。(8分)2．已知單鏈表結(jié)點數(shù)據(jù)結(jié)構(gòu)如下，編寫算法，刪除單鏈表的表首結(jié)點與表尾結(jié)點。為這兩個棧分配空間的最佳方案是( )。正確的打√，錯誤的打x) 1．線性表的惟一存儲形式就是鏈表。( )9．對相同關(guān)鍵碼集合，以不同次序插入初始為空的樹中，一定得到不同的二叉排序樹。 6．右圖中v3的入度和出度分別為__________________。6．對下面數(shù)據(jù)表，寫出采用快速排序法的前兩層遞歸調(diào)用結(jié)果。 ／* 將查找區(qū)間定為右半邊 *／}__________________。if(________________) j++。 p(w1)。鏈表類型定義如下。struct node *right } *BTree。(3分)void p(int w)。amp。if(R[m].keyk________________。 4．以(1，3，6，7，9，15，22)為權(quán)值，構(gòu)造一棵Huffman樹，并求出其WPL。 4 只有64個結(jié)點的完全二叉樹的深度為___________________。（ ）7．用Prim算法和Kruskal算法求最小生成樹的代價不一定相同。 (A)直接插入排序 (B)快速排序 (c)歸并排序 (D)選擇排序10．下列排序算法中，時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為0(log2n)的是( )。 (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]的地址為( )。例如數(shù)組{5，3，5，7，3，6}，不同的值有3個。int deln(SQ *L){／* 算法思路是，對每個元素做以下循環(huán)，如果第i個元素大于等于0，且前面有c個小于0的元素，則將它前移c個位置*／int i，c。 if(er[k])i2=k1。}2．已知數(shù)組r有n個元素，并已經(jīng)由小到大排序。if(head==p){ head=__________________。(1)寫出各條邊加入生成樹的次序(用權(quán)值表示)。四、簡答題(共38分) 1．堆排序 (1)寫出線性表(16，4，12，25，30，6，15．11，20，2，18)調(diào)整為大頂堆(用二叉樹表示)。( )三、填空題(每題2分，共16分) 1．在一個長度為n的順序表中插入一個元素，平均需移動____________個元素，時間復(fù)雜度是____________。( )2．無論是線性表還是樹，每一個結(jié)點的直接前驅(qū)結(jié)點最多只有一個。 (A)森林有4棵樹 (B)森林的最大深度為4 (c)森林的第一棵樹有4層 (D)森林有4個結(jié)點3．在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為( )。}六、編程題(共15分)1．兩個字符數(shù)組s，t中各放有一個串，編寫算法，將所有t中有而s中沒有的字符加到s中(逐個加到s的后面)。(5分)Typedef struct LinkNode{ int data。}Node。 ji。(1)計算平均查找長度。(4分) (2)采用孩子兄弟法將該樹轉(zhuǎn)換為一棵二叉樹。 3．在一個長度為n的順序表中插入一個元素，最少需要移動__________個元素，最多需要移動__________個元素。( )3．進棧、出棧操作的時間復(fù)雜度是0(n)。 (A) n1 (B) n (C) n+1 (D)O n log n4．下列排序方法中，( )的比較次數(shù)與紀(jì)錄的初始排列狀態(tài)無關(guān)。}Node。 pdata300。 if(k==alength) k。(8分)typedef struct { int elem[100]。Leavequeue(QUEUE *Q, int *e){ if(__________________) return 0。(5分)(2)基于你給出的鄰接鏈表，求從頂點C出發(fā)的廣度優(yōu)先遍歷。 7．采用快速排序法進行排序時，如果_________________，排序效率會大大降低。( )7．進棧操作時，必須判斷棧是否已滿。 (A)0 (B)1 (C)10 (D)5007．將一個元素進入隊列的時間復(fù)雜度是( )。 Struct LinkNode *lchild。amp。 for(p=T。}2．以下程序是在二叉排序樹T中找出值最大的元素，返回其地址，如果空樹返回NULL。完成以下程序。(4分)(2)線性表采用簡單選擇排序算法對線性表(26，15，12，16，5，30)進行排序，進行交換的第一對元素是哪兩個元素，在什么情況下，第一趟不需要進行元素的交換?(6分)2．(1)給出下圖所示的二叉樹后序遍歷的結(jié)果。正確的打√，錯誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個元素都最多只有一個直接后繼結(jié)點，則必為線性表。2．巳知某算法的執(zhí)行時間為(n+n2)/2+log2 (2n+1)，n為問題規(guī)模，則該算法的時間復(fù)雜度是_____________。模擬試題6一、選擇題(每小題1分，共8分) 1．如果某數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素的集合為S＝{A，B，C，D，E，F(xiàn)，G}，數(shù)據(jù)元素之間的關(guān)系為R＝{＜A，D＞，＜A，G＞，＜D，B＞，＜D，C＞，＜G，E＞，＜G，F(xiàn)＞}，則該數(shù)據(jù)結(jié)構(gòu)是一種( )。3．假設(shè)用于通信的電文僅有8個字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10，試為這8個字母設(shè)計哈夫曼編碼。( )6．用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間與圖中結(jié)點的個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。若假定查找索引表和塊均用順序查找法，則查找每一個元素的平均查找時間為___________。 (A) ni (B) ni1 (C) ni+1 (D) 不確定8．設(shè)有一個棧，元素的進棧次序為A，B，C，D，E，下列( )是不可能的出棧序列 (A)A，B，C，D，E (B)B，C，D，E，A (C)E，A，B，C，D (D)E，D，C，B，A 9．在一棵度為3的樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為l的結(jié)點數(shù)有2個，那么度為0的結(jié)點數(shù)有( )個。 sprior=p。 pnextprior=s。kn。i++)for(j=0。(5分)2．設(shè)下圖所示的二叉樹是由森林轉(zhuǎn)換而成的，試將它還原為森林。p一＞next＝f。( )6．連通分量是無向圖中的極小連通子圖。 〔A)9 (B)10 (C)11 (D)129．按字母順序，下圖中的二叉排序樹是( )。s=s0。( )6．圖的生成樹的邊數(shù)應(yīng)小于頂點數(shù)。四、算法設(shè)計(30分)1．有一個帶頭結(jié)點的單鏈表，編寫在值為x的結(jié)點之后插入m個結(jié)點的算法。 R[j]=temp。9．在下面冒泡排序算法中填入適當(dāng)內(nèi)容，使該算法在發(fā)現(xiàn)有序時能及時停止。 (A)快速排序 (B)冒泡排序 (c)歸并排序 (D)直接插入排序9．設(shè)有1000個元素，用折半查找時，最大比較次數(shù)為( )，最小比較次數(shù)為( ) (A)25 (B)10 (C)7 (D)1二、填空題(26分)1．對于一個以順序?qū)崿F(xiàn)的共享棧[1…n]，棧頂指針分別為top1和top2，top1由小到大，top2由大到小，其判斷下溢的條件是_______________；判斷上溢的條件是_____________。（ ）8．因為算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。3．設(shè)汁一個算法，建立無向圖(n個頂點，e條邊)的鄰接表。 else while( t!=NULL){ if(tkey==k) _________________。2．有向圖G用鄰接矩陣A{l…n，1…n}存儲，其第i列的所有元素等于頂點i的______________。 (A)必須是連續(xù)的 (B)部分地址必須是連續(xù)的 (c)一定是不連續(xù)的 (D)連續(xù)與否均可以3．設(shè)循環(huán)隊列Q[l…n—1]的首尾指針為f和r，當(dāng)插入元素時尾指針r加1，首指針F總是指在隊列中第一個元素的前一個位置，則隊列中元素計數(shù)為( )。( )5．即使某排序算法是不穩(wěn)定的，但該方法仍有實際應(yīng)用價值。（4分） 4．何謂隊列的“假溢”現(xiàn)象？如何解決?(4分)四、算法設(shè)計(38分) 1．試寫出求二又樹結(jié)點數(shù)目的算法。 } 6．一個nn的對稱矩陣，如果以行或列為主序存人內(nèi)存，則其容量為_________。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。 (A)插入 (B)讀表元 (C)查找 (D)定位3．串的邏輯結(jié)構(gòu)與( )的邏輯結(jié)構(gòu)不同。 (A)‘BCQR’ (B)‘BCDEF’ (C)‘BCDEFG’ (D)‘BCDEFEF’ 8．設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第1個元素，其存儲地址為1，每個元素占用1個地址空間，則a85的地址為( )。 j=j+1。 9．已知一棵二叉樹的中序遍歷結(jié)果為DBHEAFICG，后序遍歷結(jié)果為DHEBIFGCA，畫出該二又樹___________________。試偏導(dǎo)算法以判斷該鏈表中從第二項起的每個元素值是否等于其序號的平方減去其前驅(qū)結(jié)點的值，若滿足，返回True，否則返回False。( )8．不論adt棧是用數(shù)組實現(xiàn)，還是用指針實現(xiàn)，Pop(s)與Push(x,s)的時間復(fù)雜度均O(n)。 (A)10，15，14，18，20，36，40，21 (B)10，15，14，18，20，40，36，21 (C)10，15，14，20，18，40，36，21 (D)15，10，14，18，20，36，40，216．有—棵二叉樹如下圖．該樹是( )。5．模式中“ababbabbab”的前綴函數(shù)為________________。 }}三、應(yīng)用題(28分)1．設(shè)哈希表的地址空間為0~16，開始時哈希表為空，用線性探測開放地址法處理沖突，對于數(shù)據(jù)元素Jan，F(xiàn)eb，Mar，Jun，Aug，Sep，Oct，Nov，Dec，試構(gòu)造其對應(yīng)的哈希表，H(key)＝Li／2J，其中i為關(guān)鍵碼中第一個字母在字母表中的序號。( )3．設(shè)有兩個串p和q．其中q是p的子串，把q在p中首次出現(xiàn)的位置作為q在p中的位置的算法稱為匹配。 (A)數(shù)據(jù)項 (B)數(shù)據(jù)類型 (c)數(shù)據(jù)元京 (D)數(shù)據(jù)變量2．線性表的鏈接實現(xiàn)有利于( )運算。