數(shù)據(jù)結構各章習題及答案

1、數(shù)據(jù)結構習題及解答數(shù)據(jù)結構習題及解答第1章概述概述【例11】分析以下程序段的時間復雜度。f(i=0ini)f(j=0jmj)A[i][j]=0解：該程序段的時間復雜度為O(mn)?！纠?2】分析以下程序段的時間復雜度。i=s=0①while(sn)i②s=i③解：語句①為賦值語句，其執(zhí)行次數(shù)為1次，所以其時間復雜度為O(1)。語句②和語句③構成while循環(huán)語句的循環(huán)體，它們的執(zhí)行次數(shù)由循環(huán)控制條件中s與n的值確定。假定循環(huán)重復執(zhí)行x次

2、后結束，則語句②和語句③各重復執(zhí)行了x次。其時間復雜度按線性累加規(guī)則為O(x)。此時s與n滿足關系式：s≥n，而s=123…x。所以有：123…x≥n，可以推出：x=nn241212811???????x與n之間滿足x=f(n），所以循環(huán)體的時間復雜度為O(n)，語句①與循環(huán)體由線性累加規(guī)則得到該程序段的時間復雜度為O(n）?！纠?3】分析以下程序段的時間復雜度。i=1①while(i=n)i=2i②解：其中語句①的執(zhí)行次數(shù)是1，設語句

3、②的執(zhí)行次數(shù)為f(n)，則有：nnf?)(2。A.低B.高C.相同D.不好說8.數(shù)據(jù)結構作為一門獨立的課程出現(xiàn)是在（8.D）年。A.1946B.1953C.1964D.19689.數(shù)據(jù)結構只是研究數(shù)據(jù)的邏輯結構和物理結構，這種觀點（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ù)結構按邏輯結構可分為

4、兩大類，分別是______________和_________________。1.線性結構，非線性結構2.數(shù)據(jù)的邏輯結構有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。2.集合，線性，樹，圖3.線性結構反映結點間的邏輯關系是__________________的，非線性結構反映結點間的邏輯關系是__________

5、________的。3.一對一，一對多或多對多4.一個算法的效率可分為__________________效率和__________________效率。4.時間，空間5.在樹型結構中，樹根結點沒有__________________結點，其余每個結點的有且只有__________________個前趨驅結點；葉子結點沒有__________________結點；其余每個結點的后續(xù)結點可以__________________。5.前趨，

6、一，后繼，多6.在圖型結構中，每個結點的前趨結點數(shù)和后續(xù)結點數(shù)可以__________________。6.有多個7.線性結構中元素之間存在__________________關系；樹型結構中元素之間存在__________________關系；圖型結構中元素之間存在__________________關系。7.一對一，一對多，多對多8.下面程序段的時間復雜度是__________________。8.O(2n)f(i=0ini)f(j