選擇題：

在建立某高校網(wǎng)站時(shí)，為方便瀏覽，建立了校-系-教研室的鏈接則這數(shù)據(jù)結(jié)構(gòu)屬于（

）A

．線性結(jié)構(gòu) B

．樹(shù)結(jié)構(gòu) C

．圖結(jié)構(gòu) D

．集合結(jié)構(gòu)

設(shè)單鏈表的每個(gè)結(jié)點(diǎn)有兩個(gè)域:element和link，在指針p所指示結(jié)點(diǎn)之后插入新結(jié)點(diǎn)*s的操作是（

）A．s->link=p;p->link=s;C．s->link=p->link;p=s;B．s->link=p->link;p->link=sD．p->link=s;s->link=p;3.元素序列(A，B，C，D，E)順序進(jìn)棧，每個(gè)元素必須進(jìn)棧

一次，進(jìn)棧后可立即出棧，也可在棧中停留一段時(shí)間后再出棧，則下面哪個(gè)序列不能得到（

）A

．

A,B,C,D,EC.

B,E,D,C,AB

．

E,D,C,B,AD.

B,E,C,D,A4.對(duì)一個(gè)已經(jīng)存在的二叉排序樹(shù)遍歷，能夠得到非遞減序列的遍歷是（

）A）

先序遍歷

B）中序遍歷

C）

后序遍歷

D）

層遍歷5.在循環(huán)隊(duì)列中，判斷隊(duì)列滿的條件是（

）（Q.rear+1）%MAXQSIZE＝＝Q.frontQ.rear＝＝Q.front（Q.

front

+1）%MAXQSIZE＝＝Q.

rearQ.rear＋Q.front＝＝MAXQSIZE判斷題：

哈夫曼樹(shù)的根結(jié)點(diǎn)的權(quán)值等于所有葉結(jié)點(diǎn)（外結(jié)點(diǎn)）的權(quán)值之和。一個(gè)無(wú)向連通圖的生成樹(shù)是一個(gè)極大的連通子圖。

用堆排序時(shí)，若想得到一個(gè)非遞減順序表，則構(gòu)造堆的堆頂元素應(yīng)該最小選擇排序是穩(wěn)定的排序算法一個(gè)頂點(diǎn)數(shù)為n的無(wú)向連通圖至少由n-1條邊D=(A,

C,

B);三：填空題，請(qǐng)?jiān)诖痤}紙上寫(xiě)下結(jié)果（共6題，每題5分）１、數(shù)據(jù)結(jié)構(gòu)由四類基本結(jié)構(gòu)，分別是

集合

、線性結(jié)構(gòu)

、樹(shù)形結(jié)構(gòu)、_圖形結(jié)構(gòu)

。２、已知樹(shù)t的先根次序訪問(wèn)序列為GFKDAIEBCHJ樹(shù)t的后根次序訪問(wèn)序列為：

DIAEKFCJHBG請(qǐng)判斷樹(shù)t的度為

3

、層為5

。３、已知廣義表：A=(

)；B=(e);

C=(a,(b,c,d));則GetHead(GetTail(D)=

C

４、圖的遍歷方法有深度優(yōu)先和_廣度優(yōu)先５、對(duì)于關(guān)鍵字序列{46

,

58

,15

，

45

，

90

，

18

，

10

，

62}

，其快速排序第一趟的結(jié)果是_1_0

1_8

1_5_5

4_5

4_4_6

9_0

5_8

6_2_６、給出字符串“ａｂａｃａｂａａａｄ”在KMP算法中的next數(shù)0組1＿12＿12＿34＿22＿＿＿＿＿和nextval數(shù)0組102010422綜合練習(xí)二北師大06年研究生試題一、翻譯題

二、簡(jiǎn)答題（考背誦）略三、判斷題，若正確，請(qǐng)畫(huà)對(duì)號(hào)，否則畫(huà)叉，并說(shuō)明理由（２０分）·

、圖Ｇ的一棵最小生成樹(shù)的代價(jià)未必小于Ｇ的其他任何一棵生成樹(shù)的代價(jià)。（

）·

、二唯數(shù)組Ａ的每個(gè)元素是由６個(gè)字符組成的串，其行下標(biāo)i=0、２……８，列下標(biāo)j=１、２……10，若Ａ按行先存儲(chǔ)，元素A[8,5起始地址與Ａ按列先存儲(chǔ)時(shí)的元素A[5,10]的起始地址相同（設(shè)每個(gè)字符占一個(gè)字節(jié)）。（

）·、用鄰接矩陣Ａ表示圖，判定任意兩個(gè)節(jié)點(diǎn)Vi和Vj之間是否有長(zhǎng)度為m的路徑相連，則只要檢查Am的第i行第j列的元素是否為０即可（

）·、已知待排序的n個(gè)元素可分為n/k組，每個(gè)組內(nèi)包含k個(gè)元素，且任一組內(nèi)的各元素均分別大于前一組內(nèi)的所有元素和小于后

一組內(nèi)的所有元素，若采用基于比較的排序，其時(shí)間下界應(yīng)為O(nlog2K)（

）最小生成樹(shù)不一定唯一。8*10+(5-1)!=(10-1)*9+5舉例：1

2

3，畫(huà)出矩陣組內(nèi)用快速排序，快速排序的復(fù)雜度為klogk四、填空（每題６分，共30分）·

、下列程序的功能是按照右側(cè)的格式輸出的６行楊暉三角形，請(qǐng)?zhí)羁諏⒊绦蜓a(bǔ)充完整。main(){

int

y[7][7],n,m;·

for(n=1;n<7;n++)

{=1;

y[n][1]=11111211

3

3

1;

}14641y[1][n]

·

for(n=3;n<7;n++)·

for(m=2;m<n;m++)15

10

10

5

1·

y[n][ym[]n=-1][m]+y[n-1][m-1]

·

for(n=1;n<7;n++){·

for(m=1;m<=n;m++)·

printf("Y%[4nd]"[,m] );·

printf("\n");·}·}

、具有1/2(n-1)條邊的無(wú)向圖稱為無(wú)_向完全圖，簡(jiǎn)稱為完全圖

,其中n表示無(wú)向圖頂點(diǎn)的個(gè)數(shù)，1/2(n-1)是具有n個(gè)頂點(diǎn)無(wú)向圖所擁有邊的_最大數(shù)

、在AOV網(wǎng)中不可能出現(xiàn)有向環(huán)或回路，如果出現(xiàn)環(huán)或回路，這意味著某項(xiàng)活動(dòng)是_以自己為先決條件，這樣的工程無(wú)法進(jìn)行，對(duì)于計(jì)算機(jī)中的程序流程圖來(lái)說(shuō)就是

死循環(huán)、比較以下4種排序方法，填寫(xiě)下表：五：函數(shù)expand（char

s[],char

t[])在將字符串s復(fù)制到字符串t時(shí)將其中的換行符和制表符轉(zhuǎn)換為可見(jiàn)的轉(zhuǎn)義字符，即用“\n”表示換行符，用“\t”表示制表符。填空將程序補(bǔ)充完整。Expand

(char

s[

],char

t[

]){int

i,j;for(i=j=0;s[i]!=‘\0’;i++)switch

(s[j]);t[j++]=‘n’;;t[j++]=‘t’;brea]=s[i];break;}‘]\=\’‘]\=\’{case’\n’J+:+t[

case’\n’J+:+t[

default:tJ[++t[j]=‘\_0_’

;}五：應(yīng)用題（16分）已知深度為h的二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)已經(jīng)存放于數(shù)組BT[1:2h-1]中，請(qǐng)寫(xiě)算法，產(chǎn)生該二叉樹(shù)的二叉鏈表結(jié)構(gòu)。詳見(jiàn)excersize-changetree.c

(用遞歸)·

、依據(jù)所示無(wú)向圖，分別用prim和kruskal算法，畫(huà)最小生成樹(shù)普里姆算法：從一個(gè)頂點(diǎn)開(kāi)始生成樹(shù)，每次選與這個(gè)樹(shù)相關(guān)連的最小的邊，等樹(shù)長(zhǎng)成能涵蓋所有頂點(diǎn)，即可。詳見(jiàn)下圖克魯斯卡爾：每次找一條權(quán)值最小的邊，如果這個(gè)邊連接兩個(gè)不同的連通分量，則添加該邊。反復(fù)執(zhí)行到所有頂點(diǎn)都連通為止。詳細(xì)過(guò)程不再給出，請(qǐng)自行作出·、設(shè)有n個(gè)活動(dòng)需要演講會(huì)場(chǎng)，而在同一時(shí)間內(nèi)會(huì)場(chǎng)只能分配給其中一個(gè)活動(dòng)。如果用Ｅ表示活動(dòng)集合，E={1,2……n}，每個(gè)活動(dòng)i使用會(huì)場(chǎng)有一個(gè)起止時(shí)間(si,fi)，其中si<fi。如果兩個(gè)活和j的時(shí)間段不相交，則稱活動(dòng)i與活動(dòng)j是相容的，前后活動(dòng)的時(shí)間邊界重合不算相交。給定規(guī)模為10的問(wèn)題實(shí)例E如下·

{(1,3),

(0,5),

(7,10),

(6,7),

(3,6),

(8,9),

(1,2),

(11,12),(10,13)}求·解給過(guò)出程以：上選問(wèn)一題實(shí)開(kāi)例始的時(shí)解間及最求小解過(guò)的程活動(dòng)作第一個(gè)活動(dòng)，選它的后繼活動(dòng)，使后繼活動(dòng)的開(kāi)始時(shí)間大于且最接近其終止時(shí)間，依次選后繼直到?jīng)]有活動(dòng)滿足