數(shù)據(jù)結(jié)構(gòu)智慧樹知到課后章節(jié)答案2023年下山東建筑大學(xué)

數(shù)據(jù)結(jié)構(gòu)智慧樹知到課后章節(jié)答案2023年下山東建筑大學(xué)山東建筑大學(xué)

第一章測試

方法f1的時間復(fù)雜度是（）

publicintf1(intn){

intx=0;

while(n>=(x+1)*(x+1)){

x=x+1;

}

returnx;

}

A:O(logn)B:O(n)C:O(n2)D:O(n1/2)

答案:O(n1/2)

方法f2的時間復(fù)雜度是（）

publicintf2(intn){

inti=0;

intsum=0;

while(sum<n){

sum+=++i;

}

returni;

}

A:O(nlogn)B:O(n1/2)C:O(logn)D:O(n)

答案:O(n1/2)

方法f3的時間復(fù)雜度是（）

publicintf3(intn){

intx=2;

while(x<n/2){

x=2*x;

}

returnx;

}

A:O(n2)B:O(nlogn)C:O(logn)D:O(n)

答案:O(logn)

方法f4的時間復(fù)雜度是（）

publicintf4(intn){

intcount=0;

for(intk=1;k<=n;k*=2){

for(intj=1;j<=n;j++){

count++;

}

}

returncount;

}

A:O(n2)B:O(logn)C:O(nlogn)D:O(n)

答案:O(nlogn)

記問題的規(guī)模n=a.length，方法f5的時間復(fù)雜度是（）

publicvoidf5(int[]a,intx){

intj=a.length;

for(inti=0;i<a.length;i++){

if(x>a[i]){

j=i;

break;

}

}

for(inti=a.length;i>j;i--){

a[i]=a[i-1];

}

a[j]=x;

}

A:O(n2)B:O(n)C:O(nlogn)D:O(logn)

答案:O(n)

第二章測試

數(shù)據(jù)對象是指（）

A:相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合B:數(shù)據(jù)的基本單位C:性質(zhì)相同的數(shù)據(jù)元素的集合D:描述客觀事物且由計(jì)算機(jī)處理的數(shù)值、字符等符號的總稱

答案:性質(zhì)相同的數(shù)據(jù)元素的集合

數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容涉及（）

A:數(shù)據(jù)如何存儲B:數(shù)據(jù)的運(yùn)算如何實(shí)現(xiàn)C:算法用什么語言描述D:數(shù)據(jù)如何組織

答案:數(shù)據(jù)如何存儲;數(shù)據(jù)的運(yùn)算如何實(shí)現(xiàn);數(shù)據(jù)如何組織

數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（）

A:對B:錯

答案:對

數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)的表示和數(shù)據(jù)之間關(guān)系的表示。（）

A:錯B:對

答案:對

如果使用Java語言描述，鏈?zhǔn)酱鎯κ抢靡米兞縼肀硎緮?shù)據(jù)之間的關(guān)系。（）

A:對B:錯

答案:對

第三章測試

以下不是順序表特點(diǎn)的是（）。

A:插入和刪除操作需要移動數(shù)據(jù)元素B:便于隨機(jī)存取C:儲密度高D:無需預(yù)分配空間

答案:無需預(yù)分配空間

刪除順序表（共有n個數(shù)據(jù)元素）中第i（0≤i≤n-1）個數(shù)據(jù)元素時需要移動（）個數(shù)據(jù)元素。

A:iB:n-iC:n-i-1D:n-i+1

答案:n-i-1

在線性表中若經(jīng)常要存取第i個數(shù)據(jù)元素及其前驅(qū)，則宜采用（）存儲方式。

A:循環(huán)單鏈表B:不帶頭結(jié)點(diǎn)的單鏈表C:順序表D:帶頭結(jié)點(diǎn)的單鏈表

答案:順序表

在一個有序單鏈表（含有n個結(jié)點(diǎn)）中插入一個新結(jié)點(diǎn)，使單鏈表仍然保持有序的算法的時間復(fù)雜度是（）。

A:O（1）B:O（n）C:O（n2）D:O（log2n）

答案:O（n）

在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中的p結(jié)點(diǎn)之后插入一個新結(jié)點(diǎn)s，其修改鏈的Java語句序列是（）

A:p.next=s;s.prior=p;p.next.prior=s;s.next=p.prior;B:s.prior=p;s.next=p.next;p.next=s;p.next.prior=s;C:p.next=s;p.next.prior=s;s.prior=p;s.next=p.next;D:s.next=p.next;s.prior=p;p.next.prior=s;p.next=s;

答案:s.next=p.next;s.prior=p;p.next.prior=s;p.next=s;

第四章測試

有六個元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪一個不是合法的出棧序列？（）。

A:453126B:234156C:543612D:346521

答案:346521

若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（）。

A:i-jB:i-j-1C:不確定D:j-i+1

答案:不確定

若已知一個棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是（）。

A:不確定B:iC:n-iD:n-i+1

答案:不確定

設(shè)有三個元素X，Y，Z順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到的出棧排列是（）。

A:XYZB:YZXC:ZYXD:ZXY

答案:ZXY

遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。

A:棧B:線性表C:多維數(shù)組D:隊(duì)列

答案:棧

第五章測試

用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時（）。

A:頭、尾指針可能都要修改B:僅修改尾指針C:頭、尾指針都要修改D:僅修改頭指針

答案:頭、尾指針可能都要修改

用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時,其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時（）。

A:隊(duì)頭、隊(duì)尾指針都可能要修改B:隊(duì)頭、隊(duì)尾指針都要修改C:僅修改隊(duì)頭指針D:僅修改隊(duì)尾指針

答案:隊(duì)頭、隊(duì)尾指針都可能要修改

棧與隊(duì)列是一種特殊操作的線性表。（）

A:錯B:對

答案:對

隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（）

A:錯B:對

答案:錯

通常使用隊(duì)列來處理函數(shù)或過程的調(diào)用。（）

A:錯B:對

答案:錯

第六章測試

在有n個結(jié)點(diǎn)的二叉樹的二叉鏈表存儲結(jié)構(gòu)中有（）個空的指針域。

A:n+1B:n-1C:nD:0

答案:n+1

若某棵二叉樹的先根遍歷序列為ABCDEF,中根遍歷序列為CBDAEF,則這棵二叉樹的后根遍歷序列為（）。

A:CDBEFAB:FEDCBAC:CDBFEAD:DCBEFA

答案:CDBFEA

具有10個葉結(jié)點(diǎn)的二叉樹中有度為2的結(jié)點(diǎn)有（）個

A:11B:10C:8D:9

答案:9

一個具有1025個結(jié)點(diǎn)的二叉樹的深度為（）

A:11至1025之間B:11C:10至1024之間D:10

答案:11至1025之間

利用二叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是（）。

A:非空B:空C:指向最右孩子D:指向最左孩子

答案:空

第七章測試

對有n個頂點(diǎn)，e條邊且使用鄰接表存儲的有向圖進(jìn)行廣度優(yōu)先搜索，其算法時間復(fù)雜度是（）

A:O(n×e)B:O(n+e)C:O(e)D:O(n).

答案:O(n+e)

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

A:n(n+1)/2B:n–1C:n(n-1)/2D:n2

答案:n(n-1)/2

使用鄰接表存儲圖所用的空間大?。ǎ?/p>

A:與邊數(shù)的平方有關(guān)B:只與圖的邊數(shù)有關(guān)C:只與圖的頂點(diǎn)數(shù)有關(guān)D:與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)

答案:與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)

用鄰接表存儲圖時，拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度是（）

A:O(n+e)B:O(n2)C:O(n)D:O(n×e)

答案:O(n+e)

為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了需要一個數(shù)組標(biāo)志已經(jīng)訪問過的結(jié)點(diǎn)外，還需要隊(duì)列。（）

A:錯B:對

答案:對

第八章測試

已知一個長度為16的順序表L，其元素按關(guān)鍵字有序排列。若采用二分查找法查找一個L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多是（）。

A:4B:7C:6D:5

答案:5

二分查找從100個有序整數(shù)中查找某數(shù)，最壞情況下需要比較的次數(shù)是（）。

A:7B:10C:99D:50

答案:7

若二叉搜索樹是有N個結(jié)點(diǎn)的完全二叉樹，則不正確的說法是（）。

A:中位值結(jié)點(diǎn)在根結(jié)點(diǎn)或根的左子樹上B:最小值一定在葉結(jié)點(diǎn)上C:最大值一定在葉結(jié)點(diǎn)上D:所有結(jié)點(diǎn)的平均查找效率是O(logN)

答案:最大值一定在葉結(jié)點(diǎn)上

將{32,2,15,65,28,10}依次插入初始為空的二叉搜索樹。則該樹的前序遍歷結(jié)果是（）。

A:32,2,15,10,28,65B:52,10,15,28,32,65C:32,2,10,15,28,65D:10,28,15,2,65,32

答案:32,2,15,10,28,65

對二叉搜索樹進(jìn)行什么遍歷可以得到從小到大的排序序列？（）。

A:層次遍歷B:中序遍歷C:后序遍歷D:前序遍歷

答案:后序遍歷

第九章測試

從待排序的序列當(dāng)中選出關(guān)鍵字值最大的記錄放到有序序列中，該排序方法稱為（）。

A:快速排序B:直接選擇排序C:希爾排序D:冒泡排序

答案:冒泡排序

當(dāng)待排序序列基本有序時，以下排序序列當(dāng)中最不利于其優(yōu)勢的發(fā)揮（）。

A:直接插入排序B:冒泡排序C:直接選擇排序D:快速排序

答案:快速排序

下面給出的4種排序算法中（）是不穩(wěn)定的排序

A:堆排序B:2路歸并排序C:插入排序D:冒泡排序

答案:堆排序

下列排序方法中，（）所需要的輔助空間最大。

A:選擇排序B:希爾排序C:歸并排序D:快速排序

答案:歸并排序

執(zhí)行排序操作時，根據(jù)使用的存儲器，可將排序算法分為內(nèi)排序和外排序。（）

A:對B:錯

答案:對

若不考慮基數(shù)排序，則在排序過程中主要進(jìn)行的兩種基本操作是比較，移動。（）

A:錯B:對

答案:對

第十章測試

已知8個數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉搜索樹后，最后兩層上的結(jié)點(diǎn)總數(shù)為（）。

A:2B:3C:1D:4

答案:2

最小生成樹是指該樹中（）。

A:所有邊的權(quán)值之和為最小B:帶權(quán)路徑長度之和為最小C:所含結(jié)點(diǎn)個數(shù)最小D:一棵滿二叉樹

答案:所有邊的權(quán)值之和為最小

使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點(diǎn)1到其他各頂點(diǎn)的最短路徑，依次得到的各最短路徑的目標(biāo)頂點(diǎn)是（）。

A:5,2,6,3,4B:5,2,3,6,4C:5,2,3,4,6D:5,2,4,3,6

答案:5,2,3,6,4

用一個有向圖來表示航空公司所有航班的航線。下列哪種算法最適合解決找給定兩城市間最經(jīng)濟(jì)的飛行路線問題？（）。

A:深度優(yōu)先搜索B:Dijkstra算法C:Kruskal算法D:拓?fù)渑判蛩惴?/p>

答案:Dijkstra算法

Dijkstra算法用來解決哪個問題？（）

A:關(guān)鍵路徑B:拓?fù)渑判駽:最短路徑D:字符串匹配

答案:最短路徑

在n個結(jié)點(diǎn)的無向圖中，若邊數(shù)>n-1，則該圖必是連通圖。（）

A:對B:錯

答案:錯

鄰接表法只能用于有向圖的存儲，而鄰接矩陣法對于有向圖和無向圖的存儲都適用。（