❶ 電腦培訓分享數據結構與演算法知識
對於大多數的程序員來說，在學習數據分析等技術的時候需要先了解關於數據結構以及演算法等知識點，下面我們就給大家簡單介紹一下什麼是數據結構?什麼是演算法?
大部分數據結構和演算法教材，在開篇都會給這兩個概念讓悶下一個明確的定義。但是，這些定義都很抽象，對理解這兩個概念並沒有實質性的幫助，反倒會讓你陷入死摳定義的誤區。畢竟，我們現在學習，並不是為了考試，所以，概念背得再牢，不會用也就沒什麼用。
雖然我們說沒必要深挖嚴格的定義，但是這並不等於不需要理解概念。下面我就從廣義和狹義兩個層面，來幫你理解數據結構與演算法這兩個概念。
從廣義上講，數據結構就是指一組數據的存儲結構。演算法就是正滑悔操作數據的一組方法。
圖書館儲藏書籍你肯定見過吧?為了方便查找，圖書管理員一般會將書籍分門別類進行「存儲」。按照一定規律編號，就是書籍這種「數據」的存儲結構。
那我們如何來查找一本書呢?有很多種辦法，你當然可以一本一本地找，也可以先根據書籍類別的編號，是人文，還是科學、計算機，來定位書架，然後再依次查找。籠統地說，這些查找方法都是演算法。
從狹義上講，也就是我們專欄要講的，是指某些著名的數據結構和演算法，比如隊列、棧、堆、二分查找、動態規劃等。這些都是前人智慧的結晶，我們可以直接拿來用。我們要講的這些數據結構和演算法，都是前人從很多實際操作場景中抽象出來的，經過非常多的求證和檢驗，可以高效地幫助我們解決很多實際的開發問題。
那數據結構和演算法有什麼關系呢?為什麼大部分書都把這兩個東西放到一塊兒來講呢?
這是因為，數據結構和演算法是相輔相成的。數據結構是為演算法服務的，演算法要作用在特定的數據結構之上。因此，我們無法孤立數據結構來講演算法，也無法孤立演算法舉正來講數據結構。
比如，因為數組具有隨機訪問的特點，常用的二分查找演算法需要用數組來存儲數據。但如果IT培訓選擇鏈表這種數據結構，二分查找演算法就無法工作了，因為鏈表並不支持隨機訪問。
數據結構是靜態的，它只是組織數據的一種方式。如果不在它的基礎上操作、構建演算法，孤立存在的數據結構就是沒用的。
❷ 求2011年九月以及以前的計算機二級考試C語言試題及答案、以及考試內容分析和解題技巧。記住只要C的。
(1)下面敘述正確的是________。
A)演算法的執行效率與數據的存儲結構無關
B)演算法的空間復雜度是指演算法程序中指令(或語句)的條數
C)演算法的有窮性是指演算法必須能在執行有限個步驟之後終止
D)演算法的時間復雜度是指執行演算法程序所需要的時間
(1)C
知識點:演算法的基本概念；演算法復雜度的概念和意義(時間復雜度與空間復雜度)
評 析：演算法的設計可以避開具體的計算機程序設計語言，但演算法的實現必須藉助程序設計語言中提供的數據類型及其演算法。數據結構和演算法是計算機科學的兩個重要支柱。它們是一個不可分割的整體。演算法在運行過程中需輔助存儲空間的大小稱為演算法的空間復雜度。演算法的有窮性是指一個演算法必須在執行有限的步驟以後結束。演算法的時間復雜度是指執行演算法所需要的計算工作量，即演算法執行過程中所需要的基本運算次數。
(2)以下數據結構屬於非線性數據結構的是________。
A)隊列 B)線性表 C)二叉樹 D)棧
(2)C
知識點:棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算
評 析:線性表、棧和隊列等數據結構所表達和處理的數據以線性結構為組織形式。棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又稱後進先出表(Last In First Out)。隊列可看作是插入在一端進行，刪除在另一端進行的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。在隊列中，只能刪除隊頭元素，隊列的最後一個元素一定是最新入隊的元素。因此隊列又稱先進先出表(First In First Out)。二叉樹的數據結構是樹型結構，結構中數據元素之間存在著一對多的關系，因此它是一種非線性數據結構。
(3)在一棵二叉樹上第8層的結點數最多是________。
A)8 B)16 C)128 D)256
(3)C
知識點：二叉樹的定義及其存儲結構
評 析:根據二叉樹的性質：二叉樹第i(I>1)層上至多有2i-1個結點。得到第8層的結點數最多是128。
(4)下面描述中，不符合結構化程序設計風格的是________。
A)使用順序、選擇和重復(循環)三種基本控制結構表示程序的控制邏輯
B)自頂向下
C)注重提高程序的執行效率
D)限制使用goto語句
(4)C
知識點：結構化程序設計
評 析：結構化程序設計方法的四條原則是：1．自頂向下：2．逐步求精；3．模塊化；4．限制使用goto語句。「自頂向下」是說，程序設計時，應先考慮總體，後考慮細節，先考慮全局目標，後考慮局部目標；「逐步求精』』是說，對復雜問題，應設計一些子目標作過渡，逐步細節化；「模塊化」是說，一個復雜問題肯定是由若干稍簡單的問題構成，解決這個復雜問題的程序，也應對應若干稍簡單的問題，分解成若干稍小的部分。
(5)下面概念中，不屬於面向對象方法的是________。
A)對象、消息 B)繼承、多態 C)類、封裝 D)過程調用
(5)D
知識點:面向對象的程序設計方法、對象、方法、屬性及繼承與多態性
評 析:面向對象方法是一種運用對象、類、封裝、繼承、多態和消息等概念來構造、測試、重構軟體的方法。面向對象方法從對象出發，發展出對象、類、消息、繼承等概念。
(6)在結構化方法中，用數據流程圖(DFD)作為描述工具的軟體開發階段是________。
A)可行性分析 B)需求分析 C)詳細設計 D)程序編碼
(6)B
知識點:結構化設計方法
評 析:軟體開發階段包括需求分析、總體設計、詳細設計、編碼和測試五個階段。其中需求分析階段常用的工具是數據流程圖和數據字典。
(7)軟體生命周期中所花費用最多的階段是________。
A)詳細設計 B)軟體編碼 C)軟體測試 D)軟體維護
(7)D
知識點:軟體工程基本概念，軟體生命周期概念，軟體工具與軟體開發環境
評 析:軟體生命周期分為軟體定義、軟體開發及軟體運行維護3個階段。本題中詳細設計、軟體編碼和軟體測試都屬於軟體開發階段；維護是軟體生命周期的最後一個階段，也是持續時間最長，花費代價最大的一個階段，軟體工程學的一個目的就是提高軟體的可維護性，降低維護的代價。
(8)資料庫系統的核心是________。
A)數據模型 B)DBMS C)軟體工具 D)資料庫
(8)B
知識點:資料庫的基本概念：資料庫，資料庫管理系統，資料庫系統
評 析:資料庫管理系統DBMS是資料庫系統的核心。DBMS是負責資料庫的建立、使用和維護的軟體。DBMS建立在操作系統之上，實施對資料庫的統一管理和控制。用戶使用的各種資料庫命令以及應用程序的執行，最終都必須通過DBMS。另外，DBMS還承擔著資料庫的安全保護工作，按照DBA所規定的要求，保證資料庫的完整性和安全性。
(9)下列敘述中正確的是________。
A)數據處理是將信息轉化為數據的過程
B)資料庫設計是指設計資料庫管理系統
C)如果一個關系中的屬性或屬性組並非該關系的關鍵字，但它是另一個關系的關鍵
字，則稱其為本關系的外關鍵字
D)關系中的每列稱為元組，一個元組就是一個欄位
(9)C
知識點:數據模型，實體聯系模型及E-R圖，從E-R圖導出關系數據模型
評 析：數據處理是指將數據轉換成信息的過程，故選項A敘述錯誤；設計資料庫的目的實質上是設計出滿足實際應用需求的實際關系模型，故選項B敘述錯誤；關系中的行稱為元組，對應存儲文件中的記錄，關系中的列稱為屬性。對應存儲文件中的欄位，故D選項敘述錯誤。
(10)下列模式中，_______是用戶模式。
A)內模式 B)外模式 C)概念模式 D)邏輯模式
(10)B
知識點：資料庫的基本概念：資料庫，資料庫管理系統，資料庫系統
評 析：資料庫管理系統的三級模式結構由外模式、模式和內模式組成。外模式，或稱子模式，或稱用戶模式，是指資料庫用戶所看到的數據結構，是用戶看到的數據視圖。模式，或稱邏輯模式，是資料庫中對全體數據的邏輯結構和特性的描述，是所有用戶所見到的數據視圖的總和。外模式是模式的一部分。內模式，或稱存儲模式，或稱物理模式，是指數據在資料庫系統內的存儲介質上的表示。即對數據的物理結構和存取方式的描述。
36)演算法的時間復雜度是指_______。
A)執行演算法程序所需要的時間
B)演算法程序的長度
C)演算法執行過程中所需要的基本運算次數
D)演算法程序中的指令條數
(36)C
知識點：演算法復雜度的概念和意義(時問復雜度與空間復雜度)
評析：所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。為了能夠比較客觀地反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。為此，可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。
(37)下列敘述中正確的是_______。
A)線性表是線性結構 B)棧與隊列是非線性結構
C)線性鏈表是非線性結構 D)二叉樹是線性結構
(37)A
知識點：線性結構與非線性結構的概念
評析：根據數據結構中各數據元素之間相關聯關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。如果一個非空的數據結構滿足下列兩個條件： (1)有且只有一個根結點； (2)每一個結點最多有一個前件，也最多有一個後件。則稱該數據結構為線性結構，又稱線性表。所以線性表、棧與隊列、線性鏈表都是線性結構，而二叉樹是非線性結構。
(38)下面關於完全二叉樹的敘述中，錯誤的是_______。
A)除了最後一層外，每一層上的結點數均達到最大值
B)可能缺少若干個左右葉子結點
C)完全二叉樹一般不是滿二叉樹
D)具有結點的完全二叉樹的深度為[log2n]+l
(38)B
知識點：二叉樹的定義及其存儲結構
評析：這里考察完全二又樹與滿二叉樹的定義及二叉樹的性質。滿二叉樹指除最後一層外每一層上所有結點都有兩個子結點的二叉樹。完全二叉樹指除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若乾子結點(葉子結點)的二叉樹。因此選項A是正確的，而選項B是錯誤的。由定義可知，滿二叉樹肯定是完全二又樹，而完全二又樹一般不是滿二叉樹，因此選項c是正確的敘述。選項D即二又樹性質(5)，也是正確的。
(39)結構化程序設計主要強調的是_______。
A)程序的規模 B)程序的易讀性
C)程序的執行效率 D)程序的可移植性
(39)B
知識點：結構化程序設計
評析：結構化程序設計主要強調的足結構化程序清晰易讀，可理解性好，程序員能夠進行逐步求精、程序證明和測試．以保證程序的正確性。
(40)在軟體生命周期中，能准確地確定軟體系統必須做什麼和必須具備哪些功能的階段是_______。
A)概要設計 B)詳細設計 C)可行性分析 D)需求分析
(40)D
知識點：軟體工程基本概念，軟體生命周期概念，軟體工具與軟體開發環境
評析：通常，將軟體產品從提出、實現、使用維護到停止使用退役的過程稱為軟體生命周期。也就是說，軟體產品從考慮其概念開始，到該軟體產品不能使用為止的整個時期都屬於軟體生命周期。軟體生命周期的主要活動階段為：
① 可行性研究和計劃制定。確定待開發軟體系統的開發目標和總的要求，給出它的功能、性能、可靠性以及介面等方面的可行方案，制定完成開發任務的實施計劃。
②需求分析。對待開發軟體提出的需求進行分析並給出詳細定義，即准確地確定軟體系統的功能。編寫軟體規格說明書及初步的用戶手冊，提交評審。
③軟體設計。系統設計人員和程序設計人員應該在反復理解軟體需求的基礎上，給出軟體的結構、模塊的劃分、功能的分配以及處理流程。
④軟體實現。把軟體設計轉換成計算機可以接受的程序代碼。即完成源程序的編碼，編寫用戶手冊、操作手冊等面向用戶的文檔，編寫單元測試計劃。
⑤軟體測試。在設計測試用例的基礎上，檢驗軟體的各個組成部分。編寫測試分析報告。
⑥運行和維護。將已交付的軟體投入運行，並存運行使用中不斷地維護，根據新提出的需求進行必要而且可能的擴充和刪改。
(41)數據流圖用於抽象描述一個軟體的邏輯模型，數據流圖由一些特定的圖符構成。下列圖符名標識的圖符不屬於數據流圖合法圖符的是_______。
A)控制流 B)加工 C)數據存儲 D)源和潭
(41)A
知識點：結構化分析方法，數據流圖，數據字典，軟體需求規格說明書
評析：數據流圖從數據傳遞和加工的角度，來刻畫數據流從輸入到輸出的移動變換過程。數據流圖中的主要圖形元素有：加工(轉換)、數據流、存儲文件(數據源)、源和潭。
(42)軟體需求分析一般應確定的是用戶對軟體的_______。
A)功能需求 B)非功能需求 C)性能需求 D)功能需求和非功能需求
(42)D
知識點：結構化設計方法
評析：軟體需求分析中需要構造一個完全的系統邏輯模型，理解用戶提出的每一功能與性能要求，是用戶明確自己的任務。因此，需求分析應確定用戶對軟體的功能需求和非功能需求。
(43)下述關於資料庫系統的敘述中正確的是_______。
A)資料庫系統減少了數據冗餘
B)資料庫系統避免了一切冗餘
C)資料庫系統中數據的一致性是指數據類型的一致
D)資料庫系統比文件系統能管理更多的數據
(43)A
知識點：資料庫的基本概念：資料庫，資料庫管理系統，資料庫系統
評析：由於數據的集成性使得數據可為多個應JH=j所共享，特別是在網路發達的今天，資料庫與網路的結合擴大了數據關系的應用范圍。數據的共享自身義可極大地減少數據冗餘性，不僅減少了不必要的存儲空間，更為重要的是可以避免數據的不一致性。所謂數據的一致性是指在系統中同一數據的不同出現應保持相同的值，而數據的不一致性指的是同一個數據在系統的不同拷貝處有不同的值。
(44)關系表中的每一橫行稱為一個_______。
A)元組 B)欄位 C)屬性 D)碼
(44)A
知識點：資料庫的基本概念：資料庫．資料庫管理系統，資料庫系統
評析：在關系資料庫中，關系模型採用二維表來表示，簡稱「表」。二維表是由表框架及表元組組成。在表框架中，按行可以存放數據，每行數據稱為元組。
(45)資料庫設計包括兩個方面的設計內容，它們是_______。
A)概念設計和邏輯設計 B)模式設計和內模式設計
C)內模式設計和物理設計 D)結構特性設計和行為特性設計
(45)A
知識點：資料庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略
評析：資料庫設計可分為概念設計與邏輯設計。資料庫概念設計的目的是分析數據問內存語義關聯，在此基礎上建立一個數據的抽象模型。資料庫邏輯設計的主要工作是將E-R圖轉換為指定的RDBMS中的關系模型。
(61)字元(char)型數據在微機內存中的存儲形式是________。
A)反碼 B)補碼
C)EBCDIC碼 D)ASCII碼
(61)D
知識點：字元數據在內存中的存儲形式
評析：將一個字元常量放到一個字元變數中，實際上並不是把該字元本身放到內存單元中去，而是將該字元的ASCII碼值放到存儲單元中。
71)演算法的空間復雜度是指_______。
A)演算法程序的長度 B)演算法程序中的指令條數
C)演算法程序所佔的存儲空間 D)演算法執行過程中所需要的存儲空間
(71)D
知識點：演算法的復雜度
評析：一個演算法的空間復雜度，一般是指執行這個演算法所需的內存空間。
一個演算法所佔用的存儲空間包括演算法程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。
(72)下列關於棧的敘述中正確的是_______。
A)在棧中只能插入數據 B)在棧中只能刪除數據
C)棧是先進先出的線性表 D)棧是先進後出的線性表
(72)D
知識點：棧的輸入輸出操作
評析：棧是限定在一端進行插入與刪除的線性表。
棧是按照「先進後出」的或「後進先出」的原則組織數據的，因此，棧也被稱為「先進後出」表或「後進先出」表。
(73)在深度為5的滿二叉樹中，葉子結點的個數為_______。
A)32 B)31 C)16 D)15
(73)C
知識點：二叉樹的概念
評析：所謂滿二叉樹是指除最後一層外，每層上的所有結點都有兩個子結點。也就是說，在滿二又樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第K層上有2k-1個結點，且深度為m的滿二叉樹有2m個結點。
在滿二叉樹中，最後一層的結點個數就是葉子結點的個數，本題中深度為5，故葉子結點數為25-1=24==16。
(74)對建立良好的程序設計風格，下面描述正確的是_______。
A)程序應簡單、清晰、可讀性好 B)符號名的命名要符合語法
C)充分考慮程序的執行效率 D)程序的注釋可有可無
(74)A
知識點：程序設計風格
評析：要形成良好的程序設計風格，主要應注重和考慮下述一些因素：符號名的命名應具有一定的實際含義，以便於對程序功能的理解；正確的注釋能夠幫助讀者理解程序；程序編寫應優先考慮清晰性，除非對效率有特殊要求，程序編寫要做到清晰第一，效率第二。
(75)下面對對象概念描述錯誤的是_______。
A)任何對象都必須有繼承性 B)對象是屬性和方法的封裝體
C)對象問的通訊靠消息傳遞 D)操作是對象的動態性屬性
(75)A
知識點：對象的概念
評析：對象是由數據和容許的操作組成的封裝體，與客觀實體有直接的對應關系。對象之間通過傳遞消息互相聯系，以模擬現實世界中不同事物彼此之間的聯系。
(76)下面不屬於軟體工程的3個要素的是_______。
A)工具 B)過程 C)方法 D)環境
(76)D
知識點：軟體：[程的要素
評析：軟體工程包括3個要素，即方法、工具和過程。
(77)程序流程圖(PFD)中的箭頭代表的是_______。
A)數據流 B)控制流 C)調用關系 D)組成關系
(77)B
知識點：軟體設計工具
評析：程序流程圖(PFD)是一種傳統的、應用廣泛的軟體過程設計表示工具，通常也稱為程序框圖，其箭頭代表的是控制流。
(78)在數據管理技術的發展過程中，經歷了人工管理階段、文件系統階段和資料庫系統階段。其中數據獨立性最高的階段是_______。
A)資料庫系統 B)文件系統 C)人工管理 D)數據項管理
(78)A
知識點：數據管理技術的發展
評析：在數據管理技術的發展過程中，經歷了人工管理階段、文件系統階段和資料庫系統階段。其中數據獨立性最高的階段是資料庫系統。
❸ 數據結構與演算法-基礎（十八）哈希表
上期使用 紅黑樹 實現映射結構，這樣的結構滿足 Key 必須具備可比性，元素有順序地分布 這兩個特點。在實際的應用場景中，存在結構中的 元素是不需要有序的，並且 Key 也不具備可比較性 ，哈希表完全滿足這樣的應用場景。
比如設計一個公司的通訊錄，存放所有員工的通訊信息，就可以拿手機號作為 index，員工的名稱、職位等作為 value。用哈希表的方式可以將添加、刪除和搜索的時間復雜度控制在 O(1)。
這時創建一個數組，手機號作為 index，然後存放 value。這樣能將復雜度控制在 O(1)，但是這種 空間換時間 的方式也造成了一些其他問題，比如空間復雜度大（需要更多的空間），空間使用率極其低，非常浪費內存空間。
哈希表 就是空間換時間的處理方式，但是做了優化，在空間和時間兩個緯度中達到適當的平衡。
哈希表也叫做散列表，整體結構就是一個數組 ，哈希表會將 key 用哈希函數處理之後返回 hash（哈希值），hash 就是哈希表中的 index這樣的處理方式就可以滿足搜索時間是 O(1)，這樣的處理方式就可以滿足搜索時間是 O(1)。因為哈希表中的 key 可能不具備可比較性，所以要做哈希處理。
在執行哈希函數之後返回的 hash，可能會出現相同的情況 ，這樣的情況就是 哈希沖突 。解決哈希沖突常見的方法有這三種：
JDK1.8 解決哈希沖突的方式就是使用鏈地址法，其中的鏈表就是通過鏈表+紅黑樹的組合來實現 。比如當哈希表中的容量大於等於 64，並且單向鏈表的節點數大於 8 時，轉換為紅黑樹，不滿足這個條件時就使用單向鏈表。
哈希函數 是生成哈希值的實現方法，哈希函數的實現步驟大致分為兩步：
hash_code 是生成哈希值的函數，也可以直接用 JAVA 中的標准函數 hashCode() 。
這里可以用 & 位運算替換 % 運算，來提高效率。因為 & 位運算是二進制運算，所以在設計數組的時候，需要將數組的長度設計為 2 的冪次方。
一個良好的哈希函數，可以讓生成的哈希值分布更加均勻，減少哈希沖突的次數，最終可以提升哈希表的性能。
Key 的常見類型可能有證書、浮點數、字元串或者自定義對象，不同的類型生成哈希值的方式也會不一樣，但是目標是一致的，就是 盡量讓每個 Key 的哈希值唯一，盡量讓 Key 中的所有信息參與運算 。
比如在 Java 中， Long 的哈希值實現如下代碼：
這里的 >>> 和 ^ 就是將高 32 bit 和低 32 bit 混合計算出 32 bit 的哈希值。
在計算字元串的哈希值時，可以將字元串拆解成若干個字元，比如 jack，將它拆解成 j、a、c、k（字元的本質就是一個整數，所以 jack 的哈希值可以表示為 j * n3 + a * n2 + c * n1 + k * n0，表達式也可以寫成 [(j * n + a) * n + c] * n + k，代碼實現如下：
看上面代碼時，可以發現，表達式中的 n 使用的是 31 這個數字，那麼為什麼用 31 呢？
因為 31 不僅符合 22 - 1 , 而且它還是個奇素數（既是技術，又是素數，還是質數），素數和其他數相乘的結果比其他方式更容易產生唯一性，減少哈希沖突。
JDK 中，乘數 n 也是用 31，31 也是經過觀測分布結果後的選擇，關於 31 的變體可以有以下幾種：
31 * i = (25 - 1) * i = i * 25 - i = (i << 5) - i