數(shù)據(jù)結(jié)構(gòu)與算法智慧樹(shù)知到答案章節(jié)測(cè)試2023年長(zhǎng)安大學(xué)

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

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

B:數(shù)據(jù)對(duì)象

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

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

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

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

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

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

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

答案:C計(jì)算算法的時(shí)間復(fù)雜度是屬于一種（）。

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

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

C:事前分析估算的方法

D:事后分析估算的方法

答案:C算法的時(shí)間復(fù)雜度主要取決于（）。

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

B:問(wèn)題的規(guī)模

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

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

答案:Bintsuanfa(intn){inti=1,s=1;while(s＜n)s+=++I;returni;}上面算法的時(shí)間復(fù)雜度是O()。（）

A:對(duì)

B:錯(cuò)

答案:A第二章測(cè)試線性表L=(a1,a2,……,an)，下列說(shuō)法正確的是（）。

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

B:線性表中至少要有一個(gè)元素

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

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

答案:A在長(zhǎng)度為n的順序表中刪除第i(1≤i≤n)個(gè)元素時(shí)，需向前移動(dòng)（）個(gè)元素。

A:n-i

B:n-i+1

C:n

D:i-1

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

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

B:單鏈表

C:雙鏈表

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

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

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

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

C:p=p-＞next;

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

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

A:在最后一個(gè)元素的后面插入一個(gè)新元素

B:順序輸出前k個(gè)元素

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

D:刪除指定元素

答案:D第三章測(cè)試棧是（）。

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

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

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

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

答案:D一個(gè)棧的輸入序列為：a，b，c，d，e，則棧的不可能輸出的序列是（）。

A:d,e,c,b,a

B:a,b,c,d,e

C:e,d,c,b,a

D:d,c,e,a,b

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

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

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

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

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

C:front=front-＞next;

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

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

A:隊(duì)列

B:堆棧

C:數(shù)組

D:線性表

答案:A第四章測(cè)試與線性表相比，串的插入和刪除操作的特點(diǎn)是（）。

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

B:涉及移動(dòng)的元素更多

C:通常以串整體作為操作對(duì)象

D:需要更多的輔助空間

答案:C設(shè)串長(zhǎng)為n，模式串長(zhǎng)為m，則KMP算法所需的附加空間為（）。

A:O(m*n)

B:O(nlog2m)

C:O(n)

D:O(m)

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

A:1180

B:1210

C:1175

D:1205

答案:C對(duì)一些特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了（）。

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

B:減少不必要的存儲(chǔ)空間的開(kāi)銷

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

D:對(duì)矩陣元素的存取變得簡(jiǎn)單

答案:B稀疏矩陣的三元組存儲(chǔ)方法（）。

A:比十字鏈表法更高效

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

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

D:是一種鏈?zhǔn)酱鎯?chǔ)方法

答案:B第五章測(cè)試設(shè)一棵二叉樹(shù)的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹(shù)先序遍歷序列為（）。

A:adbce

B:abcde

C:debac

D:decab

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

A:對(duì)

B:錯(cuò)

答案:A在下列情況中，可稱為二叉樹(shù)的是（）。

A:哈夫曼樹(shù)

B:每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的有序樹(shù)

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

D:每個(gè)結(jié)點(diǎn)只有一棵子樹(shù)

答案:A樹(shù)的先根序列等同于與該樹(shù)對(duì)應(yīng)的二叉樹(shù)的（）。

A:層序序列

B:先序序列

C:后序序列

D:中序序列

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

A:51

B:74

C:53

D:23

答案:A第六章測(cè)試已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)（）。

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

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

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

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

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

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

B:最小生成樹(shù)算法

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

D:最短路徑算法

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

A:對(duì)

B:錯(cuò)

答案:A任何一個(gè)無(wú)向連通網(wǎng)的最小生成樹(shù)（）。

A:只有一棵

B:可能不存在

C:有一棵或多棵

D:一定有多棵

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

A:錯(cuò)

B:對(duì)

答案:B第七章測(cè)試折半查找有序表（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

答案:B鏈表適用于（）查找

A:隨機(jī)

B:順序

C:順序，也能二分法

D:二分法

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

A:對(duì)

B:錯(cuò)

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

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

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

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

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

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

A:一定都不是同義詞

B:不一定都是同義詞

C:必然有序

D:一定是同義詞

答案:B第八章測(cè)試快速排序在下列哪種情況下最易發(fā)揮其長(zhǎng)處（）。

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

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

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

D:被排序的數(shù)據(jù)完全無(wú)序

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

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

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

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

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

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

A:快速排序

B:折半插入排序

C:歸并排序

D:直接插入排序

答案:D