2023年數(shù)據(jù)結(jié)構(gòu)概論在線作業(yè)與答案

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

試卷總分:100測試時間:-

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

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

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear—1）MODn=front

滿分：2分

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

A.2

B.3

C.4

D.5

滿分：2分

3.棧和隊都是（）

A.順序存儲的

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

C.鏈?zhǔn)酱鎯Φ?/p>

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

滿分：2分

4.下面敘述對的的是（）

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

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

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

D.以上三種描述都不對

滿分：2分

5.對關(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è)計一個判別表達式中左,右括號是否配對出現(xiàn)的算法，采用()數(shù)據(jù)結(jié)構(gòu)最佳。

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

B.隊列

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

D.棧

滿分：2分

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

A.8

B.37

C.36

D.9

滿分：2分

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

較。

A.3

B.10

C.15

D.25

滿分：2分

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

A.快速排序

B.歸并排序

C.冒泡排序

D.堆

滿分：2分

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

A.分快查找

B.順序查找

C.折半查找

D.基于屬性

滿分：2分

11.廣義表運算式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.隊

D.棧

滿分:2分

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

間復(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é)點個數(shù)分別為4,2,1,1則T中的葉子

數(shù)為()

A.5

B.6

C.7

D.8

滿分：2分

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

A.最大約率

B.最小概率

C.平均概率

D.同等概率

滿分：2分

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

A.希爾排序

B.堆排序

C.選擇排序

D.歸并排序

滿分：2分

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

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

A.m-n

B.m-n-1

C.n+1

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

滿分：2分

19.求解最短途徑的F1oyd算法的時間復(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.若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要互換其所有分支結(jié)點左、右子樹的位置，運用()

遍歷方法最合適。

A.前序

B.中序

C.后序

D.按層次

滿分：2分

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

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è)無向圖的頂點個數(shù)為n,則該圖最多有（）條邊。

A.n-1

B.n（n—1）/2

C.n（n+l）/2

D.0

滿分：2分

24.要連通具有n個頂點的有向圖，至少需要（）條邊。

A.n-1

B.n

C.n+1

D.2n

滿分：2分

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

A.3.1

B.4

C.2.5

D.5

滿分：2分

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

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

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分：2分

3.隊列邏輯上是一個下端和上端既能增長又能減少的線性表（）。

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分:2分

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

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分：2分

8.隊列邏輯上是一個下端和上端既能增長又能減少的線性表。

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分：2分

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

表的平均查找時間（）

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分:2分

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

A.錯誤

B.對的

滿分：2分

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

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

A.錯誤

B.對的

滿分：2分

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

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

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分:2分

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

()

A.錯誤

B.對的

滿分:2分

19.對一棵二叉樹進行層次遍歷時，應(yīng)借助于一個棧

A.錯誤

B.對的

滿分：2分

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

A.錯誤

B.對的

滿分：2分

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

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

A.二叉樹的度為2

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

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

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

滿分：2分

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

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

B..一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同

C.一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的連續(xù)時間

的差

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

滿分：2分

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

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

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

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