02365 計算機軟件基礎（二）

高綱1412江蘇省高等教育自學考試大綱02365　　計算機軟件基礎（二）　　　　　　　　　　　　　　　南京理工大學編江蘇省高等教育自學考試委員會辦公室

Ⅰ 課程性質與課程目標一、課程性質和特點《計算機軟件基礎（二）》是江蘇省高等教育自學考試電子類專業的必修課，是為了培養和檢驗自學應考者對于計算機軟件技術的基本知識和基本技能而設置的一門專業課程。隨著計算機軟件技術的飛速發展，對于電類平臺幾乎所有專業都會涉及計算機軟件技術，各種產品、對于計算機軟件也都有所涉及，在這種形勢下，電類及其相關專業的學生了解和掌握基本的計算機軟件技術知識是十分必要的。本課程即主要介紹計算機軟件技術的基本知識、基本原理和基本算法,為電類平臺的電氣、自動化等相關專業的學生進一步學習后續課程打下基礎。二、課程目標通過本課程的學習，使自學應考者能夠掌握計算機軟件技術的基本概念和基本原理，能夠應用計算機軟件技術的基本原理和方法對計算機軟件進行簡單的程序設計，在操作系統上進行軟件應用設計，如：數據庫設計等等。同時能夠對軟件技術的新研究成果與發展趨勢有所了解，以適應現代社會對計算機軟件技術越來越高的要求。三、與相關課程的聯系與區別本課程應具備C或C++計算機程序設計等學科的知識基礎。四、課程的重點和難點課程的重點及難點參見各章節。Ⅱ 考核目標本大綱在考核目標中，按照識記、領會、應用三個層次規定其應達到的能力層次要求。三個能力層次是遞升的關系，后者必須建立在前者的基礎上。各能力層次的含義是：識記（Ⅰ）：要求考生能夠識別和記憶本課程中有關概念及規律的主要內容（如名詞解釋、原理、性質、重要結論、方法及特征、特點等），并能夠根據考核的不同要求，做正確的表述、選擇和判斷。領會（Ⅱ）：要求考生能夠領悟和理解本課程中有關概念及方法的作用、應用場合、理解其原理、理解其與相關知識的區別和聯系。應用（Ⅲ）：要求考生能夠根據已知的知識、運用該方法進行算法設計、數據庫設計等基本設計。應用包括簡單應用和綜合應用，簡單應用是指能夠復現書本上的應用實例以及習題實例，綜合應用是指能夠根據要求進行綜合性的設計。Ⅲ 課程內容與考核要求第一章 預備知識一、學習目的與要求通過本章的學習，了解集合的基本概念、性質；了解算法的基本概念、性質；學會算法時間復雜度分析。二、課程內容本章介紹了集合的基本概念、性質；算法的基本概念、性質；以及算法時空復雜度分析。為以后章節的學習打下了基礎。三、考核知識點與考核要求1集合識記：（1）集合的基本概念（2）映射（3）自然數集與數學歸納法領會：（1）列舉法表示集合（2）性質敘述法表示集合（3）集合的并、交、差運算（4）笛卡爾集（5）二元關系應用：無2算法識記：（1）算法的定義（2）算法的四個基本性質（能行性、確定性、有窮性、擁有足夠情報）（3）常見的六種算法（列舉法、歸納法、遞推、遞歸、減半遞推、回溯）（4）算法的空間復雜度領會：（1）算法的時間復雜度分析應用：無 四、本章重點、難點重點：集合的基本運算、算法的定義、算法的時間復雜度分析。第二章 基本數據結構及其運算一、學習目的與要求通過本章的學習，基本數據結構中的線性結構、樹狀結構、圖結構及其基本運算，能夠區分基本數據結構，能夠根據基本數據結構的性質描述數據，能夠使用基本數據結構設計簡單算法解決實際問題。二、課程內容本章介紹了基本數據結構中的線性結構、樹狀結構、圖結構及其基本運算。三、考核知識點與考核要求1數據結構的基本概念識記：（1）數據結構的定義（2）邏輯結構是什么（3）存儲結構是什么領會：（1）數據結構的圖形表示（2）線性結構的條件2線性表及其順序存儲結構識記：（1）什么是線性表領會：（1）線性表的順序存儲（2）什么是堆棧（3）什么是隊列應用：（1）線性表在順序存儲下的插入運算（2）線性表在順序存儲下的刪除運算（3）堆棧的應用（4）隊列的應用（5）循環隊列3線性鏈表識記：（1）線性鏈表的基本概念領會：（1）鏈表下的堆棧（2）鏈表下的隊列（3）循環鏈表應用：（1）線性鏈表的插入運算（2）線性鏈表的刪除運算4線性表的索引存儲結構不作要求5數組 領會：（1）二維數組行為主的順序存儲（2）二維數組列為主的順序存儲（3）下三角矩陣壓縮存儲（4）對稱矩陣壓縮存儲（5）三角矩陣壓縮存儲（6）一般稀疏矩陣的表示（7）稀疏矩陣的三列二維數組表示（8）十字鏈表的表示6樹與二叉樹識記：（1）樹的概念（2）樹結構的基本術語（3）二叉樹的概念（4）滿二叉樹的概念（5）完全二叉樹的概念領會：（1）二叉樹的基本性質（2）二叉樹的存儲結構（3）有序樹的二叉樹表示（4）表達式的線性化應用：（1）二叉樹的遍歷（前序，中序，后序）7圖識記：（1）圖的基本概念領會：（1）圖的關聯矩陣存儲結構（2）圖的鄰接表存儲結構應用：（1）圖的縱向優先搜索遍歷（3）圖的橫向優先搜索遍歷四、本章重點、難點重點：線性結構的插入、刪除、查找；堆棧的應用；隊列的應用；二叉樹的性質；二叉樹的遍歷；圖的遍歷。第三章 查找與排序技術一、學習目的與要求通過本章的學習，了解查找和排序的基本算法。二、課程內容本章介紹了查找和排序的基本算法。三、考核知識點與考核要求1.基本的查找技術領會：（1）順序查找（2）分塊查找應用：（1）有序表的對分查找2.哈希表技術領會：（1）直接查找技術（2）哈希表技術（3）哈希表的構造應用：（1）幾種常用的哈希表3.基本的排序技術應用：（1）冒泡排序和快速排序（2）簡單插入排序與希爾排序（3）簡單選擇排序與堆排序（4）歸并排序（5）基數排序4.二叉排序樹及其查找識記：（1）二叉排序樹的基本概念應用：（1）二叉排序樹的插入（2）二叉排序樹的刪除（3）二叉排序樹的查找5. 多層索引樹及其查找不作要求四、本章重點、難點重點：哈希表技術，基本排序技術，二叉排序樹的查找，插入與刪除第四章 資源管理技術一、學習目的與要求通過本章的學習，掌握操作系統的原理、基本概念及常用方法。二、課程內容本章介紹了操作系統的原理、基本概念及常用方法，重點介紹了多道程序設計和存儲空間的組織。三、考核知識點與考核要求1.操作系統的概念識記：（1）操作系統的功能與任務（2）操作系統的發展過程（3）操作系統的分類2.多道程序設計識記：（1）進程的基本概念（2）進程控制塊及其組織（3）多道程序的組織領會：（1）進程的狀態及其轉化（2）死鎖問題應用：（1）進程間的同步與互斥（2）P/V操作3.存儲空間的組織識記：（1）存儲管理的功能（2）文件的邏輯結構（3）文件的物理結構（4）文件的目錄結構（5）文件空閑區的組織領會：（1）界地址存儲管理（2）分段存儲管理應用：（1）分頁存儲管理四、本章重點、難點重點：P/V操作，分頁存儲管理。第五章 數據庫設計技術一、學習目的與要求通過本章的學習，掌握數據庫設計的原理、關系代數及數據庫設計過程。二、課程內容本章介紹了數據庫設計的原理、關系代數及數據庫設計過程。三、考核知識點與考核要求1.數據庫基本概念識記：（1）數據庫管理技術（2）數據庫管理系統（3）數據庫系統的構成領會：（1）信息的存在形態（2）實體間的聯系（3）數據模型（層次模型，網狀模型，關系模型）2.關系代數應用：（1）關系代數中的各種運算3.數據庫設計識記：（1）數據庫設計的基本概念（2）數據庫設計的過程（3）數據字典應用：（1）概念結構的設計四、本章重點、難點重點：關系代數中的各種運算、數據庫概念結構設計（E-R）圖第六章 編譯技術概述一、學習目的與要求通過本章的學習，了解編譯技術的基本原理。二、課程內容本章介紹了編譯技術的工作過程、詞法分析、語法加工等內容。三、考核知識點與考核要求1.編譯程序的工作過程及其基本組成識記：（1）編譯的過程（2）編譯程序的基本組成2.狀態矩陣法的編譯過程不作要求3.詞法分析識記：（1）詞法分析的任務4.中間語言表示不作要求5.語法的分析與加工識記：（1）語法分析和加工的主要任務四、本章重點、難點重點：編譯的過程第七章 應用軟件設計與開發技術一、學習目的與要求通過本章的學習，掌握軟件工程的概念、生命周期及常用方法。二、課程內容本章介紹了軟件工程的概念、生命周期及常用方法。三、考核知識點與考核要求1.軟件工程概述識記：（1）軟件工程的概念（2）軟件的生命周期（3）軟件的支撐環境2.軟件詳細設計的表達識記：（1）程序流程圖（2）NS圖3.結構化分析與設計方法識記：（1）應用軟件開發的基本原則（2）應用軟件的開發方法領會：（1）結構化的分析方法（2）數據流程圖（3）結構化的設計方法（4）模塊獨立性評價 4.測試與調試基本技術識記：（1）測試的基本概念（2）測試的三個特征（3）測試的過程（4）測試的層次領會：（1）測試的方法（2）調試與測試的關系5.軟件開發新技術領會：（1）原形方法（2）瀑布模型（3）面向對象的方法四、本章重點、難點重點：結構化的分析和設計方法。Ⅳ 關于大綱的說明與考核實施要求一、自學考試大綱的目的和作用課程自學考試大綱是根據專業自學考試計劃的要求，結合自學考試的特點而確定。其目的是對個人自學、社會助學和課程考試命題進行指導和規定。課程自學考試大綱明確了課程學習的內容以及深廣度，規定了課程自學考試的范圍和標準。因此，它是編寫自學考試教材和輔導書的依據，是社會助學組織進行自學輔導的依據，是自學者學習教材、掌握課程內容知識范圍和程度的依據，也是進行自學考試命題的依據。二、課程自學考試大綱與教材的關系課程自學考試大綱是進行學習和考核的依據，教材是學習掌握課程知識的基本內容與范圍，教材的內容是大綱所規定的課程知識和內容的擴展與發揮。課程內容在教材中可以體現一定的深度或難度，本大綱中對考核的要求是按照本專業的培養目標，以及對考生知識結構要求和專業考試計劃來確定的，深度或難度較適當。大綱與教材所體現的課程內容應基本一致；本大綱的課程內容和考核知識點是與所選教材一致的。所選教材里的部分內容，本大綱不作考核要求。（注：其中的內容與大綱要求不一致的地方，以大綱規定為準。）三、關于自學教材自學教材：《計算機軟件技術基礎》（第三版），徐士良、葛兵等編著，清華大學出版社，2010年版。四、關于自學要求和自學方法的指導本大綱的課程基本要求是依據專業考試計劃和專業培養目標而確定的。課程基本要求還明確了課程的基本內容，以及對基本內容掌握的程度。基本要求中的知識點構成了課程內容的主體部分。因此，課程基本內容掌握程度、課程考核知識點是高等教育自學考試考核的主要內容。為有效地指導個人自學和社會助學，本大綱已指明了課程的重點和難點，在章節的基本要求中一般也指明了章節內容的重點和難點。《計算機軟件基礎（二）》課程內容涉及面較寬，涉及到數據結構、算法、操作系統、數據庫技術、軟件工程等許多方面。考生在自學時往往會感到有一定困難，但自學能力的培養對獲取知識是非常必要的。在自學過程中應注意以下幾點：1．根據考核要求中的四個能力層次，在全面系統學習的基礎上掌握重點概念和重點問題，如數據結構的基本特性、線性結構、樹結構、圖結構等，注意各章內容之間的內在聯系。2．本課程的自學考試大綱是自學本課程的主要依據。在自學本課程前應先通讀大綱，了解課程的要求，獲得課程完整的概貌。在開始自學某一章時，先閱讀大綱，了解該章的課程內容，考核知識點和考核要求，在自學過程中就有的放矢。3．閱讀教材時，要求吃透每個考核知識點。對基本概念要做到深刻理解，對基本原理要弄清弄懂，對基本方法要熟練掌握。4．重視每章末的習題的作用，最好多做習題，可以幫助考生盡快地達到自考大綱的要求，并可以檢查學習掌握知識的程度。5．本課程是一門實踐性較強的課程，考生在自學過程中必須注意理論聯系實際，按實驗的目的、要求和內容認真做好實驗。建議實驗與課程自學過程同步進行。6．考生在自學時要注意基本能力的培養，即系統分析和綜合的能力，分析問題和理解知識的能力，抓住重點闡述問題的能力，以及實驗能力等。五、應考指導1. 如何學習很好的計劃和組織是你學習成功的法寶。…如果你正在接受培訓學習，一定要跟緊課程并完成作業。…為了在考試中作出滿意的回答，你必須對所學課程內容有很好的理解。…使用“行動計劃表”來監控你的學習進展。…你閱讀課本時可以做讀書筆記。如有需要重點注意的內容，可以用彩筆來標注。如：紅色代表重點；綠色代表需要深入研究的領域；黃色代表可以運用在工作之中。可以在空白處記錄相關網站，文章。2. 如何考試卷面整潔非常重要。書寫工整，段落與間距合理，卷面賞心悅目有助于教師評分，教師只能為他能看懂的內容打分。回答所提出的問題。要回答所問的問題，而不是回答你自己樂意回答的問題！避免超過問題的范圍3. 如何處理緊張情緒正確處理對失敗的懼怕，要正面思考。如果可能，請教已經通過該科目考試的人，問他們一些問題。做深呼吸放松，這有助于使頭腦清醒，緩解緊張情緒。考試前合理膳食，保持旺盛精力，保持冷靜。4. 如何克服心理障礙這是一個普遍問題！如果你在考試中出現這種情況，試試下列方法：使用“線索”紙條。進入考場之前，將記憶“線索”記在紙條上，但你不能將紙條帶進考場，因此當你閱讀考卷時，一旦有了思路就快速記下。按自己的步調進行答卷。為每個考題或部分分配合理時間，并按此時間安排進行。六、對社會助學的要求1．社會助學指導教師應熟悉本大綱所要求的內容、考核知識點和考核要求，輔導內容必須以本大綱為依據。切實作好對自學應考者的輔導，防止自學中的各種偏向，把握社會助學的正確導向。2．注意自學考試的特點，命題將覆蓋各章，特別是本大綱規定的重點和次重點，不可隨意增刪和圈定重點以免導向失誤。本大綱課程內容和考核知識點不作要求的內容則不考。3．注意培養考生的自學能力和分析、設計及應用的能力，努力引導自學應考者將識記、領會與應用聯系起來，把知識和理論轉化為能力。著重培養和提高自學應考者的分析問題和解決問題的能力。4．建議課程學習和實驗同步進行。實驗可以在主考學校，也可在有條件的地方進行。在實驗中，指導教師對考生遇到的實際問題應及時進行具體的幫助。七、對考核內容的說明1. 本課程要求考生學習和掌握的知識點內容都作為考核的內容。課程中各章的內容均由若干知識點組成，在自學考試中成為考核知識點。因此，課程自學考試大綱中所規定的考試內容是以分解為考核知識點的方式給出的。由于各知識點在課程中的地位、作用以及知識自身的特點不同，自學考試將對各知識點分別按三個或四個認知（或叫能力）層次確定其考核要求。八、關于考試命題的若干規定1、考試采用閉卷方式，考試時間為150分鐘。試卷一律用鋼筆或圓珠筆書寫，作圖可用鉛筆和直尺。可帶普通計算器。2、本大綱各章所規定的基本要求、知識點及知識點下的知識細目，都屬于考核的內容。考試命題既要覆蓋到章，并適當突出課程的重點和章節重點，加大重點內容的覆蓋密度。3、命題不應有超出大綱中考核知識點范圍的題目，考核目標不得高于大綱中所規定的相應的最高能力層次要求。命題應著重考核自學者對基本概念、基本知識和基本理論是否了解或掌握，對基本方法是否會用或熟練。4、本課程在試卷中對不同能力層次要求的分數比例大致為：識記占20%，領會占30%，簡單應用占30%，綜合應用占20%（注：不同專業、不同課程在具體規定上可有所區別）。5、要合理安排試題的難易程度，試題的難度可分為：易、較易、較難和難四個等級。每份試卷中不同難度試題的分數比例一般為：20:40:25:15。必須注意試題的難易程度與能力層次有一定的聯系，但二者不是等同的概念。在各個能力層次中對于不同的考生都存在著不同的難度。在大綱中已特別強調這個問題，考生切勿混淆。6、本課程考試命題的主要題型可能有單項選擇題、多項選擇題、填空題、名詞解釋題、簡答題、應用題等。在命題工作中必須按照本課程大綱中所規定的題型命制，考試試卷使用的題型可以略少，但不能超出本課程對題型規定。、附錄 題型舉例一、單項選擇題1.一個按行存儲的對稱矩陣，采用壓縮存儲只存下三角，首地址是100，每個元素占2個字節，第3行，第5列的元素地址是（ ）A） 122 B）124 C） 128 D）不存在2.設棧S和隊列Q的初始狀態均為空，元素X1、X2、X3、X4、X5、X6依次入棧，出棧的元素則進入隊列Q，若元素的出列順序為X3、X2、X5、X6、X4、X1，則棧的容量至少（ ）。A）2 B） 3 C）4 D） 5二、多項選擇題1.以下哪些特征是算法的基本特征（ ）A)簡潔性 B)能行性 C)有窮性 D)魯棒性2．產生死鎖的四個必要條件是：（ ）A）互斥 B）請求與保持C）資源不可剝奪 D）循環等待三、填空題1.在無向圖中兩點間存在一條路徑，那么可以稱該兩點的關系是______.2.快速排序最壞情況的復雜度為______.四、名詞解釋題1．完全二叉樹：2． DBMS：五、簡答題1．簡述軟件開發瀑布模型的幾個階段。2．簡述進程的生命期的幾個階段。六、 應用題1. HASH函數為H（k）=k%7,HASH地址空間為0……6,采用溢出HASH表構造方式處理沖突,對關鍵字序列為100,20,21,35,3,78,99,45構造HASH表和溢出區。2.寫一個算法，將一個線性單鏈表逆轉