華北科技學院
一、選擇題（每題2 分，共 10 題，總計 20 分）
1、下列資料中是非線性資料結構。
a．棧 b. 佇列 c. 完全二叉樹 d. 陣列
2、乙個棧的輸入序列為123…n，若輸出序列的第乙個元素是n，輸出第i（1<=i<=n）個元素是
a. 不確定b. n-i+1c. id. n-i
3、下面關於線性表的敘述中，錯誤的是哪乙個
a．線性表採用順序儲存，必須占用一片連續的儲存單元。
b．線性表採用順序儲存，便於進行插入和刪除操作。
c．線性表採用鏈結儲存，不必占用一片連續的儲存單元。
d．線性表採用鏈結儲存，便於插入和刪除操作。
4、某堆疊的輸入序列為a, b，c ，d,下面的四個序列中，不可能是它的輸出序列的是
a. a，c，b，d b. b, c，d，a c. c, d，b, a d. d, c，a，b
5、判定乙個棧st（最多元素為n）為空的條件是
a．st->top < > 0 b．st->top = = st->base
c．st->top < > n d．st->top = = n
6、設森林f有m個結點，它對應的二叉樹為b，b的根為p，p的右子樹結點個數為n，森林f中第一棵樹的結點個數是
a．m-n b．m-n-1 c．n+1 d．條件不足，無法確定
7、設有一組記錄的關鍵字為，用鏈位址法構造雜湊表，雜湊函式為h（key）=key mod 13,雜湊位址為1的鏈中有個記錄。
a．4b. 3 c. 2 d. 1
8、二維陣列amn按行序為主序存放在記憶體,每個陣列元素佔1 個儲存單元 , 則元素 aij 的位址計算公式是
(a) loc(aij)=loc(a11)+[(i-1)*m+(j-1)]
(b) loc(aij)=loc(a11)+[(j-1)*m+(i-1)]
(c) loc(aij)=loc(a11)+[(i-1)*n+(j-1)]
(d) loc(aij)=loc(a11)+[(j-1)*n+(i-1)]
9、連通圖g中有n個頂點,g的生成樹是的極小連通子圖。 (a) 包含g的所有邊b) 包含g的所有頂點
(c)不必包含g的所有頂點 (d)必須包含g的所有頂點和所有的邊
10、氣泡排序屬於
(a) 插入排序 (b) 選擇排序 (c)歸併排序 (d) 交換排序
二、填空題（每空2分，共10空，總計20分）
1、演算法一般應具有5個特性確定性、可行性輸出。
2、假設有二維陣列a6×8，每個元素用相鄰的6個位元組儲存，儲存器按位元組編址。已知a的起始儲存位置（基位址）為1000，則末尾元素的第乙個位元組位址為若按行儲存時，元素a[1][4]的第乙個位元組位址為下標從0開始）
3、在一棵二叉樹中，度為０的結點個數為n0，度為２的個數為n2，則n0
4、圖的遍歷有兩種,它們是和
5、查詢錶可分為靜態查詢表和查詢表。
6、在雙向鍊錶結構中，若要求在p 指標所指的結點之前插入指標為s 所指的結點，則需執行下列語句：
s->next = p； s->prior
p->prior = ss；
三、簡答題（每題6分，共4 題，總計24分）
1、已知某二叉樹按先序遍歷序列為a，b，c，e，f，d，g，h，按中序序遍歷序列為a ，e,c，f，b，g，d，h，試畫出該二叉樹形狀， 並寫出它的後序遍歷序列。
2、什麼是穩定排序?什麼是不穩定排序?
3、對下面數列 利用shell排序演算法進行排序，試畫出每遍排序結束時數列狀態。假設增量序列為5、3、1。
4、畫出下列有向圖的鄰接表儲存結構，並由鄰接表寫出廣度優先搜尋序列。
四、設a,b,c,d,e,f,g,h八個字母出現的概率分別為0.14, 0.23, 0.
07, 0.05, 0.29, 0.
03, 0.08, 0.11寫出為這八個字母設計的huffman編碼，並畫出對應huffman樹。
（本題8分）
五、已知6行7列稀疏矩陣a的三元組表表示為 n=((1,4,6),(2,3,5),
(2,6,2),(4,2,7),(5,1,2),(5,5,1),(5,6,4),(6,1,8),(6,7,8))，試寫出該稀疏矩陣及a的轉置矩陣的三元組表示。（本題8分）
六、對下圖所示的森林：（10分）
1． 給出圖c所示樹的雙親表示
2． 給出圖a所示樹的孩子鍊錶表示。
3． 將此森林轉換為相應的二叉樹
七、演算法設計：已知資料結構型別如下：
typedef structredtype;
redtype r[50];
r[ ]陣列中key內儲存著待排序的關鍵字，寫出折半插入排序的演算法
（對定義的變數和函式名加必要的注釋）（10分）
資料結構練習
華東理工大學網路學院 資料結構 ch1緒論和ch2線性表 班級學號姓名成績 一 名詞解釋 每小題2分，共10分 1.資料結構 2.線性結構 3.儲存結構 4.邏輯結構 5.非線性結構 答 1.資料結構 指的是資料之間的相互關係，即資料的組織形式。一般包括三個方面的內容 資料的邏輯結構 儲存結構和資料...
資料結構練習二
一 選擇 1 用單鏈表方式儲存的線性表,儲存每個結點需要兩個域,乙個是資料域,另乙個是 b a.當前結點所在位址域.b.指標域.c.空指標域.d.空閒域.2 在具有n個結點的單鏈表中,實現 a 的操作,其演算法的時間複雜度是o n a.遍歷鍊錶和求鍊錶的第i個結點.b.在位址為p的結點之後插入乙個結...
資料結構練習一
一 單選 1.資料結構通常是研究資料的 a 及它們之間的相互關係.a.儲存和邏輯結構 b.儲存和抽象 c.理想與抽象 d.理想與邏輯 2.資料在計算機儲存器內表示時,實體地址與邏輯位址相同並且是連續的,稱為 c a.儲存結構 b.邏輯結構 c.順序儲存結構 d.鏈式儲存結構 3.非線性結構是資料元素...