公共基礎知識算法與數據結構程序設計基礎軟件工程數據庫基礎1．算法的概念、算法時間復雜度及空間復雜度的概念2．數據結構的定義、數據邏輯結構及物理結構的定義3．棧的定義及其運算、線性鏈表的存儲方式4．樹與二叉樹的概念、二叉樹的基本性質、完全二叉樹的概念、二叉樹的遍歷5．查找6．排序第一章算法與數據結構一、算法的基本概念

1、算法：解題方案的準確而完整的描述，包括解決問題的方法和步驟

。

算法≠程序≠計算方法

2、算法的基本特征：⑴可行性：算法中描述的操作都是可以通過已經實現的基本運算的有限次數來實現

⑵確定性：算法的每個步驟必須明確定義，不允許有多義性。⑶有窮性：指算法必須能在有限的時間內做完(即算法的運行時間有限)。⑷擁有足夠的情報：指運算對象的初始輸入要完備且正確1.1算法二、算法復雜度1、時間復雜度：執行算法所需要的計算工作量2、空間復雜度：執行算法所需要的內存空間（存儲空間）。注意：1）時間復雜度通過算法所執行的基本運算次數來度量

2）空間復雜度的內存空間主要用于：內存空間算法程序初始數據運行過程中所需的額外空間執行過程的工作單元附加空間3）時間復雜度和空間復雜度不相關4）算法的效率與問題的規模和數據的存儲結構都是息息相關的。算法習題(1)算法是指（）A.查詢方法B.交工方法C.解題方案的準確而完整的描述D.排序方法(2)算法的有窮性是指：A.算法程序的運行時間是有限的B.算法程序所處理的數據量是有限的C.算法程序的長度是有限的D.算法程序只能被有限的用戶使用(3)算法的時間復雜度是指（）A.算法的執行時間

B.算法所處理的數據量C.算法程序中的語句或指令數

D.算法在執行過程中所需要的基本運算次數(4)下列敘述中正確的是（）A.一個算法的空間復雜度大，則其時間復雜度也必定大B.一個算法的空間復雜度大，則其時間復雜度也必定小C.一個算法的時間復雜度大，則其空間復雜度也必定大D.上述三種說法都不對1.2數據結構一、數據結構的基本概念1、數據結構：是抽象地研究數據的組織形式及其相互關系的一門學科。

數據的結構分為：

（1）物理結構：也被稱為“存儲結構”，是指數據在計算機存儲介質中真正存儲的結構。

（2）邏輯結構：反映數據元素之間邏輯關系的數據結構2、數據結構研究的主要內容：邏輯結構、物理結構（即存儲結構）和算法。注意：邏輯結構和物理結構沒有必然的聯系，也不一定是一一對應的。二、數據的邏輯結構：

反映數據元素之間邏輯關系的數據結構。1、線性結構：⑴有且僅有一個根結點⑵每個結點最多只有一個前件，也最多只有一個后件。例如：主要有線性表、棧、隊列、串等。

前后件關系2、非線性結構：該結構中一個結點可能有多個前件或后件。主要有樹和圖等。FCEGDABPH三、數據的存儲結構指數據的邏輯結構在計算機存儲空間中的存放形式（邏輯結構在計算機中的表示）1、順序存儲：邏輯上相鄰的數據元素，在物理存儲位置上也相鄰。2、鏈式存儲：邏輯上相鄰的元素其物理位置不一定相鄰，元素間的邏輯關系由附加的指針字段表示。注意：1）一種邏輯結構可以表示成多種存儲結構

2）存儲結構影響數據處理的效率例題：下列敘述中正確的是：A、程序執行效率與數據的存儲結構密切相關B、程序執行效率只取決于程序的控制結構C、程序執行效率只取決于所處理的數據量D、以上三種說法都不對1.3、線性表1、線性表的定義線性表是n（n≥0）個數據元素a1，a2，……，an

的有序集合。線性表是一種線性結構，每個元素在表中的位置僅取決于元素本身的序號。n為線性表的長度，n為0的表稱為空表。學號姓名語文數學計算機980001張三708069980002吳軍897698980003王平878776980004李帆768689無后件無前件a1a2a3…aiai+1…an…特點：⑴線性表中所有元素所占的存儲空間是連續的⑵線性表中各數據元素在存儲空間中是按照邏輯順序依次存放的⑶可以隨機訪問

缺點：插入和刪除運算不方便；由于要求占用連續的存儲空間，存儲分配只能預先進行2、線性表的存儲結構（1）線性表的順序存儲結構：當線性表采用順序存儲結構時，稱之為順序表。即用一組地址連續的存儲單元依次存放線性表的數據元素。在程序設計語言中，通常定義一個一維數組來表示線性表的順序存儲空間。⑴順序表的插入：要在第i(1≤i≤n)個元素之前插入一個新元素時，需要移動n-i+1個元素⑵順序表的刪除：要刪除第i(1≤i≤n)個元素時，需要移動n-i個元素真題：下列有關順序存儲結構的敘述中，不正確的是：

A、存儲密度大

B、邏輯上相鄰的結點物理上不必鄰接

C、可以通過計算機直接確定第i個結點的存儲地址

D、插入、刪除操作不方便

用一組任意的存儲單元（可以是連續的，也可以不連續）來存儲線性表的各個數據元素。數據元素（稱為結點）的存儲結構由兩部分組成：一部分用于存儲數據元素本身的信息（稱為數據域），另一部分用于存儲直接后繼的存儲位置（稱為指針域）,如下圖所示：3、線性表的鏈式存儲結構特點：①元素的存儲空間可以連續，也可以不連續②元素的邏輯關系通過鏈結點的指針反映。③順序訪問

ABC…

…NULLhead注：分單向、雙向和循環鏈表ABC…

…headABC…

…NULLhead循環鏈表：循環鏈表是另一種形式的鏈式存儲結構。它的特點是表中最后一個結點的指針域指向頭結點。雙向鏈表特點：在雙向鏈表的結點中有兩個指針域，其一指向前件，另一指向后件。真題：1、下列敘述中正確的是：

A、線性表的鏈式存儲結構與順序存儲結構所需存儲空間相同

B、線性表的鏈式存儲結構所需存儲空間一般多于順序存儲結構

C、線性表的鏈式存儲結構所需存儲空間一般少于順序存儲結構

D、以上三種說法都不對2、下列敘述中正確的是：A、有一個以上根結點的數據結構不一定是非線性結構B、只有一個根結點的數據結構不一定是線性結構C、循環鏈表是非線性結構D、雙向鏈表是非線性結構3、在一個長度為n的順序表中，在第i個元素的位置插入一個新元素，需要向后移動

個元素。4、在長度為n的順序表中插入一個元素，最壞情況下要移動表中

個元素。5、下列敘述中正確的是A)結點中有多個指針域的所有鏈表一定是非線性結構B)帶鏈的棧與隊列是線性結構C)能順序存儲的數據結構一定是線性結構D)存儲空間不連續的所有鏈表一定是非線性結構1.4棧與隊列1、棧的定義棧是一種特殊的線性表，是限定在一端進行插入和刪除運算的線性表。允許插入與刪除的一端稱為棧頂（top)，另一端稱為棧底(bottom）。

2、特點最先進入棧的元素一定在棧底，最后進入棧的元素一定在棧頂。所以堆棧又稱為“后進先出”表或“先進后出”表提示：程序設計語言中的遞歸調用采用的“棧”這種數據結構同樣有順序和鏈式兩種。（1）、入棧PUSH（S，X）

棧頂指針TOP加1，插入新元素X；若堆棧已滿，再做入棧運算時會產生溢出（通常稱為上溢）。（2）、出棧POP（S）取出棧頂元素賦給變量、棧頂指針TOP減1；若堆棧為空，再做出棧運算時會產生溢出（通常稱為下溢）。

（3）、讀棧頂元素GETTOP（S）將棧頂元素賦給變量但不改變TOP指針。3、存儲結構及運算真題：1、下列關于棧敘述正確的是A)棧頂元素最先能被刪除 B)棧頂元素最后才能被刪除C)棧底元素永遠不能被刪除 D)以上三種說法都不對2、下列敘述中正確的是A)在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態變化B)在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態變化C)在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態變化D)上述三種說法都不對3、假設用一個長度為50的數組(數組元素的下標從0～49)作為棧的存儲空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom＝49，top＝30(數組下標)，則棧中具有__

__個元素。4、若進棧序列為1，2，3，4，且進棧過程中可以出棧，則不可能的出棧序列是（A）1，4，3，2（B）2，3，4，1

（C）3，1，4，2（D）3，4，2，15、在程序設計語言中的遞歸調用的存儲分配通常用（）A)棧B)堆C)數組D)鏈表隊列1、定義是一種只允許在表的一端進行插入操作而在另一端進行刪除操作的線性表。2、特點允許插入的一端稱為隊尾（rear),允許刪除的一端稱為隊頭(front)。新來的元素總是加入到隊尾，每次離隊的總是對頭的元素。因此，也將隊列稱為“先進先出”FIFO（FirstInFirstOut）3、存儲結構同樣有順序存儲結構和鏈式存儲結構。4、基本運算①入隊:插入運算稱為入隊，rear=rear+1,rear指示了實際的隊尾位置②出隊:刪除運算稱為出隊,front=front+1，front指示的是對頭的前一個位置假溢出(a)圖是空隊列，表示該隊列最大長度maxnum=6(d）圖中rear=maxnum，如果這時有J7要入隊，則會產生假溢出5、循環隊列(順序存儲)注意：rear=front則表示可能隊滿，也可能隊空循環隊列的基本運算①入隊：插入運算稱為，rear=rear+1；當rear=m+1時(m為隊列的總容量)，則重置rear=1。②出隊：刪除運算稱為出隊，front=front+1；當front=m+1時(m為隊列的總容量)，則重置front=1。1、一個隊列的入隊序列是1、2、3、4，則隊列的輸出序列是

A)4321B)1234

C)1432D)3

2

4

1

2、在一個容量為24的循環隊列中，若頭指針front=8，尾指針rear=3，則該循環隊列中共有__________個元素3、對于循環隊列，下列敘述中正確的是A)隊頭指針是固定不變的B)隊頭指針一定大于隊尾指針C)隊頭指針一定小于隊尾指針D)隊頭指針可以大于隊尾指針，也可以小于隊尾指針4、在一個容量為24的循環隊列中，經過一系列入隊和出隊運算，若頭指針front=8，尾指針rear=8，則該循環隊列中共有__________個元素重要考點：已知循環隊列容量m，隊頭指針front和隊尾指針rear，求隊列元素個數n①當front<rear時：n=rear-front②當front>rear時：n=m+(rear-front)1、樹的基本概念⑴定義

樹是n（n≥0）個結點（數據元素）的有窮集合，是一種非線性結構。N=0時稱為空樹。⑵特點①有且僅有一個結點沒有前驅結點，即樹的根結點。②除根結點以外，其余所有結點有且僅有一個直接前驅。③包括根結點在內，每個結點可以有多個后繼結點⑶基本概念①結點的度：一個結點的子樹數目稱為該結點的度②樹的度：結點中最大的度即為樹的度。③樹的深度：樹的最大層次。④葉子結點：沒有子數，該結點的度為0.FCEGDABPH1.5樹與二叉樹2、二叉樹⑴特點只有一個根結點，每個結點最多有左、右兩棵子樹組成。若集合為空，則為空二叉樹。二叉樹的結點有三種：度為0的葉子結點、度為1的結點和度為2的結點⑵基本性質①二叉樹的第K層上最多有2k-1個結點。②深度為m的二叉樹最多有2m-1個結點。③任意二叉樹中，度為0的結點（葉子結點）總是比度為2的結點多1個。或者表述為：二叉樹中度為2的結點有n個，則該二叉樹中有n+1個葉子結點。④具有n個結點的二叉樹，深度至少為[log2n]+1ABCFEDJn0=n2+1二叉樹中結點總數：n0+n1+n23、滿二叉樹與完全二叉樹⑴滿二叉樹：除最后一層外，每一層上的所有結點都有兩個子結點，即每一層上的結點數都達到最大值。⑵完全二叉樹：除最后一層外，每一層上的結點數都達到最大值；在最后一層上只缺少右邊的若干結點。

(a)深度為3的滿二叉樹(b)深度為3的完全二叉樹的幾種形態說明：滿二叉樹一定是完全二叉樹，完全二叉樹未必是滿二叉樹。前（根）序遍歷：訪問根結點——左子樹——右子樹

ABDEHJCFG中（根）序遍歷：左子樹——訪問根結點——右子樹

DBHEJAFCG后（根）序遍歷：左子樹——右子樹——訪問根結點

DHJEBFGCAABCFEGDHJ(3)二叉樹的存儲結構：鏈式存儲(4)二叉樹的操作：遍歷真題：1、一棵二叉樹的中序遍歷結果為DBEAFC，前序遍歷結果為ABDECF，則后序遍歷結果為

。2、

①

有下列二叉樹，對此二叉樹中序遍歷的結果為（）

A）BDYEACFXZB）DYBEAFCZXC）ABCDEFXYZD）ABDYECFXZ

②某二叉樹共有60個葉子結點與50個度為1的結點，則該二叉樹中的總結點數為（）。

A）148B）169C）182D）198

③在深度為5的滿二叉樹中，葉子結點的個數為

A)32B)31C)16D)15④某二叉樹共有7個結點，其中葉子結點只有1個，則該二叉樹的深度為()(假設根結點在第1層)

A)3 B)4 C)6 D)7n0=60推出n2=n0-1=59共有:n0+n1+n2=60+50+59=16925-11.6查找1、順序查找（1）基本思想：從第一個數據元素開始，逐個把數據元素的關鍵字值和給定值比較，若某個元素的關鍵字值和給定值相等，則查找成功；否則，若全部比較完都不等，則查找失敗。（2）在下列兩種情況下只能采用順序查找：①如果線性表為無序表，則不管是順序存儲結構還是鏈式存儲結構，只能用順序查找。②即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。2、二分查找前提：順序存儲的有序表。基本思想：待查元素與表的“中間位置”元素的關鍵值進行比較，若大于關鍵字，則在查找表的后半部分繼續二分查找，否則在前半部分進行二分查找。在最壞情況下，順序查找需要比較n次，二分查找需要比較log2n次。

排序冒泡排序快速排序簡單插入排序希爾排序簡單選擇排序堆排序最壞情況下比較次數O(nlog2n)次n(n-1)/2次O(n1.5)次1.7排序下列排序方法中，最壞情況下比較次數最少的是

A)

冒泡排序

B)

簡單選擇排序

C)

直接插入排序

D)

堆排序1、交換類排序①冒泡排序基本思想：⑴首先，從前往后掃描線性表,逐次比較相鄰兩個元素的大小,若前者大于后者，則兩兩交換位置，最后將最大的元素放到了表的末尾；⑵然后，從后往前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若后面的元素小于前面的元素，則將它們互換，最后將最小者放到表的最前面。⑶再對剩余元素進行第二趟比較…，直到n個元素按遞增順序排列好為止。其特點是：第一趟排序后，最小元素被交換到第一位，最大元素被交換到最后一位。②快速排序基本思想：從序列中選取一個元素，設為T，將序列中小于T的元素移到T前面，大于T的元素移到T后面，T插入到序列分界線的位置，這個過程叫分割。然后對分割的兩部分做再次分割，直至使序列變成有序的。2、插入類排序①簡單插入排序基本思想：把n個數據元素的序列分成兩部分，{R1，…，Ri-1}為已排好序的有序部分，{Ri,Ri+1,….,Rn}為未排序部分，這時，把未排序部分的元素逐個插入到有序部分的合適位置上。②希爾排序基本思想：把整個無序序列按某個增量H分割成若干小的子序列分別進行插入排序，在排序過程中逐次縮小這個增量，直至H為13、選擇類排序(1)簡單選擇排序基本思想：第一趟排序是在無序的{R1，…，Rn}中按排序碼選出最小的元素，將它與R1交換；第二趟排序是在無序的{R2，…，Rn}中按排序碼選出最小的元素，將它與R2交換，…，最終得到遞增有序的序列。89215648851619471621564885891947第1遍第2遍1619564885892147第3遍1619214885895647其特點是：第一趟排序后，最小元素被交換到第一位。(2)堆排序第二章程序設計基礎1．結構化程序設計方法的四個原則2．對象、類、消息、繼承的概念、類與實例的區別程序設計的方法與風格

一、程序設計方法與風格1、符號名的命名應具有一定含義2、必要的程序注釋：分為序言性注釋和功能性注釋(可讀性)

3、程序編寫清晰第一、效率第二（易讀性）4、避免不必要的語句轉移5、程序設計要采用模塊化二、結構化程序設計1、設計原則①自頂向下②逐步求精③模塊化④限制使用GOTO語句最關鍵的是“以提高程序清晰性為目標”

2、程序基本結構①順序結構②選擇結構③循環結構三、面向對象的程序設計1、對象⑴定義：對象是由數據和允許的操作組成的封裝體，可以用來表示客觀世界中的任何實體。⑵屬性：對象所包含的信息（靜態）⑶方法：即對象的操作，描述了對象執行的功能（動態）⑷特征：⑴標識唯一性：對象是可以區分的。⑵分類性：可以將具有相同屬性和操作的對象抽象成類。⑶多態性：同一個操作可以是不同對象的行為。⑷封裝性：實現信息屏蔽。⑸模塊獨立性：內聚性強、耦合度弱。2、類類是具有共同屬性、共同方法的對象的集合、對象是類的實例。可以由基類（父類）產生子類，子類可以繼承其父類的全部方法和屬性。3、消息對象間相互合作的機制稱為消息，對象間通過傳遞消息相互聯系4、繼承繼承是一種類之間共享屬性和操作的機制。子類可以繼承其父類的全部方法和屬性，繼承具有傳遞性5、多態性同樣的消息被不同的對象接受時可導致完全不同的行為真題：1、下列不屬于結構化程序設計原則的是()A）可封裝B）自頂向下C）模塊化D）逐步求精2、結構化程序所要求的基本結構不包括（）A）順序結構B）GOTO跳轉C）選擇結構D）循環結構3、面向對象方法中，繼承是指（）A）一組對象所具有的相似性質B）一個對象具有另一個對象的性質C）各對象之間的共同性質D）類之間共享屬性和操作的機制4、在面向對象方法中，實現信息隱蔽是依靠（）A）對象的繼承B）對象的多態C）對象的封裝D）對象的分類5、以下不屬于對象的基本特點的是（）A)分類性B)多態性C)一致性D)封裝性6、對象實現了數據和操作的結合，是指對數據和數據的操作進行（）A)結合B)隱藏C)封裝D)抽象7、在面向對象方法中，一個對象請求另一個對象為其服務的方式是通過發送（）A)調用語句B)命令C)口令D）消息第三章軟件工程基礎一、軟件的定義1、軟件：包括程序、數據和相關文檔的完整集合。2、軟件按功能劃分：應用軟件、系統軟件與支撐軟件（或工具軟件）。應用軟件：QQ、Office(word、excel等）、Wps系統軟件：Windows、OS/2、Linux、Unix二、軟件危機與軟件工程1、軟件危機⑴概念：出現于20世紀60年代末，泛指在計算機軟件的開發和維護過程中所遇到的一系列嚴重問題。⑵軟件危機的主要表現：①用戶對交付使用的軟件系統不滿意。②軟件開發成本和進度無法控制。③軟件的質量無法保證。④現有軟件維護困難。⑤軟件的成本不斷提高。⑥軟件開發的速度跟不上硬件的發展和應用需求的增長。總的來說，歸結為成本、質量、生產率等問題。下面描述中，不屬于軟件危機表現的是A)

軟件過程不規范B)

軟件開發生產率低C)

軟件質量難以控制

D)

軟件成本不斷提高2、軟件工程為了擺脫軟件危機，提出了軟件工程的概念。所謂軟件工程，是指采用工程的概念、原理、技術和方法指導軟件的開發與維護。軟件工程學是研究軟件開發和維護的普遍原理與技術的一門工程學科。⑴軟件工程三要素①方法：是完成軟件工程項目的技術手段②工具：支持軟件的開發、管理、文檔生成③過程：支持軟件開發的各個環節的控制、管理⑵軟件工程核心思想：把軟件產品看作是一個工程產品來處理。(3)、軟件工程研究的內容與原則軟件工程研究的主要內容：軟件開發技術和軟件工程管理軟件工程的原則：抽象、信息屏蔽、模塊化等(4)軟件開發環境軟件開發環境是全面支持軟件開發全過程的軟件工具集合。三、軟件生命周期是指軟件產品從提出、實現、使用維護到停止使用退役的全過程。劃分為如下三個階段：①軟件定義②軟件開發③軟件維護3、軟件生命周期各階段的主要任務是：階段任務描述軟件定義階段可行性研究與計劃制定確定開發目標，制定實施計劃。需求分析對待開發軟件提出需求進行分析，確定軟件系統的功能需求并給出詳細定義。編寫軟件規格說明書及初步的用戶手冊，提交評審。需求分析的成果：需求規格說明書軟件開發階段軟件設計分為概要設計和詳細設計兩個階段，給出軟件的結構、模塊的劃分、功能的分配以及處理流程。這階段提交評審的文檔有概要設計說明書、詳細設計說明書和測試計劃初稿。軟件實現在軟件設計的基礎上編寫程序。軟件測試在設計測試用例的基礎上，檢驗軟件的各個組成部分。編寫測試分析報告。軟件維護運行維護將已交付的軟件投入運行，同時不斷的維護，進行必要而且可行的擴充和刪改。結構化分析方法（軟件定義階段）一、需求分析1、需求分析的成果：需求規格說明書2、需求分析方法⑴結構化分析方法①面向數據流的結構化分析方法SA②面向數據結構的Jackson方法（JSD）③面向數據結構的結構化數據系統開發方法DSSD⑵面向對象的分析方法：OOA二、結構化分析方法

1、分析手段：分解和抽象2、分析工具⑴數據流圖DFD（注意主要圖形元素說明）

加工（轉換）：輸入數據經加工變換輸出。數據流：沿箭頭放心傳送數據的通道。存儲文件（數據源）：表示處理過程中存放各種數據的文件。源，潭：表示系統和環境的接口。⑵數據字典DD：作用是對DFD中出現的被命名的圖形元素的確切解釋，（

數據字典（DD)

所定義的對象都包含于數據流圖中）是結構化分析的核心。⑶判定樹⑷判定表三、軟件需求規格說明書軟件需求規格說明書是需求分析階段的最后成果。軟件需求規格說明書的作用包括

：A)

軟件驗收的依據

B)

用戶與開發人員對軟件要做什么的共同理解C)

軟件設計的依據

結構化設計方法

（開發階段）一、軟件設計的基本概念1、軟件設計：把軟件需求轉換為軟件表示的過程，分概要設計和詳細設計兩步完成。2、設計原則⑴抽象：把事物本質的共同特性提取出來而不考慮其他細節。⑵模塊化：模塊是指把一個待開發的軟件分解成若干小的簡單的部分。模塊化是指解決一個復雜問題時自頂向下逐層把軟件系統劃分成若干模塊的過程。⑶信息隱蔽：信息隱蔽是指在一個模塊內包含的信息（過程或數據），對于不需要這些信息的其他模塊來說是不能訪問的。⑷模塊獨立性：模塊獨立性是指每個模塊只完成系統要求的獨立的子功能，并且與其他模塊的聯系最少且接口簡單。劃分模塊的原則要盡量做到“高內聚，低耦合”。二、總體設計（概要設計）：1、基本任務⑴設計軟件系統結構⑵數據結構及數據庫設計⑶編寫概要設計文檔⑷概要設計文檔評審2、設計工具：結構圖SC(StructureChart)3、面向數據流的設計方法典型的數據流類型：變換型和事務型扇入：是指直接調用該模塊的上級模塊的個數。扇入大表示模塊的復用程序高。扇出：是指該模塊直接調用的下級模塊的個數一個模塊的扇入是指有多少個上級模塊調用它。扇人越大，表示該模塊被更多的上級模塊共享。這當然是我們所希望的。但是不能為了獲得高扇人而不惜代價，例如把彼此無關的功能湊在一起構成一個模塊，雖然扇人數高了，但這樣的模塊內聚程度必然低。這是我們應避免的。設計得好的系統，上層模塊有較高的扇出，下層模塊有較高的扇人。其結構圖像清真寺的塔，上面尖，中間寬，下面小。例題：某系統結構圖如下圖所示，該系統結構圖的最大扇出數是（）A)4B)1C)3D)n某系統結構圖如下圖所示

，該系統結構圖的最大扇入數：A）n

B）

1

C）

2

D）3

某系統結構圖如下圖所示，該系統結構圖中最大扇入是

A）0

B）1

C）2

D）3

三、詳細設計：1、基本任務：為每個模塊確定算法和局部數據結構2、設計工具⑴圖形工具：①程序流程圖：構成程序流程圖的基本圖符及含義：→或↓表示控制流；□表示加工步驟；

表示邏輯條件。

②N-S圖：③PAD圖：④HIPO⑵表格工具：判定表⑶語言工具：PDL(偽碼），是一種混合語言，采用英語的詞匯和結構化程序設計語言的語法，類似編程語言。軟件工程階段用到的方法用到的工具生成的文檔需求分析結構化分析SA數據流圖DFD數據字典DD判定表判定樹軟件需求規格說明書概要設計結構化設計SD軟件結構圖SC概要設計說明書數據庫設計說明書集成測試計劃詳細設計結構化編程SP程序流程圖N-S圖問題分析圖PAD偽碼PDL軟件測試一、定義：軟件測試是為了發現錯誤而執行程序的過程。軟件測試是保證軟件質量的重要手段。

二、目標：測試是為了發現軟件中的錯誤而運行軟件的過程好的測試方案是盡可能地發現至今尚未發現的錯誤的測試方案成功的測試則是發現出了至今尚未發現的錯誤的測試。軟件測試的目的是A)

評估軟件可靠性

B)

發現并改正程序中的錯誤C)

改正程序中的錯誤

D)

發現程序中的錯誤三、原則：不要抱有“軟件不會有錯或認為查不出錯的“幻想”設計測試用例時，應同時確定輸出結果設計測試用例時，應包括合理的數據和不合理的數據軟件設計者應當避免測試自己的程序嚴格全面地執行測試計劃妥善保存測試計劃、測試用例、出錯統計和最終分析報告四、軟件測試技術與方法按照是否需要執行軟件劃分：靜態測試、動態測試。按照功能劃分：白盒測試、黑盒測試1、靜態測試與動態測試⑴靜態測試：由人工或借助工具對軟件進行閱讀和檢查。靜態測試包括代碼檢查、靜態結構分析、代碼質量度量等。⑵動態測試：是基于計算機的測試，是為了發現錯誤而執行程序的過程。動態測試的關鍵是設計高效、合理的測試用例。2、白盒測試與黑盒測試⑴白盒測試：又稱為結構測試或邏輯測試。利用程序內部的邏輯結構和特性來設計測試用例，檢查程序中的邏輯通路是否都按預定的要求正確地工作。測試的基本原則：保證每一條獨立路徑至少執行一次。測試的主要方法包括邏輯覆蓋、基本路徑測試⑵黑盒測試：又稱功能測試或數據驅動測試，是對軟件的功能進行測試和驗證。黑盒測試不考慮程序內部的邏輯結構和特性，只根據程序的需求和功能設計測試用例。測試的常用方法有等價分類法、邊界值分析法、錯誤推測法和因果圖。使用白盒測試方法時，設計測試用例應根據

A）程序的內部邏輯B）程序的復雜結構C）程序的功能

D）使用說明書五、軟件測試的實施軟件測試過程一般按4個步驟進行，即單元測試、集成測試、驗收測試（確認測試）和系統測試。1、單元測試：對模塊進行測試，目的是發現模塊內部可能存在的錯誤。2、集成測試：測試和組裝軟件，目的是發現和接口有關的錯誤。3、確認測試：驗證軟件的功能和性能是否符合需求。4、系統測試：將通過測試的軟件與硬件、外設、支撐軟件、數據和人員等其他系統元素組合在一起進行測試。

下面不屬于軟件測試實施步驟的是

A)

集成測試

B)

回歸測試

C)

確認測試

D)

單元測試程序的調試在對程序進行了成功的測試之后將進入程序調試（通常稱Debug，即排錯）。注：軟件調試與軟件測試是不同的概念，軟件調試的目的是為了改正程序中的錯誤。一、基本概念1、程序調試的任務：診斷和改正程序中的錯誤。軟件測試貫穿整個軟件生命期，調試則主要在開發階段進行。2、程序調試的步驟⑴錯誤定位⑵修改設計和代碼，以排除錯誤；⑶進行回歸測試，防止引進新的錯誤。二、軟件調試的方法調試的關鍵在于推斷程序內部的錯誤位置及原因。軟件調試可分為靜態調試和動態調試。主要的調試方法有：強行排錯法、回溯法、原因排除法1、程序測試的目的是（）A）發現程序中的錯誤

B）發現并改正程序中的錯誤C）診斷并改正程序中的錯誤

D）執行測試用例2、下面不屬于軟件開發階段任務的是（）

A）測試

B）設計

C）可行性研究D)實現3、下面可以作為軟件設計工具的是

DA）數據字典（DD）

B）甘特圖C）數據流程圖（DED圖）D）系統結構圖4、下面對軟件測試和軟件調試有關概念敘述錯誤的是A）程序調試通常也稱為Debug

B）設計正確的測試用例C）軟件測試的目的是發現錯誤和改正錯誤D）嚴格執行測試計劃，排除測試的隨意性5、下面屬于白盒測試方法的是A)

等價類劃分法B)

邊界值分析法

C)

基本路徑測試D)

錯誤推測法6、軟件設計中模塊劃分應遵循的準則是

A)

低內聚低耦合

B)

高耦合高內聚C)

高內聚低耦合7、軟件生命周期是指A)

軟件產品從提出、實現、使用維護到停止使用退役的過程B)

軟件從需求分析、設計、實現到測試完成的過程C)

軟件的開發過程

D)

軟件的運行維護過程8、下面描述中錯誤的是A)

系統總體結構圖支持軟件系統的詳細設計B)

軟件設計是將軟件需求轉換為軟件表示的過程C)

數據結構與數據庫設計是軟件設計的任務之一D)

PAD圖是軟件詳細設計的表示工具9、軟件按功能可以分為應用軟件、系統軟件和支撐軟件（或工具軟件）。下面屬于應用

軟件的是A)

學生成績管理系統

B)

C語言編譯程序C)

UNIX

操作系統

D)

數據庫管理系統10、構成計算機軟件的是A)

源代碼

B)

程序和數據C)

程序和文檔

D)

程序、數據及相關文檔11、數據流圖中帶有箭頭的線段表示的是

A)

控制流

B)

事件驅動

C)

模塊調用

D)

數據流12、在軟件開發中，需求分析階段可以使用的工具是A)

N-S圖

B)

DFD圖

C)

PAD圖

D)

程序流程圖第四章數據庫設計基礎一、數據、數據庫、數據庫管理系統1、數據(Data)：描述事物的符號記錄。2、數據庫(DB)：數據的集合。3、數據庫管理系統(DBMS)：是在操作系統支持下管理數據庫的系統軟件，是數據庫系統的核心。

⑴數據庫管理系統的功能：①數據模式定義②數據存取的物理構建③數據操縱：數據查詢、數據的刪除、數據插入、數據修改④數據的完整性、安全性定義與檢查⑤數據庫的并發控制與故障恢復⑥數據的服務⑵數據庫管理系統提供的數據語言：①數據定義語言：負責數據的模式定義與數據的物理存取構建。②數據操縱語言：負責數據的操縱，包括數據的增、刪、改和查詢。③數據控制語言：負責數據完整性、安全性的定義與檢查以及并發控制、故障恢復等。4、數據庫應用系統(DBAS)：利用數據庫系統開發的應用軟件。5、數據庫管理員(DBA):負責定義書庫內容、決定存儲結構和存取策略及安全授權等工作。6、數據庫系統(DBS)：包含硬件系統、軟件系統、數據庫、數據庫管理員和用戶。二、數據庫系統的發展1、人工管理階段：數據無法共享，冗余度大，不獨立，完全依賴于程序。2、文件系統階段：數據共享性差，獨立性也較差。3、數據庫系統階段：數據獨立性最高。三、數據庫系統的特點1、數據的集成性2、數據的高共享性和低冗余性：數據共享可以減少數據集冗余，并且避免數據的不一致性。

數據的一致性是指在系統中同一數據在不同地方出現應保持相同的值。3、數據獨立性：數據與程序獨立存放⑴物理獨立性：當數據的物理結構改變時，如存儲結構改變、存儲設備的更換、存取方式改變等都不影響數據庫的邏輯結構，應用程序不用改變。⑵邏輯獨立性：當數據的邏輯結構改變時，如修改數據模式、增加新的數據類型、改變數據間聯系等，不需要改變應用程序。4、數據統一管理與控制四、數據庫系統的內部結構體系1、三級模式⑴概念模式：是對數據庫系統中全局數據邏輯結構的描述，是全體用戶（應用）公共數據視圖。一個數據庫只有一個概念模式。⑵外模式：是數據庫用戶的數據視圖，也就是用戶所見到的數據模式，由概念模式推導而出。一個概念模式可以有若干個外模式。⑶內模式：給出了數據庫物理存儲結構與物理存取方法。內模式處于最底層，它反映了數據在計算機物理結構中的實際存儲形式，概念模式處于中間層，它反映了設計者的數據全局邏輯要求，而外模式處于最外層，它反映了用戶對數據的要求。2、兩級映射：概念模式到內模式的映射、外模式到概念模式的映射。保證了數據庫系統中的數據能夠具有較高的邏輯獨立性和物理獨立性。1、數據庫管理系統是________。A)一種編譯系統B)一種操作系統C)操作系統的一部分D)在操作系統支持下的系統軟件2、數據庫系統的核心是

系統3、在數據管理技術發展的三個階段中，數據共享最好的是________。A)數據庫系統階段B)三個階段相同C)人工管理階段D)文件系統階段4、在數據庫管理系統提供的數據定義語言、數據操縱語言和數據控制語言中，

語言負責數據的模式定義與數據的物理存取構建。5、數據庫DB、數據庫系統DBS、數據庫管理系統DBMS之間的關系是________。A)DBS包含DB和DBMSB)沒有任何關系C)DB包含DBS和DBMSD)DBMS包含DB和DBS

6、數據庫管理系統中負責數據模式定義的語言是

。7、數據獨立性是數據庫技術的重要特點之一。所謂數據獨立性是指________。A)不同的數據只能被對應的應用程序所使用B)三種說法都不對C)數據與程序獨立存放D)不同的數據被存放在不同的文件中

一、數據模型是對現實世界數據特征的抽象。是指反映客觀事物及客觀事物間聯系的數據組織的結構和形式。現實世界人的抽象認識信息世界：概念模型機器世界：具體的數據模型數據模型

1、概念數據模型：對客觀事物抽象化，實體-聯系數據模型即E-R模型2、邏輯數據模型：把概念數據邏輯化，依賴某種數據庫系統數據模型通常由數據結構、數據操作及數據約束三部分組成。層次模型、網狀模型和關系模型二、E-R模型1、實體：現實世界中客觀存在且可以相互區別的事物。2、屬性：描述實體的特征3、實體間聯系：一對一1∶1；一對多1∶m；多對多m∶n4、實體型：實體屬性的集合5、實體集：相同類型實體的集合實體集屬性聯系6、圖示法：矩形-實體集；橢圓-屬性；菱形-聯系學生1(學號、姓名、性別、出生日期、系別、籍貫)實體屬性實體集實體型學生2(學號、姓名、性別、出生日期、系別、籍貫)學生n(學號、姓名、性別、出生日期、系別、籍貫)三、數據庫管理系統所支持的數據模型分為3種：層次模型、網狀模型和關系模型。層次模型：描述數據之間的從屬層次關系。網狀模型：描述數據之間的多種從屬的網狀關系。關系模型：主要描述那種具有相關性而非從屬性的平行的數據之間按照某種序列排列的集合關系。格式為：關系名（屬性名1，屬性名2，…

，屬性名n）1、元組——記錄——行；屬性——字段——列四、關系模型：二維表結構2、域：屬性的取值范圍3、碼（鍵）：二維表中唯一標識元組的最小屬性值。一個表可能有若干鍵，它們稱為該表的候選碼（或候選鍵），從候選鍵中選取一個作為用戶使用的鍵稱為主鍵（或主碼）。如表A中的某屬性是某表B的鍵，則稱該屬性為A的外鍵（或外碼）例：1、在關系A(S，SN，D)和關系B(D，CN，NM)中，A的主關鍵字是S，B的主關鍵字是D，則稱

是關系A的外碼。2、圖書館數據庫系統中有下列模式書（書號，類別，書名，出版社，年份，作者，價格，總藏書量，現有庫存）借書卡（卡號，姓名，單位，類別）

借書記錄（卡號，書號，借期，還期）其中關系書和關系借書卡的主鍵分別為書號和卡號，關系借書記錄的主鍵為A）卡號，書號B）書號，借期C）卡號，書號，借期D）卡號，借期

二維表的性質：⑴二維表中元組個數是有限的——元組個數有限性；⑵二維表中元組均不相同——元組的唯一性；⑶二維表中元組的次序可以任意交換——元組的次序無關性；⑷二維表中元組的分量是不可分割的基本數據項——元組分量的原子性；⑸二維表中屬性名各不相同——屬性名唯一性；⑹二維表中屬性與次序無關，可任意交換——屬性的次序無關性；⑺二維表屬性的分量具有與該屬性相同的值域——分量值域的統一性。4、關系操縱：數據查詢、數據的刪除、數據插入、數據修改。5、關系中的數據約束：實體完整性約束、參照完整性約束、用戶定義的完整性約束實體完整性約束：關系中每一個元組的主碼（主鍵）屬性不能重復，并且不能取空值，關系表中至少有一個字段滿足沒有重復值（即至少有一個候選索引)參照完整性：父表關鍵字更改，子表是否作相應的變化

例題：有三個關系表R、S和T如下，其中三個關系對應的關鍵字分別為A,B和符合關鍵字（A,B）。表T的記錄項(b,q,4)違反了用戶定義的完整性約束參照完整性約束實體完整性約束AA1a1bnBB1B2fghlxynpxABCaf3bq4RST一、專門的關系模型的基本運算1、選擇()：從一個關系R中找出滿足給定條件F的元組(記錄)的操作成為選擇。記為：σF(R)關系運算2023/2/220:50選擇運算–例子關系RABCDA=B^D>5

(R)ABCD123710∧∨非與(and)或(or)有關系R如下：ABCDaa22be12cc114ee61則運算A<>B^D>=2R的結果為：空(a,a,2,2)