第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)概論及算法分析答案.doc

1、頁(yè)眉內(nèi)容第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)概論及算法分析一、選擇題1 數(shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)中_ 對(duì)象及其關(guān)系的學(xué)科。 （ 1 ）數(shù)值運(yùn)算 （ 2 ）非數(shù)值運(yùn)算（ 3 ）集合（4 ）非集合2 數(shù)據(jù)結(jié)構(gòu)的定義為(K ， R) ，其中K 是 _ 的集合。（ 1 ）算法 （ 2 ）數(shù)據(jù)元素 （3 ）數(shù)據(jù)操作（ 4 ）邏輯結(jié)構(gòu)3 算法分析的目的是_ 。（ 1 ）找出數(shù)據(jù)結(jié)構(gòu)的合理性（ 2 ）研究算法中輸入和輸出的關(guān)系 （3 ）分析算法的效率以求改進(jìn)（ 4 ）分析算法的易懂性和文檔性4.數(shù)據(jù)的不可分割的基本單位是_ 。A. 元素B. 結(jié)點(diǎn)C. 數(shù)據(jù)類型D. 數(shù)據(jù)項(xiàng)5 下列算法suanfa2的時(shí)間復(fù)雜度為_ 。int s

2、uanfa2(int n) int t=1；while(t=n)t=t*2；return t；A.O(log2n)B.O(2n)C.O(n 2 )D.O(n)6. （ ）是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A數(shù)據(jù)符號(hào)B 數(shù)據(jù)對(duì)象C數(shù)據(jù)D數(shù)據(jù)結(jié)構(gòu)7 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的() 。A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.算法D.操作8 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（）及它們之間的相互聯(lián)系。A、理想結(jié)構(gòu)，物理結(jié)構(gòu)b 、理想結(jié)構(gòu)，邏輯結(jié)構(gòu)C、物理結(jié)構(gòu)，邏輯結(jié)構(gòu)d 、抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)9 組成數(shù)據(jù)的基本單位是（）。a 、數(shù)據(jù)項(xiàng)b 、數(shù)據(jù)類型c、數(shù)據(jù)元素d 、數(shù)據(jù)變量10 數(shù)據(jù)在計(jì)算

3、機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A ）存儲(chǔ)結(jié)構(gòu) （ B）邏輯結(jié)構(gòu) （ C）順序存儲(chǔ)結(jié)構(gòu) （ D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)11 算法指的是（ ）1頁(yè)眉內(nèi)容A計(jì)算機(jī)程序B 解決問題的計(jì)算方法C排序算法D解決問題的有限運(yùn)算序列12 下列算法suanfa1中語(yǔ)句 x=x*2； 的執(zhí)行次數(shù)是（）。void suanfa1(int n) int i,j,x=1；for(i=1；i=n；i+)for(j=i； j=n； j+)x=x*2；printf(%d,x)；A.n(n-1)/2B.n(n+1)/2C.n 2D. nlog 2 n13. 由 _ 組成的集合是一個(gè)數(shù)據(jù)對(duì)象。A. 不同類

4、型的數(shù)據(jù)項(xiàng) B. 不同類型的數(shù)據(jù)元素C. 相同類型的數(shù)據(jù)項(xiàng)D. 相同類型的數(shù)據(jù)元素14在下列選項(xiàng)中，哪個(gè)不是一個(gè)算法一般應(yīng)該具有的基本特征_。A.確定性B.可行性C.無(wú)窮性D. 擁有足夠的情報(bào)15在計(jì)算機(jī)中，算法是指_ 。A.查詢方法B.加工方法C.解題方案準(zhǔn)確而完整的描述D. 排序方法16算法的時(shí)間復(fù)雜度是指_。A.執(zhí)行算法程序所需要的時(shí)間B. 算法程序的長(zhǎng)度C. 算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)D. 算法程序中的指令條數(shù)17算法的空間復(fù)雜度是指_。A.算法程序的長(zhǎng)度B.算法程序中的指令條數(shù)C. 算法程序所占的存儲(chǔ)空間D.算法執(zhí)行過程中所需要的存儲(chǔ)空間18下面敘述正確的是 _ 。A. 算法

5、的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B. 算法的空間復(fù)雜度是指算法程序中指令（或語(yǔ)句）的條數(shù) C. 算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止D. 以上三種描述都不對(duì)19 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指_。A.數(shù)據(jù)所占的存儲(chǔ)空間量B.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示頁(yè)眉內(nèi)容C. 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式D. 存儲(chǔ)在外存中的數(shù)據(jù)20算法分析的目的是 _ 。A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性B.找出算法中輸入和輸出之間的關(guān)系C. 分析算法的易懂性和可靠性D.分析算法的效率以求改進(jìn)21_不是算法的基本特征。A. 正確性B. 長(zhǎng)度有限C.在規(guī)定的時(shí)間內(nèi)完成D.確定性二、填空1 一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示( 映象 )

6、 稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。2 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D 是數(shù)據(jù)元素的有限集合，R 是 D 上的關(guān)系有限集合。3 一個(gè)算法的效率可分為時(shí)間效率和空間效率。4 設(shè)問題規(guī)模為 n ，分析下列算法的時(shí)間復(fù)雜度為O(n 1/2 ) 。for (i = 1; i * i =n; i+) +x ;s += x5 設(shè)問題規(guī)模為n ，分析下列算法的時(shí)間復(fù)雜度為O(n 3 ) 。for ( i =1 ;i = n ;i+ )for ( j = 1 ;j = i ; j+ )for ( k=1 ; k = j ; k+) +x ;s += x ; 6 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存

7、儲(chǔ)結(jié)構(gòu)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。7 一個(gè)算法具有 5 個(gè)特性 : 有窮性、確定性、可行性、有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。8 算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。9 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的_ 物理結(jié)構(gòu) _以及對(duì)數(shù)據(jù)的操作運(yùn)算。10數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 _ 線性結(jié)構(gòu) _ 、_ 樹 _ 、_ 圖 _ 和 _ 集合 _ 四種。11在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后續(xù)結(jié)點(diǎn)數(shù)可以_ 不為零 _ 。12 一種抽象數(shù)據(jù)類型包括數(shù)據(jù)和操作兩個(gè)部分。三、判斷1 程序就是算法，但算法不一定是程序。( )3頁(yè)眉內(nèi)容2 數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面。 ()3 非空線性表中任