高綱1412

江蘇省高等教育自學考試大綱

02365　　計算機軟件基礎(chǔ)（二）

南京理工大學編

江蘇省高等教育自學考試委員會辦公室

Ⅰ  課程性質(zhì)與課程目標

一、課程性質(zhì)和特點

《計算機軟件基礎(chǔ)（二）》是江蘇省高等教育自學考試電子類專業(yè)的必修課，是為了培養(yǎng)和檢驗自學應(yīng)考者對于計算機軟件技術(shù)的基本知識和基本技能而設(shè)置的一門專業(yè)課程。

隨著計算機軟件技術(shù)的飛速發(fā)展，對于電類平臺幾乎所有專業(yè)都會涉及計算機軟件技術(shù)，各種產(chǎn)品、對于計算機軟件也都有所涉及，在這種形勢下，電類及其相關(guān)專業(yè)的學生了解和掌握基本的計算機軟件技術(shù)知識是十分必要的。

本課程即主要介紹計算機軟件技術(shù)的基本知識、基本原理和基本算法,為電類平臺的電氣、自動化等相關(guān)專業(yè)的學生進一步學習后續(xù)課程打下基礎(chǔ)。

二、課程目標

通過本課程的學習，使自學應(yīng)考者能夠掌握計算機軟件技術(shù)的基本概念和基本原理，能夠應(yīng)用計算機軟件技術(shù)的基本原理和方法對計算機軟件進行簡單的程序設(shè)計，在操作系統(tǒng)上進行軟件應(yīng)用設(shè)計，如：數(shù)據(jù)庫設(shè)計等等。同時能夠?qū)浖夹g(shù)的新研究成果與發(fā)展趨勢有所了解，以適應(yīng)現(xiàn)代社會對計算機軟件技術(shù)越來越高的要求。

三、與相關(guān)課程的聯(lián)系與區(qū)別

本課程應(yīng)具備C或C++計算機程序設(shè)計等學科的知識基礎(chǔ)。

四、課程的重點和難點

課程的重點及難點參見各章節(jié)。

Ⅱ  考核目標

本大綱在考核目標中，按照識記、領(lǐng)會、應(yīng)用三個層次規(guī)定其應(yīng)達到的能力層次要求。三個能力層次是遞升的關(guān)系，后者必須建立在前者的基礎(chǔ)上。各能力層次的含義是：

識記（Ⅰ）：要求考生能夠識別和記憶本課程中有關(guān)概念及規(guī)律的主要內(nèi)容（如名詞解釋、原理、性質(zhì)、重要結(jié)論、方法及特征、特點等），并能夠根據(jù)考核的不同要求，做正確的表述、選擇和判斷。

領(lǐng)會（Ⅱ）：要求考生能夠領(lǐng)悟和理解本課程中有關(guān)概念及方法的作用、應(yīng)用場合、理解其原理、理解其與相關(guān)知識的區(qū)別和聯(lián)系。

應(yīng)用（Ⅲ）：要求考生能夠根據(jù)已知的知識、運用該方法進行算法設(shè)計、數(shù)據(jù)庫設(shè)計等基本設(shè)計。應(yīng)用包括簡單應(yīng)用和綜合應(yīng)用，簡單應(yīng)用是指能夠復現(xiàn)書本上的應(yīng)用實例以及習題實例，綜合應(yīng)用是指能夠根據(jù)要求進行綜合性的設(shè)計。

Ⅲ  課程內(nèi)容與考核要求

第一章  預備知識

一、學習目的與要求

通過本章的學習，了解集合的基本概念、性質(zhì)；了解算法的基本概念、性質(zhì)；學會算法時間復雜度分析。

二、課程內(nèi)容

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

三、考核知識點與考核要求

1集合

識記：（1）集合的基本概念

     （2）映射

     （3）自然數(shù)集與數(shù)學歸納法

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

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

     （3）集合的并、交、差運算

     （4）笛卡爾集

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

應(yīng)用：無

        2算法

識記：（1）算法的定義

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

     （3）常見的六種算法（列舉法、歸納法、遞推、遞歸、減半遞推、回溯）

     （4）算法的空間復雜度

領(lǐng)會：（1）算法的時間復雜度分析

應(yīng)用：無        

四、本章重點、難點

重點：集合的基本運算、算法的定義、算法的時間復雜度分析。

第二章  基本數(shù)據(jù)結(jié)構(gòu)及其運算

一、學習目的與要求

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

二、課程內(nèi)容

本章介紹了基本數(shù)據(jù)結(jié)構(gòu)中的線性結(jié)構(gòu)、樹狀結(jié)構(gòu)、圖結(jié)構(gòu)及其基本運算。

三、考核知識點與考核要求

1數(shù)據(jù)結(jié)構(gòu)的基本概念

識記：（1）數(shù)據(jù)結(jié)構(gòu)的定義

     （2）邏輯結(jié)構(gòu)是什么

     （3）存儲結(jié)構(gòu)是什么

領(lǐng)會：（1）數(shù)據(jù)結(jié)構(gòu)的圖形表示

     （2）線性結(jié)構(gòu)的條件

        2線性表及其順序存儲結(jié)構(gòu)

            識記：（1）什么是線性表

            領(lǐng)會：（1）線性表的順序存儲

                 （2）什么是堆棧

                 （3）什么是隊列

            應(yīng)用：（1）線性表在順序存儲下的插入運算

                 （2）線性表在順序存儲下的刪除運算

                 （3）堆棧的應(yīng)用

                 （4）隊列的應(yīng)用

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

        3線性鏈表

            識記：（1）線性鏈表的基本概念

            領(lǐng)會：（1）鏈表下的堆棧

                 （2）鏈表下的隊列

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

            應(yīng)用：（1）線性鏈表的插入運算

                 （2）線性鏈表的刪除運算

        4線性表的索引存儲結(jié)構(gòu)

            不作要求

        5數(shù)組                 

            領(lǐng)會：（1）二維數(shù)組行為主的順序存儲

（2）二維數(shù)組列為主的順序存儲

                 （3）下三角矩陣壓縮存儲

                 （4）對稱矩陣壓縮存儲

                 （5）三角矩陣壓縮存儲

                 （6）一般稀疏矩陣的表示

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

                 （8）十字鏈表的表示

        6樹與二叉樹

            識記：（1）樹的概念

                 （2）樹結(jié)構(gòu)的基本術(shù)語

                 （3）二叉樹的概念

                 （4）滿二叉樹的概念

                 （5）完全二叉樹的概念

            領(lǐng)會：（1）二叉樹的基本性質(zhì)

                 （2）二叉樹的存儲結(jié)構(gòu)

                 （3）有序樹的二叉樹表示

                 （4）表達式的線性化

            應(yīng)用：（1）二叉樹的遍歷（前序，中序，后序）

        7圖

            識記：（1）圖的基本概念

            領(lǐng)會：（1）圖的關(guān)聯(lián)矩陣存儲結(jié)構(gòu)

                 （2）圖的鄰接表存儲結(jié)構(gòu)

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

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

四、本章重點、難點

重點：線性結(jié)構(gòu)的插入、刪除、查找；堆棧的應(yīng)用；隊列的應(yīng)用；二叉樹的性質(zhì)；二叉樹的遍歷；圖的遍歷。

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

一、學習目的與要求

通過本章的學習，了解查找和排序的基本算法。

二、課程內(nèi)容

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

三、考核知識點與考核要求

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

領(lǐng)會：（1）順序查找

     （2）分塊查找

            應(yīng)用：（1）有序表的對分查找

        2.哈希表技術(shù)

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

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

                 （3）哈希表的構(gòu)造

            應(yīng)用：（1）幾種常用的哈希表

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

應(yīng)用：（1）冒泡排序和快速排序

                 （2）簡單插入排序與希爾排序

                 （3）簡單選擇排序與堆排序

                 （4）歸并排序

                 （5）基數(shù)排序

        4.二叉排序樹及其查找

識記：（1）二叉排序樹的基本概念

應(yīng)用：（1）二叉排序樹的插入

     （2）二叉排序樹的刪除

     （3）二叉排序樹的查找

        5. 多層索引樹及其查找

            不作要求

四、本章重點、難點

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

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

一、學習目的與要求

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

二、課程內(nèi)容

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

三、考核知識點與考核要求

1.操作系統(tǒng)的概念

識記：（1）操作系統(tǒng)的功能與任務(wù)

     （2）操作系統(tǒng)的發(fā)展過程

     （3）操作系統(tǒng)的分類

2.多道程序設(shè)計

識記：（1）進程的基本概念

     （2）進程控制塊及其組織

     （3）多道程序的組織

領(lǐng)會：（1）進程的狀態(tài)及其轉(zhuǎn)化

                 （2）死鎖問題

            應(yīng)用：（1）進程間的同步與互斥

                 （2）P/V操作

3.存儲空間的組織

            識記：（1）存儲管理的功能

                 （2）文件的邏輯結(jié)構(gòu)

                 （3）文件的物理結(jié)構(gòu)

                 （4）文件的目錄結(jié)構(gòu)

                 （5）文件空閑區(qū)的組織

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

                 （2）分段存儲管理       

            應(yīng)用：（1）分頁存儲管理

    四、本章重點、難點

重點：P/V操作，分頁存儲管理。

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

一、學習目的與要求

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

二、課程內(nèi)容

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

三、考核知識點與考核要求

1.數(shù)據(jù)庫基本概念

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

                 （2）數(shù)據(jù)庫管理系統(tǒng)

                 （3）數(shù)據(jù)庫系統(tǒng)的構(gòu)成

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

                 （2）實體間的聯(lián)系

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

2.關(guān)系代數(shù) 

應(yīng)用：（1）關(guān)系代數(shù)中的各種運算

3.數(shù)據(jù)庫設(shè)計

識記：（1）數(shù)據(jù)庫設(shè)計的基本概念

                 （2）數(shù)據(jù)庫設(shè)計的過程

                 （3）數(shù)據(jù)字典

            應(yīng)用：（1）概念結(jié)構(gòu)的設(shè)計

四、本章重點、難點

重點：關(guān)系代數(shù)中的各種運算、數(shù)據(jù)庫概念結(jié)構(gòu)設(shè)計（E-R）圖

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

一、學習目的與要求

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

二、課程內(nèi)容

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

三、考核知識點與考核要求

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

識記：（1）編譯的過程

                 （2）編譯程序的基本組成

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

            不作要求

3.詞法分析

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

        4.中間語言表示

不作要求

        5.語法的分析與加工

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

四、本章重點、難點

重點：編譯的過程

       第七章  應(yīng)用軟件設(shè)計與開發(fā)技術(shù)

一、學習目的與要求

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

二、課程內(nèi)容

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

三、考核知識點與考核要求

1.軟件工程概述

            識記：（1）軟件工程的概念

                 （2）軟件的生命周期

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

2.軟件詳細設(shè)計的表達

識記：（1）程序流程圖

                 （2）NS圖

        3.結(jié)構(gòu)化分析與設(shè)計方法

識記：（1）應(yīng)用軟件開發(fā)的基本原則

     （2）應(yīng)用軟件的開發(fā)方法

            領(lǐng)會：（1）結(jié)構(gòu)化的分析方法

                 （2）數(shù)據(jù)流程圖

                 （3）結(jié)構(gòu)化的設(shè)計方法

                 （4）模塊獨立性評價     

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

識記：（1）測試的基本概念

     （2）測試的三個特征

     （3）測試的過程

     （4）測試的層次

            領(lǐng)會：（1）測試的方法

                 （2）調(diào)試與測試的關(guān)系

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

領(lǐng)會：（1）原形方法

                 （2）瀑布模型

                 （3）面向?qū)ο蟮姆椒?/p>

        四、本章重點、難點

重點：結(jié)構(gòu)化的分析和設(shè)計方法。

Ⅳ  關(guān)于大綱的說明與考核實施要求

一、自學考試大綱的目的和作用

課程自學考試大綱是根據(jù)專業(yè)自學考試計劃的要求，結(jié)合自學考試的特點而確定。其目的是對個人自學、社會助學和課程考試命題進行指導和規(guī)定。

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

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

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

大綱與教材所體現(xiàn)的課程內(nèi)容應(yīng)基本一致；本大綱的課程內(nèi)容和考核知識點是與所選教材一致的。所選教材里的部分內(nèi)容，本大綱不作考核要求。（注：其中的內(nèi)容與大綱要求不一致的地方，以大綱規(guī)定為準。）

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

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

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

本大綱的課程基本要求是依據(jù)專業(yè)考試計劃和專業(yè)培養(yǎng)目標而確定的。課程基本要求還明確了課程的基本內(nèi)容，以及對基本內(nèi)容掌握的程度?；疽笾械闹R點構(gòu)成了課程內(nèi)容的主體部分。因此，課程基本內(nèi)容掌握程度、課程考核知識點是高等教育自學考試考核的主要內(nèi)容。

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

《計算機軟件基礎(chǔ)（二）》課程內(nèi)容涉及面較寬，涉及到數(shù)據(jù)結(jié)構(gòu)、算法、操作系統(tǒng)、數(shù)據(jù)庫技術(shù)、軟件工程等許多方面?？忌谧詫W時往往會感到有一定困難，但自學能力的培養(yǎng)對獲取知識是非常必要的。在自學過程中應(yīng)注意以下幾點：

1．根據(jù)考核要求中的四個能力層次，在全面系統(tǒng)學習的基礎(chǔ)上掌握重點概念和重點問題，如數(shù)據(jù)結(jié)構(gòu)的基本特性、線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)等，注意各章內(nèi)容之間的內(nèi)在聯(lián)系。

2．本課程的自學考試大綱是自學本課程的主要依據(jù)。在自學本課程前應(yīng)先通讀大綱，了解課程的要求，獲得課程完整的概貌。在開始自學某一章時，先閱讀大綱，了解該章的課程內(nèi)容，考核知識點和考核要求，在自學過程中就有的放矢。

3．閱讀教材時，要求吃透每個考核知識點。對基本概念要做到深刻理解，對基本原理要弄清弄懂，對基本方法要熟練掌握。

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

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

6．考生在自學時要注意基本能力的培養(yǎng)，即系統(tǒng)分析和綜合的能力，分析問題和理解知識的能力，抓住重點闡述問題的能力，以及實驗?zāi)芰Φ取?/p>

五、應(yīng)考指導

1. 如何學習

很好的計劃和組織是你學習成功的法寶。…如果你正在接受培訓學習，一定要跟緊課程并完成作業(yè)?！瓰榱嗽诳荚囍凶鞒鰸M意的回答，你必須對所學課程內(nèi)容有很好的理解?！褂谩靶袆佑媱澅怼眮肀O(jiān)控你的學習進展?！汩喿x課本時可以做讀書筆記。如有需要重點注意的內(nèi)容，可以用彩筆來標注。如：紅色代表重點；綠色代表需要深入研究的領(lǐng)域；黃色代表可以運用在工作之中?？梢栽诳瞻滋幱涗浵嚓P(guān)網(wǎng)站，文章。

2. 如何考試

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

3. 如何處理緊張情緒 

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

4. 如何克服心理障礙

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

六、對社會助學的要求

    1．社會助學指導教師應(yīng)熟悉本大綱所要求的內(nèi)容、考核知識點和考核要求，輔導內(nèi)容必須以本大綱為依據(jù)。切實作好對自學應(yīng)考者的輔導，防止自學中的各種偏向，把握社會助學的正確導向。

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

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

    4．建議課程學習和實驗同步進行。實驗可以在主考學校，也可在有條件的地方進行。在實驗中，指導教師對考生遇到的實際問題應(yīng)及時進行具體的幫助。

七、對考核內(nèi)容的說明

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

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

1、考試采用閉卷方式，考試時間為150分鐘。試卷一律用鋼筆或圓珠筆書寫，作圖可用鉛筆和直尺?？蓭胀ㄓ嬎闫?。

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

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

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

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

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

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

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

附錄  題型舉例

 一、單項選擇題

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

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

   2.設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素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．產(chǎn)生死鎖的四個必要條件是：（ ）

  A）互斥                      B）請求與保持

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

  三、填空題

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

  2.快速排序最壞情況的復雜度為______.

  四、名詞解釋題

  1．完全二叉樹：

  2． DBMS：

  五、簡答題

 1．簡述軟件開發(fā)瀑布模型的幾個階段。

  2．簡述進程的生命期的幾個階段。

六、 應(yīng)用題

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

  2.寫一個算法，將一個線性單鏈表逆轉(zhuǎn)