2023年奧鵬西交數(shù)據(jù)結(jié)構(gòu)作業(yè)考核試題

西交2023《數(shù)據(jù)結(jié)構(gòu)》作業(yè)考核試題

一、單選題（共3。道試題，共60分。）

1.設(shè)某哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有（）個(gè)葉子結(jié)點(diǎn)。

A.99

［對(duì)的］B.100

C.101

D.102

滿分：2分

2.字符串的長(zhǎng)度是指（）

A.串中不同字符的個(gè)數(shù)

B.串中不同字母的個(gè)數(shù)

［對(duì)的］C.串中所含字符的個(gè)數(shù)

D.串中不同數(shù)字的個(gè)數(shù)

滿分：2分

3.設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖相應(yīng)的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。

A.n-1

［對(duì)的］B.n

C.n+1

D.2n-l

滿分：2分

4.設(shè)順序線性表的長(zhǎng)度為30,提成5塊，每塊6個(gè)元素，假如采用分塊查找,則其平均查找長(zhǎng)度為（）。

A.6

B.11

C.5

［對(duì)的］D.6.5

滿分:2分

5.在一棵具有5層的滿二叉樹(shù)中結(jié)點(diǎn)數(shù)為()

［對(duì)的］A.31

B.32

C.33

D.16

滿分:2分

6.下面關(guān)于線性表的敘述錯(cuò)誤的是0。

A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間

B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間

C.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)

［對(duì)的］D.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)

滿分:2分

7.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則該無(wú)向圖中所有頂點(diǎn)的入度之和為()。

A.n

B.e

C.2n

［對(duì)的］D.2e

滿分:2分

8.設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為8,則最多通過(guò)()趟插入排序可以得到有序序列。

A.6

［對(duì)的］B.7

C.8

D.9

滿分：2分

9.設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)

的編號(hào)為()。

A.2i+1

［對(duì)的］B.2i

C.i/2

D.2i-1

滿分：2分

10.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為()。

A.top=top-Fl;

B.top=top-1;

C.top->next=top;

［對(duì)的］D.top=top->next;

滿分：2分

11.二叉排序樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均()根結(jié)點(diǎn)的值。

［對(duì)的］A.<

B.>

C.=

D.!=

滿分:2分

12.假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表達(dá)，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度

是()

A.O(n)

B.0(e)

［對(duì)的］C.O(n+e)

D.O(n*e)

滿分:2分

13.在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為()

A.e

B.2e

C.n2-e

［對(duì)的］D.n2-2e

滿分：2分

14.()二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。

A.先序遍歷

［對(duì)的］B.中序遍歷

C.后序遍歷

D.層次遍歷

滿分：2分

15.設(shè)用鄰接矩陣A表達(dá)有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為0。

A.第i行非0元素的個(gè)數(shù)之和

［對(duì)的］B.第i列非0元素的個(gè)數(shù)之和

C.第i行0元素的個(gè)數(shù)之和

D.第i列0元素的個(gè)數(shù)之和

滿分:2分

16.設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)()個(gè)元素。

［對(duì)的］A.n-i

B.n+l-i

C.n-1—i

D.i

滿分:2分

17.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊,則建立該圖鄰接表的時(shí)間復(fù)雜度為().

［對(duì)的］A.O(n+e)

B.0(n)

C.0(ne)

D.0(n)

滿分:2分

18.設(shè)一棵完全二叉樹(shù)中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為().

A.8

［對(duì)的］B.7

C.6

D.5

滿分：2分

19.建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為()

A.0(n)

B.0(1)

［對(duì)的］C.0(n)

D.O(log2n)

滿分：2分

20.下列各種排序算法中平均時(shí)間復(fù)雜度為05)是()。

A.快速排序

B.堆排序

C.歸并排序

［對(duì)的］D.冒泡排序

滿分：2分

21.設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表達(dá)為A=(D,R),D={01,02,03,04,05,06,07,08,09),R

=(r),r=(<0l,02>,<01,03〉,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>),

則數(shù)據(jù)結(jié)構(gòu)A是()。

A.線性結(jié)構(gòu)

［對(duì)的］B.樹(shù)型結(jié)構(gòu)

C.物理結(jié)構(gòu)

D.圖型結(jié)構(gòu)

滿分：2分

22.設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是0。

A.head=0

B.head—>next==0

［對(duì)的］C.head->next==head

D.head!=0

滿分：2分

23.如下陳述中對(duì)的的是0

［對(duì)的］A.串是一種特殊的線性表

B.串的長(zhǎng)度必須大于零

C.串中元素只能是字母

D.空串就是空白串

滿分：2分

24.不定長(zhǎng)文獻(xiàn)是指()

A.文獻(xiàn)的長(zhǎng)度不固定

［對(duì)的］B.記錄的長(zhǎng)度不固定

C.字段的長(zhǎng)度不固定

D.關(guān)鍵字項(xiàng)的長(zhǎng)度不固定

滿分：2分

25.設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20,15,14,18,21,36,40,10),則以20為基準(zhǔn)記錄的一趟快速排

序結(jié)束后的結(jié)果為()。

［對(duì)的］A.10,15,14,18,20,36,40,21

B.10,15.14,I8,20,40,36,21

C.10,15,14,20,18,40,36,21

D.15,10,14,18,20,36,40,21

滿分：2分

26.設(shè)某散列表的長(zhǎng)度為100,散列函數(shù)H()=k%P,則P通常情況下最佳選擇()。

A.99

［對(duì)的］B.97

C.91

D.93

滿分：2分

27.對(duì)于線性表(7,34,55,25,64,46,20,10)進(jìn)行散列存儲(chǔ)時(shí),若選用H()=K%9作為散列函數(shù)，

則散列地址為1的元素有()個(gè)

A.1

B.2

C.3

［對(duì)的］D.4

滿分：2分

28.設(shè)輸入序列1、2、3、？、n通過(guò)棧作用后，輸出序列中的第一個(gè)元素是n,則輸出序列中的第i個(gè)輸

出元素是()。

A.n-i

B.n-1-i

［對(duì)的］C.n+1-i

D.不能擬定

滿分：2分

29.下列存儲(chǔ)形式中，()不是樹(shù)的存儲(chǔ)形式

A.雙親表達(dá)法

B.左子女右兄弟表達(dá)法

C.廣義表表達(dá)法

［對(duì)的］D.順序表達(dá)法

滿分：2分

30.棧的插入和刪除操作在0進(jìn)行。

［對(duì)的］A.棧頂

B.棧底

C.任意位置

D.指定位置

滿分:2分

二、判斷題（共20道試題，共40分。）

1.由樹(shù)轉(zhuǎn)化成二叉樹(shù)，該二叉樹(shù)的右子樹(shù)不一定為空。

［對(duì)的］A.錯(cuò)誤

B.對(duì)的

滿分：2分

2.對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分：2分

3.通常使用兩個(gè)類(lèi)來(lái)協(xié)同表達(dá)單鏈表，即鏈表的結(jié)點(diǎn)類(lèi)和鏈表類(lèi)。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分：2分

4.假如某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分：2分

5.當(dāng)向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分:2分

6.中序遍歷一棵二叉排序樹(shù)可以得到一個(gè)有序的序列。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分：2分

7.非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分：2分

8.先序遍歷一棵二叉排序樹(shù)得到的結(jié)點(diǎn)序列不一定是有序的序列。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分：2分

9.若一個(gè)葉子結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的先序遍歷序列中的最

后一個(gè)結(jié)點(diǎn)。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分:2分

10.不管是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分：2分

1I.子串“ABC”在主串“AABCABCD”中的位置為2。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分:2分

12.設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為0(1og2n)?

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分：2分

13.哈夫曼樹(shù)中沒(méi)有度數(shù)為1的結(jié)點(diǎn)。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分:2分

14.子串“ABC”在主串“AABCABCD”中的位置為3。

［對(duì)的］A.錯(cuò)誤

B.對(duì)的

滿分：2分

15.線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。

［對(duì)的］A.錯(cuò)誤

B.對(duì)的

滿分:2分

16.稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表達(dá)稀疏矩陣中的非0元素。

A.錯(cuò)誤

［對(duì)的］B.對(duì)的

滿分:2分

17.希爾排序算法的時(shí)間復(fù)雜度為O(n)?

［對(duì)的］A.錯(cuò)