【正文】 }while(________________)。 R[j1]=R[j]。 do{ exchang = False。8．設(shè)鍵值序列為{k1，k2，…，kn}，建堆和排序全過(guò)程共需進(jìn)行____________次堆調(diào)整。4．設(shè)有一個(gè)空棧，現(xiàn)輸入序列為l，2，3，4，5，經(jīng)過(guò)Push，Push，Pop，Push，Pop，Push，Pop，Push后，輸出序列為_(kāi)_________________ 。 (A)1 (B)2 (C)3 (D)48．在內(nèi)部排序中，排序時(shí)不穩(wěn)定的有( )。 (A)數(shù)據(jù)項(xiàng) (B)數(shù)據(jù)類型 (c)數(shù)據(jù)元京 (D)數(shù)據(jù)變量2．線性表的鏈接實(shí)現(xiàn)有利于( )運(yùn)算。( )7．哈希表的查找效率主要取決于哈希建表時(shí)所選取的哈希函數(shù)和處理沖突的方法。( )3．設(shè)有兩個(gè)串p和q．其中q是p的子串，把q在p中首次出現(xiàn)的位置作為q在p中的位置的算法稱為匹配。2．設(shè)計(jì)一個(gè)算法，求出指定結(jié)點(diǎn)在給定的二叉排序樹(shù)中所在的層次。 }}三、應(yīng)用題(28分)1．設(shè)哈希表的地址空間為0~16，開(kāi)始時(shí)哈希表為空，用線性探測(cè)開(kāi)放地址法處理沖突，對(duì)于數(shù)據(jù)元素Jan，F(xiàn)eb，Mar，Jun，Aug，Sep，Oct，Nov，Dec，試構(gòu)造其對(duì)應(yīng)的哈希表，H(key)＝Li／2J，其中i為關(guān)鍵碼中第一個(gè)字母在字母表中的序號(hào)。 bitreptr * bstsearch(bitreptr *t，keytype k) { if (t==NULL) return NULL。5．模式中“ababbabbab”的前綴函數(shù)為_(kāi)_______________。 (A)25 (B)7 (C)10 (D) 110．在內(nèi)部排序中，排序時(shí)不穩(wěn)定的有( ) (A)插入排序 (B)冒泡排序 (C)快速排序 (D)歸并排序二、填空題(22分)1．具有64個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)________________。 (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．有—棵二叉樹(shù)如下圖．該樹(shù)是( )。 (A)理想結(jié)構(gòu)，物理結(jié)構(gòu) (B)理想結(jié)構(gòu)，抽象結(jié)構(gòu) (c)物理結(jié)構(gòu)，邏輯結(jié)構(gòu) (D)抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)2．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址( )。( )8．不論adt棧是用數(shù)組實(shí)現(xiàn)，還是用指針實(shí)現(xiàn)，Pop(s)與Push(x,s)的時(shí)間復(fù)雜度均O(n)。( )4．一棵滿二叉樹(shù)同時(shí)又是一棵平衡樹(shù)。試偏導(dǎo)算法以判斷該鏈表中從第二項(xiàng)起的每個(gè)元素值是否等于其序號(hào)的平方減去其前驅(qū)結(jié)點(diǎn)的值，若滿足，返回True，否則返回False。 2．一棵完全二叉樹(shù)共有21個(gè)結(jié)點(diǎn)，現(xiàn)順序存放在一個(gè)矢量中，矢量的下標(biāo)正好為結(jié)點(diǎn)的序號(hào)，試問(wèn)序號(hào)為12的雙親結(jié)點(diǎn)存在嗎?為什么?(4分) 3．線性表有順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)述各自的優(yōu)缺點(diǎn)。 9．已知一棵二叉樹(shù)的中序遍歷結(jié)果為DBHEAFICG，后序遍歷結(jié)果為DHEBIFGCA，畫(huà)出該二又樹(shù)___________________。 else return(1)。 j=j+1。2．循環(huán)鏈表的主要優(yōu)點(diǎn)是__________________。 (A)‘BCQR’ (B)‘BCDEF’ (C)‘BCDEFG’ (D)‘BCDEFEF’ 8．設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第1個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占用1個(gè)地址空間，則a85的地址為( )。 (A)數(shù)據(jù)項(xiàng) (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量2．線性表的鏈接實(shí)現(xiàn)有利于( )運(yùn)算。 (A)插入 (B)讀表元 (C)查找 (D)定位3．串的邏輯結(jié)構(gòu)與( )的邏輯結(jié)構(gòu)不同。(A)13 (B)33 (C)18 (D)409．如果結(jié)點(diǎn)A有3個(gè)兄弟，且B為A的雙親，則B的度為( )。3．給定一個(gè)整數(shù)集合{3，5，6，9，12}，畫(huà)出其對(duì)應(yīng)的一棵Huffman樹(shù)__________4．在雙向循環(huán)鏈表中，在指針p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作為_(kāi)_______________5．下面為樸素的模式匹配算法，請(qǐng)?jiān)谒惴ǖ南聞澗€處填上正確的子句int index(s,t)string *s，*t。 } else { i=_________________。 } 6．一個(gè)nn的對(duì)稱矩陣，如果以行或列為主序存人內(nèi)存，則其容量為_(kāi)________。三、應(yīng)用題(16分) 1．設(shè)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如下：(4分)1234567891011121314151617181920EAF^D^H^^C^^^GI^^^^B (1)根據(jù)其存儲(chǔ)結(jié)構(gòu)，畫(huà)出二叉樹(shù)。（4分） 4．何謂隊(duì)列的“假溢”現(xiàn)象？如何解決?(4分)四、算法設(shè)計(jì)(38分) 1．試寫(xiě)出求二又樹(shù)結(jié)點(diǎn)數(shù)目的算法。(10分)五、判斷題(10分)1．具有線性序關(guān)系的集合中，若a，b是集合中的任意兩個(gè)元素，則必有ab的關(guān)系。( )5．即使某排序算法是不穩(wěn)定的，但該方法仍有實(shí)際應(yīng)用價(jià)值。 ( )9．表中的每一個(gè)元素都有前驅(qū)和后繼元素。 (A)必須是連續(xù)的 (B)部分地址必須是連續(xù)的 (c)一定是不連續(xù)的 (D)連續(xù)與否均可以3．設(shè)循環(huán)隊(duì)列Q[l…n—1]的首尾指針為f和r，當(dāng)插入元素時(shí)尾指針r加1，首指針F總是指在隊(duì)列中第一個(gè)元素的前一個(gè)位置，則隊(duì)列中元素計(jì)數(shù)為( )。 (A)二叉平衡樹(shù) (B)二叉排序樹(shù) (c)堆的形狀 (D)以上都不是7．對(duì)于含有n個(gè)頂點(diǎn)e條邊的無(wú)向連通圖，利用Prim算法生成最小代價(jià)生成樹(shù)其時(shí)間復(fù)雜度為( )，利用Kruskal時(shí)間復(fù)雜度為( )。2．有向圖G用鄰接矩陣A{l…n，1…n}存儲(chǔ)，其第i列的所有元素等于頂點(diǎn)i的______________。6．設(shè)圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e，第i個(gè)頂點(diǎn)的度數(shù)為D(vi)則e＝________________(即邊數(shù)與各頂點(diǎn)的度數(shù)之間的關(guān)系)。 else while( t!=NULL){ if(tkey==k) _________________。2．設(shè)有5000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，在快速排序、堆排序和基數(shù)排序方法中，采用哪種方法最好?為什么?3．對(duì)于下圖，試給出(1)每個(gè)頂點(diǎn)的入度和出度(2)鄰接矩陣，(3)逆鄰接表；(4)強(qiáng)連通分量。3．設(shè)汁一個(gè)算法，建立無(wú)向圖(n個(gè)頂點(diǎn)，e條邊)的鄰接表。( )4．若有一個(gè)葉子結(jié)點(diǎn)是某子樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹(shù)的先序遍歷的最后一個(gè)結(jié)點(diǎn)。（ ）8．因?yàn)樗惴ê统绦驔](méi)有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。 (A)插人 (B)讀表元 (C)查找 (D)定位3．中序遍歷一棵二叉排序樹(shù)所得到的結(jié)點(diǎn)訪 (A)遞增或遞減 (B)遞減 (C)遞增 (D)無(wú)序4．SubStr(‘DATA STRUCTURE’，6，9)=（ ）。 (A)快速排序 (B)冒泡排序 (c)歸并排序 (D)直接插入排序9．設(shè)有1000個(gè)元素，用折半查找時(shí)，最大比較次數(shù)為( )，最小比較次數(shù)為( ) (A)25 (B)10 (C)7 (D)1二、填空題(26分)1．對(duì)于一個(gè)以順序?qū)崿F(xiàn)的共享?xiàng)1…n]，棧頂指針?lè)謩e為top1和top2，top1由小到大，top2由大到小，其判斷下溢的條件是_______________；判斷上溢的條件是_____________。5．后序序列和中序序列相同的二叉樹(shù)為_(kāi)________________。9．在下面冒泡排序算法中填入適當(dāng)內(nèi)容，使該算法在發(fā)現(xiàn)有序時(shí)能及時(shí)停止。 for(j=n。 R[j]=temp。 }三、應(yīng)用題(24分) 1．已知一棵二叉樹(shù)的中序遍歷結(jié)果為DBHEAFICG，先序遍歷結(jié)果為ABDEFHCFIG，試畫(huà)出該二叉樹(shù)。四、算法設(shè)計(jì)(30分)1．有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，編寫(xiě)在值為x的結(jié)點(diǎn)之后插入m個(gè)結(jié)點(diǎn)的算法。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，則元素必為線性表。( )6．圖的生成樹(shù)的邊數(shù)應(yīng)小于頂點(diǎn)數(shù)。 (A)2n 〔B)n (C)n/2 (D)n(n1)2．設(shè)連通圖G的頂點(diǎn)數(shù)為n，則G的生成樹(shù)的邊數(shù)為( ) (A)n (B)n一1 (C)2n (D) 2n13．下列哪種排序需要的附加存儲(chǔ)開(kāi)銷(xiāo)最小( )。s=s0。j=n1。 〔A)9 (B)10 (C)11 (D)129．按字母順序，下圖中的二叉排序樹(shù)是( )。( )2．二叉排序樹(shù)的左、右子樹(shù)都是二叉排序樹(shù)。( )6．連通分量是無(wú)向圖中的極小連通子圖。( )10．作為解決一類特定問(wèn)題的算法，不能沒(méi)有輸入運(yùn)算項(xiàng)。p一＞next＝f。6．哈希表的兩種形式是：__________和__________。(5分)2．設(shè)下圖所示的二叉樹(shù)是由森林轉(zhuǎn)換而成的，試將它還原為森林。(8分)2．我們用鏈表來(lái)存儲(chǔ)多項(xiàng)式, 其中, ,試編寫(xiě)求微商的算法。i++)for(j=0。im。kn。(A) n/2 (B) n (C) (n+1)/2 (D) (n1)/24．對(duì)一個(gè)具有n個(gè)元素的線性表，建立其有序單鏈表的時(shí)間復(fù)雜度為( )。 pnextprior=s。 pnext=s。 sprior=p。 pnextprior=s。 (A) ni (B) ni1 (C) ni+1 (D) 不確定8．設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳，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的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)有2個(gè)，度為2的結(jié)點(diǎn)數(shù)有1個(gè)，度為l的結(jié)點(diǎn)數(shù)有2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)有( )個(gè)。 (A)Shell排序 (c)直接插入排序15．已知8個(gè)元素(34，76，45，18，26，54，92，65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)，該樹(shù)的深度為( )。若假定查找索引表和塊均用順序查找法，則查找每一個(gè)元素的平均查找時(shí)間為_(kāi)__________。( )2．在單鏈表中任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因此可以從首結(jié)點(diǎn)進(jìn)行查找任何一個(gè)元素。( )6．用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間與圖中結(jié)點(diǎn)的個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。( )四、應(yīng)用題(20分)1．已知—個(gè)長(zhǎng)度為12的表{Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}。3．假設(shè)用于通信的電文僅有8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。試編寫(xiě)一個(gè)刪除表中所有值大于min且小于max的元素的算法。模擬試題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)是一種( )。(A)4 （B)5 (C)6 (D)205．在具有N個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件為( )。2．巳知某算法的執(zhí)行時(shí)間為(n+n2)/2+log2 (2n+1)，n為問(wèn)題規(guī)模，則該算法的時(shí)間復(fù)雜度是_____________。6．一個(gè)具有5個(gè)結(jié)點(diǎn)的有向圖最少有____________條弧。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接后繼結(jié)點(diǎn)，則必為線性表。( )5．在冒泡排序中，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無(wú)關(guān)。(4分)(2)線性表采用簡(jiǎn)單選擇排序算法對(duì)線性表(26，15，12，16，5，30)進(jìn)行排序，進(jìn)行交換的第一對(duì)元素是哪兩個(gè)元素，在什么情況下，第一趟不需要進(jìn)行元素的交換?(6分)2．(1)給出下圖所示的二叉樹(shù)后序遍歷的結(jié)果。(1)畫(huà)出該有向圖的鄰接矩陣。完成以下程序。int push(STACK *s, int e){if(__________________) return 0。}2．以下程序是