數(shù)據(jù)結(jié)構(gòu)1800題(的答案全)

...wd......wd......wd...一、選擇題1.算法的計算量的大小稱為計算的〔B〕?！颈本┼]電大學(xué)2000二、3〔20/8分〕】A．效率B.復(fù)雜性C.現(xiàn)實性D.難度2.算法的時間復(fù)雜度取決于〔C〕【中科院計算所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)定性、安全性【南京理工大學(xué)1999一、1〔2分〕【武漢交通科技大學(xué)1996一、1〔4分〕】4．一個算法應(yīng)該是〔〕?！局猩酱髮W(xué)1998二、1〔2分〕】A．程序B．問題求解步驟的描述C．要滿足五個基本特性D．A和C.5.下面關(guān)于算法說法錯誤的選項是〔〕【南京理工大學(xué)2000一、1〔1.5分〕】A．算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是一樣的C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的6.下面說法錯誤的選項是〔〕【南京理工大學(xué)2000一、2〔1.5分〕】(1〕算法原地工作的含義是指不需要任何額外的輔助空間〔2〕在一樣的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法〔3〕所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界〔4〕同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)7．從邏輯上可以把數(shù)據(jù)構(gòu)造分為〔〕兩大類。【武漢交通科技大學(xué)1996一、4〔2分〕】A．動態(tài)構(gòu)造、靜態(tài)構(gòu)造B．順序構(gòu)造、鏈?zhǔn)綐?gòu)造C．線性構(gòu)造、非線性構(gòu)造D．初等構(gòu)造、構(gòu)造型構(gòu)造8．以下與數(shù)據(jù)的存儲構(gòu)造無關(guān)的術(shù)語是〔〕。【北方交通大學(xué)2000二、1〔2分〕】A．循環(huán)隊列B.鏈表C.哈希表D.棧9．以下數(shù)據(jù)構(gòu)造中，哪一個是線性構(gòu)造〔〕【北方交通大學(xué)2001一、1〔2分〕】A．廣義表B.二叉樹C.稀疏矩陣D.串10．以下那一個術(shù)語與數(shù)據(jù)的存儲構(gòu)造無關(guān)〔〕【北方交通大學(xué)2001一、2〔2分〕】A．棧B.哈希表C.線索樹D.雙向鏈表11．在下面的程序段中，對x的賦值語句的頻度為〔〕【北京工商大學(xué)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)【南京理工大學(xué)1998一、1(2分)】13．以下哪個數(shù)據(jù)構(gòu)造不是多型數(shù)據(jù)類型〔〕【中山大學(xué)1999一、3〔1分〕】A．棧B．廣義表C．有向圖D．字符串14．以下數(shù)據(jù)構(gòu)造中，〔〕是非線性數(shù)據(jù)構(gòu)造【中山大學(xué)1999一、4】A．樹B．字符串C．隊D．棧15.以下數(shù)據(jù)中，〔〕是非線性數(shù)據(jù)構(gòu)造?！颈本├砉ご髮W(xué)2001六、1〔2分〕】A．棧B.隊列C.完全二叉樹D.堆16．連續(xù)存儲設(shè)計時，存儲單元的地址〔〕?！局猩酱髮W(xué)1999一、1〔1分〕】A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．局部連續(xù)，局部不連續(xù)17．以下屬于邏輯構(gòu)造的是〔〕?！疚靼搽娮涌萍即髮W(xué)應(yīng)用2001一、1】A．順序表B.哈希表C.有序表D.單鏈表二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()【北京郵電大學(xué)1998一、1〔2分〕】【青島大學(xué)2000一、1〔1分〕】【上海交通大學(xué)1998一、1】【山東師范大學(xué)2001一、1〔2分〕】2.記錄是數(shù)據(jù)處理的最小單位。()【上海海運學(xué)院1998一、5〔1分〕】3.數(shù)據(jù)的邏輯構(gòu)造是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系；()【北京郵電大學(xué)2002一、1〔1分〕】4．算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。()【大連海事大學(xué)2001一、10〔1分〕】5．強健的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()【大連海事大學(xué)2001一、11〔1分〕】6．算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，那么算法實際上就是程序了。()【西安交通大學(xué)1996二、7〔3分〕】7．程序一定是算法。()【燕山大學(xué)1998二、2〔2分〕并改錯】8．?dāng)?shù)據(jù)的物理構(gòu)造是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。()【山東師范大學(xué)2001一、2〔2分〕】9.數(shù)據(jù)構(gòu)造的抽象操作的定義與具體實現(xiàn)有關(guān)。()【華南理工大學(xué)2002一、1〔1分〕】10.在順序存儲構(gòu)造中，有時也存儲數(shù)據(jù)構(gòu)造中元素之間的關(guān)系。()【華南理工大學(xué)2002一、2〔1分〕】11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()【上海海運學(xué)院1999一、1〔1分〕】12.數(shù)據(jù)構(gòu)造的基本操作的設(shè)置的最重要的準(zhǔn)那么是，實現(xiàn)應(yīng)用程序與存儲構(gòu)造的獨立。()【華南理工大學(xué)2002一、5〔1分〕】13.數(shù)據(jù)的邏輯構(gòu)造說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計算機的儲存構(gòu)造.()【上海海運學(xué)院1998一、1〔1分〕】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．?dāng)?shù)據(jù)的物理構(gòu)造包括的表示和的表示。【燕山大學(xué)1998一、1〔2分〕】2.對于給定的n個元素,可以構(gòu)造出的邏輯構(gòu)造有〔1〕，〔2〕，〔3〕，〔4〕四種。【中科院計算所1999二、1〔4分〕】3．?dāng)?shù)據(jù)的邏輯構(gòu)造是指。【北京郵電大學(xué)2001二、1〔2分〕】4．一個數(shù)據(jù)構(gòu)造在計算機中稱為存儲構(gòu)造?！救A中理工大學(xué)2000一、1〔1分〕】5．抽象數(shù)據(jù)類型的定義僅取決于它的一組__〔1〕_，而與_〔2〕_無關(guān)，即不管其內(nèi)部構(gòu)造如何變化，只要它的_〔3〕_不變，都不影響其外部使用?！旧綎|大學(xué)2001三、3〔2分〕】6．?dāng)?shù)據(jù)構(gòu)造中評價算法的兩個重要指標(biāo)是【北京理工大學(xué)2001七、1〔2分〕】7.數(shù)據(jù)構(gòu)造是研討數(shù)據(jù)的_〔1〕_和_〔2〕_，以及它們之間的相互關(guān)系，并對與這種構(gòu)造定義相應(yīng)的_〔3〕_，設(shè)計出相應(yīng)的〔4〕_。【西安電子科技大學(xué)1998二、2〔3分〕】8．一個算法具有5個特性:〔1〕、〔2〕、〔3〕，有零個或多個輸入、有一個或多個輸出?！救A中理工大學(xué)2000一、2〔5分〕】【燕山大學(xué)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〕。【北方交通大學(xué)1999二、4〔5分〕】10．在下面的程序段中，對ｘ的賦值語句的頻度為______〔表示為n的函數(shù)〕FORi：＝１TOnDOFORj：＝１TOiDOFORk：＝1TOjDOｘ：＝ｘ＋delta；【北京工業(yè)大學(xué)1999一、6〔2分〕】11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：【合肥工業(yè)大學(xué)1999三、1〔2分〕】i：=1；WHILEi<nDOi：=i*2;12.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是()?！竞戏使I(yè)大學(xué)2000三、1〔2分〕】i:=1;WHILEi<nBEGINFORj:=1TOnDOx:=x+1;i:=i*2END；13.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是()【合肥工業(yè)大學(xué)2001三、1〔2分〕】i：=n*nWHILEi<>1DOi:=idiv2;14.計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為_______?！灸暇├砉ご髮W(xué)2000二、1〔1.5分〕】FOR(i=l；i<n-l；i++)FOR(j=n;j>=i;j--)s;15.下面程序段的時間復(fù)雜度為________。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;【南京理工大學(xué)2001二、1〔2分〕】16．設(shè)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è)大學(xué)1999三、8〔2分〕】四、應(yīng)用題1.數(shù)據(jù)構(gòu)造是一門研究什么內(nèi)容的學(xué)科【燕山大學(xué)1999二、1〔4分〕】2.數(shù)據(jù)元素之間的關(guān)系在計算機中有幾種表示方法各有什么特點【燕山大學(xué)1999二、2〔4分〕】3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何一樣和不同之處，抽象數(shù)據(jù)類型的主要特點是什么使用抽象數(shù)據(jù)類型的主要好處是什么【北京郵電大學(xué)1994一〔8分〕】4.答復(fù)以下問題〔每題2分〕【山東工業(yè)大學(xué)1997一〔8分〕】〔1〕在數(shù)據(jù)構(gòu)造課程中，數(shù)據(jù)的邏輯構(gòu)造，數(shù)據(jù)的存儲構(gòu)造及數(shù)據(jù)的運算之間存在著怎樣的關(guān)系〔2〕假設(shè)邏輯構(gòu)造一樣但存儲構(gòu)造不同，那么為不同的數(shù)據(jù)構(gòu)造。這樣的說法對嗎舉例說明之。〔3〕在給定的邏輯構(gòu)造及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)構(gòu)造。這樣說法對嗎舉例說明之。〔4〕評價各種不同數(shù)據(jù)構(gòu)造的標(biāo)準(zhǔn)是什么5．評價一個好的算法，您是從哪幾方面來考慮的【大連海事大學(xué)1996二、3〔2分〕】【中山大學(xué)1998三、1〔5分〕】6．解釋和比較以下各組概念【華南師范大學(xué)2000一〔10分〕】〔1〕抽象數(shù)據(jù)類型及數(shù)據(jù)類型〔2〕數(shù)據(jù)構(gòu)造、邏輯構(gòu)造、存儲構(gòu)造〔3〕抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學(xué)2000一、1〔3分〕】〔4〕算法的時間復(fù)雜性【河海大學(xué)1998一、2〔3分〕】〔5〕算法【吉林工業(yè)大學(xué)1999一、1〔2分〕】〔6〕頻度【吉林工業(yè)大學(xué)1999一、2〔2分〕】7.根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)構(gòu)造【北京科技大學(xué)1998一、1】【同濟大學(xué)1998】8．對于一個數(shù)據(jù)構(gòu)造，一般包括哪三個方面的討論【北京科技大學(xué)1999一、1〔2分〕】9.當(dāng)你為解決某一問題而選擇數(shù)據(jù)構(gòu)造時，應(yīng)從哪些方面考慮【西安電子北京科技大學(xué)2000】10.假設(shè)將數(shù)據(jù)構(gòu)造定義為一個二元組〔D，R〕,說明符號D，R應(yīng)分別表示什么【北京科技大學(xué)2001一、1〔2分〕】11．?dāng)?shù)據(jù)構(gòu)造與數(shù)據(jù)類型有什么區(qū)別【哈爾濱工業(yè)大學(xué)2001三、1〔3分〕】12．?dāng)?shù)據(jù)的存儲構(gòu)造由哪四種基本的存儲方法實現(xiàn)【山東科技大學(xué)2001一、1〔4分〕】13．假設(shè)有100個學(xué)生，每個學(xué)生有學(xué)號，姓名，平均成績，采用什么樣的數(shù)據(jù)構(gòu)造最方便，寫出這些構(gòu)造【山東師范大學(xué)1996二、2〔2分〕】14.運算是數(shù)據(jù)構(gòu)造的一個重要方面。試舉一例，說明兩個數(shù)據(jù)構(gòu)造的邏輯構(gòu)造和存儲方式完全一樣，只是對于運算的定義不同。因而兩個構(gòu)造具有顯著不同的特性，是兩個不同的構(gòu)造?！颈本┐髮W(xué)1998一、1〔5分〕】15.在編制管理通訊錄的程序時,什么樣的數(shù)據(jù)構(gòu)造適宜?為什么?【長沙鐵道學(xué)院1998四、3(6分)】16.試舉一例，說明對一樣的邏輯構(gòu)造,同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同。【北京理工大學(xué)2000三、1〔4.5分〕】17.有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復(fù)雜度為Tl=O(2n)，A2的時間復(fù)雜度為T2=O(n2)，僅就時間復(fù)雜度而言，請具體分析這兩個算法哪一個好?！颈本┖娇蘸教齑髮W(xué)2000二〔10分〕】18．設(shè)計一數(shù)據(jù)構(gòu)造，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)。【浙江大學(xué)1994一、3〔5分〕】19.寫出下面算法中帶標(biāo)號語句的頻度。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;設(shè)k的初值等于1。【北京郵電大學(xué)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));【北京郵電大學(xué)1998四、1〔5分〕】21．以下算法對一n位二進制數(shù)加1，假設(shè)無溢出，該算法的最壞時間復(fù)雜性是什么并分析它的平均時間復(fù)雜性。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；【東南大學(xué)1998三(8分)1994二〔15分〕】22.閱讀以下算法，指出算法A的功能和時間復(fù)雜性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〕【東南大學(xué)1999二〔10分〕】23.調(diào)用以下C函數(shù)f(n)或PASACAL函數(shù)f(n)答復(fù)以下問題:〔1〕試指出f(n)值的大小，并寫出f(n)值的推導(dǎo)過程;〔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);}【華中理工大學(xué)2000六〔10分〕】24．設(shè)n是偶數(shù)，試計算運行以下程序段后m的值并給出該程序段的時間復(fù)雜度。m:=0;FORi:=1TOnDOFORj:=2*iTOnDOm:=m+1;【南京郵電大學(xué)2000一、1】25．有以下運行時間函數(shù)：〔1〕T1(n)=1000;〔2〕T2(n)=n2+1000n;〔3〕T3(n)=3n3+100n2+n+1;分別寫出相應(yīng)的大O表示的運算時間。【吉林工業(yè)大學(xué)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ù)列，答復(fù)以下問題。(1)(7分)在遞歸計算Fn的時候，需要對較小的Fn-1，F(xiàn)n-2，…,Fl,F0準(zhǔn)確計算多少次?(2)(5分)如果用大O表示法，試給出遞歸計算Fn時遞歸函數(shù)的時間復(fù)雜度錄多少?【清華大學(xué)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．?dāng)?shù)據(jù)元素數(shù)據(jù)元素間關(guān)系2．集合線性構(gòu)造樹形構(gòu)造圖狀構(gòu)造或網(wǎng)狀構(gòu)造。3．?dāng)?shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系〞。4．表示〔又稱映像〕。5．〔1〕邏輯特性〔2〕在計算機內(nèi)部如何表示和實現(xiàn)〔3〕數(shù)學(xué)特性。6．算法的時間復(fù)雜度和空間復(fù)雜度。7．〔1〕邏輯構(gòu)造〔2〕物理構(gòu)造〔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)16.①(1)1(2)1(3)f(m,n-1)(4)n②917.n(n-1)/2四．應(yīng)用題1．?dāng)?shù)據(jù)構(gòu)造是一門研究在非數(shù)值計算的程序設(shè)計問題中，計算機的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。2．四種表示方法〔1〕順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作〔如插入、刪除〕效率較差?！?〕鏈?zhǔn)酱鎯Ψ绞健Ｃ總€存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組〔至少一個〕指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作〔如插入、刪除等〕，但存儲空間開銷大〔用于指針〕，另外不能折半查找等?！?〕索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建設(shè)一個索引表，索引表中索引指示存儲結(jié)點的存儲位置〔下標(biāo)〕或存儲區(qū)間端點〔下標(biāo)〕，兼有靜態(tài)和動態(tài)特性。〔4〕散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關(guān)鍵字隨機存取，不能順序存取，也不能折半存取。3．?dāng)?shù)據(jù)類型是程序設(shè)計語言中的一個概念，它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍〔對具體機器都應(yīng)有整數(shù)范圍〕，其操作有加、減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供給用戶的已實現(xiàn)了的數(shù)據(jù)構(gòu)造?！俺橄髷?shù)據(jù)類型〔ADT〕〞指一個數(shù)學(xué)模型及定義在該模型上的一組操作?！俺橄蟥暤囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。無論其內(nèi)部構(gòu)造如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機器已定義和實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實現(xiàn)三局部，封裝在一起，對用戶透明〔提供接口〕，而不必了解實現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計不再是“藝術(shù)〞，而是向“科學(xué)〞邁進了一步。4．〔1〕數(shù)據(jù)的邏輯構(gòu)造反映數(shù)據(jù)元素之間的邏輯關(guān)系〔即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系〞〕，數(shù)據(jù)的存儲構(gòu)造是數(shù)據(jù)構(gòu)造在計算機中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在邏輯構(gòu)造上的，和存儲構(gòu)造無關(guān)，而運算的實現(xiàn)那么是依賴于存儲構(gòu)造?！?〕邏輯構(gòu)造一樣但存儲不同，可以是不同的數(shù)據(jù)構(gòu)造。例如，線性表的邏輯構(gòu)造屬于線性構(gòu)造，采用順序存儲構(gòu)造為順序表，而采用鏈?zhǔn)酱鎯?gòu)造稱為線性鏈表?！?〕棧和隊列的邏輯構(gòu)造一樣，其存儲表示也可一樣〔順序存儲和鏈?zhǔn)酱鎯Α?，但由于其運算集合不同而成為不同的數(shù)據(jù)構(gòu)造?！?〕數(shù)據(jù)構(gòu)造的評價非常復(fù)雜，可以考慮兩個方面，一是所選數(shù)據(jù)構(gòu)造是否準(zhǔn)確、完整的刻劃了問題的基本特征；二是是否容易實現(xiàn)〔如對數(shù)據(jù)分解是否恰當(dāng)；邏輯構(gòu)造的選擇是否適合于運算的功能，是否有利于運算的實現(xiàn)；基本運算的選擇是否恰當(dāng)。〕5．評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的強健性；四是算法的時空效率〔運行〕。6．〔1〕見上面題3〔2〕見上面題4〔3〕見上面題3〔4〕算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?；騿栴}的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其它參數(shù)。有時考慮算法在最壞情況下的時間復(fù)雜度或平均時間復(fù)雜度。〔5〕算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。〔6〕頻度。在分析算法時間復(fù)雜度時，有時需要估算基本操作的原操作，它是執(zhí)行次數(shù)最多的一個操作，該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。7．集合、線性構(gòu)造、樹形構(gòu)造、圖形或網(wǎng)狀構(gòu)造。8．邏輯構(gòu)造、存儲構(gòu)造、操作〔運算〕。9．通常考慮算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面：程序運行時所需輸入的數(shù)據(jù)總量，對源程序進展編譯所需時間，計算機執(zhí)行每條指令所需時間和程序中指令重復(fù)執(zhí)行的次數(shù)。10．D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關(guān)系的有限集合。11．“數(shù)據(jù)構(gòu)造〞這一術(shù)語有兩種含義，一是作為一門課程的名稱；二是作為一個科學(xué)的概念。作為科學(xué)概念，目前尚無公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)構(gòu)造要包括三個方面，一是數(shù)據(jù)的邏輯構(gòu)造，二是數(shù)據(jù)的存儲構(gòu)造，三是對數(shù)據(jù)進展的操作〔運算〕。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)構(gòu)造，后者是前者的一種簡化情況。12．見上面題2。13．將學(xué)號、姓名、平均成績看成一個記錄〔元素，含三個數(shù)據(jù)項〕，將100個這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲。typedefstruct{intnum;//學(xué)號charname[8];//姓名floatscore;/平均成績}node；nodestudent[100];14.見上面題4〔3〕。15．應(yīng)從兩方面進展討論：如通訊錄較少變動〔如城市私人號碼〕，主要用于查詢，以順序存儲較方便，既能順序查找也可隨機查找；假設(shè)通訊錄經(jīng)常有增刪操作，用鏈?zhǔn)酱鎯?gòu)造較為適宜，將每個人的情況作為一個元素〔即一個結(jié)點存放一個人〕，設(shè)姓名作關(guān)鍵字，鏈表安排成有序表，這樣可提高查詢速度。16．線性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復(fù)雜度為O〔n〕；而在鏈?zhǔn)酱鎯Ψ绞较?，插入和刪除時間復(fù)雜度都是O〔1〕。17．對算法A1和A2的時間復(fù)雜度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)語句，當(dāng)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〔最高位為零，因題目假設(shè)無溢出〕，這時循環(huán)體執(zhí)行了n-1次，時間復(fù)雜度是O(n)，循環(huán)體平均執(zhí)行n/2次，時間復(fù)雜度仍是O(n)。22．該算法功能是將原單循環(huán)鏈表分解成兩個單循環(huán)鏈表：其一包括結(jié)點h到結(jié)點g的前驅(qū)結(jié)點；另一個包括結(jié)點g到結(jié)點h的前驅(qū)結(jié)點。時間復(fù)雜度是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設(shè)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ù)列。可以解得：Bm=[()n-m+2-()n-m+2](m=0,1,2,…,n-1)〔2〕時間復(fù)雜度為O(n)28．從小到大排列為：logn,n1/2+logn,n,nlogn,n2+logn，n3,n-n3+7n5,2n/2,(3/2)n,n!,一選擇題1．下述哪一條是順序存儲構(gòu)造的優(yōu)點〔〕【北方交通大學(xué)2001一、4〔2分〕】A．存儲密度大B．插入運算方便C．刪除運算方便D．可方便地用于各種邏輯構(gòu)造的存儲表示2．下面關(guān)于線性表的表達(dá)中，錯誤的選項是哪一個〔〕【北方交通大學(xué)2001一、14〔2分〕】A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進展插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。3．線性表是具有n個〔〕的有限序列〔n>0〕?！厩迦A大學(xué)1998一、4〔2分〕】A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項E．信息項4．假設(shè)某線性表最常用的操作是存取任一指定序號的元素和在最后進展插入和刪除運算，那么利用〔〕存儲方式最節(jié)省時間?！竟枮I工業(yè)大學(xué)2001二、1〔2分〕】A．順序表B．雙鏈表C．帶頭結(jié)點的雙循環(huán)鏈表D．單循環(huán)鏈表5．某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，那么采用〔〕存儲方式最節(jié)省運算時間。【南開大學(xué)2000一、3】A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表6．設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，那么選用()最節(jié)省時間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點的雙循環(huán)鏈表【合肥工業(yè)大學(xué)2000一、1〔2分〕】7．假設(shè)某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點。那么采用〔〕存儲方式最節(jié)省運算時間?！颈本├砉ご髮W(xué)2000一、1〔2分〕】A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．帶頭結(jié)點的雙循環(huán)鏈表8.靜態(tài)鏈表中指針表示的是〔〕.【北京理工大學(xué)2001六、2〔2分〕】A．內(nèi)存地址B．?dāng)?shù)組下標(biāo)C．下一元素地址D．左、右孩子地址9.鏈表不具有的特點是〔〕【福州大學(xué)1998一、8(2分)】A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比10.下面的表達(dá)不正確的選項是〔〕【南京理工大學(xué)1996一、10〔2分〕】A．線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比B.線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)C.線性表在順序存儲時，查找第i個元素的時間同i的值成正比D.線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)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)【上海海運學(xué)院1995二、1〔5分〕】12.(1)靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關(guān)。(2)靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。(3)靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的選項是〔〕【南京理工大學(xué)2000一、3〔1.5分〕】A．〔1〕，〔2〕B．〔1〕C．〔1〕，〔2〕,(3)D.〔2〕13.假設(shè)長度為n的線性表采用順序存儲構(gòu)造，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為〔〕(1<=i<=n+1)。【北京航空航天大學(xué)1999一、1〔2分〕】A.O(0)B.O(1)C.O(n)D.O(n2)14.對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為〔〕。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)【青島大學(xué)2000五、1〔2分〕】15．線性表〔a1,a2,…,an〕以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為〔〕A．O〔i〕B．O〔1〕C．O〔n〕D．O〔i-1〕【中山大學(xué)1999一、2】16．非空的循環(huán)單鏈表head的尾結(jié)點p↑滿足〔〕?！疚錆h大學(xué)2000二、10】A．p↑.link=headB．p↑.link=NILC．p=NILD．p=head17．循環(huán)鏈表H的尾結(jié)點P的特點是〔〕?！局猩酱髮W(xué)1998二、2〔2分〕】A．P^.NEXT:=HB．P^.NEXT:=H^.NEXTC．P:=HD．P:=H^.NEXT18．在一個以h為頭的單循環(huán)鏈中，p指針指向鏈尾的條件是〔〕【南京理工大學(xué)1998一、15〔2分〕】A.p＾.next=hB.p＾.next=NILC.p＾.next.＾next=hD.p＾.data=-119．完成在雙循環(huán)鏈表結(jié)點p之后插入s的操作是〔〕；【北方交通大學(xué)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指針?biāo)赶虻慕Y(jié)點前插入一個指針q所指向的新結(jié)點,其修改指針的操作是()?！颈本┼]電大學(xué)1998二、2〔2分〕】注:雙向鏈表的結(jié)點構(gòu)造為(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【北京航空航天大學(xué)2000一、1〔2分〕】22．雙向鏈表中有兩個指針域，llink和rlink，分別指回前驅(qū)及后繼，設(shè)p指向鏈表中的一個結(jié)點，q指向一待插入結(jié)點，現(xiàn)要求在p前插入q，那么正確的插入為〔〕【南京理工大學(xué)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大學(xué)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;【青島大學(xué)2001五、3〔2分〕】25．對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是〔〕A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL【北京工商大學(xué)2001一、5〔3分〕】26.在雙向鏈表存儲構(gòu)造中，刪除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;【西安電子科技大學(xué)1998一、1〔2分〕】27.雙向鏈表中有兩個指針域，llink和rlink分別指向前趨及后繼，設(shè)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都不對?！灸暇├砉ご髮W(xué)1997一、1〔2分〕】二、判斷1.鏈表中的頭結(jié)點僅起到標(biāo)識的作用。()【南京航空航天大學(xué)1997一、1〔1分〕】2.順序存儲構(gòu)造的主要缺點是不利于插入或刪除操作。()【南京航空航天大學(xué)1997一、2〔1分〕】3．線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。()【北京郵電大學(xué)1998一、2〔2分〕】4．順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩?)【北京郵電大學(xué)2002一、2〔1分〕】5.對任何數(shù)據(jù)構(gòu)造鏈?zhǔn)酱鎯?gòu)造一定優(yōu)于順序存儲構(gòu)造。()【南京航空航天大學(xué)1997一、3〔1分〕】6．順序存儲方式只能用于存儲線性構(gòu)造。()【中科院軟件所1999六、1-2〔2分〕】【上海海運學(xué)院1997一、1〔1分〕】7．集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。()【大連海事大學(xué)2001一、5(1分)】8.所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。()【合肥工業(yè)大學(xué)2000二、1〔1分〕】9.線性表的特點是每個元素都有一個前驅(qū)和一個后繼。()【合肥工業(yè)大學(xué)2001二、1〔1分〕】10.取線性表的第i個元素的時間同i的大小有關(guān).()【南京理工大學(xué)1997二、9〔2分〕】11.循環(huán)鏈表不是線性表.()【南京理工大學(xué)1998二、1〔2分〕】12.線性表只能用順序存儲構(gòu)造實現(xiàn)。()【青島大學(xué)2001四、2〔1分〕】13.線性表就是順序存儲的表。()【青島大學(xué)2002一、1〔1分〕】14．為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。()【上海海運學(xué)院1995一、1〔1分〕】【上海海運學(xué)院1997一、2〔1分〕】15.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()【上海海運學(xué)院1996一、1〔1分〕】【上海海運學(xué)院1999一、1〔1分〕】16.鏈表是采用鏈?zhǔn)酱鎯?gòu)造的線性表,進展插入、刪除操作時，在鏈表中比在順序存儲構(gòu)造中效率高。()【上海海運學(xué)院1998一、2〔1分〕】一．選擇題1.A2.B3.C4.A5.D6.D7.D8.C9.B10.B,C11.1I11.2I11.3E11.4B11.5C12.B13.C14.C15.C16.A17.A18.A19.D20.C21.B22.D23.C24.B25.B26.A27.D二．判斷題1.×2.√3.√4.×5.×6.×7.×8.×9.×10.×11.×12.×13.×14.√15.×16.√三、填空1．當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進展插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用_______存儲構(gòu)造?！颈狈浇煌ù髮W(xué)2001二、4】2．線性表L=〔a1,a2,…,an〕用數(shù)組表示，假定刪除表中任一元素的概率一樣，那么刪除一個元素平均需要移動元素的個數(shù)是________?！颈狈浇煌ù髮W(xué)2001二、9】3．設(shè)單鏈表的結(jié)點構(gòu)造為(data,next)，next為指針域，指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點,假設(shè)將結(jié)點y插入結(jié)點x之后，那么需要執(zhí)行以下語句:_______；______;【華中理工大學(xué)2000一、4〔2分〕】4．在一個長度為n的順序表中第i個元素〔1<=i<=n〕之前插入一個元素時，需向后移動________個元素?！颈本┕ど檀髮W(xué)2001二、4〔4分〕】5．在單鏈表中設(shè)置頭結(jié)點的作用是________?！竟枮I工業(yè)大學(xué)2000二、1〔1分〕】6．對于一個具有n個結(jié)點的單鏈表，在的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為________,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為________?！竟枮I工業(yè)大學(xué)2001一、1〔2分〕】7．根據(jù)線性表的鏈?zhǔn)酱鎯?gòu)造中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成________和_______；而又根據(jù)指針的連接方式，鏈表又可分成________和________。【西安電子科技大學(xué)1998二、4〔3分〕】8．在雙向循環(huán)鏈表中,向p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是_______、_______、_______、________。【中國礦業(yè)大學(xué)2000一、1〔3分〕】9.在雙向鏈表構(gòu)造中，假設(shè)要求在p指針?biāo)傅慕Y(jié)點之前插入指針為s所指的結(jié)點，那么需執(zhí)行以下語句：s^.next:=p；s^.prior:=________；p^.prior:=s；________:=s；【福州大學(xué)1998二、7(2分)】10．鏈接存儲的特點是利用________來表示數(shù)據(jù)元素之間的邏輯關(guān)系。【中山大學(xué)1998一、1〔1分〕】11.順序存儲構(gòu)造是通過________表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?gòu)造是通過________表示元素之間的關(guān)系的?！颈本├砉ご髮W(xué)2001七、2〔2分〕】12.對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共______個，單鏈表為_______個。【南京理工大學(xué)2000二、2〔3分〕】13.循環(huán)單鏈表的最大優(yōu)點是：________?！靖Ｖ荽髮W(xué)1998二、3(2分)】14.指針p指向單鏈表L中的某結(jié)點，那么刪除其后繼結(jié)點的語句是：________【合肥工業(yè)大學(xué)1999三、2〔2分〕】15.帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是：________【合肥工業(yè)大學(xué)1999三、32000三、2〔2分〕】16.在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是：__【合肥工業(yè)大學(xué)2001三、3〔2分〕】17.帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是：________?！颈本├砉ご髮W(xué)2000二、1〔2分〕】【青島大學(xué)2002三、1〔2分〕】18.在單鏈表p結(jié)點之后插入s結(jié)點的操作是：_______。【青島大學(xué)2002三、2〔2分〕】19.請在以下算法的橫線上填入適當(dāng)?shù)恼Z句?！厩迦A大學(xué)1994五〔15分〕】FUNCTIONinclusion(ha,hb:linklisttp):boolean;{以ha和hb為頭指針的單鏈表分別表示有序表A和B，本算法判別表A是否包含在表B內(nèi)，假設(shè)是，那么返回“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建設(shè)以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;【北京師范大學(xué)1999三】21.已給如下關(guān)于單鏈表的類型說明：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;【廈門大學(xué)2000三、2〔8分〕】22．假設(shè)鏈表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é)點的值各不一樣。請在劃線處填上適當(dāng)內(nèi)容，每個框只填一個語句或一個表達(dá)式，鏈表的結(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;【復(fù)旦大學(xué)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}【燕山大學(xué)1998四、1〔15分〕】24.雙鏈表中結(jié)點的類型定義為：TYPEdpointer=^list;list=RECORDdata:integer;left,right:dpointer;END;如下過程將在雙鏈表第i個結(jié)點〔i>=0〕之后插入一個元素為x的結(jié)點，請在答案欄給出題目中______處應(yīng)填入的語句或表達(dá)式，使之可以實現(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;【廈門大學(xué)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;【同濟大學(xué)2000二、1(10分)】26．在此題的程序中，函數(shù)過程Create_link_list(n)建設(shè)一個具有n個結(jié)點的環(huán)形鏈表;程序過程josephus(n,i,m)對由Create_link_list(n)所建設(shè)的具有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請在橫線處填上適當(dāng)內(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;【復(fù)旦大學(xué)1997四〔12分〕】27．對于給定的線性鏈表head,下面的程序過程實現(xiàn)了按結(jié)點值非降次序輸出鏈表中的所有結(jié)點，在每次輸出一個結(jié)點時，就把剛輸出的結(jié)點從鏈表中刪去。請在劃線處填上適當(dāng)?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；【復(fù)旦大學(xué)1996七〔20分〕1995一〔12分〕與此題相似】28．下面函數(shù)的功能是在一個按訪問頻度不增有序的，帶頭結(jié)點的雙向鏈環(huán)上檢索關(guān)鍵值為x的結(jié)點，對該結(jié)點訪問頻度計數(shù)，并維護該鏈環(huán)有序。假設(shè)未找到，那么插入該結(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<>xDO