江西財經大學
06－07第一學期期末考試試卷
試卷**：03266b授課課時：112
課程名稱：資料結構與演算法適用物件：本科
一、單項選擇題(從下列各題四個備選答案中選出乙個正確答案，並將其代號寫在答題紙相應位置處。答案錯選或未選者，該題不得分。每小題2分，共24分。)
1.資料結構被形式地定義為 (k, r)，其中k是____的有限集，r是k上的關係有限集。
a.演算法 b.資料元素 c.資料操作 d.邏輯結構
2.在資料結構中，從邏輯上可以把資料結構分成____。
a.動態結構和靜態結構b.緊湊結構和非緊湊結構
c.線性結構和非線性結構d.內部結構和外部結構
3.以下的敘述中，正確的是____。
a.線性表的儲存結構優於鏈式儲存結構
b.二維陣列是其資料元素為線性表的線性表
c.棧的操作方式是先進先出
d.佇列的操作方式是先進後出
4.若乙個棧的入棧序列是1、2、3、… 、n，其輸出序列為p1、p2、p3、… 、pn，若p1=n，則pi為____。
a. i b. n = i c. n - i +1 d.不確定
5.判斷乙個迴圈佇列qu (最多元素為m) 為空的條件是____。
a. qu->front == qu->rearb. qu->front != qu->rear
c. qu->front == (qu->rear+1)%m d. qu->front != (qu->rear+1)%m
6.在某單鏈表中，已知p所指結點不是最後結點，在p之後插入s所指結點，則執行____。
a. s->next = p; p->next=sb. s->next = p->next; p->next = s;
c. s->next = p->next; p = s; d. p->next = s; s->next = p;
7.串是一種特殊的線性表，其特殊性體現在____。
a.可以順序儲存b.資料元素是乙個字元
c.可以鏈結儲存d.資料元素可以是多個字元
8.已知某二叉樹的後序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列是____。
a. acbed b. decab c. deabc d. cedba
9.對於乙個滿二叉樹，m個樹葉，n個結點，深度為h，則____。
a. n = h + m b. h + m = 2n c. m = h-1 d. n = 2h -1
10.乙個有n個頂點的無向圖最多有____條邊。
a. n b. n(n-1) c. n(n-1)/2 d. 2n
11.順序查詢法適合於儲存結構為____的線性表。
a. 雜湊儲存b. 順序儲存或鏈結儲存
c. 壓縮儲存d. 索引儲存
12.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。
a. 插入排序 b.選擇排序 c.快速排序 d. 歸併排序
二、填空題(請在每小題的橫線上填入正確內容，每空1分，共7分。)
1.**性結構中，第乙個結點前驅結點，其餘每個結點有且只有1個前驅結點。
2.在無權圖g的鄰接矩陣中，若a[i][j]等於1，則等於a[j][i] = 。
3.根據二叉樹的定義，具有三個結點的二叉樹有種不同的形態。
4.空格串是指其長度等於
5.在雜湊儲存中，裝填因子α的值越大，則儲存元素時發生衝突的可能性就 。
6.已知模式串t= 『abacabaaad』， 其用kmp法求得的每個字元對應的next函式值為
三、簡答題(本大題共3小題，每小題5分，共15分)
1.比較靜態查詢與動態查詢的主要區別，它們的基本運算有哪些不同？
2.邏輯結構分哪幾種，儲存結構有哪幾種？
3.在具有n(n>1)個結點的各棵不同形態樹中，其中深度最小的那棵樹的深度是多少？它共有多少葉子和非葉子結點？
四、判斷題(本大題共10小題，命題正確的在題後括號內寫 「t」，錯誤的在題後括號內寫「f」，每小題1分，共10分)
1.每種資料結構都應具備三種基本運算：插入、刪除、搜尋( )。
2.滿二叉樹不一定是完全二叉樹。( )
3.帶權連通圖的最小生成樹的權值之和一定小於它的其它生成樹的權值之和。( )
4.任一棵二叉搜尋樹的平均搜尋時間都小於用順序搜尋法搜尋同樣結點的順序表的平均搜尋時間。( )
5.線性鍊錶中所有結點的型別必須相同。( )
6.用鄰接矩陣儲存乙個圖時，在不考慮壓縮儲存的情況下，所占用的儲存空間大小只與圖中頂點個數有關，而與圖的邊數無關( )。
7.在雜湊法中解決衝突時，其裝載因子的取值一定在(0，1)之間。( )
8.任何乙個關鍵活動延遲，那麼整個工程將會延遲。( )
9.平衡二叉樹的左右子樹深度之差的絕對值不超過1。( )
個結點的有向圖，若它有n(n－1)條邊，則它一定是強連通的。( )
五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1.下述演算法的功能是什麼? （6分）
linklist demo(linklist l)
return l;
} 2.將給定的圖簡化為最小的生成樹，要求從頂點1出發。（7分）
3.設雜湊表為ht[13], 雜湊函式為 h (key) = key %13。用雙雜湊法解決衝突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。
再雜湊函式為 rh (key) = (7*key) % 10 + 1, 尋找下乙個位址的公式為 hi = (hi-1 + rh (key)) % 13, h1 = h (key)。畫出相應的雜湊表, 並計算等概率下搜尋成功的平均搜尋長度。（7分）
4.設待排序的排序碼序列為,寫出使用快速排序法每趟排序後的結果。（6分）
六、演算法設計題（本題共18分，第1小題10分，第2小題8分）
1.試設計乙個實現下述要求的查詢運算函式locate。設有乙個帶表頭結點的雙向鍊錶l， 每個結點有4個資料成員：
指向前驅結點的指標llink、指向後繼結點的指標rlink，存放字元資料的成員data和訪問頻度freq。所有結點的freq 初始時都為0。每當在鍊錶上進行一次locate(l, x) 操作時，令元素值為x的結點的訪問頻度freq加1，並將該結點前移，鏈結到與它的訪問頻度相等的結點後面，使得鍊錶中所有結點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結點總是靠近表頭。
(10分)
2.設一棵二叉樹以二叉鍊錶為存貯結構，設計乙個演算法將二叉樹中所有結點的左，右子樹相互交換。要求給出二叉鍊錶的型別定義。(8分)
演算法與資料結構
演算法 是按部就班地解決某個問題的方法，是對特定問題求解步驟的一種描述。偽碼語言是一種包括高階程式語言的3種基本控制結構 順序 選擇和迴圈 和自然語言成分的 物件導向 的語言。演算法的特徵 1 可行性 一是演算法中的每個步驟必須是能實現的 二是演算法執行的結果要能達到預期的目的。2 確定性 演算法的...
資料結構與演算法
課程設計報告 目錄一 問題描述1 二 資料結構1 三 演算法設計思想及流程圖1 四 源程式2 五 測試情況6 參考文獻6 一 問題描述 計算表示式的值 問題描述 對於給定的乙個表示式，表示式中可以包括常數 算術執行符和括號，編寫程式計算表示式的值。基本要求 從鍵盤輸入乙個正確的中綴表示式，將中綴表示...
資料結構與演算法信
美國uiuc大學博士生梅俏竹 資料結構是美國所有一流計算機系的本科核心課程之一，上承計算引論與初級程式設計，下啟高階演算法和計算理論，向來是計算機本科教學的重中之重。我在北大上過的諸多本科基礎課中，無論從課程內容和老師教學下的功夫來看，張銘老師的 資料結構與演算法 課程都是首屈一指的。可以說，將北大...