【期末複習記錄】資料結構（更新到查找）

目錄

一、緒論

二、線性表 

三、棧和隊列

四、矩陣、串

五、樹和二叉樹

六、圖

七、查找

八、排序

一、緒論

算法五大特性：

有窮性 确定性 可行性 輸入 輸出

好的算法應滿足：

正确性 可讀性 健壯性 效率與低存儲需求 

時間複雜度取決于：

問題的規模  待處理資料的初态 

線性結構元素間存在 一對一 關系

樹形結構元素間存在 一對多 關系

圖形結構元素間存在 多對多 關系

資料結構三要素：

資料元素  邏輯結構  存儲結構 

鍊式結構相比于順序結構主要優點是：

插入、删除、合并等操作較友善

算法分析的目的 —— 分析算法的效率以求改進 

1、順序存儲方式隻能用于存儲線性結構。   （F) 

順序存儲方式不僅能用于存儲線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬于非線性結構，但其最佳存儲方式是順序存儲方式。

2、在一個長度為n的順序表中，删除第i個元素(1≤i≤n)時需要移動（ A ）個元素。

A.n-i

B.n-i+1

C.n-i-1

D.i

代值法  假設長度為3的表 删除第二個元素 也就是需要移動最後一個元素 就是1

則n-i=3-2=1 是以答案是A 

二、線性表 

1、一個線性表的第一個元素位址是100，每個元素長度為2，則第5個元素位址（B）

A.110   B.108   C.100   D.120

（5-1）×2+100=108

2、向一個127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（C）個元素

A.64   B.63   C.63.5   D.7 

在表頭插入元素 移動127個元素

……

在表尾插入元素 移動0個元素

（127+126+……+1+0）/ 128=63.5

3、線性表可以是空表

4、 語句p=p->next完成了指針指派并使p指針得到了p指針所指後繼結點的資料域值 （F）

不是資料域值是指針域 

5、順序表中邏輯相鄰的元素實體位置（一定）相鄰，單連結清單中邏輯上相鄰的元素實體位置（不一定）相鄰。  

6、線性表L=(a1, a2, ... , an)用數組表示，假定删除表中任一進制素的機率相同，則删除一個元素平均需要移動元素的個數是 （n-1）/ 2

 删除第一個元素需要移動n-1

……

删除最後一個元素需要移動0

（n-1+0）×n/2×1/n=（n-1）/2

7、對于一個具有n(n≥1)個結點的單連結清單，插入一個尾結點的時間複雜度是 O(n)

8、在結點個數大于1的循環單連結清單中，指針p指向其中某個結點，當執行以下程式段後讓指針s指向結點p的前驅結點，請填空。

s = p;

while(s->next!=p)   s=s->next; 

9、等機率情況下，在表長為n的順序表中插入一個元素所需移動的元素平均個數為（n/2） 

插入第一個位置 移動n個元素

……

插入最後一個位置 移動0個元素

（n+0）×（n+1）/ 2 × 1 / n+1 =n/2 

10、在一個長度為n的順序表中，向第i個元素(1≤i≤n+1)位置插入一個新元素時需要從後向前移動多少個元素  n-i+1

假設n=2 在第1個元素前插入 已知需要移動2個 代值法得 n-i+1 

11、已知頭指針 

h

 指向一個帶頭結點的非空單循環連結清單，結點結構為 

data | next

，其中 

next

 是指向直接後繼結點的指針，

p

 是尾指針，

q

 是臨時指針。現要删除該連結清單的第一個元素，正确的語句序列是：  D

A.

h->next=h->next->next; q=h->next; free(q);

B.

q=h->next; h->next=h->next->next; free(q);

C.

q=h->next; h->next=q->next; if (p!=q) p=h; free(q);

D.

q=h->next; h->next=q->next; if (p==q) p=h; free(q);

12、在雙連結清單中，将 s 所指新結點插入到 p 所指結點之後，其語句應該為 ▁▁C▁▁ 。

A.p->next = s; s->prev = p; s->next = p->next; p->next->prev = s;

B.s->next = p->next; s->prev = p; p->next = s; p->next->prev = s;

C.s->next = p->next; p->next->prev = s; p->next = s; s->prev = p;

D.p->next = s; s->prev = p; p->next->prev = s; s->next = p->next;

三、棧和隊列

1、表達式a*(b+c)-d的字尾表達式

2、遞歸函數轉換為非遞歸函數時，通常借助（ 棧 ）資料結構

3、棧在（ D ）中有所應用

A.遞歸調用

B.函數調用

C.表達式求值

D.前三個選項都有

4、循環隊列的引入，目的是為了克服 假溢出問題

5、設循環隊列的元素存放在一維數組Q［0..29］（下标為0到29）中，隊列非空時，front訓示隊頭元素位置，rear訓示隊尾元素的後一個位置。如果隊列中元素的個數為11，front的值為25，則rear的值是（ 6 ） 

 (Q.rear-Q.front+MAXSIZE)%MAXSIZE=隊列長度

（x-25+30）%30 = 11 ，即x-25+30=11 ，則x=6.

6、棧是（ C ）。

A.順序存儲的線性結構

B.鍊式存儲的非線性結構

C.限制存取點的線性結構

D.限制存儲點的非線性結構

7、下列關于棧的叙述中，錯誤的是：        C

1. 采用非遞歸方式重寫遞歸程式時必須使用棧
2. 函數調用時，系統要用棧儲存必要的資訊
3. 隻要确定了入棧次序，即可确定出棧次序
4. 棧是一種受限的線性表，允許在其兩端進行操作

A.僅 1

B.僅 1、2、3

C.僅 1、3、4

D.僅 2、3、4

I. 尾遞歸可以直接使用循環

8、若用大小為6的數組來實作循環隊列，且目前front和rear的值分别為0和4。當從隊列中删除三個元素，再加入三個元素後，front和rear的值分别為多少？  B

A.3和5

B.3和1

C.3和3

D.3和6

四、矩陣、串

1、矩陣壓縮存儲的對象包括 對稱矩陣  稀疏矩陣  上下三角矩陣

五、樹和二叉樹

1、二叉樹按某種順序線索化後，任一結點均有指向其前驅和後繼的線索  （F）

第一個結點無前驅，最後一個結點無後繼，另外，對于線索二叉樹，左子樹存在，則lchild指向左子樹，否則指向前驅，右子樹存在，則rchild指向右子樹，否則指向後繼。 

2、設高度為h的二叉樹上隻有度為0和度為2的結點,則此類二叉樹中所包含的結點數至少為（ B）。

（A）2h （B）2h-1（C）2h+1（D）h+1

隻有度為0和2兩種情況,即每個結點要麼沒有子節點,要麼有兩個子節點(概念)。

除了根節點,每層至少兩個結點,共h層,應有2(h-1)+1(除根節點外每層都有2個,最後加上1個根節點),化簡得2h-1個,選B

3、如果T2是由有序樹T轉換而來的二叉樹,那麼T中結點的前序就是T2中結點的（ A ）

（A）前序（B）中序（C）後序（D）層次序

4、二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法（ B ）

（A）正确（B）錯誤（C）不同情況下答案不确定

 二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大于其左子樹的值、小于其右子樹的值。

 5、任意一棵二叉樹的葉結點在先序、中序和後序周遊中的相對次序（ A ）

（A）不發生改變（B）發生改變（C）不能确定（D）以上都不對

前中後序周遊改變的是根的通路順序 不是葉結點的通路順序

6、對一個滿二叉樹,m個樹葉,n個結點,深度為h,則（ D ）

（A）n=h+m （B）h+m=2n（C）m=h-1（D）n=2^h-1

7、 具有5層結點的二叉平衡樹至少（ 12 ）個結點

8、一棵含有n個結點的k叉樹，可能達到的最大深度和最小深度各是多少？ 

最大深度為n個節點的單支樹,深度為n;

最小深度為完全k叉樹。 

9、如果含有n個頂點的圖形成一個環,則它有( n )棵生成樹。

n個頂點成環有n條邊 任意删除一條邊都能生成1棵生成樹 是以能生成n棵生成樹  

10、對一棵二叉排序樹采用 中序周遊 可以得到升序序列

六、圖

1、采用鄰接表存儲圖的深度優先周遊算法類似于二叉樹的先序周遊

因為圖的深度優先周遊算法先通路所在結點，再通路它的鄰接點。與二叉樹的先序周遊先通路子樹的根結點，再通路它的孩子結點（鄰接點）類似

2、采用鄰接表存儲圖的廣度優先周遊算法類似于二叉樹的按層周遊 

3、判定一個有向圖是否存在回路除了可以利用拓撲排序方法外,還可以利用（ D ）.

（A）求關鍵路徑的方法（B）求最短路徑的Dijkstm方法

（C）橫向優先搜尋算法（D）深度優先周遊算法

4、如果從一無向圖的任意頂點出發進行一次深度優先搜尋即可通路所有頂點，則該圖一定是

強連通圖

5、任何一個無向連通網的最小生成樹( A )。

A 有一棵或多棵

B 隻有1棵

C 一定有多棵

D 可能不存在

無向連通圖肯定有最小生成樹

6、下面正确的說法是( BCD )。

A 任何一個關鍵活動提前完成,将使整個工程提前完成

B 關鍵活動不按期完成就會影響整個工程的完成時間

C 所有關鍵活動都提前完成,則整個工程提前完成

D 某些關鍵活動若提前完成,将使整個工程提前完成

7、任何一個有向圖都一定存在拓撲序列。  F

任何一個有向無環圖都至少有一個拓撲序列

8、求稀疏圖的最小生成樹,用克魯斯卡爾算法來求解較好。  T

克魯斯卡爾算法适合邊少的，也即稀疏圖

9、關鍵路徑上的活動都是關鍵活動,它們是否按時完成會影響工期  T

10、稠密圖采用鄰接矩陣存儲較省空間  T 

稠密圖——鄰接矩陣   稀疏圖——鄰接表

11、若一個無向圖的以頂點V1為起點進行深度優先周遊,所得的周遊序列唯一,則可以唯一确定該圖。   T

12、有向圖的鄰接表，每個頂點的邊連結清單中的結點數等于該頂點的（  ）

A、度數     B、入度     C、出度     D、邊數

13、借助排序可以判斷工程能否順利開展，進行求解可以計算工程所需的最短工期，最短工期等于從源點到彙點的最長路徑長度

七、查找

1、有一個長度為12的有序表,按二分查找法對該表進行查找,在表内各元素等機率情況下查找成功所需的平均比較次數為（ B ）

（A）35/12（B）37/12（C）39/12（D）43/12

八、排序

1、在所有排序方法中，關鍵字比較的次數與記錄得初始排列次序無關的是（ D ）

（A）希爾排序 （B）起泡排序 （C）插入排序 （D）選擇排序