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