二級等級考試公共基礎(chǔ)知識.ppt

公共基礎(chǔ)知識，第2頁，數(shù)據(jù)結(jié)構(gòu)和算法，程序設(shè)計(jì)基礎(chǔ)，軟件工程基礎(chǔ)，數(shù)據(jù)庫基礎(chǔ)知識，第3頁，第1章，數(shù)據(jù)結(jié)構(gòu)和算法，第1頁，算法的基本概念，第2頁，線性結(jié)構(gòu)和非線性結(jié)構(gòu)，第3列的堆棧和定義，二叉樹的定義，第4頁，搜索技術(shù)和排序技術(shù)，第4頁，第1頁，算法的基本概念：(1)算法的空間復(fù)雜性：指算法運(yùn)行期間所需的輔助存儲空間的大小。(2)算法的時間復(fù)雜度：指執(zhí)行算法所需的計(jì)算工作量(基本計(jì)算次數(shù))。(3)算法的基本特征：確定性、可行性、貧困性和信息充分性。(4)算法的有限性：這意味著算法必須在執(zhí)行有限的步驟后結(jié)束。第5頁，示例1:在以下選項(xiàng)中，算法通常不應(yīng)該具有的基本特征是_ _。(5-1)(A)確定性(b)可行性(c)無限性(d)具有足夠的信息，、,示例2:算法的時間復(fù)雜度是指_ _。(2-1)(A)執(zhí)行算法程序所需的時間(b)算法程序的長度(c)算法執(zhí)行期間所需的基本操作數(shù)(d)算法程序中的指令數(shù)，示例3:算法的空間復(fù)雜性指_ _。(3-1)(A)算法程序的長度(b)算法程序中的指令數(shù)(c)算法程序占用的存儲空間(d)算法執(zhí)行所需的存儲空間，第6頁，示例4:以下描述是正確的_ _。(1-1)(A)算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)。算法的空間復(fù)雜度是指算法程序中指令(或語句)的數(shù)量。算法的有限性是指算法必須能夠在執(zhí)行有限的步驟后終止。(d)算法的時間復(fù)雜度是指執(zhí)行算法程序所需的時間，、例5:在計(jì)算機(jī)中，算法是指_ _。(6-1)(A)查詢方法(b)處理方法(c)解決方案的準(zhǔn)確完整描述(d)排序方法，示例6:算法分析的目的是_ _ _ _ _ _。(8-1)(A)找出數(shù)據(jù)結(jié)構(gòu)的合理性(b)找出算法中輸入和輸出之間的關(guān)系(c)分析算法的可理解性和可靠性(d)分析算法的改進(jìn)效率(f)，第7頁，(7)下面的陳述是正確的_ _ _ _ _ _。(069)A)如果一個算法有很大的空間復(fù)雜度，它的時間復(fù)雜度也必須很大；b)如果一個算法有很大的空間復(fù)雜度，它的時間復(fù)雜度必須很??；c)如果一個算法有很大的時間復(fù)雜度，它的空間復(fù)雜度必須很??；d)上述三種說法都不真實(shí)；，第8頁，示例9:算法的基本特征是可行性、確定性和足夠的智能。(7-1)，例7:算法的復(fù)雜度主要包括時間復(fù)雜度和_ _ _ _ _復(fù)雜度。(1-1)，空間，示例8:實(shí)現(xiàn)算法所需的存儲單元數(shù)量和算法的工作負(fù)載分別稱為_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。(6-1)，空間復(fù)雜性和時間復(fù)雜性，以及貧困，(5)問題處理方案的正確和完整的描述被稱為5。(054)算法，第9、2頁。線性結(jié)構(gòu)和非線性結(jié)構(gòu)、棧和列的定義，(1)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本概念主要研究和討論以下三個方面：1)數(shù)據(jù)集中數(shù)據(jù)元素之間的內(nèi)在邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。(2)處理數(shù)據(jù)時，計(jì)算機(jī)中各數(shù)據(jù)元素的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。(3)對各種數(shù)據(jù)結(jié)構(gòu)的操作。(2)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素前后關(guān)系的復(fù)雜性，數(shù)據(jù)結(jié)構(gòu)一般分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩種。如果非空數(shù)據(jù)結(jié)構(gòu)滿足以下兩個條件：只有一個根節(jié)點(diǎn)；(2)每個節(jié)點(diǎn)最多有一個前片和一個后片。數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)，也稱為線性表。因此，線性表、堆棧和隊(duì)列、線性鏈表都是線性結(jié)構(gòu)，而二叉樹是非線性結(jié)構(gòu)。(3)堆棧是一個特殊的線性表：插入和刪除操作只能在固定的末端進(jìn)行，即后進(jìn)先出表。(4)隊(duì)列可視為在一端(隊(duì)列的末端)插入，刪除線性標(biāo)簽(5)線性單鏈表、雙鏈表和循環(huán)鏈表的結(jié)構(gòu)和基本操作：在鏈表的操作過程中，空表和非空表的操作通過鏈接方式統(tǒng)一起來，即循環(huán)鏈表的結(jié)構(gòu)。在第12頁，(6)循環(huán)鏈表有兩個特點(diǎn)：在循環(huán)鏈表中增加一個頭節(jié)點(diǎn)，它的數(shù)據(jù)字段可以任意設(shè)置或根據(jù)需要設(shè)置，指針字段指向線性表第一個元素的節(jié)點(diǎn)。循環(huán)鏈表的頭指針指向頭節(jié)點(diǎn)。(2)循環(huán)鏈表中最后一個節(jié)點(diǎn)的指針不是空的，而是指向頭節(jié)點(diǎn)。(7)數(shù)據(jù)存儲結(jié)構(gòu)：計(jì)算機(jī)存儲空間中數(shù)據(jù)邏輯結(jié)構(gòu)的存儲形式。下面的數(shù)據(jù)結(jié)構(gòu)是一個非線性數(shù)據(jù)結(jié)構(gòu)。(1-2)(A)隊(duì)列(b)線性表(c)二叉樹(d)堆棧，、,例如：以下語句適用于_ _。(2-2)(A)線性表是線性結(jié)構(gòu)(b)堆棧和隊(duì)列是非線性結(jié)構(gòu)(c)線性鏈表是非線性結(jié)構(gòu)(d)二叉樹是線性結(jié)構(gòu)，例如：下面關(guān)于堆棧的陳述是正確的_ _。(3-2)(A)只有數(shù)據(jù)可以插入堆棧(b)只有數(shù)據(jù)可以從堆棧中刪除(c)堆棧是先進(jìn)先出的線性表(d)堆棧是先進(jìn)先出的線性表，例如:下面對隊(duì)列的描述是正確的。(5-3)(A)只有數(shù)據(jù)可以插入隊(duì)列(b)只有數(shù)據(jù)可以從隊(duì)列中刪除(c)隊(duì)列是先進(jìn)先出線性表(d)隊(duì)列是先進(jìn)先出線性表，第14頁，、,例如：堆棧和隊(duì)列的共同點(diǎn)是_ _。(6-2)(A)都是先入先出(b)都是先入后出(c)只允許在端點(diǎn)插入和刪除元素(d)沒有任何共同之處，例如：元素A、b、c、d從堆棧底部到堆棧頂部依次存儲，在第五個元素e放入堆棧之前，堆棧中的元素可以從堆棧中取出，然后堆棧輸出順序可以是_ _。例如：使用鏈表來表示線性表的優(yōu)點(diǎn)是。(8-4)(A)易于插入和刪除(b)相同的物理和邏輯數(shù)據(jù)元素序列(c)比順序存儲少的存儲空間(d)易于隨機(jī)訪問第15頁，示例：線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別為_ _。(7-3)(A)順序存取存儲器結(jié)構(gòu)，順序存取存儲器結(jié)構(gòu)(b)隨機(jī)存取存儲器結(jié)構(gòu)，順序存取存儲器結(jié)構(gòu)(c)隨機(jī)存取存儲器結(jié)構(gòu)，隨機(jī)存取存儲器結(jié)構(gòu)(d)任意存取存儲器結(jié)構(gòu)，任意存取存儲器結(jié)構(gòu)。例如，在單個鏈表中，添加頭節(jié)點(diǎn)的目的是_ _ _ _。(7-4)(A)方便操作的實(shí)現(xiàn)(b)使單個鏈表至少有一個節(jié)點(diǎn)(c)識別表節(jié)點(diǎn)中第一個節(jié)點(diǎn)的位置(d)說明單個鏈表是線性表的鏈?zhǔn)酱鎯?shí)現(xiàn)，、,第16頁，示例：數(shù)據(jù)的存儲結(jié)構(gòu)是指_ _。(4-2)(054)(A)數(shù)據(jù)占用的存儲空間量(b)計(jì)算機(jī)中數(shù)據(jù)的邏輯結(jié)構(gòu)表示(c)計(jì)算機(jī)中數(shù)據(jù)的順序存儲模式(d)存儲在外部存儲器中的數(shù)據(jù)，例如：在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的_ _ _ _ _與所用的計(jì)算機(jī)無關(guān)。(7-1)(A)存儲結(jié)構(gòu)(b)物理結(jié)構(gòu)(c)邏輯結(jié)構(gòu)(d)物理和存儲結(jié)構(gòu)，、，(2)堆棧的以下描述中的錯誤是_ _ _ _ _ _。(054)A)堆棧是先入先出的線性表B)堆棧只能存儲C)堆棧具有存儲功能D)在堆棧的插入和刪除過程中，不需要改變堆棧底部的指針，第17頁，例如：在操作過程中，可以統(tǒng)一空表和非空表操作的結(jié)構(gòu)是_ _ _ _ _ _。(4-1)示例：堆棧有三種基本操作：堆棧進(jìn)入、堆棧退出和_ _ _ _ _ _ _ _ _ _ _。(5-1)，讀取棧頂元素，循環(huán)鏈表，例如：數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)，_ _ _ _ _ _ _ _ _ _數(shù)據(jù)和對數(shù)據(jù)的操作操作。(6-2)，例如：順序存儲方法是將邏輯上相鄰的節(jié)點(diǎn)存儲在物理位置_ _ _ _ _ _的存儲單元中。(7-2)、存儲結(jié)構(gòu)、鄰接關(guān)系、示例：數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的_ _ _ _ _ _ _ _ _ _，以及對數(shù)據(jù)的操作。(6-2)，存儲結(jié)構(gòu)，第18頁，(5)數(shù)據(jù)獨(dú)立性分為邏輯獨(dú)立性和物理獨(dú)立性。當(dāng)數(shù)據(jù)的存儲結(jié)構(gòu)改變時，其邏輯結(jié)構(gòu)也隨之改變(064)邏輯獨(dú)立性，(4)下列陳述是正確的：(059)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一個存儲結(jié)構(gòu)(B)數(shù)據(jù)的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，并且存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)(C)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多個存儲結(jié)構(gòu)，并且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率(D)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多個存儲結(jié)構(gòu)， 各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率，并且 (4)按照“先進(jìn)先出”的原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是4。 (069)堆棧(5)數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。帶鏈隊(duì)列屬于5 (069)線性結(jié)構(gòu)。第19頁，第三頁。二叉樹的定義。(1)全二叉樹是指除最后一層外，每層所有節(jié)點(diǎn)上都有兩個子節(jié)點(diǎn)的二叉樹。(2)完全二叉樹是指除最后一層外，每一層的節(jié)點(diǎn)數(shù)達(dá)到最大值，最后一層只缺少右邊的子節(jié)點(diǎn)(葉節(jié)點(diǎn))的二叉樹。根據(jù)定義，完整的二叉樹絕對是完整的二叉樹，而完整的二叉樹通常不是完整的二叉樹。(3)具有n個節(jié)點(diǎn)的完全二叉樹，父節(jié)點(diǎn)的數(shù)量是int(n/2)，葉節(jié)點(diǎn)的數(shù)量等于點(diǎn)的總和減去父節(jié)點(diǎn)的數(shù)量。在第20頁，(4)二叉樹的I級(i1)上最多有2i-1個節(jié)點(diǎn)。(5)二叉樹的遍歷可以分為三種類型：前序遍歷、前序遍歷和后序遍歷。先序遍歷：首先訪問根節(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；當(dāng)遍歷左右子樹時，根節(jié)點(diǎn)左子樹右子樹仍然是第一個。中間順序遍歷：首先遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遍歷右子樹；當(dāng)遍歷左右子樹時，左子樹-根節(jié)點(diǎn)-右子樹仍然是第一個。第21頁，順序遍歷：首先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點(diǎn)；此外，當(dāng)遍歷左右子樹時，左子樹-右子樹-根節(jié)點(diǎn)仍然是第一個。在二叉樹的第八層，最大的節(jié)點(diǎn)數(shù)是_ _。(1-3)(A)8(B)16(C)128(D)256，,例如：在深度為5的完整二叉樹中，葉節(jié)點(diǎn)的數(shù)量為_ _。(3-3)(A)32(B)31(C)16(D)15，,示例：在完整二叉樹的以下描述中，錯誤為_ _。(2-3)(A)除了最后一層，每層的節(jié)點(diǎn)數(shù)已經(jīng)達(dá)到最大，(b)可能缺少幾個左右葉節(jié)點(diǎn)，(c)完整的二叉樹一般不是完整的二叉樹，(d)有節(jié)點(diǎn)的完整二叉樹的深度是log2n 1，第23頁，第24頁，(10)對于下面的二叉樹，中間順序遍歷的結(jié)果是_ _ _ _ _ _。(069)a)acbdfegb)acbdfgec)abdcgefd)fcadbed,page 25，例如：在先左后右的原則下，根據(jù)訪問根節(jié)點(diǎn)的順序，二叉樹的遍歷可以分為三種類型：前序遍歷、后序遍歷。(2-1)，中間順序，例如：如果一個完整的二叉樹有500個節(jié)點(diǎn)，那么在二叉樹中有_ _ _ _ _個葉節(jié)點(diǎn)。(3-1)，250，第26頁，(4)根據(jù)“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是(064)A)隊(duì)列b)堆棧c)雙鏈表d)二叉樹， (5)在下面的描述中，正確的是(064)A)線性鏈表是線性表的鏈存儲結(jié)構(gòu)b)堆棧和隊(duì)列是非線性結(jié)構(gòu)c)雙鏈表是非線性結(jié)構(gòu)d)對于下面的二叉樹(064)，只有根節(jié)點(diǎn)的二叉樹是線性結(jié)構(gòu)(6)，后續(xù)遍歷的結(jié)果是A)深度為7的全二叉樹中的abcdefb)dbeafcc)abdecfd)debfca(7)。 葉節(jié)點(diǎn)數(shù)為(064)A)32B)31C)64D)63、,第27頁，四、搜索和排序技術(shù)，(1)順序搜索：無序表或具有鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表。方法：從線性表中的第一個元素開始，將線性表中的元素依次與選中的元素進(jìn)行比較。如果他們是平等的，他們就會被發(fā)現(xiàn)。如果線性表中的所有元素都與選中的元素進(jìn)行了比較，但不相等，則在線性表中找不到元素。順序搜索的效率非常低。對于長度為n的線性表，在最壞的情況下，需要進(jìn)行n次比較；平均而言，需要n/2個比較。(2)二分法搜索：必須是有序表。方法：將被檢元素X與國際標(biāo)準(zhǔn)值進(jìn)行比較如果x小于中間項(xiàng)的值，則以相同的方式搜索線性表的前半部分。如果x大于中間項(xiàng)的值，則使用相同的方法在線性表格的后半部分中進(jìn)行搜索。二分法比順序搜索更有效。對于長度為n的有序線性表，在最壞的情況下，只需要log2n比較。第29頁，(3)交換類排序：冒泡排序是最簡單的交換類排序方法，它通過交換相鄰的數(shù)據(jù)元素，逐漸將線性表變?yōu)橛行?。假設(shè)線性表的長度為n，在最壞的情況下，氣泡排序需要從前到后掃描n/2次，從后到前掃描n/2次，并且需要的比較次數(shù)為n(n-1)/2?？焖倥判蚍椒ㄒ彩且环N交換類的排序方法。它從線性表中選擇一個元素T，并將表中的元素與T進(jìn)行比較。較小的元素在前面，較大的元素在后面。它分為兩個子表。然后連續(xù)執(zhí)行相同的分割。直到所有子表都為空。在最壞的情況下，所需的比較次數(shù)是n。(4)插入排序：插入排序是指將無序序列中的元素順序插入到已排序的線性表中。簡單的插入排序方法從線性表的第二個元素到最后一個元素開始，并將每個元素插入到先前排序的子表中。在最壞的情況下，所需的比較次數(shù)是n(n-1)/2。希爾排序法屬于插入排序法，但它對簡單插入排序法有很大的改進(jìn)。它將整個無序序列分成幾個小的子序列進(jìn)行插入和排序。在最壞的情況下，需要進(jìn)行n1.5比較。第31頁，(5)選擇排序：簡單選擇排序是掃描整個線性表，從中選擇最小的元素，并將其交換到表的前面；然后對剩余的子表使用相同的方法，直到子表為空。假設(shè)線性表的長度為n，在最壞的情況下，簡單排序所需的比較次數(shù)為n(n-1)/2。堆排序方法屬于選擇性排序方法。在最壞的情況下，所需的比較次數(shù)為nlog2n。(6)合并和排序是將兩個或多個有序表合并成一個新的有序表。因此，在排序過程中需要最大的內(nèi)存容量。希爾的分類方法屬于哪種類型？(5-2)(A)交換類排序方法(b)插入類排序方法(c)選擇類排序方法(d)構(gòu)建堆排序方法，例如:在以下排序方法中，需要最大內(nèi)存量的是_ _。(6-4)(A)插入排序(b)選擇排序(c)快速排序(d)合并排序，例如:在長度為n的線性表中，最壞情況下所需的比較次數(shù)為_ _。(5-4)(054)(a)n 1(b)n(c)(n 1)/2(d)n/2，(8)在長度為64的有序線性表中順序搜索，最壞情況下所需的比較次數(shù)為_ _。(069)A)63B)64C)6D)7，,第33頁，示例：在最壞的情況下，氣泡排序的時間復(fù)雜度為_ _ _ _ _ _ _ _。(3-2)，n(n-1)/2，例如：眾所周知，數(shù)據(jù)表a中的每個元素都離其最終位置不遠(yuǎn)。為了節(jié)省時間，算法應(yīng)該是_ _。(8-3)(A)堆排序(b