資料結構試題及答案

資料結構考試你來答課程測試試題（1卷）

一、單選題（每題 2 分，共20分）

1. 對乙個演算法的評價，不包括如下（）方面的內容。

a．健壯性和可讀性 b．並行性 c．正確性 d．時空複雜度

2. 在帶有頭結點的單鏈表hl中，要向表頭插入乙個由指標p指向的結點，則執行( )。

a. p->next=hl->next; hl->next=p; b. p->next=hl; hl=p;

c. p->next=hl; p=hld. hl=p; p->next=hl;

3. 對線性表，在下列哪種情況下應當採用鍊錶表示？( )

a.經常需要隨機地訪問元素b.經常需要進行插入和刪除操作

c.表中元素需要佔據一片連續的儲存空間 d.表中元素的個數不變

4. 乙個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( )

a. 2 3 1b. 3 2 1

c. 3 1 2d. 1 2 3

5. aov網是一種（）。

a．有向圖 b．無向圖 c．無向無環圖 d．有向無環圖

6. 採用開放定址法處理雜湊表的衝突時，其平均查詢長度（）。

a．低於鏈結法處理衝突 b. 高於鏈結法處理衝突

c．與鏈結法處理衝突相同 d．高於二分查詢

7. 若需要利用形參直接訪問實參時，應將形參變數說明為（）引數。

a．值 b．函式 c．指標d．引用

8. 在稀疏矩陣的帶行指標向量的鏈結儲存中，每個單鏈表中的結點都具有相同的（）。

a．行號 b．列號 c．元素值 d．非零元素個數

9. 快速排序在最壞情況下的時間複雜度為（）。

a．o(log2n) b．o(nlog2n) c．0(nd．0(n2)

10. 從二叉搜尋樹中查詢乙個元素時，其時間複雜度大致為( )。

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

二、運算題（每題 6 分，共24分）

1. 資料結構是指資料及其相互之間的當結點之間存在m對n（m：n）的聯絡時，稱這種結構為

2. 佇列的插入操作是在佇列的_________進行，刪除操作是在佇列的進行。

3. 當用長度為n的陣列順序儲存乙個棧時，假定用top==n表示棧空，則表示棧滿的條件是

4. 對於乙個長度為n的單鏈儲存的線性表，在表頭插入元素的時間複雜度為在表尾插入元素的時間複雜度為

5. 設w為乙個二維陣列，其每個資料元素占用4個位元組，行下標i從0到7 ，列下標j從0到3 ，則二維陣列w的資料元素共占用＿_____＿個位元組。w中第6 行的元素和第4 列的元素共占用＿_______＿個位元組。

若按行順序存放二維陣列w，其起始位址為100，則二維陣列元素w[6，3]的起始位址為

6. 廣義表a= (a,(a,b),((a,b),c)),則它的深度為它的長度為

7. 二叉樹是指度為2的樹。一棵結點數為n的二叉樹，其所有結點的度的總和是

8. 對一棵二叉搜尋樹進行中序遍歷時，得到的結點序列是乙個對一棵由算術表示式組成的二叉語法樹進行後序遍歷得到的結點序列是該算術表示式的

9. 對於一棵具有n個結點的二叉樹，用二叉鍊錶儲存時，其指標總數為個，其中個用於指向孩子個指標是空閒的。

10. 若對一棵完全二叉樹從0開始進行結點的編號，並按此編號把它順序儲存到一維陣列a中，即編號為0的結點儲存到a[0]中。其餘類推，則a[ i ]元素的左孩子元素為________,右孩子元素為雙親元素為

11. **性表的雜湊儲存中，處理衝突的常用方法有和兩種。

12. 當待排序的記錄數較大，排序碼較隨機且對穩定性不作要求時，宜採用排序；當待排序的記錄數較大，儲存空間允許且要求排序是穩定時，宜採用排序。

三、運算題（每題6分，共24分）

1.已知乙個65稀疏矩陣如下所示，

試：（1）（1）寫出它的三元組線性表；

（2）（2）給出三元組線性表的順序儲存表示。

2.設有乙個輸入資料的序列是 , 試畫出從空樹起，逐個輸入各個資料而生成的二叉搜尋樹。

3. 對於圖6所示的有向圖若儲存它採用鄰接表，並且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈結的，試寫出：

(1) 從頂點①出發進行深度優先搜尋所得到的深度優先生成樹；

(2) 從頂點②出發進行廣度優先搜尋所得到的廣度優先生成樹；

4.已知乙個圖的頂點集v和邊集e分別為：

v=;e=;若儲存它採用鄰接表，並且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈結的，按主教材中介紹的拓樸排序演算法進行排序，試給出得到的拓樸排序的序列。

四、閱讀演算法（每題7分，共14分）

1. int prime(int n)

(1) 指出該演算法的功能；

(2) 該演算法的時間複雜度是多少？

2. 寫出下述演算法的功能：

void aj(adjlist gl, int i, int n)

五、演算法填空（共8分）

如下為二分查詢的非遞迴演算法，試將其填寫完整。

int binsch(elemtype a[ ],int n,keytype k)

return -1; //查詢失敗，返回-1

}六、編寫演算法（共8分）

hl是單鏈表的頭指標，試寫出刪除頭結點的演算法。

elemtype delefront(lnode * & hl)

課程測試試題（1卷）參***

一、單選題（每題2分，共20分）

1.b 2.a 3.b 4.c 5.d 6.b 7.d 8.a 9.d 10.c

二、填空題（每空1分，共26分）

1. 聯絡圖（或圖結構）

2. 尾首

3. top==0

4. o（1） o（n）

5. 128 44 108

6. 3 3

7. 有序 n-1

8. 有序序列字尾表示式（或逆波蘭式）

資料結構試題及答案

資料結構試題及答案

資料結構試題及答案

資料結構試題及答案

相關推薦