【正文】 原操作 (i)的執(zhí)行時間 ? 算法的執(zhí)行時間 和 原操作執(zhí)行次數(shù)之和 成正比 ? 具體而言：從算法中選取一種對于所研究的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行的次數(shù) 作為算法運行時間的衡量準(zhǔn)則。 A. n2 B. 3n C. n(n+1) D. n3 解答： C 分析：外層循環(huán)執(zhí)行 n 次 ， 內(nèi)層循環(huán)執(zhí)行2,4,6,…… 2n次 ， 共執(zhí)行 (2+4+6+…… 2n)= n(n+1) 次 。 j=2*i。 i=n。 算法和算法分析典型題解析 選擇題 9： 假設(shè)時間復(fù)雜度為 O(n2)的算法在有 200個元素的數(shù)組上運行需要 ， 則在有 400個元素的數(shù)組上運行需要 （ ） ms? A. B. C. D. 解答： C 分析：運行時間為： *(400/200)2=。 1) 算法原地工作的含義是指不需要任何額外的輔助空間 2) 在相同的規(guī)模 n下 ， 復(fù)雜度 O(n)的算法在時間上總是優(yōu)于復(fù)雜度 O(2n)的算法 3) 所謂的時間復(fù)雜度是指最壞情況下 ， 估算算法執(zhí)行時間的一個上界 4) 同一個算法 ， 實現(xiàn)語言的級別越高 ， 執(zhí)行效率就越低 A. 1) B. 1),2) C. 1),4) D. 3) 解答： B 分析：算法原地 （ 也稱就地 ） 工作是指算法的空間復(fù)雜度為 O(1)， 例如直接插入排序算法需要一個用于交換的臨時單元；說法 2)考慮在時間上的性能 ，此時需要考慮兩個復(fù)雜度的系數(shù) ， 例如復(fù)雜度為 O(n)的算法其系數(shù)為 100,算法復(fù)雜度為 O(2n)的算法的系數(shù)為 1， 這兩個函數(shù)曲線就有一個交叉點 ，如果僅就時間復(fù)雜度而言 ， 復(fù)雜度 O(n)的算法優(yōu)于復(fù)雜度為 O(2n)的算法；時間復(fù)雜度需要考慮最壞情況下 ， 算法執(zhí)行時間的一個上界；說法 4)中“ 實現(xiàn)語言的級別 ” 指的是機器語言 、 匯編語言和高級語言 。 算法和算法分析典型題解析 選擇題 6： 某算法的時間復(fù)雜度是 O(n2)， 表明該算法 （ ） 。 算法和算法分析典型題解析 選擇題 5： 算法的時間復(fù)雜度與 （ ） 有關(guān) 。 算法和算法分析典型題解析 選擇題 4： 算法分析的目的是 （ ） ， 算法分析的兩個主要方面是 （ ） 。 算法和算法分析典型題解析 選擇題 3： 當(dāng)輸入非法錯誤時 ， 一個 “ 好 ” 的算法會進行適當(dāng)處理 ， 而不會產(chǎn)生難以理解的輸出結(jié)果 ， 這稱為算法的（ ） 。 算法和算法分析典型題解析 選擇題 2： 算法必須具備輸入 、 輸出和 （ ） 等特性 。 算法和算法分析典型題解析 選擇題 1： 下面 （ ） 不是算法應(yīng)具備的特性 。 算法的空間復(fù)雜度表示為： S(n)=O(g(n)) 表示隨著問題規(guī)模 n 的增大，算法運行所需存儲量的增長率與函數(shù) g(n)的增長率相同。 算法和算法分析 ? 考核知識點 5. 算法的空間復(fù)雜度（ ★ ） 算法的空間復(fù)雜度是指在算法的執(zhí)行過程中需要的輔助空間數(shù)量 。基本語句是執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的語句。 算法和算法分析 ? 考核知識點 4. 算法的時間復(fù)雜度（ ★★★ ） 算法的漸近時間復(fù)雜度（簡稱時間復(fù)雜度）考察當(dāng)問題規(guī)模充分大時，算法中基本語句的執(zhí)行次數(shù)在漸近意義上的階，通常用大 O記號表示。 2. 算法的特性（ ★★★★ ） 輸入、輸出、有窮性、確定性、可行性 3. 算法的描述方法（ ★ ） 常用的描述算法的方法有自然語言、流程圖、程序設(shè)計語言和偽代碼等，其中偽代碼被稱為算法語言，是比較合適的描述算法的方法。抽象數(shù)據(jù)類型的定義部分只包含數(shù)據(jù)的邏輯特性和基本操作的集合，一方面，使用者依據(jù)這些定義來使用抽象數(shù)據(jù)類型，即通過操作集合對該抽象數(shù)據(jù)類型進行各種處理；另一方面，抽象數(shù)據(jù)類型的實現(xiàn)者依據(jù)這些定義來完成該抽象數(shù)據(jù)類型的具體實現(xiàn)，包括存儲結(jié)構(gòu)的設(shè)計和基本操作的實現(xiàn)。抽象數(shù)據(jù)類型可以理解為對數(shù)據(jù)類型的進一步抽象，抽象數(shù)據(jù)類型不局限于機器已定義和實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自定義的數(shù)據(jù)類型。 數(shù)據(jù)類型是高級語言中的一個概念，它是一個值的集合和一組操作的集合，如 C語言中的整型、實型和字符型等。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲結(jié)構(gòu)來存儲，而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的。數(shù)據(jù)的邏輯結(jié)構(gòu) 屬于用戶視圖，是面向問題的 ，反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式。 典型題解析（應(yīng)用題） ? 2. 說明數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。在高級程序設(shè)計語言中，基本數(shù)據(jù)類型隱含著數(shù)據(jù)結(jié)構(gòu)和定義在該結(jié)構(gòu)上的操作的統(tǒng)一。 解答： 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合，抽象數(shù)據(jù)類型是指一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一個操作，程序設(shè)計語言中的數(shù)據(jù)類型是一個值的集合和定義在這個值集上一組操作的總稱。 A. 數(shù)據(jù)元素 B. 數(shù)據(jù)對象 C. 原子類型 D. 存儲結(jié)構(gòu) 解答： B 分析： ADT的三要素為：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系、基本操作。 A. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位 B. 數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小單位 C. 數(shù)據(jù)可由若干個數(shù)據(jù)項構(gòu)成 D. 數(shù)據(jù)元素可由若干個數(shù)據(jù)項構(gòu)成 解答： C 分析： 數(shù)據(jù)是由若干個數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素是由若干個數(shù)據(jù)項構(gòu)成。 A. 每個結(jié)點占用一片連續(xù)的存儲區(qū)域 B. 所有結(jié)點占用一片連續(xù)的存儲區(qū)域 C. 結(jié)點的最后一個域是指針類型 D. 每個結(jié)點有多少個后繼就設(shè)有多少個指針 解答： A 分析： 結(jié)點作為存取操作的獨立單位，需要占用連續(xù)的存儲區(qū)域，但不要求結(jié)點中各組成部分（域）的順序。 A. 數(shù)據(jù)和數(shù)據(jù)之間存在某種聯(lián)系 B. 元素和元