1、共25套適用于計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)系統(tǒng)練習(xí)（PS：其他正在整理，敬請期待）數(shù)據(jù)結(jié)構(gòu)試卷14一、填空題1、二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯Γ總€(gè)元素占一個(gè)存儲單元并且A00的存儲地址是200，則A612的地址是_。2、二維數(shù)組A10.205.10采用行序?yàn)橹鞣绞酱鎯?，每個(gè)元素占4個(gè)存儲單元，并且A105的存儲地址是1000，則A189的地址是_。3、求下列廣義表操作的結(jié)果：(1) GetTailGetHead(a,b),(c,d);(2) GetTailGetHeadGetTail(a,b),(c,d)4、已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是_。5、已知一個(gè)圖的鄰接矩陣

2、表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是_。6、在利用快速排序方法對一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行快速排序時(shí)，遞歸調(diào)用而使用的棧所能達(dá)到的最大深度為_，共需遞歸調(diào)用的次數(shù)為_，其中第二次遞歸調(diào)用是對_一組記錄進(jìn)行快速排序。7、在堆排序，快速排序和歸并排序中，若只從存儲空間考慮，則應(yīng)首先選取_方法，其次選取_方法，最后選取_方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取_方法；若只從平均情況下排序最快考慮，則應(yīng)選取_方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取_方法。二、選擇題1、二分查找和二叉排序樹的時(shí)間性能【 】。A. 相同 B. 不相同2、

3、采用二分查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為【 】。AO（n2） B. O(nlog2n) C. O(n) D. O(log2n)3、在待排序的元素序列基本有序的前提下，效率最高的排序方法是【 】。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序4、下述幾種排序方法中，要求內(nèi)存量最大的是【 】。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序5、設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作【 】。A. 連接 B. 模式匹配C. 求子串 D. 求串長6、二維數(shù)組A中，每個(gè)元素Aij的長度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地

4、址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時(shí)，元素A47的起始地址為【 】。A. SA+141 B. SA+180 C. SA+222 D. SA+2257、某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是【 】。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca8、在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊【 】。A. 只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)9、具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有【 】條邊才能

5、確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D. 810、二分查找和二叉排序樹的時(shí)間性能【 】。A. 相同 B. 不相同 C. 可能相同 D. 不確定三、計(jì)算與算法應(yīng)用題：1. 已知一個(gè)有向圖的頂點(diǎn)集V和邊集G分別為：V=a,b,c,d,e,f,g,hE=,;假定該圖采用鄰接矩陣表示，則分別寫出從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。2. 設(shè)散列表的長度為13，散列函數(shù)為H（h）= k%13，給定的關(guān)鍵碼序列為19，14，23，01，68，20，84，27。試畫出用線性探查法解決沖突時(shí)所構(gòu)成的散列表。0 1 2 3 4 5 6 7 8 9 10 11 12四、閱讀

6、下列算法，分析它的作用：1. void AD(Lnode* & HL) Insert(HL,30); Insert(HL,50); Delete(HL,26); Delete(HL,55); 假定調(diào)用該算法時(shí)以HL為表頭指針的單鏈表中的內(nèi)容為（15，26，48，55），則調(diào)用返回后該單鏈表中的內(nèi)容為： _。2.void AI(adjmatrrix GA,int i,int n) couti; vistedi=true; for(int j=0;jn;j+)if(GaIj! =0& GAij! =MaxValue& ! visitedj) AI(GA,j,n);該算法的功能為：_。五、算法設(shè)計(jì)1

7、. 已知深度為h的二叉樹以一維數(shù)組BT(1:2h-1)作為其存儲結(jié)構(gòu)。請寫一算法，求該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。2. 編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找item帶回整個(gè)結(jié)點(diǎn)的值并返回true，否則返回false。 bool Find（BtreeNode*BST，ElemType&item）答案一、填空1. 200+（6*20+12）= 3262. 1000+(18-10)*6 +(9-5)*4 = 12083. (1). (b) (2). (d)4. 求矩陣第i列非零元素之和 5. 將矩陣第i行全部置為零6. 2. 2; 4; （23，38，15）

8、7. 堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序二、選擇1-5BBADB 6-10ABCBB三、計(jì)算與算法應(yīng)用題：1、平均長度為4.8. 深度優(yōu)先搜索序列：a，b，f，h，c，d，g，e 廣度優(yōu)先搜索序列：a，b，c，f，d，e，h，g 7.四、閱讀下列算法，分析其作用1. （15，30，48，50）2. 從初始點(diǎn)vi出發(fā)深度優(yōu)先搜索遍歷由鄰接距陣GA所表示的圖五、算法設(shè)計(jì)1、二叉樹采取順序結(jié)構(gòu)存儲，是按完全二叉樹格式存儲的。對非完全二叉樹要補(bǔ)上“虛結(jié)點(diǎn)”。由于不是完全二叉樹，在順序結(jié)構(gòu)存儲中對葉子結(jié)點(diǎn)的判定是根據(jù)其左右子女為0。葉子和雙親結(jié)點(diǎn)下標(biāo)間的關(guān)系滿足完全二叉樹的性質(zhì)。int Leaves(int h) /求深度為h以順序結(jié)構(gòu)存儲的二叉樹的葉子結(jié)點(diǎn)數(shù)int BT; int len=2h-1, count=0; /BT是二叉樹結(jié)點(diǎn)值一維數(shù)組，容量為2h for (i=1;ilen) count+; /第i個(gè)結(jié)