鏈結儲存表示的儲存空間一般在程式的執行過程中動態分配和釋放，且只要儲存器中還有空間，就不會產生儲存溢位的問題。同時在插入和刪除時不需要保持資料元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動資料，只需修改它們的鏈結指標，修改效率較高。但訪問表中的資料元素時，只能循鏈順序訪問，因此訪問效率不高。
(2) 如果有n個表同時並存，並且在處理過程中各表的長度會動態發生變化，表的總數也可能自動改變、在此情況下，應選用鏈結儲存表示。
如果採用順序儲存表示，必須在乙個連續的可用空間中為這n個表分配空間。初始時因不知道哪個表增長得快，必須平均分配空間。在程式執行過程中，有的表占用的空間增長得快，有的表占用的空間增長得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進行元素的插入時就必須成片地移動其他的表的空間，以空出位置進行插入；在元素刪除時，為填補空白，也可能移動許多元素。
這個處理過程極其繁瑣和低效。
如果採用鏈結儲存表示，乙個表的儲存空間可以連續，可以不連續。表的增長通過動態儲存分配解決，只要儲存器未滿，就不會有表溢位的問題；表的收縮可以通過動態儲存釋放實現，釋放的空間還可以在以後動態分配給其他的儲存申請要求，非常靈活方便。對於n個表(包括表的總數可能變化)共存的情形，處理十分簡便和快捷。
所以選用鏈結儲存表示較好。
(3) 應採用順序儲存表示。因為順序儲存表示的訪問速度快，但修改效率低。若表的總數基本穩定，且很少進行插入和刪除，但要求以最快的速度訪問表中的元素，這時採用順序儲存表示較好。
四、 設有乙個雙端佇列，元素進入該佇列的順序是1, 2, 3, 4。試分別求出滿足下列條件的輸出序列。（9分）
(1) 能由輸入受限的雙端佇列得到，但不能由輸出受限的雙端佇列得到的輸出序列；（3分）
(2) 能由輸出受限的雙端佇列得到，但不能由輸入受限的雙端佇列得到的輸出序列；（3分）
(3) 既不能由輸入受限的雙端佇列得到，又不能由輸出受限的雙端佇列得到的輸出序列。（3分）
【解答】
允許在一端進行插入和刪除，但在另一端只允許插入的雙端佇列叫做輸出受限的雙端佇列，允許在一端進行插入和刪除，但在另一端只允許刪除的雙端佇列叫做輸入受限的雙端佇列。
輸出受限雙端佇列不能得到的輸出序列有：
4 1 3 2 4 2 3 1
輸人受限雙端佇列不能得到的輸出序列有：
4 2 1 3 4 2 3 1
所以有：
(1) 4 1 3 2
(2) 4 2 1 3
(3) 4 2 3 1
五、 使用 (1) 順序表示和 (2) 二叉鍊錶表示法，
分別畫出右圖所示二叉樹的儲存表示。（9分）
【解答】
六、 試分別找出滿足以下條件的所有二叉樹:（9分）
(1) 二叉樹的前序序列與中序序列相同;(3分)
(2) 二叉樹的中序序列與後序序列相同;（3分）
(3) 二叉樹的前序序列與後序序列相同。（3分）
【解答】
(1) 二叉樹的前序序列與中序序列相同：空樹或缺左子樹的單支樹；
(2) 二叉樹的中序序列與後序序列相同：空樹或缺右子樹的單支樹；
(3) 二叉樹的前序序列與後序序列相同：空樹或只有根結點的二叉樹。
七、 已知一棵二叉樹的前序遍歷的結果是abecdfghij, 中序遍歷的結果是ebcdafhigj, 試畫出這棵二叉樹。（9分）
【解答】
當前序序列為abecdfghij，中序序列為ebcdafhigj時，逐步形成二叉樹的過程如下圖所示：
八、給定權值集合, 構造相應的霍夫曼樹, 並計算它的帶權外部路徑長度。（9分）
【解答】
此樹的帶權路徑長度wpl = 229。
九、 畫出1個頂點、2個頂點、3個頂點、4個頂點和5個頂點的無向完全圖。試證明在n個頂點的無向完全圖中，邊的條數為n(n-1)/2。（9分）
【解答】
【證明】
在有n個頂點的無向完全圖中，每乙個頂點都有一條邊與其它某一頂點相連，所以每乙個頂點有n-1條邊與其他n-1個頂點相連，總計n個頂點有n(n-1)條邊。但在無向圖中，頂點i到頂點j與頂點j到頂點i是同一條邊，所以總共有n(n-1)/2條邊。
十、 有n個頂點的無向連通圖至少有多少條邊？有n個頂點的有向強連通圖至少有多少條邊？試舉例說明。（9分）
【解答】
n個頂點的無向連通圖至少有n-1條邊，n個頂點的有向強連通圖至少有n條邊。例如：
特例情況是當n = 1時，此時至少有0條邊。
十一、以鄰接表為儲存結構，寫乙個基於dfs遍歷策略的演算法，求圖中通過某頂點vk的簡單迴路（若存在）。（10分）
解：演算法思想，從給定頂點v4出發進行深度優先搜尋，在搜尋過程中判斷當前訪問的頂點是否為v4。若是，則找到一條迴路。
否則繼續搜尋。為此設乙個順序棧cycle記錄構成迴路的頂點序列，把訪問頂點的操作改為將當前訪問的頂點入棧；相應地，若從某一頂點出發搜尋完再回溯，則做退棧操作，同時要求找到的迴路的路徑應大於2。另外還設定乙個found，出值為0，當找到迴路後為1。
void dfscycle (algrph *g,int v4)
if(!found&&top>0) /*沿原路徑退回後，另選路徑進行搜尋*/
end while*/
if(found)
else printf(「設有通過點v4的迴路！\n」)}
資料結構期末考試題及答案
2012年資料結構期末考試題及答案 一 選擇題 1 在資料結構中，從邏輯上可以把資料結構分為 c a 動態結構和靜態結構 b 緊湊結構和非緊湊結構 c 線性結構和非線性結構 d 內部結構和外部結構 2 資料結構在計算機記憶體中的表示是指 a a 資料的儲存結構 b 資料結構 c 資料的邏輯結構 d ...
資料結構》期末考試試卷 含答案
一 選擇題 每小題2分，共24分 1 計算機識別 儲存和加工處理的物件被統稱為 a a.資料b.資料元素 c.資料結構d.資料型別 2 棧和佇列都是 a a 限制訪問位置的線性結構b 順序儲存的線性結構 c 鏈式儲存的線性結構d 限制訪問位置的非線性結構 3 鏈棧與順序棧相比，比較明顯的優點是 d ...
資料結構2019級期末考試 A
2010級夜大資料結構期末考試試題 a卷 姓名學號序號 成績 注意事項 本試卷滿分100分，考試時間120分鐘 一.單項選擇題，每題有乙個正確選擇。每題2分，共20分 1.下列資料結構中是線性結構。a二叉樹 b 樹 c佇列 d 圖 2.以下關於演算法的說法不正確的是 a 乙個演算法應包含有限個步驟 ...