中國大學(xué)mooc《《數(shù)據(jù)結(jié)構(gòu)與算法》(青海大學(xué)) 》章節(jié)測試答案

title《數(shù)據(jù)結(jié)構(gòu)與算法》(青海大學(xué))中國大學(xué)mooc答案100分最新版content第一章緒論（總時長：56分26秒，共6講）第一章單元測試1、下面程序段的時間復(fù)雜度為（

）。for(inti=0;i<m;i++)

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

a[i][j]=ij;A:O(m2)

B:O(n2)

C:O(mn)

D:O(m+n)

答案:O(m*n)2、執(zhí)行下面程序段時，語句S的執(zhí)行次數(shù)為（

）。for(inti=0;i<=n;i++)

for(intj=0;j<=i;j++)

S;A:nn

B:nn/2

C:(n+1)(n+2)/2

D:n(n+1)/2

答案:(n+1)(n+2)/2

3、評價一個算法性能好壞的重要標準是（

）。A:算法的魯棒性

B:算法的可讀性

C:算法的時間復(fù)雜度和空間復(fù)雜度

D:算法的正確性

答案:算法的時間復(fù)雜度和空間復(fù)雜度

4、算法的時間復(fù)雜度與（

）有關(guān)。A:問題規(guī)模

B:計算機硬件性能

C:編譯程序質(zhì)量

D:程序設(shè)計語言

答案:問題規(guī)模

5、算法分析的主要任務(wù)是分析（

）。A:算法是否具有較好的可讀性

B:算法中是否存在語法錯誤

C:算法的功能是否符合要求

D:算法的執(zhí)行時間與所需空間與問題規(guī)模的關(guān)系

答案:算法的執(zhí)行時間與所需空間與問題規(guī)模的關(guān)系6、算法分析的目的是(

)。A:找出數(shù)據(jù)結(jié)構(gòu)的合理性

B:研究算法中輸入和輸出的關(guān)系

C:分析算法的效率以求改進

D:分析算法的可讀性

答案:分析算法的效率以求改進7、數(shù)據(jù)的最小單位是（

）。A:數(shù)據(jù)項

B:數(shù)據(jù)類型

C:數(shù)據(jù)元素

D:數(shù)據(jù)變量

答案:數(shù)據(jù)項

8、某算法的時間復(fù)雜度是O（nn）,表明該算法的（

）。A:問題規(guī)模是nn

B:問題規(guī)模與nn正比

C:執(zhí)行時間與nn正比

D:執(zhí)行時間等于nn

答案:執(zhí)行時間與nn正比

9、如下程序段:

for(i=1;i<=n-1;i++)

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

x=x+1;其中語句x=x+1執(zhí)行的語句頻度為（

）。A:nn

B:n(n-1)/2

C:n(n+1)/2

D:n(n-1)

答案:n*(n-1)/210、以下算法的時間復(fù)雜度為（

）。if(n>=0)

{

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

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

printf(“輸入數(shù)據(jù)大于等于零”);

}

else

{

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

printf(“輸入數(shù)據(jù)小于零”);

}A:O(1)

B:O(nn+n)

C:O(n)

D:O(nn)

答案:O(n*n)11、在數(shù)組A[0..n-1]中查找給定值K的算法大致如下：

i=n-1;

while(i>=0&&(A[i]!=k))

i–;

returni;

該算法的時間復(fù)雜度為（

）。A:O(n-i+1)

B:O(n-i)

C:O(n)

D:無法確定

答案:O(n)12、下面算法的時間復(fù)雜度為（

）。x=100;y=100;while(y>0)

if(x>100)

{x=x-10;y–;}

else

x++;A:O(n)

B:O(100)

C:O(1)

D:O(n*n)

答案:O(1)13、下面的算法是判斷n是否為素數(shù)，其時間復(fù)雜度為（

）。voidprime(intn){

for(i=2;i<sqrt(n)&&(n%i)!=0;i++);

if(i>sqrt(n))

printf(“%disaprimenumber”,n);

else

printf(“%disnotaprimenumber”,n);}

A:O(n)

B:O(1)

C:O(sqrt(n))

sqrt表示對n取根方

D:O（n-i）

答案:O(sqrt(n))

sqrt表示對n取根方14、某算法中，執(zhí)行頻率最高的語句的語句拼讀為

則該算法的時間復(fù)雜度應(yīng)該是（

）。A:T(n)=O(nnn)

B:T(n)=O(nn)

C:T(n)=O(

(nnn+nn+n)/n

)

D:T(n)=O(nn+n)

答案:T(n)=O(nn)15、以下屬于數(shù)據(jù)元素間基本邏輯結(jié)構(gòu)的是（

）。A:集合

B:線性

C:樹

D:圖

答案:集合;

線性;

樹;

圖16、以下不屬于算法特性的是（

）。A:0個或多個輸入；至少一個輸出

B:正確性

C:確定性

D:可行性和有限性

答案:0個或多個輸入；至少一個輸出;

確定性17、算法設(shè)計的要求包括（

）。A:正確性

B:可讀性

C:健壯性

D:高效率和低存儲

答案:正確性;

可讀性;

健壯性;

高效率和低存儲18、數(shù)據(jù)元素在計算機內(nèi)存中的存儲映像包括（

）。A:順序存儲

B:非順序存儲

C:圖結(jié)構(gòu)

D:樹結(jié)構(gòu)

答案:順序存儲;

非順序存儲19、抽象數(shù)據(jù)類型包括了（

）。A:一個數(shù)據(jù)對象

B:元素的存儲結(jié)構(gòu)

C:元素間的關(guān)系

D:一組操作

答案:一個數(shù)據(jù)對象;

元素間的關(guān)系;

一組操作20、線性結(jié)構(gòu)只能用順序存儲結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序存儲結(jié)構(gòu)來存放。A:正確

B:錯誤

答案:錯誤21、算法就是程序。A:正確

B:錯誤

答案:錯誤22、算法的優(yōu)劣與算法描述的語言無關(guān)。A:正確

B:錯誤

答案:正確23、算法的可行性是指每一條指令具有明確含義。A:正確

B:錯誤

答案:錯誤24、健壯的算法不會因為非法輸入數(shù)據(jù)而出現(xiàn)莫名的執(zhí)行結(jié)果。A:正確

B:錯誤

答案:正確25、算法設(shè)計的要求就是要設(shè)計高效率和低存儲的算法。A:正確

B:錯誤

答案:錯誤

分析：二者是算法的設(shè)計要求，但不是全部。26、數(shù)據(jù)類型就是變量。A:正確

B:錯誤

答案:錯誤27、數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)分為順序存儲和非順序存儲。A:正確

B:錯誤

答案:正確28、數(shù)據(jù)結(jié)構(gòu)的順序存儲優(yōu)于非順序存儲。A:正確

B:錯誤

答案:錯誤29、元素間的邏輯關(guān)系可分為線性和非線性關(guān)系兩種。A:正確

B:錯誤

答案:正確第二章線性表（二）（總時長：59分37秒）第二章單元測試（2）1、非空循環(huán)單鏈表L中，p指針指向尾結(jié)點，則以下表達式成立的是（

）。A:p->next==NULL

B:p==NULL

C:p->next==L

D:p==L

答案:p->next==L2、若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（

）存儲方式最節(jié)省時間。A:順序表

B:雙向鏈表

C:帶頭結(jié)點的雙循環(huán)鏈表

D:單循環(huán)鏈表

答案:順序表

3、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（

）存儲方式最節(jié)省運算時間。A:單鏈表

B:僅有頭指針的單循環(huán)鏈表

C:雙鏈表

D:帶尾指針的單循環(huán)鏈表

答案:帶尾指針的單循環(huán)鏈表4、對于雙向循環(huán)鏈表，在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共（

）個。A:2

B:3

C:4

D:5

答案:45、將帶頭指針的長度為m的單鏈表，鏈接到同樣帶頭指針的長度為n的單鏈表末尾。該算法的時間復(fù)雜度為(

)。A:O(m)

B:O(n)

C:O(m+n)

D:O(m*n)

答案:O(n)6、在某雙向鏈表中刪除一個結(jié)點，需要改動（

）個指針域。A:1

B:2

C:3

D:4

答案:27、循環(huán)單鏈表中，每個結(jié)點都有一個前驅(qū)和后繼，因此循環(huán)單鏈表不是線性結(jié)構(gòu)。A:正確

B:錯誤

答案:錯誤

分析：前驅(qū)和后繼是元素間的邏輯關(guān)系。

循環(huán)單鏈表是元素的存儲關(guān)系，只是為了操作方便而采用循環(huán)鏈表，并不會改變元素的邏輯關(guān)系。8、線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)。A:正確

B:錯誤

答案:正確9、線性表在順序存儲時，刪除第i個元素的時間同i的值無關(guān)。A:正確

B:錯誤

答案:錯誤

分析：當然有關(guān)系了，i的值決定了要移動多少元素。第二章線性表（一）（總時長：72分22秒，共6講）第二章單元測試（1）1、在長度為n的順序表中的第i(1<=

i<=n+1)個位置上插入一個元素，其算法時間復(fù)雜度為（

）。A:O(logn)(以2為底)

B:O(1)

C:O(n)

D:O(n*n)

答案:O(n)

2、在長度為n的順序表中的第i(1=<i<=n+1)個位置上插入一個元素，需要移動的元素個數(shù)為（

）。A:n-i

B:i

C:n-i+1

D:n-i-1

答案:n-i+13、鏈表不具有的特點是（

）。A:插入、刪除不需要移動元素

B:可隨機訪問任一元素

C:不必事先估計存儲空間

D:所需存儲空間與線性表程度成正比

答案:可隨機訪問任一元素4、在一單鏈表中，刪除指針p所指的后繼結(jié)點，以下語句正確的是（

）。A:p->next=p->next->next;

free(p->next);

B:free(p->next);p->next=p->next->next;

C:

p=p->next;

D:s=p->next;p->next=s->next;free(s);

答案:s=p->next;p->next=s->next;free(s);5、假設(shè)刪除長度為n的順序表中的每個元素的概率相同，則刪除一個元素平均要移動的元素個數(shù)是（

）。A:n

B:(n+1)/2

C:(n-1)/2

D:n/2

答案:(n-1)/26、設(shè)某順序表中第一個元素的地址是Base，每個結(jié)點占m個單元，則第i個結(jié)點的地址為（）。A:Base+(i-1)×m

B:Base+i×m

C:Base-i×m

D:Base+(i+1)×m

答案:Base+(i-1)×m

7、長度為n的非空線性表采用順序存儲結(jié)構(gòu)，在表的第i個位置插入一個數(shù)據(jù)元素，i的合法值應(yīng)該是（

）。A:i>0

B:1≤i≤n+1

C:1≤i≤n-1

D:0≤i≤n+1

答案:1≤i≤n+1

8、非空單鏈表結(jié)點結(jié)構(gòu)為data,next，若指針p所指結(jié)點是尾結(jié)點，則（

）表達式為真。A:p==NULL

B:p->next==NULL

C:p->next==P

D:p->next!=NULL

答案:p->next==NULL9、某順序表的第一個元素的存儲地址是500，每個元素占4個單元，則第8個元素的起始地址是(

)。A:504

B:508

C:516

D:528

答案:52810、在長度為n的順序表中刪除第i(1<=i<=n)個位置上的元素，需要移動的元素個數(shù)為（

）。A:n-i

B:n-i+1

C:n-i-1

D:i

答案:n-i11、單鏈表中增加頭結(jié)點的目的是存儲鏈表的長度。A:正確

B:錯誤

答案:錯誤

分析：添加頭結(jié)點的目的是，簡化操作。不一定是為了存儲鏈表的長度。12、線性表在鏈式存儲時，查找第i個元素的時間同i的值無關(guān)。A:正確

B:錯誤

答案:錯誤13、線性表在順序存儲時，查找第i個元素的時間同i的值成正比。A:正確

B:錯誤

答案:錯誤14、線性表的特點是每個元素都有一個前驅(qū)和一個后繼。A:正確

B:錯誤

答案:錯誤

分析：首元素沒有前驅(qū)，尾元素沒有后繼。15、線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲。A:正確

B:錯誤

答案:錯誤

分析：兩種存儲結(jié)構(gòu)沒各有優(yōu)缺點。16、順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。A:正確

B:錯誤

答案:錯誤

分析：前半句正確，后半句錯誤。

順序存儲中，插入和刪除的效率比較低。17、順序表的每個結(jié)點只能是一個基本類型，而鏈表的每個結(jié)點可以是一個構(gòu)造類型。A:正確

B:錯誤

答案:錯誤18、插入和刪除操作是線性表的基本操作