數(shù)據(jù)結(jié)構(gòu)各章習(xí)題及答案

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題及解答 數(shù)據(jù)結(jié)構(gòu)習(xí)題及解答第 1 章 概述 概述【例 1-1】分析以下程序段的時間復(fù)雜度。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;解：該程序段的時間復(fù)雜度為 O(m*n)。【例 1-2】分析以下程序段的時間復(fù)雜度。i=s=0; ①while(s<n){ i++; ②s+=i; ③}解：語句①為賦值語句，其執(zhí)行次數(shù)為 1 次，所以其時間復(fù)雜度為 O(1

2、)。語句②和語句③構(gòu)成 while 循環(huán)語句的循環(huán)體，它們的執(zhí)行次數(shù)由循環(huán)控制條件中 s 與 n 的值確定。假定循環(huán)重復(fù)執(zhí)行 x 次后結(jié)束， 則語句②和語句③各重復(fù)執(zhí)行了 x 次。其時間復(fù)雜度按線性累加規(guī)則為 O(x)。此時 s 與 n 滿足關(guān)系式：s≥n，而 s=1+2+3+…+x。所以有：1+2+3+…+x≥n，可以推出：x=n n 2 412128 1 1 ? ? ? ? ? ? ?x 與 n 之間滿足 x=f( n ） ，所以循

3、環(huán)體的時間復(fù)雜度為 O( n )，語句①與循環(huán)體由線性累加規(guī)則得到該程序段的時間復(fù)雜度為 O( n ） ?！纠?1-3】分析以下程序段的時間復(fù)雜度。i=1; ①while(i<=n) i=2*i; ②解：其中語句①的執(zhí)行次數(shù)是 1，設(shè)語句②的執(zhí)行次數(shù)為 f(n)，則有： n n f ? ) ( 2 。A.低 B.高 C.相同 D.不好說8. 數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程出現(xiàn)是在（ 8. D）年。A.1946 B.1

4、953 C.1964D.19689. 數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點（9. B ） 。A.正確 B.錯誤C.前半句對，后半句錯 D.前半句錯，后半句對10. 計算機內(nèi)部數(shù)據(jù)處理的基本單位是（10. B ） 。A.數(shù)據(jù) B.數(shù)據(jù)元素 C.數(shù)據(jù)項 D.數(shù)據(jù)庫二、填空題 二、填空題 1. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是______________和_________________。1

5、. 線性結(jié)構(gòu)，非線性結(jié)構(gòu)2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。2. 集合，線性，樹，圖3. 線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是__________________的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是__________________的。3. 一對一，一對多或多對多4. 一個算法的效率可

6、分為__________________效率和__________________效率。4. 時間，空間5. 在樹型結(jié)構(gòu)中，樹根結(jié)點沒有__________________結(jié)點，其余每個結(jié)點的有且只有__________________個前趨驅(qū)結(jié)點；葉子結(jié)點沒有__________________結(jié)點；其余每個結(jié)點的后續(xù)結(jié)點可以__________________。5. 前趨，一，后繼，多6. 在圖型結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)

7、結(jié)點數(shù)可以__________________。6. 有多個7. 線性結(jié)構(gòu)中元素之間存在__________________關(guān)系；樹型結(jié)構(gòu)中元素之間存在__________________關(guān)系；圖型結(jié)構(gòu)中元素之間存在__________________關(guān)系。7. 一對一，一對多，多對多8. 下面程序段的時間復(fù)雜度是__________________。8. O(2 n )for(i=0;i<n;i++)for(j=0;j<