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

title《數(shù)據(jù)結(jié)構(gòu)與算法》(青海大學(xué))中國(guó)大學(xué)mooc答案100分最新版content第一章緒論（總時(shí)長(zhǎng)：56分26秒，共6講）第一章單元測(cè)試1、下面程序段的時(shí)間復(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í)行下面程序段時(shí)，語(yǔ)句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、評(píng)價(jià)一個(gè)算法性能好壞的重要標(biāo)準(zhǔn)是（

）。A:算法的魯棒性

B:算法的可讀性

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

D:算法的正確性

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

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

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

B:計(jì)算機(jī)硬件性能

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

D:程序設(shè)計(jì)語(yǔ)言

答案:問(wèn)題規(guī)模

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

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

B:算法中是否存在語(yǔ)法錯(cuò)誤

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

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

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

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

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

C:分析算法的效率以求改進(jìn)

D:分析算法的可讀性

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

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

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

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

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

答案:數(shù)據(jù)項(xiàng)

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

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

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

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

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

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

9、如下程序段:

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

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

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

）。A:nn

B:n(n-1)/2

C:n(n+1)/2

D:n(n-1)

答案:n*(n-1)/210、以下算法的時(shí)間復(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;

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

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

B:O(n-i)

C:O(n)

D:無(wú)法確定

答案:O(n)12、下面算法的時(shí)間復(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是否為素?cái)?shù)，其時(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表示對(duì)n取根方

D:O（n-i）

答案:O(sqrt(n))

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

則該算法的時(shí)間復(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:樹(shù)

D:圖

答案:集合;

線性;

樹(shù);

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

）。A:0個(gè)或多個(gè)輸入；至少一個(gè)輸出

B:正確性

C:確定性

D:可行性和有限性

答案:0個(gè)或多個(gè)輸入；至少一個(gè)輸出;

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

）。A:正確性

B:可讀性

C:健壯性

D:高效率和低存儲(chǔ)

答案:正確性;

可讀性;

健壯性;

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

）。A:順序存儲(chǔ)

B:非順序存儲(chǔ)

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

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

答案:順序存儲(chǔ);

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

）。A:一個(gè)數(shù)據(jù)對(duì)象

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

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

D:一組操作

答案:一個(gè)數(shù)據(jù)對(duì)象;

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

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

B:錯(cuò)誤

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

B:錯(cuò)誤

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

B:錯(cuò)誤

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

B:錯(cuò)誤

答案:錯(cuò)誤24、健壯的算法不會(huì)因?yàn)榉欠ㄝ斎霐?shù)據(jù)而出現(xiàn)莫名的執(zhí)行結(jié)果。A:正確

B:錯(cuò)誤

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

B:錯(cuò)誤

答案:錯(cuò)誤

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

B:錯(cuò)誤

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

B:錯(cuò)誤

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

B:錯(cuò)誤

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

B:錯(cuò)誤

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

）。A:p->next==NULL

B:p==NULL

C:p->next==L

D:p==L

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

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

B:雙向鏈表

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

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

答案:順序表

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

）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A:單鏈表

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

C:雙鏈表

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

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

）個(gè)。A:2

B:3

C:4

D:5

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

)。A:O(m)

B:O(n)

C:O(m+n)

D:O(m*n)

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

）個(gè)指針域。A:1

B:2

C:3

D:4

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

B:錯(cuò)誤

答案:錯(cuò)誤

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

循環(huán)單鏈表是元素的存儲(chǔ)關(guān)系，只是為了操作方便而采用循環(huán)鏈表，并不會(huì)改變?cè)氐倪壿嬯P(guān)系。8、線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)。A:正確

B:錯(cuò)誤

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

B:錯(cuò)誤

答案:錯(cuò)誤

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

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

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

B:O(1)

C:O(n)

D:O(n*n)

答案:O(n)

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

）。A:n-i

B:i

C:n-i+1

D:n-i-1

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

）。A:插入、刪除不需要移動(dòng)元素

B:可隨機(jī)訪問(wèn)任一元素

C:不必事先估計(jì)存儲(chǔ)空間

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

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

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

）。A:n

B:(n+1)/2

C:(n-1)/2

D:n/2

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

B:Base+i×m

C:Base-i×m

D:Base+(i+1)×m

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

7、長(zhǎng)度為n的非空線性表采用順序存儲(chǔ)結(jié)構(gòu)，在表的第i個(gè)位置插入一個(gè)數(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é)點(diǎn)結(jié)構(gòu)為data,next，若指針p所指結(jié)點(diǎn)是尾結(jié)點(diǎn)，則（

）表達(dá)式為真。A:p==NULL

B:p->next==NULL

C:p->next==P

D:p->next!=NULL

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

)。A:504

B:508

C:516

D:528

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

）。A:n-i

B:n-i+1

C:n-i-1

D:i

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

B:錯(cuò)誤

答案:錯(cuò)誤

分析：添加頭結(jié)點(diǎn)的目的是，簡(jiǎn)化操作。不一定是為了存儲(chǔ)鏈表的長(zhǎng)度。12、線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)。A:正確

B:錯(cuò)誤

答案:錯(cuò)誤13、線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比。A:正確

B:錯(cuò)誤

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

B:錯(cuò)誤

答案:錯(cuò)誤

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

B:錯(cuò)誤

答案:錯(cuò)誤

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

B:錯(cuò)誤

答案:錯(cuò)誤

分析：前半句正確，后半句錯(cuò)誤。

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

B:錯(cuò)誤

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