一、課程內容

　　本章介紹了集合的基本概念、性質(zhì);算法的基本概念、性質(zhì);以及算法時(shí)空復雜度分析。為以后章節的學(xué)習打下了基礎。

　　二、考核知識點(diǎn)與考核要求

　　1集合

　　識記：(1)集合的基本概念

　　(2)映射

　　(3)自然數集與數學(xué)歸納法

　　領(lǐng)會(huì )：(1)列舉法表示集合

　　(2)性質(zhì)敘述法表示集合

　　(3)集合的并、交、差運算

　　(4)笛卡爾集

　　(5)二元關(guān)系

　　應用：無(wú)

　　2算法

　　識記：(1)算法的定義

　　(2)算法的四個(gè)基本性質(zhì)(能行性、確定性、有窮性、擁有足夠情報)

　　(3)常見(jiàn)的六種算法(列舉法、歸納法、遞推、遞歸、減半遞推、回溯)

　　(4)算法的空間復雜度

　　領(lǐng)會(huì )：(1)算法的時(shí)間復雜度分析

　　應用：無(wú)

　　四、本章重點(diǎn)、難點(diǎn)

　　重點(diǎn)：集合的基本運算、算法的定義、算法的時(shí)間復雜度分析。

　　第二章 基本數據結構及其運算

　　一、學(xué)習目的與要求

　　通過(guò)本章的學(xué)習，基本數據結構中的線(xiàn)性結構、樹(shù)狀結構、圖結構及其基本運算，能夠區分基本數據結構，能夠根據基本數據結構的性質(zhì)描述數據，能夠使用基本數據結構設計簡(jiǎn)單算法解決實(shí)際問(wèn)題。

　　二、課程內容

　　本章介紹了基本數據結構中的線(xiàn)性結構、樹(shù)狀結構、圖結構及其基本運算。

　　三、考核知識點(diǎn)與考核要求

　　1數據結構的基本概念

　　識記：(1)數據結構的定義

　　(2)邏輯結構是什么

　　(3)存儲結構是什么

　　領(lǐng)會(huì )：(1)數據結構的圖形表示

　　(2)線(xiàn)性結構的條件

　　2線(xiàn)性表及其順序存儲結構

　　識記：(1)什么是線(xiàn)性表

　　領(lǐng)會(huì )：(1)線(xiàn)性表的順序存儲

　　(2)什么是堆棧

　　(3)什么是隊列

　　應用：(1)線(xiàn)性表在順序存儲下的插入運算

　　(2)線(xiàn)性表在順序存儲下的刪除運算

　　(3)堆棧的應用

　　(4)隊列的應用

　　(5)循環(huán)隊列

　　3線(xiàn)性鏈表

　　識記：(1)線(xiàn)性鏈表的基本概念

　　領(lǐng)會(huì )：(1)鏈表下的堆棧

　　(2)鏈表下的隊列

　　(3)循環(huán)鏈表

　　應用：(1)線(xiàn)性鏈表的插入運算

　　(2)線(xiàn)性鏈表的刪除運算

　　4線(xiàn)性表的索引存儲結構

　　不作要求

　　5數組

　　領(lǐng)會(huì )：(1)二維數組行為主的順序存儲

　　(2)二維數組列為主的順序存儲

　　(3)下三角矩陣壓縮存儲

　　(4)對稱(chēng)矩陣壓縮存儲

　　(5)三角矩陣壓縮存儲

　　(6)一般稀疏矩陣的表示

　　(7)稀疏矩陣的三列二維數組表示

　　(8)十字鏈表的表示

　　6樹(shù)與二叉樹(shù)

　　識記：(1)樹(shù)的概念

　　(2)樹(shù)結構的基本術(shù)語(yǔ)

　　(3)二叉樹(shù)的概念

　　(4)滿(mǎn)二叉樹(shù)的概念

　　(5)完全二叉樹(shù)的概念

　　領(lǐng)會(huì )：(1)二叉樹(shù)的基本性質(zhì)

　　(2)二叉樹(shù)的存儲結構

　　(3)有序樹(shù)的二叉樹(shù)表示

　　(4)表達式的線(xiàn)性化

　　應用：(1)二叉樹(shù)的遍歷(前序，中序，后序)

　　7圖

　　識記：(1)圖的基本概念

　　領(lǐng)會(huì )：(1)圖的關(guān)聯(lián)矩陣存儲結構

　　(2)圖的鄰接表存儲結構

　　應用：(1)圖的縱向優(yōu)先搜索遍歷

　　(3)圖的橫向優(yōu)先搜索遍歷

　　四、本章重點(diǎn)、難點(diǎn)

　　重點(diǎn)：線(xiàn)性結構的插入、刪除、查找;堆棧的應用;隊列的應用;二叉樹(shù)的性質(zhì);二叉樹(shù)的遍歷;圖的遍歷。

　　第三章 查找與排序技術(shù)

　　一、學(xué)習目的與要求

　　通過(guò)本章的學(xué)習，了解查找和排序的基本算法。

　　二、課程內容

　　本章介紹了查找和排序的基本算法。

　　三、考核知識點(diǎn)與考核要求

　　1.基本的查找技術(shù)

　　領(lǐng)會(huì )：(1)順序查找

　　(2)分塊查找

　　應用：(1)有序表的對分查找

　　2.哈希表技術(shù)

　　領(lǐng)會(huì )：(1)直接查找技術(shù)

　　(2)哈希表技術(shù)

　　(3)哈希表的構造

　　應用：(1)幾種常用的哈希表

　　3.基本的排序技術(shù)

　　應用：(1)冒泡排序和快速排序

　　(2)簡(jiǎn)單插入排序與希爾排序

　　(3)簡(jiǎn)單選擇排序與堆排序

　　(4)歸并排序

　　(5)基數排序

　　4.二叉排序樹(shù)及其查找

　　識記：(1)二叉排序樹(shù)的基本概念

　　應用：(1)二叉排序樹(shù)的插入

　　(2)二叉排序樹(shù)的刪除

　　(3)二叉排序樹(shù)的查找

　　5. 多層索引樹(shù)及其查找

　　不作要求

　　四、本章重點(diǎn)、難點(diǎn)

　　重點(diǎn)：哈希表技術(shù)，基本排序技術(shù)，二叉排序樹(shù)的查找，插入與刪除

　　第四章 資源管理技術(shù)

　　一、學(xué)習目的與要求

　　通過(guò)本章的學(xué)習，掌握操作系統的原理、基本概念及常用方法。

　　二、課程內容

　　本章介紹了操作系統的原理、基本概念及常用方法，重點(diǎn)介紹了多道程序設計和存儲空間的組織。

　　三、考核知識點(diǎn)與考核要求

　　1.操作系統的概念

　　識記：(1)操作系統的功能與任務(wù)

　　(2)操作系統的發(fā)展過(guò)程

　　(3)操作系統的分類(lèi)

　　2.多道程序設計

　　識記：(1)進(jìn)程的基本概念

　　(2)進(jìn)程控制塊及其組織

　　(3)多道程序的組織

　　領(lǐng)會(huì )：(1)進(jìn)程的狀態(tài)及其轉化

　　(2)死鎖問(wèn)題

　　應用：(1)進(jìn)程間的同步與互斥

　　(2)P/V操作

　　3.存儲空間的組織

　　識記：(1)存儲管理的功能

　　(2)文件的邏輯結構

　　(3)文件的物理結構

　　(4)文件的目錄結構

　　(5)文件空閑區的組織

　　領(lǐng)會(huì )：(1)界地址存儲管理

　　(2)分段存儲管理

　　應用：(1)分頁(yè)存儲管理

　　四、本章重點(diǎn)、難點(diǎn)

　　重點(diǎn)：P/V操作，分頁(yè)存儲管理。

　　第五章 數據庫設計技術(shù)

　　一、學(xué)習目的與要求

　　通過(guò)本章的學(xué)習，掌握數據庫設計的原理、關(guān)系代數及數據庫設計過(guò)程。

　　二、課程內容

　　本章介紹了數據庫設計的原理、關(guān)系代數及數據庫設計過(guò)程。

　　三、考核知識點(diǎn)與考核要求

　　1.數據庫基本概念

　　識記：(1)數據庫管理技術(shù)

　　(2)數據庫管理系統

　　(3)數據庫系統的構成

　　領(lǐng)會(huì )：(1)信息的存在形態(tài)

　　(2)實(shí)體間的聯(lián)系

　　(3)數據模型(層次模型，網(wǎng)狀模型，關(guān)系模型)

　　2.關(guān)系代數

　　應用：(1)關(guān)系代數中的各種運算

　　3.數據庫設計

　　識記：(1)數據庫設計的基本概念

　　(2)數據庫設計的過(guò)程

　　(3)數據字典

　　應用：(1)概念結構的設計

　　四、本章重點(diǎn)、難點(diǎn)

　　重點(diǎn)：關(guān)系代數中的各種運算、數據庫概念結構設計(E-R)圖

　　第六章 編譯技術(shù)概述

　　一、學(xué)習目的與要求

　　通過(guò)本章的學(xué)習，了解編譯技術(shù)的基本原理。

　　二、課程內容

　　本章介紹了編譯技術(shù)的工作過(guò)程、詞法分析、語(yǔ)法加工等內容。

　　三、考核知識點(diǎn)與考核要求

　　1.編譯程序的工作過(guò)程及其基本組成

　　識記：(1)編譯的過(guò)程

　　(2)編譯程序的基本組成

　　2.狀態(tài)矩陣法的編譯過(guò)程

　　不作要求

　　3.詞法分析

　　識記：(1)詞法分析的任務(wù)

　　4.中間語(yǔ)言表示

　　不作要求

　　5.語(yǔ)法的分析與加工

　　識記：(1)語(yǔ)法分析和加工的主要任務(wù)

　　四、本章重點(diǎn)、難點(diǎn)

　　重點(diǎn)：編譯的過(guò)程

　　第七章 應用軟件設計與開(kāi)發(fā)技術(shù)

　　一、學(xué)習目的與要求

　　通過(guò)本章的學(xué)習，掌握軟件工程的概念、生命周期及常用方法。

　　二、課程內容

　　本章介紹了軟件工程的概念、生命周期及常用方法。

　　三、考核知識點(diǎn)與考核要求

　　1.軟件工程概述

　　識記：(1)軟件工程的概念

　　(2)軟件的生命周期

　　(3)軟件的支撐環(huán)境

　　2.軟件詳細設計的表達

　　識記：(1)程序流程圖

　　(2)NS圖

　　3.結構化分析與設計方法

　　識記：(1)應用軟件開(kāi)發(fā)的基本原則

　　(2)應用軟件的開(kāi)發(fā)方法

　　領(lǐng)會(huì )：(1)結構化的分析方法

　　(2)數據流程圖

　　(3)結構化的設計方法

　　(4)模塊獨立性評價(jià)

　　4.測試與調試基本技術(shù)

　　識記：(1)測試的基本概念

　　(2)測試的三個(gè)特征

　　(3)測試的過(guò)程

　　(4)測試的層次

　　領(lǐng)會(huì )：(1)測試的方法

　　(2)調試與測試的關(guān)系

　　5.軟件開(kāi)發(fā)新技術(shù)

　　領(lǐng)會(huì )：(1)原形方法

　　(2)瀑布模型

　　(3)面向對象的方法

　　四、本章重點(diǎn)、難點(diǎn)

　　重點(diǎn)：結構化的分析和設計方法。

　�、� 關(guān)于大綱的說(shuō)明與考核實(shí)施要求

　　一、自學(xué)考試大綱的目的和作用

　　課程自學(xué)考試大綱是根據專(zhuān)業(yè)自學(xué)考試計劃的要求，結合自學(xué)考試的特點(diǎn)而確定。其目的是對個(gè)人自學(xué)、社會(huì )助學(xué)和課程考試命題進(jìn)行指導和規定。

　　課程自學(xué)考試大綱明確了課程學(xué)習的內容以及深廣度，規定了課程自學(xué)考試的范圍和標準。因此，它是編寫(xiě)自學(xué)考試教材和輔導書(shū)的依據，是社會(huì )助學(xué)組織進(jìn)行自學(xué)輔導的依據，是自學(xué)者學(xué)習教材、掌握課程內容知識范圍和程度的依據，也是進(jìn)行自學(xué)考試命題的依據。

　　二、課程自學(xué)考試大綱與教材的關(guān)系

　　課程自學(xué)考試大綱是進(jìn)行學(xué)習和考核的依據，教材是學(xué)習掌握課程知識的基本內容與范圍，教材的內容是大綱所規定的課程知識和內容的擴展與發(fā)揮。課程內容在教材中可以體現一定的深度或難度，本大綱中對考核的要求是按照本專(zhuān)業(yè)的培養目標，以及對考生知識結構要求和專(zhuān)業(yè)考試計劃來(lái)確定的，深度或難度較適當。

　　大綱與教材所體現的課程內容應基本一致;本大綱的課程內容和考核知識點(diǎn)是與所選教材一致的。所選教材里的部分內容，本大綱不作考核要求。(注：其中的內容與大綱要求不一致的地方，以大綱規定為準。)

　　三、關(guān)于自學(xué)教材

　　自學(xué)教材：《計算機軟件技術(shù)基礎》(第三版)，徐士良、葛兵等編著(zhù)，清華大學(xué)出版社，2010年版。

　　四、關(guān)于自學(xué)要求和自學(xué)方法的指導

　　本大綱的課程基本要求是依據專(zhuān)業(yè)考試計劃和專(zhuān)業(yè)培養目標而確定的。課程基本要求還明確了課程的基本內容，以及對基本內容掌握的程度�；�本要求中的知識點(diǎn)構成了課程內容的主體部分。因此，課程基本內容掌握程度、課程考核知識點(diǎn)是高等教育自學(xué)考試考核的主要內容。

　　為有效地指導個(gè)人自學(xué)和社會(huì )助學(xué)，本大綱已指明了課程的重點(diǎn)和難點(diǎn)，在章節的基本要求中一般也指明了章節內容的重點(diǎn)和難點(diǎn)。

　　《計算機軟件基礎(二)》課程內容涉及面較寬，涉及到數據結構、算法、操作系統、數據庫技術(shù)、軟件工程等許多方面�？忌�在自學(xué)時(shí)往往會(huì )感到有一定困難，但自學(xué)能力的培養對獲取知識是非常必要的。在自學(xué)過(guò)程中應注意以下幾點(diǎn)：

　　1.根據考核要求中的四個(gè)能力層次，在全面系統學(xué)習的基礎上掌握重點(diǎn)概念和重點(diǎn)問(wèn)題，如數據結構的基本特性、線(xiàn)性結構、樹(shù)結構、圖結構等，注意各章內容之間的內在聯(lián)系。

　　2.本課程的自學(xué)考試大綱是自學(xué)本課程的主要依據。在自學(xué)本課程前應先通讀大綱，了解課程的要求，獲得課程完整的概貌。在開(kāi)始自學(xué)某一章時(shí)，先閱讀大綱，了解該章的課程內容，考核知識點(diǎn)和考核要求，在自學(xué)過(guò)程中就有的放矢。

　　3.閱讀教材時(shí)，要求吃透每個(gè)考核知識點(diǎn)。對基本概念要做到深刻理解，對基本原理要弄清弄懂，對基本方法要熟練掌握。

　　4.重視每章末的習題的作用，最好多做習題，可以幫助考生盡快地達到自考大綱的要求，并可以檢查學(xué)習掌握知識的程度。

　　5.本課程是一門(mén)實(shí)踐性較強的課程，考生在自學(xué)過(guò)程中必須注意理論聯(lián)系實(shí)際，按實(shí)驗的目的、要求和內容認真做好實(shí)驗。建議實(shí)驗與課程自學(xué)過(guò)程同步進(jìn)行。

　　6.考生在自學(xué)時(shí)要注意基本能力的培養，即系統分析和綜合的能力，分析問(wèn)題和理解知識的能力，抓住重點(diǎn)闡述問(wèn)題的能力，以及實(shí)驗能力等。

　　五、應考指導

　　1. 如何學(xué)習

　　很好的計劃和組織是你學(xué)習成功的法寶�！�如果你正在接受培訓學(xué)習，一定要跟緊課程并完成作業(yè)�！瓰榱嗽诳荚囍凶鞒鰸M(mǎn)意的回答，你必須對所學(xué)課程內容有很好的理解�！�使用“行動(dòng)計劃表”來(lái)監控你的學(xué)習進(jìn)展�！�你閱讀課本時(shí)可以做讀書(shū)筆記。如有需要重點(diǎn)注意的內容，可以用彩筆來(lái)標注。如：紅色代表重點(diǎn);綠色代表需要深入研究的領(lǐng)域;黃色代表可以運用在工作之中�？梢栽诳瞻滋幱涗浵嚓P(guān)網(wǎng)站，文章。

　　2. 如何考試

　　卷面整潔非常重要。書(shū)寫(xiě)工整，段落與間距合理，卷面賞心悅目有助于教師評分，教師只能為他能看懂的內容打分�；卮鹚�提出的問(wèn)題。要回答所問(wèn)的問(wèn)題，而不是回答你自己樂(lè )意回答的問(wèn)題!避免超過(guò)問(wèn)題的范圍

　　3. 如何處理緊張情緒

　　正確處理對失敗的懼怕，要正面思考。如果可能，請教已經(jīng)通過(guò)該科目考試的人，問(wèn)他們一些問(wèn)題。做深呼吸放松，這有助于使頭腦清醒，緩解緊張情緒�？荚嚽昂侠砩攀�，保持旺盛精力，保持冷靜。

　　4. 如何克服心理障礙

　　這是一個(gè)普遍問(wèn)題!如果你在考試中出現這種情況，試試下列方法：使用“線(xiàn)索”紙條。進(jìn)入考場(chǎng)之前，將記憶“線(xiàn)索”記在紙條上，但你不能將紙條帶進(jìn)考場(chǎng)，因此當你閱讀考卷時(shí)，一旦有了思路就快速記下。按自己的步調進(jìn)行答卷。為每個(gè)考題或部分分配合理時(shí)間，并按此時(shí)間安排進(jìn)行。

　　六、對社會(huì )助學(xué)的要求

　　1.社會(huì )助學(xué)指導教師應熟悉本大綱所要求的內容、考核知識點(diǎn)和考核要求，輔導內容必須以本大綱為依據。切實(shí)作好對自學(xué)應考者的輔導，防止自學(xué)中的各種偏向，把握社會(huì )助學(xué)的正確導向。

　　2.注意自學(xué)考試的特點(diǎn)，命題將覆蓋各章，特別是本大綱規定的重點(diǎn)和次重點(diǎn)，不可隨意增刪和圈定重點(diǎn)以免導向失誤。本大綱課程內容和考核知識點(diǎn)不作要求的內容則不考。

　　3.注意培養考生的自學(xué)能力和分析、設計及應用的能力，努力引導自學(xué)應考者將識記、領(lǐng)會(huì )與應用聯(lián)系起來(lái)，把知識和理論轉化為能力。著(zhù)重培養和提高自學(xué)應考者的分析問(wèn)題和解決問(wèn)題的能力。

　　4.建議課程學(xué)習和實(shí)驗同步進(jìn)行。實(shí)驗可以在主考學(xué)校，也可在有條件的地方進(jìn)行。在實(shí)驗中，指導教師對考生遇到的實(shí)際問(wèn)題應及時(shí)進(jìn)行具體的幫助。

　　七、對考核內容的說(shuō)明

　　1. 本課程要求考生學(xué)習和掌握的知識點(diǎn)內容都作為考核的內容。課程中各章的內容均由若干知識點(diǎn)組成，在自學(xué)考試中成為考核知識點(diǎn)。因此，課程自學(xué)考試大綱中所規定的考試內容是以分解為考核知識點(diǎn)的方式給出的。由于各知識點(diǎn)在課程中的地位、作用以及知識自身的特點(diǎn)不同，自學(xué)考試將對各知識點(diǎn)分別按三個(gè)或四個(gè)認知(或叫能力)層次確定其考核要求。

　　八、關(guān)于考試命題的若干規定

　　1、考試采用閉卷方式，考試時(shí)間為150分鐘。試卷一律用鋼筆或圓珠筆書(shū)寫(xiě)，作圖可用鉛筆和直尺�？蓭�普通計算器。

　　2、本大綱各章所規定的基本要求、知識點(diǎn)及知識點(diǎn)下的知識細目，都屬于考核的內容�？荚嚸�題既要覆蓋到章，并適當突出課程的重點(diǎn)和章節重點(diǎn)，加大重點(diǎn)內容的覆蓋密度。

　　3、命題不應有超出大綱中考核知識點(diǎn)范圍的題目，考核目標不得高于大綱中所規定的相應的最高能力層次要求。命題應著(zhù)重考核自學(xué)者對基本概念、基本知識和基本理論是否了解或掌握，對基本方法是否會(huì )用或熟練。

　　4、本課程在試卷中對不同能力層次要求的分數比例大致為：識記占20%，領(lǐng)會(huì )占30%，簡(jiǎn)單應用占30%，綜合應用占20%(注：不同專(zhuān)業(yè)、不同課程在具體規定上可有所區別)。

　　5、要合理安排試題的難易程度，試題的難度可分為：易、較易、較難和難四個(gè)等級。每份試卷中不同難度試題的分數比例一般為：20:40:25:15。

　　必須注意試題的難易程度與能力層次有一定的聯(lián)系，但二者不是等同的概念。在各個(gè)能力層次中對于不同的考生都存在著(zhù)不同的難度。在大綱中已特別強調這個(gè)問(wèn)題，考生切勿混淆。

　　6、本課程考試命題的主要題型可能有單項選擇題、多項選擇題、填空題、名詞解釋題、簡(jiǎn)答題、應用題等。

　　在命題工作中必須按照本課程大綱中所規定的題型命制，考試試卷使用的題型可以略少，但不能超出本課程對題型規定。、

　　附錄 題型舉例

　　一、單項選擇題

　　1.一個(gè)按行存儲的對稱(chēng)矩陣，采用壓縮存儲只存下三角，首地址是100，每個(gè)元素占2個(gè)字節，第3行，第5列的元素地址是( )

　　A) 122 B)124 C) 128 D)不存在

　　2.設棧S和隊列Q的初始狀態(tài)均為空，元素X1、X2、X3、X4、X5、X6依次入棧，出棧的元素則進(jìn)入隊列Q，若元素的出列順序為X3、X2、X5、X6、X4、X1，則棧的容量至少( )。

　　A)2 B) 3 C)4 D) 5

　　二、多項選擇題

　　1.以下哪些特征是算法的基本特征( )

　　A)簡(jiǎn)潔性 B)能行性 C)有窮性 D)魯棒性

　　2.產(chǎn)生死鎖的四個(gè)必要條件是：()

　　A)互斥 B)請求與保持

　　C)資源不可剝奪 D)循環(huán)等待

　　三、填空題

　　1.在無(wú)向圖中兩點(diǎn)間存在一條路徑，那么可以稱(chēng)該兩點(diǎn)的關(guān)系是______.

　　2.快速排序最壞情況的復雜度為_(kāi)_____.

　　四、名詞解釋題

　　1.完全二叉樹(shù)：

　　2. DBMS：

　　五、簡(jiǎn)答題

　　1.簡(jiǎn)述軟件開(kāi)發(fā)瀑布模型的幾個(gè)階段。

　　2.簡(jiǎn)述進(jìn)程的生命期的幾個(gè)階段。

　　六、 應用題

　　1. HASH函數為H(k)=k%7,HASH地址空間為0……6,采用溢出HASH表構造方式處理沖突,對關(guān)鍵字序列為100,20,21,35,3,78,99,45構造HASH表和溢出區。

　　2.寫(xiě)一個(gè)算法，將一個(gè)線(xiàn)性單鏈表逆轉