數(shù)據(jù)結(jié)構(gòu)考試題庫(kù)含參考答案

/121．?dāng)?shù)據(jù)結(jié)構(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ǔ)密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?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)銷大（用于指針），另外不能折半查找等。（3）索引存儲(chǔ)方式。除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(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ǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。3．?dāng)?shù)據(jù)類型是程序設(shè)計(jì)語(yǔ)言中的一個(gè)概念，它是一個(gè)值的集合和操作的集合。如C語(yǔ)言中的整型、實(shí)型、字符型等。整型值的范圍（對(duì)具體機(jī)器都應(yīng)有整數(shù)范圍） ，其操作有加、減、乘、除、求余等。實(shí)際上數(shù)據(jù)類型是廠家提供給用戶的已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)?！俺橄髷?shù)據(jù)類型（ADT）”指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。無(wú)論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機(jī)器已定義和實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實(shí)現(xiàn)三部分，封裝在一起， 對(duì)用戶透明（提供接口），而不必了解實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計(jì)不再是“藝術(shù)”，而是向“科學(xué)”邁進(jìn)了一步。4．（1）數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運(yùn)算是對(duì)數(shù)據(jù)定義的一組操作，運(yùn)算是定義在邏輯結(jié)構(gòu)上的，和存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)，而運(yùn)算的實(shí)現(xiàn)則是依賴于存儲(chǔ)結(jié)構(gòu)。（2）邏輯結(jié)構(gòu)相同但存儲(chǔ)不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如，線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，采用順序存儲(chǔ)結(jié)構(gòu)為順序表，而采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。（3）棧和隊(duì)列的邏輯結(jié)構(gòu)相同，其存儲(chǔ)表示也可相同（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。（4）數(shù)據(jù)結(jié)構(gòu)的評(píng)價(jià)非常復(fù)雜，可以考慮兩個(gè)方面，一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整的刻劃了問(wèn)題的基本特征；二是是否容易實(shí)現(xiàn)（如對(duì)數(shù)據(jù)分解是否恰當(dāng)；邏輯結(jié)構(gòu)的選擇是否適合于運(yùn)算的功能，是否有利于運(yùn)算的實(shí)現(xiàn)；基本運(yùn)算的選擇是否恰當(dāng)。）5．評(píng)價(jià)好的算法有四個(gè)方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時(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ù)雜度。（5）算法是對(duì)特定問(wèn)題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有五個(gè)重要特性：有窮性、確定性、可行性、輸入和輸出。6）頻度。在分析算法時(shí)間復(fù)雜度時(shí)，有時(shí)需要估算基本操作的原操作，它是執(zhí)行次數(shù)最多的一個(gè)操作，該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。7．集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。 8．邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(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)系的有限集合。．“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語(yǔ)有兩種含義，一是作為一門(mén)課程的名稱；二是作為一個(gè)科學(xué)的概念。作為科學(xué)概念，目前尚無(wú)公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個(gè)方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，三是對(duì)數(shù)據(jù)進(jìn)行的操作（運(yùn)算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡(jiǎn)化情況。．見(jiàn)上面題2。．將學(xué)號(hào)、姓名、平均成績(jī)看成一個(gè)記錄（元素，含三個(gè)數(shù)據(jù)項(xiàng)），將 100個(gè)這樣的記錄存于數(shù)組中。因一般無(wú)增刪操作，故宜采用順序存儲(chǔ)。typedefstruct{int num;//學(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ī)查找；若通訊錄經(jīng)常有增刪操作，用鏈?zhǔn)酱鎯?chǔ)結(jié)構(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。structnode{int year,month,day;};typedefstruct{int num;//帳號(hào)charname[8];//姓名structnodedate;//開(kāi)戶年月日inttag;//儲(chǔ)蓄類型，如：0-零存，1-一年定期,,floatput;//存入累加數(shù);float interest;//利息float total;// 帳面總數(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次。(2)是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)是⑷的循環(huán)體，每次比 (4)少一次判斷，故執(zhí)行次數(shù)是n+(n-1)+, +2=(n+2)(n-1)/2 次。注意分析時(shí)，不要把 (2)分析成n次，更不是1次。.4(這時(shí)i=4, s=100)REPEAT語(yǔ)句先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時(shí)退出循環(huán)。.算法在最好情況下，即二進(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)。.該算法功能是將原單循環(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)。.第一層FOR循環(huán)判斷 n+1次，往下執(zhí) 行n次，第二 層FOR執(zhí)行次數(shù)為(n+(n-1)+(n-2)+表：,+1)，第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下, nni=j=nj=n-11nn-12 3n n ,n-1 n-1 ,j=3J3J3j=222j=11執(zhí)行次數(shù)為(1+2+,+n)+(2+3+7+n)+,2+n=n*n(n+1)/2-n(n 2-1)/6。在n=5時(shí)，f(5)=55，執(zhí)行過(guò)程中，輸出結(jié)果為： sum=15,sum=29,sum=41,sum=50,sum=55(每個(gè)sum=占一行,為節(jié)省篇幅，這里省去換行)。.O(n.O(n2),m的值等于賦值語(yǔ)句2m：=m+13的運(yùn)行次數(shù)’其計(jì)算式為26.26.(1)O(n)2?5.(1)O(1) (2)O(n) (3)O(n )2)O(n)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+qFo設(shè)Fm的執(zhí)行次數(shù)為Bm(m=0、Fn-2被執(zhí)行兩次，即Bn-2=2；直至數(shù)為前兩等式第一因式系數(shù)之和，數(shù)列?？梢越獾茫?、2、，、n-1)，由以上等式可知，F(xiàn)1被執(zhí)行p次、Fo被執(zhí)行q次，即B1=p,即Bm