數(shù)據(jù)結(jié)構(gòu)暨南大學(xué)試題

1.對順序存儲結(jié)構(gòu)的線性表,設(shè)表長為La;插入一個數(shù)據(jù)元素需平均]移動表中元素n/2個;在最壞情況下需移動表中元素_n_個。

2.從邏輯角度看，四種根本的數(shù)據(jù)結(jié)構(gòu)可分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)；兩種存儲結(jié)構(gòu)為順序和鏈?zhǔn)健?/p>

5.堆棧被稱為一個后進(jìn)先出的線性表;隊(duì)列被稱為一個先進(jìn)先出的線性表

6.靜態(tài)查找表的查找方法主要有：有序表查找及有序表、靜態(tài)樹表、索引順序表等查找方法；

8.內(nèi)部排序方法大致可分為插入、交換、選擇、歸并和計數(shù)等五類；簡單排序方法的時間復(fù)雜度為O(n2)。

9．前序序列和中序序列相同的二叉樹為單右支二叉樹或孤立結(jié)點(diǎn)10.文件的組織方式有順序、隨機(jī)和鏈等三種；順序文件又可分為連續(xù)文件和串聯(lián)文件兩大類。

11.在內(nèi)部排序中，平均比擬次數(shù)最少的是快速排序，要求附加的內(nèi)存容量最大的是歸并排序。

12.由n個權(quán)值構(gòu)成的哈夫曼樹共有2n-1個結(jié)點(diǎn)。

13.在單鏈表中，除首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由其直接前趨結(jié)點(diǎn)的鏈域指示。

14.棧結(jié)構(gòu)允許進(jìn)行刪除操作的一端稱為棧的棧頂。

15.GetTail(p)為求廣義表p的表尾函數(shù)。其中()是函數(shù)符號，運(yùn)算GetTail(GetHead((a,b),(c,d)))的結(jié)果是(b)。16．循環(huán)鏈表的主要優(yōu)點(diǎn)是從任一結(jié)點(diǎn)出發(fā)可以遍歷鏈表中的所有結(jié)點(diǎn)

17．在左右子樹均不空的先序線索二叉樹〔有n個結(jié)點(diǎn)〕中，空鏈域的數(shù)目是1。

18.如果含n個頂點(diǎn)的圖是一個環(huán)，那么它有n棵生成樹。

在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。假設(shè)找到，那么函數(shù)值為該元素在表中的位置，否那么為0。

Low=1;high=ST.length;

While(low<=high){

mid=(low+high)/2;

ifEQ(key,ST.elem[mid].key)returnmid;

elseifLT(key,ST.elem[mid].key)high=mid-1;

elselow=mid+1;

2.中序遍歷二叉樹T的遞歸算法，對數(shù)據(jù)元素操作調(diào)用函數(shù)printf()。

InOrderTraverse(structTNode*T){

if(T){

InOrderTraverse(___T->lchild___);

printf("%c",___T->data_____);

InOrderTraverse(___T->rchild_____);

3.voidPop(SqStack*S0,char*e){

//假設(shè)棧不空，那么刪除棧頂元素，用e返回其值。

if(S0->top==__S0->base_____)return;

____(S0->top)_____;

*e=*(____(S0->top)_____);

4.給出一整數(shù)序列(4,2,5,6,3),從小到大排序選用直接插入排序、2—路歸并排序及快速排序:(2,4,5,6,3),(2,4,5,6,3),(3,2,4,6,5)5.一顆3階的B-樹〔見下列圖〕，依次插入關(guān)鍵字3及90，分別寫出每插入一個關(guān)鍵字后所生成的B-樹?〔10分〕。

1.對關(guān)鍵字序列{72，73,71,23,94,16,05,68},按照堆排序〔直接插入排序〕的方法進(jìn)行排序?！?分〕

6.一無向帶權(quán)圖〔見下列圖〕，寫出其最小生成樹〔10分〕。

7.4個結(jié)點(diǎn)的權(quán)值為｛20，30，32，40，78｝，構(gòu)造一顆赫夫曼樹，并寫出其赫夫曼編碼〔10分〕。

四、簡答題〔每題7分，共42分〕

3.一棵二叉樹的中序遍歷序列為CDBAEGF,先序遍歷序列為ABCDEFG，試問能不能唯一確定一棵二叉樹，假設(shè)能，請畫出該二叉樹。

答：〔1〕由中序遍歷序列和先序遍歷或中序遍歷和后序遍歷序列可以唯一確定一棵二叉樹。根本思想是前序〔后序〕定根，中序分左右。

對于給定的先序和中序序列，可確定根結(jié)點(diǎn)為A,以A為根的左子樹結(jié)點(diǎn)為B,C,D,右子樹結(jié)點(diǎn)為E,F,G。進(jìn)一步確定所有子樹的根結(jié)點(diǎn)，因而也就確定了整個二叉樹。對應(yīng)的二叉樹如附圖2所示。

4.一個有向圖和該圖的鄰接表如圖1所示，并依此鄰接表進(jìn)行從頂點(diǎn)a開始出發(fā)的深度優(yōu)先遍歷，畫出由此得到的深度優(yōu)先生成樹。

答：DFS生成樹如附圖下列圖所示