數(shù)據(jù)結(jié)構(gòu)試題1(有答案)

1、試題 1 一、單選題（每題2 分，共 20 分）1. 1.對一個(gè)算法的評價(jià)，不包括如下（）方面的內(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

2、. 4.一個(gè)棧的輸入序列為1 2 3， 則下列序列中不可能是棧的輸出序列的是( c ) a. 2 3 1 b. 3 2 1 c. 3 1 2 d. 1 2 3 5. 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行號b列號c元素值d非零元素個(gè)數(shù)9. 9

3、.快速排序在最壞情況下的時(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.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é)

5、點(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)的編號， 并按此編號把它順序存儲(chǔ)到一維數(shù)組 a 中，即編號為 0 的結(jié)點(diǎn)存儲(chǔ)到 a0 中。其余類推，則a i 元素的左孩子元素為 _,右孩子元素為 _ ，雙親元素為_ 。11. 11.在

6、 線 性 表 的 散 列 存 儲(chǔ) 中 ， 處 理 沖 突 的 常 用 方 法 有_ 和_ 兩種。12. 12. 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時(shí)，宜采用_ 排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用 _ 排序。二、三、運(yùn)算題（每題 6 分，共 24 分）1.1.已知一個(gè) 6 5 稀疏矩陣如下所示，007000000520000000100000010000試：（1）（1）寫出它的三元組線性表；（2）（2）給出三元組線性表的順序存儲(chǔ)表示。2.2.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)

7、據(jù)而生成的二叉搜索樹。3.3.對于圖 6 所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(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.已知一個(gè)圖的頂點(diǎn)集v 和邊集 e 分別為：v=1,2,3,4,5,6,7; e=,; 若存儲(chǔ)它采用鄰接表， 并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。三、四、閱讀算法（每題7 分，共 14 分）1.1.int prime(int n) i

8、nt 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; i

9、nt 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 二、二

10、、填空題（每空1 分，共 26 分）1.1.聯(lián)系圖（或圖結(jié)構(gòu)）2.2.尾首3.3.top=0 4.4.o（1）o（n）5.5.128 44 108 6.6.3 3 7.7.有序n-1 8.8.有序序列后綴表達(dá)式（或逆波蘭式）9.9.2n n-1 n+1 10.10.2i+1 2i+2 (i-1)/2 11.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 所示。3.3.dfs：bfs：4.4.拓樸排序?yàn)椋? 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 所表示的圖。五、五、算法