數(shù)據(jù)結(jié)構(gòu)第1章-答案

1、第1章概論數(shù)據(jù)結(jié)構(gòu)作業(yè)答案1一、填空題01、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的(操作對象)以及它們之間的(關(guān)系和運算)等的學科。02、數(shù)據(jù)結(jié)構(gòu)被形式地定義為(DR)，其中D是(數(shù)據(jù)元素)的有限集合，R是D上的(關(guān)系)有限集合。03、數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的(邏輯結(jié)構(gòu))、數(shù)據(jù)的(存儲結(jié)構(gòu))和數(shù)據(jù)的(運算)這三個方面的內(nèi)容。04、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是(線性結(jié)構(gòu))和(非線性結(jié)構(gòu))。05、線性結(jié)構(gòu)中元素之間存在

2、(一對一)關(guān)系，樹形結(jié)構(gòu)中元素之間存在(一對多)關(guān)系，圖形結(jié)構(gòu)中元素之間存在(多對多)關(guān)系。06、在線性結(jié)構(gòu)中，第一個結(jié)點(沒有)前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點(沒有)后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。07、在樹形結(jié)構(gòu)中，樹根結(jié)點沒有(前驅(qū))結(jié)點，其余每個結(jié)點有且只有(1)個前驅(qū)結(jié)點；葉子結(jié)點沒有(后續(xù))結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以(任意多個)。08、在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點

3、數(shù)可以(任意多個)。09、數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是(順序)、(鏈式)、(索引)、(散列)。10、對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有(集合)、(線性結(jié)構(gòu))、(樹形結(jié)構(gòu))、(圖狀結(jié)構(gòu))四種。11、數(shù)據(jù)的運算最常用的有5種，它們分別是(插入)、(刪除)、(修改)、(查找)、(排序)。12、一個算法的效率可分為(時間)效率和(空間)效率。13、數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是算法的(時間復(fù)雜度)和(空間復(fù)雜

4、度)。14、一個數(shù)據(jù)結(jié)構(gòu)在計算機中的(映射)稱為存儲結(jié)構(gòu)。15、算法的五個重要特性是(有窮性)、(確定性)、(可行性)、輸入、輸出。16、已知如下程序段f(i=ni=1i)語句1x語句2f(j=nj=ij)語句3y語句4語句1執(zhí)行的頻度為(n1)；語句2執(zhí)行的頻度為(n)；語句3執(zhí)行的頻度為(n(n3)2)；語句4執(zhí)行的頻度為(n(n1)2)。17、在下面的程序段中，對ｘ的賦值語句的頻度為(n(n1)(n2)6)。f(i=1i=ij)第

5、1章概論數(shù)據(jù)結(jié)構(gòu)作業(yè)答案3C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性A09、在決定選取何種存儲結(jié)構(gòu)時，一般不考慮__。A)各結(jié)點的值如何B)結(jié)構(gòu)個數(shù)的多少C)對數(shù)據(jù)有哪些運算D)所用編程語言實現(xiàn)這種結(jié)構(gòu)是否方便C10、在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而還要存儲__。A)數(shù)據(jù)的處理方法B)數(shù)據(jù)元素的類型C)數(shù)據(jù)元素之間的關(guān)系D)數(shù)據(jù)的存儲方法B11、算法的計算量的大小稱為計算的__。A)效率B)復(fù)雜性C)現(xiàn)實性D)難

6、度A12、下面說法錯誤的是__。(1)算法原地工作的含義是指不需要任何額外的輔助空間(2)在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O()的算法n2(3)所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界(4)同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A)(1)B)(1)、(2)C)(1)、(4)D)(3)C13、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為__兩大類。A)動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B)順序結(jié)構(gòu)、鏈式結(jié)構(gòu)C)線性結(jié)構(gòu)、

7、非線性結(jié)構(gòu)D)初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)D14、以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是__。A)循環(huán)隊列B)鏈表C)哈希表D)棧A15、以下數(shù)據(jù)結(jié)構(gòu)中，__是非線性數(shù)據(jù)結(jié)構(gòu)。A)樹B)字符串C)隊列D)棧C16、以下屬于邏輯結(jié)構(gòu)的是__。A)順序表B)哈希表C)有序表D)單鏈表四、分析下面各程序段的時間復(fù)雜度01、f(i=0ini)f(j=0jmj)A[i][j]=0答：O（）nm?02、s=0f(i=0ini)f(j=0jnj)s=B[i][j]