【文章內(nèi)容簡介】 pnext=s；t=pdata；pdata=____________；sdata=____________。 2．計算機軟件系統(tǒng)中有兩種處理字符串長度的方法，一種是采用_____________另一種是采用_________。 3．假定對線性表R[059]進行分塊查找，共分10塊，每塊長度等于6。若假定查找索引表和塊均用順序查找法，則查找每一個元素的平均查找時間為___________。 4．一組記錄(50，40，95，20，15，70，60，45，80)進行冒泡排序時，第一趟需進行相鄰記錄的交換次數(shù)為__________，在整個排序過程中共需進行_________趟才可以完成。5．在堆排序、快速排序和歸并排序中，若從節(jié)省存儲空間考慮，則應首先選取_______方法，其次選__________方法，最后選取_________方法；若從排序結構的穩(wěn)定性考慮，則應選擇__________方法；若只從平均情況下排序的速度來考慮，則選擇__________方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應該取___________方法。三、判斷題(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)作用子鏈接棧時，無需判滿。( )四、應用題(20分)1．已知—個長度為12的表{Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}。①試按表中元素的次序依次插入一棵初始為空的二叉排序樹，字符之間以字典順序比較大?。嫵鰧亩媾判驑?，且求出在等概率情況下查找成功的平均查找長度。②若對表中元素先排序構成有序表，試求在等概率情況下對此有序表進行折半查找成功的平均查找長度。2．已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫出這棵二叉樹。3．假設用于通信的電文僅有8個字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10，試為這8個字母設計哈夫曼編碼。4．判別以下序列是否為堆，如果不是，則把它調(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)。五、算法設計(18分)1．已知線性表的元素按遞增順序排列，并以帶首結點的單鏈表作為存儲結構。試編寫一個刪除表中所有值大于min且小于max的元素的算法。2．試設計一個算法，求出指定結點在給定的二叉樹中的層次。3．在含有n個元素的堆中增加一個元素，且調(diào)整為堆。4．試設計將數(shù)組A[0…N—1]中所有奇數(shù)移到所有偶數(shù)之前的算法，要求不另外增加存儲空間，且時間復雜度為O(n)。模擬試題6一、選擇題(每小題1分，共8分) 1．如果某數(shù)據(jù)結構的數(shù)據(jù)元素的集合為S＝{A，B，C，D，E，F(xiàn)，G}，數(shù)據(jù)元素之間的關系為R＝{＜A，D＞，＜A，G＞，＜D，B＞，＜D，C＞，＜G，E＞，＜G，F(xiàn)＞}，則該數(shù)據(jù)結構是一種( )。 (A)線性結構 (B)樹結構 (C)圖結構 (D)鏈表結構2．設有二維數(shù)組A[50][60]，其元素長度為1字節(jié)，按列優(yōu)先順序存儲，首元素A[0][0]的地址為200，則元素A[10][20]的存儲地址為( )。 (A)820 (B)720 (C)1210 (D)14103．一組記錄(50，40，95，20，15，70，60，45，80)進行冒泡排序時，第一趟需進行相鄰記錄交換的次數(shù)為( )。 (A)5 (B)6 (C)7 (D)8 4．具有20個結點的二叉樹，其深度最大為( )。(A)4 （B)5 (C)6 (D)205．在具有N個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊空的條件為( )。 (A) front==rear (B) (rear+1)%MAXSIZE==front (C) frontrear==1 (D) rear%MAXSIZE==front6.—個55的對稱矩陣采用壓縮存儲，需要存儲( )個元素。 (A)5 (B)10 (C)15 (D)207．一個無向連通圖有5個頂點8條邊，則其生成樹將要去掉( )條邊。 (A)3 (B)4 (C)5 (D)68．設一棵二叉樹共有50個葉子結點(終端結點)，則共有( )個度為2的結點 (A)25 (B)49 (C)50 (D)51二、填空題(每題2分，共16分)1．一個算法，如果不論問題規(guī)模大小，運行所需時間都一樣，則該算法的時間復雜度是_____________。2．巳知某算法的執(zhí)行時間為(n+n2)/2+log2 (2n+1)，n為問題規(guī)模，則該算法的時間復雜度是_____________。3．在求最小生成樹的兩種算法中，____________算法適合于稀疏圖。4．一顆Huffman樹是由5個葉子結點形成的，該Huffman樹總共有_________個結點。5．設循環(huán)隊列Q[1..N]的首尾指針為F，R，當插入元素時尾指針只加1，首指針F總是指向隊列中第一個元素的前一個位置，則隊列中元素的個數(shù)為____________。6．一個具有5個結點的有向圖最少有____________條弧。7．二叉排序樹采用____________序遍歷可以得到結點的有序序列。8．設有1000個元素，用折半法查找時，最大比較次數(shù)是_____________。三、判斷題(每題1分，共8分。正確的打√，錯誤的打X)1．如果某數(shù)據(jù)結構的每一個元素都最多只有一個直接后繼結點，則必為線性表。（ ）2．如果某有向圖的所有頂點可以構成一個拓撲排序，則說明有向圖存在回路。( )3．如果把一個大頂堆看成一顆二叉樹，根元素層次為1，則層次越大的元素值越?。? ）。4．Huffman樹沒有度為1的結點。( )5．在冒泡排序中，關鍵碼的比較次數(shù)與記錄的初始排列無關。( )6．設一棵二叉樹共用50個葉子結點(終端結點)，則共有49個度為1的結點7．一個有序的單鏈表采用折半查找法比順序查找效率高得多。( )8．一個圖可以沒有邊，但不能沒有頂點。( )四、簡答題(共38分)1．排序(1)寫出線性表(26，45，12，z0，30，5，15，29，16，2，18)采用基數(shù)排序后，第一趟結束時的結果。(4分)(2)線性表采用簡單選擇排序算法對線性表(26，15，12，16，5，30)進行排序，進行交換的第一對元素是哪兩個元素，在什么情況下，第一趟不需要進行元素的交換?(6分)2．(1)給出下圖所示的二叉樹后序遍歷的結果。(5分)(2)如果下圖表示的是采用孩子—兄弟法轉(zhuǎn)換后的一棵樹。試畫出原來的樹。(5分)3．已知下圖是一個有向圖。(1)畫出該有向圖的鄰接矩陣。(5分)(2)基于你給出的鄰接矩陣，求從頂點6出發(fā)的深度優(yōu)先遍歷。(5分)4．已知有序表(4，11，13，19，26，28，33，39，42)，采用折半查找。(1)各元素的平均查找長度是多少？(4分)(2)查找值為10的元素，查找時與哪些元素進行了比較?(4分)五、程序填空題(共15分)1．己知STACK表示棧的數(shù)據(jù)結構，push為將一個值為e的元素進棧，若成功返回1，否則返回0。完成以下程序。(4分)Typedef struct { int data[100]。 int top。 /* 棧頂元素的下標 */}STACK。int push(STACK *s, int e){if(__________________) return 0。stop++。_______________=e。return 1。}2．以下程序是在二叉排序樹T中找出值最大的元素，返回其地址，如果空樹返回NULL。完成程序。(6分)Typedef struct LinkNode{ int data。 Struct LinkNode *lchild。 *rchild。}Node。Node *sm(Node *T){Node *p。 if (__________________) return NULL。 for(p=T。 __________________。 p=prchild)。 return 。}3．寫出以下程序的輸出結果。(5分)int strc(char s[], char t[]){ int i。 for(i=0。 s[i]!=0amp。amp。t[i]!=0。 i++) if(s[i]!=t[i]) break。 return(s[i]t[i])。}main(){ Printf(“%d\n”, strc(“student”, “study”))。}六、編程題(共15分)1．編寫算法對一個整型數(shù)組中的元素進行位置調(diào)整，將所有負數(shù)放在下標較低的一端，將所有正數(shù)放在下標較高的一端，所有的0在中間。(8分)2．已知二叉樹結點數(shù)據(jù)結構如下，編寫算法，在一棵二叉樹中查找值為x的葉子結點，若找到返回該結點的指針，找不到則返回空指針。(7分)Typedef struct LinkNode{ int data。 Struct LinkNode *lchild。 *rchild。}Node。模擬試題7一、選擇題(每小題1分，共8分)1．如果樹的結點A有4個兄弟，而且B為A的雙親，則B的度為( )。 (A)3 (B)4 (C)5 (D)12．設有一個棧，元素的進棧次序為A，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 3．在所有排序方法中，關鍵碼的比較次數(shù)與記錄的初始排列無關的是( (A)快速排序 (B)冒泡排序 (C)直接插入排序 (D)直接選擇排序4．設一棵二叉樹共用20個度為2的結點，則葉子結點共有( )個。 (A)40 (B)19 (C)20 (D)2l5．在具有N個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊滿的條件為( )。 (A) front==rear (B) (rear+1)%MAXSIZE==front (C) frontrear==1 (D) rear%MAXSIZE==front6．設有1000個元素，用折半查找時，最小比較次數(shù)為( )。 (A)0 (B)1 (C)10 (D)5007．將一個元素進入隊列的時間復雜度是( )。 (A)O(1) (B)O(n) (C)O(n2) (D)O(log2n)8．一棵完全二叉樹中根結點的編號為l，而且23號結點有左孩子但沒有右孩子，則完全二叉樹總共有( )個結點。 (A)24 (B)45 [C)46 (D)47二、判斷題(每題1分，共8分。正確的打√，錯誤的打X)1．如果某數(shù)據(jù)結構的每一個元素都最多只有一個直接前驅(qū)和一個直接后繼，則元素必為線性表。( )2．先序遍歷一棵一又搜索樹所得的結點訪問序列不可能是鎂值遞增序列、( )3．若有一個葉子結點是某子樹的中序遍歷的最后一個結點，則它必須是該子樹的先序遍歷的最后一個結點。( )4．有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。（ ）5．二叉排序樹中，任一結點的值都大于或等于其孩子的值。( )6．圖的生成樹的邊數(shù)應小于頂點數(shù)。( )7．進棧操作時，必須判斷棧是否已滿。( )8．如果某排序算法是穩(wěn)定的，那么該方法一定具有實際應用價值。( )三、填空題(每題2分，共16分)1．數(shù)據(jù)結構有線性結構、樹結構、_____________、____________等幾種邏輯結構。2．已知某算法的執(zhí)行時間為(n+n2)/2+log2 (2n+1)，n 為問題規(guī)模，則該算法的時間復雜度是________________。3．一個無向連通圖有6個頂點7條邊，則其生成樹有_____________條邊。4．順序存儲的隊列如果不采用循環(huán)方式