數(shù)據(jù)結(jié)構(gòu)1題復(fù)習(xí)題

1、PAGE PAGE 4數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題ch1緒論一、填空題1、填空題 （每小空1分，共5分）（ ）由某一數(shù)據(jù)對(duì)象和該對(duì)象中各個(gè)數(shù)據(jù)成員間的關(guān)系組成。依據(jù)所有數(shù)據(jù)成員之間關(guān)系的不同，（ ）分為兩大類(lèi)：（ ）和（ ）。在（ ）中的各個(gè)數(shù)據(jù)成員依次排列在一個(gè)線(xiàn)性序列中；（ ）的各個(gè)數(shù)據(jù)成員不再保持在一個(gè)線(xiàn)性序列中，每個(gè)數(shù)據(jù)成員可能與零個(gè)或多個(gè)其他數(shù)據(jù)成員發(fā)生聯(lián)系。根據(jù)視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)的（ ）和（ ）。（ ）是面向問(wèn)題的，（ ）是面向計(jì)算機(jī)的。Key： 數(shù)據(jù)結(jié)構(gòu) 線(xiàn)性結(jié)構(gòu) 非線(xiàn)性結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)2、填空題 （每小空1分，共5分）算法是一個(gè)有窮的指令集，它為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)

2、算序列。它應(yīng)當(dāng)具有輸入、輸出、（ ）、有窮性和可執(zhí)行性等特性。算法效率的度量分為（ ）和（ ）。（ ）主要通過(guò)在算法的某些部位插裝時(shí)間函數(shù)來(lái)測(cè)定算法完成某一規(guī)定功能所需的時(shí)間。而（ ）不實(shí)際運(yùn)行算法，它是分析算法中語(yǔ)句的執(zhí)行次數(shù)來(lái)度量算法的時(shí)間復(fù)雜性。程序所需的存儲(chǔ)空間包含兩個(gè)部分（ ）和（ ）。（ ）空間的大小與輸入輸出數(shù)據(jù)的個(gè)數(shù)多少，數(shù)值大小無(wú)關(guān)；（ ）空間主要包括其大小與問(wèn)題規(guī)模有關(guān)的成分變量所占空間，引用變量所占空間，以及遞歸棧所用的空間，還有在算法運(yùn)行過(guò)程中動(dòng)態(tài)分配和回收的空間。Key：確定性事后測(cè)量事前估計(jì)固定部分可變部分二、判斷題3、判斷下列敘述的對(duì)錯(cuò)。如果正確，在題前的括號(hào)內(nèi)填

3、入“”，否則填入“”。 （）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象與對(duì)象中數(shù)據(jù)元素之間關(guān)系的集合。（）數(shù)據(jù)結(jié)構(gòu)是具有結(jié)構(gòu)的數(shù)據(jù)對(duì)象。（）數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶(hù)按使用需要建立的。（）算法和程序原則上沒(méi)有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者是通用的。4、判斷下列敘述的對(duì)錯(cuò)。如果正確，在題前的括號(hào)內(nèi)填入“”，否則填入“”。 （）所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。（） 同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。（）數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。（）數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體

4、。（）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類(lèi)：線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)。三、簡(jiǎn)答題5、試計(jì)算以下求和程序中所有語(yǔ)句的總執(zhí)行次數(shù)。 float sum（ float a , int n ） float s = 0.0； for （ int i = 0； i n； i+ ）s += ai； return s；Key：2n+36、試計(jì)算以下遞歸求和程序中所有語(yǔ)句的總執(zhí)行次數(shù)。 float rsum（ float a , int n ） if （ n = 0 ） return a0； else return rsum（ a, n-1 ） + an-1； Key：7、試用大O表示法給出下面程序的時(shí)間復(fù)雜性。

5、void out （ float x , int m, int n ） float sum ； for （ int i = 0； i m； i+ ） sumi = 0.0； for （ int j = 0； j n； j+ ） sumi += xij； for （ int i = 0； i m； i+ ）cout Line: i : sumi endl；Key：8、設(shè)n為正整數(shù), 分析下列各程序段中加下劃線(xiàn)的語(yǔ)句的執(zhí)行次數(shù)。（1）for （ int i = 1； i = n； i+ ）for （ int j = 1； j = n； j+ ）cij=0.0；for （int k = 1； k = n； k+ ）cij = cij + aik * bkj； Key：n3（2）x = 0； y = 0； for （ int i = 1；