數(shù)據(jù)結(jié)構(gòu)與算法第1章參考答案08

1、習(xí)題參考答案一選擇題1. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為( C)兩大類(lèi)。A. 動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2. 在下面的程序段中，對(duì) x 的斌值語(yǔ)句的頻度為( C)。for( t = 1; kv= n;k + + )for (j=1;j = n; j + + )x=x 十 1 ；2A. O(2n) B. O (n)C. O (n2) D. O(1og2n)3. 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示數(shù)據(jù)時(shí)，相鄰的數(shù)據(jù)元素的存儲(chǔ)地址(C)。A. 一定連續(xù)B 一定不連續(xù)C.不一定連續(xù)D部分連續(xù)，部分不連續(xù)4. 下面關(guān)于算法說(shuō)法正確的是( D)。A. 算法的時(shí)間

2、復(fù)雜度一般與算法的空間復(fù)雜度成正比B. 解決某問(wèn)題的算法可能有多種，但肯定采用相同的數(shù)據(jù)結(jié)構(gòu)C. 算法的可行性是指算法的指令不能有二義性D. 同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低5. 在發(fā)生非法操作時(shí)，算法能夠作出適當(dāng)處理的特性稱(chēng)為(B)。A.正確性 B.健壯性 C.可讀性 D.可移植性二、判斷題1數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。(V)2順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插人、刪除運(yùn)算效率高。(X)3數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的次序關(guān)系，它依賴(lài)于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。(X)4. 算法的優(yōu)劣與描述算法的語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)的性能有關(guān)。(X)5. 算法必須有輸出，但可以

3、沒(méi)有輸人。(V)三、筒答題1常見(jiàn)的邏輯結(jié)構(gòu)有哪幾種，各自的特點(diǎn)是什么？常用的存儲(chǔ)結(jié)構(gòu)有哪幾種，各自的特點(diǎn) 是什么？【答】常見(jiàn)的四種邏輯結(jié)構(gòu)： 集合結(jié)構(gòu)：數(shù)據(jù)元素之間是“屬于同一個(gè)集合” 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系 樹(shù)結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系 結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系。常見(jiàn)的四種存儲(chǔ)結(jié)構(gòu)有： 順序存儲(chǔ)：把邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中。順序存儲(chǔ)結(jié)構(gòu)是 一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。 鏈接存儲(chǔ)：對(duì)邏輯上相鄰的元素不要求物理位置相鄰的存儲(chǔ)單元，元素間的邏輯關(guān)系 通過(guò)附設(shè)的指針域來(lái)表示。 索引存儲(chǔ)：通過(guò)建立索引表存

4、儲(chǔ)結(jié)點(diǎn)信息的方法，其中索引表一般存儲(chǔ)結(jié)點(diǎn)關(guān)鍵字和 一個(gè)地點(diǎn)信息，可通過(guò)該地址找到結(jié)點(diǎn)的其他信息。 散列存儲(chǔ)：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址的方法。2簡(jiǎn)述算法和程序的區(qū)別?！窘獯稹?一個(gè)算法若用程序設(shè)計(jì)語(yǔ)言來(lái)描述， 則它就是一個(gè)程序。 算法的含義與程序十分相 似，但又有區(qū)別。一個(gè)程序不一定滿足有窮性。例如，操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞， 它將永遠(yuǎn)不會(huì)停止， 即使沒(méi)有作業(yè)需要處理， 它仍處于動(dòng)態(tài)等待中。因此， 操作系統(tǒng)不是一 個(gè)算法。另一方面， 程序中的指令必須是機(jī)器可執(zhí)行的， 而算法中的指令則無(wú)此限制。 算法 代表了對(duì)問(wèn)題的解，而程序則是算法在計(jì)算機(jī)上的特定的實(shí)現(xiàn)。3.試舉一個(gè)數(shù)據(jù)

5、結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算這3 方面的內(nèi)容。【解答】略。4.運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉例說(shuō)明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同，只是對(duì)于運(yùn)算的定義不同，使得兩個(gè)結(jié)構(gòu)具有顯著不同的特性。【解答】 比如順序棧和循環(huán)隊(duì)列， 二者的邏輯結(jié)構(gòu)都是線性結(jié)構(gòu)， 都采用順序存儲(chǔ)方式存儲(chǔ)， 但它們的運(yùn)算不同， 棧限定元素的插入和刪除在棧頂進(jìn)行， 隊(duì)列限定元素在隊(duì)尾插入、 在隊(duì) 首刪除，因此它們是截然不同的數(shù)據(jù)結(jié)構(gòu)。5分析下列程序段中帶標(biāo)號(hào)“語(yǔ)句的執(zhí)行頻度 (n 為正整數(shù))。(1) j = 1; k=0;while ( j=n-1 ) j ； k=j; * 【解答】 n-1( 2)i

6、=0 ； s=0； n=100；do i+ ；s+= 10*i ;/ * # * /while!(in&s 0)if (x100) x-=10; y-;/else x ;解答 10006. 寫(xiě)出下列各程序段關(guān)于n 的時(shí)間復(fù)雜度。( 1 ) a= 1 ； m= 1 ；while ( av n)m = a;a*= 3； 解答 O(n)(2) 設(shè) n 是偶數(shù)。for (i=1 , s= 0; i v= n; i + + )for (j=2*i ; j v= n; j + + )s；解答 O( n2)(3) for (i=1 ; i =n-1 ; i + + )k = i;for(j=i 1 ；j R

7、j + 1) k = j; t = R : k ; R : k =R : i: ; R : i: =t ;解答 O( n2)7計(jì)算一元 n 次多項(xiàng)式 P( x, n) =a+ ax + a2x2 + +“的值，輸人 x,n, a, a,an,輸出多項(xiàng)式P(x, n)的值。設(shè)計(jì)算法求解，請(qǐng)選擇合適的輸人、輸出格式，要求算法具有較好的時(shí)間性能?！窘獯稹?將一元 n 次多項(xiàng)式做如下改寫(xiě)：P( x, n) =a0alxa2x2 anxnn-1=a0x(al a2x anxn-1) =ao+ X(a| + x(a2+ x(a3+ . . x(an-1 + xan) 按指數(shù)遞減次序輸人各系數(shù)，即輸人次序?yàn)閍n, an-1, , , a2, a0 算法如下：main( )s = 0;scanf( ”%f ,&x);for(k=