福師《數(shù)據(jù)結(jié)構(gòu)概論》在線作業(yè)一答案

試卷總分:100測(cè)試時(shí)間:-

一、單選題（共25道試題，共50分。）

1.最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear,隊(duì)頭是front,則隊(duì)空的條件是（）

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear—1）MODn=front

滿分：2分

2.由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的有向樹？（）

A.2

B.3

C.4

D.5

滿分：2分

3.棧和隊(duì)都是（）

A.順序存儲(chǔ)的

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

C.鏈?zhǔn)酱鎯?chǔ)的

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

滿分：2分

4.下面敘述對(duì)的的是（）

A.算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)

B.算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)

C.算法的有窮性是指算法必須能在執(zhí)行有限個(gè)環(huán)節(jié)之后終止

D.以上三種描述都不對(duì)

滿分：2分

5.對(duì)關(guān)鍵碼序列28,16,32,12,60,2,5,72快速排序，從小到大一次劃分結(jié)果為()。

A.(2,5,12,16)26(60,32,72)

B.(5,16,2,12)28(60,32,72)

C.(2,l6,12,5)28(60,32,72)

D.(5,16,2,12)28(32,60,72)

滿分:2分

6.設(shè)計(jì)一個(gè)判別表達(dá)式中左,右括號(hào)是否配對(duì)出現(xiàn)的算法，采用()數(shù)據(jù)結(jié)構(gòu)最佳。

A.線性表的順序存儲(chǔ)結(jié)構(gòu)

B.隊(duì)列

C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

D.棧

滿分：2分

7.若串S='software'淇子串的數(shù)目是()。

A.8

B.37

C.36

D.9

滿分：2分

8.若用冒泡排序方法對(duì)序列｛10,14,26,29,41,52｝從大到小排序，需進(jìn)行()次比

較。

A.3

B.10

C.15

D.25

滿分：2分

9.若規(guī)定盡也許快地對(duì)序列進(jìn)行穩(wěn)定的排序，則應(yīng)選()

A.快速排序

B.歸并排序

C.冒泡排序

D.堆

滿分：2分

10.假如規(guī)定一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的規(guī)定，則可采用()查找法。

A.分快查找

B.順序查找

C.折半查找

D.基于屬性

滿分：2分

11.廣義表運(yùn)算式Tail(((a,b),(c,d)))的操作結(jié)果是()

A.(c,d)

B.c,d

C.((c,d))

D.d

滿分：2分

12.在下面的排序方法中，輔助空間為O(n)的是()

A.希爾排序

B.堆排序

C.選擇排序

D.歸并排序

滿分：2分

13.以下數(shù)據(jù)結(jié)構(gòu)中()是非線性數(shù)據(jù)結(jié)構(gòu)

A.樹

B.字符串

C.隊(duì)

D.棧

滿分:2分

14.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)

間復(fù)雜度()(1<=i<=n+1)。

A.0(0)

B.0(1)

C.0(n)

D.0(n2)

滿分：2分

15.設(shè)樹T的度為4,其中度為1,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1則T中的葉子

數(shù)為()

A.5

B.6

C.7

D.8

滿分：2分

16.散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以()取其值域的每個(gè)值。

A.最大約率

B.最小概率

C.平均概率

D.同等概率

滿分：2分

17.在下面的排序方法中，輔助空間為0(n)的是()

A.希爾排序

B.堆排序

C.選擇排序

D.歸并排序

滿分：2分

18.設(shè)森林F相應(yīng)的二叉樹為B,它有m個(gè)結(jié)點(diǎn)，B的根為p,P的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,

森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是()

A.m-n

B.m-n-1

C.n+1

D.條件局限性，無法擬定

滿分：2分

19.求解最短途徑的F1oyd算法的時(shí)間復(fù)雜度為()。

A.0(n)

B.O(n+c)

C.0(n*n)

D.O(n*n*n)

滿分：2分

20.下列排序算法中，占用輔助空間最多的是:()

A.歸并排序

B.快速排序

C.希爾排序

D.堆排序

滿分：2分

21.若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要互換其所有分支結(jié)點(diǎn)左、右子樹的位置，運(yùn)用()

遍歷方法最合適。

A.前序

B.中序

C.后序

D.按層次

滿分：2分

22.輸入序列為ABC,可以變?yōu)镃BA時(shí)?，通過的棧操作為（）

A.push,pop,push,pop,push,pop

B.push,push,push,pop,pop,pop

C.push,push,pop,pop,push,pop

D.push,pop,push,push,pop,pop

滿分:2分

23.設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有（）條邊。

A.n-1

B.n（n—1）/2

C.n（n+l）/2

D.0

滿分：2分

24.要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（）條邊。

A.n-1

B.n

C.n+1

D.2n

滿分：2分

25.具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度（）

A.3.1

B.4

C.2.5

D.5

滿分：2分

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

1.二叉樹是度為2的有序樹（）

A.錯(cuò)誤

B.對(duì)的

滿分：2分

2.集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。

A.錯(cuò)誤

B.對(duì)的

滿分：2分

3.隊(duì)列邏輯上是一個(gè)下端和上端既能增長(zhǎng)又能減少的線性表（）。

A.錯(cuò)誤

B.對(duì)的

滿分：2分

4.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。

A.錯(cuò)誤

B.對(duì)的

滿分:2分

5.采用二叉鏈表作存儲(chǔ)結(jié)構(gòu)，樹的前序遍歷和其相應(yīng)的二叉樹的前序遍歷的結(jié)果是同樣的

A.錯(cuò)誤

B.對(duì)的

滿分：2分

6.二叉樹的遍歷結(jié)果不是唯一的（）

A.錯(cuò)誤

B.對(duì)的

滿分：2分

7.線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的（）

A.錯(cuò)誤

B.對(duì)的

滿分：2分

8.隊(duì)列邏輯上是一個(gè)下端和上端既能增長(zhǎng)又能減少的線性表。

A.錯(cuò)誤

B.對(duì)的

滿分：2分

9.線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。

A.錯(cuò)誤

B.對(duì)的

滿分：2分

10.任一查找樹（二叉分類樹）的平均查找時(shí)間都小于用順序查找法查找同樣結(jié)點(diǎn)的線性

表的平均查找時(shí)間（）

A.錯(cuò)誤

B.對(duì)的

滿分：2分

11.排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法可以終止

A.錯(cuò)誤

B.對(duì)的

滿分：2分

12.對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)（）。

A.錯(cuò)誤

B.對(duì)的

滿分：2分

13.用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。

A.錯(cuò)誤

B.對(duì)的

滿分:2分

14.順序查找法合用于存儲(chǔ)結(jié)構(gòu)為順序或鏈接存儲(chǔ)的線性表（）

A.錯(cuò)誤

B.對(duì)的

滿分：2分

15.當(dāng)待排序的元素很大時(shí)，為了互換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響

時(shí)間復(fù)雜度的重要因素

A.錯(cuò)誤

B.對(duì)的

滿分：2分

16.在執(zhí)行某個(gè)排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動(dòng)，則該

算法是不穩(wěn)定的。

A.錯(cuò)誤

B.對(duì)的

滿分：2分

17.廣義表中的元素或者是一個(gè)不可分割的原子,或者是一個(gè)非空的廣義表。

A.錯(cuò)誤

B.對(duì)的

滿分:2分

18.二叉樹以后序遍歷序列與前序遍歷序列反映的同樣的信息（他們反映的信息不獨(dú)立）

()

A.錯(cuò)誤

B.對(duì)的

滿分:2分

19.對(duì)一棵二叉樹進(jìn)行層次遍歷時(shí)，應(yīng)借助于一個(gè)棧

A.錯(cuò)誤

B.對(duì)的

滿分：2分

20.當(dāng)待排序記錄己經(jīng)從小到大排序或者已經(jīng)從大到小排序時(shí),快速排序的執(zhí)行時(shí)間最省。

A.錯(cuò)誤

B.對(duì)的

滿分：2分

三、多選題（共5道試題，共10分。）

1.有關(guān)二叉樹下列說法不對(duì)的的是（）

A.二叉樹的度為2

B.一棵二叉樹的度可以小于2

C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2

D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2

滿分：2分

2.下面關(guān)于求關(guān)鍵途徑的說法對(duì)的的是（）。

A.求關(guān)鍵途徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的

B..一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同

C.一個(gè)事件的最遲開始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開始時(shí)間與該活動(dòng)的連續(xù)時(shí)間

的差

D.關(guān)鍵活動(dòng)一定位于關(guān)鍵途徑上

滿分：2分

3.下面關(guān)于二分查找的敘述不對(duì)的的是（）

A.表必須有序，表可以順序方式存儲(chǔ),也可以鏈表方式存儲(chǔ)

B.表必須有序，并且只能從小到大排列

C.表必須有序且表中數(shù)據(jù)必須是