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

1、習(xí)題參考答案一選擇題1. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為( C)兩大類。A. 動態(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. 在下面的程序段中，對 x 的斌值語句的頻度為( 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)酱鎯Y(jié)構(gòu)表示數(shù)據(jù)時，相鄰的數(shù)據(jù)元素的存儲地址(C)。A. 一定連續(xù)B 一定不連續(xù)C.不一定連續(xù)D部分連續(xù)，部分不連續(xù)4. 下面關(guān)于算法說法正確的是( D)。A. 算法的時間

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

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

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

5、結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算這3 方面的內(nèi)容。【解答】略。4.運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。試舉例說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式完全相同，只是對于運算的定義不同，使得兩個結(jié)構(gòu)具有顯著不同的特性?！窘獯稹?比如順序棧和循環(huán)隊列， 二者的邏輯結(jié)構(gòu)都是線性結(jié)構(gòu)， 都采用順序存儲方式存儲， 但它們的運算不同， 棧限定元素的插入和刪除在棧頂進(jìn)行， 隊列限定元素在隊尾插入、 在隊 首刪除，因此它們是截然不同的數(shù)據(jù)結(jié)構(gòu)。5分析下列程序段中帶標(biāo)號“語句的執(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. 寫出下列各程序段關(guān)于n 的時間復(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計算一元 n 次多項式 P( x, n) =a+ ax + a2x2 + +“的值，輸人 x,n, a, a,an,輸出多項式P(x, n)的值。設(shè)計算法求解，請選擇合適的輸人、輸出格式，要求算法具有較好的時間性能?！窘獯稹?將一元 n 次多項式做如下改寫：P( x, n) =a0alxa2x2 anxnn-1=a0x(al a2x anxn-1) =ao+ X(a| + x(a2+ x(a3+ . . x(an-1 + xan) 按指數(shù)遞減次序輸人各系數(shù)，即輸人次序為an, an-1, , , a2, a0 算法如下：main( )s = 0;scanf( ”%f ,&x);for(k=