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