2008-09(2)數(shù)據(jù)結(jié)構(gòu)期末試卷(D.

1、汕頭職業(yè)技術(shù)學(xué)院2008-2009 學(xué)年第二學(xué)期期末試卷（D課程名稱數(shù)據(jù)結(jié)構(gòu)學(xué)分 _ 擬題人何漢陽審題人 _系（校區(qū)計算機系班級_ 學(xué)號_姓名_題號一二三四五六七八總分評卷人得分一、填空（26 分，每空一分1._ 在設(shè)計算法和程序時，不僅要考慮數(shù)據(jù)的 _ 其_ 而且要考慮數(shù)據(jù)在存儲器中的_。2. 算法設(shè)計的基本要求是：_ 、_和_。3._ 估算算法運行時間的基本考慮是：確定問題的_口確定算法執(zhí)行基本操作的_ 在難以精確計算基本執(zhí)行次數(shù)的情況下，只考慮相對于問題規(guī)模 N 的_ 。4. 對于長度為 n 的順序表的刪除算法，它的最壞情況時間復(fù)雜性及其量級分別是_和_，平均時間復(fù)雜性及其量級分別為_

2、和_。5串的堆型存儲結(jié)構(gòu)的特點是：仍以一組地址_ 的存儲單元存放串的字符序列，但其存儲空間是在算法執(zhí)行過程中 _得到的。6._ 順序隊列存在假滿現(xiàn)象，解決這個問題的常用方法是構(gòu)建_ 。7圖的常用存儲結(jié)構(gòu)有 _和_ ,Prim 算法是選用_ 存儲圖中的所有邊。8. 解決散列查找的兩個主要問題是:(1 構(gòu)造一個計算簡單且沖突盡量少的、地址分布比較_ 的_； (2 擬定解決_ 的方案。9. 假定一個順序表的長度為 50,并假定查找每個元素的概率都相同，則在查找成 功情況下的平均查找長度_ 在查找不成功情況下的平均查找長度_。10關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的排序方法是 _ 卡序；每次使兩

3、個相鄰的有序表合成一個有序表的排列方法叫做_ 卡序。二、選擇題(在正確答案上打“5 20 分,每小題 2 分1、 下面關(guān)于線性表的敘述中，錯誤的是_。A 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B 線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元C 線性表采用鏈接存儲，可以隨機存取表中的任一結(jié)點D 線性表采用順序存儲，無須為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間2、若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用_ 儲方式最節(jié)省運算時間。A 單鏈表 B 僅有頭指針的單循環(huán)鏈表C 雙鏈表 D 僅有尾指針的單循環(huán)鏈表3、 下列排序算法中,_卡序在每趟結(jié)束后不一

4、定能選出一個元素放到其排 好序的最終位置上。A 選擇 B 冒泡 C 歸并 D 堆4、 有一散列表，表長度 m 為 100 采用除余法構(gòu)造散列函數(shù)，即 H(K=K MODP(PWn 為使散列函數(shù)具有較好的性能,P 的選擇應(yīng)是_。A99 B97 C91 D935、 在包括 n 個鍵值的二叉排序樹中查找一個鍵值，其平均比較次數(shù)的量級為。AO(n BO(log2n CO( nlog2 n DO( n26 對有 14 個元素的有序表 A1.14作二分查找，查找元素 A4時的被比較元素 依次為_ 。A A1,A2,A3,A4 B A1,A14,A7,A4C A7,A3,A 5 ,A4 C A7,A 5 ,

5、A3,A47、 假設(shè)一個棧的輸入序列為 A,B,C,D,E,則下列序列中不可能是棧的輸出序列的是_0AB,C,D,A,E BE,D,A,C,BCB,C,A,D,E DA,E,D,C,B8、 前序遍歷序列和中序遍歷序列相同的非空二叉樹是：A 任一結(jié)點均無右子樹的非空二叉樹 B 根結(jié)點無右子樹的非空二叉樹C 任一結(jié)點均無左子樹的非空二叉樹 D 根結(jié)點無左子樹的非空二叉樹9、 圖中有關(guān)路徑的定義是 _oA 由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列B 由不同頂點所形成的序列C 由不同邊所形成的序列 D 上述定義都不是10、 下列說法不正確的是 _oA 圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次B

6、 圖的深度遍歷不適用于有向圖C 遍歷的基本算法有兩種：深度遍歷和廣度遍歷 D 圖的深度遍歷是一個遞歸過 程三、作圖題（14 分,每小題 7 分1.先將下列樹轉(zhuǎn)化為二叉樹，然后畫出其二重鏈?zhǔn)浇Y(jié)構(gòu)圖。2.寫出下列圖的鄰接矩陣和鄰接鏈表表示法四、已知一棵二叉樹的先序遍歷序列為：ABCDEFGHI,中序遍歷序列為:BCAEDGHFI,試畫出這棵二叉樹。（10 分五、在一個帶頭結(jié)點的單鏈表中，元素值遞增有序，編寫程序，在單鏈表中插入一 元素后，表中元素值仍保持遞增有序。（10 分六、寫出順序表上實現(xiàn)順序查找的算法，并將監(jiān)視哨設(shè)在高端。（10 分七、為了提高冒泡排序算法的效率，可在算法中設(shè)置一布爾變量 n

7、o Swap 來檢查 一次內(nèi)循環(huán)中有無記錄交換，若無交換算法即可中止結(jié)束，請用 C 語言編寫改進(jìn)后的 冒泡排序算法。（共 10 分2008-2009 學(xué)年第二學(xué)期期末試卷（D 答案課程名稱 數(shù)據(jù)結(jié)構(gòu) 擬題人何漢陽、填空（每空一分,26 分1、 邏輯結(jié)構(gòu)，運算，存儲結(jié)構(gòu)（物理結(jié)構(gòu)2、 易讀性，健壯性,高效率3、規(guī)模，次數(shù),增長率4、n-1,0(n, (n-1/2, O(n5、連續(xù)，動態(tài)分配6 循環(huán)隊列7、鄰接矩陣，鄰接鏈表，鄰接矩陣 8 均勻，散列函數(shù)沖突 9、51/2,50 10、冒泡,歸并二、選擇題(每小題 2 分，共 20 分15、CDCBB 610、CBCAB三、作圖題(14 分,每小題

8、 7 分 1、解:2、解:I)8888888888 010101011110四、 解 （10 分。I)五、解： （10 分）/ L 是帶頭結(jié)點的單鏈表，x 是待插入的整數(shù)。typedef struct node int data; struct node *next; LINKLIST; voidLin kList In sertSort(LINKLIST *L, i nt x LINKLIST *pre,*p,*s; s = (LINKLIST*malloc(sizeof(LINKLIST; s-data = x; s-next=NULL; pre = L; p = L-next; /設(shè)置一

9、 前一后指針 pre, p while(p != NULL /使 p 指向數(shù)據(jù)域不小于 x 的結(jié)點 if(p-data next; else break; pre-next = s; / 在指針 pre和 p 之間插入 s 結(jié)點 s-next = p; 六、解(10 分)。/*數(shù)據(jù)結(jié)構(gòu)按課 本描述*/ intseq_search1(KEYTYPE k, SSTABLE st int i=0; /* 假定從 0 號單元開始 存放數(shù)據(jù) */st.rst.len.key=k; /* 監(jiān)視哨設(shè)在高端 */ while(st.ri.key != k i+;if(i=st.len reture 0; else return i+1; 七、解(10 分)。void Sort_Bubble1(RecordNode *r,i nt n int i, j; int no s