最完整的數(shù)據(jù)結(jié)構1800題含答案

第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)定性、平安性【南京理工大學1999一、1〔2分〕【武漢交通科技大學1996一、1〔4分〕】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ù)結(jié)構分為〔〕兩大類?！疚錆h交通科技大學1996一、4〔2分〕】A．動態(tài)結(jié)構、靜態(tài)結(jié)構B．順序結(jié)構、鏈式結(jié)構C．線性結(jié)構、非線性結(jié)構D．初等結(jié)構、構造型結(jié)構8．以下與數(shù)據(jù)的存儲結(jié)構無關的術語是〔〕?！颈狈浇煌ù髮W2000二、1〔2分〕】A．循環(huán)隊列B.鏈表C.哈希表D.棧9．以下數(shù)據(jù)結(jié)構中，哪一個是線性結(jié)構〔〕？【北方交通大學2001一、1〔2分〕】A．廣義表B.二叉樹C.稀疏矩陣D.串10．以下那一個術語與數(shù)據(jù)的存儲結(jié)構無關？〔〕【北方交通大學2001一、2〔2分〕】A．棧B.哈希表C.線索樹D.雙向鏈表11．在下面的程序段中，對x的賦值語句的頻度為〔〕【北京工商大學2001一、10〔3分〕】FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)12．程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFA[j]>A[j+1]THENA[j]與A[j+1]對換；其中n為正整數(shù)，那么最后一行的語句頻度在最壞情況下是〔〕A.O〔n〕B.O(nlogn)C.O(n3)D.O(n2)【南京理工大學1998一、1(2分)】13．以下哪個數(shù)據(jù)結(jié)構不是多型數(shù)據(jù)類型〔〕【中山大學1999一、3〔1分〕】A．棧B．廣義表C．有向圖D．字符串14．以下數(shù)據(jù)結(jié)構中，〔〕是非線性數(shù)據(jù)結(jié)構【中山大學1999一、4】A．樹B．字符串C．隊D．棧15.以下數(shù)據(jù)中，〔〕是非線性數(shù)據(jù)結(jié)構?！颈本├砉ご髮W2001六、1〔2分〕】A．棧B.隊列C.完全二叉樹D.堆16．連續(xù)存儲設計時，存儲單元的地址〔〕?！局猩酱髮W1999一、1〔1分〕】A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．局部連續(xù)，局部不連續(xù)17．以下屬于邏輯結(jié)構的是〔〕?！疚靼搽娮涌萍即髮W應用2001一、1】A．順序表B.哈希表C.有序表D.單鏈表二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()【北京郵電大學1998一、1〔2分〕】【青島大學2000一、1〔1分〕】【上海交通大學1998一、1】【山東師范大學2001一、1〔2分〕】2.記錄是數(shù)據(jù)處理的最小單位。()【上海海運學院1998一、5〔1分〕】3.數(shù)據(jù)的邏輯結(jié)構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系；()【北京郵電大學2002一、1〔1分〕】4．算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。()【大連海事大學2001一、10〔1分〕】5．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()【大連海事大學2001一、11〔1分〕】6．算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，那么算法實際上就是程序了。()【西安交通大學1996二、7〔3分〕】7．程序一定是算法。()【燕山大學1998二、2〔2分〕并改錯】8．數(shù)據(jù)的物理結(jié)構是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。()【山東師范大學2001一、2〔2分〕】9.數(shù)據(jù)結(jié)構的抽象操作的定義與具體實現(xiàn)有關。()【華南理工大學2002一、1〔1分〕】10.在順序存儲結(jié)構中，有時也存儲數(shù)據(jù)結(jié)構中元素之間的關系。()【華南理工大學2002一、2〔1分〕】11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()【上海海運學院1999一、1〔1分〕】12.數(shù)據(jù)結(jié)構的根本操作的設置的最重要的準那么是，實現(xiàn)應用程序與存儲結(jié)構的獨立。()【華南理工大學2002一、5〔1分〕】13.數(shù)據(jù)的邏輯結(jié)構說明數(shù)據(jù)元素之間的順序關系,它依賴于計算機的儲存結(jié)構.()【上海海運學院1998一、1〔1分〕】三、填空1．數(shù)據(jù)的物理結(jié)構包括的表示和的表示?！狙嗌酱髮W1998一、1〔2分〕】2.對于給定的n個元素,可以構造出的邏輯結(jié)構有〔1〕，〔2〕，〔3〕，__〔4〕_四種?！局锌圃河嬎闼?999二、1〔4分〕】3．數(shù)據(jù)的邏輯結(jié)構是指?！颈本┼]電大學2001二、1〔2分〕】4．一個數(shù)據(jù)結(jié)構在計算機中稱為存儲結(jié)構?！救A中理工大學2000一、1〔1分〕】5．抽象數(shù)據(jù)類型的定義僅取決于它的一組__〔1〕_，而與_〔2〕_無關，即不管其內(nèi)部結(jié)構如何變化，只要它的_〔3〕_不變，都不影響其外部使用?！旧綎|大學2001三、3〔2分〕】6．數(shù)據(jù)結(jié)構中評價算法的兩個重要指標是【北京理工大學2001七、1〔2分〕】7.數(shù)據(jù)結(jié)構是研討數(shù)據(jù)的_〔1〕_和_〔2〕_，以及它們之間的相互關系，并對與這種結(jié)構定義相應的_〔3〕_，設計出相應的〔4〕_。【西安電子科技大學1998二、2〔3分〕】8．一個算法具有5個特性:〔1〕、〔2〕、〔3〕，有零個或多個輸入、有一個或多個輸出。【華中理工大學2000一、2〔5分〕】【燕山大學1998一、2〔5分〕】9．如下程序段FORi:=nDOWNTO1DO{語句1}BEGINx:=x+1；{語句2}FORj:=nDOWNTOiDO{語句3}y:=y+1;{語句4}END；語句1執(zhí)行的頻度為〔1〕；語句2執(zhí)行的頻度為〔2〕；語句3執(zhí)行的頻度為〔3〕；語句4執(zhí)行的頻度為〔4〕?！颈狈浇煌ù髮W1999二、4〔5分〕】10．在下面的程序段中，對ｘ的賦值語句的頻度為______〔表示為n的函數(shù)〕FORi：＝１TOnDOFORj：＝１TOiDOFORk：＝1TOjDOｘ：＝ｘ＋delta；【北京工業(yè)大學1999一、6〔2分〕】11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：【合肥工業(yè)大學1999三、1〔2分〕】i：=1；WHILEi<nDOi：=i*2;12.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是()?！竞戏使I(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ù)結(jié)構是一門研究什么內(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ù)結(jié)構課程中，數(shù)據(jù)的邏輯結(jié)構，數(shù)據(jù)的存儲結(jié)構及數(shù)據(jù)的運算之間存在著怎樣的關系？〔2〕假設邏輯結(jié)構相同但存儲結(jié)構不同，那么為不同的數(shù)據(jù)結(jié)構。這樣的說法對嗎？舉例說明之。〔3〕在給定的邏輯結(jié)構及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)結(jié)構。這樣說法對嗎？舉例說明之?！?〕評價各種不同數(shù)據(jù)結(jié)構的標準是什么？5．評價一個好的算法，您是從哪幾方面來考慮的？【大連海事大學1996二、3〔2分〕】【中山大學1998三、1〔5分〕】6．解釋和比擬以下各組概念【華南師范大學2000一〔10分〕】〔1〕抽象數(shù)據(jù)類型及數(shù)據(jù)類型〔2〕數(shù)據(jù)結(jié)構、邏輯結(jié)構、存儲結(jié)構〔3〕抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學2000一、1〔3分〕】〔4〕算法的時間復雜性【河海大學1998一、2〔3分〕】〔5〕算法【吉林工業(yè)大學1999一、1〔2分〕】〔6〕頻度【吉林工業(yè)大學1999一、2〔2分〕】7.根據(jù)數(shù)據(jù)元素之間的邏輯關系，一般有哪幾類根本的數(shù)據(jù)結(jié)構？【北京科技大學1998一、1】【同濟大學1998】8．對于一個數(shù)據(jù)結(jié)構，一般包括哪三個方面的討論？【北京科技大學1999一、1〔2分〕】9.當你為解決某一問題而選擇數(shù)據(jù)結(jié)構時，應從哪些方面考慮？【西安電子北京科技大學2000】10.假設將數(shù)據(jù)結(jié)構定義為一個二元組〔D，R〕,說明符號D，R應分別表示什么？【北京科技大學2001一、1〔2分〕】11．數(shù)據(jù)結(jié)構與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學2001三、1〔3分〕】12．數(shù)據(jù)的存儲結(jié)構由哪四種根本的存儲方法實現(xiàn)？【山東科技大學2001一、1〔4分〕】13．假設有100個學生，每個學生有學號，姓名，平均成績，采用什么樣的數(shù)據(jù)結(jié)構最方便，寫出這些結(jié)構？【山東師范大學1996二、2〔2分〕】14.運算是數(shù)據(jù)結(jié)構的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結(jié)構的邏輯結(jié)構和存儲方式完全相同，只是對于運算的定義不同。因而兩個結(jié)構具有顯著不同的特性，是兩個不同的結(jié)構?！颈本┐髮W1998一、1〔5分〕】15.在編制管理通訊錄的程序時,什么樣的數(shù)據(jù)結(jié)構適宜?為什么?【長沙鐵道學院1998四、3(6分)】16.試舉一例，說明對相同的邏輯結(jié)構,同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同?！颈本├砉ご髮W2000三、1〔4.5分〕】17.有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復雜度為Tl=O(2n)，A2的時間復雜度為T2=O(n2)，僅就時間復雜度而言，請具體分析這兩個算法哪一個好?！颈本┖娇蘸教齑髮W2000二〔10分〕】18．設計一數(shù)據(jù)結(jié)構，用來表示某一銀行儲戶的根本信息：賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)。【浙江大學1994一、3〔5分〕】19.寫出下面算法中帶標號語句的頻度。TYPEar=ARRAY[1..n]OFdatatype;PROCEDUREperm(a:ar;k,n:integer);VARx:datatype;i:integer;BEGIN〔1〕IFk=nTHENBEGIN〔2〕FORi:=1TOnDO〔3〕write(a[i]);writeln;ENDELSEBEGIN〔4〕FORi:=kTOnDO〔5〕a[i]:=a[i]+i*i;〔6〕perm(a,k+1,n);END;END;設k的初值等于1?！颈本┼]電大學1997二〔10分〕】20.分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。i:=0;s:=0;n:=100;REPEATi:=i+1;s:=s+10*i;UNTILNOT((i<n)AND(s<n));【北京郵電大學1998四、1〔5分〕】21．以下算法對一n位二進制數(shù)加1，假設無溢出，該算法的最壞時間復雜性是什么？并分析它的平均時間復雜性。TYPEnum=ARRAY[1..n]of[0..1]；PROCEDUREInc〔VARa：num〕；VARi：integer；BEGINi：=n；WHILEA[i]=1DOBEGINA[i]：=0；i：=i-1；END；END；A[i]：=1；ENDInc；【東南大學1998三(8分)1994二〔15分〕】22.閱讀以下算法，指出算法A的功能和時間復雜性PROCEDUREA(h,g:pointer);(h,g分別為單循環(huán)鏈表〔singlelinkedcircularlist〕中兩個結(jié)點指針)PROCEDUREB(s,q:pointer)；VARp:pointer;BEGINp:=s;WHILEp^.next<>qDOp:=p^.next;p^.next:=s;END;(ofB)BEGINB(h,g);B(g,h);END;〔ofA〕【東南大學1999二〔10分〕】23.調(diào)用以下C函數(shù)f(n)或PASACAL函數(shù)f(n)答復以下問題:〔1〕試指出f(n)值的大小，并寫出f(n)值的推導過程;〔2〕假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結(jié)果。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分〕】24．設n是偶數(shù)，試計算運行以下程序段后m的值并給出該程序段的時間復雜度。m:=0;FORi:=1TOnDOFORj:=2*iTOnDOm:=m+1;【南京郵電大學2000一、1】25．有以下運行時間函數(shù)：〔1〕T1(n)=1000;〔2〕T2(n)=n2+1000n;〔3〕T3(n)=3n3+100n2+n+1;分別寫出相應的大O表示的運算時間?！炯止I(yè)大學1999二〔12分〕】26.試給出下面兩個算法的運算時間。〔1〕fori←1tondox←x+1END〔2〕fori←1tondoforj←1tondox←x+1endend【中科院自動化研究所1995二、2〔6分〕】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ù)的時間復雜度錄多少?【清華大學2000二〔12分〕】28．將以下函數(shù)，按它們在n→∝時的無窮大階數(shù)，從小到大排序。n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,,n!,n2+logn【中科院計算所1995】緒論答案一、選擇題1.B2.C3.1C3.2B4.B5.D6.C7.C8.D9.D10.A11.C12.D13.D14.A15.C16.A17.C二、判斷題1.×2.×3.×4.×5.√6.×7.×8.√9.×10.×11.×12.√13.×三．填空題1．數(shù)據(jù)元素數(shù)據(jù)元素間關系2．集合線性結(jié)構樹形結(jié)構圖狀結(jié)構或網(wǎng)狀結(jié)構。3．數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關系的總體。而邏輯關系是指數(shù)據(jù)元素之間的關聯(lián)方式或稱“鄰接關系”。4．表示〔又稱映像〕。5．〔1〕邏輯特性〔2〕在計算機內(nèi)部如何表示和實現(xiàn)〔3〕數(shù)學特性。6．算法的時間復雜度和空間復雜度。7．〔1〕邏輯結(jié)構〔2〕物理結(jié)構〔3〕操作〔運算〕〔4〕算法。8．〔1〕有窮性〔2〕確定性〔3〕可行性。9．〔1〕n+1〔2〕n〔3〕n(n+3)/2〔4〕n(n+1)/2。10．1+〔1+2++〔1+2+3〕+…+〔1+2+…+n〕=n(n+1)(n+2)/6O(n3)11.log2n12.nlog2n13.log2n214.(n+3)(n-2)/215.O(n)①(1)1(2)1(3)f(m,n-1)(4)n②917.n(n-1)/2四．應用題1．數(shù)據(jù)結(jié)構是一門研究在非數(shù)值計算的程序設計問題中，計算機的操作對象及對象間的關系和施加于對象的操作等的學科。2．四種表示方法〔1〕順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關系。存儲密度大，但有些操作〔如插入、刪除〕效率較差。〔2〕鏈式存儲方式。每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組〔至少一個〕指針。指針反映數(shù)據(jù)元素間的邏輯關系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作〔如插入、刪除等〕，但存儲空間開銷大〔用于指針〕，另外不能折半查找等?！?〕索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表，索引表中索引指示存儲結(jié)點的存儲位置〔下標〕或存儲區(qū)間端點〔下標〕，兼有靜態(tài)和動態(tài)特性?！?〕散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關鍵字隨機存取，不能順序存取，也不能折半存取。3．數(shù)據(jù)類型是程序設計語言中的一個概念，它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍〔對具體機器都應有整數(shù)范圍〕，其操作有加、減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供應用戶的已實現(xiàn)了的數(shù)據(jù)結(jié)構?！俺橄髷?shù)據(jù)類型〔ADT〕”指一個數(shù)學模型及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關。無論其內(nèi)部結(jié)構如何變化，只要它的數(shù)學特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機器已定義和實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設計軟件系統(tǒng)時自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實現(xiàn)三局部，封裝在一起，對用戶透明〔提供接口〕，而不必了解實現(xiàn)細節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設計不再是“藝術”，而是向“科學”邁進了一步。4．〔1〕數(shù)據(jù)的邏輯結(jié)構反映數(shù)據(jù)元素之間的邏輯關系〔即數(shù)據(jù)元素之間的關聯(lián)方式或“鄰接關系”〕，數(shù)據(jù)的存儲結(jié)構是數(shù)據(jù)結(jié)構在計算機中的表示，包括數(shù)據(jù)元素的表示及其關系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在邏輯結(jié)構上的，和存儲結(jié)構無關，而運算的實現(xiàn)那么是依賴于存儲結(jié)構?！?〕邏輯結(jié)構相同但存儲不同，可以是不同的數(shù)據(jù)結(jié)構。例如，線性表的邏輯結(jié)構屬于線性結(jié)構，采用順序存儲結(jié)構為順序表，而采用鏈式存儲結(jié)構稱為線性鏈表。〔3〕棧和隊列的邏輯結(jié)構相同，其存儲表示也可相同〔順序存儲和鏈式存儲〕，但由于其運算集合不同而成為不同的數(shù)據(jù)結(jié)構?！?〕數(shù)據(jù)結(jié)構的評價非常復雜，可以考慮兩個方面，一是所選數(shù)據(jù)結(jié)構是否準確、完整的刻劃了問題的根本特征；二是是否容易實現(xiàn)〔如對數(shù)據(jù)分解是否恰當；邏輯結(jié)構的選擇是否適合于運算的功能，是否有利于運算的實現(xiàn)；根本運算的選擇是否恰當。〕5．評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時空效率〔運行〕。6．〔1〕見上面題3〔2〕見上面題4〔3〕見上面題3〔4〕算法的時間復雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?；騿栴}的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關的其它參數(shù)。有時考慮算法在最壞情況下的時間復雜度或平均時間復雜度?！?〕算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。〔6〕頻度。在分析算法時間復雜度時，有時需要估算根本操作的原操作，它是執(zhí)行次數(shù)最多的一個操作，該操作重復執(zhí)行的次數(shù)稱為頻度。7．集合、線性結(jié)構、樹形結(jié)構、圖形或網(wǎng)狀結(jié)構。8．邏輯結(jié)構、存儲結(jié)構、操作〔運算〕。9．通常考慮算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面：程序運行時所需輸入的數(shù)據(jù)總量，對源程序進行編譯所需時間，計算機執(zhí)行每條指令所需時間和程序中指令重復執(zhí)行的次數(shù)。10．D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關系的有限集合。11．“數(shù)據(jù)結(jié)構”這一術語有兩種含義，一是作為一門課程的名稱；二是作為一個科學的概念。作為科學概念，目前尚無公認定義，一般認為，討論數(shù)據(jù)結(jié)構要包括三個方面，一是數(shù)據(jù)的邏輯結(jié)構，二是數(shù)據(jù)的存儲結(jié)構，三是對數(shù)據(jù)進行的操作〔運算〕。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結(jié)構，后者是前者的一種簡化情況。12．見上面題2。13．將學號、姓名、平均成績看成一個記錄〔元素，含三個數(shù)據(jù)項〕，將100個這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲。typedefstruct{intnum;//學號charname[8];//姓名floatscore;/平均成績}node；nodestudent[100];14.見上面題4〔3〕。15．應從兩方面進行討論：如通訊錄較少變動〔如城市私人號碼〕，主要用于查詢，以順序存儲較方便，既能順序查找也可隨機查找；假設通訊錄經(jīng)常有增刪操作，用鏈式存儲結(jié)構較為適宜，將每個人的情況作為一個元素〔即一個結(jié)點存放一個人〕，設姓名作關鍵字，鏈表安排成有序表，這樣可提高查詢速度。16．線性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復雜度為O〔n〕；而在鏈式存儲方式下，插入和刪除時間復雜度都是O〔1〕。17．對算法A1和A2的時間復雜度T1和T2取對數(shù)，得nlog2和2logn。顯然，算法A2好于A1。18.structnode{intyear,month,day;};typedefstruct{intnum;//帳號charname[8];//姓名structnodedate;//開戶年月日inttag;//儲蓄類型，如：0-零存，1-一年定期……floatput;//存入累加數(shù)；floatinterest;//利息floattotal;//帳面總數(shù)}count； 19．(1)n(2)n+1(3)n(4)(n+4)(n-1)/2(5)(n+2)(n-1)/2(6)n-1這是一個遞歸調(diào)用，因k的初值為1，由語句〔6〕知，每次調(diào)用k增1，故第(1)語句執(zhí)行n次?！?〕是FOR循環(huán)語句，在滿足(1)的條件下執(zhí)行，該語句進入循環(huán)體(3)n次，加上最后一次判斷出界，故執(zhí)行了n+1次。(4)也是循環(huán)語句，當k=1時判斷n+1次〔進入循環(huán)體(5)n次〕，k=2時判斷n次，最后一次k=n-1時判斷3次，故執(zhí)行次數(shù)是〔n+1〕+n+…+3=(n+4)(n-1)/2次。語句(5)是(4)的循環(huán)體，每次比(4)少一次判斷，故執(zhí)行次數(shù)是n+(n-1)+…+2=(n+2)(n-1)/2次。注意分析時，不要把(2)分析成n次，更不是1次。20．4〔這時i=4，s=100〕REPEAT語句先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時退出循環(huán)。21．算法在最好情況下，即二進制數(shù)的最后一位為零時，只作一次判斷，未執(zhí)行循環(huán)體，賦值語句A[i]執(zhí)行了一次；最壞情況出現(xiàn)在二進制數(shù)各位均為1〔最高位為零，因題目假設無溢出〕，這時循環(huán)體執(zhí)行了n-1次，時間復雜度是O(n)，循環(huán)體平均執(zhí)行n/2次，時間復雜度仍是O(n)。22．該算法功能是將原單循環(huán)鏈表分解成兩個單循環(huán)鏈表：其一包括結(jié)點h到結(jié)點g的前驅(qū)結(jié)點；另一個包括結(jié)點g到結(jié)點h的前驅(qū)結(jié)點。時間復雜度是O(n)。23．第一層FOR循環(huán)判斷n+1次，往下執(zhí)行n次，第二層FOR執(zhí)行次數(shù)為(n+(n-1)+(n-2)+…+1)，第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下表：i=123…nj=nnnn…nj=n-1n-1n-1n-1……………j=333j=222j=11執(zhí)行次數(shù)為(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2-n(n2-1)/6。在n=5時，f(5)=55，執(zhí)行過程中，輸出結(jié)果為：sum=15,sum=29,sum=41,sum=50,sum=55〔每個sum=占一行,為節(jié)省篇幅，這里省去換行〕。24．O(n2),m的值等于賦值語句m:=m+1的運行次數(shù)，其計算式為25．(1)O(1)(2)O(n2)(3)O(n3)26．(1)O(n)(2)O(n2)27.〔1〕由斐波那契數(shù)列的定義可得：Fn=Fn-1+Fn-2=2Fn-2+Fn-3=3Fn-3+2Fn-4=5Fn-4+3Fn-5=8Fn-5+5Fn-6……=pF1+qF0設Fm的執(zhí)行次數(shù)為Bm(m=0、1、2、…、n-1)，由以上等式可知，F(xiàn)n-1被執(zhí)行一次，即Bn-1=1；Fn-2被執(zhí)行兩次，即Bn-2=2；直至F1被執(zhí)行p次、F0被執(zhí)行q次，即B1=p，B0=q。Bm的執(zhí)行次數(shù)為前兩等式第一因式系數(shù)之和，即Bm=Bm-1+Bm-2，再有Bn-1=1和Bn-2=2，這也是一個斐波那契數(shù)列?？梢越獾茫築m=[()n-m+2-()n-m+2](m=0,1,2,…,n-1)〔2〕時間復雜度為O(n)28．從小到大排列為：logn,n1/2+logn,n,nlogn,n2+logn，n3,n-n3+7n5,2n/2,(3/2)n,n!,第2章線性表一選擇題1．下述哪一條是順序存儲結(jié)構的優(yōu)點？〔〕【北方交通大學2001一、4〔2分〕】A．存儲密度大B．插入運算方便C．刪除運算方便D．可方便地用于各種邏輯結(jié)構的存儲表示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é)省時間。【哈爾濱工業(yè)大學2001二、1〔2分〕】A．順序表B．雙鏈表C．帶頭結(jié)點的雙循環(huán)鏈表D．單循環(huán)鏈表5．某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，那么采用〔〕存儲方式最節(jié)省運算時間?！灸祥_大學2000一、3】A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表6．設一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，那么選用()最節(jié)省時間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點的雙循環(huán)鏈表【合肥工業(yè)大學2000一、1〔2分〕】7．假設某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點。那么采用〔〕存儲方式最節(jié)省運算時間。【北京理工大學2000一、1〔2分〕】A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．帶頭結(jié)點的雙循環(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)【上海海運學院1995二、1〔5分〕】12.(1)靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關。(2)靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。(3)靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的選項是〔〕【南京理工大學2000一、3〔1.5分〕】A．〔1〕，〔2〕B．〔1〕C．〔1〕，〔2〕,(3)D.〔2〕13.假設長度為n的線性表采用順序存儲結(jié)構，在其第i個位置插入一個新元素的算法的時間復雜度為〔〕(1<=i<=n+1)?！颈本┖娇蘸教齑髮W1999一、1〔2分〕】A.O(0)B.O(1)C.O(n)D.O(n2)14.對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復雜度為〔〕。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)【青島大學2000五、1〔2分〕】15．線性表〔a1,a2,…,an〕以鏈接方式存儲時，訪問第i位置元素的時間復雜性為〔〕A．O〔i〕B．O〔1〕C．O〔n〕D．O〔i-1〕【中山大學1999一、2】16．非空的循環(huán)單鏈表head的尾結(jié)點p↑滿足〔〕?！疚錆h大學2000二、10】A．p↑.link=headB．p↑.link=NILC．p=NILD．p=head17．循環(huán)鏈表H的尾結(jié)點P的特點是〔〕。【中山大學1998二、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)鏈表結(jié)點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指針所指向的結(jié)點前插入一個指針q所指向的新結(jié)點,其修改指針的操作是()。【北京郵電大學1998二、2〔2分〕】注:雙向鏈表的結(jié)點結(jié)構為(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所指的結(jié)點前插入一個由p所指的鏈結(jié)點的過程依次為: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))←p【北京航空航天大學2000一、1〔2分〕】22．雙向鏈表中有兩個指針域，llink和rlink，分別指回前驅(qū)及后繼，設p指向鏈表中的一個結(jié)點，q指向一待插入結(jié)點，現(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的結(jié)點前插入一個指針q的結(jié)點操作是〔〕?！厩鄭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的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：〔〕。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;【青島大學2001五、3〔2分〕】25．對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是〔〕A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL【北京工商大學2001一、5〔3分〕】26.在雙向鏈表存儲結(jié)構中，刪除p所指的結(jié)點時須修改指針〔〕。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;【西安電子科技大學1998一、1〔2分〕】27.雙向鏈表中有兩個指針域，llink和rlink分別指向前趨及后繼，設p指向鏈表中的一個結(jié)點，現(xiàn)要求刪去p所指結(jié)點，那么正確的刪除是〔〕〔鏈中結(jié)點數(shù)大于2，p不是第一個結(jié)點〕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都不對。【南京理工大學1997一、1〔2分〕】二、判斷1.鏈表中的頭結(jié)點僅起到標識的作用。()【南京航空航天大學1997一、1〔1分〕】2.順序存儲結(jié)構的主要缺點是不利于插入或刪除操作。()【南京航空航天大學1997一、2〔1分〕】3．線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。()【北京郵電大學1998一、2〔2分〕】4．順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。()【北京郵電大學2002一、2〔1分〕】5.對任何數(shù)據(jù)結(jié)構鏈式存儲結(jié)構一定優(yōu)于順序存儲結(jié)構。()【南京航空航天大學1997一、3〔1分〕】6．順序存儲方式只能用于存儲線性結(jié)構。()【中科院軟件所1999六、1-2〔2分〕】【上海海運學院1997一、1〔1分〕】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.線性表只能用順序存儲結(jié)構實現(xiàn)。()【青島大學2001四、2〔1分〕】13.線性表就是順序存儲的表。()【青島大學2002一、1〔1分〕】14．為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。()【上海海運學院1995一、1〔1分〕】【上海海運學院1997一、2〔1分〕】15.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()【上海海運學院1996一、1〔1分〕】【上海海運學院1999一、1〔1分〕】16.鏈表是采用鏈式存儲結(jié)構的線性表,進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構中效率高。()【上海海運學院1998一、2〔1分〕】三、填空1．當線性表的元素總數(shù)根本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用_______存儲結(jié)構?！颈狈浇煌ù髮W2001二、4】2．線性表L=〔a1,a2,…,an〕用數(shù)組表示，假定刪除表中任一元素的概率相同，那么刪除一個元素平均需要移動元素的個數(shù)是________?！颈狈浇煌ù髮W2001二、9】3．設單鏈表的結(jié)點結(jié)構為(data,next)，next為指針域，指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點,假設將結(jié)點y插入結(jié)點x之后，那么需要執(zhí)行以下語句:_______；______;【華中理工大學2000一、4〔2分〕】4．在一個長度為n的順序表中第i個元素〔1<=i<=n〕之前插入一個元素時，需向后移動________個元素。【北京工商大學2001二、4〔4分〕】5．在單鏈表中設置頭結(jié)點的作用是________?！竟枮I工業(yè)大學2000二、1〔1分〕】6．對于一個具有n個結(jié)點的單鏈表，在的結(jié)點*p后插入一個新結(jié)點的時間復雜度為________,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復雜度為________?！竟枮I工業(yè)大學2001一、1〔2分〕】7．根據(jù)線性表的鏈式存儲結(jié)構中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成________和_______；而又根據(jù)指針的連接方式，鏈表又可分成________和________?！疚靼搽娮涌萍即髮W1998二、4〔3分〕】8．在雙向循環(huán)鏈表中,向p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是_______、_______、_______、________?！局袊V業(yè)大學2000一、1〔3分〕】9.在雙向鏈表結(jié)構中，假設要求在p指針所指的結(jié)點之前插入指針為s所指的結(jié)點，那么需執(zhí)行以下語句：s^.next:=p；s^.prior:=________；p^.prior:=s；________:=s；【福州大學1998二、7(2分)】10．鏈接存儲的特點是利用________來表示數(shù)據(jù)元素之間的邏輯關系?！局猩酱髮W1998一、1〔1分〕】11.順序存儲結(jié)構是通過________表示元素之間的關系的;鏈式存儲結(jié)構是通過________表示元素之間的關系的。【北京理工大學2001七、2〔2分〕】12.對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共______個，單鏈表為_______個。【南京理工大學2000二、2〔3分〕】13.循環(huán)單鏈表的最大優(yōu)點是：________?！靖Ｖ荽髮W1998二、3(2分)】14.指針p指向單鏈表L中的某結(jié)點，那么刪除其后繼結(jié)點的語句是：________【合肥工業(yè)大學1999三、2〔2分〕】15.帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是：________【合肥工業(yè)大學1999三、32000三、2〔2分〕】16.在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是：__【合肥工業(yè)大學2001三、3〔2分〕】17.帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是：________?！颈本├砉ご髮W2000二、1〔2分〕】【青島大學2002三、1〔2分〕】18.在單鏈表p結(jié)點之后插入s結(jié)點的操作是：_______?！厩鄭u大學2002三、2〔2分〕】19.請在以下算法的橫線上填入適當?shù)恼Z句。【清華大學1994五〔15分〕】FUNCTIONinclusion(ha,hb:linklisttp):boolean;{以ha和hb為頭指針的單鏈表分別表示有序表A和B，本算法判別表A是否包含在表B內(nèi)，假設是，那么返回“true”，否那么返回“false”}BEGINpa:=ha^.next;pb:=hb^.next;〔1〕;WHILE〔2〕DOIFpa^.data=pb^.dataTHEN〔3〕ELSE〔4〕;〔5〕END;20．完善算法：單鏈表結(jié)點類型為：TYPEptr=^node；node=RECORDdata：integer；next：ptrEND；過程create建立以head為頭指針的單鏈表。PROCEDUREcreate((1))；VARp,q：ptr；k：integer；BEGINnew〔head〕；q:=head；read〔k〕；WHILEk>0DOBEGIN(2);(3);(4);(5);read〔k〕END;q^.next：=NIL;END;【北京師范大學1999三】21.已給如下關于單鏈表的類型說明：TYPElist=^node;node=RECORDdata:integer;next:list;END;以下程序采用鏈表合并的方法，將兩個已排序的單鏈表合并成一個鏈表而不改變其排序性〔升序〕，這里兩鏈表的頭指針分別為p和q.PROCEDUREmergelink(VARp,q:list):VARh,r:list;BEGIN〔1〕______h^.next:=NIL;r:=h;WHILE((p<>NIL)AND(q<>NIL))DOIF(p^.data<=q^.data)THENBEGIN〔2〕___；r:=p;p:=p^.next；ENDELSEBEGIN〔3〕____；r:=q;q:=q^.next;END;IF(p=NIL)THENr^.next:=q;〔4〕__；p:=h^.next;dispose(h);END;【廈門大學2000三、2〔8分〕】22．假設鏈表p和鏈表q中的結(jié)點值都是整數(shù),且按結(jié)點值的遞增次序鏈接起來的帶表頭結(jié)點的環(huán)形鏈表。各鏈表的表頭結(jié)點的值為max,且鏈表中其他結(jié)點的值都小于max，在程序中取max為9999。在各個鏈表中，每個結(jié)點的值各不相同，但鏈表p和鏈表q可能有值相同的結(jié)點〔表頭結(jié)點除外〕。下面的程序?qū)㈡湵韖合并到鏈表p中，使得合并后的鏈表是按結(jié)點值遞增次序鏈接起來的帶表頭結(jié)點的環(huán)形鏈表，且鏈表中各個結(jié)點的值各不相同。請在劃線處填上適當內(nèi)容，每個框只填一個語句或一個表達式，鏈表的結(jié)點類型如下TYPEnodeptr=^nodetype；nodetype=RECORDdata：integer；link：nodeptr;END；CONSTmax=9999;PROCEDUREmerge(VARp:nodeptr;q:nodeptr);VARr,s:nodeptr;BEGINr:=p;WHILE(A)___DOBEGINWHILEr^.link^.data<q^.link^.dataDO(B)___;IFr^.link^.data>q^.link^.dataTHENBEGINs:=(C)_;(D)_:=s^.link;s^.link:=(E)_;(F)__:=s;(G)_;ENDELSEBEGIN(H)__;s:=q^.link;(I)__;dispose(s)ENDEND;dispose(q)END;【復旦大學1997五〔18分〕】23．PROCins__linklist(la:linkisttp;i:integer;b:elemtp);{la為指向帶頭結(jié)點的單鏈表的頭指針，本算法在表中第i個元素之前插入元素b}p:=(1);j:=(2);{指針初始化，j為計數(shù)器}WHILE(p<>NIL)AND((3))DO[p:=(4);j:=j+1；]{尋找第i-1個結(jié)點}IF(p=NIL)OR((5))THENerror(‘Nothisposition’)ELSE[new(s);s↑.data:=b;s↑.next:=p↑.next;p↑.next:=s;]ENDP;{ins-linklist}【燕山大學1998四、1〔15分〕】24.雙鏈表中結(jié)點的類型定義為：TYPEdpointer=^list;list=RECORDdata:integer;left,right:dpointer;END;如下過程將在雙鏈表第i個結(jié)點〔i>=0〕之后插入一個元素為x的結(jié)點，請在答案欄給出題目中______處應填入的語句或表達式，使之可以實現(xiàn)上述功能。PROCEDUREinsert(VARhead:dpointer;i,x:integer);VARs,p:dpointer;j:integer;BEGINnew(s);s^.data:=x;IF(i=0)THENBEGINs^.right:=head;(1)___head:=sEND{如果i=0,那么將s結(jié)點插入到表頭后返回}ELSEBEGINp:=head;(2)_______；{在雙鏈表中查找第i個結(jié)點,由p所指向}WHILE((p<>NIL)AND(j<i))DOBEGINj:=j+1;(3)_END;IFp<>NILTHENIF〔p^.right=NIL〕THENBEGINp^.right:=s;s^.right:=NIL;(4)__ENDELSEBEGINs^.right:=p^.right;(5)_;p^.right:=s;(6)ENDELSEwriteln(‘cannotfindnode!’)ENDEND;【廈門大學2002二〔12分〕】25．閱讀以下算法，填充空格，使其成為完整的算法。其功能是在一個非遞減的順序存儲線性表中，刪除所有值相等的多余元素。CONSTmaxlen=30TYPEsqlisttp=RECORDelem:ARRAY[1..maxlen]OFinteger;last:0..maxlenEND;PROCexam21(VARL:sqlisttp);j:=1;i:=2;WHILE(1)______DO[IFL.elem[i]<>L.elem[j]THEN[(2)_______;(3)______];i:=i+1](4)________;ENDP;【同濟大學2000二、1(10分)】26．在此題的程序中，函數(shù)過程Create_link_list(n)建立一個具有n個結(jié)點的環(huán)形鏈表;程序過程josephus(n,i,m)對由Create_link_list(n)所建立的具有n個結(jié)點的環(huán)形鏈表按一定的次序逐個輸出并刪除鏈表中的所有結(jié)點，參數(shù)n(n>0)指明環(huán)形鏈表的結(jié)點個數(shù)，參數(shù)i(1<=i<=n)指明起始結(jié)點，參數(shù)m(m>0)是步長，指明從起始結(jié)點或前次被刪除并輸出的結(jié)點之后的第m個結(jié)點作為本次被輸出并刪除的結(jié)點。例如，對于以下圖中具有6個結(jié)點的環(huán)形鏈表，在調(diào)用josephus(6,3,2)后，將輸出5,1,3,6,4,2請在橫線處填上適當內(nèi)容，每空只填一個語句。TYPEnodeptr=^nodetype;nodetype=RECORDdata:intrger;link:nodeptrEND;VARn,i,m:integer;FUNCTIONCreate_link_list(n:integer):nodeptr;VARhead,p,q:nodeptr;i:integer;BEGINhead:=NIL;IFn>0THENBEGINnew(head);p:=head;FORi:=1TOn-1DOBEGINp^.data:=i;new(q);(A)____;(B)____END；p^.data:=n;(C)___;END;Creat_link_list:=headEND;PROCEDUREjosephus(n,i,m:integer);VARp,q:nodeptr;j:integer;BEGINp:=Creat_link_list(n);WHILEi>1DOBEGINp:=p^.link;i:=i-1END;(D)___;WHILEj<nDOBEGINFORi:=1TOm-1DOp:=p^.link;(E)___;write(q^.data:8);(F)__;dispose(q);j:=j+1ENDEND;【復旦大學1997四〔12分〕】27．對于給定的線性鏈表head,下面的程序過程實現(xiàn)了按結(jié)點值非降次序輸出鏈表中的所有結(jié)點，在每次輸出一個結(jié)點時，就把剛輸出的結(jié)點從鏈表中刪去。請在劃線處填上適當?shù)膬?nèi)容，使之成為一個完整的程序過程，每個空框只填一個語句。TYPEnodeptr=^nodetype；nodetype=RECORDdata:integer；link:nodeptrEND;VARhead:nodeptr；PROCEDUREsort_output_delete(head:nodeptr);VARp,q,r,s:nodeptr;BEGINWHILEhead<>NILDOBEGINp:=NIL；q:=head；r:=q；s:=q^.link；WHILEs<>NILDOBEGINIFs^.data<q^.dataTHENBEGIN(1)__;(2)___END；r:=s；(3)___END；write(q^.data:5)；IFp=NILTHEN(4)___ELSE(5)____；dispose(q)；END；writelnEND；【復旦大學1996七〔20分〕1995一〔12分〕與此題相似】28．下面函數(shù)的功能是在一個按訪問頻度不增有序的，帶頭結(jié)點的雙向鏈環(huán)上檢索關鍵值為x的結(jié)點，對該結(jié)點訪問頻度計數(shù)，并維護該鏈環(huán)有序。假設未找到，那么插入該結(jié)點。所有結(jié)點的頻度域初值在建表時都為零。請將程序中四處空缺補寫完整。TYPElink=^nodenode=RECORDkey:char;freq:integer;pre,next:link;END;VARl:link;FUNCTIONloc(l:link;x:char):link;VARp,q:link;BEGINp:=l^.next;〔1〕_；WHILEp^.key<>xDOp:=p^.next;IFp=lTHEN[new(q);q^.key:=x;q^.freq:=0]ELSE{找到}[p^.freq:=p^.freq+1;q:=p;〔2〕______；WHILEq^.freq>p^.pre^.freqDOp:=p^.pre;IFp<>qTHEN[〔3〕______]]；IF〔4〕_THEN[q^.next:=p,q^.pre;=p^.pre;p^.pre^.next:=q;p^.pre:=q]return(q);END;【北京工業(yè)大學1999五(12分)】29．循環(huán)鏈表a和b的結(jié)點值為字母，其中a表非遞減有序，下面的程序欲構造一個遞增有序的循環(huán)鏈表c，其中結(jié)點的值為同時在a，b兩鏈表中出現(xiàn)的字母，且c中字母不重復，請補上程序中空缺的局部，并估計算法的時間復雜度?！苍Oa，b的結(jié)點數(shù)分別為m，n〕TYPElink=^node;node=RECORDkey:char;next:linkEND;PROCjj(a,b:link;VARc:link);VARp,q,r,s:link;BEGINnew(c);c^.next:=c;q:=a;p:=a^.next;WHILEp<>aDO[〔1〕___；WHILEp^.key=p^.next^.keyDO[q:=p;p=p^.next];｛跳過相同字母｝r:=b^.next;〔2〕_____;WHILEr^.key<>p^.keyDOr:=r^.next;IFr<>bTHEN[s:=p;q^.next:=p^.next;〔3〕;s^.next:=c^.next;c^.next:=s;c:=s]ELSE[q:=p;p:=p^.next]];c:=c^.next；END;