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