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

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