數(shù)據(jù)結(jié)構(gòu)與算法智慧樹知到課后章節(jié)答案2023年下長安大學(xué)

數(shù)據(jù)結(jié)構(gòu)與算法智慧樹知到課后章節(jié)答案2023年下長安大學(xué)長安大學(xué)

第一章測試

以下可以用于定義一個完整的數(shù)據(jù)結(jié)構(gòu)的是（）。

A:數(shù)據(jù)對象

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

C:抽象數(shù)據(jù)類型

D:數(shù)據(jù)關(guān)系

答案:抽象數(shù)據(jù)類型

以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法中，正確的是（）。

A:數(shù)據(jù)的邏輯結(jié)構(gòu)唯一決定了其存儲結(jié)構(gòu)

B:數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于其存儲結(jié)構(gòu)

C:數(shù)據(jù)的存儲結(jié)構(gòu)獨(dú)立于其邏輯結(jié)構(gòu)

D:數(shù)據(jù)結(jié)構(gòu)僅由其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)決定

答案:數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于其存儲結(jié)構(gòu)

計(jì)算算法的時間復(fù)雜度是屬于一種（）。

A:事前統(tǒng)計(jì)的方法

B:事后統(tǒng)計(jì)的方法

C:事前分析估算的方法

D:事后分析估算的方法

答案:事前分析估算的方法

算法的時間復(fù)雜度主要取決于（）。

A:數(shù)據(jù)的類型

B:計(jì)算的環(huán)境

C:問題的規(guī)模

D:待處理數(shù)據(jù)的值

答案:問題的規(guī)模

intsuanfa(intn){

inti=1,s=1;

while(s＜n)s+=++I;

returni;

}

上面算法的時間復(fù)雜度是O()。（）

A:錯B:對

答案:對

第二章測試

線性表L=(a1,a2,……,an)，下列說法正確的是（）。

A:每個元素都有一個直接前驅(qū)和一個直接后繼

B:除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅(qū)和直接后繼

C:表中諸元素的排列順序必須是由小到大或由大到小

D:線性表中至少要有一個元素

答案:除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅(qū)和直接后繼

在長度為n的順序表中刪除第i(1≤i≤n)個元素時，需向前移動（）個元素。

A:n

B:i-1

C:n-i

D:n-i+1

答案:n-i

如果線性表最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運(yùn)算時間。

A:單鏈表

B:僅有尾指針的單循環(huán)鏈表

C:僅有頭指針的單循環(huán)鏈表

D:雙鏈表

答案:僅有尾指針的單循環(huán)鏈表

在一個單鏈表中，若刪除p所指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則所需修改指針的操作為（）。

A:p=p-＞next;p-＞next=p-＞next-＞next;

B:p=p-＞next;

C:p-＞next=p-＞next-＞next;

D:p=p-＞next-＞next;

答案:p-＞next=p-＞next-＞next;

設(shè)線性表有2n個元素，以下操作中，在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn)效率更高的（）。

A:交換第i個元素和第2n-i-1個元素(i=,1,…,n-1)

B:在最后一個元素的后面插入一個新元素

C:刪除指定元素

D:順序輸出前k個元素

答案:刪除指定元素

第三章測試

棧是（）。

A:鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)

B:限制存取點(diǎn)的線性結(jié)構(gòu)

C:限制存取點(diǎn)的非線性結(jié)構(gòu)

D:順序存儲的線性結(jié)構(gòu)

答案:限制存取點(diǎn)的線性結(jié)構(gòu)

一個棧的輸入序列為：a，b，c，d，e，則棧的不可能輸出的序列是（）。

A:a,b,c,d,e

B:d,e,c,b,a

C:d,c,e,a,b

D:e,d,c,b,a

答案:d,c,e,a,b

判斷一個循環(huán)隊(duì)列Q（最多n個元素）為滿的條件是（）。

A:Q-＞rear==Q-＞front

B:Q-＞front==(Q-＞rear-1)%n

C:Q-＞rear==Q-＞front+1

D:Q-＞front==(Q-＞rear+1)%n

答案:Q-＞front==(Q-＞rear+1)%n

在一個鏈隊(duì)列中，front和rear分別為頭指針和尾指針，則插入一個結(jié)點(diǎn)s的操作為（）。

A:s-＞next=front;front=s;

B:front=front-＞next;

C:s-＞next=rear;rear=s;

D:rear-＞next=s;rear=s;

答案:rear-＞next=s;rear=s;

在解決計(jì)算機(jī)主機(jī)和打印機(jī)之間速度不匹配問題時，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個（）結(jié)構(gòu)。

A:堆棧

B:線性表

C:隊(duì)列

D:數(shù)組

答案:隊(duì)列

第四章測試

與線性表相比，串的插入和刪除操作的特點(diǎn)是（）。

A:算法的時間復(fù)雜度較高

B:通常以串整體作為操作對象

C:需要更多的輔助空間

D:涉及移動的元素更多

答案:通常以串整體作為操作對象

設(shè)串長為n，模式串長為m，則KMP算法所需的附加空間為（）。

A:O(m*n)

B:O(m)

C:O(nlog2m)

D:O(n)

答案:O(m)

數(shù)組A[0..5,0..6]的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5][5]的地址是（）。

A:1175

B:1180

C:1210

D:1205

答案:1175

對一些特殊矩陣采用壓縮存儲的目的主要是為了（）。

A:減少不必要的存儲空間的開銷

B:去掉矩陣中的多余元素

C:表達(dá)變得簡單

D:對矩陣元素的存取變得簡單

答案:減少不必要的存儲空間的開銷

稀疏矩陣的三元組存儲方法（）。

A:實(shí)現(xiàn)轉(zhuǎn)置運(yùn)算很簡單，只需將每個三元組的行標(biāo)和列標(biāo)交換

B:比十字鏈表法更高效

C:矩陣的非零元個數(shù)和位置在操作過程中變化不大時較有效

D:是一種鏈?zhǔn)酱鎯Ψ椒?/p>

答案:矩陣的非零元個數(shù)和位置在操作過程中變化不大時較有效

第五章測試

設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為（）。

A:debac

B:adbce

C:abcde

D:decab

答案:abcde

任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序不發(fā)生改變。（）。

A:錯B:對

答案:對

在下列情況中，可稱為二叉樹的是（）。

A:每個結(jié)點(diǎn)只有一棵子樹

B:哈夫曼樹

C:每個結(jié)點(diǎn)至多有兩棵子樹的樹

D:每個結(jié)點(diǎn)至多有兩棵子樹的有序樹

答案:哈夫曼樹

樹的先根序列等同于與該樹對應(yīng)的二叉樹的（）。

A:層序序列

B:中序序列

C:后序序列

D:先序序列

答案:先序序列

由權(quán)值為3，6，7，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。

A:74

B:53

C:51

D:23

答案:51

第六章測試

已知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點(diǎn)發(fā)出的邊，應(yīng)（）。

A:將鄰接矩陣的第i行元素全部置為0

B:將鄰接矩陣的第i行刪除

C:將鄰接矩陣的第i列元素全部置為0

D:將鄰接矩陣的第i列刪除

答案:將鄰接矩陣的第i行元素全部置為0

為便于判別有向圖中是否存在回路，可借助于（）。

A:廣度優(yōu)先搜索算法

B:最小生成樹算法

C:最短路徑算法

D:拓?fù)渑判蛩惴?/p>

答案:拓?fù)渑判蛩惴?/p>

已知一個有向圖的鄰接表存儲結(jié)構(gòu)如圖所示，根據(jù)深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是：v1,v3,v4,v5,v2。（）

A:對B:錯

答案:對

任何一個無向連通網(wǎng)的最小生成樹（）。

A:只有一棵

B:有一棵或多棵

C:一定有多棵

D:可能不存在

答案:有一棵或多棵

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

A:錯B:對

答案:對

第七章測試

折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（）比較大小，查找結(jié)果是失敗。

A:20，50

B:20，70，30，50

C:30，88，70，50

D:30，88，50

答案:20，70，30，50

鏈表適用于（）查找

A:順序，也能二分法

B:二分法

C:隨機(jī)

D:順序

答案:順序

在上圖所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字38所在的結(jié)點(diǎn)左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是24,48。（）

A:對B:錯

答案:對

分別以下列序列構(gòu)造二叉排序樹，與用其他三個序列所構(gòu)造的結(jié)果不同的是（）。

A:(100,80,90,60,120,110,130)

B:(100,80,60,90,120,130,110)

C:(100,120,110,130,80,60,90)

D:(100,60,80,90,120,110,130)

答案:(100,60,80,90,120,110,130)

哈希表構(gòu)建時采用線性探測法處理沖突，在某關(guān)鍵字查找成功的情況下，所探測的多個位置上的關(guān)鍵字（）。

A:一定是同義詞

B:不一定都是同義詞

C:必然有序

D:一定都不是同義詞

答案:不一定都是同義詞

第八章測試

快速排序在下列哪種情況下最易發(fā)揮其長處（）。

A:被排序的數(shù)據(jù)完全無序

B:被排序的數(shù)據(jù)中的最大值和最小值相差懸殊

C:被排序的數(shù)據(jù)已基本有序

D:被排序的數(shù)據(jù)中含有多個相同排序碼

答案:被排序的數(shù)據(jù)完全無序

若一組記錄的排序碼為（46,79,56,38,40,84），則利用堆排序的方法建立的初始堆為（）。

A:84,79,56,38,40,46

B:84,56,79,40,46,38

C:79,46,56,38,40,84

D:84,79,56,46,40,38

答案:84,79,56,38,40,46

希爾排序的組內(nèi)排序采用的是（）。

A:歸并排序

B:折半插入排序

C:快速排序

D:直接插入排序

答案: