數(shù)據(jù)結(jié)構(gòu)導(dǎo)論年月真題

02142202010

1、【單選題】數(shù)據(jù)的最小標(biāo)識(shí)單位是

數(shù)據(jù)項(xiàng)

數(shù)據(jù)類型

A:

數(shù)據(jù)元素

B:

數(shù)據(jù)變量

C:

答D:案：A

解析：數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。

2、【單選題】下面程序段的時(shí)間復(fù)雜度為for(inti=0;i<n;i++)for(intj=0;j<n;

j++)a[i][j]=i*j;

O(1)

O(n)

A:

O(2n)

B:

O(n2)

C:

答D:案：D

3、【單選題】設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head,則空循環(huán)鏈表的判定條件是

head==NULL

head->next==NULL

A:

head->next==head

B:

head=NULL

C:

答D:案：C

4、【單選題】設(shè)輸入序列為1、2、3、4、5、6,則通過棧的作用后可以得到的輸出序列為

5,3,4,6,1,2

3,2,5,6,4,1

A:

3,1,2,5,4,6

B:

1,5,4,6,2,3

C:

答D:案：B

5、【單選題】隊(duì)列是一種線性表,其具有的特征是

先進(jìn)后出

只能插入

A:

只能刪除

B:

先進(jìn)先出

C:

答D:案：D

解析：隊(duì)列是一種特殊的線性表，是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)。它只允許在表的

前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端

稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。

6、【單選題】設(shè)有一個(gè)10階的下三角矩陣A(包括對(duì)角線,按照從上到下、從左到右的順序

存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中,每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間,則a54地址與a00的地

址之差為

10

19

A:

28

B:

55

C:

答D:案：B

7、【單選題】設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n,則

這棵二叉樹中共有結(jié)點(diǎn)個(gè)數(shù)是

2n

n+1

A:

2n-1

B:

2n+1

C:

答D:案：C

8、【單選題】設(shè)按照從上到下、從左到右的順序從1開始對(duì)完全二叉樹進(jìn)行順序編號(hào),若結(jié)

點(diǎn)i有左孩子,則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為

2i+1

2i

A:

i/2

B:

2i-1

C:

答D:案：B

9、【單選題】已知一棵二叉樹的先序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍

歷的結(jié)果為

CBEFDA

FEDCBA

A:

CBEDFA

B:

CEFBDA

C:

答D:案：A

10、【單選題】一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為

n-1

n2

A:

n(n+1)/2

B:

n(n-1)/2

C:

答D:案：D

11、【單選題】設(shè)某有向圖中有n個(gè)頂點(diǎn),則該有向圖對(duì)應(yīng)的鄰接表中表頭結(jié)點(diǎn)個(gè)數(shù)為

n-1

n

A:

n+1

B:

2n-1

C:

答D:案：B

12、【單選題】若查找每個(gè)記錄的概率均等,則在具有n個(gè)記錄的連續(xù)順序文件中采用順序

查找算法查找一個(gè)記錄,其平均查找長度ASL為

(n-1)/2

n/2

A:

(n+1)/2

B:

n

C:

答D:案：C

13、【單選題】設(shè)散列表中有n個(gè)存儲(chǔ)單元,散列函數(shù)H(key)=key%p,則p最好選擇小于散列

表長度n的

奇數(shù)

素?cái)?shù)

A:

偶數(shù)

B:

合數(shù)

C:

答D:案：B

14、【單選題】下列排序算法中,穩(wěn)定的排序算法是

堆排序

快速排序

A:

直接選擇排序

B:

冒泡排序

C:

答D:案：D

15、【單選題】下列四個(gè)序列中,是堆的序列為

75,45,65,30,15,25,20,10

75,65,45,10,30,25,20,15

A:

75,65,30,15,25,45,20,10

B:

7545,65,10,25,30,20,15

C:

答D:案：A

16、【問答題】題29圖給出了一個(gè)稀疏矩陣A,請寫出該稀疏矩陣的三元組表。

答案：((0.1.5),(2,1.-1),(2.3.7),(3.1.6),(4.4.9)，(5.5.8))

17、【問答題】已知二叉樹如題30圖所示,請將該二叉樹轉(zhuǎn)換為對(duì)應(yīng)的森林。

答案：

18、【問答題】設(shè)某通信系統(tǒng)中一個(gè)待傳輸?shù)奈谋居?個(gè)不同字符,它們的出現(xiàn)頻率分別是

0.5,0.7,1.4,2.2,2.4,2.8,試畫出哈夫曼樹,并給出每個(gè)字符的哈夫曼編碼。(要求任一

結(jié)點(diǎn)的左孩子權(quán)值小于右孩子)

答案：

19、【問答題】選定散列函數(shù)為H(key)=keymod13,試用鏈地址法建立鍵值為

26,41,25,05,07,15,12,49,51,31,62的散列表。

答案：

20、【問答題】對(duì)于給定的一組鍵值:83,40,63,13,84,35,96,57,39,79,61,15,請分別寫出

直接選擇排序和冒泡排序的第一趟排序結(jié)果。

答案：

21、【問答題】寫出一個(gè)將線性表的順序表存儲(chǔ)方式(數(shù)組a、表長為n)改成單鏈表存儲(chǔ)方

式(其頭結(jié)點(diǎn)由頭指針head指向)的算法。設(shè)函數(shù)頭為:Node

*CreatedLinkedList(DataType[],intn)

答案：

22、【問答題】以二叉鏈表作存儲(chǔ)結(jié)構(gòu),請寫出二叉鏈表類型定義;利用二叉樹遍歷的遞歸算

法,試編寫求二叉樹高度的算法。

答案：

23、【填空題】數(shù)據(jù)的四類基本邏輯結(jié)構(gòu)是:線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖結(jié)構(gòu)和____

答案：集合

24、【填空題】數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和____存儲(chǔ)。

答案：散列

25、【填空題】順序表插入算法的時(shí)間復(fù)雜度是____。

答案：O(n)

26、【填空題】設(shè)r指向單鏈表的最后一個(gè)結(jié)點(diǎn),要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn),

需執(zhí)行的語句序列是r->next=s;r=s;____

答案：r->next=NULL

27、【填空題】一般情況下,函數(shù)的嵌套調(diào)用和程序遞歸的處理都是用____來實(shí)現(xiàn)的。

答案：棧

28、【填空題】m行n列的矩陣有t個(gè)非零元素,當(dāng)t滿足____條件時(shí),稱該矩陣為稀疏矩

陣。

答案：t<<m*n

29、【填空題】二叉樹的第i(i≥1)層上至多有____個(gè)結(jié)點(diǎn)。

答案：2i-1

30、【填空題】雙親表示法由一個(gè)一維數(shù)組構(gòu)成,數(shù)組的每個(gè)分量包含兩個(gè)域:____和雙親

域。

答案：數(shù)據(jù)域

31、【填空題】無向圖的鄰接矩陣是一個(gè)____矩陣。

答案：對(duì)稱

32、【填空題】設(shè)有散列函數(shù)H和鍵值k1、k2,若k1≠k2,但是H(k1)=H(k2),則稱這種現(xiàn)象

為____

答案：沖突

3