1、（12分）

　　請(qǐng)回答下列關(guān)于圖（Graph）的一些問題：

　　①（4分）有n個(gè)頂點(diǎn)的有向連通圖最多有多少條邊？最少有多少條邊？

　　②（4分）表示一個(gè)有1000個(gè)頂點(diǎn)、1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素？是否稀疏矩陣？

　　③（4分）對(duì)于一個(gè)有向圖，不用拓?fù)渑判颍�如何判斷圖中是否存在環(huán)？

　　2、（12分）

　　斐波那契數(shù)列Fn定義如下：

　　F0=0，F(xiàn)1=1，F(xiàn)n= Fn-1 + Fn-2，n=2，3，…

　　請(qǐng)就此斐波那契數(shù)列，回答下列問題：

　　①（7分）在遞歸計(jì)算Fn的時(shí)候，需要對(duì)較小的Fn－1，F(xiàn)n－2，…，F(xiàn)1，F(xiàn)0精確計(jì)算多少次？

　�、冢�5分）若干有關(guān)大O表示法，試給出遞歸計(jì)算Fn時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度是多少？

　　3、（17分）

　　有一種簡(jiǎn)單的排序算法，叫做計(jì)數(shù)排序（count sorting）。這種排存算法對(duì)一個(gè)待排序的表（用數(shù)組表示）進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是，表中所有待排序的關(guān)鍵碼互不相同。計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小。假設(shè)針對(duì)某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c，那么，這個(gè)記錄在新的有序表中的合適的存放位置即為c.

　　①（3分）給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義；

　　②（7分）使用Pascal或C語(yǔ)言編寫實(shí)現(xiàn)計(jì)數(shù)排序的算法；

　　③（4分）對(duì)于有n個(gè)記錄的表，關(guān)鍵碼比較次數(shù)是多少？

　�、埽�3分）與簡(jiǎn)單選擇排序相比較，這種方法是否更好？為什么？

　　4、（10分）

　　在一棵表示有序集S的二叉搜索樹（binary search tree）中，任意一條從根到葉節(jié)點(diǎn)的路徑將S分為3部分：在該路徑左邊節(jié)點(diǎn)中的元素組成的集合S1；在該路徑上的節(jié)點(diǎn)中的元素組成的集合S2；在該路徑右邊節(jié)點(diǎn)中的元素組成的集合S3.S＝S1∪S2∪S3.若對(duì)于任意的a∈S1，b∈S2，c∈S3，是否總有a<=b<=c？為什么？

　　5、（12分）請(qǐng)回答下列關(guān)于堆（Heap）的一些問題：

　　①（4分）堆的存儲(chǔ)表示是順序的，還是鏈接的？

　　②（4分）設(shè)有一個(gè)最小堆，即堆中任意節(jié)點(diǎn)的關(guān)鍵碼均大于它的左子女和右子女的關(guān)鍵碼。其具有最大值的元素可能在什么地方？

　　③（4分）對(duì)n個(gè)元素進(jìn)行初始建堆的過程中，最多做多少次數(shù)據(jù)比較（不用大O表示法）？

　　6、（12分）

　　已知Q是一個(gè)非空隊(duì)列，S是一個(gè)空棧。僅用隊(duì)列和棧的ADT函數(shù)和少量工作變量，使用Pascal或C語(yǔ)言編寫一個(gè)算法，將隊(duì)列Q中的所有元素逆置。

　　棧的ADT函數(shù)有：

　　makeEmpty（s：stack）；置空棧

　　push（s：stack；value：datatype）；新元素value進(jìn)棧

　　pop（s：stack）：datatype；出棧，返回棧頂值

　　isEmpty（s：stack）：boolean；判�？辗�

　　隊(duì)列的ADT函數(shù)有

　　enqueue（q：queue；value：datatype）；元素value進(jìn)隊(duì)

　　deQueue（q：queue）：datatype；出隊(duì)列，返回隊(duì)頭值

　　isEmpty（q：queue）：boolean；判隊(duì)列空否

　　7、（13分）

　　設(shè)散列表為HT[0……12]，即表的大小為m=13.現(xiàn)采用雙散列法解決沖突。散列函數(shù)和在散列函數(shù)分別為：

　　H0（key）=key%13；注：％是求余數(shù)運(yùn)算（＝mod）

　　Hi=（Hi-1+REV（key+1）%11+1）%13；i=1，2，3，…，m-1

　　其中，函數(shù)REV（x）表示顛倒10進(jìn)制數(shù)x的各位，如REV（37）=73，REV（7）=7等。若插入的關(guān)鍵碼序列為{2，8，31，20，19，18，53，27}.

　�、伲�8分）試畫出插入這8個(gè)關(guān)鍵碼后的散列表。

　�、冢�5分）計(jì)算搜索成功的平均搜索長(zhǎng)度ASL.

　　8、（12分）

　　從左到右及從右到左遍歷一個(gè)單鏈表是可能的，其方法是在從左向右遍歷的過程中將連接方向逆轉(zhuǎn)，如圖1所示。在圖中的指針p指向當(dāng)前正在訪問的節(jié)點(diǎn)，指針pr指向指針p所指節(jié)點(diǎn)的左側(cè)的節(jié)點(diǎn)。此時(shí)，指針p所指節(jié)點(diǎn)左側(cè)的所有節(jié)點(diǎn)的連接方向都已逆轉(zhuǎn)。

　　圖1題8圖

　　①（6分）使用Pascal或C語(yǔ)言編寫一個(gè)算法，從任一給定位置（pr，p）開始，將指針p右移1個(gè)節(jié)點(diǎn)。如果p移出鏈表，則將p置為NULL，并讓pr留在鏈表最右邊的節(jié)點(diǎn)上。

　　②（6分）使用Pascal或C語(yǔ)言編寫一個(gè)算法，從任一給定位置（pr，p）開始，將指針p左移一個(gè)節(jié)點(diǎn)。如果p移出鏈表，則將p置為NULL，并讓pr停留在鏈表最左邊的節(jié)點(diǎn)上。