【正文】 果首元素a[0][0]是第1個(gè)元素，那么a[4][2]是第______________個(gè)元素。3．一個(gè)無(wú)向連通圖有6個(gè)頂點(diǎn)7條邊，則其生成樹(shù)有_____________條邊。( )三、填空題(每題2分，共16分)1．?dāng)?shù)據(jù)結(jié)構(gòu)有線(xiàn)性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)、_____________、____________等幾種邏輯結(jié)構(gòu)。( )7．進(jìn)棧操作時(shí)，必須判斷棧是否已滿(mǎn)。（ ）5．二叉排序樹(shù)中，任一結(jié)點(diǎn)的值都大于或等于其孩子的值。( )2．先序遍歷一棵一又搜索樹(shù)所得的結(jié)點(diǎn)訪(fǎng)問(wèn)序列不可能是鎂值遞增序列、( )3．若有一個(gè)葉子結(jié)點(diǎn)是某子樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹(shù)的先序遍歷的最后一個(gè)結(jié)點(diǎn)。 (A)24 (B)45 [C)46 (D)47二、判斷題(每題1分，共8分。 (A)0 (B)1 (C)10 (D)5007．將一個(gè)元素進(jìn)入隊(duì)列的時(shí)間復(fù)雜度是( )。 (A)40 (B)19 (C)20 (D)2l5．在具有N個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)滿(mǎn)的條件為( )。 (A)3 (B)4 (C)5 (D)12．設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳，B，C，D，E，下列( )是不可能的出棧序列。}Node。 Struct LinkNode *lchild。(8分)2．已知二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下，編寫(xiě)算法，在一棵二叉樹(shù)中查找值為x的葉子結(jié)點(diǎn)，若找到返回該結(jié)點(diǎn)的指針，找不到則返回空指針。}main(){ Printf(“%d\n”, strc(“student”, “study”))。 i++) if(s[i]!=t[i]) break。amp。 for(i=0。}3．寫(xiě)出以下程序的輸出結(jié)果。 p=prchild)。 for(p=T。Node *sm(Node *T){Node *p。 *rchild。(6分)Typedef struct LinkNode{ int data。}2．以下程序是在二叉排序樹(shù)T中找出值最大的元素，返回其地址，如果空樹(shù)返回NULL。_______________=e。int push(STACK *s, int e){if(__________________) return 0。 int top。完成以下程序。(5分)4．已知有序表(4，11，13，19，26，28，33，39，42)，采用折半查找。(1)畫(huà)出該有向圖的鄰接矩陣。試畫(huà)出原來(lái)的樹(shù)。(4分)(2)線(xiàn)性表采用簡(jiǎn)單選擇排序算法對(duì)線(xiàn)性表(26，15，12，16，5，30)進(jìn)行排序，進(jìn)行交換的第一對(duì)元素是哪兩個(gè)元素，在什么情況下，第一趟不需要進(jìn)行元素的交換?(6分)2．(1)給出下圖所示的二叉樹(shù)后序遍歷的結(jié)果。( )8．一個(gè)圖可以沒(méi)有邊，但不能沒(méi)有頂點(diǎn)。( )5．在冒泡排序中，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無(wú)關(guān)。( )3．如果把一個(gè)大頂堆看成一顆二叉樹(shù)，根元素層次為1，則層次越大的元素值越小（ ）。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接后繼結(jié)點(diǎn)，則必為線(xiàn)性表。8．設(shè)有1000個(gè)元素，用折半法查找時(shí)，最大比較次數(shù)是_____________。6．一個(gè)具有5個(gè)結(jié)點(diǎn)的有向圖最少有____________條弧。4．一顆Huffman樹(shù)是由5個(gè)葉子結(jié)點(diǎn)形成的，該Huffman樹(shù)總共有_________個(gè)結(jié)點(diǎn)。2．巳知某算法的執(zhí)行時(shí)間為(n+n2)/2+log2 (2n+1)，n為問(wèn)題規(guī)模，則該算法的時(shí)間復(fù)雜度是_____________。 (A)5 (B)10 (C)15 (D)207．一個(gè)無(wú)向連通圖有5個(gè)頂點(diǎn)8條邊，則其生成樹(shù)將要去掉( )條邊。(A)4 （B)5 (C)6 (D)205．在具有N個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件為( )。 (A)820 (B)720 (C)1210 (D)14103．一組記錄(50，40，95，20，15，70，60，45，80)進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄交換的次數(shù)為( )。模擬試題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．在含有n個(gè)元素的堆中增加一個(gè)元素，且調(diào)整為堆。試編寫(xiě)一個(gè)刪除表中所有值大于min且小于max的元素的算法。 (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)。3．假設(shè)用于通信的電文僅有8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。②若對(duì)表中元素先排序構(gòu)成有序表，試求在等概率情況下對(duì)此有序表進(jìn)行折半查找成功的平均查找長(zhǎng)度。( )四、應(yīng)用題(20分)1．已知—個(gè)長(zhǎng)度為12的表{Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}。（ ）8．因?yàn)樗惴ê统绦驔](méi)有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。( )6．用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間與圖中結(jié)點(diǎn)的個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。( )4．若有一個(gè)葉子結(jié)點(diǎn)是某子樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹(shù)的先序遍歷的最后一個(gè)結(jié)點(diǎn)。( )2．在單鏈表中任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因此可以從首結(jié)點(diǎn)進(jìn)行查找任何一個(gè)元素。5．在堆排序、快速排序和歸并排序中，若從節(jié)省存儲(chǔ)空間考慮，則應(yīng)首先選取_______方法，其次選__________方法，最后選取_________方法；若從排序結(jié)構(gòu)的穩(wěn)定性考慮，則應(yīng)選擇__________方法；若只從平均情況下排序的速度來(lái)考慮，則選擇__________方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)該取___________方法。若假定查找索引表和塊均用順序查找法，則查找每一個(gè)元素的平均查找時(shí)間為_(kāi)__________。 2．計(jì)算機(jī)軟件系統(tǒng)中有兩種處理字符串長(zhǎng)度的方法，一種是采用_____________另一種是采用_________。 (A)Shell排序 (c)直接插入排序15．已知8個(gè)元素(34，76，45，18，26，54，92，65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)，該樹(shù)的深度為( )。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) nn11．采用順序查找法查找長(zhǎng)度為n的線(xià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í)，需( )次比較可查找成功。 (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è)。 6．串的長(zhǎng)度是( )。 pnextprior=s。 (D) sprior=p。 sprior=p。 (C) pnext=s。 pnext=s。 (B) sprior=p。 pnextprior=s。 (A) pnext=s。(A) n/2 (B) n (C) (n+1)/2 (D) (n1)/24．對(duì)一個(gè)具有n個(gè)元素的線(xiàn)性表，建立其有序單鏈表的時(shí)間復(fù)雜度為( )。 (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è)元素。kn。jt。im。j++) c[i][j]=0。i++)for(j=0。(10分)模擬試題5一、選擇題(30分)1．下列程序的時(shí)間復(fù)雜度為( )for(i=0。(8分)2．我們用鏈表來(lái)存儲(chǔ)多項(xiàng)式, 其中, ,試編寫(xiě)求微商的算法。(5分)(1)要求用Kruskal算法求出最小生成樹(shù)(2)指出生成樹(shù)的第一條邊。(5分)2．設(shè)下圖所示的二叉樹(shù)是由森林轉(zhuǎn)換而成的，試將它還原為森林。8．高度為h(≥0)的二叉樹(shù)，至少有__________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。6．哈希表的兩種形式是：__________和__________。4．有序字典是以______________為基礎(chǔ)的抽象數(shù)據(jù)類(lèi)型。p一＞next＝f。f一＞next＝p一＞next。( )10．作為解決一類(lèi)特定問(wèn)題的算法，不能沒(méi)有輸入運(yùn)算項(xiàng)。( )8．不論adt棧是用數(shù)組實(shí)現(xiàn)，還是用指針實(shí)現(xiàn)，Pop(s)與Push(x’s)的時(shí)間復(fù)雜度均)(M)。( )6．連通分量是無(wú)向圖中的極小連通子圖。( )4．一棵滿(mǎn)二叉樹(shù)同時(shí)又是一棵平衡樹(shù)。( )2．二叉排序樹(shù)的左、右子樹(shù)都是二叉排序樹(shù)。 (A)p一＞next＝p一＞next一＞next。 〔A)9 (B)10 (C)11 (D)129．按字母順序，下圖中的二叉排序樹(shù)是( )。 (A)O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 7．采用鏈結(jié)構(gòu)存儲(chǔ)線(xiàn)性表時(shí)，其地址( )。j=n1。i=n。s=s0。 (A)先序 (B)中序 (C)后序 (D)按層次5．在下列4棵樹(shù)中，哪一棵是完全二叉樹(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)最小( )。( )8．如果某排序算法是穩(wěn)定的，那么該方法一定具有實(shí)際應(yīng)用價(jià)值。( )6．圖的生成樹(shù)的邊數(shù)應(yīng)小于頂點(diǎn)數(shù)。( )4．有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，則元素必為線(xiàn)性表。(12分)3．設(shè)計(jì)一個(gè)算法，用于查找中序線(xiàn)索二叉樹(shù)中結(jié)點(diǎn)*p的中序前驅(qū)結(jié)點(diǎn)。四、算法設(shè)計(jì)(30分)1．有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，編寫(xiě)在值為x的結(jié)點(diǎn)之后插入m個(gè)結(jié)點(diǎn)的算法。 3．給定有序表D＝{15，17，18，22，35，60，88，93}，用折半查找法在D中查找18，試用圖示法表示查找過(guò)程。 }三、應(yīng)用題(24分) 1．已知一棵二叉樹(shù)的中序遍歷結(jié)果為DBHEAFICG，先序遍歷結(jié)果為ABDEFHCFIG，試畫(huà)出該二叉樹(shù)。 } _________________。 R[j]=temp。j) if(R[j]R[j1]){ temp=R[j1]。 for(j=n。 i＝1。9．在下面冒泡排序算法中填入適當(dāng)內(nèi)容，使該算法在發(fā)現(xiàn)有序時(shí)能及時(shí)停止。7．有向圖G用鄰接矩陣A[1…m，1…m ]存儲(chǔ)，其第i行的所有元素值之和等于頂點(diǎn)vi的__________________。5．后序序列和中序序列相同的二叉樹(shù)為_(kāi)________________。3．上三角矩陣壓縮存儲(chǔ)的下標(biāo)對(duì)應(yīng)關(guān)系k＝________________。 (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由大到小，其判斷下溢的條件是_______________；判斷上溢的條件是_____________。 （A） （B） （C） （D）7．對(duì)下圖v4的度為( )。 (A)插人 (B)讀表元 (C)查找 (D)定位3．中序遍歷一棵二叉排序樹(shù)所得到的結(jié)點(diǎn)訪(fǎng) (A)遞增或遞減 (B)遞減 (C)遞增 (D)無(wú)序