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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)一、選擇題（共30分）數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中的計(jì)算機(jī)操作的（ B ）和以及它們之間存在的 （ D）和操作的學(xué)科。（1）A數(shù)據(jù)映像 B數(shù)據(jù)元素 C邏輯存儲 D計(jì)算方法（2）A結(jié)構(gòu) B運(yùn)算 C算法 D關(guān)系在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以將數(shù)據(jù)結(jié)構(gòu)分為：（ C ）。 A動(dòng)態(tài)結(jié)構(gòu)和表態(tài)結(jié)構(gòu) B 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)線性表的邏輯順序和存儲順序總是一致的，這種說法 （ B ）。 A正確 B不正確 算法分析的目的是（ C

2、），算法分析的兩個(gè)主要方面是（ A ）。（1）A找了數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系 C分析算法的效率以求改進(jìn) D分析算法的易懂性和文檔性（2）A空間復(fù)雜度和時(shí)間復(fù)雜度 B正確性C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 （ B ）。Ahead = NULL Bhead -next = NULLChead - next = head Dhead != NULL非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p應(yīng)該滿足 （ C ）。Ap- next = NULL Bp = NULLCp- next = head Dp = head在一個(gè)單鏈表中，刪除p所指

3、的結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行語句（ A ）。Ap-next =p-next -next ； Bp=p-next;p-next=p-next-next ； Cp-next= p-next ； Dp=p-next-next；線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址 （ D ）。A必須連續(xù) B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以對順序存儲的線性表，設(shè)其表長為n，且在任何位置插入或刪除操作都是等概率的，則插入一個(gè)元素平均要移動(dòng)表中（ B ）個(gè)元素。An/2 B(n+1)/2 C(n-1)/2 Dn與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是（）A插入刪除操作更容易 B可以進(jìn)行隨機(jī)

4、訪問C可以省略頭結(jié)點(diǎn)指針 D順序訪問相鄰結(jié)點(diǎn)更靈活棧的特點(diǎn)是（ B ）。插入操作在（）進(jìn)行，刪除操作在（）進(jìn)行。(1) A先進(jìn)先出 B先進(jìn)后出 在棧頂 在棧底 D棧頂或棧底 隨機(jī)位置一個(gè)棧的進(jìn)棧次序?yàn)閍,b,c,d,e，則棧不可能的出棧序列是 （ C ）。Aedcba Bdecba Cdceab Dabcde若已知一個(gè)棧的進(jìn)棧序列為1,2,3,4n，其出棧序列為p1,p2,p3,pn，若有p1=n，則pi(1=in)一定為（ ）。Ai Bn Cn-i+1 D不確定已知一棵完全二叉樹中共有768個(gè)結(jié)點(diǎn)，則該樹中共有（ B ）個(gè)葉子結(jié)點(diǎn)。A383 B384 C385 D386先序遍歷和中序遍歷相同

5、的二叉樹為（ D ）。A只有根結(jié)點(diǎn)的二叉樹 B根結(jié)點(diǎn)無左孩子的二叉樹C一般二叉樹 D只有根結(jié)點(diǎn)的二叉樹和所有結(jié)點(diǎn)只有右子樹的二叉樹一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有 （ C ）條邊。An Bn(n-1) Cn(n-1)/2 D2n( B )的鄰接矩陣是對稱矩陣。A有向圖 B無向圖 CAOV圖 鄰接表是圖的（ B ）。A順序存儲結(jié)構(gòu) B鏈?zhǔn)酱鎯Y(jié)構(gòu)C索引存儲結(jié)構(gòu) D散列存儲結(jié)構(gòu)對線性表進(jìn)行二分查找時(shí)，要求線性表必須（ C ）。A以順序方式存儲 B以鏈接方式存儲C以順序方式存儲且結(jié)點(diǎn)按關(guān)鍵字有序排列D以鏈接方式存儲且結(jié)點(diǎn)按關(guān)鍵字有序排列采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（

6、C ）。An Bn/2 C(n+1)/2 D(n-1)/2有一個(gè)有序序列（1,2,3,4,5,6），當(dāng)用二分法進(jìn)行查找值為4的結(jié)點(diǎn)時(shí)，經(jīng)過（ C ）次比較后查找成功。A1 B2 C3 D4二叉樹的第i層最多有（ C ）個(gè)結(jié)點(diǎn)。 A2i B2i C2i-1 D2i-1在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ C ）倍。 A1/2 B1 C2 D4一個(gè)無向連通圖（）最小生成樹。A只有一棵 B一棵或多棵 C一定有多棵 D不一定有一個(gè)圖的（）表示法是唯一的，而（）表示法是不唯一的。A三元組 B鄰接矩陣 C鄰接表 . 索引二、選擇題（每空1分，共30分）線性結(jié)構(gòu)中元素之間存在 的關(guān)系，樹形結(jié)構(gòu)中的

7、元素之間存在 的關(guān)系，圖形結(jié)構(gòu)中的元素之間存在 的關(guān)系。算法的五個(gè)特點(diǎn)是： ， ， ， ， 。棧是限定僅在表尾進(jìn)行 操作的線性結(jié)構(gòu)。表頭一端稱為 ，表尾的一端稱為 。隊(duì)列是限定僅在表尾進(jìn)行 和在表頭進(jìn)行 的線性表，其特點(diǎn)是： 。如有如下順序棧的定義#define MAXSIZE 500Typedef struct char dataMAXSIZE;int top;sqstack;sqstack ss;則?？盏臈l件是 ，棧滿的條件是 ，棧頂元素的表 達(dá)式是 ，棧底元素的表達(dá)式是 。在一個(gè)長度為 n的向量的第i個(gè)元素（1=i=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)的元素個(gè)數(shù)數(shù)為 。在雙鏈表中，每個(gè)結(jié)點(diǎn)

8、都有兩個(gè)指針域，一個(gè)指向 ，另一個(gè)指向 。 數(shù)據(jù)的邏輯結(jié)構(gòu)包括 ， ， ， 四種類型；其中 和 統(tǒng)稱為非線性結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)分為 和 。其中要求邏輯上相鄰的元素物理上也相鄰的存儲方式為 。 三、簡答題(每小題分，共分)下列程序段的時(shí)間復(fù)雜度是 O（mn） 。 for ( i = 0 ; i n ; i+ )for( j = 0 ; j 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)當(dāng)采用鏈表表示？(B ) A.經(jīng)常需要隨機(jī)地存取元素 B

9、.經(jīng)常需要進(jìn)行插入和刪除操作 C.表中元素需要占據(jù)一片連續(xù)的存儲空間 D.表中元素的個(gè)數(shù)不變4. 一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1B. 3 2 1 C. 3 1 2 D. 1 2 35. AOV網(wǎng)是一種（ D ）。 A有向圖 B無向圖 C無向無環(huán)圖 D有向無環(huán)圖6. 采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（ B）。A低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C與鏈接法處理沖突相同 D高于二分查找7. 若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（D ）參數(shù)。A值 B函數(shù) C指針 D引用8. 在稀疏矩陣的帶行指針向量

10、的鏈接存儲中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ A）。A行號 B列號 C元素值 D非零元素個(gè)數(shù)9. 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ D）。AO(log2n) BO(nlog2n) C0(n) D0(n2)10. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)二、 運(yùn)算題（每題 6 分，共24分）1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的聯(lián)系。當(dāng)結(jié)點(diǎn)之間存在M對N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_圖_。2. 隊(duì)列的插入操作是在隊(duì)列的_尾_進(jìn)行，刪除操作是在隊(duì)列的_首進(jìn)行。3. 當(dāng)用長度為N的數(shù)組順序存儲一個(gè)棧

11、時(shí)，假定用top=N表示?？?，則表示棧滿的條件是_top=0_(要超出才為滿)_。4. 對于一個(gè)長度為n的單鏈存儲的線性表，在表頭插入元素的時(shí)間復(fù)雜度為O(1)_，在表尾插入元素的時(shí)間復(fù)雜度為O(n_。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ù)元素共占用128_個(gè)字節(jié)。W中第6 行的元素和第4 列的元素共占用_44_個(gè)字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W6，3的起始地址為108_。6. 廣義表A= (a,(a,b),(a,b),c),則它的深度為_3_，它的長度為_3_。7. 二叉樹是指度為2

12、的_有序_樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)點(diǎn)的度的總和是_n-1_。8. 對一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)有序序列_。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的_后綴表達(dá)式_。9. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲時(shí)，其指針總數(shù)為_2n_個(gè)，其中n-1_個(gè)用于指向孩子_n+1個(gè)指針是空閑的。10. 若對一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點(diǎn)存儲到A0中。其余類推，則A i 元素的左孩子元素為2i+1_,右孩子元素為_2i+2_，雙親元素為_(i-1)/2。11. 在線性表

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

14、nt) sqrt(n); while (+ix) return 1; else return 0; (1) 指出該算法的功能；(2) 該算法的時(shí)間復(fù)雜度是多少？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

15、)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. 聯(lián)系 圖（或圖結(jié)構(gòu)）2. 尾 首3. top=04.

16、O（1） O（n）5. 128 44 1086. 3 3 7. 65565515132-145-2515637 圖78. 有序序列 后綴表達(dá)式（或逆波蘭式）9. 2n n-1 n+110. 2i+1 2i+2 (i-1)/211. 開放定址法 鏈接法12. 快速 歸并三、 運(yùn)算題（每題6分，共24分）1. （1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)（2） 三元組線性表的順序存儲表示如圖7示。2. 圖8如圖8圖83. DFS： BFS： 4. 拓樸排序?yàn)椋?4 3 6 5 7 2 1 四、 閱讀算法（每題7分，共14分）1. (1) 判斷

17、n是否是素?cái)?shù)（或質(zhì)數(shù)） （2）O（）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. 棧和隊(duì)列的共同特點(diǎn)是( A )。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出 C.都是先進(jìn)先出D.沒有共同點(diǎn) 2. 用鏈接方式存儲的隊(duì)列

18、，在進(jìn)行插入運(yùn)算時(shí)( D ). A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾指針可能都要修改3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？( D ) A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹4. 設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個(gè)元素占一個(gè)空間，問A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。 A688 B678 C692 D5. 樹最適合用來表示( )。 A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)6. 二叉樹的第k層的結(jié)點(diǎn)數(shù)最多

19、為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-17. 若有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. 對n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為 A. O（1） B. O（n） C. O（1og2n） D. O（n2）9. 對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時(shí)，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)， A1 B2 C3 D410. 設(shè)有6個(gè)結(jié)點(diǎn)的

20、無向圖，該圖至少應(yīng)有( )條邊才能確保是一個(gè)連通圖。A.5 B.6 C.7 D.8二、 填空題（每空1分，共26分）1. 通常從四個(gè)方面評價(jià)算法的質(zhì)量：_、_、_和_。2. 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為_。3. 假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個(gè)，樹的深度為_，樹的度為_。4. 后綴算式9 2 3 +- 10 2 / -的值為_。中綴算式（3+4X）-2Y/3對應(yīng)的后綴算式為_。5. 若用鏈表存儲一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二

21、叉樹共有_個(gè)指針域，其中有_個(gè)指針域是存放了地址，有_個(gè)指針是空指針。6. 對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_個(gè)和_個(gè)。7. AOV網(wǎng)是一種_的圖。8. 在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_條邊。9. 假定一個(gè)線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為_、_、_和_。10. 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度_。11. 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算

22、的時(shí)間復(fù)雜度為_，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。12. 在快速排序、堆排序、歸并排序中，_排序是穩(wěn)定的。三、 運(yùn)算題（每題 6 分，共24分）1. 在如下數(shù)組A中鏈接存儲了一個(gè)線性表，表頭指針為A 0.next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. 圖10請畫出圖10圖103. 已知一個(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,(

23、6,7)25; 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4. 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。四、 閱讀算法（每題7分，共14分）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,

24、,an）,寫出算法執(zhí)行后的返回值所表示的線性表。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

25、4.C 5.C 6.D 7.D 8.C 9.D 10.A二、 填空題（每空1分，共26分）1. 正確性 易讀性 強(qiáng)壯性 高效率2. O(n)3. 9 3 34. -1 3 4 X * + 2 Y * 3 / -5. 2n n-1 n+16. e 2e7. 有向無回路8. n(n-1)/2 n(n-1)9. （12，40） （ ） （74） （23,55，63）10. 增加111. O(log2n) O(nlog2n)12. 歸并三、 運(yùn)算題（每題6分，共24分）1. 線性表為：（78，50，40，60，34，90）2. 鄰接矩陣： 鄰接表如圖11所示：圖113. 用克魯斯卡爾算法得到的最小生成

26、樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 見圖1244444222552852834528434444422255285283452843圖12四、 閱讀算法（每題7分，共14分）1. （1）查詢鏈表的尾結(jié)點(diǎn)（2）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）返回的線性表為（a2,a3,an,a1） 2. 遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。五?算法填空（每空2分，共8 分）true BST-left BST-right 六、 編寫算法（8分）int CountX(LNode* HL,ElemType x) int i=0

27、; 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、在一個(gè)長度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 ( )。A n B n/2 C (n+1)/2 D (n-1)/22、在一個(gè)單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個(gè)s所指的結(jié)點(diǎn),則執(zhí)行( )。 A slink=plink; plin

28、k=s; B plink=s; slink=q; C plink=slink; slink=p; D q link=s; slink =p;3、 棧的插入和刪除操作在（ ）進(jìn)行。A 棧頂 B 棧底 C 任意位置 D 指定位置4、 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ） A 24 B 71 C 48 D 53二、 填空題（每空1分，共32分）1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、 _ 、_和_四種。2、一種抽象數(shù)據(jù)類型包括_和_兩個(gè)部分。3、在下面的數(shù)組a中鏈接存儲著一個(gè)線性表，表頭指針為ao.next，則該線性表為_。 a 0 1 2 3 4 5 6 7 8

29、 60 56 42 38 74 25 4 3 7 6 2 0 1datanext4、在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為_和_。5、用具有n個(gè)元素的一維數(shù)組存儲一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的_，該循環(huán)隊(duì)列的最大長度為_。6、當(dāng)堆棧采用順序存儲結(jié)構(gòu)時(shí)，棧頂元素的值可用表示；當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時(shí)，棧頂元素的值可用_表示。7、一棵高度為5的二叉樹中最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)；一棵高度為5的理想平衡樹中，最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)。8、在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為_，通常它包含三個(gè)域：一是_；二是_；三是_。9、在一個(gè)索

30、引文件的索引表中，每個(gè)索引項(xiàng)包含對應(yīng)記錄的_和_兩項(xiàng)數(shù)據(jù)。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、 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_,整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。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、已知一組記錄的排序碼為（46，79，56，38，40，80, 95，2

31、4），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。2、一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT0.12，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。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），（

32、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)序號從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)鄰接表表示時(shí) 四、 閱讀算法，回答問題（每小題8分，共16分）1、假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 30 91 34 1，請寫出輸出結(jié)果。# include # include consst int stackmaxsize = 30;typedef int elemtype;struct stack

33、 elemtype stack stackmaxsize; int top;# include “stack.h”Void main ( ) stack a; initstack(a); int x; cin x; while (x! = -1) push (a, x ); cin x;while (!stackempty (a) cout pop (a) ” ;cout end1;該算法的輸出結(jié)果為：_. 2、閱讀以下二叉樹操作算法，指出該算法的功能。Template void BinTree ：unknown (BinTreeNode*t) BinTreeNode *p =t, *temp

34、; if (p!=NULL) temp = pleftchild; pleftchild = prightchild; prightchild = temp; unknown(pleftchild); undnown(prightchild); 該算法的功能是：_ 五、 算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）對順序存儲的有序表進(jìn)行二分查找的遞歸算法 。 int Binsch( ElemType A ,int low ,int high,KeyType K ) if (low = high) int mid = 1 if ( K= = A mid .key ) return mid;

35、 else if ( K datedate)return1； if(s1dates2date)return1； ； ； if( )return1； if( )return1； ； 31閱讀下面的算法 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）,寫

36、出算法執(zhí)行后的返回值所表示的線性表。32假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下： typedef struct DateType dataMaxSize； int front2,rear2； Queue2；對于i=0或1，fronti和reari分別為第i個(gè)隊(duì)列的頭指針和尾指針。請對以下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。 int EnQueue (Queue2*Q,int i,DateType x) /若第 i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1；否則返回0 if(i1)return 0； if(Qreari=Qfront return0； Qdata

37、=x； Qreari= ; return1； 33已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。 typedef struct node DateType data； Struct node * next； ListNode； typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) LinkList s； If(T) Inorder(Tlchild)； If (!Tlchild)&(!Trchild) s=(ListNode*)malloc(sizeof(ListNode)； sdata=Td

38、ata； snext=Leafhead； Leafhead=s； Inorder(Trchild)； 對于如下所示的二叉樹 （1）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)； （2）說明該算法的功能。五、算法設(shè)計(jì)題（本題共10分）34閱讀下列函數(shù)arrange() int arrange(int a,int 1,int h,int x) /1和h分別為數(shù)據(jù)區(qū)的下界和上界 int i,j,t； i=1；j=h； while(ij) while(i=x)j-； while(i=x)i+； if(ij) t=aj；aj=ai；ai=t； if(ainext s2=s2next s2(或s2!=NULL或s2&!

39、s1) s1(或s1!=NULL或s1&!s2) return 031.（1）查詢鏈表的尾結(jié)點(diǎn) （2）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）返回的線性表為（a2,a3,an,a1）32. (i1)%2(或1i) Qreari (Qreari)%Maxsize33.(1)LeafheadFHGD （2）中序遍歷二叉樹，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以Leafhead為頭指針的逆序單鏈表（或按二叉樹中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表）。五、算法設(shè)計(jì)題（本題共10分） 34（1）該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a中的元素并返回分界值i，使所有x的元素均落在a1.i上，使所有x的元

40、素均落在ai1.h上。 （2）int f(int b,int n) 或 int f(int b,int n) int p,q； int p,q； p=arrange(b,0,n1,0)； p=arrange(b,0,n1,1)； q= arrange(b,p+1,n1,1)； q= arrange(b,0,p,0)； return qp； return pq； 一、選擇題（20分）1組成數(shù)據(jù)的基本單位是（ ）。 (A) 數(shù)據(jù)項(xiàng)(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量2設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D=1，2，3，4，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A是（ ）。(A) 線性結(jié)構(gòu)(B) 樹型結(jié)構(gòu)

41、(C) 圖型結(jié)構(gòu)(D) 集合3數(shù)組的邏輯結(jié)構(gòu)不同于下列（ ）的邏輯結(jié)構(gòu)。(A) 線性表(B) 棧 (C) 隊(duì)列(D) 樹4二叉樹中第i(i1)層上的結(jié)點(diǎn)數(shù)最多有（ ）個(gè)。(A) 2i(B) 2i(C) 2i-1(D) 2i-15設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為（ ）。(A) p-next=p-next-next(B) p=p-next(C) p=p-next-next(D) p-next=p6設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1，則

42、棧S的容量至少應(yīng)該是（ ）。(A) 6(B) 4(C) 3(D) 27將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為（ ）。(A) 100(B) 40(C) 55(D) 808設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B為結(jié)點(diǎn)A的雙親結(jié)點(diǎn)，則結(jié)點(diǎn)B的度數(shù)數(shù)為（ ）。(A) 3(B) 4(C) 5(D) 19根據(jù)二叉樹的定義可知二叉樹共有（ ）種不同的形態(tài)。(A) 4(B) 5(C) 6(D) 710. 設(shè)有以下四種排序方法，則（ ）的空間復(fù)雜度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希爾排序二、填空題(30分)1. 設(shè)順序循環(huán)隊(duì)列Q0：m-1的隊(duì)頭指針和隊(duì)尾指針分別為F和R

43、，其中隊(duì)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向當(dāng)前隊(duì)尾元素所在的位置，則出隊(duì)列的語句為F =_;。2. 設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為_，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為_。3. 設(shè)一棵二叉樹中有n個(gè)結(jié)點(diǎn)，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時(shí)，該二叉鏈表中共有_個(gè)指針域，_個(gè)空指針域。4. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)B，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列為_。5. 設(shè)無向圖G中有n個(gè)頂點(diǎn)和e條邊，則其對應(yīng)的鄰接表中有_個(gè)表頭結(jié)點(diǎn)和_個(gè)表結(jié)點(diǎn)。6. 設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，所有頂點(diǎn)的度數(shù)之和

44、為m，則e和m有_關(guān)系。7. 設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為_。8. 設(shè)一棵完全二叉樹中有21個(gè)結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點(diǎn)的編號是_，編號為8的左孩子結(jié)點(diǎn)的編號是_。9. 下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。int index(char s , char t )i=j=0;while(istrlen(s) & jnext=p-next; s-next=s5. n, 2e6. m=2e7. CBA8. 4，169. i-j+1，010. n-1三、應(yīng)用題1.

45、鏈?zhǔn)酱鎯Y(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。2. 哈夫曼樹略，WPL=783. (18,5,16,19,21,23)，(5，16，21，19，18，23)4. 線性探測：鏈地址法：5. 深度：，廣度：，最小生成樹T的邊集為E=(1，4)，(1，3)，(3，5)，(5，6)，(5,6)四、算法設(shè)計(jì)題1. 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對稱算法。typedef struct int s100; int top; sqstack;int lklistsymmetry(lklist *head) sqstack stack; stack.top= -1; lklist *p; f

46、or(p=head;p!=0;p=p-next) stack.top+; stack.sstack.top=p-data; for(p=head;p!=0;p=p-next) if (p-data=stack.sstack.top) stack.top=stack.top-1; else return(0); return(1);2. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。typedef char datatype;typedef struct node datatype data; struct node *lchild,*rchild; bitree;void createbitree

47、(bitree *&bt) char ch; scanf(%c,&ch); if(ch=#) bt=0; return;bt=(bitree*)malloc(sizeof(bitree); bt-data=ch;createbitree(bt-lchild); createbitree(bt-rchild);3. 設(shè)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct node *lchild,*rchild;bitree;void inorder(bitree *bt) if (bt!=

48、0) inorder(bt-lchild); if(minnumbt-key)flag=0; minnum=bt-key; inorder(bt-rchild);數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題(24分)1下面關(guān)于線性表的敘述錯(cuò)誤的是（ ）。(A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B) 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C) 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)(D) 線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)2設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（ ）個(gè)空指針域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m3設(shè)

49、順序循環(huán)隊(duì)列Q0：M-1的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ ）。(A) R-F(B) F-R(C) (R-F+M)M(D) (F-R+M)M4設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA5設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（ ）條邊。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-16設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為（ ）。(

50、A) 9(B) 10(C) 11(D) 127設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。(A) n-1(B) n(C) n+1(D) 2n-18設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（ ）。(A) 2，3，5，8，6(B) 3，2，5，8，6(C) 3，2，5，6，8(D) 2，3，6，5，8二、填空題(24分)1. 為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題是_和_。2. 下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。typedef struct int s100; int top

51、; sqstack;void push(sqstack &stack,int x)if (stack.top=m-1) printf(“overflow”);else _;_;3. 中序遍歷二叉排序樹所得到的序列是_序列（填有序或無序）。4. 快速排序的最壞時(shí)間復(fù)雜度為_，平均時(shí)間復(fù)雜度為_。5. 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_個(gè)空指針域。6. 設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=_。7. 設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，

52、75，80，31，56)，則利用篩選法建立的初始堆為_。8. 設(shè)某無向圖G的鄰接表為，則從頂點(diǎn)V1開始的深度優(yōu)先遍歷序列為_；廣度優(yōu)先遍歷序列為_。三、應(yīng)用題(36分)1 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink）。3 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62

53、時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長度。4 設(shè)一棵樹T中邊的集合為(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5 設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計(jì)題(16分) 1 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部

54、分的每個(gè)關(guān)鍵字均大于等于Ki。2 設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=AB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題1.D2.B3.C4.A5.A6.C7.B8.C二、填空題1. 構(gòu)造一個(gè)好的HASH函數(shù)，確定解決沖突的方法2. stack.top+，stack.sstack.top=x3. 有序4. O(n2)，O(nlog2n)5. N0-1，2N0+N16. d/27. (31，38，54，56，75，80，55，63)8. (1，3，4，2)，(1，3，2，4)三、應(yīng)用題1. (22，40，45，48，80，78)，(40，45，48，8

55、0，22，78)2. q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q;3. 2,ASL=91*1+2*2+3*4+4*2)=25/94. 樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略5. E=(1，3)，(1，2)，(3，5)，(5，6)，(6，4)6. 略四、算法設(shè)計(jì)題1. 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。void quickpass(int r, int s, int t) int i=s,

56、j=t, x=rs; while(ij)while (ix) j=j-1; if (ij) ri=rj;i=i+1; while (ij & rix) i=i+1; if (inext) for(q=hb;q!=0;q=q-next) if (q-data=p-data) break;if(q!=0) t=(lklist *)malloc(sizeof(lklist); t-data=p-data;t-next=hc; hc=t;數(shù)據(jù)結(jié)構(gòu)試卷（三）一、選擇題(30分)1設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，則數(shù)據(jù)結(jié)

57、構(gòu)A是（ ）。(A) 線性結(jié)構(gòu)(B) 樹型結(jié)構(gòu)(C) 物理結(jié)構(gòu)(D) 圖型結(jié)構(gòu)2下面程序的時(shí)間復(fù)雜為（ ）for（i=1，s=0； i=n； i+） t=1；for(j=1；jnext；p-data=q-data；p-next=q-next；free(q)；(B) q=p-next；q-data=p-data；p-next=q-next；free(q)；(C) q=p-next；p-next=q-next；free(q)；(D) q=p-next；p-data=q-data；free(q)；4設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（ ）個(gè)輔助記錄單元。(A) 1(B) n(C) nlog

58、2n(D) n25設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為( )。(A) 10，15，14，18，20，36，40，21(B) 10，15，14，18，20，40，36，21(C) 10，15，14，20，18，40，36，2l(D) 15，10，14，18，20，36，40，216設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為（ ）。(A) O(1)(B) O(log2n)(C)(D) O(n2)7設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（ ）。(A) n

59、，e(B) e，n(C) 2n，e(D) n，2e8. 設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（ ）條邊。(A) n(n-1)(B) n+1(C) n(D) n(n+1)9設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列（ ）方法可以達(dá)到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序10.下列四種排序中（ ）的空間復(fù)雜度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序二、填空殖(48分，其中最后兩小題各6分)1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括_和_兩種情況。2. 設(shè)一棵完全二叉樹中有500個(gè)結(jié)點(diǎn)，則該二

60、叉樹的深度為_；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有_個(gè)空指針域。3. 設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到_種不同的輸出序列。4. 設(shè)有向圖G用鄰接矩陣Ann作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的_，第i列上所有元素之和等于頂點(diǎn)i的_。5. 設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有_個(gè)度數(shù)為1的結(jié)點(diǎn)。6. 設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為_。7. _遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列（填先序、中序或后序）。8. 設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較