【正文】 有( )個(gè)結(jié)點(diǎn)。如果是(包括空表)，返回1，不是則返回0。 Struct LinkNode *lchild。 pnext=pnextnext。 }3．已知一個(gè)單鏈表的表首指針為h，每個(gè)結(jié)點(diǎn)含元素值data和下一結(jié)點(diǎn)的地址next。 ik。 kalength。}SQ。插入成功返回1，否則返回0。 Qfront= ______________。 /* 隊(duì)首元素的下標(biāo) */ int rear。(5分) (2)根據(jù)該二叉排序樹，查找數(shù)7，需要比較哪幾個(gè)數(shù)?(5分)五、程序填空題(共15分)1．已知QUEUE表示循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，函數(shù)1eavequeue是將隊(duì)首元素的值放人變量e，然后刪除隊(duì)首元素，操作成功返回1，否則返回0。(5分)4．已知下圖是一個(gè)無向團(tuán)。四、簡(jiǎn)答題(共38分)1．排序(1)寫出線性表(26，45，12，20，30)采用快速排序算法排序后，第一趟結(jié)束時(shí)的結(jié)果。5．一個(gè)1010的三角矩陣a采用列優(yōu)先壓縮存儲(chǔ)后，如果首元素a[0][0]是第1個(gè)元素，那么a[4][2]是第______________個(gè)元素。( )三、填空題(每題2分，共16分)1．?dāng)?shù)據(jù)結(jié)構(gòu)有線性結(jié)構(gòu)、樹結(jié)構(gòu)、_____________、____________等幾種邏輯結(jié)構(gòu)。（ ）5．二叉排序樹中，任一結(jié)點(diǎn)的值都大于或等于其孩子的值。 (A)24 (B)45 [C)46 (D)47二、判斷題(每題1分，共8分。 (A)40 (B)19 (C)20 (D)2l5．在具有N個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為( )。}Node。(8分)2．已知二叉樹結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下，編寫算法，在一棵二叉樹中查找值為x的葉子結(jié)點(diǎn)，若找到返回該結(jié)點(diǎn)的指針，找不到則返回空指針。 i++) if(s[i]!=t[i]) break。 for(i=0。 p=prchild)。Node *sm(Node *T){Node *p。(6分)Typedef struct LinkNode{ int data。_______________=e。 int top。(5分)4．已知有序表(4，11，13，19，26，28，33，39，42)，采用折半查找。試畫出原來的樹。( )8．一個(gè)圖可以沒有邊，但不能沒有頂點(diǎn)。( )3．如果把一個(gè)大頂堆看成一顆二叉樹，根元素層次為1，則層次越大的元素值越?。? ）。8．設(shè)有1000個(gè)元素，用折半法查找時(shí)，最大比較次數(shù)是_____________。4．一顆Huffman樹是由5個(gè)葉子結(jié)點(diǎn)形成的，該Huffman樹總共有_________個(gè)結(jié)點(diǎn)。 (A)5 (B)10 (C)15 (D)207．一個(gè)無向連通圖有5個(gè)頂點(diǎn)8條邊，則其生成樹將要去掉( )條邊。 (A)820 (B)720 (C)1210 (D)14103．一組記錄(50，40，95，20，15，70，60，45，80)進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄交換的次數(shù)為( )。3．在含有n個(gè)元素的堆中增加一個(gè)元素，且調(diào)整為堆。 (1)(100，86，48，73，35．39，42，57，66，21)； (2)(12，70，33，65．z4，56，48，92，86，33)； (3)(103，97，56，38，66，242，12，30，52，06，20)。②若對(duì)表中元素先排序構(gòu)成有序表，試求在等概率情況下對(duì)此有序表進(jìn)行折半查找成功的平均查找長(zhǎng)度。（ ）8．因?yàn)樗惴ê统绦驔]有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。( )4．若有一個(gè)葉子結(jié)點(diǎn)是某子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹的先序遍歷的最后一個(gè)結(jié)點(diǎn)。5．在堆排序、快速排序和歸并排序中，若從節(jié)省存儲(chǔ)空間考慮，則應(yīng)首先選取_______方法，其次選__________方法，最后選取_________方法；若從排序結(jié)構(gòu)的穩(wěn)定性考慮，則應(yīng)選擇__________方法；若只從平均情況下排序的速度來考慮，則選擇__________方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)該取___________方法。 2．計(jì)算機(jī)軟件系統(tǒng)中有兩種處理字符串長(zhǎng)度的方法，一種是采用_____________另一種是采用_________。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) nn11．采用順序查找法查找長(zhǎng)度為n的線性表．則查找每個(gè)元素的平均比較次數(shù)為( ) (A) n (B) n/2 (C) (n+1)/2 (D) (n1)/212．已知一個(gè)有序表為(13，18，24，35，47，50，62，83，90，115，134)，當(dāng)二分查找值為90的元素時(shí)，需( )次比較可查找成功。 6．串的長(zhǎng)度是( )。 (D) sprior=p。 (C) pnext=s。 (B) sprior=p。 (A) pnext=s。 (A) O(mnt) (B) O(m+n+t) (C) O(m+n) (D) O(mt+n)2．從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)真值表歸約（1≤i≤n），需向前移動(dòng)（ ）個(gè)元素。jt。j++) c[i][j]=0。(10分)模擬試題5一、選擇題(30分)1．下列程序的時(shí)間復(fù)雜度為( )for(i=0。(5分)(1)要求用Kruskal算法求出最小生成樹(2)指出生成樹的第一條邊。8．高度為h(≥0)的二叉樹，至少有__________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。4．有序字典是以______________為基礎(chǔ)的抽象數(shù)據(jù)類型。f一＞next＝p一＞next。( )8．不論adt棧是用數(shù)組實(shí)現(xiàn)，還是用指針實(shí)現(xiàn)，Pop(s)與Push(x’s)的時(shí)間復(fù)雜度均)(M)。( )4．一棵滿二叉樹同時(shí)又是一棵平衡樹。 (A)p一＞next＝p一＞next一＞next。 (A)O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 7．采用鏈結(jié)構(gòu)存儲(chǔ)線性表時(shí)，其地址( )。i=n。 (A)先序 (B)中序 (C)后序 (D)按層次5．在下列4棵樹中，哪一棵是完全二叉樹( )。( )8．如果某排序算法是穩(wěn)定的，那么該方法一定具有實(shí)際應(yīng)用價(jià)值。( )4．有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。(12分)3．設(shè)計(jì)一個(gè)算法，用于查找中序線索二叉樹中結(jié)點(diǎn)*p的中序前驅(qū)結(jié)點(diǎn)。 3．給定有序表D＝{15，17，18，22，35，60，88，93}，用折半查找法在D中查找18，試用圖示法表示查找過程。 } _________________。j) if(R[j]R[j1]){ temp=R[j1]。 i＝1。7．有向圖G用鄰接矩陣A[1…m，1…m ]存儲(chǔ)，其第i行的所有元素值之和等于頂點(diǎn)vi的__________________。3．上三角矩陣壓縮存儲(chǔ)的下標(biāo)對(duì)應(yīng)關(guān)系k＝________________。 （A） （B） （C） （D）7．對(duì)下圖v4的度為( )。( )模擬試題3一、選擇題(20分)1．組成數(shù)據(jù)的基本單位是( )。( )6．用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間與圖中結(jié)點(diǎn)的個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。( )2．在單鏈表中任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因此可以從首結(jié)點(diǎn)進(jìn)行查找任何一個(gè)元素。四、算法設(shè)計(jì)(30分)1．某百貨公司倉(cāng)庫(kù)中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成一個(gè)單鏈表存于計(jì)算機(jī)中，鏈表的每個(gè)結(jié)點(diǎn)指出同樣價(jià)格的若干臺(tái)，現(xiàn)在又新到m臺(tái)價(jià)格為n元的電視機(jī)入庫(kù)，試編寫倉(cāng)庫(kù)電視機(jī)鏈表增加電視機(jī)的算法。 else_________________。8．下列算法實(shí)現(xiàn)二叉樹排序樹上的查找，請(qǐng)?jiān)诳崭裉幪钌线m當(dāng)?shù)恼Z(yǔ)句，完成上述功能。4．線索化二叉樹中某結(jié)點(diǎn)D，沒有左孩子的主要條件是______________。 (A)n(n一1)／2 (D)n(n—1) (C)n2 (D) n2 19．設(shè)有100個(gè)元素，用折半查找時(shí)，最大比較次數(shù)為( )，最小比較次數(shù)為（ ）。 (A)1 (B)n (C)n log2 n (D)Ln log2 n J5．若結(jié)定的關(guān)鍵碼集合為{20，15，14，18，2l，36，40，10}，一趟快速排序結(jié)束時(shí)，鍵值的排列為( )。( )模擬試題2一、選擇題(20分)1．?dāng)?shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的( )以及它們之間的相互關(guān)系。( )7．先序遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問序列不可能是鏈值遞增序列。( )3．在堆中執(zhí)行INSERT與DELETEMIN運(yùn)算都只需O(log2n)時(shí)間。(15分) (a1，b1，a2，b2，…am，bm，bm+1，…，bn) m≤nc= (a1，b1，a2，b2，…an，bn，an+1，…，am) mn 3．已知一個(gè)單鏈表中每個(gè)結(jié)點(diǎn)存放一個(gè)整數(shù)，并且其結(jié)點(diǎn)數(shù)不少于2。 (3)畫出二叉樹的后序線索化樹。 8．先序序列和中序序列相同的二叉樹為_________________。 } if(j==tlen) return(itlen)。 while((i＜s一＞len)＆＆(j＜t一＞len)) if (s一＞ch[i]==t一＞ch[j]){ i=i+1。 (A)D一＞Lchild＝NULL (B)D一＞1tag＝1 (C)D一＞Rchild＝NULL (D)D一＞1tag＝0二、填空題(每空2分，共22分)1．對(duì)于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q[0…m—1]，隊(duì)首、隊(duì)尾指針分別為f和r，其判空的條件是____________，判滿的條件是______________。 (A)pnext＝pnextnext (B)p＝pnext (C)p＝pnextnext (D)pnext＝p 6．設(shè)一數(shù)列的輸入順序?yàn)?，2，3，4，5，6，通過棧操作不可能排成的輸出序列為( ) (A)3，2，5，6，4，1 (B)l，5，4，6，2，3 (C)2，4，3，5，1，6 (D)4，5，3，6，2，1 7．設(shè)字符中S1＝‘ASCDEFG’，S2＝‘PQRST’，則運(yùn)算S＝Concat(Sub(S1,2,Length(S2))，Sub(S1，Length(S2)，2))后結(jié)果為( )。模擬試題1一、選擇題(20分)1．組成數(shù)據(jù)的基本單位是( )。 (A)線性表 (B)棧 (C)隊(duì)列 (D)樹4．二叉樹第i(i≥1)層最多有( )個(gè)結(jié)點(diǎn) (A)2i， (B)2i (C)2i1 (D)2i一1 5．設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(若存在)，則修改指針的操作為( )。 (A)3 (B)4 (C)5 (D)110．線索化二叉樹中某結(jié)點(diǎn)D，沒有左孩子的主要條件是( )。{ i＝j(luò)＝0。 j=_________________。 7．設(shè)F是森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有______________。 (2)寫出按先序、中序、后序遍歷該二叉樹所得的結(jié)點(diǎn)序列。(13分) 2．設(shè)a＝(a1，a2，…am)和b＝(b1,b2，…，bn)是兩個(gè)循環(huán)鏈表寫出將這兩個(gè)表合并為循環(huán)鏈表c的算法。( )2．二叉排序樹的左、右子樹都是二叉排序樹。( )6．連通分量是無向圖中的極小連通子圖。( )10．作為解決一類特定問題的算法，不能沒有輸入運(yùn)算項(xiàng)。 (A)r一f (B)n一(r一f) (C)(r—f十n)％n (D)(f一r十n)％n4．完成堆排序的全過程需要( )個(gè)記錄大小的輔助空間。 (A)O(1og2n) (B)O(n2) (C)O(ne) (D)O(e log2 e)8．具有n個(gè)頂點(diǎn)的完全有向圖的邊數(shù)為( )。3．設(shè)有一空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過Push，Push，Pop，Push，Pop，Push，Push操作后，輸出序列為________________。7．按________________遍歷二叉樹，可以得到按值遞增的關(guān)鍵碼序列，在下圖中所示的二叉樹中，檢索關(guān)鍵碼85的過程中，需與85進(jìn)行比較的關(guān)健碼序列為________________。 if(tkeyk)__________________。4．簡(jiǎn)述堆排序的基本思想，對(duì)鍵