數(shù)據(jù)結(jié)構(gòu)95952

1、一、單項(xiàng)選擇題，請?jiān)诿啃☆}的四個(gè)備選答案中選擇一個(gè)，將其前面的字母填入（ ）中， 多選不得分。（每小題分，共分） 已知線性表L（ a ,a ,a ），下列說法正確的是（ ）。 1 2 n A 每個(gè)元素都有一個(gè)直接前趨和一個(gè)直接后繼。 B 線性表中至少要有一個(gè)元素。 C 表中元素必須由小到大或由大到小排列。 D 除第一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)直接前趨和一個(gè)直接后繼。 若某線性表最常用的操作是取第 i 個(gè)元素，則采用（ ）存儲方式最節(jié)省運(yùn)算時(shí)間。 A 順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e ,e , e ,e , e ,e ,依次通過棧S進(jìn)

2、入隊(duì)列Q，即一個(gè)元1 2 3 4 5 6 素出棧后即進(jìn)入隊(duì)列Q，若個(gè)元素的出隊(duì)序列是e , e ,e , e ,e , e ，則棧S的容量至少 2 4 3 6 5 1 應(yīng)該是（ ）。 A B C D 稀疏矩陣一般的壓縮存儲方法有（ ）兩種。 A二維數(shù)組和三維數(shù)組 B三元組表和哈希表 C三元組表和十字鏈表 D哈希表和十字鏈表 5. 中序遍歷一顆二叉排序樹所得到的結(jié)點(diǎn)訪問序列是結(jié)點(diǎn)值的（ ）序列。 A 遞增或遞減 B 遞減 C 遞增 D 無序 一棵深度為的滿二叉樹中節(jié)點(diǎn)總數(shù)為（ ）。 A B C D 一個(gè)單鏈表中，已知*q 結(jié)點(diǎn)是*p 結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在*q 和*p 之間插入*s 結(jié)點(diǎn)， 則必須

3、執(zhí)行（ ）操作。 Aqnext=p next; p next=s; Bqnext=s; snext= p ; Cp next=snext; snext=p Dp next=s; snext=q 在順序表2、5、7、10、14、15、18中，用二分法查找關(guān)鍵碼 12需做（ ）次關(guān)鍵碼 比較。 A2 B3 C1 D5 9. 一個(gè)具有 n 個(gè)頂點(diǎn) e 條邊的圖中，所有頂點(diǎn)的度數(shù)之和等于（ ）。 An B2n C e D2e 10.若一棵完全二叉樹中某結(jié)點(diǎn)無左孩子，則該結(jié)點(diǎn)一定是（ ）。 A度為的結(jié)點(diǎn) B度為的結(jié)點(diǎn) C葉子結(jié)點(diǎn) D分支結(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu)試題 B (2002) 一、單項(xiàng)選擇題，請?jiān)诿啃☆}的四

4、個(gè)備選答案中選擇一個(gè)，將其前面的字母填入（ ）中， 多選不得分。（每小題分，共分） 數(shù)據(jù)結(jié)構(gòu)研究（ ）。 A) 數(shù)據(jù)的邏輯結(jié)構(gòu)B) 數(shù)據(jù)的物理結(jié)構(gòu)C) 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu) D) 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及操作的實(shí)現(xiàn)。 帶頭結(jié)點(diǎn)的單循環(huán)鏈表head 為空的判定條件是（ ） A ）head=NULL B）head->next=NULL C）head->next=head D)head=head 在雙向鏈表存儲結(jié)構(gòu)中，在結(jié)點(diǎn) p 后插入一個(gè)新結(jié)點(diǎn) q，其操作為（ ）。 A）P->next=q; q->prior=p; p->next->prior=q; q-

5、>next=q; B）P->next=q; p->next->prior=q; q->prior=p;q->next=p->next; C）q->prior=p;q->next=p->next; p->next->prior=q; p->next=q; D）P->next=p->next; q->prior=p;p-next=q; q->next=p; 若以二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹 是( )。 A ） 二叉排序樹 B ） 哈夫曼樹 C ） 堆

6、D ）B樹 對二叉排序樹進(jìn)行( )遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的有序序列 A) 前序 B) 中序 C) 后序 D) 按層序 在樹中，若結(jié)點(diǎn)A 有四個(gè)兄弟，而且B 是A 的雙親，則B 的度為（ ）。 A） B） C） D） n 個(gè)頂點(diǎn)的連通圖至少有（A ）條邊 （A ） n-1 （B ） n （C） n+1 （D ）0 .設(shè)順序表為4, 6, 12, 38, 40, 67, 80用二分法查找 72，需要進(jìn)行的比較次數(shù)為（ ）。 A） B） C） D） 設(shè)數(shù)據(jù)結(jié)構(gòu)為（D，R），其中D=a,b,c,d,e,f,R=<d,b>,<b,a>,<b,c>,<

7、d,f>,<f,e>，該數(shù)據(jù) 結(jié)構(gòu)是（ ）。 A）線性表 B）有向圖 C）無向圖 D）樹 10假設(shè)以S 和O 分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列 可表示為僅由 S 和O 組成的序列，稱可以操作的序列為合法序列，否則為不合法序列。下 面的操作序列中，（ ）為不合法序列。 A）SOSSOSOO B）SOOSOSSO C）SSSOOSOO D）SOSOSO 數(shù)據(jù)結(jié)構(gòu)試題 A(計(jì)算機(jī) 031-4, 網(wǎng)絡(luò) 031-2, 軟件 031-2) 一、單項(xiàng)選擇題, 每小題后面有四個(gè)可供選擇的答案,請從中選擇一個(gè)正確的答案, 將其前 面的字母填寫在( )中。(共

8、20 分,每小題 2 分) 1. 用鏈表表示線性表的優(yōu)點(diǎn)是 ( )。 A.便于隨機(jī)存取 B.花費(fèi)的存儲空間比順序表少 C.便于插入與刪除 D.數(shù)據(jù)元素的物理順序與邏輯順序相同 2.有一個(gè)有序表為1,3,9,12,32,41,45,62,75,77,82,95,100, 如果采用二分查找法, 查 值為 82 的結(jié)點(diǎn)時(shí)，（ ）次比較后查找成功。 A. 1 B. 2 C. 4 D. 8 3.一棵二叉樹有 67 個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)的度或者是 0，或者是 2。這棵二叉樹中度為 2 的結(jié) 點(diǎn)有( )個(gè)。 A. 33 B.34 C.32 D.30 4.隊(duì)列與一般線性表的區(qū)別在于( )。 A. 數(shù)據(jù)元素的類型不

9、同 B. 插入或刪除操作的位置受限制 C. 數(shù)據(jù)元素的個(gè)數(shù)不同 D. 邏輯結(jié)構(gòu)不同 5.在一個(gè)單鏈表中，已知 q 所指節(jié)點(diǎn)是 p 所指節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，若在 q 和 p 之間插入 s 節(jié) 點(diǎn)，則執(zhí)行( )。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s;s->next=q; 6. 設(shè)進(jìn)棧的順序?yàn)?a b c d，則不可能得到的出棧序列是( )。 A.a b c d B.d c b a C.a c d

10、 b D.d a b c 7.將下列查找算法, 按查找速度從慢到快的順序排列, 正確的是（ ）。 A.順序 折半 哈希 分塊 B.順序 分塊 折半 哈希 C.分塊 折半 哈希 順序 D.順序 哈希 分塊 折半 8.具有 n 個(gè)頂點(diǎn)的有向完全圖有（ ）條弧。 A.n B.n*(n-1) C.n*(n+1) D.n*n 9.一棵深度為 5 的滿二叉樹中,結(jié)點(diǎn)的總數(shù)為 ( )。 A.31 B.32 C.33 D.16 10. 二維數(shù)組A910 采用行優(yōu)先的存儲方法，若每個(gè)元素占 3個(gè)存儲單元且A00 的地址為200，則A69 的地址為( )。 數(shù)據(jù)結(jié)構(gòu)試題 B(計(jì)算機(jī) 031-4 網(wǎng)絡(luò) 031-2

11、軟件 031-2) 一、單項(xiàng)選擇題, 每小題后面有四個(gè)可供選擇的答案,請從中選擇一個(gè)正確的答案, 將其前 面的字母填寫在( )中。(共 20 分,每小題 2 分) 在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中，若插入一個(gè)新結(jié)點(diǎn)，單鏈表仍然有序，則算法的 時(shí)間復(fù)雜度為（ ）。 O(1) O(n) O(n2) O(nlog2n) 下列數(shù)據(jù)結(jié)構(gòu)中，（ ）是線性結(jié)構(gòu)。 A樹 B 隊(duì)列 C圖 D A 和B 設(shè)單鏈表中指針p 指向結(jié)點(diǎn)a，若要刪除a 之后的結(jié)點(diǎn)（若存在），則需要修改指針的 操作為（ ）。 Ap->next=p->next->next p=p->next Cp= p->ne

12、xt->next p->next=p 若一棵二叉樹具有 10 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹的度為 0 的結(jié)點(diǎn)個(gè)數(shù)是( ) 9 B11 C12 D、不確定 下列四棵二叉樹中（ ）是一個(gè)堆。 若采用鄰接矩陣法存儲一個(gè)n 個(gè)頂點(diǎn)的無向圖，則該鄰接矩陣是一個(gè) ( ) 。 A 上三角矩陣 B 稀疏矩陣 C對角矩陣 D. 對稱矩陣 二叉樹第i(i>=1)層上至多有（ ）結(jié)點(diǎn)。 i i Ai i n 個(gè)頂點(diǎn)的連通圖至少有（ ）條邊。 An-1 Bn Cn+1 D 0 采用折半查找方法進(jìn)行查找，數(shù)據(jù)文件應(yīng)為（ ）。 有序表 順序存儲結(jié)構(gòu) B 有序表 鏈?zhǔn)酱鎯Y(jié)構(gòu) C 隨機(jī)表 順序存儲結(jié)構(gòu)

13、D 隨機(jī)表 鏈?zhǔn)酱鎯Y(jié)構(gòu) 10從一個(gè)具有n 個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x 的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平 均比較（ ）個(gè)結(jié)點(diǎn)。 n n/2 （n-1 ）/2 (n+1)/2 一、單項(xiàng)選擇題, 每小題后面有四個(gè)可供選擇的答案,請從中選擇一個(gè)正確的答案, 將其前面的字母填寫在( ) 中。(共 10 分,每小題 2 分) 1. 數(shù)據(jù)結(jié)構(gòu)中, ( )是線性結(jié)構(gòu)。 A. Graphics B. Tree C. Generalized list D. Queue 2. 樹型結(jié)構(gòu)中元素間存在( ）的關(guān)系。 A. 一對一 B. 多對多 C. 一對多 D. 隨機(jī) 3. ( )是下面的有向圖的拓?fù)溆行蛐蛄小?/p>

14、 A. A、C、B、D、E、F B. A、B、C、D、E、F C. A、B、D、C、E、F D. F、E、D、B、C、A 4. 在有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中結(jié)點(diǎn)總數(shù)為( ）。 A. 不確定 B. 2n-1 C. 2n D. 2n+1 5.稀疏矩陣一般的壓縮存儲方法有( )兩種。 A.二維數(shù)組和三維數(shù)組 B.三元組表和散列表 C.三元組表和十字鏈表 D.散列表和十字鏈表 二、問答題:（共分，每小題 5 分） 1. 什么是數(shù)據(jù)結(jié)構(gòu)? 數(shù)據(jù)結(jié)構(gòu)主要研究哪三個(gè)方面的問題? 2. 如果一棵樹有n 個(gè)度為 1 的結(jié)點(diǎn), 有n 個(gè)度為2 的結(jié)點(diǎn), 有n 個(gè)度為3 的結(jié)點(diǎn), 則該樹有多少個(gè)度為0 的結(jié)點(diǎn)?

15、 1 2 3寫出推導(dǎo)步驟。 三、應(yīng)用題:(共 40 分,每小題 10 分) 1. 有一組數(shù)據(jù)（20，69，15，32，8，6，88，65，12，19），請分別用 SHELL 排序法（第一趟排序的增量為， 第二趟增量為 3）和選擇排序法對其按由小到大的次序排序，寫出第一趟和第二趟的排序結(jié)果。 一、單項(xiàng)選擇題, 每小題后面有四個(gè)可供選擇的答案,請從中選擇一個(gè)正確的答案, 將其前面的字母填寫在( ) 中。(共 10 分,每小題 2 分) 1. 數(shù)據(jù)的( )結(jié)構(gòu),包括集合、線性表、樹和圖結(jié)構(gòu) 4 種基本類型。 A.存儲結(jié)構(gòu) B.邏輯結(jié)構(gòu) C.基本運(yùn)算 D.算法描述 2. 數(shù)據(jù)的存儲結(jié)構(gòu)包括順序;鏈接;

16、散列和( )4 種基本類型。 A. Vector B. Array C. Sets D. Index 3. 設(shè)棧的輸入序列是 1 2 3 4,則( )是不可能的出棧序列。 A.1 2 4 3 B. 2 1 3 4 C. 1 4 3 2 D. 4 3 1 2 4. 一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn),其中葉子結(jié)點(diǎn)的個(gè)數(shù)是( )。 A. 250 B. 500 C. 254 D.501 5.假定有 K 個(gè)關(guān)鍵字互為同義詞,若用線性探測法把這 K 個(gè)關(guān)鍵字存入散列表中,至少要進(jìn)行( )次探測。 A.K-1 次 B. K(K-1)/2 次 C.K+1 次 D.K(K+1)/2 次 二、問答題:（共分，每小

17、題 5 分） 1. 什么是棧，棧的特點(diǎn)有哪些？ 2. 如果二叉樹中度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 n2,則葉子結(jié)點(diǎn)的個(gè)數(shù) n0 為多少? 要求有計(jì)算步驟。 三、應(yīng)用題:(共 40 分,每小題 10 分) 1. 有一組數(shù)據(jù)（34，16，5，7，8，100，23，19，27，13），請分別用堆排序法和冒泡排序法對其按由大到小 的次序排序，寫出第一趟和第二趟的排序結(jié)果。 一單項(xiàng)選擇題（每題2分，共20分）1順序表是線性表的 （ ）鏈?zhǔn)酱鎯Y(jié)構(gòu) 順序存儲結(jié)構(gòu) 索引存儲結(jié)構(gòu) 散列存儲結(jié)構(gòu)2.對于順序表的優(yōu)缺點(diǎn)，以下說法錯誤的是 （ ） 無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲空間 可以方便地隨機(jī)存取表中的任一

18、結(jié)點(diǎn) 插人和刪除運(yùn)算較方便 由于順序表要求占用連續(xù)的空間，存儲分配只能預(yù)先進(jìn)行(靜態(tài)分配)3. 單鏈表中，增加頭結(jié)點(diǎn)的目的是為了 ( )使單鏈表至少有一個(gè)結(jié)點(diǎn) 標(biāo)示表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置方便運(yùn)算的實(shí)現(xiàn) 說明單鏈表是線性表的鏈?zhǔn)酱鎯?shí)現(xiàn)4.循環(huán)隊(duì)列的隊(duì)滿條件為（在犧牲一個(gè)存儲空間的情況下） ( )rear % maxsize =(front+1) % maxsize;(rear+1)% maxsize = front+1(rear+1)% maxsize = frontrear = front5.循環(huán)隊(duì)列的人隊(duì)操作應(yīng)為 ( )rear= rear+1 datarear=xdatarear=x re

19、ar= rear+1rear=( rear+1)% maxsize datarear=xdatarear=x rear=(rear+1)% maxsize6設(shè)有一順序棧已含3個(gè)元素，如下圖所示，元素a4正等待進(jìn)棧。那么下列4個(gè)序列中不可能出現(xiàn)的出棧序列是 （ ） 0 1 2 3 maxsize-1a1a2a3sq top a3,a1,a4,a2 a3,a2,a4,a1 a3,a4,a2,a1 a4,a3,a2,a17以下說法錯誤的是 ( ) 二叉樹可以是空集二叉樹的任一結(jié)點(diǎn)都有兩棵子樹二叉樹與樹具有相同的樹形結(jié)構(gòu)二叉樹中任一結(jié)點(diǎn)的兩棵子樹有次序之分8深度為5的二叉樹最多有( )個(gè)結(jié)點(diǎn)(設(shè)樹的層

20、數(shù)為6) 64 63 32 319將含有83個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號，根為1號，后面按從上到下、從左到右的順序?qū)Y(jié)點(diǎn)編號，那么編號為41的雙結(jié)點(diǎn)編號為 ( )圖142 40 21 2010在圖1的二叉樹中，（ ）不是完全二叉樹。二填空題（1-3題每空2分，4-6題每空1分，共20分）1下面程序段的時(shí)間復(fù)雜度T(n)= _。for(i=l;i<=n;i+)k+;for(j=1;j<=n;j+)l+=k;2以下運(yùn)算實(shí)現(xiàn)在順序棧上的進(jìn)棧，請?jiān)赺處用適當(dāng)?shù)囊蕴畛洌ù娣艞Ｔ氐臄?shù)組為ElmList）。template<class ELEM>void Push(ELEM

21、item) if(top >= maxsize-1cerr << “棧滿” << endl;return;_= item ; _； 3. 以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上的出隊(duì)列，請?jiān)赺處用適當(dāng)句子予以填充。（存放隊(duì)列元素的數(shù)組為ElmList）圖2template<class ELEM> ELEM Queue:DeQueue() if(curr_len = = _)cerr << “隊(duì)空” << endl;return； ELEM temp = _; _ _ ; return temp; 4.二叉樹第i(i>=0)層上至多有_個(gè)結(jié)

22、點(diǎn)。5.對任何二叉樹，若度為2的節(jié)點(diǎn)數(shù)為n2，則葉子數(shù)n0=_。6一棵樹的形狀如圖2所示，它的根結(jié)點(diǎn)是_，葉子結(jié)點(diǎn)是_ _，這棵樹的度是_，這棵樹的深度是_，結(jié)點(diǎn)F的孩子結(jié)點(diǎn)是_，結(jié)點(diǎn)G的父結(jié)點(diǎn)是_。三問答題（每題10分，共40分）1數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容有哪些，數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)有哪些，存儲結(jié)構(gòu)有哪些？2畫出圖3所示二叉樹的中序線索二叉鏈表存儲結(jié)構(gòu)示意圖。圖3AJIFCHGDB3已知一棵二叉樹的前根序列和中根序列分別為ABDGHECFIJ及GDHBEACIJF，請畫出這棵二叉樹。4給定權(quán)值7，18，3，32，5，26，12，8，構(gòu)造相應(yīng)的哈夫曼樹，并求這棵哈夫曼樹的帶權(quán)路徑長度WPL。四算法設(shè)計(jì)

23、題（每題10分，共20分）1 設(shè)A=（a1,a2,a3,.an）和B=(b1,b2,. .,bm)是兩個(gè)線性表（假定所含數(shù)據(jù)元素均為整數(shù)）。若n=m且ai=bi(i=1,. .,n),則稱A=B;若ai=bi(i=1,. .,j)且aj+1<bj+1（j<n<=m）, 則稱A<B;在其他情況下均稱A>B。試編寫一個(gè)比較A和B的算法，當(dāng)A<B,A=B或A>B是分別輸出-1，0或者1。2假設(shè)在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)*s的前趨結(jié)點(diǎn)。五選作題（任選其一，共10分）1設(shè)有線性表A=(a1,

24、a2,. .,am)和B=(b1,b2,. .,bn).試寫合并A、B為線性表C的算法，使得：C=假設(shè)A、B均以單鏈表為存儲結(jié)構(gòu)。2有一二叉鏈表，按后根遍歷時(shí)輸出的結(jié)點(diǎn)順序?yàn)閍1, a2,an-1, an。試編寫一算法，要求輸出后根序列的逆序an,an-1 ，a2 , a1 。一 單項(xiàng)選擇題（每題2分，共20分）1.以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)A.圖 B.字符串 C.隊(duì) D.棧2.隊(duì)列的特點(diǎn)是（ ）。 A.先進(jìn)先出 B. 后進(jìn)先出 C.沒有約束 D. 先進(jìn)后出 3.有個(gè)元素6,5,4,3,2,1順序進(jìn)棧，問下列哪一個(gè)是不合法的出棧序列：A.5,4,3,6,1,2  

25、;   B.4,5,3,1,2,6     C.3,4,6,5,2,1     D.2,3,4,1,5,64.設(shè)順序表的長為n,則其每個(gè)元素(查找概率均等)的平均查找長度是 （ ）A.n B. (n-1)/2 C. n/2 D. (n+1)/25.下面關(guān)于串的敘述中，哪一個(gè)是不正確的（ ）A.串是字符的有限序列 B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算 D.串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?某二叉樹結(jié)點(diǎn)的中序序列為A、B、C、D、E、F、G，后序序列為B、D、C、A、F、G

26、、E，則其左子樹中結(jié)點(diǎn)數(shù)目為（ ）A.3 B.2 C.4 D.57.如果一個(gè)圖有e條邊，則圖中所有頂點(diǎn)的度的和是（ ）。A.e B. e/2 C. 2e D. e-18.下面關(guān)于圖的存儲的敘述中正確的是（ ）A.鄰接矩陣占用的存儲空間只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)；B.鄰接矩陣占用的存儲空間只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)；C.鄰接表占用的存儲空間只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)；D.鄰接表占用的存儲空間只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)。9.下面的排序算法中，時(shí)間復(fù)雜度不是O(n2）的是（ ）。 A.直接插入排序 B.冒泡排序 C.二路歸并排序 D.直接選擇排序10.已知廣義表LS=

27、(a,(b,c),(d,e,f)，該廣義表的長度為（ ）。 A.3 B.6 C.1 D.2二問答題（每題10分，共40分）1. 畫出與下圖所示的二叉樹相對應(yīng)的森林，并寫出該森林的先序和后序遍歷序列。ABCDEFGH2. 對于下面的圖，請完成下列任務(wù):(1)畫出它的鄰接表 (2)寫出從頂點(diǎn)A出發(fā)的深度優(yōu)先搜索序列 (3)求從A到其他頂點(diǎn)的最小路徑。391081261519 6ABDFEC3.判別序列（12，70，33，65，24，56，48，92，86，33）是否為小頂堆，如果不是，則把它調(diào)整為小頂堆， 寫出小頂堆所對應(yīng)的序列。4. 已知散列函數(shù)為H(K)=K mod 13,關(guān)鍵碼序列為25，3

28、7，52，43，84，99，120，15，26，11，70，82，1，采用拉鏈法處理沖突，畫出構(gòu)造的開散列表，并計(jì)算查找成功的平均查找長度。三算法閱讀題（要求：寫出算法功能，并舉例說明）（每題5分，共15分）1. struct Node char data; Node *llink; Node *rlink; ;void function1 (Node* root) f(root!=NULL) function1(root->llink); cout << root->data << “ “; function1(root->rlink); 2. vo

29、id function2(char A, int n)char x;int s, h, m;for(int i=1;i<n;i+)x = Ai; s = 0; h = i - 1;while(s<=h)m = (s+h)/2;if(x < Am) h = m- 1;else s = m + 1;for(int j=i-1;j>=s;j-) Aj+1 = Aj;As = x;3. int function3( char *d, char *s)int i =0; while (si != '0' && di != '0' )

30、 if (di > si) return 1; else if (di < si) return -1; i +; if( di = ='0' && si != '0') return -1; else if (si = = '0'&& di != '0') return 1; return 0; 四算法設(shè)計(jì)題（第一題10分，第二題15分）1 已知一個(gè)整數(shù)順序表L，要求將其拆分為一個(gè)正整數(shù)順序表L1和一個(gè)負(fù)整數(shù)順序表L2。2無向圖采用鄰接表方式存儲，要求編寫按廣度優(yōu)先搜索策略實(shí)現(xiàn)對圖的遍

31、歷算法。一、單選題, 從可供選擇的4個(gè)答案中, 選擇一個(gè)正確的答案, 將其前面的字母填寫在( )中,共40分,每小題4分。1.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行( )。A.s->next=p->next;  p->next=s;   B.q->next=s;   s->next=p; C.p->next=s->next;  s->next=p;   D.p->next=s;   s->

32、next=q;2.帶頭結(jié)點(diǎn)的單鏈表為空的判定條件是( )。A.head= =NULLB.head->next= =NULLC.head->next= =head  D.head!=NULL3. 若一棵完全二叉樹中某結(jié)點(diǎn)無左孩子，則該結(jié)點(diǎn)一定是（）。A度為的結(jié)點(diǎn) B度為的結(jié)點(diǎn) C葉子結(jié)點(diǎn) D分支結(jié)點(diǎn)4.設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是( )。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孫5在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為： （ ）。A. O(0) B. O(1) C. O(n) D. O(n2)6一個(gè)棧的入棧序

33、列是a, b, c, d, e，則棧的不可能的出棧序列是（ ）。A. edcba B. cdeba C.debca D.abcde7前序遍歷和中序遍歷結(jié)果相同的二叉樹是（ ）。A. 根結(jié)點(diǎn)無左孩子的二叉樹 B. 根結(jié)點(diǎn)無右孩子的二叉樹C. 所有結(jié)點(diǎn)只有左子樹的二叉樹 D. 所有結(jié)點(diǎn)只有右子樹的二叉樹8.用順序存儲的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組A1 An中，結(jié)點(diǎn)Ai若有左子樹，則左子樹的根結(jié)點(diǎn)是（ ）。 A. A2i-1 B.A2i+1 C.Ai/2 D.A2i9.對任何一棵四叉樹T，如果其終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，度為3的結(jié)點(diǎn)個(gè)數(shù)為n3,度為4的結(jié)點(diǎn)個(gè)數(shù)為n4

34、,則（ ）。 A.n0=n2+n3+n4+1 B.n0=n2+2n3+3n4+1 C.n0=n1+n2+2n3+3n4+1 D.沒有規(guī)律10.算法指的是（ ）。A. 對特定問題求解步驟的一種描述 B. 計(jì)算機(jī)程序 C. 解決問題的計(jì)算方法 D. 數(shù)據(jù)處理二、填空題, 請將答案填寫在題目的( )內(nèi)。（共24分，每小題6分）1在一個(gè)長度為n的順序表的第i（1in+1）個(gè)元素之前插入一個(gè)元素，需向后移動（ ）個(gè)元素，刪除第i（1in）個(gè)元素時(shí)，需向前移動（ ）個(gè)元素。2. 權(quán)值為2, 4, 1,7, 3，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，其帶權(quán)路徑長度為（ ）。3. 已知一棵二叉樹的前序遍歷序列為ABC

35、DEFGH，中序遍歷序列為CDBAFEHG，該二叉樹的后序遍歷序列是4. 已知二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu) lchild data rchild其中，data：數(shù)據(jù)域，存儲元素的值lchild：左指針域，存儲左孩子指針rchild：右指針域，存儲右孩子指針請將Struct BiNode的定義填寫完整。template <class T>struct BiNode ; ; ; ;三、閱讀下列算法, 將合適的語句填寫在_處, 使算法完善。(共24分,每小題6分)1.在線性表中查找元素x, 若找到x, 返回第一個(gè)找到的x的序號, 若找不到,返回0const int MaxSize =100; te

36、mplate  < class T >/模板類 SeqList class SeqListpublic private:       T dataMaxSize; / 存放數(shù)據(jù)元素的數(shù)組       int length; / 線性表的長度 ; template <class T> SeqList<T>:Locate(T x)/在線性表中查找元素x，返回其在表中的序號 for (int i=0; i<length; i+) if return

37、i+1; /下標(biāo)為i的元素等于x，返回其序號i+1 ; /退出循環(huán)，說明查找失敗2. 算法的功能是將一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換為二至九進(jìn)制之間的任一進(jìn)制數(shù)(用r表示)輸出。void Decimaltor(int num, int r) top=-1;/采用順序棧, 并假設(shè)棧不會溢出 While (num!=0) ; S+top=k; ;While (top!=-1) ;3. 循環(huán)順序隊(duì)列入隊(duì)操作const int QueueSize=100;template <class T> class CirQueuepublic:void EnQueue(T x); private: T dataQ

38、ueueSize; /存放隊(duì)列元素的數(shù)組 int front, rear; ; template <class T> void CirQueue<T>:EnQueue(T x) /元素x入隊(duì)列 if throw "隊(duì)列已滿" ; ; /在隊(duì)尾處插入元素4. 按中序遍歷次序輸出二叉樹中的葉子結(jié)點(diǎn)的值template <class T>struct BiNode /二叉樹的結(jié)點(diǎn)結(jié)構(gòu) T data; BiNode<T> *lchild, *rchild;template <class T>class BiTreepublic: BiTree( ); /構(gòu)造函數(shù)，初始化一棵二叉樹，其前序序列由鍵盤輸入 BiTree(void); /析構(gòu)函數(shù)，釋放二叉鏈表中各結(jié)點(diǎn)的存儲空間private: BiNode<T> *root; /指向根結(jié)點(diǎn)的頭指針 ;template<class T>void BiTree<T>:leaf(BiNode<T> *root) if(root=NULL) return;else ; if ;