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

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

關于數(shù)據結構以下說法正確的是（）。

A:數(shù)據項是數(shù)據的基本單位B:數(shù)據結構是帶有結構的各數(shù)據項的集合C:數(shù)據對象是帶結構的數(shù)據元素的子集D:數(shù)據元素是數(shù)據的最小單位

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

A:相互之間存在一種或多種特定關系的數(shù)據元素的集合B:數(shù)據的存儲結構C:一種數(shù)據類型D:一組性質相同的數(shù)據元素的集合

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

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

答案:邏輯數(shù)據結構在計算機內存中的表示是指（）。

A:數(shù)據的邏輯結構B:數(shù)據結構C:數(shù)據元素之間的關系D:數(shù)據的存儲結構

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

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

答案:數(shù)據元素之間的關系在數(shù)據結構中，從邏輯上可以把數(shù)據結構分成（）。

A:緊湊結構和非緊湊結構B:動態(tài)結構和靜態(tài)結構C:線性結構和非線性結構D:內部結構和外部結構

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

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

答案:抽象數(shù)據類型數(shù)據的存儲結構包括（）。

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

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

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

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

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

答案:問題的規(guī)模和待處理數(shù)據的初態(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:研究算法中的輸入和輸出的關系B:分析算法的效率以求改進C:找出數(shù)據結構的合理性D:分析算法的易懂性和文檔性

答案:分析算法的效率以求改進算法指的是（）。

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

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

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

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

i=1;

while(i<=n)

i=i*3;

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

答案:O(log3n)計算下列程序的漸進時間復雜度為（）。

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))

第二章單元測試

線性表的順序存儲結構是一種（）的存儲結構。

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

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

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

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

A:多對多關系B:多對一關系C:一對一關系D:一對多關系

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

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

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

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

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

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假設刪除長度為n的順序表中的每個元素的概率相同，則刪除一個元素平均要移動的元素個數(shù)是（）。

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

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

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

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

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

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

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

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

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

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

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

答案:在第i個結點后插入一個新結點（1≤i≤n）線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（）。

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

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

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是帶頭結點的單鏈表，則刪除首元結點的語句是（）。

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所指結點的后繼結點q(注:P既不是第一個結點,也不是最后一個結點)，則執(zhí)行（）操作。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;以下鏈表結構中，從當前結點出發(fā)能夠訪問到任一結點的是（）。

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

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

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

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

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

答案:已知某個結點的位置后，能容易找到它的直接前驅線性表Ｌ在（）情況下適用于使用鏈式結構實現(xiàn)。

A:需不斷對Ｌ進行刪除插入B:Ｌ中結點結構復雜C:Ｌ中含有大量的結點D:需經常修改Ｌ中的結點值

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

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

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

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

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

第三章單元測試

棧是一種受限的線性結構，其操作特點是（）。

A:沒有順序B:先進后出C:先進先出D:后進后出

答案:先進后出若讓元素1,2,3,4,5依次進棧，則出棧次序不可能出現(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以下關于順序棧的操作，正確的是（）。

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

答案:n個元素進入一個順序棧后，如果一次性進棧完畢再出棧，它們的出棧順序一定與進棧順序相反向一個棧頂指針為top的不帶頭結點的鏈棧中插人一個*S結點的時候，應當執(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；向一個帶頭結點、棧頂指針為top的鏈棧中插人一個*S結點的時候，應當執(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；算術表達式a+b*(c+d)/e轉為后綴表達式后為（）。

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

答案:abcd+*e/+設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用（）數(shù)據結構最佳。

A:隊列B:線性表的順序存儲結構C:棧D:線性表的鏈式存儲結構

答案:棧鏈式棧的存儲結構為(data,next)，top和bottom分別是指向棧頂和棧底的指針，此時p指針所指的結點入棧，則應執(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的不帶頭結點的鏈棧中插人一個*S結點的時候，應當執(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;鏈式棧結點為：(data,link)，top指向棧頂。若想刪除棧頂結點，并將刪除結點的值保存到x中，則應執(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；以下會用到棧的應用的是（）。

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

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

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

答案:棧隊列是一種受限的線性結構，其操作原則是（）。

A:先進先出B:后進先出C:先進后出D:不分順序

答案:先進先出判定一個順序隊列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為當前隊列頭元素的前一位置，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)隊列的插入操作在（）進行。

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

答案:rear所指的位置一個隊列的進隊順序是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í)行插入操作時（）。

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

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

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

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

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

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

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

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

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

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

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

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

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ù)據元素沒限制C:可以鏈式存儲D:數(shù)據元素是字符

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

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

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

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

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

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

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

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

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

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

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

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)的位置設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱做（）。

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

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

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

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

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

答案:j=next[j]已知字符串s為"abcacaabaabcc"，模式串t為"babaabc"。采用KMP算法進行匹配，第一次出現(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設主串的長度為n，子串的長度為m，那么BF算法的時間復雜度和KMP算法的時間復雜度為（）

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ù)組A=array[0..8,0..8](9行*9列)，設每個數(shù)據元素占2個存儲單元，基地址為0，則LOC[5,5]=（）。

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

答案:100設有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內存首地址A開始順序存放，當用以列為主存放時，元素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的關系為（）。

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對稀疏矩陣進行壓縮存儲的目的是（）。

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

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

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

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

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

答案:66

第六章單元測試

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

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

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

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

答案:82表達人類社會中的族譜關系最適合的數(shù)據結構為（）。

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

答案:樹不含任何結點的空樹（）。

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

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

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

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

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

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

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

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

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

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

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

答案:59一個具有129個結點的二叉樹的高h為（）。

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

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

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

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

A:順序存儲結構和鏈式存儲結構都不能使用B:不能用順序存儲結構存儲;C:不能用鏈式存儲結構存儲;D:順序存儲結構和鏈式存儲結構都能存儲

答案:順序存儲結構和鏈式存儲結構都能存儲一棵有124個葉子結點的完全二叉樹最多有（）個結點。

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

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

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

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

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

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

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

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

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

答案:加快查找結點的前驅或后繼的速度一個具有129個結點的二叉樹的高h為（）。

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

答案:8至129之間如果二叉樹T2是由一棵樹T1轉換而來的二叉樹，那么T1中結點的先根序列對應T2的（）序列。

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

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

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

答案:100由權值為7,19,2,6,32,3,21,10的結點構成的哈夫曼樹的帶權路徑長度為（）。

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

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

答案:219拓撲排序算法是通過重復選擇具有___個前驅頂點的過程來完成的。

答案: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)在無向圖中定義頂點的度為與它相關聯(lián)的（）的數(shù)目。

A:權值B:權C:邊D:頂點

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

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

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

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

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

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ù)據結構，關于其存儲結構，正確的描述是（）。

A:它不能用順序存儲結構存儲B:順序存儲結構和鏈式存儲結構都不能使用C:它不能用鏈式存儲結構存儲D:順序存儲結構和鏈式存儲結構都能使用

答案:順序存儲結構和鏈式存儲結構都能使用由一個具有n個頂點的連通圖生成的最小生成樹中，具有（）條邊。

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

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

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

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

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

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

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

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

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

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

A:求關鍵路徑B:求最短路徑C:拓撲排序D:深度優(yōu)先遍歷

答案:拓撲排序關鍵路徑是AOE網絡中（）。

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

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

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

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

A:e2B:eC:2eD:n2

答案:2e在下列有關圖的存儲結構的說法中錯誤的是（）。

A:鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。B:對同一個有向圖來說，鄰接表中邊結點數(shù)與逆鄰接表中邊結點數(shù)相等。C:用鄰接矩陣存儲一個圖時所占用的存儲空間大小與圖中的頂點個數(shù)有關，而與圖的邊數(shù)無關。D:鄰接矩陣只適用于稠密圖(邊數(shù)接近于頂點數(shù)的平方)，鄰接表適用于稀疏圖(邊數(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:先序遍歷

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

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

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

答案:最早開始時間和最晚開始時間相等的活動。若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點A開始對該圖進行廣度優(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>}，則由該圖產生的一種可能的拓撲序列為

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:鏈接方式存儲，元素無序B:順序方式存儲，元素無序C:鏈接方式存儲，元素有序D:順序方式存儲，元素有序

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

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

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

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

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

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

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

A:結點太復雜B:結點太多C:完全二叉樹D:呈單支樹

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

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

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

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

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