【正文】 *D． p=rearnextnext；rearnextnext=pnext； free(p)； 16．在一個單鏈表中，若刪除 *p 結(jié)點的后繼結(jié)點，則執(zhí)行 ( )。 A． snext=p； pnext=s。 A． snext=pnext； pnext=s； B． pnext=snext； snext=p； *C． qnext=s。 A． n B． n/2 *C． (n1)/2 D． (n+1)/2 9．帶頭結(jié)點的單鏈表為空的條件是 ( )。 * A． 順序表是用一維數(shù)組實現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對地址 B．順序表的所有存儲結(jié)點按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列 C．順序表的特點是：邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰 D．順序表的特點是：邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中 5．對順序表上的插入、刪除算法的時間復(fù)雜度分析來說，通常以 ( )為標(biāo)準(zhǔn)操作。試確定下列各程序段中前面加記號 的語句的頻度： (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é)點代表一個 ( )。 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)。 5．將數(shù)量級 210， n， n2， n3， nlog2n， log2n， 2n， n!， (2／ 3)n， n2／ 3按增長率進(jìn)行排列。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。 3．簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素 ，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對象。 ?? i=1； WHILE (i=n) i=i*2； ?? 答： O(log2n) 2．?dāng)⑹鏊惴ǖ亩x及其重要特性。 18．?dāng)?shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的 __設(shè)計 __和 __實現(xiàn) __。 15．一個算法的時空性能是指該算法的 _時間復(fù)雜度 ___和 ___空間復(fù)雜度 _，前者是算法包含的 __計算量 __，后者是算法需要的 ___存儲量 __。 11．從數(shù)據(jù)結(jié)構(gòu)的觀點看，通常所說的“數(shù)據(jù)”應(yīng)分成三個不同的層次，即 __數(shù)據(jù) __、 __數(shù)據(jù)元素 _和 __數(shù)據(jù)項 ___。 7．算法的五個重要特性是 __可行性 ___、 ___確定性 ___、 ___有窮性 ___、 ___輸入 __、 ___輸出 __。 3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)包括 _____集合結(jié)構(gòu) ___、 _____線性結(jié)構(gòu) ___、 ____樹型結(jié)構(gòu) _____和 __圖狀結(jié)構(gòu) _____四種類型。 ╳ 7．算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。 √ 3．?dāng)?shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機(jī)中的映像分別稱為存儲結(jié)構(gòu)、結(jié)點、數(shù)據(jù)域。 A．線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu) *B．二維數(shù)組是它的每個數(shù)據(jù)元素為一個線性表的線性表 C．棧的操作方式是先進(jìn)先出 D．隊列的操作方式是先進(jìn)后出 10．根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù) 據(jù)組織形式，其中解釋錯誤的是 ( )。 *A．隨機(jī)存取 B．順序存取 C．索引存取 D． Hash 存取 6．算法分析的目的是 ( )。 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è)計問題中計算機(jī)的 ( (1) )以及它們之間的 ( (2) )和運算的學(xué)科。 (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) )的有限集合。 A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出的關(guān)系 *C．分析算法的效率以求改進(jìn) D．分析算法的易懂性和文檔性 7．計算機(jī)算法指的是 ( (1) )，它必須具備輸入、輸出和 ( (2) )等五個特征。 *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．以下說法正確的是 ( )。 ╳ 4．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位。 √ 8．順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。 4．在線性結(jié)構(gòu)中，開始結(jié)點 __沒有 _前驅(qū)結(jié)點，其余每個結(jié)點有且只有 __一個 _個前驅(qū)結(jié)點。 2 8．下列程序段的時間復(fù)雜度是 __O（ n） ___。 12．根據(jù)需要，數(shù)據(jù)元素又被稱為 __結(jié)點 __、 __記錄 __、 ___元素 __或 __頂點 _。 16．在一般情況下，一個算法的時間復(fù)雜度是 __問題規(guī)模 __的函數(shù)。 19．?dāng)?shù)據(jù)對象是性質(zhì)相同的 __數(shù)據(jù)元素 _的集合。 答：算法是對特定問題求解步驟的一種描述，是指令的有限序列。 答：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計算機(jī)中并被計算機(jī)程序識別和處理的符號的集合。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。 答： (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é)點？ 答：圖略。 8．分析下列程序的時間復(fù)雜度 (設(shè) n 為正整數(shù) )。 *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)，下列說法正確的是 ( )。 A．條件判斷 *B．結(jié)點移動 C．算術(shù)表達(dá)式 D．賦值語句 6．對于順序表的優(yōu)缺點，以下說法錯誤的是 ( )。 A． head=NULL *B． headnext=NULL C． headnext=head D． head!=NULL 10．非空單循環(huán)鏈表 head 的尾結(jié)點 *p 滿足 ( )。 snext=p； D． pnext=s。 *B． snext=pnext； pnext=s； C． snext=pnext； p=s； D． pnext=s； snext=p。 *A． q=pnext； pnext=qnext； free(q)； B． p=pnext； pnext=pnextnext； free(p)； C． pnext=pnext； free(pnext)； D． p=pnextnext；free(pnext)； 17． 設(shè)指針 p 指向雙鏈表的某一結(jié)點，則雙鏈表結(jié)構(gòu)的對稱性可用 ( )式來刻畫。 A．單鏈表 B．雙鏈表 C．循環(huán)鏈表 *D．順序表 二、判斷題 √ 1．順序存儲的線性表可以隨機(jī)存取。 √ 5．在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。 ╳ 9．在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲結(jié)構(gòu)。對任意一對相鄰結(jié)點 ai、 ai+1(1≤ in)， ai 稱為 ai+1 的直接 _前驅(qū) _， ai+1稱為 ai的直接 __后繼 __。 5．在單鏈表中，刪除 p 所指結(jié)點的直接后繼的操作是 __ q=pnext； pnext=qnext； free(q)； ___ 9．單鏈表表示法的基本思想是用 ___指針 ___表示結(jié)點間的邏輯關(guān)系。 13．在雙鏈表中，每個結(jié)點有兩個指針域，一個指向 ___前驅(qū) __，另一個指向 ___后繼 ___。 17．設(shè) r 指向單循環(huán)鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后插入 s 所指的結(jié)點，需執(zhí)行的三條語句是 ___snext= rnext __； rnext=s； r=s； 18．在單鏈表中，指針 p 所指結(jié)點為最后一個結(jié)點的條件是 __ pnext=NULL___。頭指針是指向鏈表中的第一個結(jié)點的指針。 3．在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)點？具體的移動次數(shù)取決于哪兩個因素？ 答：平均移動表中大約一半的結(jié)點，插入操作平均移動 n/2 個結(jié)點，刪除操作平均移動（ n1） /2 個結(jié)點。 5．雙鏈表和單循環(huán)鏈表中，若僅知道指針 p 指向某個結(jié)點，不知道頭指針，能否將結(jié)點 *p 從相應(yīng)的鏈表中刪除？若可以，其時間復(fù)雜度各為多少？ 答：能刪除。Lnext) { q=L； L=Lnext； p=L。在此情況下，應(yīng)選擇哪一種存儲結(jié)構(gòu)？為什么？ 答：應(yīng)選用鏈?zhǔn)酱鎯Y(jié)構(gòu)。因為順序存儲結(jié)構(gòu)存取元素操作的時間復(fù)雜度為 O(1)。 Typedef struct node2 {datatype data。 void Seqreverse(SeqList *L){／／順序表的就地逆置 for(i=0； j=Llength1； ij； i++， j) {t=Ldata[i]。 void Linkedreverse(LinkedList *L){／／鏈表的就地逆置 p=Lnext； Lnext=NULL； while(p!=NULL) {r=p， p=pnext； ／／ r 指向當(dāng)前待逆置的結(jié)點， p 記下下 — 個結(jié)點 rnext=L— next； Lnext=r； ／／放到表頭 } } 2．設(shè)順序表 L 是一個遞增 (允許有相同的值 )有序表，試寫一算法將 x 插入 L 中，并使 L仍為一個有序表。amp。 void LinkListinsert(LinkedList *L， int x){／／ x 插入有序鏈表 L 中 q=L； p=q— next； while(p!=NULLamp。 void LinkedListlnsert(LinkedList *L， int x， int i) {／／不帶頭結(jié)點的單鏈表的第 i 個元素之前插入一個元素 p=L： j=1。試寫一算法分別以順序存儲和鏈?zhǔn)酱鎯?A 和 B 歸并成一個仍按元素值遞增有序的線性表 C。amp。} (2) VOid Linkmerge(LinkedList *A， LinkedList *B， LinkedList *C) {／／有序鏈表 A 和 B 歸并成有序鏈表 C pa=A— next； pb=B— next； C=A； pc=C； while(paamp。 答：分析：先在 la 中找到第 i 個結(jié)點，分別用兩個指針 pre 和 p 指向第 i1 和第 i 個結(jié)點，然后用指針 q 從第 i 個結(jié)點起向后走 len 個元素，使 q 指向此位置。ki) ／／在 la 表中查找第 i 個結(jié)點 {pre=p； p=pnext。 k=1； ／／ j1 時 while(ramp。amp。amp。 答：分析：用三個變量 i、 j、 k 分別指示 A、 B、 C 三個順序表的當(dāng)前位置，若 A、 B 表中當(dāng)前元素值相同，則寫入 C 中，并使 i、 j、 k 值增 1；若 A 表元素值較小，則使 i 增 1；若 B 表元素值較小，則使 j 增 1，直到有一個表先結(jié)束。 s 為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點 *s 的直接前驅(qū)結(jié)點。 答：分析： p 指向待處理的單鏈表的首元結(jié)點，構(gòu)造三個空的單循環(huán)鏈表，分別存儲三類字符，其中一個表可使用原來的單鏈表。 ／／ q 記下 L 中下一個結(jié)點的位置 if(p— data=’ z’ amp。(p— data=’ 0’ ) ／／鏈接到數(shù)字鏈表的頭部 {p— next=pb— next； pb— next=p； } else{pnext=pcnext； pcnext=p； }／／鏈接到其他字母鏈表的頭部 p=q； } } 1己知 A、 B 和 C 為三