資料結構複習題 2019

資料結構期末複習題1（0907）

一、基本要求

1．資料結構基本概念

（1）資料、資料物件和資料結構（邏輯、物理結構、基本操作）

（2）抽象資料型別

（3）演算法的特徵及評價的標準

2．線形結構

（1）順序表的特點及儲存結構

（2）鍊錶的特點及儲存結構

（3）棧的特點及基本操作

（4）佇列的特點及基本操作

（5）順序串和鏈串的儲存結構

（6）二維陣列的位址計算

（7）特殊矩陣的概念及儲存結構（對稱、三角、對角、稀疏）

（8）廣義表的概念及儲存結構

（9）線性表的排序（簡單插入、選擇和交換）

（10）線性表的查詢（順序、折半和分塊索引）

3．樹形結構

（1）二叉樹的性質及儲存結構（順序、二叉鍊錶、三叉鍊錶）

（2）二叉樹的遍歷

（3）線索二叉樹

（4）樹的儲存結構（雙親、孩子-雙親、孩子-兄弟鍊錶）

（5）樹、二叉樹與森林的轉化方法

（6）哈夫曼樹

（7）二叉排序樹及平衡化

（8）堆排序樹

（9）樹的等價類劃分

4．圖形結構

（1）圖的定義及儲存結構

（2）圖的深度優先和廣度優先遍歷。

（3）圖的連通性

（4）最小（代價）生成樹

（5）拓撲排序

（6）關鍵路徑

（7）最短路徑（單源、頂點對）

5．查詢表

（1）雜湊表的概念

（2）雜湊表解決雜湊衝突的方法（開放位址法、鏈位址法）

（3）雜湊表的插入和刪除

（4）b_樹的概念、儲存結構及基本操作（查詢、插入、刪除）

6．排序方法

（1）希爾排序

（2）快速排序

（3）二路歸併排序

（4）基數排序（鏈式、計數）

（5）排序方法比較和分析（時間效能、空間效能、穩定性）

二、單選題

1．要求具有同一邏輯結構的資料元素具有相同的特性，其含義為

a. 資料元素具有同一的特點

b. 資料元素其對應的資料個數及資料項的型別要一致

c. 每個資料元素都一樣

d. 僅需要資料元素包含的資料項的個數相同

2．在乙個單鏈表中，已知*q結點是*p結點的前驅結點，若在*q 和*p之間插入結點*s，則執行操作

a. s->next=p->next;p->next=s;

b. s->next=p;p->next=s

c. q->next=s;s->next=p

d. p->next=s;s->next=q;

3．設指標p指向雙鏈表的某一結點，則雙鏈表結構的對稱性可以用下面的操作來反映

a. p->prior->next=p->next->next;

b. p->prior->prior=p->next->prior;

c. p->prior->next=p-> next->prior;

d. p->next->next= p->prior->prior;

4．表示式a*(b+c)--d的字尾表示式是

a．abcd*+- b．abc+*d-

c．abc*+d- d．-+*abcd

5．設乙個棧的輸入序列為a，b，c，d，則借助乙個棧所得到的輸出序列不可能是

a．a，b，c，d b．d，c，b，a

c. a，c，d，b d. d，a，b，c

6．設有乙個順序棧的入棧序列是a、b、c，則3個元素都出棧的可能不同排列個數為

a．4 b．5 c. 6 d. 7

7．若已知乙個棧的入棧序列是1，2，3，…，n，其輸出序列為pl，p2，p3，…，pn，若pl是n，則 pi是

a．ib．n-i c．n-i+1 d．不確定

8．已知廣義表ls=((a，b，c)，(d，e，f))，運算head和tail函式取出元素e的運算是

a．head(tail(ls

b．tail(head(ls))

c．head(tail(head(tail(ls))))

d．head(tail(tail(head(ls))))

9．二維陣列a的每個元素是由6個字元組成的串，其行下標i=0，l，…，8，列下標為j=1，2．…．10。設每個字元佔乙個位元組,若按行先儲存，元素a[8，5]的起始位址與a按列儲存時起始位址相同的元素是

a．a[8，5] b．a[3，10]

c．a[5，8] d．a[0，9]

10．陣列a[1..5，1..6]的每個元素佔5個單元，將其按行優先次序儲存在起始位址為1000的連續的記憶體單元中，則元素a[5，5]的位址為

a. 1140 b. 1145 c. 1120 d. 1125

11．某二叉樹的先序序列和後序序列正好相反，則該二叉樹的特點一定是

a. 空或只有乙個結點

b. 高度等於其結點數

c. 任一結點無左孩子

d. 任一結點無右孩子

12．下列說法正確的是

(1)二又樹按某種方式線索化後，任一節點均有指向前趨和後繼的線索

(2)二叉樹的前序遍歷序列中，任意乙個節點均處於在子孫節點前

(3)二叉排序樹中任一節點的值大於其左孩子的值，小於右孩子的值

a．(1)(2)(3) b．(1)(2)

c．(1)(3) d．前面的可選答案都不對

13．下面的說法中正確的是

(1)任何一棵二叉樹的葉子節點在三種遍歷中的相對次序不變。

(2)按二叉樹定義，具有三個節點的二叉樹共有6種。

a．(1)，(2) b．(1) c．(2) d．(1)，(2)都錯

14．樹有先根遍歷和後根遍歷，樹可以轉化為對應的二叉樹。下面的說法正確的是

a．樹的後根遍歷與其對應的二叉樹的後根遍歷相同

b．樹的後根遍歷與其對應的二叉樹的中根遍歷相同

c．樹的先根遍歷與其對應的二叉樹的中根遍歷相同

d．以上都不對

15．.下圖的鄰接表中，從頂點v1 出發採用深度優先搜尋法遍歷該圖，則可能的頂點序列是

a. v1v2v3v4v5 b. v1v2v3v5v4

c. v1v4v3v5v2 d. v1v3v4v5v2

16．以下說法不正確的是

a．無向圖中的極大連通子圖稱為連通分量

b．連通圖的廣度優先搜尋中一般要採用佇列來暫存剛訪問過

的頂點c．圖的深度優先搜尋中一般要採用棧來暫存剛訪問過的頂點

d．有向圖的遍歷不可採用廣度優先搜尋

17．在平衡二叉樹中插入乙個結點後引起了不平衡，設最低(最接近於葉子)的不平衡點是a，並已知a的左、右孩子的平衡因子分別為-1和0，則應進行的平衡旋轉是

a．ll型 b．lr型 c．rl型 d．rr型

18．設雜湊表長為14，雜湊函式h(key)=key％11，表中已有資料的關鍵字為15，38，61，84，四個，現將關鍵字為49的結點加到表中，用二次探測再雜湊法解決衝突，則放入的位置是

a．8 b．3 c．5 d．9

19．對雜湊檔案，以下說法錯誤的是

a．雜湊檔案插入、刪除方便，不需要索引區且節省儲存空間

b．雜湊檔案只能按關鍵字隨機訪問且訪問速度快

c．經過多次插入、刪除後，可能出現溢位桶滿的情況

d．雜湊檔案順序訪問方便

20．在平衡二叉樹中插入乙個結點後造成了不平衡，設最低的不平衡結點為a，並已知a的左孩子的平衡因子為0，右孩子的平衡因子為1，則應調整以使其平衡，所作的平衡旋轉是

a. ll型 b. lr型 c. rl型 d. rr型

21．在n個結點且為完全二叉樹的二叉排序樹中查詢乙個鍵值，其平均比較次數的數量級為

a. o(n) b. o(log2n) c. o(nlog2n) d. o(n2)

22．下列排序演算法中，在待排序資料已基本有序時，效率最高的排

序方法是

a．插入 b．選擇 c．快速 d．堆

23．關鍵路徑是事件結點網路中

a．從源點到匯點的最長路徑 b．從源點到匯點的最短路徑

c．最長的迴路d．最短的迴路

24．將兩個各有n個元素的有序表歸併成乙個有序表，其最少的比

較次數是

a．n b．2n-1 c．2n d．n-1

25．下列排序演算法中，時間複雜度不受資料初始狀態影響，恒為

0(nlog2n)的是

a. 堆排序b. 氣泡排序

c. 直接選擇排序 d. 快速排序

26．資料表a中有10000個元素，如果僅要求求出其中最大的10個元素，則採用最節省時間的排序演算法是

a. 堆排序 b. 希爾排序

c. 快速排序 d. 直接選擇排序

27．在分塊索引查詢的索引表中查詢，演算法中採用的技術是

a. 窮舉法 b. 貪心法

c. 分治法 d. 回溯法

28．有向圖g用鄰接矩陣a儲存，則頂點i的入度等於a中

a. 第i行1的元素之和

b. 第i列1的元素之和

c. 第i行0的元素個數

d. 第i列非0的元素個數

三、問答題

1．資料結構被形式地定義為（d,r），其中d和r 的含義是什麼。（d是資料元素的集合，r是資料關係的集合）。資料的邏輯結構包括哪四種型別。

（線性結構、樹形結構、圖形結構、集合型別）。從儲存結構的概念上講，順序表是線性表的（順序儲存結構），鍊錶是（鏈式儲存結構）。

2．演算法的五個重要特性有哪些。（有窮性、確定性、可行性、輸入、輸出）。抽象資料型別是指乙個（數學模型）以及定義在該模型上的（一組操作）。

3．在含有n個結點的順序儲存的線性表中，在任意乙個結點前插入乙個結點所需要移動結點的平均次數為（ n/2 ）。在含有n個結點的順序儲存的線性表中，任意刪除乙個結點所需要移動結點的平均次數為（ n-1/2 ）。對乙個線性表分別進行遍歷和逆置運算，其最好的時間複雜度量級均為（o(n)）。

資料結構複習題 2019

資料結構複習題

資料結構複習題

資料結構複習題

相關推薦