數(shù)據(jù)結(jié)構(gòu)期末模擬試題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上吉首大學試題庫課程測試試題（ 卷）-以下為教師填寫-I、命題院（部）： 數(shù)學與計算機科學學院 II、課程名稱： 數(shù)據(jù)結(jié)構(gòu) III、測試學期：20 20 學年度第 學期IV、測試對象： 學院 專業(yè) 級 班V、問卷頁數(shù)（A4）： 頁VI、答卷頁數(shù)（A4）： 頁VII、考試方式： 閉卷 （開卷、閉卷或課程小論文，請?zhí)顚懬宄￢III、問卷內(nèi)容：（請老師在出題時安排緊湊，填空題象征性的留出一點空格，學生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號）一、 單選題（每題 2 分，共20分）1. 對一個算法的評價，不包括如下（ ）方面的內(nèi)容。 A健壯性和可讀性 B并

2、行性 C正確性 D時空復(fù)雜度2. 在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(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. 對線性表，在下列哪種情況下應(yīng)當采用鏈表表示？( ) A.經(jīng)常需要隨機地存取元素 B.經(jīng)常需要進行插入和刪除操作 C.表中元素需要占據(jù)一片連續(xù)的存儲空間 D.表中元素的個數(shù)不變4. 一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( )

3、A. 2 3 1B. 3 2 1 C. 3 1 2 D. 1 2 35. AOV網(wǎng)是一種（ ）。 A有向圖 B無向圖 C無向無環(huán)圖 D有向無環(huán)圖6. 采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。A低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C與鏈接法處理沖突相同 D高于二分查找7. 若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（ ）參數(shù)。A值 B函數(shù) C指針 D引用8. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（ ）。A行號 B列號 C元素值 D非零元素個數(shù)9. 快速排序在最壞情況下的時間復(fù)雜度為（ ）。AO(log2n) BO(nlog2n) C

4、0(n) D0(n2)10. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)二、 運算題（每題 6 分，共24分）1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_。當結(jié)點之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_。2. 隊列的插入操作是在隊列的_進行，刪除操作是在隊列的_進行。3. 當用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則表示棧滿的條件是_。4. 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為_，在表尾插入元素的時間復(fù)雜度為_。5. 設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4

5、個字節(jié)，行下標i從0到7 ，列下標j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用_個字節(jié)。W中第6 行的元素和第4 列的元素共占用_個字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W6，3的起始地址為_。6. 廣義表A= (a,(a,b),(a,b),c),則它的深度為_，它的長度為_。7. 二叉樹是指度為2的_樹。一棵結(jié)點數(shù)為N的二叉樹，其所有結(jié)點的度的總和是_。8. 對一棵二叉搜索樹進行中序遍歷時，得到的結(jié)點序列是一個_。對一棵由算術(shù)表達式組成的二叉語法樹進行后序遍歷得到的結(jié)點序列是該算術(shù)表達式的_。9. 對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_個，其

6、中_個用于指向孩子，_個指針是空閑的。10. 若對一棵完全二叉樹從0開始進行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點存儲到A0中。其余類推，則A i 元素的左孩子元素為_,右孩子元素為_，雙親元素為_。11. 在線性表的散列存儲中，處理沖突的常用方法有_和_兩種。12. 當待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_排序；當待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用_排序。三、 運算題（每題6分，共24分）1. 已知一個6´5稀疏矩陣如下所示，試：（1） 寫出它的三元組線性表；（2） 給出三元組線性表的順序存儲表示。2. 設(shè)

7、有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。3. 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：(1) 從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4. 已知一個圖的頂點集V和邊集E分別為： 圖6 V=1,2,3,4,5,6,7;E=<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<

8、;5,1>,<5,7>,<6,1>,<6,2>,<6,5>若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。四、 閱讀算法（每題7分，共14分）1. int Prime(int n) int i=1; int x=(int) sqrt(n); while (+i<=x) if (n%i=0) break; if (i>x) return 1; else return 0; (1) 指出該算法的功能；(2) 該算法的時間復(fù)雜度是多

9、少？2. 寫出下述算法的功能： void AJ(adjlist GL, int i, int n) Queue Q; InitQueue(Q); cout<<i<<' ' visitedi=true; QInsert(Q,i); while(!QueueEmpty(Q) int k=QDelete(Q); edgenode* p=GLk; while(p!=NULL) int j=p->adjvex; if(!visitedj) cout<<j<<' ' visitedj=true; QInsert(Q,j)

10、; p=p->next; 五、 算法填空（共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; /查找成功，返回元素的下標 else if (K<mid.key) _; /在左子表上繼續(xù)查找 else _; /在右子表上繼續(xù)查找return -1; /查找失敗，返回-1六、 編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點的算法。ElemT

11、ype 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. 聯(lián)系 圖（或圖結(jié)構(gòu)）2. 尾 首3. top=04. O（1） O（n）5. 128 44 1086. 3 3 65515132-145-2515637 圖77. 有序 n-18. 有序序列 后綴表達式（或逆波蘭式）9. 2n n-1 n+110. 2i+1 2i+2 (i-1)/211. 開放定址法 鏈接法12. 快速 歸并三、 運算題（每題6分，共24分）1. （1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)（2） 三元組線性表的順序存儲表示如圖7示。圖82. 如圖8所示。3. DFS： BFS： 4. 拓樸排序為： 4 3 6 5 7 2 1 四、 閱讀算法（每題7分，共14分）1. (1) 判斷n是否是素數(shù)（或質(zhì)數(shù)） （2）O（）2. 功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。五、 算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 六、