【文章內(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é)省存儲空間考慮，則應(yīng)首先選取_______方法，其次選__________方法，最后選取_________方法；若從排序結(jié)構(gòu)的穩(wěn)定性考慮，則應(yīng)選擇__________方法；若只從平均情況下排序的速度來考慮，則選擇__________方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)該取___________方法。三、判斷題(10分)1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單元。( )2．在單鏈表中任何兩個元素的存儲位置之間都有固定的聯(lián)系，因此可以從首結(jié)點進行查找任何一個元素。( )3．設(shè)有兩個串p和q．其中q是p的子串，把q在p中首次出現(xiàn)的位置作為q在p中的位置的算法稱為匹配。( )4．若有一個葉子結(jié)點是某子樹的中序遍歷的最后一個結(jié)點，則它必須是該子樹的先序遍歷的最后一個結(jié)點。( )5．對于n個記錄的集合進行冒泡排序，在最壞情況下的時間復(fù)雜度是0(n2)。( )6．用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間與圖中結(jié)點的個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。( )7．哈希表的查找效率主要取決于哈希建表時所選取的哈希函數(shù)和處理沖突的方法。（ ）8．因為算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。( )9．按中序遍歷一棵二叉排序樹所得到的中序遍歷序列是一個遞增序列10．進棧操作push(x，s)作用子鏈接棧時，無需判滿。( )四、應(yīng)用題(20分)1．已知—個長度為12的表{Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}。①試按表中元素的次序依次插入一棵初始為空的二叉排序樹，字符之間以字典順序比較大?。嫵鰧?yīng)的二叉排序樹，且求出在等概率情況下查找成功的平均查找長度。②若對表中元素先排序構(gòu)成有序表，試求在等概率情況下對此有序表進行折半查找成功的平均查找長度。2．已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫出這棵二叉樹。3．假設(shè)用于通信的電文僅有8個字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10，試為這8個字母設(shè)計哈夫曼編碼。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)。五、算法設(shè)計(18分)1．已知線性表的元素按遞增順序排列，并以帶首結(jié)點的單鏈表作為存儲結(jié)構(gòu)。試編寫一個刪除表中所有值大于min且小于max的元素的算法。2．試設(shè)計一個算法，求出指定結(jié)點在給定的二叉樹中的層次。3．在含有n個元素的堆中增加一個元素，且調(diào)整為堆。4．試設(shè)計將數(shù)組A[0…N—1]中所有奇數(shù)移到所有偶數(shù)之前的算法，要求不另外增加存儲空間，且時間復(fù)雜度為O(n)。模擬試題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)是一種( )。 (A)線性結(jié)構(gòu) (B)樹結(jié)構(gòu) (C)圖結(jié)構(gòu) (D)鏈表結(jié)構(gòu)2．設(shè)有二維數(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個結(jié)點的二叉樹，其深度最大為( )。(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．設(shè)一棵二叉樹共有50個葉子結(jié)點(終端結(jié)點)，則共有( )個度為2的結(jié)點 (A)25 (B)49 (C)50 (D)51二、填空題(每題2分，共16分)1．一個算法，如果不論問題規(guī)模大小，運行所需時間都一樣，則該算法的時間復(fù)雜度是_____________。2．巳知某算法的執(zhí)行時間為(n+n2)/2+log2 (2n+1)，n為問題規(guī)模，則該算法的時間復(fù)雜度是_____________。3．在求最小生成樹的兩種算法中，____________算法適合于稀疏圖。4．一顆Huffman樹是由5個葉子結(jié)點形成的，該Huffman樹總共有_________個結(jié)點。5．設(shè)循環(huán)隊列Q[1..N]的首尾指針為F，R，當(dāng)插入元素時尾指針只加1，首指針F總是指向隊列中第一個元素的前一個位置，則隊列中元素的個數(shù)為____________。6．一個具有5個結(jié)點的有向圖最少有____________條弧。7．二叉排序樹采用____________序遍歷可以得到結(jié)點的有序序列。8．設(shè)有1000個元素，用折半法查找時，最大比較次數(shù)是_____________。三、判斷題(每題1分，共8分。正確的打√，錯誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個元素都最多只有一個直接后繼結(jié)點，則必為線性表。（ ）2．如果某有向圖的所有頂點可以構(gòu)成一個拓?fù)渑判?，則說明有向圖存在回路。( )3．如果把一個大頂堆看成一顆二叉樹，根元素層次為1，則層次越大的元素值越?。? ）。4．Huffman樹沒有度為1的結(jié)點。( )5．在冒泡排序中，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無關(guān)。( )6．設(shè)一棵二叉樹共用50個葉子結(jié)點(終端結(jié)點)，則共有49個度為1的結(jié)點7．一個有序的單鏈表采用折半查找法比順序查找效率高得多。( )8．一個圖可以沒有邊，但不能沒有頂點。( )四、簡答題(共38分)1．排序(1)寫出線性表(26，45，12，z0，30，5，15，29，16，2，18)采用基數(shù)排序后，第一趟結(jié)束時的結(jié)果。(4分)(2)線性表采用簡單選擇排序算法對線性表(26，15，12，16，5，30)進行排序，進行交換的第一對元素是哪兩個元素，在什么情況下，第一趟不需要進行元素的交換?(6分)2．(1)給出下圖所示的二叉樹后序遍歷的結(jié)果。(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ù)結(jié)構(gòu)，push為將一個值為e的元素進棧，若成功返回1，否則返回0。完成以下程序。(4分)Typedef struct { int data[100]。 int top。 /* 棧頂元素的下標(biāo) */}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．寫出以下程序的輸出結(jié)果。(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)整，將所有負(fù)數(shù)放在下標(biāo)較低的一端，將所有正數(shù)放在下標(biāo)較高的一端，所有的0在中間。(8分)2．已知二叉樹結(jié)點數(shù)據(jù)結(jié)構(gòu)如下，編寫算法，在一棵二叉樹中查找值為x的葉子結(jié)點，若找到返回該結(jié)點的指針，找不到則返回空指針。(7分)Typedef struct LinkNode{ int data。 Struct LinkNode *lchild。 *rchild。}Node。模擬試題7一、選擇題(每小題1分，共8分)1．如果樹的結(jié)點A有4個兄弟，而且B為A的雙親，則B的度為( )。 (A)3 (B)4 (C)5 (D)12．設(shè)有一個棧，元素的進棧次序為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．在所有排序方法中，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無關(guān)的是( (A)快速排序 (B)冒泡排序 (C)直接插入排序 (D)直接選擇排序4．設(shè)一棵二叉樹共用20個度為2的結(jié)點，則葉子結(jié)點共有( )個。 (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．設(shè)有1000個元素，用折半查找時，最小比較次數(shù)為( )。 (A)0 (B)1 (C)10 (D)5007．將一個元素進入隊列的時間復(fù)雜度是( )。 (A)O(1) (B)O(n) (C)O(n2) (D)O(log2n)8．一棵完全二叉樹中根結(jié)點的編號為l，而且23號結(jié)點有左孩子但沒有右孩子，則完全二叉樹總共有( )個結(jié)點。 (A)24 (B)45 [C)46 (D)47二、判斷題(每題1分，共8分。正確的打√，錯誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個元素都最多只有一個直接前驅(qū)和一個直接后繼，則元素必為線性表。( )2．先序遍歷一棵一又搜索樹所得的結(jié)點訪問序列不可能是鎂值遞增序列、( )3．若有一個葉子結(jié)點是某子樹的中序遍歷的最后一個結(jié)點，則它必須是該子樹的先序遍歷的最后一個結(jié)點。( )4．有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。（ ）5．二叉排序樹中，任一結(jié)點的值都大于或等于其孩子的值。( )6．圖的生成樹的邊數(shù)應(yīng)小于頂點數(shù)。( )7．進棧操作時，必須判斷棧是否已滿。( )8．如果某排序算法是穩(wěn)定的，那么該方法一定具有實際應(yīng)用價值。( )三、填空題(每題2分，共16分)1．?dāng)?shù)據(jù)結(jié)構(gòu)有線性結(jié)構(gòu)、樹結(jié)構(gòu)、_____________、____________等幾種邏輯結(jié)構(gòu)。2．已知某算法的執(zhí)行時間為(n+n2)/2+log2 (2n+1)，n 為問題規(guī)模，則該算法的時間復(fù)雜度是________________。3．一個無向連通圖有6個頂點7條邊，則其生成樹有_____________條邊。4．順序存儲的隊列如果不采用循環(huán)方式