千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案概論第1章算法

一、挑選題

1.算法的時(shí)光復(fù)雜度是指（）。

A）執(zhí)行算法程序所需要的時(shí)光

B）算法程序中的指令條數(shù)

C）算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)

D）算法程序的長度

2.算法的空間復(fù)雜度是指（）。

A）算法程序的長度

B）算法程序所占的存儲空間

C）算法執(zhí)行過程中所需要的存儲空間

D）算法程序中的指令條數(shù)

3.下面（）的時(shí)光復(fù)雜度最好（即執(zhí)行時(shí)光最短）。

log)

A）O(n)B）O(n

2

log)D）O(n2)

C）O(nn

2

4.下面累加求和程序段的時(shí)光復(fù)雜度為（）。

intsum(inta[],intn)

{

inti,s=0;

for(i=0;ix)

return1;

else

return0;

}

log)

A）O(1)B）O(n

2

C）O(n)D）O(n)

8.下面程序段的時(shí)光復(fù)雜度為（）

intfun(intn)

{

inti=1,s=1;

while(sa2、a1==a2、a1”、“=”、“a2)

return">";

elase

if(a1==a2)

return"=";

elase

return"200)

return0;//數(shù)組中數(shù)據(jù)有錯(cuò)，統(tǒng)計(jì)失敗

for(j=0;j,,,,,}

則該數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)。

6.一種數(shù)據(jù)結(jié)構(gòu)的元素集合為D，它在D上的二元關(guān)系R為：

D={a,b,c,d,e,f,g,h}

R={,,,,,,}

則該數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)。

7.數(shù)據(jù)的規(guī)律結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，其中的非線性結(jié)構(gòu)有兩種基本類型。

三、簡答題

1.數(shù)據(jù)結(jié)構(gòu)主要討論的三個(gè)問題是什么？

2.一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含兩方面的信息是什么？

3.簡述數(shù)據(jù)存儲結(jié)構(gòu)中的挨次存儲方式。

4.簡述數(shù)據(jù)存儲結(jié)構(gòu)中的鏈?zhǔn)酱鎯Ψ绞?/p>

參考答案

一、單選題

1.①B，②D

2.C

3.D

4.A

5.C

6.A

7.C8.B9.B10.D11.C12.B

二、填空題

1.數(shù)據(jù)元素，數(shù)據(jù)項(xiàng)

2.鏈?zhǔn)?、索?/p>

3.線性結(jié)構(gòu)與非線性結(jié)構(gòu)

4.線性結(jié)構(gòu)

5.線性

6.非線性（或樹形）

7.樹和圖

三、簡答題

1.答案：數(shù)據(jù)結(jié)構(gòu)主要討論的三個(gè)問題是：①數(shù)據(jù)的規(guī)律結(jié)構(gòu)，②數(shù)據(jù)的存儲結(jié)構(gòu)，

③對各種數(shù)據(jù)結(jié)構(gòu)舉行的運(yùn)算。

2.答案：一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含兩方面的信息：①表示數(shù)據(jù)元素的信息；②表示各數(shù)據(jù)元素之間的前后件關(guān)系。

3.答案：在數(shù)據(jù)的存儲結(jié)構(gòu)中，挨次存儲方式的含義如下：

挨次存儲方式：把規(guī)律上相鄰的數(shù)據(jù)元素存儲在物理位置也相鄰的存儲單元里，數(shù)據(jù)元素之間的規(guī)律關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。

4.答案：在數(shù)據(jù)的存儲結(jié)構(gòu)中，鏈?zhǔn)酱鎯Ψ绞降暮x如下：

鏈?zhǔn)酱鎯Ψ绞剑菏褂弥羔槺硎緮?shù)據(jù)元素之間的規(guī)律關(guān)系，各個(gè)數(shù)據(jù)元素的存儲位置可以任意，不要求規(guī)律上相鄰的數(shù)據(jù)元素在物理位置上也相鄰。

第3章線性表及其存儲結(jié)構(gòu)

一、單選題

1.在一個(gè)長度為n的挨次存儲的線性表中，向第i個(gè)元素（1≤i≤n+1）位置插入一個(gè)新元素時(shí)，需要從后向前依次后移（）個(gè)元素。

A）n-iB）n–i+1

C）n–i-1D）i

2.在一個(gè)長度為n的挨次存儲的線性表中，刪除第i個(gè)元素（1≤i≤n+1）時(shí)，需要先前向后依次前移（）個(gè)元素。

A）n-iB）n–i+1

C）n–i-1D）i

3.在一個(gè)長度為n的挨次表中，存在值為x的元素。在此表中用挨次搜尋法，查找值為x的元素，在等概率狀況下，查找勝利時(shí)的平均查找長度為（）。

A）nB）n/2

C）(n+1)/2D）(n-1)/2

4.在一個(gè)長度為n的挨次表中，刪除值為x的元素時(shí)，需要比較元素的次數(shù)和移動元素次數(shù)的和為（）。

A）n/2B）(n+1)/2

C）nD）n+1

5.在一個(gè)挨次表的表尾，插入一個(gè)元素時(shí)的時(shí)光復(fù)雜度為（）。

log)

A）O(1)B）O(n

2

C）O(n)D）O(n2)

6.在一個(gè)挨次表的隨意位置，插入一個(gè)元素的時(shí)光復(fù)雜度為（）。

log)

A）O(1)B）O(n

2

C）O(n)D）O(n