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

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

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

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

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

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

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

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

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

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

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

15.GetTail(p)為求廣義表p的表尾函數(shù)。其中()是函數(shù)符號(hào)，運(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．在左右子樹(shù)均不空的先序線索二叉樹(shù)〔有n個(gè)結(jié)點(diǎn)〕中，空鏈域的數(shù)目是1。

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

在有序表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.中序遍歷二叉樹(shù)T的遞歸算法，對(duì)數(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-樹(shù)〔見(jiàn)下列圖〕，依次插入關(guān)鍵字3及90，分別寫(xiě)出每插入一個(gè)關(guān)鍵字后所生成的B-樹(shù)?〔10分〕。

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

6.一無(wú)向帶權(quán)圖〔見(jiàn)下列圖〕，寫(xiě)出其最小生成樹(shù)〔10分〕。

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

四、簡(jiǎn)答題〔每題7分，共42分〕

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

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

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

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

答：DFS生成樹(shù)如附圖下列圖所示