第一章緒論
一．選擇題
1．資料結構被形式地定義為（k，r），其中k是①_b_的有限集合，r是k上的②_d_的有限集合。
①a．演算法 b．資料元素 c．資料操作 d．邏輯結構 ②a．操作 b．映象 c．儲存 d．關係
2．演算法分析的目的是①c，演算法分析的兩個主要方面是②a。
①a．找出資料結構的合理性
b．研究演算法中的輸入和輸出的關係
c．分析演算法的效率以求改進
d．分析演算法的易懂性和文件性
②a．空間複雜性和時間複雜性
b．正確性和簡明性
c．可讀性和文件性
d．資料複雜性和程式複雜性
3． 在計算機儲存器內表示時，實體地址和邏輯位址相同並且是連續的，稱之為
(b)a．邏輯結構 b．順序儲存結構
c．鍊錶儲存結構 d．以上都不對
4．資料結構中，在邏輯上可以把資料結構分成：( c ）。
a．動態結構和靜態結構 b．緊湊結構和非緊湊結構
c．線性結構和非線性結構 d．內部結構和外部結構
5．以下屬於順序儲存結構優點的是（ a ）。
a．儲存密度大 b．插入運算方便
c．刪除運算方便 d．可方便地用於各種邏輯結構的儲存表示
6．資料結構研究的內容是（ d ）。
a．資料的邏輯結構 b．資料的儲存結構
c．建立在相應邏輯結構和儲存結構上的演算法 d．包括以上三個方面
7．鏈式儲存的儲存結構所佔儲存空間（a ）。
a．分兩部分，一部分存放結點值，另一部分存放表示結點間關係的指標
b．只有一部分，存放結點值
c．只有一部分，儲存表示結點間關係的指標
d．分兩部分，一部分存放結點值，另一部分存放結點所佔單元數
8．乙個正確的演算法應該具有 5 個特性，除輸入、輸出特性外，另外 3 個特性是（ a ）。
a．確定性、可行性、有窮性 b．易讀性、確定性、有效性
c．有窮性、穩定性、確定性 d．可行性、易讀性、有窮性
9．以下關於資料的邏輯結構的敘述中正確的是（ a）。
a．資料的邏輯結構是資料間關係的描述
b．資料的邏輯結構反映了資料在計算機中的儲存方式
c．資料的邏輯結構分為順序結構和鏈式結構
d．資料的邏輯結構分為靜態結構和動態結構
10．演算法分析的主要任務是（ c ）。
a．**演算法的正確性和可讀性 b．**資料組織方式的合理性
c．為給定問題尋找一種效能良好的解決方案 d．研究資料之間的邏輯關係
二．解答
設有一資料的邏輯結構為：b=(d, s)，其中：
d=s=畫出這個邏輯結構示意圖。
第二章線性表
一、選擇題
1．下述哪一條是順序儲存結構的優點？（ a）
a．儲存密度大 b．插入運算方便 c．刪除運算方便 d．可方便地用於各種邏輯結構的儲存表示
2．下面關於線性表的敘述中，錯誤的是哪乙個？（ b）
a．線性表採用順序儲存，必須占用一片連續的儲存單元。
b．線性表採用順序儲存，便於進行插入和刪除操作。
c．線性表採用鏈結儲存，不必占用一片連續的儲存單元。
d．線性表採用鏈結儲存，便於插入和刪除操作。
3．若某線性表最常用的操作是訪問任一指定序號的元素和在最後進行插入和刪除運算，則利用（a ）儲存方式最節省時間。
a．順序表 b．雙鏈表 c．帶頭結點的雙迴圈鍊錶 d．單迴圈鍊錶
4．某線性表中最常用的操作是在最後乙個元素之後插入乙個元素和刪除第乙個元素，則採用（ d）儲存方式最節省運算時間。
a．單鏈表 b．僅有頭指標的單迴圈鍊錶 c．雙鏈表 d．僅有尾指標的單迴圈鍊錶
5．在乙個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動（a）個元素
a．n-i b．n-i+l c．n-i-1 d．i
6．從乙個具有n個結點的單鏈表中查詢其值等於x的結點時，在查詢成功的情況下，需平均比較（c）個元素結點
a．n/2 b．n c．（n+1）/2 d．（n-1）/2
7．設單鏈表中指標p指向結點m，若要刪除m之後的結點（若存在），則需修改指標的操作為（a）
a．p->next=p->next->next; b．p=p->next;
c．p=p->next->next; d．p->next=p;
8．在乙個單鏈表中，已知q結點是p結點的前趨結點，若在q和p之間插入s結點，則須執行（b）
a．s->next=p->next; p->next=s
b．q->next=s; s->next=p
c．p->next=s->next; s->next=p
d．p->next=s; s->next=q
9．線性表的順序儲存結構是一種（a）的儲存結構。
a．隨機訪問 b．順序訪問 c．索引訪問 d．雜湊訪問
二、填空
1．**性表的順序儲存中，元素之間的邏輯關係是通過性表的鏈結儲存中，元素之間的邏輯關係是通過指標決定的。
2．在雙向鍊錶中，每個結點含有兩個指標域，乙個指向直接前驅結點，另乙個指向直接後繼結點。
3．當對乙個線性表經常進行訪問操作，而很少進行插入和刪除操作時，則採用_順序儲存結構為宜。相反，當經常進行的是插入和刪除操作時，則採用鏈式儲存結構為宜。
三、演算法設計
1．設有乙個正整數序列組成的有序單鏈表（按遞增次序有序，且允許有相等的整數存在），試編寫能實現下列功能的演算法（要求用最少的時間和最小的空間）
①確定在序列中比正整數x大的數有幾個（相同的數隻計算一次）
②將單鏈表中比正整數x小的偶數從單鏈表中刪除
int count(linklist h,int x)
return num;
void delevenl(linklist &h,int x)
else
2．設有乙個表頭指標為h的單鏈表。試設計乙個演算法，通過遍歷一趟鍊錶，將鍊錶中所有結點的鏈結方向逆轉，如下圖所示。要求逆轉結果鍊錶的表頭指標h指向原鍊錶的最後乙個結點。
2．void converse(linklist &h)
p->next=h;
h=p;
pλ 3．設計演算法將乙個帶頭結點的單鏈表a分解為兩個具有相同結構的鍊錶b、c，其中b表的結點為a表中值小於零的結點，而c表的結點為a表中值大於零的結點（鍊錶a的元素型別為整型，要求b、c表利用a表的結點）。
3．void decompose(linklist la,linklist &lb,linklist &lc)
} else p=la;
4. 假設鍊錶a、b分別表示乙個集合，試設計演算法以判斷集合a是否是集合b的子集，若是，則返回1，否則返回0，並分析演算法的時間複雜度。
4．int subset(linklist la, linklist lb)
return 1;
}演算法時間複雜度o（
5．設有一單迴圈鍊錶la，其結點有三個域：prior、data與next，其中data為資料域,，next域指向直接後繼，prior域應指向直接前驅，但目前空著。試寫一演算法將此單迴圈鍊錶改造為雙向迴圈鍊錶。
5．void priorset(dulinklist &la)
q->prior=p;
第三章棧和佇列
一、選擇題
1．已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行,則可能出現的出棧序列為（ c）
a.5，4，3，2，1，6 b.2，3，5，6，1，4
c.3，2，5，4，1，6 d.1，4，6，5，2，3
設有乙個棧，元素的進棧次序為a, b, c, d, e,下列是不可能的出棧序列（c ）
a．a, b, c, d, e b．b, c, d, e, a
c．e, a, b, c, d d．e, d, c, b, a
2．在乙個具有n個單元的順序棧中，假定以位址低端（即0單元）作為棧底，以top作為棧頂指標，當做出棧處理時，top變化為（c ）
a．top不變 b．top=0 c．top-- d．top++
資料結構習題庫
知識點 01 緒論 02 順序表 03 鍊錶 04 棧 05 鏈佇列 06 迴圈佇列 07 串 08 陣列的順序表示 09 稀疏矩陣 10 廣義表 11 二叉樹的基本概念 12 二叉樹遍歷 二叉樹性質 13 樹 樹與二叉樹的轉換 14 赫夫曼樹 15 圖的定義 圖的儲存 16 圖的遍歷 17 圖的生...
演算法與資料結構
演算法 是按部就班地解決某個問題的方法，是對特定問題求解步驟的一種描述。偽碼語言是一種包括高階程式語言的3種基本控制結構 順序 選擇和迴圈 和自然語言成分的 物件導向 的語言。演算法的特徵 1 可行性 一是演算法中的每個步驟必須是能實現的 二是演算法執行的結果要能達到預期的目的。2 確定性 演算法的...
資料結構與演算法
課程設計報告 目錄一 問題描述1 二 資料結構1 三 演算法設計思想及流程圖1 四 源程式2 五 測試情況6 參考文獻6 一 問題描述 計算表示式的值 問題描述 對於給定的乙個表示式，表示式中可以包括常數 算術執行符和括號，編寫程式計算表示式的值。基本要求 從鍵盤輸入乙個正確的中綴表示式，將中綴表示...