一、填空題：（每小題2分，共10分）設(shè)有數(shù)據(jù)結(jié)構(gòu)（D,R）,其中D是數(shù)據(jù)元素的有限集，R是的有限集。深度為k的二叉樹其結(jié)點(diǎn)數(shù)至多有個(gè)。棧是一種特殊的線性表，它允許在表的一端進(jìn)行 操作。通常象交通、道路問題的數(shù)學(xué)模型是一種稱為 的數(shù)據(jù)結(jié)構(gòu)。哈希表是一種查找表，可以根據(jù)哈希函數(shù)直接獲得 。二、單項(xiàng)選擇題：（每小題2分，共10分）對(duì)于下列各題，在備選答案中選出一個(gè)正確的，并將其編號(hào)填在“ ”位置上。若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)元素的值，則采用存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表下列排序算法中，算法在進(jìn)行一趟相應(yīng)的排序處理結(jié)束后不一定能選出一個(gè)元素放到其最終位置上。A.直選擇排序B.冒泡排序C.歸并排序D.堆排序隊(duì)列的操作原則是。A.先進(jìn)后出B.先進(jìn)先出C.只能進(jìn)行插入D.只能進(jìn)行刪除在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，非空的鏈域個(gè)數(shù)為。n-1B.nC.n+1D.不確定對(duì)具有n個(gè)元素的有序查找表采用折半查找算法查找一個(gè)鍵值，其最壞比較次數(shù)的數(shù)量級(jí)為。A.O（log2n）B.O（n）C.O（nlog2n）D.O（n2）三、判斷題：（每小題2分，共10分）判斷下列各題是否正確，若正確，在題后的括號(hào)內(nèi)填“T”，否則填“F”。在棧為空的情況下不能作出棧處理，否則，將產(chǎn)生下溢出。（）如果有向圖G=（V,E）的拓?fù)湫蛄形ㄒ?，則圖中必定僅有一個(gè)頂點(diǎn)的入度為0、一個(gè)頂點(diǎn)的出度為0。（ ）在大根堆中，必定滿足每個(gè)結(jié)點(diǎn)的鍵值大于其左右子樹中所有結(jié)點(diǎn)的鍵值。（）在采用線性探測(cè)法處理沖突的散列表中所有同義詞在表中相鄰。（）在索引順序表中，對(duì)索引表既可采用順序查找，也可采用二分查找。（）四、 解答下列各題：（每題10分，共40分）已知線性表L采用帶頭結(jié)點(diǎn)的的單向循環(huán)鏈表表示，試給出它的存儲(chǔ)結(jié)構(gòu)類型描述及相應(yīng)的示意圖。。已知一棵二叉樹的先序、中序和后序序列如下所示，請(qǐng)?zhí)顚懜餍蛄兄锌崭裉幍慕Y(jié)點(diǎn)，并畫出該二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)示意圖。先序序列是：_B_F_ICEH_G；中序序列是：D_KFIA_EJC_；后序序列是：_K_FBHJ_G_A已知數(shù)據(jù)表為（48，70，33，65，24，56，12，92，86，22），a）寫出采用快速排序算法進(jìn)行排序時(shí)第一趟快速劃分的詳細(xì)過程及結(jié)果；b）寫出按基數(shù)排序思想對(duì)最低位進(jìn)行一次分配和收集的結(jié)果。對(duì)圖1所示的帶權(quán)無向圖，寫出它的鄰接矩陣和深度優(yōu)先搜索序列，并按克魯斯卡算法求其最小生成樹（寫出求解的詳細(xì)過程示意圖）。圖1帶權(quán)無向圖五、 算法設(shè)計(jì)題：（前兩題必做，每題15分，共30分；第三題為附加題，選做，10分）已知隊(duì)列Q以循環(huán)隊(duì)列存儲(chǔ)。寫出Q的存儲(chǔ)結(jié)構(gòu)類型描述，并試編寫算法實(shí)現(xiàn)將元素x插入隊(duì)列Q的入隊(duì)操作EnQueue（Q,x）和從隊(duì)列Q中獲取隊(duì)首元素的函數(shù)GetTop（Q）。假設(shè)線性表L=（al,a2,......,an）用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)表示，試編寫算法對(duì)其實(shí)現(xiàn)就地逆置，即利用原鏈表中每一個(gè)結(jié)點(diǎn)存儲(chǔ)空間，使得元素的邏輯次序改變?yōu)椋╝n,……,a2,al）。設(shè)非空二叉樹T采用中序線索二叉鏈表表示，寫出T的存儲(chǔ)結(jié)構(gòu)類型描述。試編寫算法InOrderTraverse（T）實(shí)現(xiàn)對(duì)二叉樹T的中序遍歷。專升本《數(shù)據(jù)結(jié)構(gòu)》試卷2一、單項(xiàng)選擇題：（每小題2分，共10分）折半查找法要求查找表中各元素的鍵值必須是。A.遞增或遞減B.遞增C.遞減D.無序若對(duì)某線性表最常進(jìn)行的操作是在最后一個(gè)元素之后插入和刪除第一個(gè)元素，則采用存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.雙鏈表C.僅有頭指針的單循環(huán)鏈表D.僅有尾指針的單循環(huán)鏈表有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為一(假設(shè)根結(jié)點(diǎn)的層次為1)。A.8B.7C.6D.5對(duì)于鍵值序列(2,33,21,18,65,38,7,49,24,86),用篩選法建堆，必須從鍵值為—的結(jié)點(diǎn)開始。A.86B.2C.65D.38設(shè)圖G用鄰接表存儲(chǔ),則求每個(gè)頂點(diǎn)入度的算法時(shí)間復(fù)雜度為。A.O(n)B.O(n+e)C.O(n*n)D.O(n*e)二、判斷題：(每小題2分,共10分)在隊(duì)滿情況下不能作入隊(duì)處理,否則,將產(chǎn)生“上溢”。()基于插入思想的排序算法都是穩(wěn)定的。()一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)不一定相等。()若一棵二叉樹的任一非葉子結(jié)點(diǎn)度為2,則該二叉樹為滿二叉樹。()廣義表是線性表的推廣,因此也可以采用順序方式進(jìn)行存儲(chǔ)。()三、填空題：(每小題2分,共10分)TOC\o"1-5"\h\z在單鏈表中,刪除指針P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是： 。有向圖G用鄰接矩陣A[1..n,1..n]存儲(chǔ)表示,其第i行的所有元素之和等于頂點(diǎn)i的 ?；鶖?shù)排序算法的時(shí)間復(fù)雜度為 。平衡二叉樹中每個(gè)結(jié)點(diǎn)的平衡因子定義為 。利用直接插入排序算法對(duì)有n個(gè)元素的數(shù)據(jù)表進(jìn)行排序,在最壞情況下,元素的移動(dòng)次數(shù)為。四、 解答下列各題：(每小題10分,共40分)寫出采用順序方式存儲(chǔ)的棧的類型描述及相應(yīng)的入棧、出棧操作的示意圖。已知數(shù)據(jù)表為(60,20,31,5,44,55,61,30,80,150,4,29),寫出采用希爾排序算法進(jìn)行排序的詳細(xì)過程和結(jié)果(假設(shè)增量序列dlta[]={6,3,1})。已知圖G的鄰接表存儲(chǔ)結(jié)構(gòu)示意圖如下所示,畫出它的邏輯關(guān)系示意圖,以及按深度優(yōu)先搜索和廣度優(yōu)先搜索進(jìn)行遍歷所得到的頂點(diǎn)序列。設(shè)散列函數(shù)為H(K)=Kmod5,散列表的地址空間為0..6,初始時(shí)散列表為空,用線性探測(cè)法解決沖突,請(qǐng)寫出依次插入23,14,9,30,12,18時(shí)散列地址的計(jì)算過程及結(jié)果,以及最后得到的散列表。五、 算法設(shè)計(jì)題：(前兩題必做,每題15分,共30分；第三題為附加題,選做,10分)設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C,其中：B表中的結(jié)點(diǎn)為A表中元素的順序號(hào)為奇數(shù)的結(jié)點(diǎn),而C表中的結(jié)點(diǎn)為A表中元素的順序號(hào)為偶數(shù)的結(jié)點(diǎn)。(要求利用原表結(jié)點(diǎn)。)已知S為順序棧。寫出S的存儲(chǔ)結(jié)構(gòu)類型描述。試編寫算法實(shí)現(xiàn)將元素x插入棧S的入棧操作Push(S,x)和刪除棧頂元素的出棧操作Pop(S)。已知一棵完全二叉樹存于順序表sa中,sa.elem[1..sa.last]包含各結(jié)點(diǎn)值。試編寫算法根據(jù)此順序存儲(chǔ)結(jié)構(gòu)建立該二叉樹的二叉鏈表T。(專升本)《數(shù)據(jù)結(jié)構(gòu)》試題(模A)2004-5-1一、單項(xiàng)選擇題數(shù)據(jù)的不可分割的基本單位是 。A.元素 B.結(jié)點(diǎn) C.數(shù)據(jù)類型 D.數(shù)據(jù)項(xiàng)2?下列算法suanfa2的時(shí)間復(fù)雜度為—。intsuanfa2(intn){intt=1；while(tO)個(gè)結(jié)點(diǎn)的完全二叉樹的深度是 。A.elog2(n)u B.elog2(n)+1uC.?log2(n+1)? D.?log2(n)+1?7.與中綴表達(dá)式a+b*c-d等價(jià)的前綴表達(dá)式是 。

A.+a-*bcd*+-abcd-+a*bcdabcd+*-A.+a-*bcd*+-abcd-+a*bcdabcd+*-8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次與表中元素 進(jìn)行比較,。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,37對(duì)長(zhǎng)度為10的表作選擇(簡(jiǎn)單選擇)排序,共需比較 次關(guān)鍵字。A.45B.90C.55D.11010?對(duì)n個(gè)元素的表作快速排序，在最壞情況下,算法的時(shí)間復(fù)雜度為—。A.O(log2n)B.O(nlog2n)C.O(n2)D.O(2n)11.對(duì)長(zhǎng)度為10的表作2_路歸并排序,共需移動(dòng) 次(個(gè))記錄。A.20B.45C.40D.30二、填空(每空1分,共11分)TOC\o"1-5"\h\z一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映象)稱為 。線性表中 稱為表的長(zhǎng)度。棧中元素的進(jìn)出原則為 。4?設(shè)數(shù)組A[1..10,1..8]的基地址為2000，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素A[4,5]的存儲(chǔ)地址為 ;若以列序?yàn)橹餍蝽樞虼鎯?chǔ),則元素A[4,5]的存儲(chǔ)地址為 。一棵深度為6的滿二叉樹有 個(gè)非終端結(jié)點(diǎn)。若一棵二叉樹中有8個(gè)度為2的結(jié)點(diǎn),則它有 個(gè)葉子。順序查找n個(gè)元素的順序表,當(dāng)使用監(jiān)視哨時(shí),若查找成功,比較關(guān)鍵字的次數(shù)至少為 次,最多為 次;若查找失敗,比較關(guān)鍵字的次數(shù)為 次。對(duì)長(zhǎng)度為400的表采用分塊(區(qū))查找,最理想的塊長(zhǎng)為 。三、 回答下列問題(每小題5分,共10分)線性表的存儲(chǔ)結(jié)構(gòu),在什么情況下采用順序結(jié)構(gòu)?為什么?二叉樹有哪幾種基本形態(tài)?畫圖說明之。四、 試畫出下列存儲(chǔ)結(jié)構(gòu)圖(每小題4分,共20分)1?數(shù)組A[1..2,0..2]的以列序?yàn)橹餍虻捻樞虼鎯?chǔ)結(jié)構(gòu)。依次將元素A,C,D,B插入一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出所有插入完成之后的鏈?zhǔn)綏?。二叉樹的順序存?chǔ)結(jié)構(gòu):圖的鄰接矩陣:有向圖的逆鄰接表:五、 求解下列問題(每小題6分,共24分)給定30個(gè)字符組成的電文:DDDDDAAABEEAAFCDAACABBCCCBAADD試為字符A、B、C、D、E、F設(shè)計(jì)哈夫曼(Huffman)編碼。畫出相應(yīng)的哈夫曼樹；(2)分別列出A、B、C、D、E、F的哈夫曼碼；(3)計(jì)算該樹的帶權(quán)路徑長(zhǎng)度WPL。試按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序,將所有元素插入一棵初始為空的二叉排序樹中,使之仍是一棵二叉排序樹。試畫出插入完成之后的二叉排序樹；若查找元素17,它將依次與二叉排序樹中哪些元素比較大小?假設(shè)每個(gè)元素的查找概率相等,試計(jì)算該樹的平均查找長(zhǎng)度ASL。對(duì)該樹進(jìn)行中序遍歷,試寫出中序遍歷序列。試將森林F={T1,T2,T3,T4}轉(zhuǎn)換為一棵二叉樹。T1 T2T3 T4找出下面網(wǎng)絡(luò)的最小生成樹。六、 填空題(在算法中有下劃線 的位置填空,使之成為完整、正確的算法)算法說明：已知r[1..n]是n個(gè)記錄的遞增有序表，用折半查找法查找關(guān)鍵字為k的記錄，若查找失敗，則輸出”Failure”，返回零；否則輸出”Success”，并返回該記錄的序號(hào)值。(共8分)算法(C函數(shù))：intbin_search(structarecordr[]，intn，k：keytype)/*r[l..n]為n個(gè)記錄的遞增有序表,k為關(guān)鍵字*/{intlow,mid,hig；low=l；hig=n； /*各變量初始化*/while( ){mid= ；if(k七、算法設(shè)計(jì)(算法中必須有注釋，每小題8分，共16分)1?設(shè)n個(gè)元素的線性表順序存儲(chǔ)在一維數(shù)組st[1..maxlen]的前n個(gè)位置上，試將新元素e插入表中第i-1個(gè)和第i個(gè)元素之間，寫出算法。2?設(shè)Head為帶表頭結(jié)點(diǎn)的單鏈表的頭指針，試寫出算法:若為非空表，則輸出首結(jié)點(diǎn)和尾結(jié)點(diǎn)的值(data值)；否則輸出:”Emptylist!”。(專升本)《數(shù)據(jù)結(jié)構(gòu)》試題(模B)2004-5-1一、 單項(xiàng)選擇題TOC\o"1-5"\h\z數(shù)據(jù)的基本單位是 。A.結(jié)點(diǎn) B.數(shù)據(jù)元素 C.數(shù)據(jù)類型 D.數(shù)據(jù)項(xiàng)下列算法suanfa1中語句"x=x*2；"的執(zhí)行次數(shù)是 。voidsuanfa1(intn){inti，j，x=1；for(i=1；i0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度是 。A.elog2(n)+1uB.elog2(n)-1uC.?log2(n)-1? D.?log2(n)+1?與中綴表達(dá)式a-b/c+d等價(jià)的前綴表達(dá)式是 。A.-a+/bcdB./-+bcdC.+-/bcd D.abcd-/+對(duì)有3600個(gè)記錄的索引順序表(分塊表)進(jìn)行查找，最理想的塊長(zhǎng)為 。A.1800 B.60C.1200D.elog23600u對(duì)n個(gè)元素的表作堆排序，在最壞情況下,算法的時(shí)間復(fù)雜度為—。A.O(log2n)B.O(nlog2n)C.O(n2)D.O(2n)二、 填空題(每空1分，共11分)一個(gè)算法具有5個(gè)特性: 、 、 、有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。2?設(shè)長(zhǎng)度為n的線性表順序存貯，若在它的第i-1和第i個(gè)元素之間插入一個(gè)元素，共需移動(dòng) 個(gè)元素(1三、 回答下列問題(每小題5分，共10分)線性表的存儲(chǔ)結(jié)構(gòu)，在什么情況下采用鏈接表(如:單鏈表)結(jié)構(gòu)?為什么?空格串與空串有區(qū)別?舉例說明之。四、 試畫出下列存儲(chǔ)結(jié)構(gòu)圖(每小題5分，共20分)試畫出下列稀疏矩陣以列序?yàn)橹餍虻娜M表。試畫出下列二叉樹的中序線索二叉樹存儲(chǔ)結(jié)構(gòu)圖。試用孩子兄弟(左孩子右兄弟)表示法畫出下列樹的存儲(chǔ)結(jié)構(gòu)圖。試畫出下列有向網(wǎng)的逆鄰接表。五、 求解下列問題(每小題6分，共24分)已知二叉樹的前序遍歷序列和中序遍歷序列分別是：B，A，C，D，F(xiàn)，E，G和D，C，A，F(xiàn)，GE，B，試畫出該二叉樹。試按表(25，15，19，24，20，5，16，45，40，38)中元素的排列次序，將所有元素插入一棵初始為空的二叉排序樹中，使之仍是一棵二叉排序樹。(1)試畫出插入完成之后的二叉排序樹；(2)若查找元素17，它將依次與二叉排序樹中哪些元素比較大小?(3)假設(shè)每個(gè)元素的查找概率相等，試計(jì)算該樹的平均查找長(zhǎng)度ASL；(4)對(duì)該樹進(jìn)行中序遍歷，試寫出中序遍歷序列。3?試用權(quán)集合{4,6,5，12,2，1，13}，構(gòu)造赫夫曼(Huffman)樹，(1)列出構(gòu)造過程，(2)分別計(jì)算該赫夫曼樹的路徑長(zhǎng)度和帶權(quán)路徑長(zhǎng)度。4.找出下面網(wǎng)絡(luò)的最小生成樹:六、 執(zhí)行下面的C程序，指出輸出結(jié)果。(8分)structnode{chardata；structnode*next；}；voidlink_list(structnode*p){while(p!=NULL){printf("%c",p->data)；p=p->next；}printf("\n")；}main(){charch；structnode*q,*p,*f,*head=NULL；for(ch='A'；chdata=ch；p->next=head；head=p；link_list(p)；}p=head；head=NULL；while(p!=NULL){q=p；p=p->next；q->next=head；head=q；f=head；while(f->next!=NULL){link_list(head)；f=f->next->next；}}}七、算法設(shè)計(jì)(算法中必須有注釋,每小題8分,共16分)設(shè)n個(gè)元素的線性表順序存儲(chǔ)在一維數(shù)組st[l..maxlen]的前n個(gè)位置上，試寫出算法:刪除表中第i(1<i<n)個(gè)元素。2?設(shè)Head為帶表頭結(jié)點(diǎn)的單鏈表的頭指針，試寫出算法:若為非空表，則輸出:最大結(jié)點(diǎn)和最小結(jié)點(diǎn)的值(data值)；否則,輸出:“Emptylist”。網(wǎng)計(jì)(專升本)《數(shù)據(jù)結(jié)構(gòu)》試題(模C)2004-5-1一、選擇題由 組成的集合是一個(gè)數(shù)據(jù)對(duì)象。A.不同類型的數(shù)據(jù)項(xiàng) B.不同類型的數(shù)據(jù)元素 C.相同類型的數(shù)據(jù)項(xiàng) D.相同類型的數(shù)據(jù)元素 是線性表。A.(孔子,諸葛亮，曹雪芹) B.{A,B,C,D}C.{10,11,12,13,14} D.(1,2,3,...) 是表示線性數(shù)據(jù)結(jié)構(gòu)的。A.循環(huán)鏈表B.鄰接多重表 C.孩子鏈表 D.單鏈表將線性表的數(shù)據(jù)元素以 結(jié)構(gòu)存放,查找一個(gè)數(shù)據(jù)元素所需的時(shí)間不依賴于表的長(zhǎng)度。A.循環(huán)雙鏈表 B.哈希(Hash)表 C.一維數(shù)組 D.單鏈表設(shè)數(shù)組A[1..8,1..10]的基地址為4000,每個(gè)元素占2個(gè)存儲(chǔ)單元,若以列序?yàn)橹餍蝽樞虼鎯?chǔ),則元素A[4,7]的存儲(chǔ)地址是 。(假定無第0行第0列元素)A.4072 B.4104 C.4102 D.40746?設(shè)依次進(jìn)入一個(gè)棧的元素序列為c,a,b,d，不可得到出棧的元素序列有 。A.a.b,c,dB.a,d,c,bC.b,a,d,cD.c,d,a,b___又是一棵滿二叉樹。A.二叉排序樹 B.深度為5有31個(gè)結(jié)點(diǎn)的二叉樹C.有15個(gè)結(jié)點(diǎn)的完全二叉樹 D.哈夫曼(Huffman)樹深度為k的滿二叉樹有 個(gè)分枝結(jié)點(diǎn)。A.2k-1 B.2k-1-1 C.2k+1 D.2k-1+19?具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。A.elog2(n)u B.?log2(n)?+1C.elog2(n+1)uD.?log2(n+1)?折半查找20個(gè)記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù) 。A.最多為6 B.最多為5 C.最少為3D.最少為4折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次與表中元素 進(jìn)行比較。A.25,40,60B.25,40C.20,36,40,60D.20,36,40TOC\o"1-5"\h\z查找哈希(Hash)表,解決沖突的的方法有 。A.除留余數(shù)法 B.線性探測(cè)再散列法C.直接地址法 D.鏈地址法對(duì)有10個(gè)記錄的表作簡(jiǎn)單選擇排序,需要比較___次關(guān)鍵字。A.100 B.45 C.50 D.90對(duì)有n個(gè)記錄的表作快速排序,在最壞情況下,算法的時(shí)間復(fù)雜度是 。A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)一個(gè)排序算法時(shí)間復(fù)雜度的大小 有關(guān)。A.與所需比較關(guān)鍵字的次數(shù) B.與該算法的穩(wěn)定性 C.不與所需移動(dòng)記錄的數(shù)目 D.與所需輔助存儲(chǔ)空間的大小二、 畫圖題(每小題4分,共20分)依次輸入元素X,Y,Z,插入到一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出空的鏈?zhǔn)綏：兔坎迦胍粋€(gè)元素之后的鏈?zhǔn)綏Ｊ疽鈭D。試用雙親表示法畫出下列樹T的存儲(chǔ)結(jié)構(gòu)圖。3?試畫出有3行4列元素的二維數(shù)組B的以列序?yàn)橹餍虻捻樞虼鎯?chǔ)結(jié)構(gòu)圖。試畫出下列圖的鄰接表。已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別是：I,A,B,E,F,G,C,H,D和A,E,F,B,I,G,H,C,D試畫出該二叉樹。三、 求解問題(每小題7分,共28分)用算符優(yōu)先法求下列算術(shù)表達(dá)式的值,試簡(jiǎn)要說明求值過程,畫出*作數(shù)棧和運(yùn)算符棧的主要變化過程。12+20/(10-2*3)給定電文(文本):FFAAABBBAAABBCCCDEGGG試為字符A、B、C、D、E、F、G設(shè)計(jì)哈夫曼(Huffman)編碼:(1)畫出相應(yīng)的哈夫曼樹，列出各字符的哈夫曼碼；(2)計(jì)算該哈夫曼樹的帶權(quán)路徑長(zhǎng)度。3?假定后序遍歷二叉樹的結(jié)果是A,C,B,(1)試畫出所有可得到這一結(jié)果的不同形態(tài)的二叉樹；(2)分別寫出這些二叉樹的中序遍歷序列。4.對(duì)20個(gè)記錄的表作折半查找,(1)畫出描述折半查找過程的判定樹；(2)若每個(gè)記錄的查找概率相等,試計(jì)算查找成功時(shí)的平均查找長(zhǎng)度。四、 分析算法回答問題(每小題10,共20分)設(shè)二叉樹T的存儲(chǔ)結(jié)構(gòu)為二叉鏈表,結(jié)點(diǎn)結(jié)構(gòu)定義如下：structnode{chardata； //data為字符型structnode*lchild,*rchild； //指向左右孩子的指針}；設(shè)root為二叉樹T的根指針,(1)對(duì)二叉樹T執(zhí)行算法traversal(root),試指出其輸出結(jié)果；(2)假定二叉樹T共有n個(gè)結(jié)點(diǎn)，試分析算法traversal(root)的時(shí)間復(fù)雜度。算法(C函數(shù))如下：voidtraversal(structnode*root){if(root){printf("%c",root->data)；traversal(root->lchild)；printf("%c",root->data)；traversal(root->rchild)；}}五、 設(shè)計(jì)算法:輸入一個(gè)m*n的整數(shù)矩陣，如果各個(gè)元素互不相同，則輸出信息"沒有重碼!"；否則輸出信息"有重碼:"和重碼值(相同的元素)。1?用C語言寫出所用數(shù)據(jù)結(jié)構(gòu)的類型定義和算法；分析算法的時(shí)間復(fù)雜度。一、判斷題(每小題1分，共15分)1.非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。()數(shù)組是一種沒有插入與刪除*作的線性結(jié)構(gòu)。()稀疏矩陣中值為0的元素分布有規(guī)律，因此可以采用三元組方法進(jìn)行壓縮存儲(chǔ)。()空串與由空格組成的串沒有區(qū)別。()將T在S中首次出現(xiàn)的位置作為T在S中的位置的*作稱為串的模式匹配。()6.深度為h的非空二叉樹的第i層最多有2h-1個(gè)結(jié)點(diǎn)。()7.完全二叉樹就是滿二叉樹。()8.已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹。()非空二叉排序樹的任意一棵子樹也是二叉排序樹。()10.有向圖是一種非線性結(jié)構(gòu)。()帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。()12.AOE網(wǎng)是一種帶權(quán)的無環(huán)連通圖。()折半查找方法適用于按值有序的線性鏈表的查找。()哈希表的查找效率主要取決于所選擇的哈希函數(shù)與處理沖突的方法。()選擇排序過程中元素之間的比較次數(shù)與原始序列的狀態(tài)無關(guān)。()二、單項(xiàng)選擇題(每小題2分，共20分)1.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除它的第i數(shù)據(jù)元素之前，需要先依次向前移動(dòng) 個(gè)數(shù)據(jù)元素。()A.n-iB.n+iC.n-i-1D.n-i+1在單鏈表中，已知q指的結(jié)點(diǎn)是q指的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在q和p指的結(jié)點(diǎn)之間插入一個(gè)由s指的結(jié)點(diǎn)，則需執(zhí)行 。()A.link(s)—link(p),link(p)—s B.link(q)—s,link(s)—pC.link(p)—link(s),link(s)—p D.link(p)—s,link(s)—q在非空雙向循環(huán)鏈表中由q所指的那個(gè)鏈結(jié)點(diǎn)前面插入一個(gè)由p指的鏈結(jié)點(diǎn)的動(dòng)作對(duì)應(yīng)的語句依次為:rlink(p)—q,llink(p)—llink(q),llink—p, 。(空白處為一條賦值語句)()A.rlink(q)—pB.rlink(llink(q)—pC.rlink(llink(p))—pD.rlink(rlink(p)—p4?為了節(jié)省存儲(chǔ)空間，將n階對(duì)稱矩陣A中包括主對(duì)角線元素在內(nèi)的下三角部分的所有元素按照行序?yàn)橹餍蚍绞酱娣旁谝痪S數(shù)組B［l:n(n-l)/2］中，對(duì)任意下三角部分的元素aij(i>j)在B的下標(biāo)k是()A.i(i-l)/2+j B.(i(i-l))/2+j C.i(i+l)/2+j B.(i(i+l))/2+j5?某堆棧的輸入序列為a,b,c,d，下面的四個(gè)序列中， 不可能是它的輸出序列。()A.a,c,b,dB.b,c,d,aC.d,c,a,bD.c,d,b,a6?若非空隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),front和rear分別為隊(duì)頭元素與隊(duì)列尾元素的指針，刪除此時(shí)隊(duì)列的一個(gè)元素的*作時(shí)依次執(zhí)行p—fTont, ，callRET(P)。()A.front—link(rear)B.rear—link(p)C.rear—link(front)D.front—link(p)TOC\o"1-5"\h\z7?中綴表達(dá)式A-(B+C)*D/E的后綴形式是 。()A.ABC+-D*E/B.ABC+D*-E/C.ABC+D-*E/D.ABC+D*E/-8?廣大義表A=((),(a),(b,(c,d)))的長(zhǎng)度為()A.2 B.3 C.4 D.59.在初始為空的雜湊表中依次插入關(guān)鍵字序列(MON，TUE，WED，THU，F(xiàn)RI，SAT，SUN),雜湊函數(shù)為H(k)=iMOD7，其中，i為關(guān)鍵字k的第一個(gè)字母在英文字母表中的序號(hào)，地址值域?yàn)椋?:6］，采用線性再散列法處理沖突。插入后的雜湊表應(yīng)該如 所示。()A.0 l 2 3 4 5 6 B.0 l2 3 4 5 6THUTUEWEDFRISUNSATMON TUETHUWEDFRISUNSATMONC.0 l 2 3 4 5 6 D.0 l2 3 4 5 6TUETHUWEDFRISATSUNMON TUETHUWEDSUNSATFRIMON10?從未排序序列中選擇一個(gè)元素，該元素將未排序序列分成前后兩個(gè)部分，前一部分中所有元素都小于等于所選元素。后一部分中所有元素都大于等于所選元素，而所選元素處在排序的最終位置。這種排序方法稱為 排序法。()A.插入 B.謝爾 C.快速 D.堆積三、填空題(每小題2分，共20分)已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占 k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為L(zhǎng)OC(al),那么，TOC\o"1-5"\h\zLOC(ai)= 。若一棵二叉樹有10個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)的點(diǎn)個(gè)數(shù)為 。3?具有n個(gè)結(jié)點(diǎn)的非空二叉排序樹的最小深度為 。深度為h且有 個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。(設(shè)根結(jié)點(diǎn)處在第1層)。二叉樹的前序遍歷序列為A，B，C，E，F(xiàn)，D，G，H，中序遍歷序列為A，E，C，F(xiàn)，B，G，H，其后序遍歷序列為 。已知序列(34，76，45，18，26，54，92，65，)，按照逐點(diǎn)插入法建立一棵二叉排序列樹，該樹的深度是 。一個(gè)不帶有權(quán)的有向圖采用鄰接矩陣存儲(chǔ)方法，其鄰接矩陣是一個(gè) 。帶權(quán)連通圖G=<V,E>，其中V={v1,v2,v3,v4,v5,},E={(v1,,v2)7,(v1,v4)6,(v1,v4)9,(v2,v3)8,(v2,v4)4,(v2,v5)