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

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

A:對(duì)

B:錯(cuò)

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

A:錯(cuò)

B:對(duì)

答案:B第一章測(cè)試算法的時(shí)間復(fù)雜度取決于（）。

A:算法的長(zhǎng)短

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

C:執(zhí)行算法的計(jì)算機(jī)性能的高低

D:待處理數(shù)據(jù)的初態(tài)

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

A:效率

B:現(xiàn)實(shí)性

C:難度

D:復(fù)雜度

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

A:編譯后執(zhí)行程序的質(zhì)量

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

C:源程序的長(zhǎng)度

D:計(jì)算機(jī)硬件的運(yùn)行速度

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

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

B:數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)唯一地決定了該數(shù)據(jù)結(jié)構(gòu)的存儲(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)

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

A:數(shù)據(jù)的邏輯結(jié)構(gòu)

B:數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

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

D:建立在相應(yīng)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)上的算法

答案:C第二章測(cè)試線性表是具有n個(gè)（）的有限序列。

A:字符

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

C:表元素

D:數(shù)據(jù)項(xiàng)

答案:B單鏈表又稱為線性鏈表，在單鏈表上實(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單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是（）。

A:標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置

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

C:使單鏈表至少有一個(gè)結(jié)點(diǎn)

D:說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)

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

A:p->next=q->next;q=p->next;

B:p->next=q;q->next=p->next;

C:q=p->next;p->next=q->next;

D:q->next=p->next;p->next=q;

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

A:不必事先估計(jì)存儲(chǔ)空間

B:可隨機(jī)訪問(wèn)任一元素

C:插入、刪除不需要移動(dòng)元素

D:所需空間與線性表長(zhǎng)度成正比

答案:B第三章測(cè)試循環(huán)隊(duì)列存儲(chǔ)在A[0..m]中，則入隊(duì)時(shí)的操作是（）。

A:rear=(rear+1)%(m-1)

B:rear=(rear+1)%(m+1)

C:rear=(rear+1)%m

D:rear=rear+1

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

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

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

C:A、B、C都不對(duì)

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

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

A:front+size-1

B:front+size

C:(front+size)%m

D:(front+size-1)%m

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

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

B:先后次序無(wú)關(guān)緊要

C:先存入元素，再移動(dòng)棧頂指針

D:同時(shí)進(jìn)行

答案:A設(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:4

B:1

C:3

D:2

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

A:后進(jìn)后出

B:后進(jìn)先出

C:先進(jìn)先出

D:不分順序

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

A:a，b，c，d

B:d，a，b，c

C:a，c，d，b

D:d，c，b，a

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

A:1

B:5

C:1或者5

D:3

答案:C?？捎糜冢ǎ?/p>

A:遞歸調(diào)用

B:表達(dá)式求值

C:A、B、C都是

D:子程序調(diào)用

答案:C表達(dá)式a(b+c)-d的后綴表達(dá)式是（）。

A:abc+d-

B:abcd*+-

C:-+*abcd

D:abc+*d-

答案:D第四章測(cè)試若串S=“software”，則其子串?dāng)?shù)目是____，其中空串和S串本身這兩個(gè)字符串也算作S的字串

A:36

B:9

C:8

D:37

答案:D串的長(zhǎng)度是指____。

A:串中所含非空格字符的個(gè)數(shù)

B:串中所含不同字符的個(gè)數(shù)

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

D:串中所含不同字母的個(gè)數(shù)

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

A:串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)

B:模式匹配是串的一種重要運(yùn)算

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

D:串是字符的有限序列

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

A:數(shù)據(jù)元素是多個(gè)字符

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

C:可以順序存儲(chǔ)

D:可以鏈?zhǔn)酱鎯?chǔ)

答案:B在用KMP算法進(jìn)行模式匹配時(shí)，模式串“ababaaababaa”的next數(shù)組值為_(kāi)___。

A:-1，0，1，2，1，2，1，1，1，1，2，1

B:-1，0，1，2，3，0，1，2，3，2，2，3

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

D:-1，0，0，1，2，3，1，1，2，3，4，5

答案:D第五章測(cè)試若一個(gè)問(wèn)題既可以用迭代方式也可以用遞歸方式求解，則____的方法具有更髙的時(shí)空效率。

A:遞歸

B:先遞歸后迭代

C:先迭代后遞歸

D:迭代

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

A:迭代部分

B:遞歸部分

C:終止條件和迭代部分

D:終止條件和遞歸部分

答案:D設(shè)有一個(gè)遞歸算法如下

intfact(intn){

//n大于等于0

if(n

A:n-1

B:n

C:n+1

D:n+2

答案:C任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。

A:錯(cuò)

B:對(duì)

答案:B下列說(shuō)法中，正確的是（）。

A:對(duì)同一輸入序列進(jìn)行兩組不同的合法入棧和出棧組合操作，所得的輸出序列也一定相同

B:隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算

C:通常使用隊(duì)列來(lái)處理函數(shù)或過(guò)程調(diào)用

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

答案:D第六章測(cè)試稀疏矩陣一般的壓縮存儲(chǔ)方法有____兩種。

A:三元組和十字鏈表

B:散列和十字鏈表

C:二維數(shù)組和三維數(shù)組

D:三元組和散列

答案:A設(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開(kāi)始取值），在一維數(shù)組B中的下標(biāo)k的值是____。

A:i(i+1)/2+j

B:i(i+1)/2+j-1

C:i(i-1)/2+j

D:i(i-1)/2+j-1

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

A:(i-1)n+j-1

B:jm+i-1

C:i(j-1)

D:(i-1)n+j

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

A:48

B:252

C:96

D:288

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

A:SA+225

B:SA+222

C:SA+141

D:SA+180

答案:D第七章測(cè)試對(duì)于一棵具有n個(gè)結(jié)點(diǎn)、度為4的樹(shù)來(lái)說(shuō)，（）。

A:至少在某一層上正好有4個(gè)結(jié)點(diǎn)

B:樹(shù)的高度最多是n-3

C:第i層上最多有4(i-1)個(gè)結(jié)點(diǎn)

D:樹(shù)的高度最多是n-4

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

）。

A:B

B:A

C:J

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

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

A:判斷兩個(gè)結(jié)點(diǎn)值分別為x、y的結(jié)點(diǎn)是不是在同一層上

B:求結(jié)點(diǎn)值為x的結(jié)點(diǎn)的所有孩子

C:層次遍歷二叉樹(shù)

D:先序遍歷二叉樹(shù)

答案:C若一棵二叉樹(shù)的先序序列和后序遍歷