數(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ù)項是數(shù)據(jù)的基本單位B:數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合C:數(shù)據(jù)對象是帶結(jié)構(gòu)的數(shù)據(jù)元素的子集D:數(shù)據(jù)元素是數(shù)據(jù)的最小單位

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

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

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

A:邏輯和存儲B:存儲C:邏輯D:物理

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

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

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

A:數(shù)據(jù)的存儲方法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:動態(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)可以用（）定義一個完整的數(shù)據(jù)結(jié)構(gòu)。

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

答案:抽象數(shù)據(jù)類型數(shù)據(jù)的存儲結(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)計算機算法指的是解決問題的步驟序列，它必須具備（）這五個特性。

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

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

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

答案:問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)在下面的程序段中，對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]對換；

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:計算機程序D:查找或排序過程

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

A:其他說法都不對B:算法的時間效率C:算法的空間效率D:算法的空間效率和時間效率

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

i=1;

while(i<=n)

i=i*3;

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

答案:O(log3n)計算下列程序的漸進(jìn)時間復(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))

第二章單元測試

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

A:索引存取B:散列存取C:順序存取D:隨機存取

答案:隨機存取對線性表的定義是（）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

答案:連續(xù)或不連續(xù)都可以在單鏈表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句應(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é)點的單鏈表，則刪除首元結(jié)點的語句是（）。

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

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

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

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

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

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

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

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

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

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

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

答案:可以通過頭結(jié)點直接計算第i個結(jié)點的存儲地址單鏈表又稱線性鏈表，在單鏈表上實施刪除操作（）。

A:只需移動結(jié)點，不需改變結(jié)點指針B:不需要移動結(jié)點，不需改變結(jié)點指針C:既需移動結(jié)點，又需要改變結(jié)點指針D:不需移動結(jié)點，只需改變結(jié)點指針

答案:不需移動結(jié)點，只需改變結(jié)點指針單鏈表又稱線性鏈表，在單鏈表上實施插入操作（）

A:只需移動結(jié)點，不需改變結(jié)點指針B:不需移動結(jié)點，只需改變結(jié)點指針C:不需要移動結(jié)點，不需改變結(jié)點指針D:既需移動結(jié)點，又需要改變結(jié)點指針

答案:不需移動結(jié)點，只需改變結(jié)點指針在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點后插入q所指向的新結(jié)點，其修改指針的操作是（）。

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;在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（）。

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é)點出發(fā)能夠訪問到任一結(jié)點的是（）。

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

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

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

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

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

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

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

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

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

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

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

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

第三章單元測試

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

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若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pj為（）。

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

答案:n-j+1判定一個順序棧ST(最多元素數(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:棧是一種對進(jìn)棧和出棧操作的次序做了限制的線性表B:若一個棧的存儲空間為S[n]，則對棧的進(jìn)棧和出棧操作最多只能執(zhí)行n次C:空棧沒有棧頂指針D:n個元素進(jìn)入一個順序棧后，如果一次性進(jìn)棧完畢再出棧，它們的出棧順序一定與進(jìn)棧順序相反

答案:n個元素進(jìn)入一個順序棧后，如果一次性進(jìn)棧完畢再出棧，它們的出棧順序一定與進(jìn)棧順序相反向一個棧頂指針為top的不帶頭結(jié)點的鏈棧中插人一個*S結(jié)點的時候，應(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；向一個帶頭結(jié)點、棧頂指針為top的鏈棧中插人一個*S結(jié)點的時候，應(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è)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。

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

答案:棧鏈?zhǔn)綏５拇鎯Y(jié)構(gòu)為(data,next)，top和bottom分別是指向棧頂和棧底的指針，此時p指針?biāo)傅慕Y(jié)點入棧，則應(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;向一個棧頂指針為top的不帶頭結(jié)點的鏈棧中插人一個*S結(jié)點的時候，應(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é)點為：(data,link)，top指向棧頂。若想刪除棧頂結(jié)點，并將刪除結(jié)點的值保存到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；以下會用到棧的應(yīng)用的是（）。

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

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

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

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

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

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

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判定一個順序循環(huán)隊列Q(最多有n個元素)為空的條件是（）。

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)隊列，隊尾指針是rear，隊頭是front，則隊滿的條件是（）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A:線性表B:隊列C:棧D:有序表

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

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:可以順序存儲B:數(shù)據(jù)元素沒限制C:可以鏈?zhǔn)酱鎯:數(shù)據(jù)元素是字符

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

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

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

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

答案:兩個串的長度相等且對應(yīng)位置的字符相同在串的簡單模式匹配中(BF)，當(dāng)模式串位j與目標(biāo)串位i比較時,兩字符不相等，則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比較時，兩字符不相等，則i的位移方式是（）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

答案:i不變或者移動到下一位置在KMP模式匹配中，用next數(shù)組存放模式串的部分匹配信息。當(dāng)模式串位j與目標(biāo)串位i比較時，兩字符不相等，則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])時,i=j=0,則下次開始匹配時，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算法的時間復(fù)雜度和KMP算法的時間復(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)

第五章單元測試

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

A:隨機存取B:順序存儲C:ABC都不對D:輸入輸出

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

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

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

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

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

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

答案:base+255若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(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將一個A[1..100,1..100]的三對角矩陣，按行序優(yōu)先存入一維數(shù)組B[1..298]中，A中元素A66,66，在B數(shù)組中的位置K為（）。

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

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

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

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

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

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

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

答案:66

第六章單元測試

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

答案:100由權(quán)值為7,19,2,6,32,3,21,10的結(jié)點構(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個字符設(shè)計赫夫曼編碼，并求出用赫夫曼編碼傳送電文的總長度為___bit。

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

答案:0

第七章單元測試

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

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

答案:2具有n個頂點的有向圖最多有（）條邊。

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

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

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

答案:邊具有n個頂點且每一對不同的頂點之間都有一條邊的無向圖被稱為（）。

A:無向強連通圖B:無向完全圖C:無向樹圖D:無向連通圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A:圖B:隊列C:樹D:棧

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

A:非連通B:強連通C:有向D:連通

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

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

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

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

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

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

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

A:從源點到匯點的最長路徑B:最短回路C:最長回路D:從源點到匯點的最短路徑

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

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

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

A:e2B:eC:2eD:n2

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

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

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

A:aedfcbB:abedfcC:aebdfcD:acfebd

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

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

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

A:樹B:圖C:隊列D:棧

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

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

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已知一個有向圖的邊集為{<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

第八章單元測試

對n個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為（）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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