人生難得幾回搏，此時不搏更待何時？

"數據結構"期末考試試題

一、單選題(每小題2分

共12分)

1．在一個單鏈表HL中

若要向表頭插入一個由指針p指向的結點

則執行( )

A． HL＝ps p一>next＝HL

B． p一>next＝HL；HL＝p3

C． p一>next＝Hl；p＝HL；

D． p一>next＝HL一>next;HL一>next＝p；

2．n個頂點的強連通圖中至少含有( )

A.n-l條有向邊 B.n條有向邊

C.n(n-1)／2條有向邊 D.n(n一1)條有向邊

3.從一棵二叉搜索樹中查找一個元素時

其時間復雜度大致為( )

A.O(1) B.O(n)

C.O(1Ogzn) D.O(n2)

4．由權值分別為3

8

6

2

5的葉子結點生成一棵哈夫曼樹

它的帶權路徑長度為( )

A．24 B．48

C． 72 D． 53

5．當一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時

應最好把它說明為( )參數

以節省參數值的傳輸時間和存儲參數的空間

A.整形 B.引用型

C.指針型 D.常值引用型·

6．向一個長度為n的順序表中插人一個新元素的平均時間復雜度為( )

A．O(n) B．O(1)

C．O(n2) D．O(10g2n)

二、填空題(每空1分

共28分)

1．數據的存儲結構被分為--、--、--和--四種

2．在廣義表的存儲結構中

單元素結點與表元素結點有一個域對應不同

各自分別為--域和--域

3．--中綴表達式 3十x*(2.4／5-6)所對應的后綴表達式為----

4．在一棵高度為h的3叉樹中

最多含有--結點

5．假定一棵二叉樹的結點數為18

則它的最小深度為--

最大深度為--·

6．在一棵二叉搜索樹中

每個分支結點的左子樹上所有結點的值一定--該結點的值

右子樹上所有結點的值一定--該結點的值

7．當向一個小根堆插入一個具有最小值的元素時

該元素需要逐層--調整

直到被調整到--位置為止

8．表示圖的三種存儲結構為--、--和---

9．對用鄰接矩陣表示的具有n個頂點和e條邊的圖進行任一種遍歷時

其時間復雜度為--

對用鄰接表表示的圖進行任一種遍歷時

其時間復雜度為--

10．從有序表(12

18

30

43

56

78

82

95)中依次二分查找43和56元素時

其查找長度分別為--和--·

11．假定對長度n＝144的線性表進行索引順序查找

并假定每個子表的長度均為

則進行索引順序查找的平均查找長度為--

時間復雜度為--·

12．一棵B-樹中的所有葉子結點均處在--上

13．每次從無序表中順序取出一個元素

把這插入到有序表中的適當位置

此種排序方法叫做--排序；每次從無序表中挑選出一個最小或最大元素

把它交換到有序表的一端

此種排序方法叫做--排序

14．快速排序在乎均情況下的時間復雜度為--

最壞情況下的時間復雜度為--

三、運算題(每小題6分

共24分)

1．假定一棵二叉樹廣義表表示為a(b(c

d)

c(((

8)))

分別寫出對它進行先序、中序、后序和后序遍歷的結果

先序：

中序；

后序：

2．已知一個帶權圖的頂點集V和邊集G分別為：

V＝{0

1

2

3

4

5}；

E={(0

1)8

(0

2)5

(0

3)2

(1

5)6

(2

3)25

(2

4)13

(3

5)9

(4

5)10}

則求出該圖的最小生成樹的權

最小生成樹的權；

3．假定一組記錄的排序碼為(46

79

56

38

40

84

50

42)

則利用堆排序方法建立的初始堆為--

4．有7個帶權結點

其權值分別為3

7

8

2

6

10

14

試以它們為葉子結點生成一棵哈夫曼樹

求出該樹的帶權路徑長度、高度、雙分支結點數

帶權路徑長度：-- 高度：-- 雙分支結點數：--

四、閱讀算法

回答問題(每小題8分

共16分)

1．VOldAC(List&L)

{

InitList(L)；

InsertRear(L;25)；

InsertFront(L

50)；

IntaL4]＝{5

8

12

15

36};

for(inti＝0; i<5; i++)

if (a[i]

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的c语言边序列构造邻接表,结构C语言版期末考试考试(有答案).doc的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。