完整版數(shù)據(jù)結(jié)構(gòu)試題及答案10套

1、 分）分，共20一、單選題（每題 2 ）方面的內(nèi)容。1.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（B 1. D時(shí)空復(fù)雜度 C正確性 A健壯性和可讀性 B并行性指向的結(jié)中，要向表頭插入一個(gè)由指針p 2.在帶有頭結(jié)點(diǎn)的單鏈表HL2. )。點(diǎn)，則執(zhí)行(A B. p-next=HL; HL=p; A. p-next=HL-next; HL-next=p; D. HL=p; p-next=HL; C. p-next=HL; p=HL; ) ( B 3.對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？3. B.經(jīng)常需要進(jìn)行插入和刪除操作 A.經(jīng)常需要隨機(jī)地存取元素 表中元素的個(gè)數(shù)不變 D. C.表中元素需要占據(jù)一片連續(xù)的

2、存儲(chǔ)空間 序列的是輸出1 2 3，則下列序列中不可能是棧的4. 4.一個(gè)棧的輸入序列為 ) C ( B. 3 2 1 A. 2 3 1 D. 1 2 3 C. 3 1 2 。 ） 5.AOV網(wǎng)是一種（D 5. 有向無環(huán)圖 DC無向無環(huán)圖 B無向圖 A有向圖 。B）6. 6.采用開放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（ 高于鏈接法處理沖突B. A低于鏈接法處理沖突 D高于二分查找 C與鏈接法處理沖突相同 ）參數(shù)。 7.若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（D 7. D引用 B 函數(shù) C指針A值 在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具 8.8. ）。有相同的

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

4、空，則 3.3.當(dāng)用長(zhǎng)度為N 表示棧滿的條件是_top=0_(要超出才為滿)_。 4. 4.對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度 。_，在表尾插入元素的時(shí)間復(fù)雜度為_為0從個(gè)字節(jié)，行下標(biāo)i設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用45.5. 個(gè)字_W的數(shù)據(jù)元素共占用到3 ，則二維數(shù)組到7 ，列下標(biāo)j從0若按行_列的元素共占用個(gè)字節(jié)。中第6 行的元素和第4 節(jié)。W的起始，3，其起始地址為100，則二維數(shù)組元素W6順序存放二維數(shù)組W _。地址為，它的長(zhǎng)度為則它的深度為_6.廣義表A= (a,(a,b),(a,b),c),6. _。的二叉一棵結(jié)點(diǎn)數(shù)為N的_樹。二叉樹是指度為7.

5、 7.2 _。樹，其所有結(jié)點(diǎn)的度的總和是個(gè)一序列是，時(shí)得到的結(jié)點(diǎn)一棵二叉搜索樹進(jìn)行中序遍歷對(duì)8. 8. 對(duì)一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到。_ 。的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的_個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為n 9.對(duì)于一棵具有9. ，子向孩用中_個(gè)于指_個(gè)，其 個(gè)指針是空閑的。_并按此編號(hào)把它順序存開始進(jìn)行結(jié)點(diǎn)的編號(hào)，若對(duì)一棵完全二叉樹從010. 10. A i 中。其余類推，則的結(jié)點(diǎn)存儲(chǔ)到A0儲(chǔ)到一維數(shù)組A中，即編號(hào)為0，雙親元素為_,右孩子元素為元素的左孩子元素為 。_有方法的常用，存儲(chǔ)中處理沖突性11. 11.在線表的散列 _兩種。_和當(dāng)待排序的記錄數(shù)較大，

6、排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用12.12. 排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序_ 排序。是穩(wěn)定時(shí)，宜采用_ 分）6分，共24三、運(yùn)算題（每題 10000?00000?00?010?000?02?00050?70000? 稀疏矩陣如下所示，?5已知一個(gè)1.6 試： 寫出它的三元組線性表；（1） ）（2給出三元組線性表的順序存儲(chǔ)表示。 試畫出從空樹起，, 46, 25, 78, 62, 12, 80 2.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。并且每個(gè)頂點(diǎn)鄰接表中的所示的有向圖若存儲(chǔ)它采用鄰接表，63.對(duì)于圖 邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接

7、的，試寫出： (1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹； (2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 分別為：V和邊集E4.已知一個(gè)圖的頂點(diǎn)集 V=1,2,3,4,5,6,7; E=,; 并且每個(gè)頂若存儲(chǔ)它采用鄰接表，點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序6 圖號(hào)從小到大的次序鏈接的，按主教材 中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。 14分）四、閱讀算法（每題7分，共 int Prime(int n) 1.1. int i=1; int x=(int) sqrt(n); while (+ix) return 1; else return 0; 指出

8、該算法的功能；(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) int mid=_； if (K=Amid.key) return mid; /查找成功，返回

9、元素的下標(biāo) else if (Kmid.key) _; /在左子表上繼續(xù)查找 else _; /在右子表上繼續(xù)查找 return -1; /查找失敗，返回-1 六、編寫算法（共8分） HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。 ElemType DeleFront(LNode * & HL) 參考答案 一、單選題（每題2分，共20分） 10.C 9.D 4.C 5.D 6.B 7.D 8.A 1.B 2.A 3.B 填空題（每空1分，共26分）二、 聯(lián)系 圖（或圖結(jié)構(gòu)）1. 尾 首2. top=0 3. ）O（nO4.（1） 108 44 5.128 3 6.3 n-1 7.有序 5 5

10、6 后綴表達(dá)式（或逆波蘭式） 8.有序序列 n+1 n-1 9.2n 1 1 5 (i-1)/2 2i+2 10.2i+1 -1 3 2 鏈接法 11.開放定址法 -2 5 4 歸并 12.快速 5 1 5 分）三、運(yùn)算題（每題6分，共24 ) (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分1.（1） 7 6 3 三元組線性表的順序存儲(chǔ)表示如圖7示。（2） 7 圖 圖8 所示。2.如圖8 ? 3.DFS： ? BFS： 拓樸排序?yàn)椋?. 4 3 6 5 7 2 1 14分）7四、閱讀算法（每題分，共 n判斷1.(1) 是否是素?cái)?shù)（或質(zhì)數(shù)） n） O（

11、 （2）2.功能為：從初始點(diǎn)v出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 i五、算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 六、編寫算法（8分） ElemType DeleFront(LNode * & HL) if (HL=NULL) 散牲?空表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.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)(

12、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，A22存放 (10)位置在676，每個(gè)元素占一個(gè)空間，問A33存放在什么位置？腳注(10)(10)(10)表示用10進(jìn)制表示。 A688 B678 C692 D696 5.樹最適合用來表示( )。 A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù) 6.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為( ). kk

13、-1 D. 2 C.2K-1 B.2K+1 A 2 -1 7.若有18個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放A1中， 現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為 A. O（1） B. O（n） C. O（1ogn） D. O（n2） 29.對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選 用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)， A1 B2 C3 D4 10.設(shè)有6個(gè)結(jié)點(diǎn)的無

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

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

16、篩運(yùn)算的時(shí)間復(fù)雜度為_11. _。整個(gè)堆排序過程的時(shí)間復(fù)雜度為 _排序是穩(wěn)定的。12.在快速排序、堆排序、歸并排序中， 分）運(yùn)算題（每題三、 6 分，共24 ，試寫出該A 0.next1.在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為 線性表。 0 1 2 3 4 5 A 6 7 data 60 50 78 90 34 40 1 next 0 3 5 4 7 2 2.請(qǐng)畫出圖10的鄰接矩陣和鄰接表。 3.已知一個(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)

17、9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 圖10 用克魯斯卡爾算法得到最小生成樹，試寫出在最 小生成樹中依次得到的各條邊。 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； 請(qǐng)回答下列問題： （1）說明語句S1的功能； （2）說明

18、語句組S2的功能； （3）設(shè)鏈表表示的線性表為（a,a, ,a）,寫出算法執(zhí)行后的返回值所n12表示的線性表。 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)

19、參考答案 一、 單選題（每題2分，共20分） 1.A 2.D 3.D 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 3 4.-1 3 4 X * + 2 Y * 3 / - 5.2n n-1 n+1 6.e 2e 7.有向無回路 8.n(n-1)/2 n(n-1) 9.（12，40） （ ） （74） （23,55，63） 10.增加1 11.O(logn) O(nlogn) 2212.歸并 三、運(yùn)算題（每題6分，共24分） 1.線性表為：（78，50，40，60，34，90） 011

20、10?11100?10111?01101?01101? 鄰接矩陣：2. 鄰接表如圖11所示： 11 圖 3.用克魯斯卡爾算法得到的最小生成樹為： (4,7)20 (2,5)10, (1,4)8, (1,3)5, (4,6)4, (1,2)3, 12 4.見圖 2 2 2 2 4 4 2 5 5 4 4 4 5 4 3 8 8 2 5 3 4 8 12 圖 分）7分，共14四、閱讀算法（每題 ）查詢鏈表的尾結(jié)點(diǎn)1.（1 （2）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) ） ,a （3）返回的線性表為（a,a,a12n3 2.遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。 分）8 五、算法填空（每空2分，共

21、BST-right BST-left true 六、編寫算法（8分） int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計(jì)數(shù)器 while(p!=NULL) if (P-data=x) i+; p=p-next; x結(jié)點(diǎn)個(gè)數(shù)i /while, 出循環(huán)時(shí)中的值即為return i; /CountX 一、單選題（每小題2分，共8分） 1、在一個(gè)長(zhǎng)度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長(zhǎng)度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 ( )。 A n B n/2 C (n+1)/2 D (n-1

22、)/2 2、在一個(gè)單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個(gè)s所指的結(jié)點(diǎn),則執(zhí)行( )。 A slink=plink; plink=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)路 徑長(zhǎng)度為（ ） A 24 B 71 C 48 D 53 二、填空題（每空1分，共32分） 1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、 _ 、_和_四種。 2

23、、一種抽象數(shù)據(jù)類型包括_和_兩個(gè)部分。 3、在下面的數(shù)組a中鏈接存儲(chǔ)著一個(gè)線性表，表頭指針為ao.next，則該線性表為_。 a 0 1 2 3 4 5 6 7 8 data 25 74 60 56 42 38 next 1 0 6 3 7 2 4 判斷鏈HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，4、在以 _。表為空的條件分別為_和個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向、用具有n5 。_，該循環(huán)隊(duì)列的最大長(zhǎng)度為_隊(duì)首元素的表示；6、當(dāng)堆棧采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用 表示。當(dāng)堆棧采用鏈接存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用_個(gè)結(jié)點(diǎn)，最多含有、一棵高度為75的二叉樹中

24、最少含有 個(gè)結(jié)點(diǎn)；個(gè)結(jié)點(diǎn)，最多含有_一棵高度為5的理想平衡樹中，最少含有 個(gè)結(jié)點(diǎn)。_，通常它包含三個(gè)域：、在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為_8 _。；三是；二是一是_和_、在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對(duì)應(yīng)記錄的9_兩項(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、在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為 _,整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。 12、在對(duì)m階的B_樹插入元素的過程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引 項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)

25、鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于_個(gè)，則必須把它分裂為_個(gè)結(jié)點(diǎn)。 三、運(yùn)算題（每小題6分，共24分） 1、已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對(duì)其進(jìn)行快速排序的每一次劃分結(jié)果。 2、一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT0.12，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。 3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。 4、

26、已知一個(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），（5，8），（5，9），（6，7），（7，8），（8，9） 當(dāng)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫出從頂點(diǎn)V出發(fā)按深度優(yōu)先0搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。 假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序鏈接的。 圖 深度優(yōu)先序列 廣度優(yōu)先序列 鄰接矩陣表示時(shí) 鄰接表表示時(shí) 四、閱讀算法，回答問題（每小題8分，共16分） 1、假定從鍵盤上輸入一批整數(shù)，依次為：78 63

27、45 30 91 34 1，請(qǐng)寫出輸出結(jié)果。 # include # include consst int stackmaxsize = 30; typedef int elemtype; struct stack 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

28、 end1; 該算法的輸出結(jié)果為： _. 2、閱讀以下二叉樹操作算法，指出該算法的功能。 Template void BinTree ： unknown (BinTreeNode*t) BinTreeNode *p =t, *temp; if (p!=NULL) temp = pleftchild; pleftchild = prightchild; prightchild = temp; unknown(pleftchild); rightchild); undnown(p 該算法的功能是：_ 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分） 對(duì)順序存儲(chǔ)的有序表進(jìn)行二分查找的遞歸算法

29、。 int Binsch( ElemType A ,int low ,int high,KeyType K ) if (low = high) int mid = 1 if ( K= = A mid .key ) return mid; else if ( K Amid.key) return 2 else return 3 else return 4 六、編寫算法（10分） 編寫算法，將一個(gè)結(jié)點(diǎn)類型為L(zhǎng)node的單鏈表按逆序鏈接，即若原單鏈表中存儲(chǔ)元素的次序?yàn)閍，a，a，則逆序鏈接后變?yōu)? a，a，a。 1nn-11nn-1Void contrary (Lnode * & HL) 數(shù)據(jù)結(jié)構(gòu)試

30、題（答案） 一、單選題（每小題2分，共8分） 題 號(hào) 1 2 3 4 B D A 案答 C 分）二、填空題（每空1分，共32 1： 集合、線性、樹、圖； 數(shù)據(jù)描述、操作聲名；：2 ；744260255638 3：（，） ；nextHL=HL ；next =NULLHL ：45： 前一個(gè)位置； n-1； 6： S.stack S.top; HSdata; 7： 5 31 8： 邊結(jié)點(diǎn)、鄰接點(diǎn)域、權(quán)域、鏈域； 9： 索引值域、開始位置域； 10： 10、3、3、B、I和J； 11： O（logn）、O(nlogn); 2212： m 、 m - 1 三、運(yùn)算題（每小題6分，共24分） 1、 劃分次

31、序 劃分結(jié)果 38 24 40 46 56 80 第一次 95 79 24 38 40 46 56 80 第二次 95 79 24 38 40 第三次46 56 80 95 79 24 38 第四次 40 46 56 80 95 79 24 38 40 46 56 第五次79 80 95 24 38 40 第六次 46 56 79 80 95 2、 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找長(zhǎng)度：ASL=14/10= 1.4 SUCC3、此二叉樹的后序遍歷結(jié)果是：EDCBIHJGFA 4、 圖 深度優(yōu)

32、先序列 廣度優(yōu)先序列 0，1，4，2，7，3，8，6，5，5鄰接矩陣表示時(shí) 20，1，8，3，4，6，7，9 9 0，鄰接表表示時(shí) 4，1，3，7，2，8，04，38，95，67，12 ，6，9，5 四、閱讀算法，回答問題（每小題8分，共16分） 1、 1、該算法的輸入結(jié)果是：34 91 30 45 63 78 2、 2、該算法的功能是：交換二叉樹的左右子樹的遞歸算法。 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分） 1、1是：（low + high）/2; 2是： Binsch(A,low,mid1,K); 3是： Binsch(A,mid+1,high,K); 4是： -1； 六、

33、編寫算法（10分） 根據(jù)編程情況，酌情給分。 Lnode *P=HL; HL=NULL; While (p!=null) Lnode*q=p; P=pnext; qnext=HL; HL=q; 第一部分 選擇題(30分) 一、項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。 1算法指的是（ ） A計(jì)算機(jī)程序 B解決問題的計(jì)算方法 C排序算法 D解決問題的有限運(yùn)算序列 2線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ ） A必須是不連續(xù)的 B連續(xù)與否均可 C必須是連續(xù)的 D和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù) 3將長(zhǎng)度為n

34、的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（ ） AO（1） BO（n） CO（m） DO（m+n） 4由兩個(gè)棧共享一個(gè)向量空間的好處是：（ ） A減少存取時(shí)間，降低下溢發(fā)生的機(jī)率 B節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率 C減少存取時(shí)間，降低上溢發(fā)生的機(jī)率 D節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率 5設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（ ） Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m 6如下陳述中

35、正確的是（ ） A串是一種特殊的線性表 B串的長(zhǎng)度必須大于零 C串中元素只能是字母 D空串就是空白串 7若目標(biāo)串的長(zhǎng)度為n，模式串的長(zhǎng)度為n/3，則執(zhí)行模式匹配算法時(shí)，在最n壞情況下的時(shí)間復(fù)雜度是（ ） 323） （n DO CO（n） OO A （） B（n） 8一個(gè)非空廣義表的表頭（ ） A不可能是子表 B只能是子表 C只能是原子 D可以是子表或原子 9假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表 5 3 3 2 0 0?8060?806?0?806?077000006800? ） 對(duì)應(yīng)的稀疏矩陣是（ 0000?00?500004B.A.0000?0070.D0005040?0 ?20

36、00C.? ?003000000054?004?5 ?00300000? 則度為1,2 的結(jié)點(diǎn)個(gè)數(shù)為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為10在一棵度為3的樹中,度為) 0的結(jié)點(diǎn)個(gè)數(shù)為( 7 D C6 B5 A4 ) ,零元素的個(gè)數(shù)為( 11在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中222e Dne Cn Ae B2e v,則刪除與某個(gè)頂點(diǎn)個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示12假設(shè)一個(gè)有ni) 相關(guān)的所有弧的時(shí)間復(fù)雜度是( O(n*e) D CO(n+e) B O(e) AO(n) ）進(jìn)20，35，15，27，6813用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47 行排序時(shí)，序列的變化情況如下：84 ，68，35，47，27，