數(shù)據(jù)結(jié)構(gòu)與算法智慧樹知到課后章節(jié)答案2023年下中國(guó)民用航空飛行學(xué)院

數(shù)據(jù)結(jié)構(gòu)與算法智慧樹知到課后章節(jié)答案2023年下中國(guó)民用航空飛行學(xué)院中國(guó)民用航空飛行學(xué)院

緒論單元測(cè)試

本課程中需要掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。

A:對(duì)B:錯(cuò)

答案:對(duì)

在本課程的學(xué)習(xí)中還需要掌握算法基本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析方法，能夠設(shè)計(jì)出求解問題的高效算法。

A:錯(cuò)B:對(duì)

答案:對(duì)

第一章測(cè)試

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

A:問題的規(guī)模B:執(zhí)行算法的計(jì)算機(jī)性能的高低C:算法的長(zhǎng)短D:待處理數(shù)據(jù)的初態(tài)

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

算法的計(jì)算量的大小稱為算法的（）。

A:難度B:效率C:現(xiàn)實(shí)性D:復(fù)雜度

答案:復(fù)雜度

算法的時(shí)間復(fù)雜度與（）有關(guān)。

A:編譯后執(zhí)行程序的質(zhì)量B:計(jì)算機(jī)硬件的運(yùn)行速度C:問題規(guī)模D:源程序的長(zhǎng)度

答案:問題規(guī)模

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

A:數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)唯一地決定了該數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)B:數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)獨(dú)立于其存儲(chǔ)結(jié)構(gòu)C:數(shù)據(jù)結(jié)構(gòu)僅由其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)決定D:數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)獨(dú)立于該數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)

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

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

A:包括以上三個(gè)方面B:建立在相應(yīng)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)上的算法C:數(shù)據(jù)的邏輯結(jié)構(gòu)D:數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

答案:包括以上三個(gè)方面

第二章測(cè)試

線性表是具有n個(gè)（）的有限序列。

A:字符B:表元素C:數(shù)據(jù)項(xiàng)D:數(shù)據(jù)元素

答案:數(shù)據(jù)元素

單鏈表又稱為線性鏈表，在單鏈表上實(shí)施插入和刪除操作（）。

A:既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針B:只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針C:不需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針D:不需移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針

答案:不需移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針

單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是（）。

A:說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)B:使單鏈表至少有一個(gè)結(jié)點(diǎn)C:方便運(yùn)算的實(shí)現(xiàn)D:標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置

答案:方便運(yùn)算的實(shí)現(xiàn)

單鏈表中，要將指針q指向的新結(jié)點(diǎn)插入到指針p指向的單鏈表結(jié)點(diǎn)之后，下面的操作序列中（）是正確的。

A:q=p->next;p->next=q->next;B:p->next=q->next;q=p->next;C:p->next=q;q->next=p->next;D:q->next=p->next;p->next=q;

答案:q->next=p->next;p->next=q;

鏈表不具有的特點(diǎn)是（）。

A:插入、刪除不需要移動(dòng)元素B:可隨機(jī)訪問任一元素C:不必事先估計(jì)存儲(chǔ)空間D:所需空間與線性表長(zhǎng)度成正比

答案:可隨機(jī)訪問任一元素

第三章測(cè)試

循環(huán)隊(duì)列存儲(chǔ)在A[0..m]中，則入隊(duì)時(shí)的操作是（）。

A:rear=(rear+1)%(m+1)B:rear=rear+1C:rear=(rear+1)%(m-1)D:rear=(rear+1)%m

答案:rear=(rear+1)%(m+1)

關(guān)于循環(huán)隊(duì)列，以下（）的說法正確。

A:循環(huán)隊(duì)列不會(huì)產(chǎn)生上溢出B:循環(huán)隊(duì)列不會(huì)產(chǎn)生假溢出C:循環(huán)隊(duì)列不會(huì)產(chǎn)生溢出D:A、B、C都不對(duì)

答案:循環(huán)隊(duì)列不會(huì)產(chǎn)生假溢出

如果循環(huán)隊(duì)列用大小為m的數(shù)組表示，隊(duì)頭位置為front、隊(duì)列元素個(gè)數(shù)為size，那么隊(duì)尾元素位置rear為（）。

A:(front+size-1)%mB:front+sizeC:front+size-1D:(front+size)%m

答案:(front+size-1)%m

若順序棧的棧頂指針指向棧頂元素位置，則壓入新元素時(shí)，應(yīng)（）。

A:先存入元素，再移動(dòng)棧頂指針B:先移動(dòng)棧頂指針C:先后次序無關(guān)緊要D:同時(shí)進(jìn)行

答案:先移動(dòng)棧頂指針

設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素{1,2,3,4,5,6,7}依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是{2,5,6,4,7,3,1}，則棧S的容量至少是：

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

答案:4

棧操作數(shù)據(jù)的原則是（）。

A:不分順序B:后進(jìn)后出C:先進(jìn)先出D:后進(jìn)先出

答案:后進(jìn)先出

設(shè)一個(gè)棧的輸入序列為a，b，c，d，則借助一個(gè)棧所得到的輸出序列不可能是（）。

A:a，b，c，dB:a，c，d，bC:d，c，b，aD:d，a，b，c

答案:d，a，b，c

設(shè)一個(gè)堆棧的入棧順序是1、2、3、4、5。若第一個(gè)出棧的元素是4，則最后一個(gè)出棧的元素必定是（）。

A:3B:1或者5C:1D:5

答案:1或者5

?？捎糜冢ǎ?。

A:表達(dá)式求值B:遞歸調(diào)用C:A、B、C都是D:子程序調(diào)用

答案:A、B、C都是

表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。

A:abcd*+-B:-+*abcdC:abc+*d-D:abc*+d-

答案:abc+*d-

第四章測(cè)試

若串S=“software”，則其子串?dāng)?shù)目是____，其中空串和S串本身這兩個(gè)字符串也算作S的字串

A:37B:9C:36D:8

答案:37

串的長(zhǎng)度是指____。

A:串中所含非空格字符的個(gè)數(shù)B:串中所含字符的個(gè)數(shù)C:串中所含不同字符的個(gè)數(shù)D:串中所含不同字母的個(gè)數(shù)

答案:串中所含字符的個(gè)數(shù)

下面關(guān)于串的敘述中，哪一個(gè)是不正確的____。

A:空串是由空格構(gòu)成的串B:模式匹配是串的一種重要運(yùn)算C:串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)D:串是字符的有限序列

答案:空串是由空格構(gòu)成的串

串是一種特殊的線性表，其特殊性體現(xiàn)在____。

A:數(shù)據(jù)元素是多個(gè)字符B:數(shù)據(jù)元素是一個(gè)字符C:可以鏈?zhǔn)酱鎯?chǔ)D:可以順序存儲(chǔ)

答案:數(shù)據(jù)元素是一個(gè)字符

在用KMP算法進(jìn)行模式匹配時(shí)，模式串“ababaaababaa”的next數(shù)組值為____。

A:-1，0，0，1，2，3，1，1，2，3，4，5B:-1，0，1，2，3，4，5，6，7，8，9，9C:-1，0，1，2，1，2，1，1，1，1，2，1D:-1，0，1，2，3，0，1，2，3，2，2，3

答案:-1，0，0，1，2，3，1，1，2，3，4，5

第五章測(cè)試

若一個(gè)問題既可以用迭代方式也可以用遞歸方式求解，則____的方法具有更髙的時(shí)空效率。

A:先迭代后遞歸B:先遞歸后迭代C:迭代D:遞歸

答案:迭代

一個(gè)遞歸算法必須包括____。

A:迭代部分B:終止條件和遞歸部分C:終止條件和迭代部分D:遞歸部分

答案:終止條件和遞歸部分

設(shè)有一個(gè)遞歸算法如下

intfact(intn){

//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);}則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。

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

答案:n+1

任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。

A:錯(cuò)B:對(duì)

答案:對(duì)

下列說法中，正確的是（）。

A:隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算B:消除遞歸不一定需要使用棧C:對(duì)同一輸入序列進(jìn)行兩組不同的合法入棧和出棧組合操作，所得的輸出序列也一定相同D:通常使用隊(duì)列來處理函數(shù)或過程調(diào)用

答案:消除遞歸不一定需要使用棧

第六章測(cè)試

稀疏矩陣一般的壓縮存儲(chǔ)方法有____兩種。

A:散列和十字鏈表B:三元組和散列C:二維數(shù)組和三維數(shù)組D:三元組和十字鏈表

答案:三元組和十字鏈表

設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)空間，將其下三角部分按照行優(yōu)先存放在一維數(shù)組B[0..n(n+1)/2-1]中，對(duì)于下三角部分的任一元素a_{i,j}(i>=j，i和j從0開始取值），在一維數(shù)組B中的下標(biāo)k的值是____。

A:i(i+1)/2+jB:i(i-1)/2+jC:i(i+1)/2+j-1D:i(i-1)/2+j-1

答案:i(i+1)/2+j

設(shè)二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲(chǔ)在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為____。

A:i*(j-1)B:(i-1)*n+j-1C:j*m+i-1D:(i-1)*n+j

答案:(i-1)*n+j

有一個(gè)二維數(shù)組A[6][8]，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，那么這個(gè)數(shù)組占用的存儲(chǔ)空間大小是（）個(gè)字節(jié)。

A:48B:288C:96D:252

答案:288

二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[4][7]的起始地址為()。提示：是按列存放。

A:SA+141B:SA+225C:SA+222D:SA+180

答案:SA+180

第七章測(cè)試

對(duì)于一棵具有n個(gè)結(jié)點(diǎn)、度為4的樹來說，（）。

A:樹的高度最多是n-4B:第i層上最多有4(i-1)個(gè)結(jié)點(diǎn)C:至少在某一層上正好有4個(gè)結(jié)點(diǎn)D:樹的高度最多是n-3

答案:樹的高度最多是n-3

假設(shè)每個(gè)結(jié)點(diǎn)值為單個(gè)字符，而一棵樹的層次遍歷序列為ABCDEFGHIJ，則其根結(jié)點(diǎn)的值是（

）。

A:BB:AC:A、B、C都不對(duì)D:J

答案:A

二叉樹若用順序方法存儲(chǔ)，則下列4種運(yùn)算中()最容易實(shí)現(xiàn)。

A:求結(jié)點(diǎn)值為x的結(jié)點(diǎn)的所有孩子B:先序遍歷二叉樹C:判斷兩個(gè)結(jié)點(diǎn)值分別為x、y的結(jié)點(diǎn)是不是在同一層上D:層次遍歷二叉樹

答案:層次遍歷二叉樹

若一棵二叉樹的先序序列