C語(yǔ)言公共基礎(chǔ)知識(shí)

1、第一部分公共基礎(chǔ)部分知識(shí)歸納數(shù)據(jù)結(jié)構(gòu)與算法算法-是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則算法的基本要素-一是對(duì)數(shù)據(jù)對(duì)象的 運(yùn)算和操作，二是算法的 控制結(jié)構(gòu)算法設(shè)計(jì)基本方法-列舉法、歸納法、遞推、遞歸、減半遞推算法的復(fù)雜度-包括時(shí)間復(fù)雜度和空間復(fù)雜度時(shí)間復(fù)雜度-執(zhí)行算法所需的計(jì)算工作量空間復(fù)雜度-執(zhí)行算法所需的內(nèi)存空間數(shù)據(jù)結(jié)構(gòu)-相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。如春、夏、秋、冬；18、11、35、23、16。；父親、兒子、女兒等都是數(shù)據(jù)元素。前件-數(shù)據(jù)元素之間的關(guān)系，如父親是兒子和女兒的前件后件-如兒子是父親的后件結(jié)構(gòu)-指數(shù)據(jù)元素之間的前后件關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)一是指反映數(shù)據(jù)元素之間邏輯關(guān)系，而與它們?cè)谟?jì)算機(jī)中的

2、存儲(chǔ)位置 無(wú)關(guān)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）-數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式，數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間的位置關(guān)系可能與邏輯關(guān)系不同。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)分兩類-線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)（線性表）-滿足下列兩個(gè)條件（1）有且只有一個(gè)根結(jié)點(diǎn)（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件和后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，否則為非線性結(jié)構(gòu)。線性表是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)元素之間的相對(duì)位置是線性的，其存儲(chǔ)方式為順序存儲(chǔ)的，如數(shù)組棧-是限定在一端進(jìn)行插入與刪除的線性表，一端封閉，另一端開(kāi)口，其操作原則是先進(jìn)后出，棧的運(yùn)算有入棧、退棧、讀棧頂元素隊(duì)列-是指

3、在一端進(jìn)行插入（稱為隊(duì)尾）而在另一端進(jìn)行刪除（稱為隊(duì)頭）的線性表，其操作規(guī)則是“先進(jìn)先出”，其運(yùn)算有入隊(duì)和退隊(duì)。樹(shù)-是一種簡(jiǎn)單的非線性結(jié)構(gòu)，而且是層次結(jié)構(gòu)，是倒立的大樹(shù)，有根結(jié)點(diǎn)、父結(jié) 點(diǎn)、子結(jié)點(diǎn)、葉子結(jié)點(diǎn)。根結(jié)點(diǎn)在第一層，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹(shù)的度，樹(shù)的最大層次稱為樹(shù)的深度。二叉樹(shù)-（1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)（左子樹(shù) 和右子樹(shù)），其存儲(chǔ)結(jié)構(gòu)為鏈?zhǔn)健６鏄?shù)性質(zhì)-（1）K層上最多有2（ K-1）個(gè)結(jié)點(diǎn)（2）深度為m的二叉樹(shù)最多有2m- 1個(gè)結(jié)點(diǎn)（3）度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）比度為2的結(jié)點(diǎn)多一個(gè)（4）具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)

4、，其深度至少為L(zhǎng)og2n+1 ，其中Log2n表示對(duì)Log2n取整滿二叉樹(shù)-除最后一層外，其余層的結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)完全二叉樹(shù)-除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)。滿二叉樹(shù)是完全二叉樹(shù)，而完全二叉樹(shù)不是滿二叉樹(shù)。完全二叉樹(shù)有兩個(gè)性質(zhì)：（1）具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為L(zhǎng)og2n+1（ 2） 二叉樹(shù)遍歷-不重復(fù)地訪問(wèn)各個(gè)結(jié)點(diǎn)。分為前序遍歷（DLR-根左右）、中序遍歷（LDR-左根右）和后序遍歷（LRD-左右根）查找技術(shù)-順序查找對(duì)于長(zhǎng)度為n的有序線性表，查找時(shí)需要比較n次二分法查找對(duì)于長(zhǎng)度為n的有序線性表，查找時(shí)

5、需要比較log2n次排序技術(shù)-假設(shè)線性表的長(zhǎng)度為n,則冒泡排序和簡(jiǎn)單插入排序 的比較次數(shù)（時(shí)間復(fù) 雜度）為n（n-1）/2;希爾排序的比較次數(shù)為 O（n 1.5）;簡(jiǎn)單選擇排序的比較次數(shù)為n（n- 1）/2;堆排序的比較次數(shù)為 O（nlog2n）.習(xí)題1算法的時(shí)間復(fù)雜度是指（），算法的空間復(fù)雜度是指（）；線性表、棧、隊(duì)列、線性鏈表是（線性結(jié)構(gòu)），樹(shù)是（非線性結(jié)構(gòu)）；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（）；隊(duì)列是（先進(jìn)先出），棧是（先進(jìn)后出）；下列二叉樹(shù)的遍歷結(jié)果：前序遍歷（ABDECF）、中序遍歷（DBEAFC）、后續(xù)遍歷（ DEBFCA）在深度為 5 的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（16）；設(shè)樹(shù) T 的度為

6、 4，其中度為1，2，3，4 的結(jié)點(diǎn)的個(gè)數(shù)分別為 4， 2， 1，1。則 T 中的葉子結(jié)點(diǎn)的個(gè)數(shù)為（ 8）；對(duì) 于長(zhǎng)度為 n 的有序線性表，順序查找次數(shù)為（ n） ,二分法查找次數(shù)為（ log2n ）；一棵 完全二叉樹(shù)共有 700 個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中有（ 350）個(gè)葉子結(jié)點(diǎn)；一棵二叉樹(shù)的中 序遍歷結(jié)果為 DBEAFC,前序遍歷結(jié)果為 ABDECF,則后續(xù)遍歷結(jié)果為（DEBFCA）; 冒泡排序的時(shí)間復(fù)雜度為（ n（n-1）/2 ） ;在一個(gè)容量為 15 的循環(huán)隊(duì)列中，若頭指針 front=6, 尾指針 rear=9, 則該循環(huán)隊(duì)列中共有（ 3）元素；程序設(shè)計(jì)基礎(chǔ)結(jié)構(gòu)化程序設(shè)計(jì)的三種結(jié)構(gòu) -是

7、順序、選擇和循環(huán)對(duì)象 -表示客觀世界的任何實(shí)體類- 是具有共同屬性和方法的對(duì)象的集合實(shí)例 -任何一個(gè)對(duì)象都是其對(duì)應(yīng)類的實(shí)例消息 -一個(gè)實(shí)例和另一個(gè)實(shí)例之間傳遞的信息繼承 -是指直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。例如子類繼承父類結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào) - 程序的易讀性良好的程序設(shè)計(jì)風(fēng)格是 - 程序應(yīng)簡(jiǎn)單、清晰、可讀性好在面向?qū)ο蠓椒ㄖ校粋€(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其服務(wù)的方式是通過(guò)發(fā)送（消息）來(lái) 實(shí)現(xiàn)的信息隱蔽的概念與（模塊獨(dú)立性）概念直接相關(guān)（任何對(duì)象都具有繼承性）這句話是錯(cuò)誤的注釋分為（序言性注釋）和（功能性注釋）在面向?qū)ο蠓椒ㄖ?，信息隱蔽是通過(guò)對(duì)象的（封裝性）來(lái)實(shí)現(xiàn)的 類是一個(gè)支持

8、集成的抽象數(shù)據(jù)類型，而對(duì)象是類的（實(shí)例）在面向?qū)ο蠓椒ㄖ?，類之間共享屬性和操作的機(jī)制稱為（繼承）第三章軟件工程基礎(chǔ)軟件生命周期 - 軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程。分為軟件 定義、軟件開(kāi)發(fā)、軟件運(yùn)行維護(hù)三個(gè)階段。軟件生命周期的主要活動(dòng)階段 - 可行性分析、需求分析、軟件設(shè)計(jì)、軟件實(shí)現(xiàn)、軟件 測(cè)試、運(yùn)行和維護(hù)。常見(jiàn)的需求分析方法 - （ 1）結(jié)構(gòu)化分析方法 -主要包括面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法 SA；面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法JSD；面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法 DSSD。（2）面向?qū)ο蟮姆治龇椒?OOA結(jié)構(gòu)化分析方法工具-（1）數(shù)據(jù)流圖DFD，記住DFD圖的幾

9、個(gè)符號(hào)：（ 2）數(shù)據(jù)字典 DD（ 3 ）判定樹(shù)（ 4 ）判定表程序結(jié)構(gòu)圖（SC）, N-S圖，問(wèn)題分析圖（PAD）程序流程圖（PFD）的幾個(gè)符號(hào)：軟件測(cè)試 -黑盒測(cè)試：功能測(cè)試白盒測(cè)試：內(nèi)部結(jié)構(gòu)測(cè)試,窮舉路徑測(cè)試習(xí)題 3 在軟件生命周期中,能準(zhǔn)確地判斷軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是（需求分析）軟件工程的 3 個(gè)要素（工具）,（過(guò)程）,（方法） 檢查軟件產(chǎn)品是否符合需求定義的過(guò)程稱為（確認(rèn)測(cè)試） 軟件設(shè)計(jì)原則是（抽象）、（模塊化）、（信息隱蔽） 需求分析常用的工具是（ DFD） 在結(jié)構(gòu)化方法中，軟件功能分解屬于（總體設(shè)計(jì)）階段 軟件測(cè)試的目的是（改正錯(cuò)誤） 軟件需求分析階段可分為四

10、個(gè)方面（需求獲取）、（需求分析）、（編寫需求格式說(shuō) 明）、（需求評(píng)審）軟件是（程序）、（數(shù)據(jù)）、（文檔）的集合Jakson 方法是一中面向（數(shù)據(jù)流）的結(jié)構(gòu)化方法 軟件工程研究的內(nèi)容包括（軟件開(kāi)發(fā)技術(shù)）、（軟件工程管理） 數(shù)據(jù)流圖的類型有（交換型）、（事務(wù)型） 軟件開(kāi)發(fā)環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的（軟件工具）集合第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫(kù) -DB ；數(shù)據(jù)庫(kù)管理系統(tǒng) -DBMS ；數(shù)據(jù)庫(kù)管理員 -DBA ；數(shù)據(jù)庫(kù)系統(tǒng) -DBS； 數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng) -DBAS數(shù)據(jù)模型所描述的內(nèi)容分三個(gè)部分（數(shù)據(jù)結(jié)構(gòu)）、（數(shù)據(jù)操作）、（數(shù)據(jù)約束） 邏輯數(shù)據(jù)模型分（層次模型）、（網(wǎng)狀模型）、（關(guān)系模型）、（面向?qū)ο竽Ｐ?/p>

11、）E-R模型-實(shí)體關(guān)系模型，主要由實(shí)體、屬性、聯(lián)系組成，聯(lián)系分：1對(duì)1,1對(duì)多,多對(duì)多；以二維表為基本結(jié)構(gòu)所建立的模型稱為關(guān)系模型,關(guān)系模型采用二維表來(lái)表示,簡(jiǎn)稱 表,由行和列組成,行稱為元組或記錄,列稱為字段主鍵 -唯一標(biāo)識(shí)一個(gè)記錄的字段外鍵 -一個(gè)表的字段是其他表的主鍵 在數(shù)據(jù)管理技術(shù)的發(fā)展過(guò)程中,經(jīng)歷了人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫(kù)系統(tǒng)階 段,其中數(shù)據(jù)獨(dú)立性最高的階段是（數(shù)據(jù)庫(kù)系統(tǒng)）數(shù)據(jù)庫(kù)系統(tǒng)減少了（數(shù)據(jù)冗余）；數(shù)據(jù)庫(kù)系統(tǒng)的核心是（數(shù)據(jù)庫(kù)管理系統(tǒng)） 用樹(shù)型結(jié)構(gòu)來(lái)表示實(shí)體間聯(lián)系的模型稱為（層次模型） 關(guān)系表中的每一行稱為（元組） 關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)能實(shí)現(xiàn)的專門關(guān)系運(yùn)算包括（選擇）、（投

12、影）、（連接） 在關(guān)系數(shù)據(jù)庫(kù)中，用來(lái)表示實(shí)體之間聯(lián)系的是（二維表） 數(shù)據(jù)庫(kù)設(shè)計(jì)包括兩方面的設(shè)計(jì)內(nèi)容（概念設(shè)計(jì)）、（邏輯設(shè)計(jì)） 將 E-R 圖轉(zhuǎn)換到關(guān)系模式時(shí)，實(shí)體與聯(lián)系都可以表示成（關(guān)系） 一個(gè)項(xiàng)目具有一個(gè)項(xiàng)目主管，一個(gè)項(xiàng)目主管可以管理多個(gè)項(xiàng)目，則實(shí)體“項(xiàng)目主管”與“項(xiàng)目”的聯(lián)系屬于（一對(duì)多） 數(shù)據(jù)獨(dú)立性分為邏輯獨(dú)立性和物理獨(dú)立性，當(dāng)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)改變時(shí)，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序不必修改，稱為（邏輯獨(dú)立性） 數(shù)據(jù)庫(kù)系統(tǒng)中實(shí)現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱為（數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS）關(guān)系模型的完整性規(guī)則是對(duì)關(guān)系的某種約束條件，包括實(shí)體完整性、（參照完整性） 和自定義完整性第

13、四章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)4 1 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念 數(shù)據(jù)：實(shí)際上就是描述事物的符號(hào)記錄。 數(shù)據(jù)的特點(diǎn)：有一定的結(jié)構(gòu)，有型與值之分，如整型、實(shí)型、字符型等。而數(shù)據(jù)的值 給出了符合定型的值，如整型值 15 。數(shù)據(jù)庫(kù)：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng) 用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序共享。數(shù)據(jù)庫(kù)存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)。 數(shù)據(jù)庫(kù)管理系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、 控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心。數(shù)據(jù)庫(kù)管理系統(tǒng)功能：1）數(shù)據(jù)模式定義：即為數(shù)據(jù)庫(kù)構(gòu)建其數(shù)據(jù)框架；（2）數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模

14、式的物理存取與構(gòu)建提供有效的存取方法與手 段；（3）數(shù)據(jù)操縱：為用戶使用數(shù)據(jù)庫(kù)的數(shù)據(jù)提供方便，如查詢、插入、修改、刪除等以 及簡(jiǎn)單的算術(shù)運(yùn)算及統(tǒng)計(jì)；（4）數(shù)據(jù)的完整性、安生性定義與檢查；（5）數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)；（6）數(shù)據(jù)的服務(wù)：如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測(cè)、分析等。 為完成以上六個(gè)功能，數(shù)據(jù)庫(kù)管理系統(tǒng)提供以下的數(shù)據(jù)語(yǔ)言：（1）數(shù)據(jù)定義語(yǔ)言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；（2）數(shù)據(jù)操縱語(yǔ)言：負(fù)責(zé)數(shù)據(jù)的操縱，如查詢與增、刪、改等；（3）數(shù)據(jù)控制語(yǔ)言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù) 等。數(shù)據(jù)語(yǔ)言按其使用方式具有兩種結(jié)構(gòu)形式：交互式命令（ 又稱自含型或自主

15、型語(yǔ)言 ）宿主型語(yǔ)言（一般可嵌入某些宿主語(yǔ)言中）。數(shù)據(jù)庫(kù)管理員：對(duì)數(shù)據(jù)庫(kù)進(jìn)行規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等的專業(yè)管理人員。 數(shù)據(jù)庫(kù)系統(tǒng)：由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件）、數(shù)據(jù)庫(kù)管理員（人 員）、硬件平臺(tái)（硬件）、軟件平臺(tái)（軟件）五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。 數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)：由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。文件系統(tǒng)階段：提供了簡(jiǎn)單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但是它無(wú)法提供完整的、統(tǒng) 一的、管理和數(shù)據(jù)共享的能力。層次數(shù)據(jù)庫(kù)與網(wǎng)狀數(shù)據(jù)庫(kù)系統(tǒng)階段 ：為統(tǒng)一與共享數(shù)據(jù)提供了有力支撐。 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)階段數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)：數(shù)據(jù)的集成性 、數(shù)據(jù)的高共享性與低冗余性 、數(shù)據(jù)獨(dú)立性 （物理獨(dú)立性與邏輯

16、獨(dú)立性）、數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式：1）概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視圖；（2）外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見(jiàn)到的數(shù)據(jù) 模式； （3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法。數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射：（1）概念模式到內(nèi)模式的映射；（2）外模式到概念模式的映射。4.2 數(shù)據(jù)模型數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行 為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表與操作提供一個(gè)抽象的框架。描述了數(shù)據(jù)結(jié) 構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束。E-R 模型的基本概念（1）實(shí)體：現(xiàn)實(shí)世界中的事

17、物；（2）屬性：事物的特性；（3）聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系。實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián) 系。E-R模型三個(gè)基本概念之間的聯(lián)接關(guān)系：實(shí)體是概念世界中的基本單位，屬性有屬性 域，每個(gè)實(shí)體可取屬性域內(nèi)的值。一個(gè)實(shí)體的所有屬性值叫元組。E-R模型的圖示法：（1 ）實(shí)體集表示法； （2）屬性表法； （3）聯(lián)系表示法。層次模型的基本結(jié)構(gòu)是樹(shù)形結(jié)構(gòu)，具有以下特點(diǎn)：（ 1 ）每棵樹(shù)有且僅有一個(gè)無(wú)雙親結(jié)點(diǎn)，稱為根；（2）樹(shù)中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親。從圖論上看，網(wǎng)狀模型是一個(gè)不加任何條件限制的無(wú)向圖。關(guān)系模型采用二維表來(lái)表示，簡(jiǎn)稱表，由表框架及表的元組組成。一個(gè)二維表就是一 個(gè)關(guān)系。在二

18、維表中凡能唯一標(biāo)識(shí)元組的最小屬性稱為鍵或碼。從所有侯選健中選取一個(gè)作為用戶使用的鍵稱主鍵。表 A中的某屬性是某表 B的鍵，則稱該屬性集為 A的外鍵或外 碼。關(guān)系中的數(shù)據(jù)約束： （1）實(shí)體完整性約束：約束關(guān)系的主鍵中屬性值不能為空值； （2）參照完全性約束：是關(guān)系之間的基本約束；（3）用戶定義的完整性約束：它反映了具體應(yīng)用中數(shù)據(jù)的語(yǔ)義要求。4.3 關(guān)系代數(shù) 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)之一是它建立在數(shù)據(jù)理論的基礎(chǔ)之上，有很多數(shù)據(jù)理論可以表 示關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)與關(guān)系演算。關(guān)系模型的基本運(yùn)算：（1）插入 （2）刪除 （3） 修改 （ 4）查詢（包括投影、選擇、笛卡爾積運(yùn)算）4.4

19、 數(shù)據(jù)庫(kù)設(shè)計(jì)與管理數(shù)據(jù)庫(kù)設(shè)計(jì)是數(shù)據(jù)應(yīng)用的核心。數(shù)據(jù)庫(kù)設(shè)計(jì)的兩種方法： （1）面向數(shù)據(jù)：以信息需求為主，兼顧處理需求； （2）面向過(guò)程：以處理需求為主，兼顧信息需求。數(shù)據(jù)庫(kù)的生命周期：需求分析階段、概念設(shè)計(jì)階段、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、 編碼階段、測(cè)試階段、運(yùn)行階段、進(jìn)一步修改階段。需求分析常用結(jié)構(gòu)析方法和面向?qū)ο蟮姆椒ā＝Y(jié)構(gòu)化分析（簡(jiǎn)稱SA）方法用自頂向下、逐層分解的方式分析系統(tǒng)。用數(shù)據(jù)流圖表達(dá)數(shù)據(jù)和處理過(guò)程的關(guān)系。對(duì)數(shù)據(jù)庫(kù)設(shè) 計(jì)來(lái)講，數(shù)據(jù)字典是進(jìn)行詳細(xì)的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果。數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，包括 5 個(gè)部分：數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流（可以 是數(shù)據(jù)項(xiàng)，也可以是數(shù)

20、據(jù)結(jié)構(gòu)）、數(shù)據(jù)存儲(chǔ)、處理過(guò)程。數(shù)據(jù)庫(kù)概念設(shè)計(jì)的目的是分析數(shù)據(jù)內(nèi)在語(yǔ)義關(guān)系。設(shè)計(jì)的方法有兩種（ 1 ）集中式模式設(shè)計(jì)法（適用于小型或并不復(fù)雜的單位或部門） ；（ 2 ）視圖集成設(shè)計(jì)法。設(shè)計(jì)方法： E-R 模型與視圖集成。視圖設(shè)計(jì)一般有三種設(shè)計(jì)次序：自頂向下、由底向上、由內(nèi)向外。視圖集成的幾種沖突：命名沖突、概念沖突、域沖突、約束沖突。關(guān)系視圖設(shè)計(jì)：關(guān)系視圖的設(shè)計(jì)又稱外模式設(shè)計(jì)。關(guān)系視圖的主要作用：（1）提供數(shù)據(jù)邏輯獨(dú)立性；（2）能適應(yīng)用戶對(duì)數(shù)據(jù)的不同需求；（3）有一定數(shù)據(jù)保密功能。數(shù)據(jù)庫(kù)的物理設(shè)計(jì)主要目標(biāo)是對(duì)數(shù)據(jù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以 提高數(shù)據(jù)庫(kù)訪問(wèn)速度有效利用存儲(chǔ)空間。一般

21、RDBMS 中留給用戶參與物理設(shè)計(jì)的內(nèi)容大致有索引設(shè)計(jì)、集成簇設(shè)計(jì)和分區(qū)設(shè)計(jì)。數(shù)據(jù)庫(kù)管理的內(nèi)容：（1）數(shù)據(jù)庫(kù)的建立；（2）數(shù)據(jù)庫(kù)的調(diào)整；（3）數(shù)據(jù)庫(kù)的重組；（4）數(shù)據(jù)庫(kù)安全性與完整性控制；（5）數(shù)據(jù)庫(kù)的故障恢復(fù)；（6）數(shù)據(jù)庫(kù)監(jiān)控。下面是公共基礎(chǔ)部分可以變化的題 :1 一棵二叉樹(shù) ,第 K 層上最多有 2（k-1） 個(gè)結(jié)點(diǎn) ,深度為 K 的二叉樹(shù)最多有 2k-1 個(gè)結(jié)點(diǎn) , 如 果是滿二叉樹(shù)呢 ?例如 :在深度為 5 的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（ =2（5-1）=16 ）2 一棵二叉樹(shù)共有 70 個(gè)葉子結(jié)點(diǎn)和 80 個(gè)度為 1 的結(jié)點(diǎn) , 問(wèn)這個(gè)二叉樹(shù)的總結(jié)點(diǎn)是多少 ?答:因?yàn)槎葹?0 的結(jié)

22、點(diǎn)（葉子結(jié)點(diǎn)）比度為 2 的結(jié)點(diǎn)多一個(gè) ,所以度為 2的結(jié)點(diǎn)數(shù)是 69, 所以總結(jié)點(diǎn) =70+69+80=219 個(gè)3 一棵完全二叉樹(shù)共有 700 個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中有（ 350 ）個(gè)葉子結(jié)點(diǎn)解答 :700/2=350若把 700 改為 675 呢 ?（=675/2=337.5 進(jìn)行四舍五入 =338）4設(shè)樹(shù) T 的度為 4，其中度為 1， 2，3，4的結(jié)點(diǎn)的個(gè)數(shù)分別為 4，2，1，1。則 T 中 的葉子結(jié)點(diǎn)的個(gè)數(shù)為（ 8）解答 :n0=（t-1）nt+（t-2）n（t-1）+.+1*n2+0*n1+1=3*1+2*1+1*2+0*4+1=85 在一個(gè)容量為 15 的循環(huán)隊(duì)列中，若頭指針

23、front=6, 尾指針 rear=9, 則該循環(huán)隊(duì)列中 共有多少個(gè)元素 ?（3 個(gè) ）解答:若頭尾,元素個(gè)數(shù) =尾-頭:若頭尾,元素個(gè)數(shù) =15+（ 尾-頭）6 設(shè)有則R和S能進(jìn)行交集（RnS）、并集（RuS）、差操作（R-S）如果R和S的元不同的話，貝V R和S只能進(jìn)行笛卡爾集（RXS）和自然連接7 關(guān)于二叉樹(shù)遍歷問(wèn)題：有兩個(gè)題型，一是給出二叉樹(shù)，求三種遍歷結(jié)果；二是給出 兩種遍歷，求第三種遍歷結(jié)果。后者有點(diǎn)難度三種遍歷是：前序（根左右）、中序（左根右）和后序（左右根）8 關(guān)于查找和排序問(wèn)題：查找技術(shù) -順序查找 對(duì)于長(zhǎng)度為 n 的有序線性表，查找時(shí)需要比較 n 次分法查找 對(duì)于長(zhǎng)度為 n

24、 的有序線性表，查找時(shí)需要比較 log2n 次 排序技術(shù)-假設(shè)線性表的長(zhǎng)度為n,則冒泡排序和簡(jiǎn)單插入排序的比較次數(shù)(時(shí)間復(fù) 雜度)為 n(n-1)/2; 希爾排序的比較次數(shù)為 O(n1.5); 簡(jiǎn)單選擇排序的比較次數(shù)為 n(n- 1)/2; 堆排序的比較次數(shù)為 O(nlog2n).9 關(guān)于出棧的問(wèn)題：記住是先進(jìn)后出例1 ：棧底到頂依次存放 A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧, 則出?？赡艿男蛄惺茿BCED DCBEA DBCEA CDABE例 2：如果進(jìn)棧序列為 e1,e2,e3,e4 ,則可能的出棧序列為：e3,e1,e4,e2 e2,e4,e3,e1e3,e4,e1,e

25、2 任意順序10關(guān)于 E-R 圖是實(shí)體屬性和實(shí)體關(guān)系圖,實(shí)體之間的關(guān)系有 1： 11： mm:n第二部分全國(guó)計(jì)算機(jī)等級(jí)考試 二級(jí)公共考試訓(xùn)練模擬試題一一選擇題（每小題 2 分）在下列各題的 A）， B）， C）， D ）， 4個(gè)選項(xiàng)中，只有 1 個(gè)選項(xiàng)是正確選項(xiàng)添涂在答 題卡相應(yīng)位置上，答在試卷上不得分。1棧和隊(duì)列的共同特點(diǎn)是（ C）。A）都是先進(jìn)先出B）都是先進(jìn)后出C）只允許在端點(diǎn)處插入和刪除元素 C）沒(méi)有共同點(diǎn)2已知二叉樹(shù)后序編歷序列是 dabec ，中續(xù)遍歷序列是 debac ，它的前序編歷序列是 （D）。A）acbedB ） decabC ） deabcD ） cebda33鏈表不具有

26、的特點(diǎn)是（ B）。A）不必事先估計(jì)存儲(chǔ)空間 B）可隨機(jī)訪問(wèn)任一元素C）插入刪除不需要的移動(dòng)元素 D）所需空間與線性長(zhǎng)度4結(jié)構(gòu)化程序設(shè)計(jì)的 3 種結(jié)構(gòu)是（ D）。A）順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu) B）分支結(jié)構(gòu)、等價(jià)結(jié)構(gòu)、循環(huán)結(jié)構(gòu)C）多分支結(jié)構(gòu)、賦值機(jī)構(gòu)、等價(jià)結(jié)構(gòu) D）順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)5為了提高測(cè)試的效率。應(yīng)該（ D）A）隨即選取測(cè)試數(shù)據(jù) B）取一切可能的輸入數(shù)據(jù)作為測(cè)試數(shù)據(jù)C）在完成編碼以后指定軟件的測(cè)試次數(shù)D）集中對(duì)付那些錯(cuò)誤的群集的程序6算法的時(shí)間復(fù)雜度是指（ C）A）執(zhí)行算法程序所需要的時(shí)間B ）算法程序的長(zhǎng)度C）在完成編碼以后指定軟件的測(cè)試次數(shù)D ）算法程序中的指定條數(shù)7軟件

27、生命周期中花費(fèi)用最多的階段是（D）A）詳細(xì)設(shè)計(jì)B）軟件編碼C）軟件測(cè)試D）軟件維護(hù)8 數(shù)據(jù)庫(kù)管理系統(tǒng) DBMS中用來(lái)定義模擬、內(nèi)模式和外模式的語(yǔ)言為（ C）A）C B ） Basic C）DDL D）DML9下列有關(guān)數(shù)據(jù)庫(kù)的描述，正確的是（C）A）數(shù)據(jù)庫(kù)是一個(gè) DBF文件B）數(shù)據(jù)庫(kù)是一個(gè)關(guān)系C）數(shù)據(jù)庫(kù)是一個(gè)結(jié)構(gòu)化的數(shù)據(jù)集合D）數(shù)據(jù)庫(kù)是一組文件10下列有關(guān)數(shù)據(jù)庫(kù)的描述，正確的是（ D）A）數(shù)據(jù)處理是將信息轉(zhuǎn)化為數(shù)據(jù)的過(guò)程B）數(shù)據(jù)的物理獨(dú)立性是指當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)改變時(shí)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不變C）關(guān)系中的每一列稱為元組，一個(gè)元組就是一個(gè)字節(jié)D）如果一個(gè)關(guān)系中的屬性或?qū)傩越M并非該關(guān)系的關(guān)鍵字，但它是另一個(gè)

28、關(guān)系的鍵字，則稱其為本關(guān)系的外關(guān)鍵字二、填空題（每空 2 分）請(qǐng)將每一個(gè)空的正確答案寫在答題卡【11】 【15】序號(hào)的橫線上，答案試卷上不得分。1 算法的基本特征是可行性、確定性、【有窮性】 在長(zhǎng)度為 n 的有序線性表中進(jìn)行二分查找。最壞的情況下，需要的比較次數(shù)為 【 log2n 】。在面向?qū)ο蟮某绦蛟O(shè)計(jì)中。類描述的是具有相似性質(zhì)的一組【對(duì)象】。通常，將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱為【軟件生命周 期】。數(shù)據(jù)庫(kù)管理系統(tǒng)常見(jiàn)的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和【關(guān)系模型】 3 種。模擬測(cè)試二一.選擇題 (每小題 2 分)在下列各題的 A),B),C),D),4 個(gè)選項(xiàng)中 ,只有

29、 1 個(gè)選項(xiàng)是正確的 ,請(qǐng)將正確選項(xiàng)填涂在答 題卡相應(yīng)的位置上 ,答在試卷上不得分 .1. 已知一棵二叉樹(shù)前序遍歷和中序遍歷分別為 ABDEGCFH和DBGEACHF,則該二叉樹(shù)的 后序遍歷為 (B)A)GEDHFBCAB)DGEBHFCAC)ABCDEFGHD)ACBFEDHG2. 樹(shù)是結(jié)點(diǎn)的集合 ,它的根結(jié)點(diǎn)的數(shù)目是 (A)A)有且只有1個(gè)B)1或多于1C)0或1D)至少23. 如果進(jìn)棧序列為 e1,e2,e3,e4, 則可能的出棧序列是 (B)A)e3,e1,e4,e2B)e2,e4,e3,e1C)e3,e4,e1,e2D) 任意順序4. 在設(shè)計(jì)程序時(shí) ,應(yīng)采納的原則之一是 （D）A）不

30、限制goto語(yǔ)句的使用B）減少或取消注解行C）程序越短越好D）程序結(jié)構(gòu)應(yīng)有助于讀者理解5. 程序設(shè)計(jì)語(yǔ)言的基本成分是數(shù)據(jù)成分,運(yùn)算成分 ,控制成分和 （D）A）對(duì)象成分B）變量成分C）語(yǔ)句成分D）傳輸成分6. 下列敘述中 ,不屬于軟件需求規(guī)格說(shuō)明書(shū)的作用的是 （D） 便于用戶 ,開(kāi)發(fā)人員進(jìn)行理解和交流反映出用戶問(wèn)題的結(jié)構(gòu) ,可以作為軟件開(kāi)發(fā)工作的基礎(chǔ)和依據(jù) 作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)便于開(kāi)發(fā)人員進(jìn)行需求分析7. 下列不屬于軟件工程 3 個(gè)要素的是 （D）A）工具B）過(guò)程C）方法D）環(huán)境8. 單個(gè)用戶使用的數(shù)據(jù)視圖描述稱為 （A）A）外模式B）概念模式C）內(nèi)模式D）儲(chǔ)存模式9. 將 E-R 圖轉(zhuǎn)換

31、到關(guān)系模式時(shí) ,實(shí)體與聯(lián)系都可以表示成 （B）A）屬性B）關(guān)系C）鍵D）域10.SQL 語(yǔ)言又稱為 （C）A）結(jié)構(gòu)化定義語(yǔ)言B）結(jié)構(gòu)化控制語(yǔ)言C）結(jié)構(gòu)化查詢語(yǔ)言D）結(jié)構(gòu)化操縱語(yǔ)言二.填空題 （每空 2 分）請(qǐng)將每一個(gè)空的正確答案寫在答題卡 1115 序號(hào)的橫線上 ,答在試卷上不得分2. 在面向?qū)ο蠓椒ㄖ?,類之間共享屬性和操作的機(jī)制稱為繼承 .3. 耦合和內(nèi)聚是評(píng)價(jià)模塊獨(dú)立性的兩個(gè)主要標(biāo)準(zhǔn),其中 內(nèi)聚 反映了模塊內(nèi)個(gè)成分之間的聯(lián)系 .4. 一個(gè)項(xiàng)目具有一個(gè)項(xiàng)目主管 ,一個(gè)項(xiàng)目主管可管理多個(gè)項(xiàng)目,則實(shí)體“項(xiàng)目主管”與實(shí)體“項(xiàng)目”的聯(lián)系屬于 一對(duì)多 的聯(lián)系5. 數(shù)據(jù)庫(kù)設(shè)計(jì)分為以下6個(gè)設(shè)計(jì)階段：需求

32、分析階段、數(shù)據(jù)庫(kù)概念設(shè)計(jì)階段、邏輯設(shè) 計(jì)階段、物理設(shè)計(jì)階段、實(shí)施階段、運(yùn)行和維護(hù)階段模擬測(cè)試三選擇題 （每小題 2 分）在下列各題的 A）,B）,C）,D）4 個(gè)選項(xiàng)中 ,只有 1 個(gè)選項(xiàng)是正確的 ,請(qǐng)將正確選項(xiàng)填涂在答題 卡的相應(yīng)位置上 ,答在試卷上不得分 .1. 算法的空間復(fù)雜度是指 （D）A）算法程序的長(zhǎng)度C）算法程序所占的存儲(chǔ)空間2 用鏈表示線性表的優(yōu)點(diǎn)是A）便于隨機(jī)存取C）便于插入和刪除操作序相同B)D)C)B)D)算法程序中的指令條數(shù)執(zhí)行過(guò)程中所需要的存儲(chǔ)空間花費(fèi)的存儲(chǔ)空間較順序儲(chǔ)存少數(shù)據(jù)元素的物理順序與邏輯順3 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（A）存儲(chǔ)結(jié)構(gòu)E）物理結(jié)構(gòu)

33、C）邏輯結(jié)構(gòu)D）物理和存儲(chǔ)結(jié)構(gòu)4 結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是（ D ）A）程序的規(guī)模E）程序的效率C）程序設(shè)計(jì)語(yǔ)言的先進(jìn)性D）程序易讀性5 軟件設(shè)計(jì)包括軟件的結(jié)構(gòu)、數(shù)據(jù)接口和過(guò)程設(shè)計(jì)，其中軟件的過(guò)程設(shè)計(jì)是指（ B ）A）模塊間的關(guān)系E）系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程描述C）軟件層次結(jié)構(gòu)D）軟件開(kāi)發(fā)過(guò)程6 檢查軟件產(chǎn)品是否符合需求定義的過(guò)程稱為（ A ）A）確認(rèn)測(cè)試E）集成測(cè)試C）驗(yàn)證測(cè)試D）驗(yàn)收測(cè)試7 數(shù)據(jù)流圖用于抽象描述一個(gè)軟件的邏輯模型，數(shù)據(jù)流圖由一些特定的圖符組成下列圖符名稱標(biāo)識(shí)的圖符不屬于數(shù)據(jù)流圖合法圖符的是（A ）A）控制流E）加工C）數(shù)據(jù)存儲(chǔ)D）源和潭8 應(yīng)用數(shù)據(jù)庫(kù)的主要目的是（ C

34、 ）A）解決數(shù)據(jù)保密問(wèn)題E）解決數(shù)據(jù)完整性問(wèn)題C）解決數(shù)據(jù)共享問(wèn)題D）解決數(shù)據(jù)量大的問(wèn)題9 在數(shù)據(jù)庫(kù)設(shè)計(jì)中，將 E-R圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型的過(guò)程屬于（ B ）A）需求分析階段E）邏輯設(shè)計(jì)階段C）概念設(shè)計(jì)階段 D）物理設(shè)計(jì)階段10. 在數(shù)據(jù)管理技術(shù)的發(fā)展過(guò)程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系 統(tǒng)階段其中數(shù)據(jù)獨(dú)立性最高的階段是（ A ）A）數(shù)據(jù)庫(kù)系統(tǒng)E）文件系統(tǒng)C）人工管理D）數(shù)據(jù)項(xiàng)管理填空題（每空2分）請(qǐng)將每一個(gè)空的正確答案寫在答題卡 1115 序號(hào)的橫線上 ,答在試卷上不得分1. 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 非線性結(jié)構(gòu) 兩大類 .2. 順序儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置和

35、相臨 的存儲(chǔ)單元中 .3. 一個(gè)類可以從直接或間接的祖先中繼承所有屬性和方法.采用這個(gè)方法提高了軟件的 可重用性 .4. 軟件工程研究的內(nèi)容主要包括 :軟件開(kāi)發(fā) 技術(shù)和軟件工程管理 .5. 關(guān)系操作的特點(diǎn)是 邏輯數(shù)據(jù)模型 操作 .模擬測(cè)試四選擇題 ( 每小題 2 分)在下列各題的 A),B),C),D)4 個(gè)選項(xiàng)中 ,只有 1 個(gè)選項(xiàng)是正確的 ,請(qǐng)將正確選項(xiàng)填涂在答題 卡的相應(yīng)位置上 ,答在試卷上不得分 .1. 在深度為 5 的滿二叉樹(shù)中 ,葉子結(jié)點(diǎn)的個(gè)數(shù)為 (B)A)32B)31C)16D)152. 若某二叉樹(shù)的前序遍歷是 abdgcefh, 中序遍歷是 dgbaechf, 后序遍歷的結(jié)點(diǎn)訪

36、問(wèn)順序 是( D )A)bdgcefhaB)gdbecfhaC)bdgaechfD)gdbehfca3. 一些重要的程序語(yǔ)言(如C語(yǔ)言和 Pascal語(yǔ)言)允許過(guò)程的遞歸應(yīng)用.而實(shí)現(xiàn)遞歸 調(diào)用中的儲(chǔ)存分配通常用( A )A)棧B)堆C)數(shù)組D)鏈表4. 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括軟件開(kāi)發(fā)技術(shù)和(B)A)消除軟件危機(jī)B)軟件工程管理C）程序設(shè)計(jì)自動(dòng)化 D）實(shí)現(xiàn)軟件可重用5. 開(kāi)發(fā)軟件時(shí)對(duì)提高開(kāi)發(fā)人員工作效率至關(guān)重要的是 （B）A）操作系統(tǒng)的資源管理功能 B）先進(jìn)的軟件開(kāi)發(fā)工具而后環(huán)境C）程序人員的數(shù)量D）計(jì)算機(jī)的并行處理能力6. 在軟件測(cè)試設(shè)計(jì)中 ,軟件測(cè)試是主目的是 （D）A）實(shí)

37、驗(yàn)性運(yùn)行軟件 B）證明軟件正確C）找出軟件中全部錯(cuò)誤 D）發(fā)現(xiàn)軟件錯(cuò)誤而執(zhí)行程序7. 數(shù)據(jù)處理的最小單位是 （C）A）數(shù)據(jù)B）數(shù)據(jù)元素C）數(shù)據(jù)項(xiàng)D）數(shù)據(jù)結(jié)構(gòu)8. 索引屬于 （ B ）A）模式B）內(nèi)模式C）外模式D）概念模式9. 下述關(guān)于數(shù)據(jù)庫(kù)系統(tǒng)的敘述中正確的是 （ B ）數(shù)據(jù)庫(kù)系統(tǒng)減少了數(shù)據(jù)冗余數(shù)據(jù)庫(kù)系統(tǒng)避免了一切冗余數(shù)據(jù)庫(kù)系統(tǒng)中的一致性是指數(shù)據(jù)類型一致數(shù)據(jù)庫(kù)系統(tǒng)比文件系統(tǒng)管理更多的數(shù)據(jù)10. 數(shù)據(jù)庫(kù)系統(tǒng)的核心是 （B）A）數(shù)據(jù)庫(kù)B）數(shù)據(jù)庫(kù)管理系統(tǒng)C）模擬模型D）軟件工程二填空題 （ 每空 2 分）請(qǐng)將每一個(gè)空的正確答案寫在答題卡 1115序號(hào)的橫線上，答在試卷上不得分1. 樹(shù)形結(jié)構(gòu)中 ,

38、樹(shù)根結(jié)點(diǎn)沒(méi)有 前件 .2. Jackson 結(jié)構(gòu)化程序設(shè)計(jì)方法是英國(guó)的 M.Jackson 提出的 ,它是一種面向 12的設(shè)計(jì)方 法.3. 面向?qū)ο蟮哪Ｐ椭?,最基本的概念是對(duì)象和 數(shù)據(jù)結(jié)構(gòu) .4. 軟件設(shè)計(jì)模塊化的目的是 類.5. 數(shù)據(jù)模型按不同應(yīng)用層次分成3種類型,它們是概念數(shù)據(jù)模型、降低副雜性和物理數(shù)據(jù)模型 .模擬測(cè)試五一選擇題 （每小題 2分）在下列各題的 A）,B）,C）,D）4 個(gè)選項(xiàng)中 ,只有 1個(gè)選項(xiàng)是正確的 ,請(qǐng)將正確選項(xiàng)填涂在答題 卡的相應(yīng)位置上 ,答在試卷上不得分 .1. 數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科,主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算以及 （A）A）數(shù)據(jù)的

39、存儲(chǔ)結(jié)構(gòu)B）計(jì)算方法C）數(shù)據(jù)映象D）邏輯存儲(chǔ)2. 串的長(zhǎng)度是 （D）A）串中不同字符的個(gè)數(shù) B）串中不同字母的個(gè)數(shù)C）串中所含字符的個(gè)數(shù)且字符個(gè)數(shù)大于零D）串中所含字符的個(gè)數(shù)3. 在計(jì)算機(jī)中 , 算法是指 （B）A）加工方法B）解題方案的準(zhǔn)確而完整的描述C）排序方法D）查詢方法4. 以下不屬于對(duì)象的基本特征的是 （C）A）分類性B）多態(tài)性C）繼承性D）封裝性5. 開(kāi)發(fā)軟件所需高成本和產(chǎn)品的低質(zhì)量之間有著尖銳的矛盾,這種現(xiàn)象稱作 （B）A）軟件投機(jī)B）軟件危機(jī)C）軟件工程D）軟件產(chǎn)生6. 下面不屬于軟件設(shè)計(jì)原則的是 （C）A）抽象B）模塊化C）自底向上D）信息隱蔽7. 開(kāi)發(fā)大型軟件時(shí) ,產(chǎn)生困難

40、的根本原因是 （A）A）大系統(tǒng)的復(fù)雜性C）人員知識(shí)不足C）客觀世界千邊萬(wàn)化 D）時(shí)間緊、任務(wù)重8 下列 QSL 語(yǔ)句中 ,用于修改表結(jié)構(gòu)的是 （A）A）ALTERB）CREATEC）UPDATED）INSERT9. 數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)系統(tǒng)和數(shù)據(jù)庫(kù)管理之間的關(guān)系是（B）數(shù)據(jù)庫(kù)包括數(shù)據(jù)庫(kù)系統(tǒng)和數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)包括數(shù)據(jù)庫(kù)和數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)庫(kù)管理系統(tǒng)包括數(shù)據(jù)庫(kù)和數(shù)據(jù)庫(kù)系統(tǒng)三者沒(méi)有明顯的包含關(guān)系10. 關(guān)系模型允許定義 3 類數(shù)據(jù)約束 ,下列不屬于數(shù)據(jù)約束的是 （C）A）實(shí)體完整性的約束 B）參照完整性的約束C）域完整性的約束D）用戶自定義的完整性約束二填空題 （ 每空 2 分）請(qǐng)將每一個(gè)空的正確

41、答案寫在答題卡 1115序號(hào)的橫線上，答在試卷上不得分長(zhǎng)度為 n 的順序存儲(chǔ)在線性表中 ,當(dāng)在任何位置上插上一個(gè)元素概率都相等時(shí),插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為 n/2.用樹(shù)型結(jié)構(gòu)表示實(shí)體類型及實(shí)體間聯(lián)系的數(shù)據(jù)模型稱為層次模型 .類是一個(gè)支持集成的抽象數(shù)據(jù)類型 ,而對(duì)象是類的 實(shí)例 .數(shù)據(jù)流圖的類型有 14和事務(wù)型 .當(dāng)數(shù)據(jù)的物理結(jié)構(gòu) （存儲(chǔ)結(jié)構(gòu)、存取方式等 ）改變時(shí) ,不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu) ,從而不致 引起應(yīng)用程序的變化 ,這是指數(shù)據(jù)的 變換行 .模擬測(cè)試六 一.選擇題 (每小題 2 分)在下列各題的 A),B)C),D)4 個(gè)選項(xiàng)中 ,只有 1 個(gè)選項(xiàng)是正確的 ,請(qǐng)將正確選項(xiàng)填涂在

42、答題 卡相應(yīng)的位置上 ,答在試卷上不得分 .1. 假設(shè)線性表的長(zhǎng)度為 n, 則在最壞的情況下 ,冒泡排序需要的比較次數(shù)為 (D)log2n2. 算法分析的目的是 (D)A)找出數(shù)據(jù)結(jié)構(gòu)的合理性 B)找出算法中輸入和輸出之間的關(guān)系C)分析算法的易懂性和可靠性D)分析算法的效率以求改進(jìn)3. 線性表 L=(a), 下列說(shuō)法正確的是 ( D )每個(gè)元素都有一個(gè)直接前件和直接后件線性表中至少要有一個(gè)元素表中諸元素的排列順序必須是由小到大或由大到小除第一個(gè)元素和最后一個(gè)元素外 ,其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前件和直接后 件4. 在單鏈表中 ,增加頭結(jié)點(diǎn)的目的是 (A)A)方便運(yùn)算的實(shí)現(xiàn)B)使單鏈表至

43、少有一個(gè)結(jié)點(diǎn)C)標(biāo)識(shí)表中首結(jié)點(diǎn)的位置 D)說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)5. 軟件工程的出現(xiàn)是由于 (C)A)程序設(shè)計(jì)方法學(xué)的影響 B)軟件產(chǎn)業(yè)化的需要C)軟件危機(jī)的出現(xiàn)D)計(jì)算機(jī)的發(fā)展6. 軟件開(kāi)發(fā)離不開(kāi)系統(tǒng)環(huán)境的支持 , 其中必要的測(cè)試數(shù)據(jù)屬于 （D）A）硬件資源B）通信資源C）支持軟件D）輔助資源7. 在數(shù)據(jù)流圖中 ,帶有名字的箭頭表示 （D）A）模塊之間的調(diào)用關(guān)系 B）程序的組成成分C）控制程序的執(zhí)行順序 D）數(shù)據(jù)的流向8. 分布式數(shù)據(jù)庫(kù)系統(tǒng)不具有的特點(diǎn)是 （D）A）數(shù)據(jù)分布性和邏輯整體性 B）位置透明性和復(fù)制透明性C）分布性D）數(shù)據(jù)冗余9. 關(guān)系表中的每一橫行稱為一個(gè) （A）A）元

44、組B）字段C）屬性D）碼10. 下列數(shù)據(jù)模型中 ,具有堅(jiān)實(shí)理論基礎(chǔ)的是 （C）A）層次模型B）網(wǎng)狀模型C）關(guān)系模型D）以上三個(gè)都是二.填空題 （每空 2 分）請(qǐng)將每一空的正確答案寫在答題卡1115序號(hào)的橫線上，答在試卷上不得分在算法正確的前提下 ,評(píng)價(jià)一個(gè)算法的兩個(gè)標(biāo)準(zhǔn)是時(shí)間復(fù)雜度和空間復(fù)雜度 .將代數(shù)式z=轉(zhuǎn)換成程序設(shè)計(jì)中的表達(dá)式為SQRT（xA2+yA2）/（a+b）.軟件危機(jī)出現(xiàn)于 20 世紀(jì) 60 年代末,為了解決軟件危機(jī) ,人們提出了 軟件工程學(xué) 的原理 來(lái)設(shè)計(jì)軟件 ,這就是軟件工程誕生的基礎(chǔ) .數(shù)據(jù)模型 是數(shù)據(jù)庫(kù)設(shè)計(jì)的核心 .在關(guān)系模型中 ,把數(shù)據(jù)看成一個(gè)二維表 ,每一個(gè)二維表稱為

45、一個(gè) 關(guān)系.模擬測(cè)試七 一.選擇題 (每小題 2 分)在下列各題的 A),B)C),D)4 個(gè)選項(xiàng)中 ,只有 1 個(gè)選項(xiàng)是正確的 ,請(qǐng)將正確選項(xiàng)填涂在答題 卡相應(yīng)的位置上 ,答在試卷上不得分1. 下列敘述中正確的是 (A)A)線性表是線性結(jié)構(gòu)B)棧與隊(duì)列是非線性結(jié)構(gòu)C)線性鏈表是非線性結(jié)構(gòu)D)二叉樹(shù)是線性結(jié)構(gòu)2. 非空的循環(huán)單列表head的尾結(jié)點(diǎn)(由p所指向),滿足(C)A)p next=NULLB)p=NULLC)pnext=headD)p=head3. 已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn),為節(jié)省時(shí)間，應(yīng)采用的算法是(B)A)堆排序B)直接插入排序C)快速排序D)直接選擇排序4. 對(duì)建立

46、良好的程序設(shè)計(jì)風(fēng)格 ,下面描述正確的是 (A)A)程序應(yīng)簡(jiǎn)單、清晰、可讀性好B)符號(hào)名的命名只要符合語(yǔ)法C)充分考慮程序的執(zhí)行效率D)程序的注釋可有可無(wú)5. 下列不屬于結(jié)構(gòu)化分析常用工具的是(A)A)數(shù)據(jù)流圖B)數(shù)據(jù)字典C)判定樹(shù)D)PAD圖6. 在軟件生產(chǎn)過(guò)程中 ,需求信息的給出是 (D)A)程序員B)項(xiàng)目管理者C)軟件分析設(shè)計(jì)人員 D)軟件用戶7. 下列工具中為需求分析常用的工具是(D)A)PADB)PFDC)N-SD)DFD8. NULL 是指(C)9. 數(shù)據(jù)庫(kù)的故障恢復(fù)一般是由 (C)A)數(shù)據(jù)流圖完成的B)數(shù)據(jù)字典完成的C)DBA 完成的 D)PAD 圖完成的10. 下列說(shuō)法中 ,不屬

47、于數(shù)據(jù)模型所描述的內(nèi)容的是 (C)A)數(shù)據(jù)結(jié)構(gòu)B)數(shù)據(jù)操作C)數(shù)據(jù)查詢D)數(shù)據(jù)約束二. 填空題 ( 每空 2 分)請(qǐng)將每一空的正確答案寫在答題卡1115序號(hào)的橫線上，答在試卷上不得分1. 冒泡排序法在最好的情況下的元素交換次數(shù)為0.2. 在最壞的情況下 ,堆排序需要比較的次數(shù)為 O(log2n).3. 若串 s= “ MathTypes ” ,則其子串的數(shù)目是 46.4. 軟件開(kāi)發(fā)環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具 集合.5. 關(guān)系數(shù)據(jù)庫(kù)的關(guān)系演算語(yǔ)言是以謂詞演算為基礎(chǔ)的DML語(yǔ)言.模擬測(cè)試八一.選擇題(每小題 2分)在下列各題的 A),B)C),D)4 個(gè)選項(xiàng)中 ,只有 1 個(gè)選項(xiàng)是正確

48、的 ,請(qǐng)將正確選項(xiàng)填涂在答題 卡相應(yīng)的位置上 ,答在試卷上不得分 .1. 循環(huán)鏈表的主要優(yōu)點(diǎn)是 (B)不在需要頭指針了 從表中任一結(jié)點(diǎn)出發(fā)都能訪問(wèn)到整個(gè)鏈表在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開(kāi)已知某個(gè)結(jié)點(diǎn)的位置后 ,能夠容易找到它的直接前件2. 棧底至棧頂依次存放元素 A,B,C,D，在第五個(gè)元素E入棧前,棧中元素可以出棧,則出棧 序列可能是 (B)A)ABCDEB)DCBEAC)DBCEAD)CDABE3. n 個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有 (C)A)n-1B)n(n-1)C)nD)n+14. 在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前 ,在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率 ,現(xiàn)在,在程序的效 率相比

49、 ,人們更重視程序的 (C)A)安全性B) 一致性C)可理解性 D)合理性5. 模塊獨(dú)立性是軟件模塊化所提出的要求,衡量模塊獨(dú)立性的度量標(biāo)準(zhǔn)則是模塊的 (C)A)抽象和信息隱蔽B)局部化和封裝化C)內(nèi)聚性和耦合性D)激活機(jī)制和控制方法6. 軟件開(kāi)發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成(A)A)定義、開(kāi)發(fā)、運(yùn)行維護(hù) B)設(shè)計(jì)階段、編程階段、測(cè)試階段C)總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編程調(diào)試 D)需求分析、功能定義、系統(tǒng)設(shè)計(jì)7. 在軟件工程中 ,白盒測(cè)試法可用于測(cè)試程序的內(nèi)部結(jié)構(gòu) ,此方法將程序看作是 (A)A)路徑的集合B)循環(huán)的集合C) 目標(biāo)的集合D)地址的集合8. 在數(shù)據(jù)管理技術(shù)發(fā)展過(guò)程中 ,文件

50、系統(tǒng)與數(shù)據(jù)庫(kù)系統(tǒng)的主要區(qū)別是數(shù)據(jù)庫(kù)系統(tǒng)具有(A)A)特定的數(shù)據(jù)模型B)數(shù)據(jù)無(wú)冗余C)數(shù)據(jù)可共享D)專門的數(shù)據(jù)管理軟件9. 數(shù)據(jù)庫(kù)設(shè)計(jì)包括兩個(gè)方面的設(shè)計(jì)內(nèi)容,它們是 (A)10. 實(shí)體是信息世界中廣泛使用的一個(gè)術(shù)語(yǔ) ,它用于表示 （C）A）有生命的事物 B）無(wú)生命的事物 C）實(shí)際存在的事物 D） 一切事物二. 填空題 （ 每空 2 分）請(qǐng)將每一空的正確答案寫在答題卡 1115序號(hào)的橫線上，答在試卷上不得分1. 常用的黑盒測(cè)試有等價(jià)分類法、邊值分析法、因果圖法和錯(cuò)誤推測(cè)法 4種.2. 測(cè)試的目的的暴露錯(cuò)誤 ,評(píng)價(jià)程序的可靠性 ;而調(diào)試的目的是發(fā)現(xiàn)錯(cuò)誤的位置并改正 錯(cuò)誤.3. 軟件維護(hù)活動(dòng)包括以下幾

51、類 :改正性維護(hù)、適應(yīng)性維護(hù)、 完善性 維護(hù)和預(yù)防性維護(hù)4 .在面向?qū)ο蟮脑O(shè)計(jì)中 ,用來(lái)請(qǐng)求對(duì)象執(zhí)行某一處理或回答某些信息的要求稱為消息.5.關(guān)鍵字ASC和DESC分別表示升序排列和降序排列的含義模擬測(cè)試九一.選擇題（每小題 2分）在下列各題的 A）,B）C）,D）4 個(gè)選項(xiàng)中 ,只有 1 個(gè)選項(xiàng)是正確的 ,請(qǐng)將正確選項(xiàng)填涂在答題 卡相應(yīng)的位置上 ,答在試卷上不得分1. 最簡(jiǎn)單的交換排序方法是 （D）A）快速排序B）選擇排序C）堆排序D）冒泡排序2. 棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（A）線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)列方式和索引方式 表存儲(chǔ)結(jié)構(gòu)和數(shù)組線行存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)3. 線性表的順序存儲(chǔ)結(jié)

52、構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是（B）A）順序存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)、順序結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)B）隨機(jī)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)、順序存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)C）隨機(jī)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)D）任意存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)、任意存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)4完全不考慮程序的內(nèi)部結(jié)構(gòu)和內(nèi)部特征，而只是根據(jù)程序功能導(dǎo)出測(cè)試用例的方法 是（ A）A）黑盒測(cè)試法B）白盒測(cè)試法C）錯(cuò)誤推測(cè)法D）安裝測(cè)試法5 在結(jié)構(gòu)化設(shè)計(jì)方法中，生成的結(jié)構(gòu)圖（ SC）中，帶有箭頭的連線表示（A）A）模塊之間的調(diào)用關(guān)系 B）程序的組成成分C）控制程序的執(zhí)行順序 D）數(shù)據(jù)的流向6下列選項(xiàng)中，不屬于模塊間耦合的是（ C）A）數(shù)據(jù)耦合B）同構(gòu)耦合C）異構(gòu)耦合D）公用耦合7一個(gè)關(guān)系

53、中屬性個(gè)數(shù)為 1 時(shí)，稱此關(guān)系為（ C）A）對(duì)應(yīng)關(guān)系B）單一關(guān)系C）兀關(guān)系D）兀關(guān)系8為用戶與數(shù)據(jù)庫(kù)系統(tǒng)提供接口的語(yǔ)言是（ C）A）高級(jí)語(yǔ)言B）數(shù)據(jù)描述語(yǔ)言（DDL） C）數(shù)據(jù)操縱語(yǔ)言（DML） D）匯編總匯9相對(duì)于數(shù)據(jù)庫(kù)系統(tǒng)，文件系統(tǒng)的主要缺陷有數(shù)據(jù)關(guān)聯(lián)差、數(shù)據(jù)數(shù)據(jù)不一致性和 （D）A）可重用性差B）安全性差C）非持久性D）冗余性10需求分析階段的任務(wù)是確定（ D）A）軟件開(kāi)發(fā)方法B）軟件開(kāi)發(fā)工具C）軟件開(kāi)發(fā)費(fèi)用D）軟件系統(tǒng)功能二. 填空題 （ 每空 2 分）請(qǐng)將每一空的正確答案寫在答題卡1115序號(hào)的橫線上，答在試卷上不得分棧和隊(duì)列通常采用的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ) 。在程序設(shè)計(jì)階段應(yīng)該

54、采取 自頂向下 和逐步求精的方法，把一個(gè)模塊的功能逐步分 解，細(xì)化為一系列具體的步驟，進(jìn)而用某種程序設(shè)計(jì)語(yǔ)言寫成程序。軟件結(jié)構(gòu)是以 模塊為基礎(chǔ)而組成的一種控制層次結(jié)構(gòu)。數(shù)據(jù)庫(kù)系統(tǒng)階段的數(shù)據(jù)具有較高的獨(dú)立性，數(shù)據(jù)獨(dú)立性包括物理獨(dú)立性和邏輯獨(dú)立性 兩個(gè)含義。數(shù)據(jù)庫(kù)保護(hù)分為：安全性控制、完整性控制 、并發(fā)性控制和數(shù)據(jù)的復(fù)制。模擬測(cè)試十一.選擇題（每小題 2分）在下列各題的 A）,B）C）,D）4 個(gè)選項(xiàng)中 ,只有 1 個(gè)選項(xiàng)是正確的 ,請(qǐng)將正確選項(xiàng)填涂在答題 卡相應(yīng)的位置上 ,答在試卷上不得分。1 下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是（ B）A）線性鏈表B）棧C）循環(huán)鏈表D）順序表2具有 3 個(gè)結(jié)點(diǎn)的二叉樹(shù)有（ D）A） 2種形態(tài) B） 4種形態(tài) C） 7種形態(tài) D） 5種形態(tài)B)3設(shè)有如圖所示二叉樹(shù)：對(duì)此二叉樹(shù)前序列遍歷的結(jié)果為（A)ZBTYCPXAB)ATBZXCYPC)ZBTACYXPD)ATBZXCPY 4結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是（ D）A）程序的規(guī)模B）程序的效率C）程序設(shè)計(jì)語(yǔ)言的先進(jìn)性 D）程序醫(yī)讀性5程序的 3 種基本控制結(jié)構(gòu)是（ B）A）過(guò)程、子過(guò)程和分程序 B）順序、選擇和循環(huán)C）遞歸、堆棧和隊(duì)列 D）調(diào)用、返回和轉(zhuǎn)移6下列敘述中，不屬于測(cè)試的特征的是（ C）A）測(cè)試的挑剔性 B）完全測(cè)試的不可能性 C）測(cè)試的可靠性 D）測(cè)試的經(jīng)濟(jì)性7需求分