第1章緒論一、選擇題1.算法的計算量的大小稱為計算的（）?！颈本┼]電大學2000二、3（20/8分）】A．效率B.復雜性C.現(xiàn)實性D.難度2.算法的時間復雜度取決于（）【中科院計算所1998二、1（2分）】A．問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B3.計算機算法指的是（1），它必須具備（2）這三個特性。(1)A．計算方法B.排序方法C.解決問題的步驟序列D.調(diào)度方法(2)A．可執(zhí)行性、可移植性、可擴充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性4．一個算法應該是（）?！局猩酱髮W1998二、1（2分）】A．程序B．問題求解步驟的描述C．要滿足五個基本特性D．A和C.5.下面關于算法說法錯誤的是（）【南京理工大學2000一、1（1.5分）】A．算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的6.下面說法錯誤的是（）【南京理工大學2000一、2（1.5分）】(1）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模n下，復雜度O(n)的算法在時間上總是優(yōu)于復雜度O(2n)的算法（3）所謂時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界（4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)7．從邏輯上可以把數(shù)據(jù)結構分為（）兩大類。【武漢交通科技大學1996一、4（2分）】A．動態(tài)結構、靜態(tài)結構B．順序結構、鏈式結構C．線性結構、非線性結構D．初等結構、構造型結構8．以下與數(shù)據(jù)的存儲結構無關的術語是（）?！颈狈浇煌ù髮W2000二、1（2分）】A．循環(huán)隊列B.鏈表C.哈希表D.棧9．以下數(shù)據(jù)結構中，哪一個是線性結構（）？【北方交通大學2001一、1（2分）】A．廣義表B.二叉樹C.稀疏矩陣D.串10．以下那一個術語與數(shù)據(jù)的存儲結構無關？（）【北方交通大學2001一、2（2分）】A．棧B.哈希表C.線索樹D.雙向鏈表13．以下哪個數(shù)據(jù)結構不是多型數(shù)據(jù)類型（）【中山大學1999一、3（1分）】A．棧B．廣義表C．有向圖D．字符串14．以下數(shù)據(jù)結構中，（）是非線性數(shù)據(jù)結構【中山大學1999一、4】A．樹B．字符串C．隊D．棧15.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結構?！颈本├砉ご髮W2001六、1（2分）】A．棧B.隊列C.完全二叉樹D.堆16．連續(xù)存儲設計時，存儲單元的地址（）?！局猩酱髮W1999一、1（1分）】A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)17．以下屬于邏輯結構的是（）。【西安電子科技大學應用2001一、1】A．順序表B.哈希表C.有序表D.單鏈表二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()2.記錄是數(shù)據(jù)處理的最小單位。()【上海海運學院1998一、5（1分）】3.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系；()【北京郵電大學2002一、1（1分）】4．算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。()5．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()6．算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。()7．程序一定是算法。()【燕山大學1998二、2（2分）并改錯】8．數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。()【山東師范大學2001一、2（2分）】9.數(shù)據(jù)結構的抽象操作的定義與具體實現(xiàn)有關。()【華南理工大學2002一、1（1分）】10.在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。()11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()12.數(shù)據(jù)結構的基本操作的設置的最重要的準則是，實現(xiàn)應用程序與存儲結構的獨立。()13.數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系,它依賴于計算機的儲存結構.()三、填空1．數(shù)據(jù)的物理結構包括的表示和的表示?！狙嗌酱髮W1998一、1（2分）】2.對于給定的n個元素,可以構造出的邏輯結構有（1），（2），（3），__（4）_四種。3．數(shù)據(jù)的邏輯結構是指?！颈本┼]電大學2001二、1（2分）】4．一個數(shù)據(jù)結構在計算機中稱為存儲結構?！救A中理工大學2000一、1（1分）】5．抽象數(shù)據(jù)類型的定義僅取決于它的一組__（1）_，而與_（2）_無關，即不論其內(nèi)部結構如何變化，只要它的_（3）_不變，都不影響其外部使用?！旧綎|大學2001三、3（2分）】6．數(shù)據(jù)結構中評價算法的兩個重要指標是【北京理工大學2001七、1（2分）】7.數(shù)據(jù)結構是研討數(shù)據(jù)的_（1）_和_（2）_，以及它們之間的相互關系，并對與這種結構定義相應的_（3）_，設計出相應的（4）_。【西安電子科技大學1998二、2（3分）】8．一個算法具有5個特性:（1）、（2）、（3），有零個或多個輸入、有一個或多個輸出。11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：【合肥工業(yè)大學1999三、1（2分）】i：=1；WHILEi<nDOi：=i*2;12.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是()。【合肥工業(yè)大學2000三、1（2分）】i:=1;WHILEi<nBEGINFORj:=1TOnDOx:=x+1;i:=i*2END；13.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是()【合肥工業(yè)大學2001三、1（2分）】i：=n*n WHILEi<>1DOi:=idiv2;14.計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為_______。【南京理工大學2000二、1（1.5分）】FOR(i=l；i<n-l；i++)FOR(j=n;j>=i;j--)s;15.下面程序段的時間復雜度為________。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;【南京理工大學2001二、1（2分）】16．設m.n均為自然數(shù)，m可表示為一些不超過n的自然數(shù)之和，f(m,n)為這種表示方式的數(shù)目。例f(5,3)=5，有5種表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。①以下是該函數(shù)的程序段，請將未完成的部分填入，使之完整intf(m,n)intm,n;{if(m==1)return(1);if(n==1){return(2);}if(m<n){returnf(m,m);}if(m==n){return1+(3);}returnf(m.n-1)+f(m-n,(4));}②執(zhí)行程序，f(6,4)=?！局锌圃很浖?997二、1（9分）】

17.在有n個選手參加的單循環(huán)賽中，總共將進行______場比賽?！竞戏使I(yè)大學1999三、8（2分）】四、應用題1.數(shù)據(jù)結構是一門研究什么內(nèi)容的學科？【燕山大學1999二、1（4分）】2.數(shù)據(jù)元素之間的關系在計算機中有幾種表示方法？各有什么特點？【燕山大學1999二、2（4分）】3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？【北京郵電大學1994一（8分）】4.回答問題（每題2分）【山東工業(yè)大學1997一（8分）】（1）在數(shù)據(jù)結構課程中，數(shù)據(jù)的邏輯結構，數(shù)據(jù)的存儲結構及數(shù)據(jù)的運算之間存在著怎樣的關系？（2）若邏輯結構相同但存儲結構不同，則為不同的數(shù)據(jù)結構。這樣的說法對嗎？舉例說明之。（3）在給定的邏輯結構及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)結構。這樣說法對嗎？舉例說明之。（4）評價各種不同數(shù)據(jù)結構的標準是什么？5．評價一個好的算法，您是從哪幾方面來考慮的？6．解釋和比較以下各組概念【華南師范大學2000一（10分）】（1）抽象數(shù)據(jù)類型及數(shù)據(jù)類型（2）數(shù)據(jù)結構、邏輯結構、存儲結構（3）抽象數(shù)據(jù)類型（4）算法的時間復雜性（5）算法（6）頻度7.根據(jù)數(shù)據(jù)元素之間的邏輯關系，一般有哪幾類基本的數(shù)據(jù)結構？8．對于一個數(shù)據(jù)結構，一般包括哪三個方面的討論？【北京科技大學1999一、1（2分）】9.當你為解決某一問題而選擇數(shù)據(jù)結構時，應從哪些方面考慮？【西安電子北京科技大學2000】10.若將數(shù)據(jù)結構定義為一個二元組（D，R）,說明符號D，R應分別表示什么？11．數(shù)據(jù)結構與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學2001三、1（3分）】12．數(shù)據(jù)的存儲結構由哪四種基本的存儲方法實現(xiàn)？【山東科技大學2001一、1（4分）】13．若有100個學生，每個學生有學號，姓名，平均成績，采用什么樣的數(shù)據(jù)結構最方便，寫出這些結構？14.運算是數(shù)據(jù)結構的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結構的邏輯結構和存儲方式完全相同，只是對于運算的定義不同。因而兩個結構具有顯著不同的特性，是兩個不同的結構。15.在編制管理通訊錄的程序時,什么樣的數(shù)據(jù)結構合適?為什么?【長沙鐵道學院1998四、3(6分)】16.試舉一例，說明對相同的邏輯結構,同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同。17.有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復雜度為Tl=O(2n)，A2的時間復雜度為T2=O(n2)，僅就時間復雜度而言，請具體分析這兩個算法哪一個好。【北京航空航天大學2000二（10分）】18．設計一數(shù)據(jù)結構，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)。【浙江大學1994一、3（5分）】23.調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n)回答下列問題:（1）試指出f(n)值的大小，并寫出f(n)值的推導過程;（2）假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結果。C函數(shù)：intf(intn){inti,j，k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--)for(k=1;k<j+1;k++)sum++;printf("sum=%d\n",sum)；}return(sum);}【華中理工大學2000六（10分）】25．有下列運行時間函數(shù)：（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;分別寫出相應的大O表示的運算時間。27.斐波那契數(shù)列Fn定義如下F0=0，F(xiàn)l=1，F(xiàn)n=Fn-1+Fn-2,n=2,3...請就此斐波那契數(shù)列，回答下列問題。(1)(7分)在遞歸計算Fn的時候，需要對較小的Fn-1，F(xiàn)n-2，…,Fl,F0精確計算多少次?(2)(5分)如果用大O表示法，試給出遞歸計算Fn時遞歸函數(shù)的時間復雜度錄多少?28．將下列函數(shù)，按它們在n→∝時的無窮大階數(shù)，從小到大排序。n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,,n!,n2+logn第2章線性表一選擇題1．下述哪一條是順序存儲結構的優(yōu)點？（）【北方交通大學2001一、4（2分）】A．存儲密度大B．插入運算方便C．刪除運算方便D．可方便地用于各種邏輯結構的存儲表示2．下面關于線性表的敘述中，錯誤的是哪一個？（）【北方交通大學2001一、14（2分）】A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。3．線性表是具有n個（）的有限序列（n>0）?！厩迦A大學1998一、4（2分）】A．表元素B．字符C．數(shù)據(jù)元素D．數(shù)據(jù)項E．信息項4．若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間?！竟枮I工業(yè)大學2001二、1（2分）】A．順序表B．雙鏈表C．帶頭結點的雙循環(huán)鏈表D．單循環(huán)鏈表5．某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。【南開大學2000一、3】A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表6．設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用()最節(jié)省時間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結點的雙循環(huán)鏈表7．若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點。則采用（）存儲方式最節(jié)省運算時間。【北京理工大學2000一、1（2分）】A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．帶頭結點的雙循環(huán)鏈表8.靜態(tài)鏈表中指針表示的是（）.【北京理工大學2001六、2（2分）】A．內(nèi)存地址B．數(shù)組下標C．下一元素地址D．左、右孩子地址9.鏈表不具有的特點是（）【福州大學1998一、8(2分)】A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D所需空間與線性長度成正比10.下面的敘述不正確的是（）【南京理工大學1996一、10（2分）】A．線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比B.線性表在鏈式存儲時，查找第i個元素的時間同i的值無關C.線性表在順序存儲時，查找第i個元素的時間同i的值成正比D.線性表在順序存儲時，查找第i個元素的時間同i的值無關11.線性表的表元存儲方式有(（1）)和鏈接兩種。試指出下列各表中使用的是何種存儲方式：表1是(（2）)存儲方式；表2是(（3）)存儲方式；表3是(（4）)存儲方式；表4是(（5）)存儲方式。表左的s指向起始表元。表元編號貨號數(shù)量表元間聯(lián)系16184022205233103154450120557811766910240表1s→

表元編號貨號數(shù)量表元間聯(lián)系16184052205213103154450120257811766910243表2s→

表元編號貨號數(shù)量表元間聯(lián)系16184052205213103154450120057811766910243表3s→

表元編號貨號數(shù)量表元間聯(lián)系1216184052220521031031546450120035781176169102435表4s→

供選擇的答案：A.連續(xù)B.單向鏈接C.雙向鏈接D.不連接E.循環(huán)鏈接F.樹狀G.網(wǎng)狀H.隨機I.順序J.順序循環(huán)12.(1)靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關。(2)靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。(3)靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（）A．（1），（2）B．（1）C．（1），（2）,(3)D.（2）13.若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為（）(1<=i<=n+1)?！颈本┖娇蘸教齑髮W1999一、1（2分）】A.O(0)B.O(1)C.O(n)D.O(n2)14.對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)15．線性表（a1,a2,…,an）以鏈接方式存儲時，訪問第i位置元素的時間復雜性為（）A．O（i）B．O（1）C．O（n）D．O（i-1）【中山大學1999一、2】16．非空的循環(huán)單鏈表head的尾結點p↑滿足（）?！疚錆h大學2000二、10】A．p↑.link=headB．p↑.link=NILC．p=NILD．p=head17．循環(huán)鏈表H的尾結點P的特點是（）?！局猩酱髮W1998二、2（2分）】A．P^.NEXT:=HB．P^.NEXT:=H^.NEXTC．P:=HD．P:=H^.NEXT18．在一個以h為頭的單循環(huán)鏈中，p指針指向鏈尾的條件是（）【南京理工大學1998一、15（2分）】A.p＾.next=hB.p＾.next=NILC.p＾.next.＾next=hD.p＾.data=-119．完成在雙循環(huán)鏈表結點p之后插入s的操作是（）；【北方交通大學1999一、4（3分）】A．p^.next:=s;s^.priou:=p;p^.next^.priou:=s;s^.next:=p^.next;B．p^.next^.priou:=s;p^.next:=s;s^.priou:=p;s^.next:=p^.next;C．s^.priou:=p;s^.next:=p^.next;p^.next:=s;p^.next^.priou:=s;D．s^.priou:=p;s^.next:=p^.next;p^.next^.priou:=s;p^.next:=s;20．在雙向循環(huán)鏈表中,在p指針所指向的結點前插入一個指針q所指向的新結點,其修改指針的操作是()。注:雙向鏈表的結點結構為(llink,data,rlink)。供選擇的答案：A．p↑.llink：=q；q↑.rlink：=p；p↑.llink↑.rlink：=q；q↑.llink：=q；B．p↑.llink：=q；p↑.llink↑.rlink：=q；q↑.rlink：=p；q↑.llink:=p↑.llink；C．q↑.rlink：=p；q↑.llink：=p↑.llink；p↑.llink↑.rlink：=q;p↑.llink：=q;D．q↑.llink:=p↑.llink；q↑.rlink:=p；p↑.llink：=q；p↑.llink：=q；（編者按：原題如此）21．在非空雙向循環(huán)鏈表中q所指的結點前插入一個由p所指的鏈結點的過程依次為:rlink(p)←q;llink(p)←llink(q);llink(q)←p;（）A．rlink(q)←pB．rlink(llink(q))←pC．rlink(llink(p))←pD．rlink(rlink(p))←p22．雙向鏈表中有兩個指針域，llink和rlink，分別指回前驅(qū)及后繼，設p指向鏈表中的一個結點，q指向一待插入結點，現(xiàn)要求在p前插入q，則正確的插入為（）【南京理工大學1996一、1（2分）】A.p＾.llink:=q;q＾.rlink:=p;p＾.llink＾.rlink:=q;q^.llink:=p^.llink;B.q＾.llink:=p^.llink;p＾.llink^.rlink:=q;q＾.rlink:=p;p^.llink:=q^.rlink;C.q^.rlink:=p;p^.rlink:=q;p^.llink^.rlink:=q;q^.rlink:=p;D.p^.llink^.rlink:=q;q^.rlink:=p;q^.llink:=p^.llink;p^.llink:=q;23．在雙向鏈表指針p的結點前插入一個指針q的結點操作是（）?！厩鄭u大學2000五、2（2分）】A.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；B.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;24．在單鏈表指針為p的結點之后插入指針為s的結點，正確的操作是：（）。A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;25．對于一個頭指針為head的帶頭結點的單鏈表，判定該表為空表的條件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL26.在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（）。A．(p^.llink)^.rlink:=p^.rlink(p^.rlink)^.llink:=p^.llink;B．p^.llink:=(p^.llink)^.llink(p^.llink)^.rlink:=p;C．(p^.rlink)^.llink:=pp^.rlink:=(p^.rlink)^.rlinkD．p^.rlink:=(p^.llink)^.llinkp^.llink:=(p^.rlink)^.rlink;27.雙向鏈表中有兩個指針域，llink和rlink分別指向前趨及后繼，設p指向鏈表中的一個結點，現(xiàn)要求刪去p所指結點，則正確的刪除是（）（鏈中結點數(shù)大于2，p不是第一個結點）A．p^.llink^.rlink:=p^.llink;p^.llink^.rlink:=p^.rlink;dispose(p);B．dispose(p);p^.llink^.rlink:=p^.llink;p^.llink^,rlink:=p^.rlink;C．p^.llink^.rlink:=p^.llink;dispose(p);p^.llink^.rlink:=p^.rlink;D．以上A，B，C都不對?！灸暇├砉ご髮W1997一、1（2分）】二、判斷1.鏈表中的頭結點僅起到標識的作用。()【南京航空航天大學1997一、1（1分）】2.順序存儲結構的主要缺點是不利于插入或刪除操作。()【南京航空航天大學1997一、2（1分）】3．線性表采用鏈表存儲時，結點和結點內(nèi)部的存儲空間可以是不連續(xù)的。()4．順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。()5.對任何數(shù)據(jù)結構鏈式存儲結構一定優(yōu)于順序存儲結構。()【南京航空航天大學1997一、3（1分）】6．順序存儲方式只能用于存儲線性結構。()7．集合與線性表的區(qū)別在于是否按關鍵字排序。()【大連海事大學2001一、5(1分)】8.所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。()【合肥工業(yè)大學2000二、1（1分）】9.線性表的特點是每個元素都有一個前驅(qū)和一個后繼。()【合肥工業(yè)大學2001二、1（1分）】10.取線性表的第i個元素的時間同i的大小有關.()【南京理工大學1997二、9（2分）】11.循環(huán)鏈表不是線性表.()【南京理工大學1998二、1（2分）】12.線性表只能用順序存儲結構實現(xiàn)。()【青島大學2001四、2（1分）】13.線性表就是順序存儲的表。()【青島大學2002一、1（1分）】14．為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。()15.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()16.鏈表是采用鏈式存儲結構的線性表,進行插入、刪除操作時，在鏈表中比在順序存儲結構中效率高。()三、填空1．當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用_______存儲結構?！颈狈浇煌ù髮W2001二、4】2．線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是________。【北方交通大學2001二、9】3．設單鏈表的結點結構為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結點，指針py指向data為y的新結點,若將結點y插入結點x之后，則需要執(zhí)行以下語句:_______；______;【華中理工大學2000一、4．在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動________個元素。5．在單鏈表中設置頭結點的作用是________?！竟枮I工業(yè)大學2000二、1（1分）】6．對于一個具有n個結點的單鏈表，在已知的結點*p后插入一個新結點的時間復雜度為________,在給定值為x的結點后插入一個新結點的時間復雜度為________?！竟枮I工業(yè)大學2001一、1（2分）】7．根據(jù)線性表的鏈式存儲結構中每一個結點包含的指針個數(shù)，將線性鏈表分成________和_______；而又根據(jù)指針的連接方式，鏈表又可分成________和________?！疚靼搽娮涌萍即髮W1998二、4（3分）】8．在雙向循環(huán)鏈表中,向p所指的結點之后插入指針f所指的結點，其操作是_______、_______、_______、________。9.在雙向鏈表結構中，若要求在p指針所指的結點之前插入指針為s所指的結點，則需執(zhí)行下列語句：s^.next:=p；s^.prior:=________；p^.prior:=s；________:=s；10．鏈接存儲的特點是利用________來表示數(shù)據(jù)元素之間的邏輯關系。【中山大學1998一、1（1分）】11.順序存儲結構是通過________表示元素之間的關系的;鏈式存儲結構是通過________表示元素之間的關系的。12.對于雙向鏈表,在兩個結點之間插入一個新結點需修改的指針共______個，單鏈表為_______個。13.循環(huán)單鏈表的最大優(yōu)點是：________?！靖Ｖ荽髮W1998二、3(2分)】14.已知指針p指向單鏈表L中的某結點，則刪除其后繼結點的語句是：________15.帶頭結點的雙循環(huán)鏈表L中只有一個元素結點的條件是：________16.在單鏈表L中，指針p所指結點有后繼結點的條件是：__【合肥工業(yè)大學2001三、3（2分）】17.帶頭結點的雙循環(huán)鏈表L為空表的條件是：________。18.在單鏈表p結點之后插入s結點的操作是：_______?！厩鄭u大學2002三、2（2分）】30.以下程序的功能是實現(xiàn)帶附加頭結點的單鏈表數(shù)據(jù)結點逆序連接，請?zhí)羁胀晟浦?。voidreverse(pointerh)/*h為附加頭結點指針；類型pointer同算法設計第3題*/{pointerp,q;p=h->next;h->next=NULL;while((1)________){q=p;p=p->next;q->next=h->next;h->next=(2)________;}}【西南交通大學2000一、9】31.下面是用c語言編寫的對不帶頭結點的單鏈表進行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當?shù)恼Z句。voidreverse（linklist&L）{p=null；q=L；while（q！=null）{(1);q->next=p；p=q；(2)___;}(3)_____;}【北京理工大學2001九、1（6分）】34.一元稀疏多項式以循環(huán)單鏈表按降冪排列，結點有三個域，系數(shù)域coef，指數(shù)域exp和指針域next；現(xiàn)對鏈表求一階導數(shù)，鏈表的頭指針為ha，頭結點的exp域為–1。derivative(ha){q=ha;pa=ha->next;while((1)_______){if((2)____){((3)__);free(pa);pa=((4)_);}else{pa->coef((5)___);pa->exp((6)___);q=((7)__);}pa=((8)________);}}【南京理工大學2000三、3（10分）】36．對單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，完成其功能。typedefstructnode{intdata;structnode*next;}linknode,*link;voidInsertsort(linkL){linkp,q,r,u;p=L->next;(1)______;while((2)________){r=L;q=L->next;while((3)________&&q->data<=p->data){r=q;q=q->next;}u=p->next;(4)______;(5)______;p=u;}}【北京科技大學2001二（10分）】37．下面是一個求兩個集合A和B之差C=A-B的程序，即當且僅當e是A的一個元素，但不是B中的一個元素時，e才是C中的一個元素。集合用有序鏈表實現(xiàn)，初始時，A，B集合中的元素按遞增排列，C為空；操作完成后A，B保持不變，C中元素按遞增排列。下面的函數(shù)append(last,e)是把值為e的新結點鏈接在由指針last指向的結點的后面，并返回新結點的地址；函數(shù)difference(A,B)實現(xiàn)集合運算A-B，并返回表示結果集合C的鏈表的首結點的地址。在執(zhí)行A-B運算之前，用于表示結果集合的鏈表首先增加一個附加的表頭結點，以便新結點的添加，當A-B運算執(zhí)行完畢，再刪除并釋放表示結果集合的鏈表的表頭結點。程序(a)（編者略去這個PASCAL程序）程序（b）typedefstructnode{intelement;structnode*link;}NODE;NODE*A，*B，*C;NODE*append(NODE*last,inte){last->link=(NODE*)malloc(sizeof(NODE));last->link->element=e;return(last->link);}NODE*difference(NODE*A,NODE*B){NODE*C,*last;C=last=(NODE*)malloc(sizeof(NODE));while(1)___if(A->element<B->element){last=append(last,A->element);A=A->link;}elseif(2)___{A=A->link;B=B->link;}ELSE(3)___;while(4)__{last=append(last,A->element);A=A->link;}(5)___;last=C;C=C->link;free(last);return(C);}/*callform:C=difference(A,B);*/【上海大學2000一、4（10分）】四應用題1．線性表有兩種存儲結構：一是順序表，二是鏈表。試問：（1）如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結構？為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應采用哪種存儲結構？為什么？【西安電子科技大學1999軟件二、1（5分）】2．線性表的順序存儲結構具有三個弱點：其一，在作插入或刪除操作時，需移動大量元素；其二，由于難以估計，必須預先分配較大的空間，往往使存儲空間不能得到充分利用；其三，表的容量難以擴充。線性表的鏈式存儲結構是否一定都能夠克服上述三個弱點，試討論之?！局貞c大學2000二、5】3．若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用何種存儲結構？為什么？4．線性結構包括______、______、_______和_______。線性表的存儲結構分成______和______。請用類PASCＡL語言描述這兩種結構?！救A北計算機系統(tǒng)工程研究所1999一、2（10分）】5．線性表（a1，a2，…，an）用順序映射表示時，ai和ai+1（1<=i<n〉的物理位置相鄰嗎？鏈接表示時呢？6.說明在線性表的鏈式存儲結構中，頭指針與頭結點之間的根本區(qū)別；頭結點與首元結點的關系。7.試述頭結點,首元結點,頭指針這三個概念的區(qū)別.9.在單鏈表和雙向鏈表中，能否從當前結點出發(fā)訪問到任何一個結點?10.如何通過改鏈的方法，把一個單向鏈表變成一個與原來鏈接方向相反的單向鏈表？12.設單鏈表結點指針域為next，試寫出刪除鏈表中指針p所指結點的直接后繼的C語言語句。13.設單鏈表中某指針p所指結點（即p結點）的數(shù)據(jù)域為data，鏈指針域為next，請寫出在p結點之前插入s結點的操作（PASCAL語句）?！颈本┛萍即髮W1999一、2（2分）】14.有線性表(a1,a2,…,an),采用單鏈表存儲，頭指針為H，每個結點中存放線性表中一個元素，現(xiàn)查找某個元素值等于X的結點。分別寫出下面三種情況的查找語句。要求時間盡量少。（1）線性表中元素無序。（2）線性表中元素按遞增有序。（3）線性表中元素按遞減有序。16．寫出下圖雙鏈表中對換值為23和15的兩個結點相互位置時修改指針的有關語句。結點結構為：(llink,data,rlink)【北京郵電大學1992三、4（25/4分）】17．按照下列題目中的算法功能說明，將算法描述片段中的錯誤改正過來。（1）（４分）下面的算法描述片段用于在雙鏈表中刪除指針變量p所指的結點：p^.rlink←p^.llink^.rlink;p^.llink←p.^rlink^.llinkdispose(p);（2）（６分）下面的算法描述片段用于在雙鏈表中指針變量p所指結點后插入一個新結點：new(q);q^.llink←p;p^.rlink←q;q^.rlink←p^.rlink;q←p^.rlink^.llink;【山東大學1999八（10分）】19．設雙向循環(huán)鏈表中結點的數(shù)據(jù)域、前驅(qū)和后繼指針域分別為data,pre和next,試寫出在指針p所指結點之前插入一s結點的C語言描述語句?！颈本┛萍即髮W2001一、3（2分）】20．本題給出一個子程序的框圖，如圖2，試填空完善此算法框圖。該子程序用來尋找第一個均出現(xiàn)在三個整數(shù)單向鏈表f1，f2，f3中的相同整數(shù)。假定在調(diào)用該子程序前，這三個整數(shù)鏈表已按從小到大的次序排序，單向鏈表的形式如下圖1的例子所示。注：在圖2的框圖中：found和exit均為布爾型的變量，可取值為true和false。val是整型變量，用來存放第一個均出現(xiàn)在f1，f2，f3中的相同整數(shù)。若f1，f2和f3中無相同的整數(shù)，found的值為false，否則found的值為true。f1↑.link表示訪問f1所指結點的link域。21.一線性表存儲在帶頭結點的雙向循環(huán)鏈表中，L為頭指針。如下算法：（1）說明該算法的功能。（2）在空缺處填寫相應的語句。voidunknown(BNODETP*L){…p=L->next;q=p->next;r=q->next；while(q!=L){while(p!=L)&&(p->data>q->data)p=p->prior；q->prior->next=r；(1)______；q->next=p->next；q->prior=p；(2)______；(3)______；q=r；p=q->prior；(4)______；}}【北京理工大學1999第二部分數(shù)據(jù)結構[7]（8分）】五、算法設計題假設有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結點存放歸并后的單鏈表。類似本題的另外敘述有：（1）設有兩個無頭結點的單鏈表,頭指針分別為ha,hb,鏈中有數(shù)據(jù)域data,鏈域next,兩鏈表的數(shù)據(jù)都按遞增序存放,現(xiàn)要求將hb表歸到ha表中,且歸并后ha仍遞增序,歸并中ha表中已有的數(shù)據(jù)若hb中也有,則hb中的數(shù)據(jù)不歸并到ha中,hb的鏈表在算法中不允許破壞。【南京理工大學1997四、3（15分）】PROCEDUREmerge(ha,hb);（2）已知頭指針分別為la和lb的帶頭結點的單鏈表中，結點按元素值非遞減有序排列。寫出將la和lb兩鏈表歸并成一個結點按元素值非遞減有序排列的單鏈表（其頭指針為lc），并計算算法的時間復雜度。2.圖（編者略）中帶頭結點且頭指針為ha和hb的兩線性表A和B分別表示兩個集合。兩表中的元素皆為遞增有序。請寫一算法求A和B的并集AUB。要求該并集中的元素仍保持遞增有序。且要利用A和B的原有結點空間。類似本題的另外敘述有：(1)已知遞增有序的兩個單鏈表A，B分別存儲了一個集合。設計算法實現(xiàn)求兩個集合的并集的運算A:=A∪B（2）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。編一函數(shù)，求A與B的交集，并存放于A鏈表中。（3）設有兩個從小到大排序的帶頭結點的有序鏈表。試編寫求這兩個鏈表交運算的算法（即L1∩L2）。要求結果鏈表仍是從小到大排序，但無重復元素?！灸暇┖娇蘸教齑髮W1996十一（10分）】（4）己知兩個線性表A，B均以帶頭結點的單鏈表作存儲結構，且表中元素按值遞增有序排列。設計算法求出A與B的交集C，要求C另開辟存儲空間，要求C同樣以元素值的遞增序的單鏈表形式存貯。（5）已知遞增有序的單鏈表A,B和C分別存儲了一個集合，設計算法實現(xiàn)A：=A∪（B∩C），并使求解結構A仍保持遞增。要求算法的時間復雜度為O(|A|+|B|+|C|)。其中,|A|為集合A的元素個數(shù)。3.知L1、L2分別為兩循環(huán)單鏈表的頭結點指針，m,n分別為L1、L2表中數(shù)據(jù)結點個數(shù)。要求設計一算法，用最快速度將兩表合并成一個帶頭結點的循環(huán)單鏈表?！緰|北大學1996二(12分)】類似本題的另外敘述有：（1）試用類Pascal語言編寫過程PROCjoin（VARla：link；lb：link） 實現(xiàn)連接線性表la和lb(lb在后)的算法，要求其時間復雜度為0（1），占用輔助空間盡量小。描述所用結構。（2）設有兩個鏈表，ha為單向鏈表，hb為單向循環(huán)鏈表。編寫算法，將兩個鏈表合并成一個單向鏈表，要求算法所需時間與鏈表長度無關?！灸暇┖娇蘸教齑髮W1997四（8分）】4.順序結構線性表LA與LB的結點關鍵字為整數(shù)。LA與LB的元素按非遞減有序，線性表空間足夠大。試用類PASCAL語言給出一種高效算法，將LB中元素合到LA中，使新的LA的元素仍保持非遞減有序。高效指最大限度的避免移動元素?！颈本┕I(yè)大學1997一、2(12分)】5.已知不帶頭結點的線性鏈表list，鏈表中結點構造為（data、link），其中data為數(shù)據(jù)域，link為指針域。請寫一算法，將該鏈表按結點數(shù)據(jù)域的值的大小從小到大重新鏈接。要求鏈接過程中不得使用除該鏈表以外的任何鏈結點空間?！颈本┖娇蘸教齑髮W1998五（15分）】6.設L為單鏈表的頭結點地址，其數(shù)據(jù)結點的數(shù)據(jù)都是正整數(shù)且無相同的，試設計利用直接插入的原則把該鏈表整理成數(shù)據(jù)遞增的有序單鏈表的算法?！緰|北大學1996六(14分)】類似本題的另外敘述有：（1）設一單向鏈表的頭指針為head,鏈表的記錄中包含著整數(shù)類型的key域,試設計算法,將此鏈表的記錄按照key遞增的次序進行就地排序.【中科院計算所1999五、1（10分）】7.設Listhead為一單鏈表的頭指針，單鏈表的每個結點由一個整數(shù)域DATA和指針域NEXT組成，整數(shù)在單鏈表中是無序的。編一PASCAL過程，將Listhead鏈中結點分成一個奇數(shù)鏈和一個偶數(shù)鏈，分別由P,Q指向，每個鏈中的數(shù)據(jù)按由小到大排列。程序中不得使用NEW過程申請空間。【山東大學1993六(15分)】類似本題的另外敘述有：（1）設計算法將一個帶頭結點的單鏈表A分解為兩個具有相同結構的鏈表B、C，其中B表的結點為A表中值小于零的結點，而C表的結點為A表中值大于零的結點（鏈表A的元素類型為整型，要求B、C表利用A表的結點）。(2)設L為一單鏈表的頭指針，單鏈表的每個結點由一個整數(shù)域data和指針域NEXT組成，整數(shù)在單鏈表中是無序的。設計算法，將鏈表中結點分成一個奇數(shù)鏈和一個偶數(shù)鏈，分別由P，Q指向，每個鏈中的數(shù)據(jù)按由小到大排列，算法中不得申請新的結點空間?！厩鄭u海洋大學1999三（12分）】(3)將一個帶頭結點的單鏈表A分解為兩個帶頭結點的單鏈表A和B，使得A表中含有原表中序號為奇數(shù)的元素，而B表中含有原表中序號為偶數(shù)的元素，且保持其相對順序不變。1)寫出其類型定義：2)寫出算法。8.已知線性表（a1a2a3…an）按順序存于內(nèi)存，每個元素都是整數(shù)，試設計用最少時間把所有值為負數(shù)的元素移到全部正數(shù)值元素前邊的算法：例：（x,-x,-x,x,x,-x…x）變?yōu)椋?x,-x,-x…類似本題的另外敘述有：（1）設有一元素為整數(shù)的線性表L=(a1,a2,a3,…,an),存放在一維數(shù)組A[N]中,設計一個算法,以表中an作為參考元素,將該表分為左、右兩部分,其中左半部分每個元素小于等于an,右半部分每個元素都大于an,an位于分界位置上(要求結果仍存放在A[N]中)。【北京理工大學1999八（6分）】（2）順序存儲的線性表A,其數(shù)據(jù)元素為整型,試編寫一算法,將A拆成B和C兩個表,使A中元素值大于等于0的元素放入B,小于0的放入C中..要求:1）表B和C另外設置存儲空間;2）表B和C不另外設置,而利用A的空間.（3）知線性表（a1,a2,a3,…,an）按順序存儲，且每個元素都是整數(shù)均不相同，設計把所有奇數(shù)移到所有偶數(shù)前邊的算法。（要求時間最少，輔助空間最少）(4)編寫函數(shù)將一整數(shù)序列中所有負數(shù)移到所有正數(shù)之前，要求時間復雜度為O（n）(5)已知一個由n（設n=1000）個整數(shù)組成的線性表，試設計該線性表的一種存儲結構，并用標準pascal語言描述算法，實現(xiàn)將n個元素中所有大于等于19的整數(shù)放在所有小于19的整數(shù)之后。要求算法的時間復雜度為O(n),空間復雜度O(1)?！疚靼步煌ù髮W1996六（11分）】9.試編寫在帶頭結點的單鏈表中刪除（一個）最小值結點的（高效）算法。voiddelete（Linklist&L）10.已知非空線性鏈表由list指出，鏈結點的構造為（data,link）.請寫一算法，將鏈表中數(shù)據(jù)域值最小的那個鏈結點移到鏈表的最前面。要求：不得額外申請新的鏈結點?！颈本┖娇蘸教齑髮W2001四（10分）】11.已知p指向雙向循環(huán)鏈表中的一個結點，其結點結構為data、llink、rlink三個域，寫出算法change(p),交換p所指向的結點和它的前綴結點的順序?！臼锥冀?jīng)貿(mào)大學1997二、2（15分）】12.線性表(a1,a2,a3,…,an)中元素遞增有序且按順序存儲于計算機內(nèi)。要求設計一算法完成：（1）用最少時間在表中查找數(shù)值為x的元素。（2）若找到將其與后繼元素位置相交換。（3）若找不到將其插入表中并使表中元素仍遞增有序。【東北大學1996三(12分)】13.設單鏈表的表頭指針為h，結點結構由data和next兩個域構成，其中data域為字符型。寫出算法dc(h,n),判斷該鏈表的前n個字符是否中心對稱。例如xyx,xyyx都是中心對稱?！臼锥冀?jīng)貿(mào)大學1998三、9（15分）】14.已知兩個單鏈表A和B,其頭指針分別為heada和headb，編寫一個過程從單鏈表A中刪除自第i個元素起的共len個元素，然后將單鏈表A插入到單鏈表B的第j個元素之前。類似本題的另外敘述有：（1）h1、h2為兩個鏈表的表頭指針，結點結構為data和link兩個域組成。寫出算法inde(h1,h2,i,j,l),將鏈表h1從第i個結點起的l個結點刪除，并插入到h2表的第j個結點之前。15.設線性表存于A[1..size]的前num各分量中，且遞增有序。請設計一個算法，將x插入到線性表的適當位置上，以保持線性表的有序性，并在設計前說明設計思想，最后說明所設計算法的時間復雜度。類似本題的另外敘述有：(1)試編制在線性表L={12,13,21,24,28,30,42,}中插入數(shù)據(jù)元素26的程序。（要求該程序用turboPascal語言編制并能在計算機上運行，結點類型為鏈式結構）【大連海事大學1996二、1(16分)】16.假設一個單循環(huán)鏈表，其結點含有三個域pre、data、link。其中data為數(shù)據(jù)域；pre為指針域，它的值為空指針（NIL）；link為指針域，它指向后繼結點。請設計算法，將此表改成雙向循環(huán)鏈表。17.已知遞增有序的單鏈表A,B分別存儲了一個集合，請設計算法以求出兩個集合A和B的差集A-B（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構成的集合），并以同樣的形式存儲，同時返回該集合的元素個數(shù)。18.已知一個單鏈表中每個結點存放一個整數(shù)，并且結點數(shù)不少于2，請設計算法以判斷該鏈表中第二項起的每個元素值是否等于其序號的平方減去其前驅(qū)的值，若滿足則返回ture，否則返回false.19．兩個整數(shù)序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已經(jīng)存入兩個單鏈表中，設計一個算法，判斷序列B是否是序列A的子序列?！緰|北大學1999二(10分)】20．L1與L2分別為兩單鏈表頭結點地址指針，且兩表中數(shù)據(jù)結點的數(shù)據(jù)域均為一個字母。設計把L1中與L2中數(shù)據(jù)相同的連續(xù)結點順序完全倒置的算法?！緰|北大學1997四(１５分)】類似本題的另外敘述有：(1)知L為鏈表的頭結點地址，表中共有m(m>3)個結點，從表中第i個結點(1<i<m)起到第m個結點構成一個循環(huán)部分鏈表，設計將這部分循環(huán)鏈表中所有結點順序完全倒置的算法。21.請寫一個算法將順序存儲結構的線性表（a1...an）逆置為(an...a1)。【大連海事大學1996八(６分)】類似本題的另外敘述有：(1)設有一帶頭結點的單鏈表,編程將鏈表顛倒過來.要求不用另外的數(shù)組或結點完成.(2)設有一個帶頭結點的單向鏈表，數(shù)據(jù)項遞減有序。寫一算法，重新排列鏈表，使數(shù)據(jù)項遞增有序，要求算法時間復雜度為O（n）。（注：用程序?qū)崿F(xiàn)）【南京航空航天大學1997七（12分）】(3)試編寫求倒排循環(huán)鏈表元素的算法?！灸暇┖娇蘸教齑髮W1995十二（10分）】(4)請設計算法將不帶頭結點的單鏈表就地逆置。【北方交通大學2001三（12分）】(5)試編寫算法，將不設表頭結點的、不循環(huán)的單向鏈表就地逆轉?！颈狈浇煌ù髮W1997五（10分）】(6)有一個單鏈表L（至少有1個結點），其頭結點指針為head，編寫一個過程將L逆置，即最后一個結點變成第一個結點，原來倒數(shù)第二個結點變成第二個結點，如此等等?！狙嗌酱髮W2001四、2（8分）】22．設有一個由正整數(shù)組成的無序（向后）單鏈表，編寫完成下列功能的算法：（1）找出最小值結點，且打印該數(shù)值；（2）若該數(shù)值是奇數(shù)，則將其與直接后繼結點的數(shù)值交換；（3）若該數(shù)值是偶數(shù)，則將其直接后繼結點刪除?！緰|北大學2000二(15分)】23．已知L為沒有頭結點的的單鏈表中第一個結點的指針，每個結點數(shù)據(jù)域存放一個字符，該字符可能是英文字母字符或數(shù)字字符或其它字符，編寫算法構造三個以帶頭結點的單循環(huán)鏈表表示的線性表，使每個表中只含同一類字符。（要求用最少的時間和最少的空間）【東北大學2002三(15分)】24．在一個遞增有序的線性表中，有數(shù)值相同的元素存在。若存儲方式為單鏈表，設計算法去掉數(shù)值相同的元素，使表中不再有重復的元素。例如：（7，10，10，21，30，42，42，42，51，70）將變作（7，10，21，30，42，51，70），分析算法的時間復雜度?！颈本┕I(yè)大學1996三(15分)】26．設有一個正整數(shù)序列組成的有序單鏈表（按遞增次序有序，且允許有相等的整數(shù)存在），試編寫能實現(xiàn)下列功能的算法：（要求用最少的時間和最小的空間）(1)確定在序列中比正整數(shù)x大的數(shù)有幾個（相同的數(shù)只計算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的數(shù)有5個）；(2)在單鏈表將比正整數(shù)x小的數(shù)按遞減次序排列；(3)將正整數(shù)（比）x大的偶數(shù)從單鏈表中刪除。【東北大學2001二(17分)】27.編寫一個算法來交換單鏈表中指針P所指結點與其后繼結點，HEAD是該鏈表的頭指針，P指向該鏈表中某一結點。類似本題的另外敘述有：(1)已知非空線性鏈表第一個結點由List指出，請寫一算法，交換p所指的結點與其下一個結點在鏈表中的位置(設p指向的不是鏈表最后那個結點)。【北京航空航天大學1999五（10分）】(2)已知任意單鏈表如圖所示(編者略去圖)。Head為表頭指針，指向表的第一個元素，p為指向表中任意結點的指針，試設計一個算法，將p指向的結點和其后面結點交換位置（可采用任何高級語言描述算法）。28．設鍵盤輸入n個英語單詞，輸入格式為n,w1,w2,…,wn,其中n表示隨后輸入英語單詞個數(shù)，試編一程序，建立一個單向鏈表，實現(xiàn)：（10分）（1）如果單詞重復出現(xiàn)，則只在鏈表上保留一個。（單考生做）。（2）除滿足（1）的要求外。鏈表結點還應有一個計數(shù)域，記錄該單詞重復出現(xiàn)的次數(shù)，然后輸出出現(xiàn)次數(shù)最多的前k(k<=n)個單詞（統(tǒng)考生做）。【南京航空航天大學1998九（10分）】29．已知一雙向循還鏈表，從第二個結點至表尾遞增有序，（設a1<x<an）如下圖(“第二個結點至表尾”指a1..an，因篇幅所限，編者略去圖)。試編寫程序，將第一個結點刪除并插入表中適當位置，使整個鏈表遞增有序。30.已知長度為n的線性表A采用順序存儲結構，請寫一時間復雜度為0(n)、空間復雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。（O（1）表示算法的輔助空間為常量）。31．設民航公司有一個自動預訂飛機票的系統(tǒng)，該系統(tǒng)中有一張用雙重鏈表示的乘客表，表中結點按乘客姓氏的字母序相鏈。例如，下面是張某個時刻的乘客表。試為該系統(tǒng)寫出一個當任一乘客要訂票時修改乘客表的算法。序號dataLlinkRlink1Liu652Chan493Wang574Bao025Mai136Dong817Xi308Deng969Cuang2832．設有一頭指針為L的帶有表頭結點的非循環(huán)雙向鏈表，其每個結點中除有pred（前驅(qū)指針），data（數(shù)據(jù)）和next（后繼指針）域外，還有一個訪問頻度域freq。在鏈表被起用前，其值均初始化為零。每當在鏈表中進行一次Locate(L,x)運算時，令元素值為x的結點中freq域的值增1，并使此鏈表中結點保持按訪問頻度非增（遞減）的順序排列，同時最近訪問的結點排在頻度相同的結點的最后，以便使頻繁訪問的結點總是靠近表頭。試編寫符合上述要求的Locate(L,x)運算的算法，該運算為函數(shù)過程，返回找到結點的地址，類型為指針型。【清華大學1997二（10分）】33．給定(已生成)一個帶表頭結點的單鏈表，設head為頭指針，結點的結構為(data,next),data為整型元素，next為指針，試寫出算法:按遞增次序輸出單鏈表中各結點的數(shù)據(jù)元素，并釋放結點所占的存儲空間。(要求;不允許使用數(shù)組作輔助空間)【華中理工大學2000八、2（13分）】34．已知三個帶頭結點的線性鏈表A、B和C中的結點均依元素值自小至大非遞減排列（可能存在兩個以上值相同的結點），編寫算法對A表進行如下操作：使操作后的鏈表A中僅留下三個表中均包含的數(shù)據(jù)元素的結點，且沒有值相同的結點，并釋放所有無用結點。限定算法的時間復雜度為O（m+n+p），其中m、n和p分別為三個表的長度。第3章棧和隊列一選擇題1.對于棧操作數(shù)據(jù)的原則是（）。A.先進先出B.后進先出C.后進后出D.不分順序2.在作進棧運算時,應先判別棧是否(①),在作退棧運算時應先判別棧是否(②)。當棧中元素為n個,作進棧運算時發(fā)生上溢,則說明該棧的最大容量為(③)。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時,應將兩棧的(④)分別設在這片內(nèi)存空間的兩端,這樣,當(⑤)時，才產(chǎn)生上溢。①,②:A.空B.滿C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2④:A.長度B.深度C.棧頂D.棧底⑤:A.兩個棧的棧頂同時到達?？臻g的中心點.B.其中一個棧的棧頂?shù)竭_棧空間的中心點.C.兩個棧的棧頂在?？臻g的某一位置相遇.D.兩個棧均不空,且一個棧的棧頂?shù)竭_另一個棧的棧底.3.一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（）。A.不確定B.n-i+1C.iD.n-i4.若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（）。A.i-j-1B.i-jC.j-i+1D.不確定的5.若已知一個棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是()。A.iB.n-iC.n-i+1D.不確定6.有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是合法的出棧序列？（）A.543612B.453126C.346521D.2341567.設棧的輸入序列是1，2，3，4,則（）不可能是其出棧序列。【中科院計算所2000一、10(2分)】A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，E.3，2，1，4，8.一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）。A.23415B.54132C.23145D.154329.設一個棧的輸入序列是1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（）。A.51234B.45132C.43125D.3215410.某堆棧的輸入序列為a,b，c，d,下面的四個序列中，不可能是它的輸出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b11.設abcdef以所給的次序進棧，若在進棧操作時，允許退棧操作,則下面得不到的序列為（）。A．fedcbaB.bcafedC.dcefbaD.cabdef12.設有三個元素X，Y，Z順序進棧（進的過程中允許出棧），下列得不到的出棧排列是()。A．XYZB.YZXC.ZXYD.ZYX13.輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為（）【中山大學1999一、8(1分)】A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop14.若一個棧以向量V[1..n]存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是()。A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-115.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個棧(i=1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]16.棧在（）中應用?！局猩酱髮W1998二、3（2分）】A.遞歸調(diào)用B.子程序調(diào)用C.表達式求值D.A，Ｂ，Ｃ17.一個遞歸算法必須包括（）?！疚錆h大學2000二、2】A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分18.執(zhí)行完下列語句段后，i值為：（）【浙江大學2000一、6(3分)】intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.無限遞歸19.表達式a*(b+c)-d的后綴表達式是()?！灸暇├砉ご髮W2001一、2（1.5分）】A．a(chǎn)bcd*+-B.abc+*d-C.abc*+d-D.-+*abcd20.表達式3*2^(4+2*2-6*3)-5求值過程中當掃描到6時，對象棧和算符棧為（），其中^為乘冪。A.3,2,4,1,1；(*^(+*-B.3,2,8；(*^-C.3,2,4,2,2；(*^(-D.3,2,8；(*^(-21.設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結構最佳。A．線性表