【正文】 __s 指向的結(jié)點(diǎn)。 8．對(duì)于一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表，在 p 所指結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為 __O(1)__，在給定值為 x 的結(jié)點(diǎn)后插入新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 __ O(n)__。 a1 稱為 _第一個(gè) _結(jié)點(diǎn)， an 稱為 __最后一個(gè) _結(jié)點(diǎn)， i 稱為 ai 在線性表中的 _位置 __。 ╳ 4．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰。 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．在一個(gè)單鏈表中，若刪除 *p 結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行 ( )。 A． snext=pnext； pnext=s； B． pnext=snext； snext=p； *C． qnext=s。 * 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)操作。 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)類型為樹(shù)型結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。 ?? i=1； WHILE (i=n) i=i*2； ?? 答： O(log2n) 2．?dāng)⑹鏊惴ǖ亩x及其重要特性。 15．一個(gè)算法的時(shí)空性能是指該算法的 _時(shí)間復(fù)雜度 ___和 ___空間復(fù)雜度 _，前者是算法包含的 __計(jì)算量 __，后者是算法需要的 ___存儲(chǔ)量 __。 7．算法的五個(gè)重要特性是 __可行性 ___、 ___確定性 ___、 ___有窮性 ___、 ___輸入 __、 ___輸出 __。 ╳ 7．算法和程序沒(méi)有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。 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)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù) 據(jù)組織形式，其中解釋錯(cuò)誤的是 ( )。 A．?dāng)?shù)據(jù)元素具有同一的特點(diǎn) *B．不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致 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é)科。 A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出的關(guān)系 *C．分析算法的效率以求改進(jìn) D．分析算法的易懂性和文檔性 7．計(jì)算機(jī)算法指的是 ( (1) )，它必須具備輸入、輸出和 ( (2) )等五個(gè)特征。 ╳ 4．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。 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)。 12．根據(jù)需要，數(shù)據(jù)元素又被稱為 __結(jié)點(diǎn) __、 __記錄 __、 ___元素 __或 __頂點(diǎn) _。 19．?dāng)?shù)據(jù)對(duì)象是性質(zhì)相同的 __數(shù)據(jù)元素 _的集合。 答：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。 答： (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)？ 答：圖略。 *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． head=NULL *B． headnext=NULL C． headnext=head D． head!=NULL 10．非空單循環(huán)鏈表 head 的尾結(jié)點(diǎn) *p 滿足 ( )。 *B． snext=pnext； pnext=s； C． snext=pnext； p=s； D． pnext=s； snext=p。 A．單鏈表 B．雙鏈表 C．循環(huán)鏈表 *D．順序表 二、判斷題 √ 1．順序存儲(chǔ)的線性表可以隨機(jī)存取。 ╳ 9．在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。 5．在單鏈表中，刪除 p 所指結(jié)點(diǎn)的直接后繼的操作是 __ q=pnext； pnext=qnext； free(q)； ___ 13．在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 ___前驅(qū) __，另一個(gè)指向 ___后繼 ___。頭指針是指向鏈表中的第一個(gè)結(jié)點(diǎn)的指針。 5．雙鏈表和單循環(huán)鏈表中，若僅知道指針 p 指向某個(gè)結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn) *p 從相應(yīng)的鏈表中刪除？若可以，其時(shí)間復(fù)雜度各為多少？ 答：能刪除。在此情況下，應(yīng)選擇哪一種存儲(chǔ)結(jié)構(gòu)？為什么？ 答：應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 Typedef struct node2 {datatype data。 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è)有序表。 void LinkListinsert(LinkedList *L， int x){／／ x 插入有序鏈表 L 中 q=L； p=q— next； while(p!=NULLamp。試寫(xiě)一算法分別以順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)將 A 和 B 歸并成一個(gè)仍按元素值遞增有序的線性表 C。} (2) VOid Linkmerge(LinkedList *A， LinkedList *B， LinkedList *C) {／／有序鏈表 A 和 B 歸并成有序鏈表 C pa=A— next； pb=B— next； C=A； pc=C； while(paamp。ki) ／／在 la 表中查找第 i 個(gè)結(jié)點(diǎn) {pre=p； p=pnext。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é)束。 答：分析： p 指向待處理的單鏈表的首元結(jié)點(diǎn)，構(gòu)造三個(gè)空的單循環(huán)鏈表，分別存儲(chǔ)三類字符，其中一個(gè)表可使用原來(lái)的單鏈表。(p— data=’ 0’ ) ／／鏈接到數(shù)字鏈表的頭部 {p— next=pb— next； pb— next=p； } else{pnext=pcnext； pcnext=p； }／／鏈接到其他字母鏈表的頭部 p=q； } } 1己知 A、 B 和 C 為三個(gè)遞增有序的線性表 ，現(xiàn)要求對(duì) A 表進(jìn)行如下操作：刪去那些既在 B 表中出現(xiàn)又在 C 表中出現(xiàn)的元素。 else {same=[j]； ／／找到了相同元素 same while([j]==same) j++； while([k]==same) k++； ／ j、 k 后移到新的元素 while(iAlengthamp。 答：分析：在雙循環(huán)鏈表中插入和刪除結(jié)點(diǎn)要注意修改雙向的指針。試寫(xiě)一符合上述要求的 LocateNode 操作的算法。n， amp。分別以數(shù)組和以不帶頭結(jié)點(diǎn)的、已知尾指針的單循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu)解決上述問(wèn)題。以下序列中不可能出現(xiàn)的出棧序列是 ( )。 =(+1)％ maxslze； 8．循環(huán)隊(duì)列的入隊(duì)操作應(yīng)為 ( 初值為 1 )。 A． Topnext=s； B． snext=Topnext； Topnext=s； *C． snext=Top； Top=s； D． snext=Top； Top=Topnext； 15．從棧頂指針為 Top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪結(jié)點(diǎn)的值保存到 x 中，其操作步驟為 ( )。 √ 4．在鏈隊(duì) 中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。 4．假設(shè)以 S 和 X 分別表示入棧和出棧操作，則對(duì)輸入序列 a， b， c， d， e 進(jìn)行一系列棧操作 SSXSXSSXXX之后，得到的輸出序列為 __ b， c， e， d， a ___。 14 9．在隊(duì)列中，新插入的結(jié)點(diǎn)只能添加到 __隊(duì)尾 __。用整型變量 t 來(lái)指示當(dāng)前棧頂?shù)奈恢茫?A[t]為棧頂元素。 第五節(jié) 樹(shù) (樹(shù)根結(jié)點(diǎn)的高度為 1) 一、選擇題 1．以下說(shuō)法錯(cuò)誤的是 ( )。設(shè)空棧時(shí)，輸入序列 a， b， c 經(jīng)過(guò) push， pop， push， push， pop 操作后，從棧中彈出的元素是 ___c__。當(dāng) lq． front==lq． rear 時(shí)，隊(duì)中無(wú)元素，此時(shí) ___隊(duì)空 __。__。 ╳ 6．循環(huán)隊(duì)列中元素個(gè)數(shù)為 rearfront。 A． fnext=s； f=s； *B． rnext=s； r=s； C． snext=r； r=s； D． snext=f； f=s； 17．一個(gè)棧的入棧序列是 a， b， c， d， e，則棧的不可能的輸出序列是 ( )。 A． sq． front=(sq． front+1)％ maxsize； *B． sq． front=sq． front+1； C． sq． rear=(sq． rear+1)％ maxsize； D． sq． rear=sq． rear+1。 *A．通常不會(huì)出現(xiàn)棧滿的情況 B．通常不會(huì)出現(xiàn)?？盏那闆r C．插入操作更容易實(shí)現(xiàn) D．刪除操作更容易實(shí)現(xiàn) 5．若一個(gè)棧的輸入序列是 1， 2， 3， 4，?， n，輸出序列的第一個(gè)元素是 n，則第 i 個(gè)輸出元素是 ( )。i++)A[I]=1； ／／用 1 標(biāo)志在環(huán)上的結(jié)點(diǎn) j=0； for(i=0； iN。 答：分析：對(duì)所有指數(shù)相同的項(xiàng)，將其對(duì)應(yīng)系數(shù)相加，若和不為 0，則構(gòu)造新“和多項(xiàng)式”的結(jié)點(diǎn)；將所有指數(shù)不同的項(xiàng)復(fù)制到和多項(xiàng)式中。 typedef struct DLNode {int data， freq； struct DLNode *prior， *next； }DLNode， *DLinkedList； void LocateNode(DLinkedList head， int x) {／／雙鏈表按訪問(wèn)頻度域 freq 遞減次序排列 p2=head； p1=p2— next； ／／ p2 在前， p1 在后 while(p1) ／／查找單鏈表中值為 x 的結(jié)點(diǎn) if(pl— data==x) {pl— freq++； break； }／／使值為 x 的結(jié)點(diǎn)的 freq 加 1 else {p2=pl； p1=p2— next； } 11 if(p1==NULL) printf(” Not found.＼ n” )； else{if(p1— next==NULL) {p2— next=p1— next； temp=p1； } ／／在鏈表中找 temp 所指向的結(jié)點(diǎn)，按 freq 值遞減應(yīng)插入的位置 else{p2— next=p1— next； ／／插入鏈表中間的某一位置 p1— nextprior=p2； temp=pl； } for(p2=head， p1=p2next； plamp。amp。Adata[i]same)