【正文】 *A．?dāng)?shù)據(jù)元素 B．?dāng)?shù) 據(jù)項 C．?dāng)?shù)據(jù) D．?dāng)?shù)據(jù)結(jié)構(gòu) 2．線性表 L=(a1， a2，?， ai，?， an)，下列說法正確的是 ( )。 (4)x=n； y=0； while(x=(y+1)*(y+1)) y++； 答： (1) O(n) (2) O(1) (3) O(n) (4) O(n1/2) 9． 設(shè) n 為正數(shù)。 8．分析下列程序的時間復(fù)雜度 (設(shè) n 為正整數(shù) )。 7．設(shè)有如圖 所示的邏輯結(jié)構(gòu)圖，給出它的邏輯結(jié)構(gòu)，并說出它是什么類型的邏輯結(jié)構(gòu)。 答： (2／ 3)n， 210， log2n， n2／ 3， n， nlog2n， n2， n3， 2n， n! 6．設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為： D={k1， k2， k3，?， k9}， R={k1， k3， k1， k8， k2， k3， k2， k4， k2， k5， k3， k9， k5， k6， k8， k9， k9， k7，k4， k6}，畫出這個邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系 R， 哪些結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點？ 答：圖略。邏輯結(jié)構(gòu)與計算機無關(guān)，存儲結(jié)構(gòu)是數(shù)據(jù) 元素之間的關(guān)系在計算機中的表示。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。 答：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合。算法應(yīng)該具有下列特性：可行性、確定性、有窮性、輸入和輸出。 答：算法是對特定問題求解步驟的一種描述，是指令的有限序列。 四、應(yīng)用題 1．分析下列程序段的時間復(fù)雜度。 19．?dāng)?shù)據(jù)對象是性質(zhì)相同的 __數(shù)據(jù)元素 _的集合。通常認為，具有指數(shù)階量級的算法是 __不可行 __的。 16．在一般情況下，一個算法的時間復(fù)雜度是 __問題規(guī)模 __的函數(shù)。 14．通常從 ___確定性 ___、 __可讀性 _、 ___健壯性 __、 _高 效性 __等幾方面評價算法 (包括程序 )的質(zhì)量。 12．根據(jù)需要，數(shù)據(jù)元素又被稱為 __結(jié)點 __、 __記錄 __、 ___元素 __或 __頂點 _。 S=0； for(i=1； i=n； i++) for(j=1； j=n； j++) s=s+B[i,j]； sum=s； 10．存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的 ___物理 __實現(xiàn)。 2 8．下列程序段的時間復(fù)雜度是 __O（ n） ___。 6．在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點可以有 ___任意個 ___。 4．在線性結(jié)構(gòu)中，開始結(jié)點 __沒有 _前驅(qū)結(jié)點，其余每個結(jié)點有且只有 __一個 _個前驅(qū)結(jié)點。 2， 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容 ___數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、對數(shù)據(jù)施加的操作 ___。 √ 8．順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。 √ 6．?dāng)?shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計算機中實際的存儲形式。 ╳ 4．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位。 √ 2．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。 *A．集合中任何兩個結(jié)點之間都有邏輯關(guān)系但組織形式松散 B．線性結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列形成一條“鎖鏈” C．樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點像自然界中的樹 D．圖狀結(jié)構(gòu)中的各個結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接 11．以下說法正確的是 ( )。 A．必須是連續(xù)的 B．部分必須是連續(xù)的 C．一定是不連續(xù)的 *D．連續(xù)不連續(xù)都可以 9．在以下的敘述中，正確的是 ( )。 A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出的關(guān)系 *C．分析算法的效率以求改進 D．分析算法的易懂性和文檔性 7．計算機算法指的是 ( (1) )，它必須具備輸入、輸出和 ( (2) )等五個特征。 A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) *C．線性結(jié)構(gòu)和非線性結(jié)構(gòu) D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 5．線性表的順序存儲結(jié)構(gòu)是一種 ( )的存儲結(jié) 構(gòu)。 (1) A．操作對象 B．計算方法 *C．物理存儲 D．?dāng)?shù)據(jù)映像 (2) A．結(jié)構(gòu) *B．關(guān)系 C．運算 D．算法 3．?dāng)?shù)據(jù)結(jié)構(gòu)被形式地定義為 (D， R)，其中 D 是 ( (1) )的有限集合， R 是 D 上 ( (2) )的有限集合。 1 數(shù)據(jù)結(jié)構(gòu)習(xí)題答案 第一節(jié) 概 論 一、選擇題 1．要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性，這意味著 ( )。 A．?dāng)?shù)據(jù)元素具有同一的特點 *B．不僅數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致 C．每個數(shù)據(jù)元素都一樣 D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等 2．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的 ( (1) )以及它們之間的 ( (2) )和運算的學(xué)科。 (1) A．算法 *B．?dāng)?shù)據(jù)元素 C．?dāng)?shù)據(jù)操作 D．邏輯結(jié)構(gòu) (2)A．操作 B．映像 C．存儲 *D．關(guān)系 4．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 ( )。 *A．隨機存取 B．順序存取 C．索引存取 D． Hash 存取 6．算法分析的目的是 ( )。 (1) A．計算方法 B．排序方法 *C．解決某一問題的有限運算序列 D．調(diào)度方法 (2) A．可行性、可移植性和可擴充性 *B．可行性、確定性和有窮性 C． 確定性，有窮性和穩(wěn)定性 D．易讀性、穩(wěn)定性和安全性 8．線性表若采用鏈表存儲結(jié)構(gòu)，要求內(nèi)存中可用存儲單元的地址 ( )。 A．線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu) *B．二維數(shù)組是它的每個數(shù)據(jù)元素為一個線性表的線性表 C．棧的操作方式是先進先出 D．隊列的操作方式是先進后出 10．根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù) 據(jù)組織形式，其中解釋錯誤的是 ( )。 A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位 B．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位 C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合 *D．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合 二、判斷題 ╳ 1．?dāng)?shù)據(jù)元素是 數(shù)據(jù)的最小單位。 √ 3．?dāng)?shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像分別稱為存儲結(jié)構(gòu)、結(jié)點、數(shù)據(jù)域。 √ 5．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。 ╳ 7．算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。 三、填空題 1．所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的 ____邏輯關(guān)系 _____。 3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)包括 _____集合結(jié)構(gòu) ___、 _____線性結(jié)構(gòu) ___、 ____樹型結(jié)構(gòu) _____和 __圖狀結(jié)構(gòu) _____四種類型。 5．在樹形結(jié)構(gòu)中，根結(jié)點只有 ___一個 ___，其余每個結(jié)點有且只有 ___一個 ___前驅(qū)結(jié)點；葉結(jié)點沒有 ___后繼 __結(jié)點，其余每個結(jié)點的后繼結(jié)點可 以有 __任意個 __ 7．算法的五個重要特性是 __可行性 ___、 ___確定性 ___、 ___有窮性 ___、 ___輸入 __、 ___輸出 __。 for (i=1； i=n； i++) A[i， i]=0； 9．下列程序段的時間復(fù)雜度是 __ O（ n2） ___。 11．從數(shù)據(jù)結(jié)構(gòu)的觀點看，通常所說的“數(shù)據(jù)”應(yīng)分成三個不同的層次，即 __數(shù)據(jù) __、 __數(shù)據(jù)元素 _和 __數(shù)據(jù)項 ___。 13．通常，存儲結(jié)點之間可以有 ___順序存儲 __、 ____鏈式存儲 __、 ____索引存儲 __、 ___散列存儲 _四種關(guān)聯(lián)方式，稱為四種基本存儲方式。 15．一個算法的時空性能是指該算法的 _時間復(fù)雜度 ___和 ___空間復(fù)雜度 _，前者是算法包含的 __計算量 __，后者是算法需要的 ___存儲量 __。 17．常見時間復(fù)雜度的量級有：常數(shù)階 O(__1_)、對數(shù)階 O(__log2n___)、線性階 O(__n__)、平方階 O(_n2_)和指數(shù)階 O(__2n_)。 18．?dāng)?shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的 __設(shè)計 __和 __實現(xiàn) __。 20．抽象數(shù)據(jù)類型是指一個 __數(shù)學(xué)模型 __以及定義在該模型上的一組操作。 ?? i=1； WHILE (i=n) i=i*2； ?? 答： O(log2n) 2．?dāng)⑹鏊惴ǖ亩x及其重要特性。其中每一條指令表示一個或多個操作。 3．簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素 ，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對象。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。 4．邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么關(guān)系？ 答：在數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是密切相關(guān)的，存儲結(jié)構(gòu)不僅將數(shù)據(jù)元素存儲到計算機中，而且還要表示各數(shù)據(jù)元素之間的邏輯關(guān)系。 5．將數(shù)量級 210， n， n2， n3， nlog2n， log2n， 2n， n!， (2／ 3)n， n2／ 3按增長率進行排列。開始結(jié)點 k k2，終端結(jié)點 k k7。 3 答：數(shù)據(jù)邏輯結(jié)構(gòu)為： D={k1， k2， k3，?， k8}， R={k1， k2， k1， k3， k3， k5， k3， k4， k4， k7， k4， k6， k5， k8}，其邏輯結(jié)構(gòu)類型為樹型結(jié)構(gòu)。 (1)int rec(int n) {if(n==1)return(1)； else return(n*rec(n1))； } (2)x=91； y=100； While (y0) if(x10) y； (3)i=1； j=0； while(i+j=n) if(ij)j++； else i++。試確定下列各程序段中前面加記號 的語句的頻度： (1)i=1； k=0； while(i=n1) {k+=10*i； i++； ) (2) k=0； for(i=1； i=n； i++) for(j=i； j=n： j++) k++； 答： (1)n1 (2)n+(n1)+?? +1=n(n+1)/2 第二節(jié) 線性表 一、選擇題 1．線性結(jié)構(gòu)中的一個結(jié)點代表一個 ( )。 A．每個元素都有一個直接前驅(qū)和直接后繼 B．線性表中至少要有一個元素 C．表中諸元素的排列順序必須是由小到大或由大到小的 D． *除第一個元素和最后一個元素外其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼 3．順序表是線性表的 ( )。 * A． 順序表是用一維數(shù)組實現(xiàn)的線性表，數(shù)組的下標可以看成是元素的絕對地址 B．順序表的所有存儲結(jié)點按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列 C．順序表的特點是：邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰 D．順序表的特點是：邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中 5．對順序表上的插入、刪除算法的時間復(fù)雜度分析來說，通常以 ( )為標準操作。 A．無需為表示結(jié)點間的 邏輯關(guān)系而增加額外的存儲空間 B．可以方便地隨機存取表中的任一結(jié)點 *C．插入和刪除操作較方便 D．由于順序表要求占用連續(xù)的空間，存儲分配只能預(yù)先進行 (靜態(tài)分配 ) 7．在含有 n 個結(jié)點的順序存儲的線性表中，在任一結(jié)點前插入一個結(jié)點所需移動結(jié)點的平均次數(shù)為 ( )。 A． n B． n/2 *C． (n1)/2 D． (n+1)/2 9．帶頭結(jié)點的單鏈表為空的條件是 ( )。 A． pnext=NULL B． p=NULL *C． pnext=head D． p=head 11．在雙循環(huán)鏈表的 *p 結(jié)點之后插入 *s 結(jié)點的操作是 ( )。 A． snext=pnext； pnext=s； B． pnext=snext； snext=p； *C． qnext=s。 snext=q； 13. 在一個單鏈表中，若 *p 結(jié)點不是最后結(jié)點。 A． snext=p； pnext=s。 14. 若某線性表中最常用的操作是取第 i 個元素和找第 i 個元素的前驅(qū)元素，則采用 ( )存儲方式最節(jié)省時間。 A． p=rear； rear=rearnext； free(p) B． rear=rearnext； free(rear)； C． rear=rearnextnext； free(rear)； *D． p=rearnextnext；rearnextnext=pnext； free(p)； 16．在一個單鏈表中，若刪除 *p 結(jié)點的后繼結(jié)點，則執(zhí)行 ( )。 A ． ppriornext==pnextnext B ． ppriorprior==pnextprior *C ． ppr