科目代碼、名稱： 804《C語言程序設計與數據結構》
編制單位： 計算機學院
一、考試總體要求
本考試大綱適用于報考我校計算機學院電子信息專業的碩士研究生入學考試。主要涵蓋《C語言程序設計》和《數據結構》兩門課程的內容，所占的比例為40%和60%。
《C語言程序設計》課程的考試目標是要求學生掌握C語言基本知識；熟練掌握結構化程序設計的方法，形成良好的程序設計風格；掌握程序設計中基本的數據結構和算法，達到訓練學生的
邏輯思維能力的目的。
《數據結構》課程的考試目標是要求考生比較系統地理解數據結構的基本概念、基本原理和方法，掌握數據的
邏輯結構、存儲結構及其差異，以及各種基本操作的實現。能夠運用所學的基本原理和基本方法分析、判斷和解決有關理論問題和實際問題。能夠對算法進行設計與分析，能夠選擇合適的數據結構和方法進行問題求解。
二、考試形式與試卷結構
1．考試形式：閉卷、筆試，答題時間180分鐘，滿分150分。
2．試卷結構與題型：選擇題、填空題、閱讀程序題、應用題、算法設計題、程序設計題；除此之外還可能有簡答題、改錯題等。
三、考試內容及要求
《C語言程序設計》課程考試內容與要求
（一）C語言概述
1．了解C語言的特點及發展。
2．掌握程序的基本結構與書寫格式。
3．掌握頭文件、數據說明、函數的開始和結束標志。
（二）數據類型、運算符與表達式
1．掌握各種數據類型及其定義方法。
2．理解運算符的種類、運算優先級、結合性。
3．掌握不同類型數據間的轉換與運算。
4．掌握表達式類型（賦值表達式、算術表達式、關系表達式、邏輯表達式、條件表達式、逗號表達式）和求值規則。
（三）順序程序設計
1．理解表達式語句、空語句、復合語句以及賦值語句。
2．掌握數據的輸入/輸出和輸入/輸出函數。
（四）選擇結構程序設計
1．熟練掌握if語句實現選擇結構。
2．熟練掌握switch語句實現多分支選擇結構。
（五）循環控制
1．熟練掌握for循環結構。
2．熟練掌握while和do-while循環結構。
3．掌握continue、break、return語句。
4．熟練掌握循環的嵌套。
（六）數組
1．掌握數組的定義和數組元素的引用方法及數組的初始化方法。
2．熟練掌握一維和二維數組的基本操作和基本算法。
3．熟練掌握字符數組的存儲結構，字符串的輸入/輸出，對字符串進行處理的基本函數和對字符串進行處理的基本算法。
（七）函數
1．理解庫函數的正確調用。
2．熟練掌握函數的定義方法。
3．掌握函數的類型和返回值。
4．掌握形式參數與實在參數的區別，參數值的傳遞。
5．理解函數的一般調用和嵌套調用，學會遞歸調用。
6．掌握局部變量和全局變量。
7．理解變量的存儲類型(自動、靜態、寄存器、外部)，變量的作用域和生存期。
8．了解內部函數和外部函數。
（八）預處理命令
1．理解編譯預處理的概念和特點。
2．了解帶參數的宏定義及其使用，了解不帶參數的宏定義及其使用。
3．理解“文件包含”的概念和使用。
（九）指針
1．掌握指針的概念及指針的定義。
2．掌握指針運算。
3．掌握指向變量、數組、字符串、函數的指針變量。
4．熟練掌握用指針作函數參數。
5．掌握指針數組和指向指針數據的指針的概念及其定義方法。
6．掌握動態內存分配與指向它的指針變量。
（十）結構體與共用體
1．理解結構體類型和結構體變量。
2．掌握結構體數組和結構體指針。
3．了解運用指針處理鏈表。
4．理解共用體類型。
5．理解枚舉類型。
（十一）文件
1．理解文件類型指針(file類型指針)。
2．掌握文件的打開與關閉(fopen和fclose函數)。
3．掌握文件的讀與寫(fprintf和fscanf函數)。
《數據結構》課程考試內容與要求
（一）概述
1．理解數據的邏輯結構與存儲結構的基本概念。
2．理解算法定義、基本性質以及算法分析，包括時間復雜度和空間復雜度的計算。
（二）線性表
1．理解線性關系、線性表的定義，線性表的基本操作。
2．掌握線性表的順序存儲結構與鏈式存儲結構(包括單鏈表、循環鏈表和雙向鏈表)的構造原理。
3．熟練掌握在以上兩種存儲結構的基礎上對線性表實施的基本操作，包括順序表的插入與刪除、鏈表的建立、插入與刪除、查找等操作對應的算法設計。
4．掌握鏈表的常用應用。
（三）棧和隊列
1．理解棧與隊列的基本概念與基本操作。
2．掌握棧與隊列的順序存儲結構與鏈式存儲結構的構造原理。
3．熟練掌握在不同存儲結構的基礎上對棧與隊列實施插入與刪除等基本操作的算法設計。
4．掌握棧和隊列在解決實際問題中應用。例如：遞歸過程、表達式求值、數制轉換、迷宮、排隊問題等。
（四）串、數組和廣義表
1．理解串的基本概念及順序和鏈式存儲結構。
2．掌握串的模式匹配過程及算法設計。
3．掌握數組的順序存儲結構及地址計算。
4．理解特殊矩陣的壓縮存儲方法。
5．理解廣義表的基本概念、存儲結構。
（五）樹與二叉樹
1．理解樹與二叉樹的基本概念，名詞術語。
2．掌握二叉樹的基本性質和存儲結構。
3．掌握二叉樹與樹、樹林之間的轉換。
4．熟悉掌握二叉樹的遍歷，包括遞歸和非遞歸算法。
5．掌握以二叉鏈表形式存儲的二叉樹遍歷算法的應用。
6．掌握哈夫曼樹的基本概念，哈夫曼樹和哈夫曼編碼的構造和算法設計。
（六）圖
1．理解圖的基本概念、名詞術語。
2．掌握圖的鄰接矩陣存儲方法和鄰接表?含逆鄰接表?存儲方法的構造原理及特點。
3．熟練掌握圖的深度優先搜索與廣度優先搜索過程和算法設計。
4．掌握最小生成樹和最短路徑的構造和算法設計。
5．掌握AOV網與拓撲排序基本概念與求解過程。
（七）查找
1．掌握順序查找、折半查找和分塊查找的查找算法的設計與算法復雜性的分析過程。
2．掌握二叉排序樹的概念、構造、基本操作及實現算法的設計。
3．掌握平衡二叉樹的概念、構造、插入和刪除過程。
4．掌握散列(Hash)表的構造、散列函數的構造、處理散列沖突的基本方法以及散列表的查找和平均查找長度的計算。
（八）內部排序
1．理解排序的基本概念，各種內排序方法的基本原理和特點，包括排序過程中進行的元素之間的比較次數，排序總趟數、排序穩定性以及時間復雜度與空間復雜度計算。
2．掌握直接插入排序、折半插入排序、選擇排序；起泡排序、希爾排序法、快速排序、堆排序、二路歸并排序、基數排序；
3．了解各種內部排序算法的應用。
四、參考書目
《C語言程序設計》 譚浩強 編 清華大學出版社
《數據結構(C語言版)》 嚴蔚敏 吳偉民主編 清華大學出版社
京公安網備11010802020593號
