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

此文檔收集于網(wǎng)絡(luò)，如有侵權(quán)，請 聯(lián)系網(wǎng)站刪除一、 單選題（每題 2 分，共20分）1. 1. 對一個(gè)算法的評(píng)價(jià)，不包括如下（B ）方面的內(nèi)容。 A健壯性和可讀性 B并行性 C正確性 D時(shí)空復(fù)雜度2. 2. 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針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ù)的存儲(chǔ)空間 D.表中元素的個(gè)數(shù)不變4. 4. 一個(gè)棧的輸入序列為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. 采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（ ）。A低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C與鏈接法處理沖突相同 D高于二分查找7. 7. 若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（ ）參數(shù)。A值 B函數(shù) C指針 D引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。A行號(hào) B列號(hào) C元素值 D非零元素個(gè)數(shù)9. 9. 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ ）。AO(log2n) BO(nlog2n) C0(n) D0(n2)10. 10. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(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)系時(shí)，稱這種結(jié)構(gòu)為_。2. 2. 隊(duì)列的插入操作是在隊(duì)列的_尾_進(jìn)行，刪除操作是在隊(duì)列的_首_進(jìn)行。3. 3. 當(dāng)用長度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示棧空，則表示棧滿的條件是_top=0_(要超出才為滿)_。4. 4. 對于一個(gè)長度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。5. 5. 設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié)，行下標(biāo)i從0到7 ，列下標(biāo)j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用_個(gè)字節(jié)。W中第6 行的元素和第4 列的元素共占用_個(gè)字節(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)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)_。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的_。9. 9. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為_個(gè)，其中_個(gè)用于指向孩子，_個(gè)指針是空閑的。10. 10. 若對一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A0中。其余類推，則A i 元素的左孩子元素為_,右孩子元素為_，雙親元素為_。11. 11. 在線性表的散列存儲(chǔ)中，處理沖突的常用方法有_和_兩種。12. 12. 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時(shí)，宜采用_排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用_排序。三、 三、 運(yùn)算題（每題6分，共24分）1. 1. 已知一個(gè)65稀疏矩陣如下所示，試：（1） （1） 寫出它的三元組線性表；（2） （2） 給出三元組線性表的順序存儲(chǔ)表示。2. 2. 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。3. 3. 對于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4. 4. 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為： 圖6 V=1,2,3,4,5,6,7;E=,;若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(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) 該算法的時(shí)間復(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） 三元組線性表的順序存儲(chǔ)表示如圖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是否是素?cái)?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. 棧和隊(duì)列的共同特點(diǎn)是( )。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出 C.都是先進(jìn)先出D.沒有共同點(diǎn) 2. 2. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( ). A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾指針可能都要修改3. 3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？( ) A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹4. 4. 設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個(gè)元素占一個(gè)空間，問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個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放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個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為 A. O（1） B. O（n） C. O（1og2n） D. O（n2）9. 9. 對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)， A1 B2 C3 D410. 10. 設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有( )條邊才能確保是一個(gè)連通圖。A.5 B.6 C.7 D.8二、 二、 填空題（每空1分，共26分）1. 1. 通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：_、_、_和_。2. 2. 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級(jí)表示為_。3. 3. 假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個(gè)，樹的深度為_，樹的度為_。4. 4. 后綴算式9 2 3 +- 10 2 / -的值為_。中綴算式（3+4X）-2Y/3對應(yīng)的后綴算式為_。5. 5. 若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有_個(gè)指針域，其中有_個(gè)指針域是存放了地址，有_個(gè)指針是空指針。6. 6. 對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_個(gè)和_個(gè)。7. 7. AOV網(wǎng)是一種_的圖。8. 8. 在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_條邊。9. 9. 假定一個(gè)線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為_、_、_和_。10. 10. 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度_。11. 11. 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。12. 12. 在快速排序、堆排序、歸并排序中，_排序是穩(wěn)定的。三、 三、 運(yùn)算題（每題 6 分，共24分）1. 1. 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A 0.next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. 2. 圖10請畫出圖10的鄰接矩陣和鄰接表。3. 3. 已知一個(gè)圖的頂點(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í)，每加入一個(gè)數(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)計(jì)出單鏈表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）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）返回的線性表為（a2,a3,an,a1） 2. 2. 遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。五、 五、 算法填空（每空2分，共8 分）true BST-left BST-right 六、 六、 編寫算法（8分）int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計(jì)數(shù)器 while(p!=NULL) if (P-data=x) i+; p=p-next; /while, 出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) return i; /CountX 一、 一、 單選題（每小題2分，共8分）1、 1、在一個(gè)長度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 ( )。A n B n/2 C (n+1)/2 D (n-1)/22、 2、在一個(gè)單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個(gè)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ù)類型包括_和_兩個(gè)部分。3、 3、在下面的數(shù)組a中鏈接存儲(chǔ)著一個(gè)線性表，表頭指針為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個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的_，該循環(huán)隊(duì)列的最大長度為_。6、 6、當(dāng)堆棧采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用表示；當(dāng)堆棧采用鏈接存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用_表示。7、 7、一棵高度為5的二叉樹中最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)；一棵高度為5的理想平衡樹中，最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)。8、 8、在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為_，通常它包含三個(gè)域：一是_；二是_；三是_。9、 9、在一個(gè)索引文件的索引表中，每個(gè)索引項(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ù)為_個(gè)，樹的深度為_,樹的度為_, 結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為_,孩子結(jié)點(diǎn)為_ 。11、 11、 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_,整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。12、 12、 在對m階的B_樹插入元素的過程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于_個(gè)，則必須把它分裂為_個(gè)結(jié)點(diǎn)。三、 三、 運(yùn)算題（每小題6分，共24分）1、 1、已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。2、 2、一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT0.12，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。3、 3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。4、 4、已知一個(gè)圖的頂點(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)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序鏈接