【正文】 行插入和刪除操作的線性表，宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)。 8．若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入、刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)該用哪種存儲(chǔ)結(jié)構(gòu)？為什么？ 答：應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。 while((i=Llength1)amp。 SeqList *Seqmerge(SeqList A， SeqList B， SeqList *C){／／有序順序表 A 和 B 歸并成有序順序表 C i=0； j=0； k=0； ／／ i， i， k 分別為順序表 A， B， C 的下標(biāo) while(imamp。klen) {q=q— next； k++； } ／／查找 la 表中第 i+len1 個(gè)結(jié)點(diǎn) if(!q) exit(0)； if(pre==la) la=q— next； ／／ i=1 的情況 else pre— next=q— next； ／／完成刪除 ／／將從 la 中刪除的結(jié)點(diǎn)插入到 lb 中 if(j==1) {qnext=lb； lb=p； } ／／ j=1 時(shí) 8 else { r=lb。(j=)) {if([i]==[j]) ／／找到值相同的元素 {Cdata[k]=[i]； ／／相同元素寫入 C 表中 k++； i++； j++； } else if([i][j]) i++；／／ A、 B 表當(dāng)前元素不等，值較小的下標(biāo)增 1 else j++； } Clength=k； return C； } 9 11．假設(shè)在長度大于 1 的 單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。 ／／ i 指示 A 中元素原來的位置， m 為移動(dòng)后的位置 while(iAlengthamp。pdata!=x) p=pnext； ／／在鏈表中查找值為 x 的結(jié)點(diǎn) if(pdata==x) ／／找到值為 x 的結(jié)點(diǎn) {q=pprior； ／／ q 指向值為 x 的結(jié)點(diǎn)的前驅(qū) s=(DLinkedList)malloc(sizeof(DLNode))； sdata=y； snext=p； sprior=q； ／／將 y 插入到 q 與 p 指向的結(jié)點(diǎn)之間 pprior=s； qnext=s； } else{printf(”沒有值為 x 的結(jié)點(diǎn)” )； exit(0)； } } void DLDelete(DLinkedList L， int x) {／／在雙循環(huán)鏈表中刪除結(jié)點(diǎn) p=Lnext； while(p!=Lamp。 Plink add(PLink pa， PLink pb) {／／多項(xiàng) 式相加 p=pa； q=pb； pc=(PLink)malloc(sizeof(struct PNode))； r=pc； while(p!=NULLamp。 A．不確定 B． ni *C． ni+1 D． ni1 6．以下說法正確的是 ( )。 A． e， d， c， b， a B． d， e， c， b， a *C． d， c， e， a， b D． a， b， c， d， e 18．一個(gè)隊(duì)列的入隊(duì)序列是 1， 2， 3， 4，則隊(duì)列可能的輸出序列是 ( )。 6．在一個(gè)鏈隊(duì)中，如果 f、 r 分別為隊(duì)頭、隊(duì)尾指針，則插入 s 所指結(jié)點(diǎn)的操作是 _rnext=s。 四、應(yīng)用題 2．設(shè)有字符串為 3*ya/y^2，試?yán)脳懗鰧⑵滢D(zhuǎn)換為 3y*ay2^/的操作過程。 14．設(shè)用一維數(shù)組 A[n]來表示一個(gè)棧，令 A[0]為棧底。 3．在具有 n 個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 ___n1_個(gè)元素。 A．必須判別棧是否滿 B．判別棧元素的類型 *C．必須判別棧是否空 D．對(duì)棧不做任何判別 14，向一個(gè)棧頂指針為 Top 的鏈棧中插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，其操作步驟為 ( )。 A． 4 *B． 5 C． 6 D． 7 3．設(shè)有一順序棧已經(jīng)含有 3 個(gè)元素，如圖 31 所示，元素 a4 正等待入棧。m)； while(n!=0) ／／若 n=0 則退出循環(huán) {s=(Plink)malloc(sizeof(struct PNode))； scoef=n； sexp=m； rnext=s； r=s；／／把 s 鏈接到 r 的后面 printf(”輸入系數(shù)和指數(shù) :” )； scanf(amp。 (2)刪除值為 x 的結(jié)點(diǎn)。amp。用順序表實(shí)現(xiàn)并寫出 C 的算法。amp。ji1) ／／找到第 i1 個(gè)元素 {p=p— next； j++； } if(i=0||p==NULL) printf(”插入位置不正確＼ n” )； else {q=(LinkedList*)malloc(sizeof(LinkedList))； q— data=x； 7 if(i==1) {q— next=L； L=q； } ／／在第一個(gè)元素之前插入 else{q— next=p— next； p— next=q； } ／／在其他位置插入 } } 5．設(shè) A、 B 是兩個(gè)線性表，其表中元素遞增有序，長度分別為 m 和 n。 } } (2)鏈表的就地逆置 分析：本算法的思想是逐個(gè)地把 L 的當(dāng)前元素 r 插入到新的鏈表頭部。 7．如果有 n 個(gè)線性表同時(shí)共存，并且在處理過程中各表的長度會(huì)發(fā)生動(dòng)態(tài)變化，線性表的總長度也會(huì)自動(dòng)地改變。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。 4．線性表的邏輯結(jié)構(gòu)是 __線性 _結(jié)構(gòu)，其所含結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的 ___長度 _。 A．不再需要頭指針了 B．已知某個(gè)結(jié)點(diǎn)的位置后，容易找到它的直接前驅(qū) C．在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開 *D．從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表 20．在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是 ( )。 A． n B． n/2 *C． (n1)/2 D． (n+1)/2 9．帶頭結(jié)點(diǎn)的單鏈表為空的條件是 ( )。 5．將數(shù)量級(jí) 210， n， n2， n3， nlog2n， log2n， 2n， n!， (2／ 3)n， n2／ 3按增長率進(jìn)行排列。 18．?dāng)?shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的 __設(shè)計(jì) __和 __實(shí)現(xiàn) __。 3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)包括 _____集合結(jié)構(gòu) ___、 _____線性結(jié)構(gòu) ___、 ____樹型結(jié)構(gòu) _____和 __圖狀結(jié)構(gòu) _____四種類型。 *A．隨機(jī)存取 B．順序存取 C．索引存取 D． Hash 存取 6．算法分析的目的是 ( )。 *A．集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散 B．線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鎖鏈” C．樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹 D．圖狀結(jié)構(gòu)中的各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接 11．以下說法正確的是 ( )。 2 8．下列程序段的時(shí)間復(fù)雜度是 __O（ n） ___。 答：算法是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。 8．分析下列程序的時(shí)間復(fù)雜度 (設(shè) n 為正整數(shù) )。 snext=p； D． pnext=s。 √ 5．在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。 9．單鏈表表示法的基本思想是用 ___指針 ___表示結(jié)點(diǎn)間的邏輯關(guā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)。因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)存取元素操作的時(shí)間復(fù)雜度為 O(1)。amp。amp。 k=1； ／／ j1 時(shí) while(ramp。 s 為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn) *s 的直接前驅(qū)結(jié)點(diǎn)。amp。amp。amp。 *A．因鏈棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會(huì)出現(xiàn)棧滿情況 B．因順序棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會(huì)出現(xiàn)棧滿情況 C．對(duì)于鏈棧而言，在棧滿狀態(tài)下，如果再進(jìn)行 入棧操作，則會(huì)發(fā)生“上溢” D．對(duì)于順序棧而言，在棧滿狀態(tài)下，如果再進(jìn)行入棧操作，則會(huì)發(fā)生“下溢” 7．順序隊(duì)列的入隊(duì)操作應(yīng)為 ( 初值為 1 )。 A． 4， 3， 2， 1 *B． 1， 2， 3， 4 C． 1， 4， 3， 2 D． 3， 2， 4， 1 19．設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用 ( )數(shù)據(jù)結(jié)構(gòu)最佳。 r=s。假定用 X 代表掃描該字符串過程中順序取 一個(gè)字符入棧的操作，用 S 代表從棧中取出一個(gè)字符加入到新字符串尾的出棧操作。 13．設(shè)有一個(gè)空棧，現(xiàn)在輸入序列為 1， 2， 3， 4， 5，經(jīng)過 push， push， pop， push， pop， push 后，棧頂指針?biāo)冈厥?__4__。 2．從棧頂指針為 Top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將結(jié)點(diǎn)保存在 x 中，進(jìn)行的操作是 _ x=Topdata； Top=Topnext； __。 A． (sq． rear+1)％ maxsize==(sq． front+1)％ maxsize； B． (sq． rear+1)％ maxsize==sq． front+1； C． (sq． rear+1)％ maxsize==sq． front； *D． sq． rear==sq． front； 13．如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則出棧操作時(shí) ( )。 A． 2 *B． 3 C． 5 D． 6 2．若一個(gè)棧的輸入序列是 a、 b、 c，則通過入棧、出棧操作可能得到 a、 b、 c 的不同排列個(gè)數(shù)為 ( )。n， amp。 (1)在值為 x 的結(jié)點(diǎn)之前插入值為 y 的結(jié)點(diǎn)。p— data=’ a’ ) ／／鏈接到字母鏈表的頭部 {p— next=pa— next； pa— next=p； } else if (p— data=’ 9’ amp。個(gè)結(jié)點(diǎn) p=p— next； ／／ p 指向原鏈表 A 中的奇數(shù)序號(hào)的結(jié)點(diǎn) } r— next=NULL； ／／將生成 B 鏈表中的最后一個(gè)結(jié)點(diǎn)的 next 域置為空 } 9．假設(shè)以兩個(gè)元素值遞增有序排列的線性表 A、 B 分別表示兩個(gè)集合，要求另辟空間構(gòu)造一個(gè)線性表 C，其元素為兩集合的交集，且表 C 中的元素值也遞增有序排列。 void Deletelnsert(LinkedList *la， LinkedList *lb， int i， int j, int len) {／／刪除不帶頭結(jié)點(diǎn)的單鏈表 la 中第 i 個(gè)元素起共 len 個(gè)元素 ,并將這峰元素插入到單鏈表 lb中第 j個(gè)結(jié)點(diǎn)之前 if(i0||j0||len0) exit(0)； p=la； k=1； pre=NULL； while(pamp。amp。 Ldata[j]=t。 qnext=NULL； } return L； } 答：如果長度大于 1，則將首元結(jié)點(diǎn)刪除并插入到表尾。 答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)的線性表中的第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。 5 3．所有結(jié)點(diǎn)按一對(duì)一的鄰接關(guān)系構(gòu)成的整體就是 __線性 __結(jié)構(gòu)。 A． rear 和 rearnextnext *B． rearnext 和 rear C． rearnextnext 和 rear D． rear 和 rearnext 19．循環(huán)鏈表的主要優(yōu)點(diǎn)是 ( )。 4 A． n *B． n/2 C． (n1)/2 D． (n+1)/2 8．在含有 n 個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，刪除一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為 ( )。邏輯結(jié)構(gòu)與計(jì)算機(jī)無關(guān)，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù) 元素之間的關(guān)系在計(jì)算機(jī)中的表示。通常認(rèn)為，具有指數(shù)階量級(jí)的算法是 __不可行 __的。 2， 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容 ___數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、對(duì)數(shù)據(jù)施加的操作 ___。 A．動(dòng)態(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．線性表的順序存儲(chǔ)結(jié)構(gòu)是一種 ( )的存儲(chǔ)結(jié) 構(gòu)。 A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位 B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位 C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合 *D．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合 二、判斷題 ╳ 1．?dāng)?shù)據(jù)元素是 數(shù)據(jù)的最小單位。