數(shù)據(jù)結(jié)構(gòu)與算法知到智慧樹章節(jié)測試課后答案2024年秋山東石油化工學(xué)院

數(shù)據(jù)結(jié)構(gòu)與算法知到智慧樹章節(jié)測試課后答案2024年秋山東石油化工學(xué)院第一章單元測試

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

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

答案:數(shù)據(jù)對(duì)象是帶結(jié)構(gòu)的數(shù)據(jù)元素的子集數(shù)據(jù)結(jié)構(gòu)的定義是（）。

A:相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合B:數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C:一種數(shù)據(jù)類型D:一組性質(zhì)相同的數(shù)據(jù)元素的集合

答案:相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。

A:邏輯和存儲(chǔ)B:存儲(chǔ)C:邏輯D:物理

答案:邏輯數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指（）。

A:數(shù)據(jù)的邏輯結(jié)構(gòu)B:數(shù)據(jù)結(jié)構(gòu)C:數(shù)據(jù)元素之間的關(guān)系D:數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

答案:數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)（）。

A:數(shù)據(jù)的存儲(chǔ)方法B:數(shù)據(jù)的處理方法C:數(shù)據(jù)元素的類型D:數(shù)據(jù)元素之間的關(guān)系

答案:數(shù)據(jù)元素之間的關(guān)系在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。

A:緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)B:動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C:線性結(jié)構(gòu)和非線性結(jié)構(gòu)D:內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

答案:線性結(jié)構(gòu)和非線性結(jié)構(gòu)可以用（）定義一個(gè)完整的數(shù)據(jù)結(jié)構(gòu)。

A:數(shù)據(jù)關(guān)系B:抽象數(shù)據(jù)類型C:數(shù)據(jù)元素D:數(shù)據(jù)對(duì)象

答案:抽象數(shù)據(jù)類型數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括（）。

A:邏輯結(jié)構(gòu)和物理結(jié)構(gòu)B:線性結(jié)構(gòu)和非線性結(jié)構(gòu)C:虛擬結(jié)構(gòu)和抽象結(jié)構(gòu)D:連續(xù)結(jié)構(gòu)和非連續(xù)結(jié)構(gòu)

答案:連續(xù)結(jié)構(gòu)和非連續(xù)結(jié)構(gòu)計(jì)算機(jī)算法指的是解決問題的步驟序列，它必須具備（）這五個(gè)特性。

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

答案:可執(zhí)行性、確定性、有窮性、輸入、輸出算法的時(shí)間復(fù)雜度取決于（）。

A:待處理數(shù)據(jù)的初態(tài)B:算法執(zhí)行的實(shí)際時(shí)間C:問題的規(guī)模D:問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)

答案:問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)在下面的程序段中，對(duì)x的賦值的語句頻度為（）。

for(i=0;i<n;i++)

for(j=0;j<n;j++)

x=x+1;

A:O(n)B:O(n2)C:O(2n)D:O(log2n)

答案:O(n2)下面的程序段中，n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）

for(i=n-1;i>=1;i--)

for(j=1;j<=i;j++)

if(A[j]>A[j+1])

A[j]與A[j+1]對(duì)換；

A:O(n)B:O(n3)C:O(nlog2n)D:O(n2)

答案:O(n2)算法分析的目的是（）。

A:研究算法中的輸入和輸出的關(guān)系B:分析算法的效率以求改進(jìn)C:找出數(shù)據(jù)結(jié)構(gòu)的合理性D:分析算法的易懂性和文檔性

答案:分析算法的效率以求改進(jìn)算法指的是（）。

A:求解特定問題的指令有限序列B:解決問題的方法C:計(jì)算機(jī)程序D:查找或排序過程

答案:求解特定問題的指令有限序列算法的效率主要是指（）

A:其他說法都不對(duì)B:算法的時(shí)間效率C:算法的空間效率D:算法的空間效率和時(shí)間效率

答案:算法的空間效率和時(shí)間效率試分析下面各程序段的時(shí)間復(fù)雜度為（）。

i=1;

while(i<=n)

i=i*3;

A:O(n)B:O(1)C:O(log3n)D:O(log2n)

答案:O(log3n)計(jì)算下列程序的漸進(jìn)時(shí)間復(fù)雜度為（）。

x=n;//n>1

y=0;

while(x≥(y+1)*(y+1))

y++;

A:O(n)B:O(1)C:O(sqrt(n))D:O(log3n)

答案:O(sqrt(n))

第二章單元測試

線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。

A:索引存取B:散列存取C:順序存取D:隨機(jī)存取

答案:隨機(jī)存取對(duì)線性表的定義是（）。

A:一個(gè)有限序列，可以為空?B:一個(gè)無限序列，不可以為空C:一個(gè)無限序列，可以為空D:一個(gè)有限序列，不可以為空

答案:一個(gè)有限序列，可以為空?線性結(jié)構(gòu)的數(shù)據(jù)元素之間存在一種（）。

A:多對(duì)多關(guān)系B:多對(duì)一關(guān)系C:一對(duì)一關(guān)系D:一對(duì)多關(guān)系

答案:一對(duì)一關(guān)系有關(guān)線性表L=(a1，a2,……an)，下列說法正確的是（）。

A:每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B:表中諸元素的排列必須是由小到大或由大到小C:線性表中至少有一個(gè)元素D:除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。

答案:除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。以下關(guān)于順序表的說法中，正確的是（）。

A:在順序表中每一元素的數(shù)據(jù)類型還可以是順序表B:順序表可以利用一維數(shù)組表示,因此順序表與一維數(shù)組在結(jié)構(gòu)上是一致的，它們可以通用C:順序表和一維數(shù)組一樣,都可以按下標(biāo)隨機(jī)(或直接)訪問，順序表還可以從某一指定元素開始,向前或向后逐個(gè)元素順序訪問D:在順序表中,邏輯上相鄰的元素在物理位置上不一定相鄰

答案:順序表和一維數(shù)組一樣,都可以按下標(biāo)隨機(jī)(或直接)訪問，順序表還可以從某一指定元素開始,向前或向后逐個(gè)元素順序訪問順序表具有的特點(diǎn)是（）。

A:不必事先估計(jì)存儲(chǔ)空間B:插入、刪除不需要移動(dòng)元素C:可隨機(jī)訪問任一元素D:所需空間不必連續(xù)

答案:可隨機(jī)訪問任一元素若長度為n的順序表在其第i個(gè)位置插入一個(gè)新元素，需移動(dòng)的元素個(gè)數(shù)是（）。

A:n-i+1B:n-iC:iD:n

答案:n-i+1向一個(gè)有126個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)的元素個(gè)數(shù)為（）。

A:8B:63.5C:7D:63

答案:63假設(shè)刪除長度為n的順序表中的每個(gè)元素的概率相同，則刪除一個(gè)元素平均要移動(dòng)的元素個(gè)數(shù)是（）。

A:(n+1)/2B:(n-1)/2C:nD:n/2

答案:(n-1)/2假設(shè)長度為127的順序表，在任意位置上插入和刪除元素都是等概率的，刪除一個(gè)新元素時(shí)需平均移動(dòng)表中的（）個(gè)元素。

A:64B:63C:63.5D:127

答案:63若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）(1<=i<=n+1)。

A:O(n2)B:O(1)C:O(n)D:O(0)

答案:O(n)在長度為n的順序表中刪除一個(gè)元素的時(shí)間復(fù)雜度為（）。

A:O(n^2)B:O(1)C:O(log2n)D:O(n)

答案:O(n)若設(shè)一個(gè)順序表的長度為n,那么，在表中順序查找一個(gè)值為x的元素時(shí)，在等概率的情況下，查找成功的數(shù)據(jù)平均比較次數(shù)為（）。

A:(n+1)/2B:(n-1)/2C:NULLD:n

答案:(n+1)/2在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(n)的操作是（）。

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

答案:在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。

A:部分地址必須是連續(xù)的B:必須是連續(xù)的C:連續(xù)或不連續(xù)都可以D:一定是不連續(xù)的

答案:連續(xù)或不連續(xù)都可以在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語句應(yīng)為（）。

A:s->next=p->next;p->next=s;B:s->next=p->next;p->next=s->next;C:(*p).next=s;(*s).next=(*p).next;D:s->next=p+1;p->next=s;

答案:s->next=p->next;p->next=s;已知L是帶頭結(jié)點(diǎn)的單鏈表，則刪除首元結(jié)點(diǎn)的語句是（）。

A:L->next=L->next->next;B:L->next=L;C:L=L->next;D:L=L->next->next;

答案:L->next=L->next->next;在一個(gè)單鏈表中,若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)q(注:P既不是第一個(gè)結(jié)點(diǎn),也不是最后一個(gè)結(jié)點(diǎn))，則執(zhí)行（）操作。

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

答案:p-next=q->next;單鏈表的存儲(chǔ)結(jié)構(gòu)中增加了一個(gè)頭結(jié)點(diǎn)，關(guān)于頭結(jié)點(diǎn)的描述中，下面哪一項(xiàng)是錯(cuò)誤的（）

A:在單鏈表中增加頭結(jié)點(diǎn)，插入或刪除首元結(jié)點(diǎn)時(shí)不必進(jìn)行特殊處理B:若鏈表中有頭結(jié)點(diǎn)，則頭指針一定不為空C:頭結(jié)點(diǎn)中不存儲(chǔ)鏈表的數(shù)據(jù)元素，而是一些諸如表長之類的輔助信息D:有沒有頭結(jié)點(diǎn)對(duì)算法執(zhí)行的效率沒有任何影響

答案:有沒有頭結(jié)點(diǎn)對(duì)算法執(zhí)行的效率沒有任何影響帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。

A:head!=NULLB:head->next==NULLC:head->next==LD:head==NULL

答案:head->next==NULL單鏈表的存儲(chǔ)密度（）。

A:等于1B:不能確定C:大于1D:小于1

答案:小于1以下關(guān)于單鏈表的敘述中，不正確的是（）。

A:結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲(chǔ)密度小于順序存儲(chǔ)結(jié)構(gòu)B:可以通過頭結(jié)點(diǎn)直接計(jì)算第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址C:插入、刪除運(yùn)算操作方便，不必移動(dòng)結(jié)點(diǎn)D:邏輯上相鄰的元素物理上不必相鄰

答案:可以通過頭結(jié)點(diǎn)直接計(jì)算第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址單鏈表又稱線性鏈表，在單鏈表上實(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)指針單鏈表又稱線性鏈表，在單鏈表上實(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)指針在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（）。

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

答案:q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（）。

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

答案:p->next->prior=p->prior;p->prior->next=p->next;以下鏈表結(jié)構(gòu)中，從當(dāng)前結(jié)點(diǎn)出發(fā)能夠訪問到任一結(jié)點(diǎn)的是（）。

A:雙向鏈表和循環(huán)鏈表?B:單向鏈表、雙向鏈表和循環(huán)鏈表C:單向鏈表和循環(huán)鏈表D:單向鏈表和雙向鏈表

答案:雙向鏈表和循環(huán)鏈表?循環(huán)鏈表的主要特點(diǎn)是（）

A:在進(jìn)行插入刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開B:已知某個(gè)結(jié)點(diǎn)的位置后，能容易找到它的直接前驅(qū)C:在鏈表的任意位置出發(fā)都能掃描到整個(gè)鏈表D:不再需要頭指針了

答案:在鏈表的任意位置出發(fā)都能掃描到整個(gè)鏈表雙向鏈表的主要特點(diǎn)是（）

A:已知某個(gè)結(jié)點(diǎn)的位置后，能容易找到它的直接前驅(qū)B:在鏈表的任意位置出發(fā)都能掃描到整個(gè)鏈表C:不再需要頭指針了D:在進(jìn)行插入刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開

答案:已知某個(gè)結(jié)點(diǎn)的位置后，能容易找到它的直接前驅(qū)線性表Ｌ在（）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。

A:需不斷對(duì)Ｌ進(jìn)行刪除插入B:Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜C:Ｌ中含有大量的結(jié)點(diǎn)D:需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值

答案:需不斷對(duì)Ｌ進(jìn)行刪除插入若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。

A:帶頭結(jié)點(diǎn)的雙循環(huán)鏈表B:順序表C:雙鏈表D:單循環(huán)鏈表

答案:順序表某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A:僅有尾指針的單循環(huán)鏈表B:循環(huán)鏈表C:單鏈表D:雙鏈表

答案:僅有尾指針的單循環(huán)鏈表

第三章單元測試

棧是一種受限的線性結(jié)構(gòu)，其操作特點(diǎn)是（）。

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

答案:先進(jìn)后出若讓元素1,2,3,4,5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種情況。

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

答案:4,3,1,2,5若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pj為（）。

A:jB:n-jC:不確定D:n-j+1

答案:n-j+1判定一個(gè)順序棧ST(最多元素?cái)?shù)為m)為滿的的條件是ST->top==m0-1，則其為空的條件是（）。

A:ST->top=mB:ST->top<>mC:ST->top<>0D:ST->top==-1

答案:ST->top==-1以下關(guān)于順序棧的操作，正確的是（）。

A:棧是一種對(duì)進(jìn)棧和出棧操作的次序做了限制的線性表B:若一個(gè)棧的存儲(chǔ)空間為S[n]，則對(duì)棧的進(jìn)棧和出棧操作最多只能執(zhí)行n次C:空棧沒有棧頂指針D:n個(gè)元素進(jìn)入一個(gè)順序棧后，如果一次性進(jìn)棧完畢再出棧，它們的出棧順序一定與進(jìn)棧順序相反

答案:n個(gè)元素進(jìn)入一個(gè)順序棧后，如果一次性進(jìn)棧完畢再出棧，它們的出棧順序一定與進(jìn)棧順序相反向一個(gè)棧頂指針為top的不帶頭結(jié)點(diǎn)的鏈棧中插人一個(gè)*S結(jié)點(diǎn)的時(shí)候，應(yīng)當(dāng)執(zhí)行語句（）。

A:S->next＝top->next；top->next＝S；B:S->next=top；top=S；C:top->next=S;D:S->next＝top；top＝S->next；

答案:S->next=top；top=S；向一個(gè)帶頭結(jié)點(diǎn)、棧頂指針為top的鏈棧中插人一個(gè)*S結(jié)點(diǎn)的時(shí)候，應(yīng)當(dāng)執(zhí)行語句（）。

A:S->next=top->next；top->next=S；B:top->next=S；C:S->next=top；top=S；D:S->next=top；top=S->next；

答案:S->next=top->next；top->next=S；算術(shù)表達(dá)式a+b*(c+d)/e轉(zhuǎn)為后綴表達(dá)式后為（）。

A:abcde*/++B:abcde/+*+C:abcde/*++D:abcd+*e/+

答案:abcd+*e/+設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。

A:隊(duì)列B:線性表的順序存儲(chǔ)結(jié)構(gòu)C:棧D:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

答案:棧鏈?zhǔn)綏５拇鎯?chǔ)結(jié)構(gòu)為(data,next)，top和bottom分別是指向棧頂和棧底的指針，此時(shí)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，則應(yīng)執(zhí)行操作是（）。

A:p->next=top;top=p;B:p->next=top;top=p->link;C:p->next=top->next;top=p;D:p->next=top;top->next=p;

答案:p->next=top;top=p;向一個(gè)棧頂指針為top的不帶頭結(jié)點(diǎn)的鏈棧中插人一個(gè)*S結(jié)點(diǎn)的時(shí)候，應(yīng)當(dāng)執(zhí)行語句（）。

A:S->next=top;top=S;B:S->next=top;top=S->next;C:top->next=S;D:S->next=top->next;top->next=S;

答案:S->next=top;top=S;鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top指向棧頂。若想刪除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行操作（）。

A:top=top->link;x=top->link；B:x=top;top=top->link；C:x=top->data;top=top->link；D:x=top->link；

答案:x=top->data;top=top->link；以下會(huì)用到棧的應(yīng)用的是（）。

A:其他選項(xiàng)均有可能B:子程序調(diào)用C:括號(hào)匹配D:遞歸

答案:其他選項(xiàng)均有可能實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用（）數(shù)據(jù)結(jié)構(gòu)。

A:鏈表B:數(shù)組C:棧D:堆

答案:棧隊(duì)列是一種受限的線性結(jié)構(gòu)，其操作原則是（）。

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

答案:先進(jìn)先出判定一個(gè)順序隊(duì)列Q(最多有n個(gè)元素)為滿的條件是（）。

A:Q->rear+1==Q->frontB:Q->rear-Q->front+1==nC:Q->rear-Q->front==nD:Q->rear==Q->front

答案:Q->rear-Q->front==n判定一個(gè)順序循環(huán)隊(duì)列Q(最多有n個(gè)元素)為空的條件是（）。

A:Q->front==(Q->rear+1)%nB:Q->rear==Q->frontC:Q->rear==Q->front+1D:Q->front==(Q->rear-1)%n

答案:Q->rear==Q->front最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)滿的條件是（）。

A:(rear-l)%n==frontB:rear+1==frontC:(rear+1)%n==frontD:rear==front

答案:(rear+1)%n==front數(shù)組Ｑ[ｎ]用來表示一個(gè)循環(huán)隊(duì)列，front為當(dāng)前隊(duì)列頭元素的前一位置，rear為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）。

A:(n+rear-front)%nB:n+rear-frontC:rear-frontD:(n+front-rear)%n

答案:(n+rear-front)%n循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（）。

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

答案:rear=(rear+1)%(m+1)隊(duì)列的插入操作在（）進(jìn)行。

A:任意位置B:指定位置C:rear所指的位置D:front所指的位置

答案:rear所指的位置一個(gè)隊(duì)列的進(jìn)隊(duì)順序是1,2,3,4,則該隊(duì)列可能的輸出序列是（）。

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

答案:1,2,3,4對(duì)于鏈?zhǔn)疥?duì)列，在執(zhí)行插入操作時(shí)（）。

A:頭、尾指針都要修改B:僅修改頭指針C:僅修改尾指針D:頭、尾指針可能都要修改

答案:頭、尾指針可能都要修改用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行出隊(duì)運(yùn)算時(shí)（）。

A:頭、尾指針可能都要修改B:頭、尾指針都要修改C:僅修改尾指針D:僅修改頭指針

答案:頭、尾指針可能都要修改用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（）。

A:僅修改隊(duì)頭指針B:隊(duì)頭、隊(duì)尾指針都要修改C:僅修改隊(duì)尾指針D:隊(duì)頭、隊(duì)尾指針可能都要修改

答案:隊(duì)頭、隊(duì)尾指針可能都要修改在帶頭結(jié)點(diǎn)的鏈接方式存儲(chǔ)的隊(duì)列中，在進(jìn)行入隊(duì)運(yùn)算時(shí)（）。

A:僅修改頭指針B:僅修改尾指針C:頭、尾指針可能都要修改D:頭、尾指針都要修改

答案:僅修改尾指針在帶頭結(jié)點(diǎn)的鏈接方式存儲(chǔ)的隊(duì)列中，在進(jìn)行出隊(duì)運(yùn)算時(shí)（）。

A:頭、尾指針都要修改B:僅修改頭指針C:頭、尾指針都可能不需要修改D:僅修改尾指針

答案:頭、尾指針都可能不需要修改為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。

A:線性表B:隊(duì)列C:棧D:有序表

答案:隊(duì)列某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，若元素a,b,c,d,e依次入此隊(duì)列后再進(jìn)行出隊(duì)操作，則不可能得到的出隊(duì)序列是()。

A:b,a,c,d,e

B:d,b,a,c,e

C:e,c,b,a,d

D:d,b,c,a,e

答案:d,b,c,a,e

第四章單元測試

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

A:可以順序存儲(chǔ)B:數(shù)據(jù)元素沒限制C:可以鏈?zhǔn)酱鎯?chǔ)D:數(shù)據(jù)元素是字符

答案:數(shù)據(jù)元素是字符與線性表相比，串的插入和刪除操作的特點(diǎn)是（）。

A:通常以串整體作為操作對(duì)象B:涉及移動(dòng)元素更多C:算法的時(shí)間復(fù)雜度較高D:需要更多的輔助空間

答案:通常以串整體作為操作對(duì)象判斷兩個(gè)字符串相等是指（）。

A:兩個(gè)串長度相等且含有相同的字符集B:兩個(gè)串的長度相等且對(duì)應(yīng)位置的字符相同C:兩個(gè)串的長度相等D:兩個(gè)串含有相同的字符集

答案:兩個(gè)串的長度相等且對(duì)應(yīng)位置的字符相同在串的簡單模式匹配中(BF)，當(dāng)模式串位j與目標(biāo)串位i比較時(shí),兩字符不相等，則i的位移方式是（）。(下標(biāo)從0開始)

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

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

A:i不變或者移動(dòng)到下一位置B:j不變C:j=next[j]D:i=next[j]

答案:i不變或者移動(dòng)到下一位置串的長度是指（）。

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

答案:串中所含字符的個(gè)數(shù)下面關(guān)于串的敘述中，正確的是（）。

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

答案:串是一種特殊的線性表若串str=“Software”,其子串的個(gè)數(shù)是（）。

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

答案:37空串與空格串（）。

A:不相同B:無法確定C:可能相同D:相同

答案:不相同一個(gè)子串在包含它的主串中位置是指（）。

A:子串的第一個(gè)字符在主串中首次出現(xiàn)的位置B:子串的最后那個(gè)字符在主串中的位置C:子串的最后那個(gè)字符在主串中首次出現(xiàn)的位置D:子串的第一個(gè)字符在主串中的位置

答案:子串的第一個(gè)字符在主串中首次出現(xiàn)的位置設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱做（）。

A:求串長B:求子串C:模式匹配D:連接

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

A:j不變B:j=next[j]C:i=next[j]D:i不變或者移動(dòng)到下一位置

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

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

答案:j=next[j]已知字符串s為"abcacaabaabcc"，模式串t為"babaabc"。采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失配”(s[i]!=t[j])時(shí),i=j=0,則下次開始匹配時(shí)，i和j的值分別是（）

A:i=1,j=0B:i=0,j=-1C:i=2,j=0D:i=1,j=2

答案:i=1,j=0設(shè)主串的長度為n，子串的長度為m，那么BF算法的時(shí)間復(fù)雜度和KMP算法的時(shí)間復(fù)雜度為（）

A:O(nxm)，O(n+m)B:O(m)，O(n)C:O(n)，O(m)D:O(n+m)，O(nxm)

答案:O(nxm)，O(n+m)字符串“ababaabab”的next數(shù)組為（）。

A:(-1,0,0,1,2,3,1,2,3)B:(-1,0,-1,0,-1,1,0,-1,0)C:(-1,0,-1,0,-1,0,-1,0,0)D:(-1,0,-1,0,-1,-1,-1,0,0)

答案:(-1,0,0,1,2,3,1,2,3)

第五章單元測試

一個(gè)稀疏矩陣采用壓縮后，和直接采用二維數(shù)組存儲(chǔ)相比會(huì)失去（）特性。

A:隨機(jī)存取B:順序存儲(chǔ)C:ABC都不對(duì)D:輸入輸出

答案:隨機(jī)存取假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[0..8,0..8](9行*9列)，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為0，則LOC[5,5]=（）。

A:102B:100C:88D:89

答案:100設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址A開始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5,8]的存儲(chǔ)首地址為（）。

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

答案:BA+180在二維數(shù)組A[9][10]中，每個(gè)數(shù)組元素占用3個(gè)字節(jié)，從首地址base開始按行連續(xù)存放。在這種情況下，元素A[8][5]的地址為（）。

A:base+141B:base+222C:base+144D:base+255

答案:base+255若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（i<j）的位置k的關(guān)系為（）。

A:j*(j-1)/2+iB:i*(i+1)/2+jC:j*(j+1)/2+iD:i*(i-1)/2+j

答案:j*(j-1)/2+i將一個(gè)A[1..100,1..100]的三對(duì)角矩陣，按行序優(yōu)先存入一維數(shù)組B[1..298]中，A中元素A66,66，在B數(shù)組中的位置K為（）。

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

答案:196對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是（）。

A:便于進(jìn)行矩陣運(yùn)算B:便于輸入和輸出C:節(jié)省存儲(chǔ)空間D:降低運(yùn)算的時(shí)間復(fù)雜度

答案:節(jié)省存儲(chǔ)空間稀疏矩陣常用的壓縮存儲(chǔ)方法有（）。

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

答案:三元組和十字鏈表有一個(gè)100*90的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是（）。

A:18000B:33C:66D:60

答案:66

第六章單元測試

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

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

答案:n-1在一棵度為4的樹T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹T的葉結(jié)點(diǎn)個(gè)數(shù)是（）

A:82B:113C:41D:122

答案:82表達(dá)人類社會(huì)中的族譜關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為（）。

A:線性表B:數(shù)組C:樹D:圖

答案:樹不含任何結(jié)點(diǎn)的空樹（）。

A:是一棵二叉樹;B:是一棵樹;C:是一棵樹也是一棵二叉樹;D:既不是樹也不是二叉樹

答案:是一棵樹也是一棵二叉樹;有關(guān)二叉樹下列說法正確的是（）。

A:二叉樹中每個(gè)結(jié)點(diǎn)的度都為2B:一棵二叉樹的度可以小于2C:二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2D:二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2

答案:一棵二叉樹的度可以小于2在一棵高度為k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（）。

A:2kB:2k-1C:2k-1D:2k-1+1

答案:2k-1若一棵完全二叉樹中某結(jié)點(diǎn)無左孩子，則該結(jié)點(diǎn)一定是（）。

A:葉子結(jié)點(diǎn)B:分支結(jié)點(diǎn)C:度為2的結(jié)點(diǎn)D:度為1的結(jié)點(diǎn)

答案:葉子結(jié)點(diǎn)一棵完全二叉樹上有98個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。

A:48B:51C:50D:49

答案:49某二叉樹中有60個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)為（）。

A:不一定B:60C:59D:61

答案:59一個(gè)具有129個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）。

A:7B:8C:8至129之間D:7至129之間

答案:8至129之間對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用（）遍歷實(shí)現(xiàn)編號(hào)。

A:后序B:中序C:從根開始按層次遍歷D:先序

答案:后序二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（）。

A:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用B:不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ);C:不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ);D:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)

答案:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)一棵有124個(gè)葉子結(jié)點(diǎn)的完全二叉樹最多有（）個(gè)結(jié)點(diǎn)。

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

答案:248在有10個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，空指針數(shù)為（）。

A:10B:11C:不定D:9

答案:11已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷的結(jié)果為（）。

A:FEDCBAB:CBEDFAC:不確定D:CBEFDA

答案:CBEFDAn個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（）。

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

答案:n+1引入二叉線索樹的目的是（）。

A:為了能在二叉樹中方便的進(jìn)行插入與刪除B:為了能方便的找到雙親C:加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度D:使二叉樹的遍歷結(jié)果唯一

答案:加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度一個(gè)具有129個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）。

A:7至129之間B:8至129之間C:8D:7

答案:8至129之間如果二叉樹T2是由一棵樹T1轉(zhuǎn)換而來的二叉樹，那么T1中結(jié)點(diǎn)的先根序列對(duì)應(yīng)T2的（）序列。

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

答案:先序遍歷設(shè)哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（）個(gè)葉子結(jié)點(diǎn)。

A:102B:101C:100D:99

答案:100由權(quán)值為7,19,2,6,32,3,21,10的結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長度為（）。

A:241B:271C:261D:231

答案:261有一電文共使用8種字符abcdefgh，各字符出現(xiàn)的次數(shù)分別為3，31，6，8，16，21，4，11。構(gòu)造赫夫曼樹，為這8個(gè)字符設(shè)計(jì)赫夫曼編碼，并求出用赫夫曼編碼傳送電文的總長度為___bit。

答案:219拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有___個(gè)前驅(qū)頂點(diǎn)的過程來完成的。

答案:0

第七章單元測試

在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的（）倍。

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

答案:2具有n個(gè)頂點(diǎn)的有向圖最多有（）條邊。

A:n(n+1)B:n(n-1)C:nD:n2

答案:n(n-1)在無向圖中定義頂點(diǎn)的度為與它相關(guān)聯(lián)的（）的數(shù)目。

A:權(quán)值B:權(quán)C:邊D:頂點(diǎn)

答案:邊具有n個(gè)頂點(diǎn)且每一對(duì)不同的頂點(diǎn)之間都有一條邊的無向圖被稱為（）。

A:無向強(qiáng)連通圖B:無向完全圖C:無向樹圖D:無向連通圖

答案:無向完全圖在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為s，則所有頂點(diǎn)的入度之和為（）。

A:nB:s+1C:sD:s-1

答案:s有8個(gè)結(jié)點(diǎn)的無向連通圖最少有（）條邊。

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

答案:7無向圖的鄰接矩陣是一個(gè)（）。

A:零矩陣B:對(duì)角矩陣C:上三角矩陣D:對(duì)稱矩陣

答案:對(duì)稱矩陣在無向圖G的鄰接矩陣A中，若A[i,j]等于1，則A[j,i]等于（）。

A:i+jB:0C:1D:i-j

答案:1下列說法中正確的是（）。

A:一個(gè)圖的鄰接矩陣表示不唯一，鄰接表表示也不唯一B:一個(gè)圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一C:一個(gè)圖的鄰接矩陣表示不唯一，鄰接表表示唯一D:一個(gè)圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一

答案:一個(gè)圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一圖是非線性數(shù)據(jù)結(jié)構(gòu)，關(guān)于其存儲(chǔ)結(jié)構(gòu)，正確的描述是（）。

A:它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)B:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用C:它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)D:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能使用

答案:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能使用由一個(gè)具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有（）條邊。

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

答案:n-1用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常借助（）來實(shí)現(xiàn)算法。

A:圖B:隊(duì)列C:樹D:棧

答案:棧若從無向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索可以訪問圖中所有的頂點(diǎn)，則該圖一定是（）圖。

A:非連通B:強(qiáng)連通C:有向D:連通

答案:連通圖的深度優(yōu)先遍歷類似于二叉樹的（）。

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

答案:先序遍歷下面（）算法適合構(gòu)造一個(gè)稠密圖G的最小生成樹。

A:Floyd算法B:Prim算法C:Dijkstra算法D:Kruskal算法

答案:Prim算法下面（）方法可以判斷出一個(gè)有向圖是否有環(huán)。

A:求關(guān)鍵路徑B:求最短路徑C:拓?fù)渑判駾:深度優(yōu)先遍歷

答案:拓?fù)渑判蜿P(guān)鍵路徑是AOE網(wǎng)絡(luò)中（）。

A:從源點(diǎn)到匯點(diǎn)的最長路徑B:最短回路C:最長回路D:從源點(diǎn)到匯點(diǎn)的最短路徑

答案:從源點(diǎn)到匯點(diǎn)的最長路徑對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖,若采用鄰接矩陣表示，則該矩陣大小是（）

A:nB:(n-1)2C:n2D:n-1

答案:n2對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖,若采用鄰接矩陣表示，矩陣中的非零元素個(gè)數(shù)是（）。

A:e2B:eC:2eD:n2

答案:2e在下列有關(guān)圖的存儲(chǔ)結(jié)構(gòu)的說法中錯(cuò)誤的是（）。

A:鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無向圖的存儲(chǔ)都適用。B:對(duì)同一個(gè)有向圖來說，鄰接表中邊結(jié)點(diǎn)數(shù)與逆鄰接表中邊結(jié)點(diǎn)數(shù)相等。C:用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)所占用的存儲(chǔ)空間大小與圖中的頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。D:鄰接矩陣只適用于稠密圖(邊數(shù)接近于頂點(diǎn)數(shù)的平方)，鄰接表適用于稀疏圖(邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平方)。

答案:鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無向圖的存儲(chǔ)都適用。設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)不可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。

A:aedfcbB:abedfcC:aebdfcD:acfebd

答案:acfebd廣度優(yōu)先遍歷類似于二叉樹的（）。

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

答案:層次遍歷用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常借助（）來實(shí)現(xiàn)算法。

A:樹B:圖C:隊(duì)列D:棧

答案:隊(duì)列關(guān)鍵路徑中的關(guān)鍵活動(dòng)是指活動(dòng)的___開始時(shí)間和___開始時(shí)間相等的活動(dòng)。

答案:最早開始時(shí)間和最晚開始時(shí)間相等的活動(dòng)。若一個(gè)圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點(diǎn)A開始對(duì)該圖進(jìn)行廣度優(yōu)先遍歷，得到的頂點(diǎn)序列可能為

A:A,B,D,C,E,FB:A,B,C,F,D,E

C:A,C,B,F,D,ED:A,B,C,D,E,F

答案:A,C,B,F,D,E已知一個(gè)有向圖的邊集為{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>}，則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨?/p>

A:

a,c,b,e,d

B:a,b,d,e,b

C:

a,c,d,b,e

D:a,b,c,d,e

答案:a,b,c,d,e

第八章單元測試

對(duì)n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長度為（）。

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

答案:(n+1)/2適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（）。

A:鏈接方式存儲(chǔ)，元素?zé)o序B:順序方式存儲(chǔ)，元素?zé)o序C:鏈接方式存儲(chǔ)，元素有序D:順序方式存儲(chǔ)，元素有序

答案:順序方式存儲(chǔ)，元素有序采用折半查找方式查找一個(gè)長度為n的有序順序表時(shí)，其平均查找長度為（）。

A:O(n)B:O(log2n)C:O(n2)D:O(nlog2n)

答案:O(log2n)二叉排序樹關(guān)鍵字中序遍歷序列的排列順序是（）。

A:由小到大B:無序排列C:由大到小

答案:由小到大在對(duì)查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于（）。

A:靜態(tài)查找表B:靜態(tài)查找表與動(dòng)態(tài)查找表C:兩種表都不適合D:動(dòng)態(tài)查找表

答案:動(dòng)態(tài)查找表二叉排序樹的查找效率與二叉樹的樹形有關(guān)，在（）時(shí)其查找效率最低。

A:結(jié)點(diǎn)太復(fù)雜B:結(jié)點(diǎn)太多C:完全二叉樹D:呈單支樹

答案:呈單支樹下面關(guān)于哈希查找的說法，正確的是（）。

A:哈希表的平均查找長度有時(shí)也和記錄總數(shù)有關(guān)B:哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好,沖突小。C:不存在特別好與壞的哈希函數(shù)，要視情況而定D:除留余數(shù)法是所有哈希函數(shù)中最好的

答案:不存在特別好與壞的哈希函數(shù)，要視情況而定對(duì)于線性表(7,34,55,25,64,46,20,10)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%9作為散列函數(shù)，則散列地址為1的元素有（）個(gè)。

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

答案:4設(shè)哈希表的地址范圍為0~13,哈希函數(shù)為:H(key)=key%13。用線性探測法處理沖突,輸入關(guān)鍵字序列:(10,24,3