數(shù)據(jù)結(jié)構(gòu)第一章緒論部分習(xí)題一、選擇題 1. 下面說法錯(cuò)誤的是 。 (1)算法原地工作的含義是指不需要任何額外的輔助空間。 (2)在相同的規(guī)模n下，復(fù)雜度O(n)的撒在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法。(3)所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界。(4)同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率越低。A、（1） B、（1）（2） C、（1）（4） D、（3）2. 一個(gè)遞歸算法必須包括 。A、遞歸部分 B、終止條件和遞歸部分C、迭代部分 D、終止條件和迭代部分3. 數(shù)據(jù)的 包括查找、插入、刪除、更新、排序等操作類型。A、存儲(chǔ)結(jié)構(gòu) B、邏輯結(jié)構(gòu)C、基本運(yùn)算 D、算法描述4. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。A、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu) D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)5. 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的 。A、存儲(chǔ)結(jié)構(gòu) B、存儲(chǔ)實(shí)現(xiàn) C、邏輯結(jié)構(gòu) D、運(yùn)算實(shí)現(xiàn)6. 通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著 。A、數(shù)據(jù)具有同一特點(diǎn)B、不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同,而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C、每個(gè)數(shù)據(jù)元素都一樣D、數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等7. 以下說法正確的是 。A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位B、數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D、一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)8. 以下說法錯(cuò)誤的是 。A、程序設(shè)計(jì)的實(shí)質(zhì)是數(shù)據(jù)處理B、數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的組織形式，基本運(yùn)算規(guī)定了數(shù)據(jù)的基本操作方式C、運(yùn)算實(shí)現(xiàn)是完成運(yùn)算功能的算法或這些算法的設(shè)計(jì)D、數(shù)據(jù)處理方式總是與數(shù)據(jù)的某種相應(yīng)表示形式相聯(lián)系，反之亦然9. 下列程序段的時(shí)間復(fù)雜度為 。 x=n; y=0; while (x=(y+1)*(y+1) y=y+1;A、O(n) B、O(n1/2 ) C、O(1) D、O(n2)10. 下列敘述中有關(guān)好的編程風(fēng)格的正確描述是 。A、程序中的注釋是可有可無(wú)的B、對(duì)遞歸定義的數(shù)據(jù)結(jié)構(gòu)不要使用遞歸過程C、過程應(yīng)是自封閉的，盡量少使用全程變量D、多采用一些技巧以提高程序的運(yùn)行效率二、填空題 1. 一個(gè)算法有5個(gè)特性：有窮性 、 確定性 、 可行性、有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。2. 算法的時(shí)間復(fù)雜度是指該算法所求解問題規(guī)模（或頻度）的函數(shù)。3. 算法的可行性是指每一條指令都應(yīng)在有限的時(shí)間內(nèi)完成。4、線性結(jié)構(gòu)的特征：邏輯上滿足有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，且其余結(jié)點(diǎn)有 且僅有唯一的一個(gè)直接前趨和一個(gè)直接后繼。5. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序 、 鏈接、索引存儲(chǔ)和散列存儲(chǔ)4種。6. 從邏輯關(guān)系上講數(shù)據(jù)結(jié)構(gòu)主要分為兩大類，它們是線性結(jié)構(gòu) 和 非線性結(jié)構(gòu)。三、給出下列算法的時(shí)間復(fù)雜度。 1、Sum(int n) int sum=0,i,j; for (i=1;i=n;i+) p=1; for(j=1;j=i;j+) p=p*j; sum=sum