數(shù)據(jù)結(jié)構(gòu)（天津大學）智慧樹知到答案章節(jié)測試2023年

第一章測試數(shù)據(jù)的存儲結(jié)構(gòu)是指（）

A:存儲在外存中的數(shù)據(jù)

B:數(shù)據(jù)在計算機中的順序存儲方式

C:數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示

D:數(shù)據(jù)所占的存儲空間量

答案:C算法的空間復雜度是指（）

A:算法執(zhí)行過程中所需要的存儲空間

B:算法程序所占的存儲空間

C:算法程序中的指令條數(shù)

D:算法程序的長度

答案:A下列敘述中正確的是（）

A:一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率

B:一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)

C:數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)

D:一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率

答案:D程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關。

A:對

B:錯

答案:A算法計算量的大小稱為計算的（）

A:現(xiàn)實性

B:復雜性

C:規(guī)模

D:效率

答案:B算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。

A:對

B:錯

答案:B抽象數(shù)據(jù)類型可通過固有的數(shù)據(jù)類型來表示和實現(xiàn)。

A:錯

B:對

答案:B算法是指令的有限序列。

A:錯

B:對

答案:B數(shù)據(jù)的不可分割的最小單位是數(shù)據(jù)元素。

A:對

B:錯

答案:B第二章測試下述哪個是順序存儲結(jié)構(gòu)的優(yōu)點？（）

A:刪除運算方便

B:存儲密度大

C:插入運算方便

D:可方便的用于各種邏輯結(jié)構(gòu)的存儲表示

答案:B若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。

A:循環(huán)鏈表

B:雙向鏈表

C:順序表

D:靜態(tài)鏈表

答案:C設線性表有n個元素，以下操作中在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高是（）

A:順序輸出這n個元素

B:交換第1個與第2個元素的值

C:輸出第i（1≤i≤n）個元素的值

D:輸出與給定值x相等的元素在線性表中的序號

答案:C在n個結(jié)點的線性表的順序?qū)崿F(xiàn)中，算法的時間復雜度為O(1)的操作是（）。

A:訪問第i個結(jié)點和求第i個結(jié)點的直接前驅(qū)

B:在第i個結(jié)點后插入一個新結(jié)點

C:以上都不對

D:刪除第i個結(jié)點

答案:A循環(huán)鏈表H尾結(jié)點p的特點是()。

A:p->next==H

B:p->next==H->next

C:p==H

D:p==H->next

答案:A向一個長度為n的順序表中的第i個元素之前插入一個元素時，需要向后移動()個元素。

A:i

B:n-i+1

C:n-i

D:1

答案:B在一個長度為n的順序表中刪除第i個元素時，需要向前移動()個元素。

A:i

B:n-i+1

C:1

D:n-i

答案:D鏈表的每個結(jié)點中都只包含一個指針。

A:對

B:錯

答案:B鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。

A:錯

B:對

答案:A當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。

A:錯

B:對

答案:A第三章測試對于棧操作數(shù)據(jù)的原則是（）。

A:后進先出

B:先進先出

C:后進后出

D:不分次序

答案:A隊列的先進先出特征是指()。

A:當同時進行插入、刪除操作時，總是插入操作優(yōu)先

B:每次從隊中刪除的元素總是最早插入的元素

C:每當有刪除操作時，總要先做一次插入操作

D:最后插入隊列的元素總是最后被刪除

答案:D棧和隊列的共同點是（）。

A:都是后進后出

B:都是先進先出

C:無共同點

D:只允許在端點處進行插入和刪除

答案:D設入棧序列為1,2,3,4,5,則可能得到的出棧序列為（）。

A:1,4,2,3,5

B:1,2,5,3,4

C:3,1,2,5,4

D:3,2,5,4,1

答案:D假設棧初始為空，將中綴表達式a/b+(cd-ef)/g轉(zhuǎn)化為等價的狗追表達式的過程中，當掃描到f時，棧中的元素依次是（）

A:/+-*

B:+(-

C:

+(-

D:/+(-

答案:C棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。

A:錯

B:對

答案:B在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。

A:錯

B:對

答案:A對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。

A:錯

B:對

答案:B棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。

A:對

B:錯

答案:B棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。

A:對

B:錯

答案:B第四章測試字符串采用節(jié)點大小為1的鏈表作為其存儲結(jié)構(gòu)，是指（）

A:鏈表中只存放一個字符

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

C:鏈表的長度為1

D:鏈表的每個鏈節(jié)點的數(shù)據(jù)域中不僅只存放了一個字符

答案:B串‘a(chǎn)babaaababaa’的next數(shù)組為（

）

A:0123012322345

B:012345678999

C:012121111212

D:011234223456

答案:D字符串‘a(chǎn)babaabab’的nextval為（

）

A:

0,1,0,1,0,1,0,1,1

B:

0,1,0,1,0,2,1,0,1

C:

0,1,0,1,0,0,0,1,1

D:

0,1,0,1,0,4,1,0,1

答案:D空串與空格字符組成的串它們的區(qū)別在于（

）

A:沒有區(qū)別

B:兩串包含的字符不相同

C:兩串的長度相等

D:兩串的長度不相等

答案:D一個子串在包含它的主串中的位置是指什么（

）

A:子串的第一個字符在主串中的位置

B:子串的第一個字符在主串中首次出現(xiàn)的位置

C:子串的最后那個字符在主串中的位置

D:子串的最后那個字符在主串中首次出現(xiàn)的位置

答案:B如果一個串中的所有字符均在另一串中出現(xiàn)，那么這說明前者是后者的子串。

A:對

B:錯

答案:B求子串在串中首次出現(xiàn)位置的運算叫做串的模式匹配。此表述

A:對

B:錯

答案:A一個長度為n（n>0）的串的子串有n（n+1）/2個。

A:對

B:錯

答案:A如果兩個串含有相同的字符集，則這兩者相等。

A:對

B:錯

答案:BKMP算法的特點是在模式匹配時指示模式串的指針不會變小。（

）

A:錯

B:對

答案:A第五章測試常對數(shù)組進行的兩種基本操作是（

）

A:索引與修改

B:建立與刪除

C:查找與索引

D:查找與修改

答案:DA[N，N]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組T[N(N+I)/2]中，則對任一上三角元素a[i][j]對應T[k]的下標k是(

)。

A:

i(j-i)/2+1

B:

i(i-l)/2+j

C:

j(j-l)/2+i

D:

j(i-l)/2+1

答案:C所謂稀疏矩陣指的是(

)

A:包含有零元素的矩陣

B:零元素個數(shù)占矩陣元素中總個數(shù)一半的矩陣

C:零元素個數(shù)較多的矩陣

D:零元素個數(shù)遠遠多于非零元素個數(shù)且分布沒有規(guī)律的矩陣

答案:D廣義表（（a,b,c,d））的表頭是（

），表尾是（

）。

A:

（a,b,c,d）

B:

（）

C:

（b,c,d）

D:

a

答案:AB用數(shù)組r存儲靜態(tài)鏈表，結(jié)點的next域指向后繼，工作指針j指向鏈中結(jié)點，使j沿鏈移動的操作為(

)。

A:

j=j+1

B:

j=r[j].next

C:

j=r[j]->next

D:

j=j->next

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

）

A:錯

B:對

答案:A一個稀疏矩陣Amn采用三元組形式表示，若把三元組中有關行下標與列下標的值互換，并把m和n的值互換，則就完成了Amn的轉(zhuǎn)置運算。（

）

A:對

B:錯

答案:B廣義表的取表尾運算，其結(jié)果通常是個表，但有時也可是個單元素值。（

）

A:錯

B:對

答案:A有一個100×90的稀疏矩陣，非0元素有10個，設每個整型數(shù)占兩字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是(

)。

A:

33

B:

66

C:

60

D:

18000

答案:B數(shù)組是一種復雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關系既不是線性的，也不是樹形的。（

）

A:錯

B:對

答案:A第六章測試以下說法錯誤的是（

）

A:任何只含一個結(jié)點的集合是一棵樹

B:樹形結(jié)構(gòu)的特點是一個結(jié)點可以有多個直接前趨

C:樹形結(jié)構(gòu)中的一個結(jié)點至多只有一個直接后繼

D:樹(及一切樹形結(jié)構(gòu))是一種”分支層次”結(jié)構(gòu)

答案:B設森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（

）。

A:

M1+M2

B:

M1

C:

M3

D:

M2+M3

答案:D在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒（

）

A:左子結(jié)點，右子結(jié)點和兄弟結(jié)點

B:左子結(jié)點

C:右子結(jié)點

D:左子結(jié)點和右子結(jié)點

答案:D一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有(

)結(jié)點。

A:

2h

B:

h+1

C:

2h+1

D:

2h-1

答案:D已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷是（

）。

A:

acbed

B:

cedba

C:

decab

D:

deabc

答案:B二叉樹的遍歷只是為了在應用中找到一種線性次序。（

）

A:對

B:錯

答案:A用鏈表(llink-rlink)存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n-1個空指針。（

)

A:錯

B:對

答案:A中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列。(

)

A:錯

B:對

答案:B

用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。(

)

A:錯

B:對

答案:A非空二叉樹上葉結(jié)點數(shù)等于雙分支結(jié)點數(shù)加1。(

)

A:對

B:錯

答案:A第七章測試求最短路徑的Dijkstra算法的時間復雜度是（）

A:O(n)

B:O(n+e)

C:O(nn)

D:O(ne)

答案:C在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（

)倍。

A:

2

B:

1

C:

1/2

D:

4

答案:A有8個結(jié)點的無向圖最多有

條邊。

A:112

B:56

C:14

D:28

答案:D用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用(

)來實現(xiàn)算法的。

A:棧

B:樹

C:圖

D:隊列

答案:D圖的深度優(yōu)先遍歷類似于二叉樹的

。

A:先序遍歷

B:后序遍歷

C:層次遍歷

D:中序遍歷

答案:A一個有向圖的鄰接表和逆鄰接表中的結(jié)點個數(shù)一定相等。（

）

A:對

B:錯

答案:A在n個頂點的無向圖中，若邊數(shù)大于n-1，則該圖必是連通圖。（

）

A:對

B:錯

答案:A若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲序列必定存在。（

）

A:錯

B:對

答案:B對任意一個圖，從某頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問圖的所有頂點。（

）

A:對

B:錯

答案:B圖G的生成樹是該圖的一個極小連通子圖。（

）

A:錯

B:對

答案:A第八章測試查找相同結(jié)點的效率折半查找總比順序查找高。（）

A:錯

B:對

答案:A對無序表用折半查找比順序查找快。（）

A:錯

B:對

答案:A二叉排序樹按照中序遍歷將各結(jié)點打印出來，將得到按照從小到大的排列。（）

A:對

B:錯

答案:A二叉排序樹一定是滿二叉樹。（）

A:錯

B:對

答案:A當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前者比后者的查找速度(

)

A:在大部分情況下要快

B:不一定

C:取決于表遞增還是遞減

D:必定快

答案:A若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為(

)。

A:

(n+1)/2

B:

n

C:

n/2

D:

(n-1)/2

答案:A二分法查找的時間復雜性為（

）。

A:

O（nlogn）

B:

O（n）

C:

O（n2）

D:

O（logn）

答案:D下面關于哈希(Hash，雜湊)查找的說法正確的是(

)。

A:除留余數(shù)法是所有哈希函數(shù)中最好的

B:若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單的將該元素刪去即可

C:不存在特別好與壞的哈希函數(shù)，要視情況而定

D:哈希函數(shù)構(gòu)造的越復雜越好，因為這樣隨機性好，沖突小

答案:C設二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均查找長度為（

）。

A:O(n)

B:O(n2)

C:O(1)

D:

O(log2n)

答案:D負載因子(裝填因子)是哈希表的一個重要參數(shù)，它反映哈希表的裝滿程度。（

）

A:對

B:錯

答案:A第九章測試某排序方法的穩(wěn)定性是指(

)

A:平均時間為0（nlogn）的排序方法

B:該排序算法允許有相同的關鍵字記錄

C:以上都不對

D:該排序算法不允許有相同的關鍵字記錄

答案:C下面四種排序方法中，排序過程中的比較次數(shù)與排序方法無關的是(

)

A:插入排序法

B:選擇排序法

C:快速排序法

D:堆積排序法

答案:B下列排序方法中，哪一個是穩(wěn)定的排序方法？（

）

A:二分法插入排序

B:快速排序

C:希爾排序

D:直接選擇排序

答案:A對一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為：（1）8447251521

（2）1547258421

（3）1521258447

（4）1521254784，則采用的排序是(