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

數(shù)據(jù)結(jié)構(gòu)與算法知到智慧樹章節(jié)測試課后答案2024年秋長安大學(xué)第一章單元測試

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

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

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

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

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

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

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

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

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

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

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

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

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

A:事前分析估算的方法

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

C:事后分析估算的方法

D:事前統(tǒng)計的方法

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

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

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

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

C:問題的規(guī)模

D:計算的環(huán)境

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

intsuanfa(intn){

inti=1,s=1;

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

returni;

}

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

A:對B:錯

答案:對

第二章單元測試

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

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

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

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

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

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

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

A:n-i+1

B:n

C:n-i

D:i-1

答案:n-i

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

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

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

C:單鏈表

D:雙鏈表

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

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

A:p=p-＞next;

B:p-＞next=p-＞next-＞next;

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

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

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

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

A:順序輸出前k個元素

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

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

D:刪除指定元素

答案:刪除指定元素

第三章單元測試

棧是（）。

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

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

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

D:限制存取點的非線性結(jié)構(gòu)

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

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

A:d,e,c,b,a

B:a,b,c,d,e

C:d,c,e,a,b

D:e,d,c,b,a

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

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

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

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

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

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

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

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

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

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

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

D:front=front-＞next;

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

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

A:堆棧

B:隊列

C:線性表

D:數(shù)組

答案:隊列

第四章單元測試

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

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

B:需要更多的輔助空間

C:涉及移動的元素更多

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

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

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

A:O(n)

B:O(m*n)

C:O(nlog2m)

D:O(m)

答案:O(m)

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

A:1205

B:1175

C:1210

D:1180

答案:1175

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

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

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

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

D:表達變得簡單

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

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

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

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

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

D:比十字鏈表法更高效

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

第五章單元測試

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

A:decab

B:abcde

C:debac

D:adbce

答案:abcde

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

A:錯B:對

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

A:哈夫曼樹

B:每個結(jié)點至多有兩棵子樹的樹

C:每個結(jié)點只有一棵子樹

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

答案:哈夫曼樹

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

A:層序序列

B:中序序列

C:先序序列

D:后序序列

答案:先序序列

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

A:51

B:53

C:74

D:23

答案:51

第六章單元測試

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

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

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

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

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

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

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

A:最小生成樹算法

B:最短路徑算法

C:拓撲排序算法

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

答案:拓撲排序算法

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

A:對B:錯

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

A:只有一棵

B:一定有多棵

C:有一棵或多棵

D:可能不存在

答案:有一棵或多棵

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

A:對B:錯

答案:對

第七章單元測試

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

A:30，88，50

B:20，70，30，50

C:20，50

D:30，88，70，50

答案:20，70，30，50

鏈表適用于（）查找

A:順序

B:隨機

C:二分法

D:順序，也能二分法

答案:順序

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

A:對B:錯

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

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

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

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

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,56,79,40,46,38

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

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

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

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

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

A:折半插入排序

B:直接插入排序

C:歸并排序

D:快速排序

答案