2020年江西師范大學碩士研究生入學考試初試科目
考試大綱

一、考試形式與試卷結構

（一）試卷滿分 及 考試時間

本試卷滿分為 150 分，考試時間為180分鐘。

（二）答題方式

答題方式為閉卷、筆試。

試卷由試題和答題紙組成；答案必須寫在答題紙相應的位置上。

二、考查目標（復習要求）

全日制攻讀碩士學位研究生入學考試C語言程序設計與數據結構科目考試內容包括C語言程序設計、數據結構等2門學科基礎課程，要求考生系統掌握相關學科的基本知識、基礎理論和基本方法，并能運用相關理論和方法分析、解決實際問題。

三、考查范圍或考試內容概要

第一部分：C語言程序設計

第一章　程序設計和C語言

1．什么是計算機程序

2．什么是計算機語言

3．C語言的發展及其特點

4．最簡單的C語言程序

5．運行C程序的步驟與方法
6．程序設計的任務

第二章 算法
1．什么是算法
2．簡單的算法舉例
3．算法的特性
4．怎樣表示一個算法
5．結構化程序設計方法

第三章 順序程序設計
1．數據的表現形式及其運算
2．C語句
3．數據的輸入輸出

第四章 選擇結構程序設計
1．選擇結構和條件判斷
2．用if語句實現選擇結構
3．關系運算符和關系表達式
4．邏輯運算符和邏輯表達式
5．條件運算符和條件表達式
6．選擇結構的嵌套
7．用switch語句實現多分支選擇結構

第五章 循環結構程序設計
1．用while語句實現循環
2．用do…while語句實現循環
3．用for語句實現循環
4．循環的嵌套
5．幾種循環的比較
6．改變循環執行的狀態

第六章 利用數組處理批量數據
1．一維數組
2．二維數組
3．字符數組

第七章 用函數實現模塊化程序設計
1．為什么要用函數
2．怎樣定義函數
3．調用函數
4．對被調用函數的聲明和函數原型
5．函數的嵌套調用
6．函數的遞歸調用
7．數組作為函數參數
8．局部變量和全局變量
9．變量的存儲方式和生存期
10．關于變量的聲明和定義
11．內部函數和外部函數

第八章 指針
1．指針是什么
2．指針變量
3．通過指針引用數組
4．通過指針引用字符串
5．指向函數的指針
6．返回指針值的函數
7．指針數組和多重指針
8．動態內存分配與指向它的指針變量

第九章自定義數據類型
1．結構體變量
2．結構體數組
3．結構體指針
4．用指針處理鏈表
5．共用體類型
6．枚舉類型
7．用typedef聲明新類型名

第十章 文件的輸入輸出
1．C文件的基本知識
2．打開與關閉文件
3．順序讀寫數據文件
4．隨機讀寫數據文件
5．文件讀寫的出錯檢測

參考教材或主要參考書：

1．C程序設計(第四版)，譚浩強，清華大學出版社，2010年6月

第二部分：數據結構

第一章　緒論
1. 數據結構的基本概念
2. 抽象數據類型
3. 算法和算法的時間復雜度
4. 算法書寫規范

第二章  線性表
1. 線性表概述
2. 線性表的順序表示和實現
3. 線性表的鏈式表示和實現
4. 靜態鏈表
5. 算法設計舉例

第三章 堆棧和隊列
1. 堆棧
2. 堆棧應用
3. 隊列
4. 優先級隊列

第四章 串
1. 串概述
2. 串的存儲結構
3. 串基本操作的實現算法
4. 串的模式匹配算法

第五章 數組
1. 數組概述
2. 動態數組
3. 特殊矩陣的壓縮存儲
4. 稀疏矩陣的壓縮存儲

第六章 遞歸算法
1. 遞歸的概念
2. 遞歸算法的執行過程
3. 遞歸算法的設計方法
4. 遞歸過程和運行時棧
5. 遞歸算法的時間效率分析
6. 遞歸算法到非遞歸算法的轉換

第七章 廣義表
1. 廣義表概述
2. 廣義表的存儲結構
3. 廣義表的操作實現

第八章 樹和二叉樹
1. 樹
2. 二叉樹
3. 二叉樹的設計和實現
4. 二叉樹遍歷
5. 線索二叉樹
6. 哈夫曼樹
7. 等價問題
8. 樹與二叉樹的轉換
9. 樹的遍歷

第九章 圖
1. 圖概述
2. 圖的存儲結構
3. 圖的實現
4. 圖的遍歷
5. 最小生成樹
6. 最短路徑
7. 拓撲排序
8. 關鍵路徑

第十章 排序
1. 排序的基本概念
2. 插入排序
3. 選擇排序
4. 交換排序
5. 歸并排序
6. 基數排序
7. 排序算法性能比較

第十一章 查找
1. 查找的基本概念
2. 靜態查找
3. 動態查找
4. 哈希查找

第十二章 文件
1. 文件概述
2. 順序文件
3. 索引文件
4. ISAM文件
5. VSAM文件
6. 散列文件

參考教材或主要參考書：

1．《數據結構—使用C語言（第4版）》，朱戰立，電子工業出版社，2009年1月

四、樣卷

2020年江西師范大學碩士研究生入學考試試題樣卷

一、簡答題（10小題，每小題5分，共50分）

1、 算法具有哪些特點？

2、 C語言中的主要數據類型有哪些？

3、 C語言中break語句與continue語句有何區別？

4、 什么是形式參數？什么是實際參數？

5、 將以下for循環改寫為while循環：

for(sum=0,i=0;i<1000;sum+=2*I,i++);

printf(“sum=%d\n”,sum);

6、 簡述結構化程序設計的基本思想。

7、 寫出抽象數據類型棧的主要操作。

8、 什么是滿二叉樹？什么是完全二叉樹？

9、 什么是內部排序？什么是外部排序？

10、      寫出二叉樹三種遍歷操作的定義。

二、填空題（5個空，每空2分，共10分）

1、 組成C語言源程序的基本單位是_______。

2、 以下定義中，值為5的枚舉常量是_________。

enum week{sun,mon=4,tue,wed,thu,fri,sat};

3、 假設在程序中a，b，c均被定義成int型，則能正確表示代數式 的C語言表達式是_________。

4、 若已定義a=8，b=2，則表達式a＆＆（a-b*4）||b的值為__________。

5、 若有下列說明和賦值語句：

int a=8,b;

b=++a;

則變量b的值是__________。

三、判斷題（5小題，每小題2分，共10分）

1、 隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。

2、 用散列方法存儲，查找效率不高。

3、 線性表的存儲方式既可以是順序方式，也可以是鏈式方式。

4、 二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。

5、 用二叉鏈表法存儲包含n個結點的二叉樹，結點的2n個指針區域中有n+1個為空指針。

四、應用題（3小題，每小題10分，共30分）

1、 試分別畫出具有3個結點的樹和具有3個結點的二叉樹的所有不同形態。

2、 已知序列40，30，50，24，28，46，60，10。試畫出由該輸入序列構成的二叉排序樹，并分別給出依次執行下列操作后的二叉排序樹（共畫四棵樹）（1）插入數據42和80；（2）刪除數據30；（3）刪除數據50。

3、 請簡述直接插入排序的基本思想，并對于下列給定數據{27，46，5，18，16，51，32，26}寫出其排序過程。

五、程序設計題（5小題，每小題10分，共50分）

1、  設計一個函數，利用單鏈表原來的結點空間將一個帶頭結點的單鏈表就地轉置。假定程序中已有說明如下：

typedef struct node

{     int data;

struct node *next;

}linknode;

typedef linknode *linklist;

2、  試編寫一個函數，實現在順序存儲方式下字符串比較運算的函數strcompare(seqstring s1,seqstring s2)。假定程序中已有說明如下：

#define MAXSIZE 100

Typedef struct{

  char str[MAXSIZE];

  int length;

}seqstring;

3、  試編寫一個C程序，輸入一個10進制非負整數，將該數轉換為8進制整數，并計算其各位數字之和。

4、  試編寫一個C程序，利用公式 ，計算 的近似值。

5、  試編寫一個遞歸函數，將一顆給定二叉樹中所有結點的左右子女互換。假定程序中已有說明如下：

Typedef struct_BiTNode{

  int data;

  struct_BiTNode *lchild;

  struct_BiTNode *rchild;

}BiTNode,*pBiTNode;