1、第1章概論數(shù)據(jù)結(jié)構(gòu)作業(yè)答案1一、填空題01、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的(操作對(duì)象)以及它們之間的(關(guān)系和運(yùn)算)等的學(xué)科。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ù)的(存儲(chǔ)結(jié)構(gòu))和數(shù)據(jù)的(運(yùn)算)這三個(gè)方面的內(nèi)容。04、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是(線性結(jié)構(gòu))和(非線性結(jié)構(gòu))。05、線性結(jié)構(gòu)中元素之間存在

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

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

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

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

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

7、非線性結(jié)構(gòu)D)初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)D14、以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語(yǔ)是__。A)循環(huán)隊(duì)列B)鏈表C)哈希表D)棧A15、以下數(shù)據(jù)結(jié)構(gòu)中，__是非線性數(shù)據(jù)結(jié)構(gòu)。A)樹B)字符串C)隊(duì)列D)棧C16、以下屬于邏輯結(jié)構(gòu)的是__。A)順序表B)哈希表C)有序表D)單鏈表四、分析下面各程序段的時(shí)間復(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]