數(shù)據(jù)結構試題1(有答案)

1、試題 1 一、單選題（每題2 分，共 20 分）1. 1.對一個算法的評價，不包括如下（）方面的內(nèi)容。a健壯性和可讀性b并行性c正確性d時空復雜度2. 2.在帶有頭結點的單鏈表hl 中，要向表頭插入一個由指針p 指向的結點，則執(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.對線性表，在下列哪種情況下應當采用鏈表表示？( ) a.經(jīng)常需要隨機地存取元素b.經(jīng)常需要進行插入和刪除操作c.表中元素需要占據(jù)一片連續(xù)的存儲空間d.表中元素的個數(shù)不變4

2、. 4.一個棧的輸入序列為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.采用開放定址法處理散列表的沖突時，其平均查找長度（） 。a低于鏈接法處理沖突b. 高于鏈接法處理沖突c與鏈接法處理沖突相同d高于二分查找7. 7.若需要利用形參直接訪問實參時，應將形參變量說明為 （）參數(shù)。a值b函數(shù)c指針d引用8. 8.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同的（） 。a行號b列號c元素值d非零元素個數(shù)9. 9

3、.快速排序在最壞情況下的時間復雜度為（） 。ao(log2n) bo(nlog2n) c0(n) d0(n2) 10.10. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為( )。a. o(n) b. o(1) c. o(log2n) d. o(n2) 一、二、運算題（每題6 分，共 24分）1.1.數(shù)據(jù)結構是指數(shù)據(jù)及其相互之間的_ 。 當結點之間存在m對 n（m：n）的聯(lián)系時，稱這種結構為_ 。2.2.隊列的插入操作是在隊列的_尾_進行，刪除操作是在隊列的_首_進行。3.3.當用長度為 n 的數(shù)組順序存儲一個棧時，假定用top=n 表示?？眨瑒t表示棧滿的條件是 _top=0_(要超出才為滿

4、 )_ 。4.4.對于一個長度為 n 的單鏈存儲的線性表， 在表頭插入元素的時間復雜度為_，在表尾插入元素的時間復雜度為_。5.5.設 w 為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4 個字節(jié)，行下標i 從 0到 7 ，列下標 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 的_ 樹。 一棵結點數(shù)為 n 的二叉樹，其所有結

5、點的度的總和是_ 。8.8.對 一 棵 二 叉 搜 索 樹 進 行 中 序 遍 歷 時 ， 得 到 的 結 點 序 列 是 一 個_ 。對一棵由算術表達式組成的二叉語法樹進行后序遍歷得到的結點序列是該算術表達式的_ 。9.9.對于一棵具有n 個結點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_ 個 ， 其 中 _ 個 用 于 指 向 孩 子 ，_ 個指針是空閑的。10. 10. 若對一棵完全二叉樹從0 開始進行結點的編號， 并按此編號把它順序存儲到一維數(shù)組 a 中，即編號為 0 的結點存儲到 a0 中。其余類推，則a i 元素的左孩子元素為 _,右孩子元素為 _ ，雙親元素為_ 。11. 11.在

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

7、據(jù)而生成的二叉搜索樹。3.3.對于圖 6 所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，試寫出：(1) 從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；4.4.已知一個圖的頂點集v 和邊集 e 分別為：v=1,2,3,4,5,6,7; e=,; 若存儲它采用鄰接表， 并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。三、四、閱讀算法（每題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)該算法的時間復雜度是多少？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; /查找成功，返回元素的下標else if (kmid.key) _; /在左子表上繼續(xù)查找else _; /在右子表上繼續(xù)查找 return -1; /查找失敗，返回 -1 五、六、編寫算法（共 8 分）hl 是單鏈表的頭指針，試寫出刪除頭結點的算法。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)系圖（或圖結構）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.有序序列后綴表達式（或逆波蘭式）9.9.2n n-1 n+1 10.10.2i+1 2i+2 (i-1)/2 11.11.開放定址法鏈接法12.12.快速歸并三、三、運算題（每題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 所示。3.3.dfs：bfs：4.4.拓樸排序為：4 3 6 5 7 2 1 四、四、閱讀算法（每題7 分，共 14 分）1.1.(1) 判斷 n 是否是素數(shù)（或質(zhì)數(shù)）（2）o（）2.2.功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表gl 所表示的圖。五、五、算法