清華大學(xué)數(shù)據(jù)結(jié)構(gòu)試題及答案.doc

此文檔收集于網(wǎng)絡(luò)，如有侵權(quán)，請 聯(lián)系網(wǎng)站刪除一、 單選題（每題 2 分，共20分）1. 1. 對一個算法的評價，不包括如下（B ）方面的內(nèi)容。 A健壯性和可讀性 B并行性 C正確性 D時空復(fù)雜度2. 2. 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. HL=p; p-next=HL;3. 3. 對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( ) A.經(jīng)常需要隨機(jī)地存取元素 B.經(jīng)常需要進(jìn)行插入和刪除操作 C.表中元素需要占據(jù)一片連續(xù)的存儲空間 D.表中元素的個數(shù)不變4. 4. 一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. AOV網(wǎng)是一種（ ）。 A有向圖 B無向圖 C無向無環(huán)圖 D有向無環(huán)圖6. 6. 采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。A低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C與鏈接法處理沖突相同 D高于二分查找7. 7. 若需要利用形參直接訪問實(shí)參時，應(yīng)將形參變量說明為（ ）參數(shù)。A值 B函數(shù) C指針 D引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。A行號 B列號 C元素值 D非零元素個數(shù)9. 9. 快速排序在最壞情況下的時間復(fù)雜度為（ ）。AO(log2n) BO(nlog2n) C0(n) D0(n2)10. 10. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)二、 二、 運(yùn)算題（每題 6 分，共24分）1. 1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_。當(dāng)結(jié)點(diǎn)之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_。2. 2. 隊列的插入操作是在隊列的_尾_進(jìn)行，刪除操作是在隊列的_首_進(jìn)行。3. 3. 當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則表示棧滿的條件是_top=0_(要超出才為滿)_。4. 4. 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為_，在表尾插入元素的時間復(fù)雜度為_。5. 5. 設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標(biāo)i從0到7 ，列下標(biāo)j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用_個字節(jié)。W中第6 行的元素和第4 列的元素共占用_個字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W6，3的起始地址為_。6. 6. 廣義表A= (a,(a,b),(a,b),c),則它的深度為_，它的長度為_。7. 7. 二叉樹是指度為2的_樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)點(diǎn)的度的總和是_。8. 8. 對一棵二叉搜索樹進(jìn)行中序遍歷時，得到的結(jié)點(diǎn)序列是一個_。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的_。9. 9. 對于一棵具有n個結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_個，其中_個用于指向孩子，_個指針是空閑的。10. 10. 若對一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點(diǎn)存儲到A0中。其余類推，則A i 元素的左孩子元素為_,右孩子元素為_，雙親元素為_。11. 11. 在線性表的散列存儲中，處理沖突的常用方法有_和_兩種。12. 12. 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時，宜采用_排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用_排序。三、 三、 運(yùn)算題（每題6分，共24分）1. 1. 已知一個65稀疏矩陣如下所示，試：（1） （1） 寫出它的三元組線性表；（2） （2） 給出三元組線性表的順序存儲表示。2. 2. 設(shè)有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。3. 3. 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小到大的次序鏈接的，試寫出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4. 4. 已知一個圖的頂點(diǎn)集V和邊集E分別為： 圖6 V=1,2,3,4,5,6,7;E=,;若存儲它采用鄰接表，并且每個頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。四、 四、 閱讀算法（每題7分，共14分）1. 1. int Prime(int n) int i=1; int x=(int) sqrt(n); while (+ix) return 1; else return 0; (1) (1) 指出該算法的功能；(2) (2) 該算法的時間復(fù)雜度是多少？2. 2. 寫出下述算法的功能： void AJ(adjlist GL, int i, int n) Queue Q; InitQueue(Q); coutiadjvex; if(!visitedj) coutjnext; 五、 五、 算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。Int Binsch(ElemType A ,int n,KeyType K)int low=0;int high=n-1;while (low=high)int mid=_；if (K=Amid.key) return mid; /查找成功，返回元素的下標(biāo) else if (Kmid.key) _; /在左子表上繼續(xù)查找 else _; /在右子表上繼續(xù)查找return -1; /查找失敗，返回-1六、 六、 編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。ElemType DeleFront(LNode * & HL)參考答案一、 一、 單選題（每題2分，共20分）1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C二、 二、 填空題（每空1分，共26分）1. 1. 聯(lián)系 圖（或圖結(jié)構(gòu)）2. 2. 尾 首3. 3. top=04. 4. O（1） O（n）5. 5. 128 44 1086. 6. 3 3 7. 7. 65515132-145-2515637 圖7有序 n-18. 8. 有序序列 后綴表達(dá)式（或逆波蘭式）9. 9. 2n n-1 n+110. 10. 2i+1 2i+2 (i-1)/211. 11. 開放定址法 鏈接法12. 12. 快速 歸并三、 三、 運(yùn)算題（每題6分，共24分）1. 1. （1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)（2） 三元組線性表的順序存儲表示如圖7示。2. 2. 圖8如圖8所示。3. 3. DFS： BFS： 4. 4. 拓樸排序?yàn)椋?4 3 6 5 7 2 1 四、 四、 閱讀算法（每題7分，共14分）1. 1. (1) 判斷n是否是素數(shù)（或質(zhì)數(shù)） （2）O（）2. 2. 功能為：從初始點(diǎn)vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。五、 五、 算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 六、 六、 編寫算法（8分）ElemType DeleFront(LNode * & HL)if (HL=NULL) cerr空表next;ElemType temp=p-data;delete p;return temp; 一、 一、 單選題（每題 2 分，共20分）1. 1. 棧和隊列的共同特點(diǎn)是( )。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出 C.都是先進(jìn)先出D.沒有共同點(diǎn) 2. 2. 用鏈接方式存儲的隊列，在進(jìn)行插入運(yùn)算時( ). A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾指針可能都要修改3. 3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？( ) A. 隊列 B. 棧 C. 線性表 D. 二叉樹4. 4. 設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個元素占一個空間，問A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。 A688 B678 C692 D6965. 5. 樹最適合用來表示( )。 A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)6. 6. 二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-17. 7. 若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為( ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，38. 8. 對n個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為 A. O（1） B. O（n） C. O（1og2n） D. O（n2）9. 9. 對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個， A1 B2 C3 D410. 10. 設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有( )條邊才能確保是一個連通圖。A.5 B.6 C.7 D.8二、 二、 填空題（每空1分，共26分）1. 1. 通常從四個方面評價算法的質(zhì)量：_、_、_和_。2. 2. 一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為_。3. 3. 假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個，樹的深度為_，樹的度為_。4. 4. 后綴算式9 2 3 +- 10 2 / -的值為_。中綴算式（3+4X）-2Y/3對應(yīng)的后綴算式為_。5. 5. 若用鏈表存儲一棵二叉樹時，每個結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點(diǎn)的二叉樹共有_個指針域，其中有_個指針域是存放了地址，有_個指針是空指針。6. 6. 對于一個具有n個頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_個和_個。7. 7. AOV網(wǎng)是一種_的圖。8. 8. 在一個具有n個頂點(diǎn)的無向完全圖中，包含有_條邊，在一個具有n個頂點(diǎn)的有向完全圖中，包含有_條邊。9. 9. 假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為_、_、_和_。10. 10. 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度_。11. 11. 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為_，整個堆排序過程的時間復(fù)雜度為_。12. 12. 在快速排序、堆排序、歸并排序中，_排序是穩(wěn)定的。三、 三、 運(yùn)算題（每題 6 分，共24分）1. 1. 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A 0.next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. 2. 圖10請畫出圖10的鄰接矩陣和鄰接表。3. 3. 已知一個圖的頂點(diǎn)集V和邊集E分別為： V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4. 4. 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。四、 四、 閱讀算法（每題7分，共14分）1. 1. LinkList mynote(LinkList L) /L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。2. 2. void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatadata) item=BST-data;/查找成功 return _; else if(itemdata) return Find(_,item); else return Find(_,item); /if六、 六、 編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。 int CountX(LNode* HL,ElemType x)參考答案一、 一、 單選題（每題2分，共20分）1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A二、 二、 填空題（每空1分，共26分）1. 1. 正確性 易讀性 強(qiáng)壯性 高效率2. 2. O(n)3. 3. 9 3 34. 4. -1 3 4 X * + 2 Y * 3 / -5. 5. 2n n-1 n+16. 6. e 2e7. 7. 有向無回路8. 8. n(n-1)/2 n(n-1)9. 9. （12，40） （ ） （74） （23,55，63）10. 10. 增加111. 11. O(log2n) O(nlog2n)12. 12. 歸并三、 三、 運(yùn)算題（每題6分，共24分）1. 1. 線性表為：（78，50，40，60，34，90）2. 2. 鄰接矩陣： 鄰接表如圖11所示：圖113. 3. 用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4. 見圖124444422255285283452843圖12四、 四、 閱讀算法（每題7分，共14分）1. 1. （1）查詢鏈表的尾結(jié)點(diǎn)（2）將第一個結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）返回的線性表為（a2,a3,an,a1） 2. 2. 遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄洹Ｎ濉?五、 算法填空（每空2分，共8 分）true BST-left BST-right 六、 六、 編寫算法（8分）int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計數(shù)器 while(p!=NULL) if (P-data=x) i+; p=p-next; /while, 出循環(huán)時i中的值即為x結(jié)點(diǎn)個數(shù) return i; /CountX 一、 一、 單選題（每小題2分，共8分）1、 1、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 ( )。A n B n/2 C (n+1)/2 D (n-1)/22、 2、在一個單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個s所指的結(jié)點(diǎn),則執(zhí)行( )。 A slink=plink; plink=s; B plink=s; slink=q; C plink=slink; slink=p; D q link=s; slink =p;3、 3、 棧的插入和刪除操作在（ ）進(jìn)行。A 棧頂 B 棧底 C 任意位置 D 指定位置4、 4、 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ） A 24 B 71 C 48 D 53二、 二、 填空題（每空1分，共32分）1、 1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、 _ 、_和_四種。2、 2、一種抽象數(shù)據(jù)類型包括_和_兩個部分。3、 3、在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為ao.next，則該線性表為_。 a 0 1 2 3 4 5 6 7 8 60 56 42 38 74 25 4 3 7 6 2 0 1datanext4、 4、在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為_和_。5、 5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的_，該循環(huán)隊列的最大長度為_。6、 6、當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用表示；當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時，棧頂元素的值可用_表示。7、 7、一棵高度為5的二叉樹中最少含有_個結(jié)點(diǎn)，最多含有_個結(jié)點(diǎn)；一棵高度為5的理想平衡樹中，最少含有_個結(jié)點(diǎn)，最多含有_個結(jié)點(diǎn)。8、 8、在圖的鄰接表中，每個結(jié)點(diǎn)被稱為_，通常它包含三個域：一是_；二是_；三是_。9、 9、在一個索引文件的索引表中，每個索引項(xiàng)包含對應(yīng)記錄的_和_兩項(xiàng)數(shù)據(jù)。10、 10、 假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個，樹的深度為_,樹的度為_, 結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為_,孩子結(jié)點(diǎn)為_ 。11、 11、 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為_,整個堆排序過程的時間復(fù)雜度為_。12、 12、 在對m階的B_樹插入元素的過程中，每向一個結(jié)點(diǎn)插入一個索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于_個，則必須把它分裂為_個結(jié)點(diǎn)。三、 三、 運(yùn)算題（每小題6分，共24分）1、 1、已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。2、 2、一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT0.12，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。3、 3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。4、 4、已知一個圖的頂點(diǎn)集V各邊集G如下：V = 0，1，2，3，4，5，6，7，8，9；E = （0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）當(dāng)它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。假定每個頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接