數據結構試題答案

一、單項選擇題（每題2分，共30分）

1.若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則採用（  ）存儲方式最節省時間。

A) 單鏈表           B) 雙鏈表          C) 單向循環鏈表     D) 順序表

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

A) 符號構成的序列                      B) 符號構成的集合

C) 字符構成的序列                      D) 字符構成的集合

3.設矩陣A的任一元素aij(1≤i,j≤10)滿足：

aij≠0；(i≥j,1≤i,j≤10)

aij=0； (i<j,1≤i,j≤10)

現將A的所有非0元素以行序為主序存放在首地址為2000的存儲區域中，每個元素佔有4個單元，則元素A[9,5]的首地址為（  ）。

A) 2340             B) 2336            C) 2164              D) 2160

4.如果以鏈表作為棧的存儲結果，則出棧操作時（  ）。

A) 必須判別棧是否為滿                  B) 對棧不作任何判別

C) 必須判別棧是否為空                  D) 判別棧元素的類型

5.設數組Data[0..m]作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針,則執行出隊操作的語句為（  ）。

A) front = front+1                     B) front = (front+1) % m

C) rear = (rear+1) % m                 D) front = (front+1) % (m+1)

6.深度為6(根的層次為1)的二叉樹至多有（  ）結點。

A) 64               B) 32              C) 31                D) 63

7.將含100個結點的完全二叉樹從根這一層開始，每層上從左到右依次堆結點編號，根結點的編號為1。編號為49的結點X的雙親的編號為（  ）。

A) 24               B) 25              C) 23                D) 無法確定

8.設有一個無向圖 和 ，如果 為 的生成樹，則下面不正確的説法是（  ）。

A)  為 的子圖                       B)  為 的連通分量

C)  為 的極小連通子圖且       D)  為 的一個無環子圖

9.用線性探測法查找閉散列表，可能要探測多個散列地址，這些位置上的鍵值（  ）。

A) 一定都是同義詞                      B) 一定都不是同義詞

C) 多相同                               D) 不一定都是同義詞

10.二分查找要求被查找的表是（  ）。

A) 鍵值有序的鏈接表                    B) 鏈接表但鍵值不一定有序

C) 鍵值有序的順序表                    D) 順序表但鍵值不一定有序

11.當初始序列已經按鍵值有序，用直接插入算法對其進行排序，需要循環的次數為（  ）。

A)               B)           C)             D) n－1

12.堆是一個鍵值序列 ,對 ，滿足（  ）。

A)                        B)

C)  且 ( )      D)  或 ( )

13.使用雙向鏈表存儲數據，其優點是可以（  ）。

A) 提高檢索速度                        B) 很方便地插入和刪除數據

C) 節約存儲空間                        D) 很快回收存儲空間

14.設計一個判別表達式中左右括號是否配對出現地算法，採用（  ）數據結構最佳。

A) 線性表地順序存儲結構                B) 棧

C) 隊列                                D) 線性表達的鏈式存儲結構

15.設深度為k的二叉樹上只有度為0和2的結點，則此類二叉樹中所含的結點數至少為（  ）。

A) k + 1            B) 2k              C) 2k - 1             D) 2k + 1

二、填空題（每空2分，共28分）

1.設r指向單鏈表的最後一個結點，要在最後一個結點之後插入s所指的結點，需執行的三條語句是_____________________________________________r=s;r->next=NULL。

2.在單鏈表中，指針p所指結點為最後一個結點的條件是___________________。

3.設一個鏈棧的棧頂指針是ls，棧中結點格式為              ，棧空的條件為_____________。如果棧不為空，則出棧操作為p=ls;______________;free(p)。

4.已知一棵度為3的樹有2個度為1的'結點，3個度為2的結點，4個度為3的結點，則該樹有________個葉子結點。

5.樹有三種常用的存儲結構，即孩子鏈表法，孩子兄弟鏈表法和____________。

6.n個頂點的連通圖的生成樹有__________條邊。

7.一個有向圖G中若有弧 、 和 ，則在圖G的拓撲序列中，頂點 的相對位置為___________。

8.設表中元素的初始狀態是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸併排序方法對其進行排序(按遞增順序)，________最省時間，__________最費時間。

9.下面是將鍵值為x的結點插入到二叉排序樹中的算法，請在劃線處填上適當的內容。

Typedef struct pnode

{ int key;

struct node * left, * right;

}

Void search (int x; pnode t )

{ if (_____________)

{p = malloc (size);

p->key=x;p->left=NULL;

p->right=NULL;

t=p;

}

else

if (xkey) search (x,t->left)

else  _________________

}

10.線性表的____________的主要優點是從表中任意結點出發都能訪問到所有結點。而使用____________，可根據需要在前後兩個方向上方便地進行查找。

三、應用題（每題10分，共30分）

1.在雙鏈表中，要在指針變量P所指結點之後插入一個新結點，請按順序寫出必要的算法步驟。(設：P所指結點不是鏈表的首尾結點，q是與p同類型的指針變量)

2.已知待排序文件各記錄的排序碼順序如下：

72  73  71  23  94  16  05  68

請列出快速排序過程中每一趟的排序結果。

四、算法題(共12分)

編寫算法，實現單鏈表上的逆置運算(説明：即將單鏈表中的元素次序反轉)

參考答案：

一、單項選擇題（每題2分，共30分）

1.D   2.C  3.D   4.C   5.D   6.D   7.A   8.B   9.D   10.C   11.D   12.C  13.A   14.B   15.C

二、填空題（每空2分，共28分）

1. r->next=s;                             2. p->next=NULL;

3. ls = = NULL; ls=ls->link。 4. 12

5. 雙親表示法   6. n-1

7. i,j,k    8. 冒泡排序，快速排序

9. t= =NULL，search（x,t->right）； 10.循環鏈表，雙向鏈表

三、應用題（每題10分，共30分）

1．new(q)；

q↑k ← p；

q↑k ← p↑k；

p↑k↑k ← q；

p↑k ← q。

評分細則：按順序每對一個給2分，全對計10分。

2．各趟結果如下：

[68 05 71 23 16] 72 [94 73]

[16 05 23] 68 [71] 72 [94 73]

[05] 16 [23] 68 [71] 72 [94 73]

05 16 [23] 68 [71] 72 [94 73]

05 16 23 68 71  72 [94 73]

05 16 23 68 71  72 [73] 94

05 16 23 68 71  72  73 94

四．算法題(共12分)

void invert（ pointer head）

{p=NULL;

while ( head<>NULL)

{u=head;

head=head->next;

u->next=p;

p=u;

}

head=p;

}