數(shù)據(jù)結(jié)構(gòu)（綿陽師范學(xué)院）智慧樹知到課后章節(jié)答案2023年下綿陽師范學(xué)院

數(shù)據(jù)結(jié)構(gòu)（綿陽師范學(xué)院）智慧樹知到課后章節(jié)答案2023年下綿陽師范學(xué)院綿陽師范學(xué)院

第一章測試

計算機(jī)算法是指解決問題的步驟序列,它必須具備（）、輸入和輸出5個特性。

A:可行性、可移植性、可擴(kuò)充性B:確定性、有窮性、穩(wěn)定性C:可行性、確定性、有窮性D:易讀性、穩(wěn)定性、安全性

答案:可行性、確定性、有窮性

當(dāng)需要解決的問題的規(guī)模（以某種單位計算）由1增至n時，解決問題的算法所耗費的時間也以某種單位由f(1)增至f(n)，則該算法的時間代價是（）。

A:f(1)B:nC:1D:f(n)

答案:f(n)

下面關(guān)于算法說法錯誤的是（）。

A:算法是指令的有限序列B:算法必須在執(zhí)行有窮步之后結(jié)束C:算法的可行性是指指令不能有二義性D:算法是對特定問題求解步驟的一種描述

答案:算法的可行性是指指令不能有二義性

從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。

A:順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)B:動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)C:線性結(jié)構(gòu)、非線性結(jié)構(gòu)D:初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

答案:線性結(jié)構(gòu)、非線性結(jié)構(gòu)

程序可以采用自然語言、數(shù)學(xué)語言或者約定的符號語言來描述。

A:錯B:對

答案:錯

順序存儲設(shè)計時，存儲單元的地址不一定連續(xù)。

A:對B:錯

答案:錯

數(shù)據(jù)結(jié)構(gòu)的研究范圍主要包括（）。

A:相應(yīng)的運算B:編程語言C:物理結(jié)構(gòu)D:邏輯結(jié)構(gòu)

答案:相應(yīng)的運算;物理結(jié)構(gòu);邏輯結(jié)構(gòu)

對于n個元素可以構(gòu)造的邏輯結(jié)構(gòu)有（）。

A:集合B:有序表C:鏈表D:線性結(jié)構(gòu)

答案:集合;線性結(jié)構(gòu)

下述（）與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)。

A:棧B:循環(huán)隊列C:散列表D:雙向鏈表

答案:循環(huán)隊列;散列表;雙向鏈表

以下說法錯誤的是（）。

A:數(shù)據(jù)元素是數(shù)據(jù)的最小單位B:數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合C:數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D:數(shù)據(jù)項是數(shù)據(jù)的基本單位

答案:數(shù)據(jù)元素是數(shù)據(jù)的最小單位;數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合;數(shù)據(jù)項是數(shù)據(jù)的基本單位

第二章測試

下述（）是順序存儲結(jié)構(gòu)的優(yōu)點。

A:方便地運用于各種邏輯結(jié)構(gòu)的存儲表示B:插入運算方便C:按位查找方便D:刪除運算方便

答案:按位查找方便

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

A:i-1B:nC:n-i+1D:n-i

答案:n-i

對于順序存儲的線性表,其算法時間復(fù)雜度為O(1)的運算應(yīng)該是（）。

A:改變第i（1<=i<=n）個元素的值B:將n個元素從小到大排序C:在第i（1<=i<=n）個元素后插入一個新元素D:刪除第i（1<=i<=n）個元素

答案:改變第i（1<=i<=n）個元素的值

將兩個有n個元素的有序表歸并為一個有序表，最少比較次數(shù)為（）。

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

答案:n

一個順序表所占用的存儲空間大小與表的長度無關(guān)。

A:錯B:對

答案:錯

一個鏈表最常用的操作是在末尾插入結(jié)點和刪除結(jié)點,則選用帶頭結(jié)點的雙循環(huán)鏈表最節(jié)省時間。

A:對B:錯

答案:對

關(guān)于線性表順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的描述中，正確的是（）。

A:如頻繁使用插入和刪除結(jié)點操作，順序存儲結(jié)構(gòu)更優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)B:線性表的順序存儲結(jié)構(gòu)優(yōu)于其鏈?zhǔn)酱鎯Y(jié)構(gòu)C:線性表的長度變化較大時，鏈?zhǔn)酱鎯Y(jié)構(gòu)更優(yōu)于順序存儲結(jié)構(gòu)D:順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都可以進(jìn)行順序存取

答案:線性表的長度變化較大時，鏈?zhǔn)酱鎯Y(jié)構(gòu)更優(yōu)于順序存儲結(jié)構(gòu);順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都可以進(jìn)行順序存取

取線性表的第i個元素的時間與i的大小有關(guān)。

A:錯B:對

答案:錯

在n個元素的線性表的數(shù)組表示中,時間復(fù)雜度為O(1)的操作是（）。

A:在第i(1B:在最后一個結(jié)點后插入一個新值C:訪問第i(1D:刪除第i(1

答案:在最后一個結(jié)點后插入一個新值;訪問第i(1

在n個元素的線性表中,刪除第1個結(jié)點時間復(fù)雜度為O(1)。

A:對B:錯

答案:錯

第三章測試

棧和隊列具有相同的（）。

A:運算B:邏輯結(jié)構(gòu)C:抽象數(shù)據(jù)類型D:存儲結(jié)構(gòu)

答案:邏輯結(jié)構(gòu)

棧和隊列的主要區(qū)別在于（）。

A:所包含的元素不一樣B:插入，刪除操作的限定不一樣C:它們的存儲結(jié)構(gòu)不一樣D:它們的邏輯結(jié)構(gòu)不一樣

答案:插入，刪除操作的限定不一樣

棧的應(yīng)用不包括（）。

A:迷宮求解B:圖的廣度優(yōu)先遍歷C:遞歸D:進(jìn)制轉(zhuǎn)換

答案:圖的廣度優(yōu)先遍歷

元素a,b,c,d,e依次進(jìn)入初始為空的棧中,若元素進(jìn)棧后，可停留、可出棧,直到所有元素都出棧,則在所有可能的出棧序列中,以元素d開頭的序列個數(shù)是（）。

A:6B:3C:4D:5

答案:4

刪除棧頂元素不是棧的基本操作。

A:錯B:對

答案:錯

表達(dá)式1*(2+3)+a的后綴表達(dá)式是123+*a+。

A:對B:錯

答案:對

有六個元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪些是合法的出棧序列（）?

A:543612B:346521C:453126D:234156

答案:543612;453126;234156

對于棧操作數(shù)據(jù)的特點不正確的是（）。

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

答案:先進(jìn)先出;不分順序;后進(jìn)后出

棧是一種受限的線性表,允許在其兩端進(jìn)行操作。

A:對B:錯

答案:錯

不允許對隊列進(jìn)行的操作有（）。

A:對隊列中的元素排序B:取出最近進(jìn)隊的元素C:刪除隊頭元素D:在隊列元素之間插入元素

答案:對隊列中的元素排序;取出最近進(jìn)隊的元素;在隊列元素之間插入元素

第四章測試

兩個字符串相等的條件是（）。

A:含有相同的字符集B:串的長度相等C:都是非空串D:兩個串的長度相等且對應(yīng)位置的字符相同

答案:兩個串的長度相等且對應(yīng)位置的字符相同

下面關(guān)于串的敘述中，正確的是（）。

A:串的長度必須大于零B:空串就是空白串C:串中元素只能是字母D:串是一種特殊的線性表

答案:串是一種特殊的線性表

若串s=“World”，其子串的個數(shù)是（）。

A:6B:15C:5D:16

答案:16

字符串str=“software”，若采用動態(tài)分配的順序存儲方法需要（）個字節(jié)（設(shè)每種數(shù)據(jù)均占用2個字節(jié)）。

A:32B:動態(tài)產(chǎn)生，視情況而定C:8D:16

答案:16

串采用節(jié)點大小為2的鏈表作為其存儲結(jié)構(gòu)，是指（）。

A:鏈表中每個節(jié)點的數(shù)據(jù)域中只存放2個字符B:其余選項都不對C:鏈表的長度為2D:鏈表中只存放2個字符

答案:鏈表中每個節(jié)點的數(shù)據(jù)域中只存放2個字符

設(shè)有兩個串T和S，其中T是S的子串，則求T在S中首次出現(xiàn)位置的算法稱為（）。

A:串聯(lián)接B:模式匹配C:求子串D:求串長

答案:模式匹配

在串的簡單模式匹配中，當(dāng)模式串位j與目標(biāo)串位i比較時，兩字符不相等，則i的位移方式是（）。

A:i=j-i+1B:i=j+1C:i++D:i=i-j+1

答案:i=i-j+1

在KMP模式匹配中，用next數(shù)組存放模式串的部分匹配信息。當(dāng)模式串位j與目標(biāo)串位i比較時，兩字符不相等，則i的位移方式是（）。

A:j=next[j]B:i不變C:j不變D:i=next[j]

答案:i不變

在KMP模式匹配中，用next數(shù)組存放模式串的部分匹配信息。當(dāng)模式串位j與目標(biāo)串位i比較時，兩字符不相等，則j的位移方式是（）。

A:i=next[j]B:i不變C:j=next[j]D:j不變

答案:j=next[j]

空格串是由一個或多個空格字符組成的串，其長度為1。

A:錯B:對

答案:錯

第五章測試

設(shè)有10×6的數(shù)組A，數(shù)組下標(biāo)從0,0開始，其每個元素占2個字節(jié)，按列優(yōu)先順序存儲，若已知A[3][4]在內(nèi)存中的地址是1086，則A[4][5]的地址是（）。

A:1108B:1140C:1054D:1296

答案:1108

以下物理結(jié)構(gòu)中，不能夠?qū)?shù)據(jù)元素進(jìn)行隨機(jī)訪問的是（）

A:對稱矩陣的壓縮存儲B:數(shù)組的順序存儲C:三元組順序表D:三對角矩陣的壓縮存儲

答案:三元組順序表

若對n階對稱矩陣A，下標(biāo)從1開始，以行序為主序方式將其下三角形的元素依次存放于一維數(shù)組B［1..(n(n+1))/2］中，則在B中確定a[i][j](1≤i，j≤n，且i≤j)的位置k的計算公式為()。

A:i(i+1)/2+jB:j(j+1)/2+iC:j(j-1)/2+iD:i(i-1)/2+j

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

經(jīng)常對數(shù)組進(jìn)行的兩種基本操作是()。

A:查找與索引B:查找和修改C:建立與刪除D:索引和修改

答案:查找和修改

將一個A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，元素A[66][65]在B數(shù)組中的位置K為（）。

A:195B:198C:197D:196

答案:195

下面說法不正確的是()。

A:廣義表的表頭總是一個廣義表B:廣義表可以是一個多層次的結(jié)構(gòu)C:一個非空廣義表的表尾總是一個廣義表D:廣義表難以用順序存儲結(jié)構(gòu)進(jìn)行存儲

答案:廣義表的表頭總是一個廣義表

廣義表（（a,b,c,d））的表尾是（）。

A:（）B:（b,c,d）C:（a,b,c,d）D:a

答案:（）

廣義表（a,(b,c),d,e）的表頭為（）。

A:(a,(b,c))B:a,(b,c)C:(a)D:a

答案:a

數(shù)組是一種非線性結(jié)構(gòu)，除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等操作。

A:對B:錯

答案:錯

稀疏矩陣中非零元素的個數(shù)遠(yuǎn)小于矩陣中元素的總數(shù)。

A:對B:錯

答案:對

第六章測試

一棵有n個結(jié)點的樹的所有結(jié)點的度數(shù)之和為（）。

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

答案:n-1

已知一棵完全二叉樹的第6層(設(shè)根為第1層）有8個葉結(jié)點,則該完全二叉樹的結(jié)點個數(shù)最多是（）。

A:111B:119C:39D:52

答案:111

二叉排序樹是動態(tài)樹表,查找失敗時插入新結(jié)點,會引起樹的重新分裂和組合

A:錯B:對

答案:錯

哈夫曼樹具有最小的帶權(quán)路徑長度

A:錯B:對

答案:對

在下列關(guān)于二叉樹遍歷的說法中,錯誤的是（）。

A:若有一個結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列的最后一個結(jié)點,則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點B:若有一個葉子結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列的最后一個結(jié)點,則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點C:若有一個葉子結(jié)點是二叉樹中某個子樹的前序遍歷結(jié)果序列的最后一個結(jié)點,則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點D:若有一個結(jié)點是二叉樹中某個子樹的前序遍歷結(jié)果序列的最后一個結(jié)點,則它一定是該子樹的中序遍歷結(jié)果序列的最后一個結(jié)點

答案:若有一個結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列的最后一個結(jié)點,則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點;若有一個葉子結(jié)點是二叉樹中某個子樹的前序遍歷結(jié)果序列的最后一個結(jié)點,則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點;若有一個結(jié)點是二叉樹中某個子樹的前序遍歷結(jié)果序列的最后一個結(jié)點,則它一定是該子樹的中序遍歷結(jié)果序列的最后一個結(jié)點

下列關(guān)于樹的說法中,錯誤的是（）。

A:一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)B:高度為h(h>0）的完全二叉樹對應(yīng)的森林所含的樹的個數(shù)一定是hIV.一棵樹中的葉子數(shù)一定是hC:一對于有n個結(jié)點的二又樹,其高度為log.nD:完全二叉樹中,若一個結(jié)點沒有左孩子,則它必是葉結(jié)點

答案:高度為h(h>0）的完全二叉樹對應(yīng)的森林所含的樹的個數(shù)一定是hIV.一棵樹中的葉子數(shù)一定是h;一對于有n個結(jié)點的二又樹,其高度為log.n;完全二叉樹中,若一個結(jié)點沒有左孩子,則它必是葉結(jié)點

將森林轉(zhuǎn)換為對應(yīng)的二又樹,若在二叉樹中,結(jié)點u是點v的父結(jié)點的父結(jié)點,則在原來的森林中,u和v可能具有的關(guān)系是（）。

A:兄弟關(guān)系B:u的父結(jié)點與v的父結(jié)點是兄弟關(guān)系C:父子關(guān)系

答案:兄弟關(guān)系;父子關(guān)系

設(shè)X是樹T中的一個非根結(jié)點,B是T所對應(yīng)的二又樹.在B中,X是其雙親結(jié)點的右孩子,下列結(jié)論中錯誤的是（）。

A:在樹T中,X一定無右邊兄弟B:在樹T中,X一定是葉子結(jié)點C:在樹T中,X是其雙親結(jié)點的第一個孩子D:在樹T中,X一定有左邊兄弟

答案:在樹T中,X一定無右邊兄弟;在樹T中,X一定是葉子結(jié)點;在樹T中,X是其雙親結(jié)點的第一個孩子

第七章測試

在一個具有n個頂點的無向連通圖中至少有（）條邊。

A:nB:n/2C:n-1D:n+1

答案:n-1

非空無向圖的鄰接矩陣是一個（）。

A:上三角矩陣B:零矩陣C:對稱矩陣D:對角矩陣

答案:對稱矩陣

如果從無向圖的任一頂點出發(fā)進(jìn)行一次廣度優(yōu)先遍歷即可訪問所有頂點，則該圖一定是（）。

A:一棵樹B:有回路C:連通圖D:完全圖

答案:連通圖

一個有向圖G=(V，E)，V={0，1，2，3，4}，E={<0，1>，<1，2>，<0，3>，

<2，1>，<1，4>，<2，4>，<4，3>}，現(xiàn)按深度優(yōu)先遍

歷算法遍歷，從頂點0出發(fā)，所得到的頂點序列是（）

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

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

強連通圖是任何頂點到其他所有頂點都有邊。

A:對B:錯

答案:錯

有向圖中任一頂點的入度等于出度。

A:錯B:對

答案:錯

對任何有向圖調(diào)用一次廣度優(yōu)先遍歷算法便可訪問所有的頂點。

A:對B:錯

答案:錯

對任何非強連通圖必須2次或以上調(diào)用廣度優(yōu)先遍歷算法才可訪問所有的頂點

A:錯B:對

答案:對

樹最適合用來表示（）的數(shù)據(jù)。

A:元素之間具有分支層次關(guān)系B:有序C:任意元素之間具有多種聯(lián)系D:無序

答案:元素之間具有分支層次關(guān)系

具有10個葉子結(jié)點的二叉樹中有（）個度為2的結(jié)點。

A:9B:11C:10D:8

答案:9

第八章測試

采用折半搜索算法搜索長度為n的有序表時，元素的平均搜索長度為

A:O（nlog2n）B:O（log2n）C:O（n2）D:O（n）

答案:O（log2n）

對包含n個元素的散列表進(jìn)行搜索，平均搜索長度為

A:不直接依賴于nB:其余都不對C:O（n）D:O（log2n）

答案:不直接依賴于n

折半(二分)查找有序表(3,4,5,10,13,14,20,30),若查找元素30,則被比較的元素依次為（）

A:10,20,30B:10,14,30C:10,14,20,30D:13,30

答案:10,14,20,30

對線性表進(jìn)行折半搜索時，要求線性表必須

A:以鏈接方式存儲且結(jié)點按關(guān)鍵碼有序排列B:以數(shù)組方式存儲且結(jié)點按關(guān)鍵碼有序排列C:以數(shù)組方式存儲D:以鏈接方式存儲

答案:以數(shù)組方式存儲且結(jié)點按關(guān)鍵碼有序排列

哈希函數(shù)處理沖突的方法有

A:隨機(jī)探查法B:線性探測法C:拉鏈法D:開放定址法

答案:拉鏈法;開放定址法

構(gòu)造（Hash）函數(shù)的方法有

A:隨機(jī)探查法B:鏈地址法C:線性探測法D:除留取余法

答案:隨機(jī)探查法;線性探測法;除留取余法

以折半搜索方法搜索一個線性表時，此線性表必須是順序存儲的有序表。

A:對B:錯

答案:對

在索引表中，每個索引項至少包含有關(guān)鍵碼值域和子表地址域這兩項。

A:對B:錯

答案:對

在散列存儲中，裝載因子α又稱為裝載系數(shù)，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則α等于n/m

A:對B:錯

答案:對

順序查找的平均查找長度是n/2

A:錯B:對

答案:錯

第九章測試

設(shè)一組初始記錄關(guān)鍵字序列為(12，24，18，36，19，38，20，40，35，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為()。

A:12，24，18，36，19，38，20，40，35，70B:12，18，19，20，24，36，35，38，40，70C:12，18，19，20，24，36，38，40，35，70D:12，18，24，36，19，20，38，40，35，70

答案:12，18，24，36，19，20，38，40，35，70

若用冒泡排序?qū)﹃P(guān)鍵字序列{17，15，13，11，10，6}，進(jìn)行從小到大的排序，所需進(jìn)行的關(guān)鍵字比較總次數(shù)是(