2013年黃岡師范學院專升本計算機科學與技術《專業(yè)綜合》考試大綱

黃岡師范學院2013年專升本計算機科學與技術《專業(yè)綜合》考試大綱

十一、
計算機科學與技術《專業(yè)綜合》考試大綱
考試科目：C
語言、數據結構
課程一：《C
程序設計》考試大綱
一、總體要求：
1．了解高級程序設計語言的結構，掌握C語言的基本語法、基本的程序設計過程和技巧。
2．掌握基本的分析問題和利用計算機求解問題的能力，具備初步的高級語言程序設計能力。
二、考核知識點
1、數據定義
數據定義包括數據類型和存儲類別
(1)基本類型
基本類型指整型、實型和字符型
① 常量
熟練掌握各種表示形式的整數、實數、字符常量和字符串常量，符號常量的定義和使用。
包括整數的十進制、八進制和十六進制的表示形式、長整型常量和無符號型常量的表示形式，實數的浮點表示法和科學記數法，字符的轉義序列，常用符號常量的含義（如NULL、EOF等）
② 變量
熟練掌握變量的定義和初始化
(2)構造類型
構造類型包括數組和結構
① 數組
熟練掌握一維和二維數組的定義和初始化，數組元素的引用。
包括一維字符數組和字符串，二維字符數組和字符串數組
② 結構
熟練掌握結構類型的定義，結構變量的定義和初始化，結構變量成員的引用。
(3) 指針
① 熟練掌握指針和地址的概念
② 熟練掌握指針變量的定義和初始化
③ 熟練掌握通過指針引用指向實體
(4) 構造類型和指針類型的混合定義及應用
① 熟練掌握指針、數組和地址間的關系
② 熟練掌握指針數組
③ 熟練掌握結構數組
④ 熟練掌握結構指針
⑤ 掌握結構中含指針或數組
⑥ 掌握嵌套結構
⑦ 掌握指向指針的指針（二級）
⑧ 單向鏈表:掌握單向鏈表的建立和遍歷,了解插入和刪除單向鏈表中的一個節(jié)點
(5) 空類型
掌握空類型的定義和使用
(6) 變量的存儲類別、作用域和生存期
① 掌握變量的存儲類別
auto 自動型、static 靜態(tài)型
② 掌握全局變量和局部變量
注意區(qū)分：自動局部變量和靜態(tài)局部變量
2、運算及流程控制
(1)基本運算
包括算術運算（含自增、自減操作）、關系運算、邏輯運算、條件運算、賦值運算。
熟練掌握運算符的功能
熟練掌握運算符的優(yōu)先級和結合方向
熟練掌握隱式類型轉換和強制類型轉換
(2)表達式
熟練掌握各類表達式的組成規(guī)則和計算過程
(3)語句
① 熟練掌握表達式語句、空語句、復合語句；

② 熟練掌握簡單控制語句（break、continue、return）；

③ 熟練掌握選擇控制語句(if、switch)
④ 熟練掌握重復控制語句(for、while、do—while);
3、程序結構和函數
(1)程序結構
熟練掌握main函數與其他函數之間的關系
包括標準庫函數和自定義函數
(2)函數的定義
① 熟練掌握函數定義的ANSI C格式
② 熟練掌握函數的參數（形式參數和實在參數）及參數傳遞
包括指針作為函數的參數
③ 熟練掌握函數的返回值
(3)函數的調用
① 函數調用的一般格式
熟練掌握通過函數名調用函數
② 掌握函數的嵌套調用和遞歸調用
③ 熟練掌握標準庫函數的調用
常用數學函數：cos、sqrt、pow、exp、fabs、log、log10等
常用字符函數：isalnum、isalpha、isdigit、islower、toupper等
常用字符串函數：strcpy、strcmp、strcat、strlen等
4、編譯預處理和命令行參數
(1)熟練掌握編譯預處理的基本概念
(2)掌握宏定義
(3)掌握文件包含
5、常用算法
以下算法針對本大綱中列出的各種數據結構
(1)分類（排序）算法
冒泡、選擇、插入
(2)檢索（查找）算法
① 無序數據序列的查找（見遍歷算法）
② 有序數據序列的查找：二分法
(3)遍歷算法
① 一維數組和二維數組的遍歷
② 單向鏈表的遍歷
(4)簡單的數值計算方法：如多項式函數的計算
(5)其它基本算法：如進制轉換
教材：C程序設計，譚浩強，清華大學出版社
試卷結構（C語言部分，100分）
試卷題型比例：
選擇題 約40%
填空題 約30%
程序理解題 約30%

課程二：《數據結構》考試大綱
一、總體要求：
1、基本理論知識
(l)什么是數據結構、基本概念和基本術語，算法的描述和算法分析。
(2)什么是線性表、在線性表上常進行的基本操作以及這些操作分別在順序存儲和鏈式存儲結構下的實現及復雜度分析。
(3)棧和隊列的定義、表示方法和實現。
(4)串的定義及其基本操作。
(5)數組的定義、運算和存儲、稀疏矩陣的壓縮存儲。
(6)樹的定義、基本術語和存儲結構，二叉樹的定義和性質、二叉樹的存儲結構及其各種操作，哈夫曼樹。
(7)圖的定義和術語、圖的存儲結構及其各種操作。
(8)各種查找方法的算法、適用范圍及時間復雜度的分析。
(9)多種內排算法的基本思想和算法的時間復雜度分析，不同排序方法的比較。
2、基本技能
(1)能閱讀用類C語言編寫的算法。
(2)能分析算法所完成的功能、運行結果和時間復雜度。
(3)能根據要求用類C語言編寫算法。
二、考核知識點
1、緒論
(1)數據、數據元素、數據項、數據對象、數據結構、邏輯結構、物理結構、元素、結點等基本概念。抽象數據類型的定義、表示和實現方法。
(2)算法、算法的特性、如何用類C語言來描述算法。
(3)算法設計的基本要求以及計算語句頻度和估算算法時間復雜度的方法。
2、線性表
(1)線性表的定義和操作。
(2)順序存儲線性表的實現和運算。
(3)鏈式存儲線性表，帶有附加表頭結點和不帶附加表頭結點的單鏈表、循環(huán)鏈表和雙向鏈表的實現和查找對插入、刪除等基本操作。
3、棧和隊列
(1)棧和隊列的定義及其存儲結構、循環(huán)隊列。
(2)棧和隊列的主要運算。
(3)棧的應用舉例，如：數制轉換、表達式求值等。
4、串
(1)串的定義、空串、空格串。
(2)串的基本操作。
(3)串的順序存儲結構及在順序存儲結構下基本操作的實現。
(4)串的模式匹配算法。
5、樹和二叉樹
(1)樹的定義和術語。
(2)二叉樹(完全二叉樹、滿二叉樹)的定義和性質、二叉樹的存儲結構（順序表示法和二叉鏈表表示法）。
(3)二叉樹遍歷的遞歸算法。
(4)樹和森林轉換為二叉樹的方法。
6、圖
(1)圖的定義。
(2)圖的基本術語。
①圖及無向圖、有向圖、網、子圖、連通圖、強連通圖。
②頂點的度、入度、出度。
③頂點間路徑、路徑長度、環(huán)。
(3)圖的存儲結構
①鄰接矩陣
②鄰接表(含逆鄰接表)
(4)遍歷圖
①深度優(yōu)先搜索遍歷圖的算法及其時間復雜度。
②廣度優(yōu)先搜索遍歷圖的思想及其時間復雜度。
(5)生成樹
①生成樹、最小生成樹的概念。
②最小生成樹的構造過程(Prim算法和Kruskal算法)及其時間復雜度。
(6)兩類求最短路徑問題的解法。
8、排序
(1)排序的目的、分類和排序方法的穩(wěn)定性的定義。
(2)插入排序
①直接插入排序的算法。
②希爾排序的思想。
(3)選擇排序
①簡單的選擇排序的算法。
③堆的定義、堆排序的思想。
(4)歸并排序的思想。
(5)基數排序的思想及特點。
(6)各種內部排序方法的比較。
9、查找
(1)查找、關鍵字、平均查找長度等概念。
(2)靜態(tài)查找表的查找算法及其效率(最壞和平均查找長度)。
①順序查找
②分塊查找
(3)動態(tài)查找表
①二叉排序樹定義、構造過程及其查找算法和效率。
(4)哈希表
①哈希表的特點。
②構造哈希函數的方法（除留余數法等）。
③處理沖突的方法。
教材：《數據結構》（C語言版） 朱站立編著 西安交通大學出版社
試卷結構（數據結構部分，100分）
試卷題型比例：
選擇題 約50%
填空題 約30%
計算分析算法題 約20%