資料結構整理

第四章串

1 下面關於串的的敘述中，哪個是不正確的？

a．串是字元的有限序列

b．空串是由空格構成的串

c．模式匹配是串的一種重要運算

d．串既可以採用順序儲存，也可以採用鏈式儲存

2串是一種特殊的線性表，下面哪個敘述體現這種特殊性？

a. 資料元素是乙個字元 b. 可以順序儲存

c. 資料元素可以是多個字元 d. 可以鏈結儲存

3 串的長度是指（）

a．串中所含不同字母的個數

b．串中所含字元的個數

c．串中所含不同字元的個數

d．串中所含非空格字元的個數

4空串與空格串是相同的,這種說法__a. 正確 b.不正確

5.設有兩個串p和q,求q在p中首次出現的位置的運算稱作

a.連線 b.模式匹配 c.求子串 d,求串長

6.串是任意有限個（）。

a 符號構成的集合 b 符號構成的序列

c 字元構成的集合 d 字元構成的序列

第五章陣列和廣義表

1已知廣義表l=((x, y, z), a, (u, t, w)), 從l表中取出原子項t的運算是( )。

a head(tail(tail(l))) b head(tail(head(tail(tail(l)))))

c head(tail(head(tail(l)))) d tail(head(head(tail(l))))

解答：tail(l)= (a, (u, t, w))

tail(tail(l))=((u, t, w))

head(tail(tail(l)))=(u, t, w)

tail(head(tail(tail(l))))= ( t, w)

head(tail(head(tail(tail(l))))) =t 所以選b

2將乙個a[1..100, 1..100]的三對角矩陣按行優先存入一維陣列b[1..298]中，a中元素a66, 65在b陣列中的位置為（）

a 198 b 195 c 196 d 197

3 廣義表a=(a, b, (c, d), (e, (f, g)))，則下面式子的值為（） head(tail(head(tail(tail(a)))))

a (g) b (d) c c d d

解答：tail(l)= (b, (c, d), (e, (f, g)))

tail(tail(l))= ((c, d), (e, (f, g)))

head(tail(tail(l)))= (c, d)

tail(head(tail(tail(l))))= (d)

head(tail(head(tail(tail(l))))) =d 選d

4陣列通常只有兩種運算（）和（），這決定了陣列通常採用（）來實現儲存。答案：訪問修改順序結構

5 設二維陣列a[0..8, 1..10]按行優先儲存，每個元素是6個字元組成的串（每個字元佔乙個儲存單元），則存放a至少需要（）個儲存單元；a的第8列和第5行共佔（）個儲存單元。

解答：9×10 ×6 =540 (9+10-1)×6=108

6 ．畫出下列廣義表的圖形表示

（1）a(b,(a,a,c(a)),c(a)) （2）d(a( ),b(e),c(a,l(b,c,d)))

第七章圖

prim演算法

演算法思想：假設 n=(v，|e|) 是連通圖，te是n上最小生成樹中邊的集合。演算法從u=(u0 v)，te={}開始，重複執行下述操作：

在所有u u，v v－u的邊(u, v) 中找一條代價最小的邊(u0, v0)併入集合te，同時v0併入u，直至u=v為止。此時，te中必有n-1條邊，則t=(v，) 為n的最小生成樹。課本174頁圖7.

16 prim

1給出如圖所示的無向圖g的鄰接矩陣和鄰接表兩種儲存結構。

2. 假設圖的頂點是a、b……請根據下面的鄰接矩陣畫出相應的無向圖或有向圖。

3. 分別給出如圖所示g圖的深度優先搜尋和廣度優先搜尋得到的頂點訪問序列。

4. 應用prim演算法求圖所示帶權連通圖的最小生成樹。

5用dag圖描述表示式 ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

6設圖如右所示，在下面的5個序列中，符合深度優先遍歷的序列有多少？（）

a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

a．5個 b．4個 c．3個 d．2個

7 下面哪一方法可以判斷出乙個有向圖是否有環（迴路）：

a深度優先遍歷 b拓撲排序 c求最短路徑 d求關鍵路徑

8在有向圖g的拓撲序列中，若頂點vi在頂點vj之前，則下列情形不可能出現的是（）。

a．g中有弧 b．g中有一條從vi到vj的路徑

c．g中沒有弧 d．g中有一條從vj到vi的路徑

9 下列有關圖的說法錯誤的是（）

a. 在有向圖中，出度為0的結點稱為葉子。

b. 用鄰接矩陣表示圖，容易判斷任意兩個結點之間是否有邊相連，並求得各結點的度。

c. 按深度方向遍歷圖和先根次序遍歷樹類似，得到的結果是唯一的。

d. 若有向圖g中從結點vi到結點vj有一條路徑，則在圖g的結點的線性序列中結點vi必在結點vj之前的話，則稱為乙個拓撲序列。

5. 寫出圖所示有向圖的拓樸排序序列。

第九章查詢

1 從乙個空的二叉排序樹開始,依次插入25, 13, 15, 34, 7, 20, 37. 畫出插入完成後的二叉樹.

除留餘數法

設定雜湊函式為:h(key) = key mod p ( p≤m )

其中， m為表長 p 為不大於 m 的質數或是不含 20 以下的質因子

開放定址法

例表長為11的雜湊表中已填有關鍵字為17，60，29的記錄，h(key)=key mod 11,現有第4個記錄，其關鍵字為38，按三種處理衝突的方法，將它填入表中

(1) h(38)=38 mod 11=5 衝突 h1=(5+1) mod 11=6衝突

h2=(5+2) mod 11=7 衝突 h3=(5+3) mod 11=8不衝突

(2) h(38)=38 mod 11=5衝突h1=(5+1) mod 11=6 衝突

h2=(5-1) mod 11=4不衝突

(3) h(38)=38 mod 11=5衝突設偽隨機數序列為9，則：

h1=(5+9) mod 11=3 不衝突

2給定關鍵字集合構造雜湊表設定雜湊函式 h(key) = key mod 11 ( 表長=11 )

若採用線性探測再雜湊處理衝突

若採用二次探測再雜湊處理衝突

1設有序表為，請分別畫出對給定值f,g和h進行折半查詢的過程。

2.設雜湊表長m=14，雜湊函式為h(k)=k mod 11，表中一共有8個元素，試畫出採用二次探測法處理衝突的雜湊表。

3.線性表的關鍵字集合為，共有13個元素，已知雜湊函式為：h（k）=k mod 13，採用鏈結表處理衝突，試設計這種鍊錶結構。

4. 設關鍵字集合為，雜湊函式為：h（k）=k mod 7，雜湊表長度m=10，起始位址為0，分別用線性探測和鏈結表法來解決衝突。試畫出對應的雜湊表。

第十章排序

最好情況

比較次數為n-1次移動次數為2（n-1）次

最壞情況

比較次數為 =(n+2)(n-1)/2

移動次數為 =(n+4)(n-1)/2

直接插入排序的優缺點

直接插入排序演算法簡單，當待排序記錄數量n很小時，區域性有序時，較為適用。

1當n很大時，其效率不高。

2若對直接插入排序演算法進行改進，可從減少「比較」和「移動」次數這兩方面著手。

3折半存入排序、二路插入排序、表插入排序、希爾排序都是對直接插入排序的改進。

折半插入排序效能分析

減少了比較次數，移動次數不變。

時間複雜度仍為o（n2）。

自測題在對一組記錄（54，38，96，23，15，72，60，45，83）

進行直接排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較多少次

希爾(shell 1959)排序

基本思想：從「減小n」和「基本有序」兩方面改進。

將待排序的記錄劃分成幾組，從而減少參與直接插入排序的資料量，當經過幾次分組排序後，記錄的排列已經基本有序，這個時候再對所有的記錄實施直接插入排序。

自測題請給出對一組記錄（54,38,96,23,15,90,72,60,45,83）

進行希爾排序（增量序列為5，3，1）時的排序過程（參照課本271頁排序過程）。

起泡排序效能分析

平均時間複雜度：o(n2)

快速排序

基本思想：從排序序列中任選一記錄作為樞軸（或支點），凡其關鍵字小於樞軸的記錄均移動至該記錄之前，而關鍵字大於樞軸的記錄均移動至該記錄之後。一趟排序後「樞軸」到位，並將序列分成兩部分，再分別對這兩部分排序。

快速排序的平均時間複雜度為o（nlog2n）最差為o(n2)

補充：線性表

鏈式儲存結構的優缺點

優點：– 儲存空間動態分配，可以按需使用

– 插入、刪除結點操作時通常只需要修改指標，不必移動資料元素

缺點：– 每個結點附加指標域

– 非隨機訪問結構，查詢定位操作需從頭指標出發順著鍊錶掃瞄

線性表實現方法的比較

1實現不同

– 順序表方法簡單，各種高階語言中都有陣列型別，容易實現；鍊錶的操作是基於指標的，相對來講複雜些。

資料結構整理

資料結構整理

資料結構整理

資料結構複習整理

相關推薦