a. 98b. 99c. 50d. 48
8、下列序列中， a 是執行第一趟快速排序後得到的序列（排序的關鍵字型別是字串）。
a. [da , ax , eb , de , bb] ff [ha , gc] b. [cd , eb , ax , da] ff [ha , gc , bb]
c. [gc , ax , eb , cd , bb] ff [da , ha] d. [ax , bb , cd , da] ff [eb , gc , ha]
9、用n個鍵值構造一棵二叉排序樹，最低高度為 d 。
a. n/2b. nc. [log2n] d. [log2n+1]
10、二分查詢法要求查詢表中各元素的鍵值必須是 a 排列。
a. 遞增或遞減 b. 遞增 c. 遞減d. 無序
11、對於關鍵值序列，用篩選法建堆，必須從關鍵值為的節點開始。
a. 100b. 12c. 60d. 15
二、 判斷題：
1、串長度是指串中不同字元的個數
2、陣列可以看成是線性結構的一種推廣，因此可以對它進行插入、刪除等運算
3、在順序表中取出第i 個元素所花費的時間與i 成正比
4、在棧滿的情況下，不能作進棧運算，否則產生「上溢
5、二路歸併排序的核心操作是將兩個有序序列歸併為乙個有序序列
6、對任意乙個圖，從它的某個頂點出發進行一次深度優先或廣度優先搜尋遍歷可訪問到該圖的每個頂點
7、乙個有向圖的鄰接表和逆鄰接表中的節點個數一定相等
8、在索引順序表上實現分塊查詢，在等概率查詢情況下，其平均查詢長度不僅與表的個數有關，而且與每一塊中的元素個數有關
9、二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：若它的左子樹非空，則根節點的值大於其左孩子的值；若它的右子樹非空，則根節點的值小於其右孩子的值
10、在執行某個排序演算法的過程中，出現了排序碼朝著最終排序序列位置相反的方向移動，則該演算法是不穩定的
三、 填空題：
1．在帶有頭結點的單鏈表l中，第乙個元素結點的指標是2．在雙迴圈鍊錶中，在指標p所指結點前插入指標s所指的結點，需執行下列語句s^.next := p； s^.
prior := p^.priorp^.
prior := ss； 3．設s[1 .. maxsize]為乙個順序儲存的棧，變數top指示棧頂位置，棧為空的條
件是棧為滿的條件是4．具有100個結點的完全二叉樹的深度為5. 有向圖 g用鄰接矩陣 a［1 .. n，1 .. n］儲存，其第 i行的所有元素之和等
於頂點 i的6．在順序檔案中，要訪問第i個記錄，必須先訪問
7. 對於右面的二叉樹，按中序遍歷所得到的結點序列
為8．分別採用堆排序、快速排序、插入排序和歸併排序演算法
對初始狀態為遞增序列的表按遞增順序排序，最省時間
的是演算法，最費時間的是演算法。
9．對上圖所示的網，執行prim演算法可得到最小生成樹，試在下表的空白處填上適
當的內容，以說明該演算法的執行過程。
10．設雜湊函式為h（key），用拉鍊（鏈位址）法解決衝突，h的值域為0，…，n-1，
構造的雜湊表型別如下type link = ^nodenode = record
key：keytype；
next：link；
endopenhash = array［0．．n-1］of link； 請在下列演算法劃線處填上適當內容，以完成在雜湊表hp中查詢鍵值等於k的結點，
若查詢成功，返回該結點的指標，否則返回空指標。
function research（k：keytype； hp：openhash）：link；
begin
i := h（k）；
suc := false；
while（p＜＞nil）and（not sue） doif p^.key ＜＞ k
then
else suc := true；
return（p）
end；
四、應用題： 1．已知二叉樹的後序和中序序列如下，構造出該二叉樹後序序列：abcdefg中序序列：
acbgedf 2．有一組關鍵碼序列（3，19，65，13，97，49，41，95，1，73），採用氣泡排序
方法由小到大進行排序，請寫出每趟的結果。 3．設圖g =（v，e），v =｛1，2，3，4，5，6｝，e =｛<1，2>，，<2，5>，<3，
6>，<6， 5>， <5， 4>， <6，4>｝。請寫出圖 g中頂點的所有拓撲序列。 4．設雜湊函式為h（k）= k mod 7，閉雜湊表的位址空間為 o，…，6，開始時雜湊
表為空，用線性探測法解決衝突，請畫出依次插入鍵值23，14，9，6，30，12，
18後的雜湊表。 5．對下面兩棵二叉樹，分別畫出它們的順序儲存結構。
6．已知圖g的鄰接表如下，畫出圖g的所有連通分量。
五、演算法設計題： l．設二叉排序樹的根指標為t，每個結點的結構為： lchild key rchild ，試用類pascal語言寫出演算法以輸出二叉排序樹中最大的鍵值。
2．設乙個環上有若干個整數，現採用單迴圈鍊錶l儲存該環，已知l的結點結構為：
data next ，試畫出鍊錶l的結構圖，並編寫演算法判斷環上任意兩個相鄰元素值之差的絕對值是否不超過2。
3．設一棵二叉樹以二叉鍊錶來儲存，結點結構為： lchild data rchild 設計演算法以求此二叉樹上度為1的結點個數。
資料結構C 模擬試卷
第 1 題.復合題共計 10 分 選擇題 第 1.1 題.客觀單選題 1 分 線性表的邏輯順序和儲存順序總是一致的，這種說法 正確不正確 有些情況可能是正確的 取決於機器實現 第 1.2 題.客觀單選題 1 分 乙個順序表第1個元素的儲存位址是100，每個元素占用位元組數為5，第5個元素的起始位址是...
資料結構模擬考試試卷
一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1.程式和演算法原則上沒有區別，所以在討論資料結構時可以通用。2.在單鏈表中，元素的儲存位置用指標聯絡，所以可以從頭結點開始查詢任何乙個元素。3.乙個棧的輸入序列為 a，b，c，d，可以得到輸出序列 c，a，b，d。4.佇列是一種 先進先出 ...
《資料結構》課程模擬試卷2019
學號姓名教師得分 一 填空 30分左右 1.由85個節點構成的完全二叉樹，其深度為其中第6層的節點數為 個。2 關鍵字1，2，3，5，13，18，27，對其進行折半查詢，那麼查詢關鍵字13的比較次數是 次。3 有一棵二叉樹，它的中序遍歷為 4，5，2，1，6,3，前序遍歷為 1，2，4，5，3，6那...