【正文】 模擬試題1一、選擇題(20分)1．組成數(shù)據(jù)的基本單位是( )。 (A)數(shù)據(jù)項 (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量2．線性表的鏈接實現(xiàn)有利于( )運算。 (A)插入 (B)讀表元 (C)查找 (D)定位3．串的邏輯結構與( )的邏輯結構不同。 (A)線性表 (B)棧 (C)隊列 (D)樹4．二叉樹第i(i≥1)層最多有( )個結點 (A)2i， (B)2i (C)2i1 (D)2i一1 5．設單鏈表中指針p指向結點A，若要刪除A之后的結點(若存在)，則修改指針的操作為( )。 (A)pnext＝pnextnext (B)p＝pnext (C)p＝pnextnext (D)pnext＝p 6．設一數(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．設字符中S1＝‘ASCDEFG’，S2＝‘PQRST’，則運算S＝Concat(Sub(S1,2,Length(S2))，Sub(S1，Length(S2)，2))后結果為( )。 (A)‘BCQR’ (B)‘BCDEF’ (C)‘BCDEFG’ (D)‘BCDEFEF’ 8．設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第1個元素，其存儲地址為1，每個元素占用1個地址空間，則a85的地址為( )。(A)13 (B)33 (C)18 (D)409．如果結點A有3個兄弟，且B為A的雙親，則B的度為( )。 (A)3 (B)4 (C)5 (D)110．線索化二叉樹中某結點D，沒有左孩子的主要條件是( )。 (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，其判空的條件是____________，判滿的條件是______________。2．循環(huán)鏈表的主要優(yōu)點是__________________。3．給定一個整數(shù)集合{3，5，6，9，12}，畫出其對應的一棵Huffman樹__________4．在雙向循環(huán)鏈表中，在指針p所指的結點之后插入指針f所指的結點，其操作為________________5．下面為樸素的模式匹配算法，請在算法的下劃線處填上正確的子句int index(s,t)string *s，*t。{ i＝j＝0。 while((i＜s一＞len)＆＆(j＜t一＞len)) if (s一＞ch[i]==t一＞ch[j]){ i=i+1。 j=j+1。 } else { i=_________________。 j=_________________。 } if(j==tlen) return(itlen)。 else return(1)。 } 6．一個nn的對稱矩陣，如果以行或列為主序存人內(nèi)存，則其容量為_________。 7．設F是森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結點，B中右指針域為空的結點有______________。 8．先序序列和中序序列相同的二叉樹為_________________。 9．已知一棵二叉樹的中序遍歷結果為DBHEAFICG，后序遍歷結果為DHEBIFGCA，畫出該二又樹___________________。三、應用題(16分) 1．設二叉樹的順序存儲結構如下：(4分)1234567891011121314151617181920EAF^D^H^^C^^^GI^^^^B (1)根據(jù)其存儲結構，畫出二叉樹。 (2)寫出按先序、中序、后序遍歷該二叉樹所得的結點序列。 (3)畫出二叉樹的后序線索化樹。 2．一棵完全二叉樹共有21個結點，現(xiàn)順序存放在一個矢量中，矢量的下標正好為結點的序號，試問序號為12的雙親結點存在嗎?為什么?(4分) 3．線性表有順序表和鏈表兩種存儲結構，簡述各自的優(yōu)缺點。（4分） 4．何謂隊列的“假溢”現(xiàn)象？如何解決?(4分)四、算法設計(38分) 1．試寫出求二又樹結點數(shù)目的算法。(13分) 2．設a＝(a1，a2，…am)和b＝(b1,b2，…，bn)是兩個循環(huán)鏈表寫出將這兩個表合并為循環(huán)鏈表c的算法。(15分) (a1，b1，a2，b2，…am，bm，bm+1，…，bn) m≤nc= (a1，b1，a2，b2，…an，bn，an+1，…，am) mn 3．已知一個單鏈表中每個結點存放一個整數(shù)，并且其結點數(shù)不少于2。試偏導算法以判斷該鏈表中從第二項起的每個元素值是否等于其序號的平方減去其前驅(qū)結點的值，若滿足，返回True，否則返回False。(10分)五、判斷題(10分)1．具有線性序關系的集合中，若a，b是集合中的任意兩個元素，則必有ab的關系。( )2．二叉排序樹的左、右子樹都是二叉排序樹。( )3．在堆中執(zhí)行INSERT與DELETEMIN運算都只需O(log2n)時間。( )4．一棵滿二叉樹同時又是一棵平衡樹。( )5．即使某排序算法是不穩(wěn)定的，但該方法仍有實際應用價值。( )6．連通分量是無向圖中的極小連通子圖。( )7．先序遍歷一棵二叉排序樹所得的結點訪問序列不可能是鏈值遞增序列。( )8．不論adt棧是用數(shù)組實現(xiàn)，還是用指針實現(xiàn)，Pop(s)與Push(x,s)的時間復雜度均O(n)。 ( )9．表中的每一個元素都有前驅(qū)和后繼元素。( )10．作為解決一類特定問題的算法，不能沒有輸入運算項。( )模擬試題2一、選擇題(20分)1．數(shù)據(jù)結構是研究數(shù)據(jù)的( )以及它們之間的相互關系。 (A)理想結構，物理結構 (B)理想結構，抽象結構 (c)物理結構，邏輯結構 (D)抽象結構，邏輯結構2．線性表采用鏈式存儲時，其地址( )。 (A)必須是連續(xù)的 (B)部分地址必須是連續(xù)的 (c)一定是不連續(xù)的 (D)連續(xù)與否均可以3．設循環(huán)隊列Q[l…n—1]的首尾指針為f和r，當插入元素時尾指針r加1，首指針F總是指在隊列中第一個元素的前一個位置，則隊列中元素計數(shù)為( )。 (A)r一f (B)n一(r一f) (C)(r—f十n)％n (D)(f一r十n)％n4．完成堆排序的全過程需要( )個記錄大小的輔助空間。 (A)1 (B)n (C)n log2 n (D)Ln log2 n J5．若結定的關鍵碼集合為{20，15，14，18，2l，36，40，10}，一趟快速排序結束時，鍵值的排列為( )。 (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．有—棵二叉樹如下圖．該樹是( )。 (A)二叉平衡樹 (B)二叉排序樹 (c)堆的形狀 (D)以上都不是7．對于含有n個頂點e條邊的無向連通圖，利用Prim算法生成最小代價生成樹其時間復雜度為( )，利用Kruskal時間復雜度為( )。 (A)O(1og2n) (B)O(n2) (C)O(ne) (D)O(e log2 e)8．具有n個頂點的完全有向圖的邊數(shù)為( )。 (A)n(n一1)／2 (D)n(n—1) (C)n2 (D) n2 19．設有100個元素，用折半查找時，最大比較次數(shù)為( )，最小比較次數(shù)為（ ）。 (A)25 (B)7 (C)10 (D) 110．在內(nèi)部排序中，排序時不穩(wěn)定的有( ) (A)插入排序 (B)冒泡排序 (C)快速排序 (D)歸并排序二、填空題(22分)1．具有64個結點的完全二叉樹的深度為_________________。2．有向圖G用鄰接矩陣A{l…n，1…n}存儲，其第i列的所有元素等于頂點i的______________。3．設有一空棧，棧頂指針為1000H(十六進制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過Push，Push，Pop，Push，Pop，Push，Push操作后，輸出序列為________________。4．線索化二叉樹中某結點D，沒有左孩子的主要條件是______________。5．模式中“ababbabbab”的前綴函數(shù)為________________。6．設圖G的頂點數(shù)為n，邊數(shù)為e，第i個頂點的度數(shù)為D(vi)則e＝________________(即邊數(shù)與各頂點的度數(shù)之間的關系)。7．按________________遍歷二叉樹，可以得到按值遞增的關鍵碼序列，在下圖中所示的二叉樹中，檢索關鍵碼85的過程中，需與85進行比較的關健碼序列為________________。8．下列算法實現(xiàn)二叉樹排序樹上的查找，請在空格處填上適當?shù)恼Z句，完成上述功能。 bitreptr * bstsearch(bitreptr *t，keytype k) { if (t==NULL) return NULL。 else while( t!=NULL){ if(tkey==k) _________________。 if(tkeyk)__________________。 else_________________。 }}三、應用題(28分)1．設哈希表的地址空間為0~16，開始時哈希表為空，用線性探測開放地址法處理沖突，對于數(shù)據(jù)元素Jan，F(xiàn)eb，Mar，Jun，Aug，Sep，Oct，Nov，Dec，試構造其對應的哈希表，H(key)＝Li／2J，其中i為關鍵碼中第一個字母在字母表中的序號。2．設有5000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，在快速排序、堆排序和基數(shù)排序方法中，采用哪種方法最好?為什么?3．對于下圖，試給出(1)每個頂點的入度和出度(2)鄰接矩陣，(3)逆鄰接表；(4)強連通分量。4．簡述堆排序的基本思想，對鍵值集合{72，73，71，23，94，16，05，68}對應的二叉樹進行進堆，并寫出具體步驟。四、算法設計(30分)1．某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構成一個單鏈表存于計算機中，鏈表的每個結點指出同樣價格的若干臺，現(xiàn)在又新到m臺價格為n元的電視機入庫，試編寫倉庫電視機鏈表增加電視機的算法。2．設計一個算法，求出指定結點在給定的二叉排序樹中所在的層次。3．設汁一個算法，建立無向圖(n個頂點，e條邊)的鄰接表。五、判斷題(10分)1．數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( )2．在單鏈表中任何兩個元素的存儲位置之間都有固定的聯(lián)系，因此可以從首結點進行查找任何一個元素。( )3．設有兩個串p和q．其中q是p的子串，把q在p中首次出現(xiàn)的位置作為q在p中的位置的算法稱為匹配。( )4．若有一個葉子結點是某子樹的中序遍歷的最后一個結點，則它必須是該子樹的先序遍歷的最后一個結點。( )5．對于n個記錄的集合進行冒泡排序，在最壞情況下的時間復雜度是0(n2)。( )6．用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間與圖中結點的個數(shù)有關，而與圖的邊數(shù)無關。( )7．哈希表的查找效率主要取決于哈希建表時所選取的哈希函數(shù)和處理沖突的方法。（ ）8．因為算法和程序沒有區(qū)別，所以在數(shù)據(jù)結構中二者是通用的。( )9．按中序遍歷一棵二叉排序樹所得到的中序遍歷序列是一個遞增序列10．進棧操作push(x，s)作用于鏈接棧時，無需判滿。( )模擬試題3一、選擇題(20分)1．組成數(shù)據(jù)的基本單位是( )。 (A)數(shù)據(jù)項 (B)數(shù)據(jù)類型 (c)數(shù)據(jù)元京 (D)數(shù)據(jù)變量2．線性表的鏈接實現(xiàn)有利于( )運算。 (A)插人 (B)讀表元 (C)查找 (D)定位3．中序遍歷一棵二叉排序樹所得到的結點訪 (A)遞增或遞減 (B)遞減 (C)遞增 (D)無序4．SubStr(‘DATA STRUCTURE’，6，9)=（ ）。 (A)‘STR