【正文】 tn； t++) {Cdata[k]=[t]。 void Deletelnsert(LinkedList *la， LinkedList *lb， int i， int j, int len) {／／刪除不帶頭結(jié)點的單鏈表 la 中第 i 個元素起共 len 個元素 ,并將這峰元素插入到單鏈表 lb中第 j個結(jié)點之前 if(i0||j0||len0) exit(0)； p=la； k=1； pre=NULL； while(pamp。kj1) {r=r— next； k++； } ／／查找 Lb 表中第 i— 1 個元素 if(!r) exit(0)； q— next=r— next； r— next=p； ／／完成插入 } } 7．單鏈表 L 是一個遞減有序表，試寫一高效算法，刪除表中值大于 min 且小于 max 的結(jié)點 (若表中有這樣的結(jié)點 )，同時釋放被刪結(jié)點空間，這里 min 和 max是兩個給定的參數(shù)。個結(jié)點 p=p— next； ／／ p 指向原鏈表 A 中的奇數(shù)序號的結(jié)點 } r— next=NULL； ／／將生成 B 鏈表中的最后一個結(jié)點的 next 域置為空 } 9．假設(shè)以兩個元素值遞增有序排列的線性表 A、 B 分別表示兩個集合，要求另辟空間構(gòu)造一個線性表 C，其元素為兩集合的交集，且表 C 中的元素值也遞增有序排列。 void DeletePre(Linkedlist *s) {／／刪除單循環(huán)鏈表中結(jié)點 s 的直接前驅(qū) p=s； while(p— next— next!=s) p=p— next； ／／找到 s 的前驅(qū)的前驅(qū) p q=p— next； ／／ q 是 p 的后繼，即 s 的前驅(qū) p— next=s； ／／將 q 刪除 free(q)； } 12．計算帶頭結(jié)點的循環(huán)鏈表的結(jié)點個數(shù)。p— data=’ a’ ) ／／鏈接到字母鏈表的頭部 {p— next=pa— next； pa— next=p； } else if (p— data=’ 9’ amp。amp。 (1)在值為 x 的結(jié)點之前插入值為 y 的結(jié)點。 答： typedef struct Node {DataType data； struct Node *prior， *next； }DLNode， *DLinkedList； void DLchange(DLinkedList p) {／／將雙循環(huán)鏈表中 p 指向的結(jié)點與其右邊的一個結(jié)點進行交換 q=p— next； ／／ q 指向 p 的后繼 p— prior— next=q； q— prior=p— prior； ／／將 p 的前驅(qū)與 q 相鏈接 p— next=q— next； p— prior=q； ／／將 p 插入到 q 之后 qnext— prior=p； q— next=p； } 17．設(shè)有一個雙鏈表，每個結(jié)點中除有 prior、 data 和 next 三個域外，還有一個可訪問頻度域 freq，在鏈表啟用之前，其初始值均為 0。n， amp。 } 20．約瑟夫環(huán)問題：任給正整數(shù) n、 k，按下述方法可得排列 1， 2，?， n 的一個置換：將數(shù)字 l， 2，?， n 環(huán)形排列，按順時針方向從 1 開始計數(shù)；計 滿 k時輸出該位置上的數(shù)字 (并從環(huán)中刪去該數(shù)字 )，然后從下一個數(shù)字開始繼續(xù)計數(shù)，直到環(huán)中所有數(shù)字均被輸出為止。 A． 2 *B． 3 C． 5 D． 6 2．若一個棧的輸入序列是 a、 b、 c，則通過入棧、出棧操作可能得到 a、 b、 c 的不同排列個數(shù)為 ( )。 B． []=x； =+1； C． =(+1)％ maxsize； [+1]=x。 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．如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時 ( )。 ╳ 2．與順序棧相比，鏈棧的一個優(yōu)點是插入和刪除操作更加方便。 2．從棧頂指針為 Top 的鏈棧中刪除一個結(jié)點，并將結(jié)點保存在 x 中，進行的操作是 _ x=Topdata； Top=Topnext； __。 7．棧的邏輯特點是 __后進先出 ____，隊列的邏輯特點是 _先進先出 __，二者的共同特點是 _操作受限 __。 13．設(shè)有一個空棧，現(xiàn)在輸入序列為 1， 2， 3， 4， 5，經(jīng)過 push， push， pop， push， pop， push 后，棧頂指針所指元素是 __4__。 答： XSXXXSSSXXSXXSXXSSSS 3．設(shè)有一個輸入序列 a， b， c， d，元素經(jīng)過一個棧到達輸出序列，而且元素一旦離開輸入序列就不能再回到輸入序列，試問經(jīng)過這個棧后可以得到多少種輸出序列 ? 答：可以得到 14 種輸出序列： abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba,badc. 4．按照運算符優(yōu)先法 ，畫出對下面算術(shù)表達式求值時，操作數(shù)棧和運算符棧的變化過程： 92*4+(8+1)/3。假定用 X 代表掃描該字符串過程中順序取 一個字符入棧的操作，用 S 代表從棧中取出一個字符加入到新字符串尾的出棧操作。 ___ ls = ls next __；free(p)。 r=s。 ╳ 9．若以鏈表作為棧的存儲結(jié)構(gòu)，則入棧需要判斷棧是否滿． √ 10．若以鏈表作為棧的存儲結(jié)構(gòu)，則出棧需要判斷棧是否空。 A． 4， 3， 2， 1 *B． 1， 2， 3， 4 C． 1， 4， 3， 2 D． 3， 2， 4， 1 19．設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用 ( )數(shù)據(jù)結(jié)構(gòu)最佳。 *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+l； 11．循環(huán)隊列的隊滿條件為 ( )。 *A．因鏈棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況 B．因順序棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況 C．對于鏈棧而言，在棧滿狀態(tài)下，如果再進行 入棧操作，則會發(fā)生“上溢” D．對于順序棧而言，在棧滿狀態(tài)下，如果再進行入棧操作，則會發(fā)生“下溢” 7．順序隊列的入隊操作應(yīng)為 ( 初值為 1 )。／／將計滿 k 值的數(shù)字輸出，并將其位置標為 0 表明已刪除 } } void Js2(LinkedList last， int N， int K) {／／以不帶頭結(jié)點的、已知尾指針的單循環(huán)鏈表為存儲結(jié)構(gòu) p=last； q=pnext； ／／此時 q 為頭結(jié)點 fp 為 q 的前驅(qū) while(N0) {for(j=2； j=K； j++) ／／循環(huán) K1 次 {p=q； q=pnext； } printf(” %d”， qdata)； N； pnext=qnext。amp。p1freqtempfreq； p2=p1， pl=p2next)；／／插入 if(p1==NULL) {p2next=temp； tempprior=p2； tempnext=NULL； } else {p2next=temp； tempprior=p2； tempnext=pl； p1prior=temp； } } } 18．給出用單鏈表存儲多項式的結(jié)構(gòu)，并編寫一個按指數(shù)值遞增次序輸入所產(chǎn)生的多項式鏈表的過程。amp。Adata[i]==same。amp。 ／／ q 記下 L 中下一個結(jié)點的位置 if(p— data=’ z’ amp。 s 為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點 *s 的直接前驅(qū)結(jié)點。amp。 k=1； ／／ j1 時 while(ramp。 答：分析：先在 la 中找到第 i 個結(jié)點，分別用兩個指針 pre 和 p 指向第 i1 和第 i 個結(jié)點，然后用指針 q 從第 i 個結(jié)點起向后走 len 個元素，使 q 指向此位置。amp。 void LinkedListlnsert(LinkedList *L， int x， int i) {／／不帶頭結(jié)點的單鏈表的第 i 個元素之前插入一個元素 p=L： j=1。amp。 void Seqreverse(SeqList *L){／／順序表的就地逆置 for(i=0； j=Llength1； ij； i++， j) {t=Ldata[i]。因為順序存儲結(jié)構(gòu)存取元素操作的時間復(fù)雜度為 O(1)。Lnext) { q=L； L=Lnext； p=L。 3．在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)點？具體的移動次數(shù)取決于哪兩個因素？ 答：平均移動表中大約一半的結(jié)點，插入操作平均移動 n/2 個結(jié)點，刪除操作平均移動（ n1） /2 個結(jié)點。 17．設(shè) r 指向單循環(huán)鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后插入 s 所指的結(jié)點，需執(zhí)行的三條語句是 ___snext= rnext __； rnext=s； r=s； 18．在單鏈表中，指針 p 所指結(jié)點為最后一個結(jié)點的條件是 __ pnext=NULL___。 9．單鏈表表示法的基本思想是用 ___指針 ___表示結(jié)點間的邏輯關(guān)系。對任意一對相鄰結(jié)點 ai、 ai+1(1≤ in)， ai 稱為 ai+1 的直接 _前驅(qū) _， ai+1稱為 ai的直接 __后繼 __。 √ 5．在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。 *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)的對稱性可用 ( )式來刻畫。 snext=p； D． pnext=s。 A．條件判斷 *B．結(jié)點移動 C．算術(shù)表達式 D．賦值語句 6．對于順序表的優(yōu)缺點，以下說法錯誤的是 ( )。 8．分析下列程序的時間復(fù)雜度 (設(shè) n 為正整數(shù) )。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。 答：算法是對特定問題求解步驟的一種描述，是指令的有限序列。 16．在一般情況下，一個算法的時間復(fù)雜度是 __問題規(guī)模 __的函數(shù)。 2 8．下列程序段的時間復(fù)雜度是 __O（ n） ___。 √ 8．順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。 *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．以下說法正確的是 ( )。 (1) A．操作對象 B．計算方法 *C．物理存儲 D．數(shù)據(jù)映像 (2) A．結(jié)構(gòu) *B．關(guān)系 C．運算 D．算法 3．數(shù)據(jù)結(jié)構(gòu)被形式地定義為 (D， R)，其中 D 是 ( (1) )的有限集合， R 是 D 上 ( (2) )的有限集合。 *A．隨機存取 B．順序存取 C．索引存取 D． Hash 存取 6．算法分析的目的是 ( )。 √ 3．數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像分別稱為存儲結(jié)構(gòu)、結(jié)點、數(shù)據(jù)域。 3．數(shù)據(jù)的邏輯結(jié)構(gòu)包括 _____集合結(jié)構(gòu) ___、 _____線性結(jié)構(gòu) ___、 ____樹型結(jié)構(gòu) _____和 __圖狀結(jié)構(gòu) _____四種類型。 11．從數(shù)據(jù)結(jié)構(gòu)的觀點看，通常所說的“數(shù)據(jù)”應(yīng)分成三個不同的層次，即 __數(shù)據(jù) __、 __數(shù)據(jù)元素 _和 __數(shù)據(jù)項 ___。 18．數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的 __設(shè)計 __和 __實現(xiàn) __。 3．簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素 ，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對象。 5．將數(shù)量級 210， n， n2， n3， nlog2n， log2n， 2n， n!， (2／ 3)n， n2／ 3按增長率進行排列。試確定下列各程序段中前面加記號 的語句的頻度： (1)i=1； k=0；