數(shù)據(jù)結(jié)構(gòu)（西安理工大學）智慧樹知到課后章節(jié)答案2023年下西安理工大學

數(shù)據(jù)結(jié)構(gòu)（西安理工大學）智慧樹知到課后章節(jié)答案2023年下西安理工大學西安理工大學

第一章測試

研究數(shù)據(jù)結(jié)構(gòu)就是研究(

)。

A:數(shù)據(jù)的存儲結(jié)構(gòu)B:數(shù)據(jù)的邏輯結(jié)構(gòu)C:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)在運算上的實現(xiàn)D:數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

答案:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)在運算上的實現(xiàn)

關于算法的說法，錯誤的是(

)。

A:其他三項都是錯誤的B:算法的可行性是指指令不能有二義性C:算法最終必須由計算機程序?qū)崿F(xiàn)D:為解決某問題的算法和為該問題編寫的程序含義是相同的

答案:其他三項都是錯誤的

數(shù)據(jù)的(

)包括集合、線性、樹和圖4種基本類型。

A:存儲結(jié)構(gòu)B:邏輯結(jié)構(gòu)C:算法描述D:基本運算

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

數(shù)據(jù)的存儲結(jié)構(gòu)包括順序、鏈式、散列和(

)4種基本類型。

A:向量B:索引C:數(shù)組D:集合

答案:索引

下面算法的時間復雜度為(

)。for(i=0;i<m;i++)for(j=0;j<n;j++)

A[i][j]=i*j;

A:O(n2)B:O(m+n)C:O(m×n)D:O(m2)

答案:O(m×n)

以下（

）屬于設計一個“好”的算法應考慮達到的目標。

A:可讀性B:正確性C:效率與低存儲量要求D:健壯性

答案:可讀性;正確性;效率與低存儲量要求;健壯性

依據(jù)所有數(shù)據(jù)成員之間的邏輯關系的不同，數(shù)據(jù)結(jié)構(gòu)分為（

）。??

A:物理結(jié)構(gòu)B:線性結(jié)構(gòu)C:邏輯結(jié)構(gòu)D:非線性結(jié)構(gòu)

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

在存儲數(shù)據(jù)時，不僅要考慮存儲各數(shù)據(jù)元素的值，而且還要存儲數(shù)據(jù)元素之間的關系。

A:錯B:對

答案:對

在邏輯結(jié)構(gòu)定義的操作與具體實現(xiàn)有關。

A:錯B:對

答案:錯

算法是對解題方法和步驟的描述。

A:對B:錯

答案:對

算法分析的兩個主要方面是時間復雜度和空間復雜度的分析。

A:錯B:對

答案:對

第二章測試

線性表是（

）。

A:一個無限序列，可以為空。B:一個有限序列，可以為空。C:一個無限序列，不能為空。D:一個有限序列，不能為空。

答案:一個有限序列，可以為空。

若某線性表中最常用的操作是取第i個元素和查找第i個元素的前驅(qū)，則采用（）存儲方法最節(jié)省時間。

A:雙向鏈表B:單鏈表C:循環(huán)鏈表D:順序表

答案:順序表

單鏈表中，增加一個頭結(jié)點的目的是為了（

）。

A:使單鏈表至少有一個結(jié)點B:說明單鏈表是線性表的鏈式存儲C:方便運算的實現(xiàn)D:標識表結(jié)點中首結(jié)點的位置

答案:方便運算的實現(xiàn)

在帶有頭結(jié)點的單鏈表Head中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（

）。

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

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

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

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

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

Head->next=p;

在n個結(jié)點的順序表中，算法的時間復雜度是O(1)的操作是（）。

A:將n個元素從小到大排序B:訪問第i個元素（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）C:刪除第i個元素（1≤i≤n）D:在第i個元素后插入一個新結(jié)點（1≤i≤n）

答案:訪問第i個元素（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）

下列說法正確的有(

)。

A:所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關系?B:算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時二者通用C:從邏輯關系上講，數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)D:數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關E:“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)相等

答案:所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關系?;從邏輯關系上講，數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu);數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關

線性表的邏輯順序和存儲順序總是一致的。

A:錯B:對

答案:錯

在線性表的順序存儲結(jié)構(gòu)中，插入和刪除時移動元素的個數(shù)與該元素的位置有關。

A:對B:錯

答案:對

順序存儲結(jié)構(gòu)只能存儲線性結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)只能存儲非線性結(jié)構(gòu)。

A:錯B:對

答案:錯

線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。

A:對B:錯

答案:錯

鏈式存儲方式以指針表示元素間的邏輯關系。

A:對B:錯

答案:對

第三章測試

在順序?？盏那闆r下不能進行出棧操作，否則將產(chǎn)生“下溢”。

A:對B:錯

答案:對

棧和隊列都是限制存取位置的線性表。

A:對B:錯

答案:對

若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行，則不可能得到出棧序列：a,f,e,d,c,b。

A:對B:錯

答案:錯

入棧操作和入隊列操作在鏈式存儲結(jié)構(gòu)上實現(xiàn)時一般不需要考慮棧溢出的情況。

A:對B:錯

答案:對

同一個棧內(nèi)的各個數(shù)據(jù)元素類型可以不一致。

A:對B:錯

答案:錯

以下說法中正確的是（

）

A:當隊列中無數(shù)據(jù)元素時，稱空隊列。

B:棧是一種操作不受限制的線性表。C:隊列被稱為“先進后出”表。D:棧是一種只允許在一端進行插入和刪除的線性表。

答案:當隊列中無數(shù)據(jù)元素時，稱空隊列。

;棧是一種只允許在一端進行插入和刪除的線性表。

以下說法中錯誤的是(

)?。

A:棧不能對輸入序列部分或全局求逆。B:利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，這種形式的棧稱為順序棧。C:當top等于數(shù)組最大下標時則棧滿。D:top=-1時為空棧，元素進棧時指針top不斷減1。

答案:棧不能對輸入序列部分或全局求逆。;top=-1時為空棧，元素進棧時指針top不斷減1。

已知一個棧的進棧序列是a1,a2,a3....an.其輸出序列為1,2,3...n,若a3=1則a1為（

）

A:可能是3B:不可能是3C:一定是2D:不可能是2E:可能是2

答案:可能是3;一定是2;不可能是2

棧的特點是（

）

A:先進后出B:進優(yōu)于出C:出優(yōu)于進D:先進先出

答案:先進后出

設循環(huán)隊列的容量為20，序號從0到19，經(jīng)過一系列的入隊和出隊后，front=5,rear=10,問隊列中有多少個元素（采用節(jié)省一個隊列存儲空間的方式）。

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

答案:5

一個隊列的入隊序列是1，2，3，4，則隊列的出隊序列是（

）

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

答案:1，2，3，4

一般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應該設置（

）

A:棧B:?；蜿犃蠧:數(shù)組D:隊列

答案:棧

設用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（

）

A:對棧不作任何判別B:必須判別棧是否為滿C:必須判別棧是否為空D:判別棧元素的類型

答案:必須判別棧是否為空

第四章測試

KMP算法的特點是在模式匹配時指示主串的指針不會變小。

A:錯B:對

答案:對

空串與空格串是相同的。

A:對B:錯

答案:錯

串的長度是指串中不同字符的個數(shù)。

A:錯B:對

答案:錯

設有兩個串P和Q，其中Q是P的子串，把Q在P中首次出現(xiàn)的位置作為子串Q在P中的位置的算法稱為模式匹配算法。

A:錯B:對

答案:對

設模式串（子串）的長度為m，目標串（主串）的長度為n。當n≈m且處理只匹配一次的模式時，簡單模式匹配（BF）算法所花費的時間代價也可能會比KMP算法更節(jié)省。

A:對B:錯

答案:對

串是一種特殊的線性表，下列不能體現(xiàn)其特殊性的是（

）

A:可以鏈接存儲B:數(shù)據(jù)元素可以是非字符數(shù)據(jù)C:可以順序存儲D:數(shù)據(jù)元素是字符型數(shù)據(jù)

答案:可以鏈接存儲;數(shù)據(jù)元素可以是非字符數(shù)據(jù);可以順序存儲

以下說法中錯誤的是(

)

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

答案:串中的元素只能是字母;串的長度必須大于零;空串就是空白串

兩個串相等必須有（

）

A:串中各位置字符均對應相等B:串長度任意C:串長度不相等D:串長度相等E:串中的各位置字符任意

答案:串中各位置字符均對應相等;串長度相等

若串S=”software”，其子串的數(shù)目是（

）

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

答案:37

下面（

）不是“abcd321ABCD”的子串（

）

A:abcABB:abcdC:21ABD:321AB

答案:abcAB

已知模式串為“aaab”，其next數(shù)組值為（

）

A:0,1,2,0B:-1,0,1,2C:-1,1,0,0D:0,0,1,2

答案:-1,0,1,2

設主串為“abccdcdccdbaa”，模式串為“cdcc”，用BF算法在第（

）次匹配成功。

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

答案:6

設串s1=“ABCDEFG”，s2=“12345”，用字符數(shù)組從0下標位置存儲，函數(shù)strcat(s,t)返回s和t串的連接串，strsub(s,i,j)返回串s中從第i個字符開始的連續(xù)j個字符組成的子串，strlen(s)返回串s的長度，則strcat(strsub(s1,2,strlen(s2)),strsub(s1,strlen(s2),2))的結(jié)果是（

）

A:CDEFGFGB:CDEFG12C:BCDEFG1D:CD12345

答案:CDEFGFG

第五章測試

稀疏矩陣壓縮存儲后，必會失去隨機存取功能。

A:對B:錯

答案:對

數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。

A:對B:錯

答案:錯

數(shù)組的存儲結(jié)構(gòu)是一組連續(xù)的內(nèi)存單元。

A:錯B:對

答案:對

廣義表中原子個數(shù)即為廣義表的長度。

A:錯B:對

答案:錯

廣義表中元素的個數(shù)即為廣義表的深度。

A:對B:錯

答案:錯

廣義表((a),(a))的表頭和表尾是（

）

A:aB:((a))C:(a)D:b

答案:((a));(a)

以下屬于特殊矩陣的是(

)

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

答案:對稱矩陣;對角矩陣;下三角矩陣;上三角矩陣

以下不屬于數(shù)組操作的是(

)

A:修改B:刪除C:插入D:存取E:查找

答案:刪除;插入

對行下標由1到50、列下標由1到80的二維數(shù)組a，若該數(shù)組的起始地址為2000且每個元素占2個存儲單元，并以行為主序順序存儲，則元素a[45][68]的存儲地址為（

）

A:9174B:9172C:9175D:9173

答案:9174

在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（

）

A:元素值B:非零元素個數(shù)C:行號D:列號

答案:行號

設有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（

）

A:28B:55C:10D:19

答案:19

設二維數(shù)組A[0~m][0~n]按行優(yōu)先順序存儲在內(nèi)存中，第一個元素的地址為p，每個元素占k個字節(jié)，則a[i][j]的地址為（

）

A:p+((i-1)*n+j-1)*kB:p+(j*n+i-1)*kC:p+((j-1)*n+i-1)*kD:p+(i*n+j)*k

答案:p+(i*n+j)*k

下面說法不正確的是（

）

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

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

第六章測試

一棵完全二叉樹上有1001個結(jié)點，其葉子結(jié)點的個數(shù)是（）。

A:A～C都不對B:500C:250D:505

答案:A～C都不對

一棵有124個葉結(jié)點的完全二叉樹最多有（）個結(jié)點。

A:248B:247C:250D:249

答案:248

在n個結(jié)點的線索二叉樹中，線索的數(shù)目為（）

A:nB:2nC:n+1D:n-1

答案:n+1

設有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有（）個結(jié)點。

A:13B:12C:25D:26

答案:25

樹的基本遍歷策略可分為先根遍歷和后根遍歷，而二叉樹的基本遍歷策略可分為先序、中序和后序這三種遍歷。我們把由樹轉(zhuǎn)化得到的二叉樹稱為該樹對應的二叉樹，則（）是正確的。

A:樹的先根遍歷與其對應的二叉樹先序遍歷序列相同B:樹的后根遍歷與其對應的二叉樹后序遍歷序列相同C:樹的先根遍歷與其對應的二叉樹中序遍歷序列相同

答案:樹的先根遍歷與其對應的二叉樹先序遍歷序列相同

完全二叉樹（）。

A:適合于順序存儲結(jié)構(gòu)存儲B:葉子結(jié)點可在任一層出現(xiàn)C:某些結(jié)點有左子樹時則必有右子樹D:不一定適合順序存儲結(jié)構(gòu)存儲E:某些結(jié)點有右子樹時則必有左子樹

答案:適合于順序存儲結(jié)構(gòu)存儲;某些結(jié)點有右子樹時則必有左子樹

對于二叉樹，下列描述正確的是（）

A:高度為k的二叉樹結(jié)點數(shù)最多時一定是滿二叉樹B:一定有度數(shù)為1的結(jié)點C:第k層上最多有2k-1個結(jié)點D:葉子結(jié)點數(shù)目比度數(shù)為2的結(jié)點數(shù)目多1個E:邊的個數(shù)比結(jié)點個數(shù)少1個F:n個結(jié)點共有n-1個非空指針域

答案:高度為k的二叉樹結(jié)點數(shù)最多時一定是滿二叉樹;葉子結(jié)點數(shù)目比度數(shù)為2的結(jié)點數(shù)目多1個;邊的個數(shù)比結(jié)點個數(shù)少1個;n個結(jié)點共有n-1個非空指針域

關于哈夫曼編碼的說法正確的是（

）

A:是一種最佳編碼B:編碼無二義性C:WPL最小D:不允許出現(xiàn)頻度相同的字符E:兩個頻度相同的字符其編碼長度一定相等

答案:是一種最佳編碼;編碼無二義性;WPL最小

存在這樣的二叉樹，對它采用任何次序進行遍歷得到的結(jié)果都相同。

A:錯B:對

答案:對

二叉樹就是結(jié)點度為2的有序樹。

A:錯B:對

答案:錯

若一個結(jié)點是二叉樹子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子樹的先序遍歷序列中的最后一個結(jié)點。

A:對B:錯

答案:錯

一棵含有n個結(jié)點的完全二叉樹，它的高度是?log2n?+1。

A:錯B:對

答案:對

線索二叉樹的左線索指向其某種遍歷序列的直接前驅(qū)結(jié)點，右線索指向其某種遍歷序列的直接后繼結(jié)點。

A:錯B:對

答案:對

第七章測試

無向圖的鄰接矩陣是（

）矩陣。

A:上三角陣B:下三角陣C:稀疏矩陣D:對稱

答案:對稱

用鄰接表存儲的圖所用空間大?。?/p>

）

A:只與圖的頂點數(shù)有關與邊數(shù)的平方有關B:與邊數(shù)的平方有關C:與圖的頂點數(shù)和邊數(shù)都有關D:只與圖的邊數(shù)有關

答案:與圖的頂點數(shù)和邊數(shù)都有關

不論基于圖的鄰接表還是基于鄰接矩陣存儲，圖的廣度優(yōu)先遍歷算法類似于樹的（

）

A:先序遍歷B:中序遍歷C:后序遍歷D:層次遍歷

答案:層次遍歷

一個連通圖的生成樹是包含該圖的所有頂點的（

）

A:極大連通子圖B:極大子圖C:極小子圖D:極小連通子圖

答案:極小連通子圖

具有n個頂點的連通有向圖中，至少需要（

）條邊。

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

答案:n

下列哪些算法是屬于圖的應用算法（

）

A:拓撲排序算法B:歐幾里德算法C:克魯斯卡爾（Kruskal）算法D:哈夫曼（Huffman）算法E:迪杰斯特拉（Dijkstra）算法

答案:拓撲排序算法;克魯斯卡爾（Kruskal）算法;迪杰斯特拉（Dijkstra）算法

下列（

）算法可用于構(gòu)造圖的生成樹。

A:FloydB:DFSC:PrimD:BFSE:kruskal

答案:DFS;Prim;BFS;kruskal

下列（

）是構(gòu)造最短路徑的方法。

A:PrimB:FloydC:KruskalD:BFSE:Dijkstra

答案:Floyd;Dijkstra

n個結(jié)點的無向圖，若沒有頂點到自身的邊，也沒有一個頂點到另一個頂點的多重邊，此時若有n(n-1)/2條邊，則該無向圖一定是連通圖。

A:對B:錯

答案:對

用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用空間大小與圖的頂點數(shù)有關，與圖的邊數(shù)無關。

A:對B:錯

答案:對

對于任意一個圖，從它的某個頂點出發(fā)進行一次深度或者廣度遍歷可以訪問到該圖的每個頂點。

A:對B:錯

答案:錯

對于無向圖的生成樹，從同一頂點出發(fā)所得的生成樹相同。

A:對B:錯

答案:錯

有向圖頂點v的度是其鄰接矩陣中第v行1的個數(shù)。

A:錯B:對

答案:錯

第八章測試

衡量一個查找算法執(zhí)行效率高低的最重要的指標是（）。

A:所需的內(nèi)存大小B:查找表中的元素個數(shù)C:查找過程中關鍵字比較的最大次數(shù)D:平均查找長度

答案:平均查找長度

對線性表進行二分查找時，要求線性表必須

（

）。

A:采用鏈接存儲結(jié)構(gòu)B:采用順序存儲結(jié)構(gòu)且元素按查找關鍵字有序排列C:采用鏈接存儲結(jié)構(gòu)且結(jié)點按查找關鍵字有序排列D:采用順序存儲結(jié)構(gòu)

答案:采用順序存儲結(jié)構(gòu)且元素按查找關鍵字有序排列

哈希查找中的沖突是指（

）。.

A:兩個元素的關鍵字值相同B:兩個元素的關鍵字值不同C:不同關鍵字值對應相同的存儲地址D:兩個元素具有相同序號

答案:不同關鍵字值對應相同的存儲地址

對于一棵二叉排序樹進行（）遍歷可得到按關鍵字有序排列的數(shù)據(jù)序列。

A:先序B:層序C:后序D:中序

答案:中序

順序查找適合于采用（

）存儲結(jié)構(gòu)的線性表。

A:順序或鏈式B:散列C:壓縮D:索引

答案:順序或鏈式

下面關于哈希查找的說法中，正確的是()

A:采用鏈地址法處理沖突時，若規(guī)定采用頭插法進行插入，則插入任何一個元素的時間是相同的B:鏈地址法處理沖突的平均查找長度小于線性探測和二次探測C:用鏈地址處理沖突，適合表長不確定的情況D:用鏈地址處理沖突，不會引起二次聚集的現(xiàn)象E:采用鏈地址法處理沖突時，查找任何一個元素的時間都相同

答案:采用鏈地址法處理沖突時，若規(guī)定采用頭插法進行插入，則插入任何一個元素的時間是相同的;鏈地址法處理沖突的平均查找長度小于線性探測和二次探測;用鏈地址處理沖突，適合表長不確定的情況;用鏈地址處理沖突，不會引起二次聚集的現(xiàn)象

以下關于二叉排序樹的說法中，正確的是()

A:對某棵二叉排序樹進行中序遍歷，一定能得到按關鍵字升序排列的有序序列B:二叉排序樹中右子樹上所有結(jié)點的關鍵字值均大于它的根結(jié)點C:二叉排序樹一定為一棵平衡二叉樹D:二叉排序樹中左子樹上所有結(jié)點的關鍵字值均小于它的根結(jié)點E:在二叉排序樹上的查找過程與折半查找過程類似

答案:對某棵二叉排序樹進行中序遍歷，一定能得到按關鍵字升序排列的有序序列;二叉排序樹中右子樹上所有結(jié)點的關鍵字值均大于它的根結(jié)點;二叉排序樹中左子樹上所有結(jié)點的關鍵字值均小于它的根結(jié)點;在二叉排序樹上的查找過程與折半查找過程類似

在一個結(jié)點值按照查找關鍵字有序排列的單鏈表上可以采用折半查找方法來提高查找速度。

A:錯B:對

答案:錯

折半查找過程所對應的判定樹一定是一棵平衡二叉樹。

A:錯B:對

答案:對

在任意一個數(shù)據(jù)表上，采用折半查找一定比采用順序查找的查找速度快。

A:對B:錯

答案:錯

在結(jié)點數(shù)確定的二叉排序樹上進行查找的平均查找長度與二叉樹的形態(tài)有關，最好的情況是二叉排序樹為平衡二叉樹的時候。

A:對B:錯

答案:對

折半查找的效率與二叉排序樹的查找效率是一樣的。

A:錯B:對

答案:錯

第九章測試

對同一組數(shù)據(jù)分別采用直接插入排序和折半插入排序進行排序，二者可能存在的不同之處在于（

）。

A:整個排序過程中的關鍵字比較次數(shù)B:整個排序過程中的元素移動次數(shù)C:占用的輔助內(nèi)存