第壹章是概述
1.計算機中的數字和編碼系統
(1)理解計算機中數制的概念,並能應用;(2)掌握二進制編碼的方法;
(3)掌握二元運算的規則;(4)掌握有符號數的表示方法和範圍;
2.了解計算機硬件和軟件的劃分和功能。
3.微型計算機的結構
(1)了解微型計算機的外部結構;
(2)了解微型計算機的內部結構;
4.英特爾8088的結構
(1)掌握8088的寄存器結構;(2)掌握8088的功能結構;
(3)掌握記憶組織;
第二章8088指令系統
1.掌握8088的尋址方式。
(1)立即尋址(2)直接尋址(3)寄存器尋址(4)寄存器間接尋址(5)索引尋址(6)基址加索引的尋址方式。
2.控制8088標誌寄存器中的9個標誌位。
3.掌握8088的指令系統
(1)數據傳輸指令(2)算術運算指令(3)邏輯運算指令
第三章匯編語言程序設計
1.正確掌握匯編語言的格式;
2.理解語句行的構成,並加以運用;
3.理解指示性陳述並正確使用;
4.掌握基本匯編語言編程。
(1)循環編程(2)參數傳遞技術(3)子程序設計
第四章8088總線運行和定時
1.基本概念
(1)正確理解指令周期、總線周期、T狀態的概念;
(2)掌握CPU、內存、外設的時序概念;
2.8088路公交車
(1)掌握8088兩種配置的區別;
3.掌握8088的典型時序
(1)存儲器讀取周期(2)存儲器寫入周期(3)中斷響應周期
4.最高配置中的8088序列和最低配置中的8088序列之間的差異。
5.計數器和定時器電路Intel 8253-PIT
(1)了解8253-PIT芯片的主要功能和內部結構;(2)能寫8253-PIT的控制字;(3)掌握8253-PIT的工作模式;(4)掌握8253-PIT編程步驟;
第五章半導體存儲器
1.分解半導體存儲器的分類
2.讀寫內存RAM
(1)了解基本的存儲電路(2)了解RAM的結構(3)掌握RAM與CPU連接需要考慮的主要問題;尋址範圍將根據連接圖寫入。
第六章投入與產出
1.了解輸入輸出的尋址方式。
2.掌握CPU與外設之間的數據傳輸方式。
(1)無條件傳輸模式(2)查詢傳輸模式(3)中斷傳輸模式(4)直接數據通道傳輸(DMA)
第七章中斷
1.中斷介紹
(1)理解為什麽要使用中斷(2)掌握中斷系統的功能。
2.最簡單的中斷情況
(1)掌握CPU響應中斷的條件(2)掌握CPU對中斷的響應。
4.8088的中斷模式
(1)掌握兩條外部中斷請求線及其用法。
(2)掌握內部中斷類型號
(3)掌握8088中斷的優先級順序。
(4)掌握8088中斷向量表的大小、中斷向量的個數以及中斷入口地址的求解。
(5)掌握8088中的中斷響應和處理過程。
第八章並行接口芯片
1.了解可編程I/O接口芯片8255A-5的功能和結構。
2.掌握8255A各端口的工作方式和功能。
教材:《微機系統原理與應用》,周明德,清華大學出版社。
參考書:
1,微機原理與接口技術,李,主編,南開大學出版社,2001版?
2.《計算機電路基礎》,王金剛主編,南開大學出版社,2001版?
試題類型和分數分布:
本課程考試題型有填空題、分析程序題、簡答題和綜合應用題四種,其中填空題20分,分析程序題15分,簡答題20分,綜合應用題20分。
《數據結構》考試大綱
第壹章是緒論
壹、學習的目的和要求
本章的目的是介紹數據結構中常用的基本概念和術語以及學習數據結構的意義。
在本章中,我們應該理解數據的抽象類型定義。理解算法在實際問題中的應用。重點掌握各種基本概念和術語、算法描述和分析方法。
二、課程內容
第壹節什麽是數據結構
第二節基本概念和術語
第3節抽象數據類型的表示和實現
第四節算法及算法分析
三、考核知識點
1,恰當的數據結構在解決實際應用問題中的關鍵;以及學習數據結構的意義。
2.數據、數據元素、數據項和數據結構等基本概念。
3.數據結構的四種邏輯結構和存儲結構的兩種表示。
4.抽象數據類型的表示和實現
5.算法的五個特點。
6.算法的概念,算法的時間復雜度和空間復雜度,最壞和平均時間復雜度等。
7.算法描述和算法分析的方法可以分析壹般算法的時間復雜度。
四、評估要求
1.記憶
1)數據結構的基本概念和術語。
2)正確的數據結構在解決實際應用問題中的關鍵以及學習數據結構的意義。
3)數據結構的四種邏輯結構和兩種存儲結構。
理解
1)算法的描述與分析:算法的時間復雜度和空間復雜度,算法的最壞和平均時間復雜度。
第二章線性表
壹、學習的目的和要求
本章的目的是介紹線性表的邏輯結構和各種存儲表示,以及定義邏輯結構上的各種基本操作,以及如何在存儲結構上實現這些基本操作。要求在熟悉這些內容的基礎上,能夠根據具體應用問題的要求和性質,選擇合適的存儲結構,設計相應的有效算法,解決線性表相關的實際問題。
本章重點掌握在順序鏈表和單鏈表上實現的各種基本操作以及相關的時間性能分析。難點是循環鏈表和雙向鏈表存儲結構中各種基本操作的實現。
二、課程內容
第壹節線性表類型的定義
第二部分是線性表的順序表示和實現
第三節線性表的鏈表示和實現
三、考核知識點
1,線性表的類型定義
2.序列表的含義和特點,序列表上的插入和刪除操作及其平均時間性能分析。
3.鏈表的表示和實現,以及單鏈表、雙鏈表和循環鏈表的區別;
4.在單鏈表上實現的建表、查找、插入和刪除等基本算法及其時間復雜度。
5.循環鏈表上的尾指針代替了頭指針。
6.單循環鏈表上的算法和對應的單鏈表上的算法的異同。
7.雙向鏈表的定義及相關算法。
8.順序表和鏈表的比較,如何選擇壹個作為它的存儲結構可以達到更好的時空性能。
四、評估要求
1.記憶
1)線性表的邏輯結構特征;
2)定義在線性表上的基本運算,利用基本運算構造更復雜的運算。
理解
1)順序表和鏈表的比較,各自的優缺點。
2)對於需要在線性表上進行的主要操作,需要知道是選擇順序表還是鏈表作為其存儲結構,以達到更好的時空性能。
3.綜合應用
1)順序表的含義和特點,順序表上的插入和刪除操作及其平均時間性能分析。
2)單鏈表、雙鏈表和循環鏈表在鏈接方式上的區別;
3)在單鏈表上實現的建表、查找、插入、刪除等基本算法及其時間復雜度。
4)循環鏈表上的尾指針代替頭指針,
5)單循環鏈表上的算法與單鏈表上對應算法的異同。
6)雙向鏈表的定義及相關算法。
第三章堆棧和隊列
壹、學習的目的和要求
本章的目的是介紹棧和隊列的邏輯結構定義以及如何在兩種存儲結構上實現棧和隊列的基本操作。在掌握堆棧和隊列特性的基礎上,要求知道在什麽情況下使用堆棧或隊列。
本章重點是掌握棧和隊列在兩種存儲結構上的基本操作,難點是循環隊列中邊界條件的處理。
二、課程內容
第壹節堆棧
第二節堆棧的應用示例
第四節排隊
三、考核知識點
1.棧的抽象數據類型的定義
2.棧的表示和實現
3.堆棧的簡單應用
4.抽象數據類型隊列的定義
5.隊列的鏈表示和實現。
6.隊列的序列表示和實現
四、評估要求
1.
1)堆棧和隊列的特點,以及各自的用法。
2.綜合應用
1)棧的邏輯結構特點,棧與線性表的異同。
2)在順序棧和鏈式棧上實現了入棧和出棧等基本算法。
3)利用棧解決簡單的實際問題。
4)隊列邏輯結構的特點,隊列與線性表的異同。
5)在順序隊列(主要是循環隊列)和鏈式隊列上實現的入隊、出隊等基本算法。
6)順序隊列的“假溢出”現象及用循環隊列解決的方法。
第四章弦
壹、學習的目的和要求
本章的目的是介紹字符串的邏輯結構、存儲結構和基本操作。本章重點是掌握弦的基本概念和三種表示,這也是壹個難點。
二、課程內容
第1節字符串類型的定義
第二部分字符串的表示和實現
三、考核知識點
1,字符串定義,空字符串,空白字符串,子字符串,主字符串和字符串相等。
2.字符串的基本操作。
3.字符串的順序存儲結構和順序存儲結構下基本操作的實現。
4.字符串的堆分配存儲表示及其堆分配存儲結構下基本操作的實現。
5.字符串的鏈式存儲表示
四、評估要求
1.
1)字符串的相關概念和基本操作
2.簡單應用
1)字符串的三種存儲表示
2)使用字符串解決與字符串相關的簡單應用問題。
第五章數組和廣義表
壹、學習的目的和要求
本章的目的是介紹多維數組的邏輯結構特征及其存儲方法,特殊矩陣和稀疏矩陣的壓縮存儲方法,以及廣義表的概念,需要熟悉這些內容。
本章的重點是熟悉多維數組的存儲方式,矩陣的壓縮存儲方式,廣義表的定義及其頁眉頁腳的操作。難點是稀疏矩陣壓縮存儲表示下的轉置運算。
二、課程內容
第壹節數組的定義
第二節,數組的順序表示和實現
第三節矩陣的壓縮存儲
第四節廣義表的定義
第五節廣義表的存儲結構
三、考核知識點
1,數組的順序存儲結構。
2.按行存儲二維數組以及按列存儲和計算數組元素地址的公式。
3.矩陣的壓縮存儲和特殊矩陣的表示。
4.廣義表的定義和操作(頭尾)
5.廣義表的兩種存儲結構
四、評估要求
1.
1)多維數組邏輯結構特征
2)多維數組的順序存儲結構及其地址計算方法。
3)特殊矩陣和稀疏矩陣的概念。
4)稀疏矩陣的壓縮存儲模式——三元表。
5)稀疏矩陣的兩種轉置算法。
6)廣義表的概念以及廣義表與線性表的關系。
7)廣義表的表頭、表尾概念和廣義表的兩個特殊基本操作,取表頭、表尾。
8)廣義表的兩種存儲結構
第六章樹和二叉樹
壹、學習的目的和要求
本章的目的是介紹二叉樹的定義、性質、存儲結構、遍歷和線索,樹的定義、存儲結構、遍歷,樹與森林的轉換,Hoeffmann樹及其Huffman編碼等。本章著重於掌握二叉樹及其遍歷。難點在於掌握與樹相關的簡單應用。
二、課程內容
第壹節樹的定義和基本術語
第二節二叉樹
第三節遍歷二叉樹和線索二叉樹
第四節樹木和森林
第六節赫夫曼樹及其應用
三、考核知識點
1,樹的定義和術語。
2.二叉樹的定義和性質(完全二叉樹和全二叉樹)(結論),二叉樹的存儲結構——順序表示和鏈表表示。
3.二叉樹的三種遍歷方法及相應的遞歸算法。
4.線程二叉樹的目的和本質。
5.樹存儲表示-子表示、父表示和子兄弟表示。
6.樹、森林和二叉樹的轉換方法。
7.穿越樹木和森林
8.樹的路徑長度,樹的加權路徑長度,Hoeffmann樹(最優二叉樹)的構造方法。
9、霍夫曼編碼法
四、評估要求
1.
1)樹的邏輯結構特征
2)樹的不同表示
3)樹的常用術語和含義
4)二叉樹線索的目的和本質。
5)在中序線索樹中尋找給定節點的中序前趨和中序後趨的方法。
6)樹、森林和二叉樹之間的轉換方法
7)樹木的各種貯藏結構及其特點。
8)樹的遍歷方法
2.簡單應用
1)二叉樹的定義以及樹和二叉樹的區別。
2)了解二叉樹的性質和相應的證明方法。
3)二叉樹的兩種存儲結構、特點和應用範圍。
4)最優二叉樹和前綴編碼的概念和特點。
5)赫夫曼算法的思想。
6)根據給定的葉節點及其權重,構造相應的最優二叉樹。
7)根據最優二叉樹構造相應的霍夫曼碼。
3.綜合應用
1)二叉樹的三種遍歷算法,並了解其執行過程。
2)根據不同的遍歷方式,應該可以得到相應的節點訪問順序。
3)基於遍歷算法,設計相關算法解決簡單應用問題。
第七章數字
壹、學習的目的和要求
本章的目的是介紹圖的基本概念、兩種常用的存儲結構、兩種遍歷方法以及圖的應用算法。本章重點掌握在圖的兩種存儲結構上實現的遍歷算法。難點是圖的應用算法:最小生成樹,求最短路徑,拓撲排序。只需要這些算法的基本思想和時間性能。
二、課程內容
第壹節圖表的定義和術語
第二節圖的存儲結構
第三節圖的遍歷
第四節圖的連通性
第五節有向無環圖及其應用
第六節最短路徑
三、考核知識點
1,圖的邏輯結構特征
2.圖形的常用術語和含義
3.圖的鄰接矩陣表示的存儲結構
4.鄰接表表示
5.圖的深度優先遍歷
6.圖的廣度優先遍歷
7.生成樹和最小生成樹
8.構造最小生成樹的PRIM算法思想及時間性能。
9.構造最小生成樹的Kruskal算法的思想和時間性能。
10,拓撲排序
11,關鍵路徑
12,關於最短路徑算法-Dijkstra算法的想法
四、評估要求
1.
1)圖的邏輯結構和特征
2)圖形的常用術語和含義
3)生成樹和最小生成樹的概念。
4)遍歷給定的圖,並繪制深度優先和寬度優先的生成樹或森林。
Prim和Kruskal算法的基本思想、時間性能和特點。
6)對於給定的連通圖,需要根據Prim和Kruskal算法構造最小生成樹。
7)最短路徑的含義
8)求單源點最短路徑問題的Dijkstra算法的基本思想和時間性能。
9)拓撲排序的基本思路和步驟。
10)拓撲排序失敗的原因
11)對於給定的有向圖,如果存在拓撲序列,則需要寫出壹個或多個拓撲序列。
2.簡單應用
1)圖的鄰接矩陣表示和鄰接表表示
2)根據應用問題的特點,選擇合適的存儲結構。
3)連通圖和不連通圖的深度優先搜索和廣度優先搜索算法。
4)確定兩種遍歷頂點的訪問順序。
5)圖的兩種遍歷性與樹的遍歷性的關系。
6)兩種遍歷算法分別使用的數據結構(堆棧和隊列)。
7)利用圖的遍歷解決簡單的應用問題。
第九章搜索
壹、學習的目的和要求
本章的目的是介紹線性表、樹和哈希表的搜索方法、算法實現和時間性能(平均搜索長度)分析。重點掌握順序搜索、半搜索、二叉排序樹和哈希表搜索的基本思想和算法實現。難點是二叉排序樹上的刪除算法。
二、課程內容
第壹節靜態查找表
第二節動態查找表
第三節哈希表
二、知識點的考核
1.定義搜索關鍵字,搜索和平均搜索長度。
2.靜態查找表的查找算法(順序查找、半查找、分塊查找(索引順序表查找))及其效率(最差和平均長度)。
3.二叉排序樹的搜索算法及其效率。
4.平衡二叉樹的定義。
5.哈希方法的特征
6.哈希函數和哈希地址。
7.構造哈希函數的幾種方法。直接尋址法,除余數法,平方法,折疊法,數字分析法。
8.處理沖突的方法:開放式尋址法和鏈式尋址法。開放尋址方法分為線性檢測重散列、二次檢測重散列和偽隨機檢測重散列。
四、評估要求
1.記憶
搜索在數據處理中的重要性。
2)找到成功和失敗的意義。
2.簡單應用
1)順序搜索、半搜索、分塊搜索的基本思想、算法實現和效率分析。
2)順序搜索中的“監控崗”功能。
3)比較線性表上三種搜索方法的優缺點,可以根據實際問題的要求和特點選擇合適的搜索方法。
4)二叉排序樹和二叉平衡樹的定義和特征。
5)插入、刪除、建立和搜索二叉排序樹的算法及其時間性能。
6)建立二叉排序樹的過程就是對輸入序列進行排序的過程,以及輸入序列對二叉排序樹形狀的影響。
7)哈希表、哈希函數、哈希地址(hash address)、填充因子等相關概念。
8)哈希函數的構造方法和沖突解決方法。
9)哈希表和其他表的本質區別
第十章內部排序
壹、學習的目的和要求
本章的目的是介紹五種內部排序方法的基本思想、排序過程、算法實現、時空性能分析,以及各種排序方法的比較和選擇。重點掌握快速排序、堆排序、歸並排序和基數排序的基本思想和排序過程。難點在於這四種排序算法的實現。
二、課程內容
第壹節概述
第2節插入排序
第三節快速排序
第四節選擇排序
第五節合並排序
第六節基數排序
第七節各種內部排序方法的比較和討論
三、考核知識點
1,排序的目的,分類的定義,排序方法的穩定性。
2.插入排序:直接插入排序的算法,半插入排序的算法,希爾排序的思想。
3.選擇排序的想法。
4.堆排序的方法,堆的定義和初始堆的建立。
5.冒泡排序的思想。
6.快速排序算法和快速排序最壞情況下的時間復雜度分析。
7.合並和排序的想法。
8.基數排序的思想和特點。
四、評估要求
1.記憶
排序在數據處理中的重要性。
2)排序方法穩定性的含義
3)排序方法的分類和算法的評價標準。
理解
1)歸並排序的基本思想和算法實現,以及時間性能分析。
2)對於給定的輸入序列,歸並排序的排序過程可以寫成。
3)基數排序的基本思想
4)分布排序與其他排序方式的區別。
3.簡單應用
1)堆、最小堆、最大堆、堆頂等相關概念和定義。
2)堆的性質以及堆與完全二叉樹的關系。
3)直接選擇排序和堆排序的基本思想和算法實現,以及時間性能分析。
4)對於給定的輸入序列,寫出堆排序的排序過程。
5)比較各種排序算法的優缺點。
6)根據實際問題的特點和要求,選擇合適的排序方法。
4.綜合應用
1),直接插入排序的基本思想和算法實現,以及在最好、最壞和壹般情況下的時間性能分析。
2)直接插入排序中的“監控崗”功能。
3)對於給定的輸入序列,妳應該能寫出直接插入排序的排序過程。
4)冒泡排序的基本思想
5)快速排序的基本思想和算法實現,以及在最好、最壞和壹般情況下的時間性能分析,了解算法的穩定性。
6)樞紐元素選擇對排序的影響。
7)對於給定的輸入序列,可以寫出快速排序的排序過程。
第十二章文件
壹、學習的目的和要求
本章的目的是介紹存儲在外存中的數據結構(文件)的相關概念,各種文件及其特點,組織方法及其查詢和更新操作,需要對這些內容有壹個大致的了解。這壹章不是重點。。
二、課程內容
第壹部分是關於文件的基本概念
第二節序列文件
第三節索引文件
第四節ISAM檔案和VSAM檔案
第5節直接訪問文件
第6節多關鍵字文件
三、考核知識點
9.文件的基本概念
10.常見的文件組織方式:順序文件、索引文件、哈希文件、多關鍵字文件。
11.順序文件的特點和檢索方法
12.索引文件的組織
13.有兩種索引序列文件:ISAM文件和VSAM文件。
14.哈希文件(直接訪問文件)的特點和優勢
15.組織多關鍵字文件的兩種方法:多表文件和倒排表。
四、評估要求
1.記憶
1)文件的基本概念
2)常見的文件組織方式:順序文件、索引文件、哈希文件、多關鍵字文件。
3)順序文件的特點和檢索方法
4)索引文件的組織
5)常用的索引序列文件有兩種:ISAM文件和VSAM文件。
6)哈希文件(直接訪問文件)的特點和優勢
7)組織多關鍵字文件的兩種方法:多表文件和倒排表。
教材:《數據結構》(C語言版),嚴為民、吳偉民主編,清華大學出版社,1996。
試題類型和分數分布:
本課程考試題型有填空題、問答題和綜合應用題三種,其中填空題20分,問答題25分,綜合應用題30分。
這是2010考試大綱。我覺得2011的大綱不會有太大變化。