922程序设计与数据结构考试大纲

仅次于选择益友，就是选择好书。——考尔德
江苏自动化研究所硕士研究生入学考试
《数据结构与程序设计》考试大纲

　　
一、命题范围及考查的知识点
（一）、数据结构部分
1、概述
（1）数据的逻辑结构与存储结构的基本概念；
（2）算法的定义、基本性质以及算法分析的基本概念，包括采用大?形式表示时间或空间复杂度。
2、线性表
（1）线性关系、线性表的定义，线性表的基本操作；
（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理；
(3)在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入和删除、链表的建立、插入和删除、检索等操作对应的算法设计(含递归算法的设计)。
3、堆栈与队列
(1)堆栈与队列(含循环队列)的基本概念、基本操作；
(2)堆栈与队列的顺序存储结构与链式存储结构的构造原理；
(3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作。
4、树与二叉树
(1)树与二叉树的基本概念，基本特征、名词术语；
(2)完全二叉树、满二叉树的概念、二叉树的基本性质；
(3)二叉树的顺序存储结构与二叉链表存储结构的构造原理、二叉树的前序遍历、中序遍历、后序遍历和按层次遍历算法(重点为非递归算法)以及利用遍历解决有关二叉树的其它操作；
(4

个人资料整理，仅供个人学习使用

902 数据结构与C语言程序设计考研大纲

一、考试内容

（一）数据结构

1.线性表

1）线性表的定义

2）线性表的顺序存储和基本运算（查找、插入和删除）的实现

3）线性表的链式存储和基本运算（查找、插入和删除）的实现

4）线性表的应用

2.栈、队列和矩阵

1）栈和队列的定义

2）栈和队列的实现

（1）栈的顺序存储和基本操作（入栈、出栈和判栈空、栈满）的实现

（2）栈的链式存储和基本操作（入栈、出栈和判栈空）的实现

（3）队列的链式存储和基本操作（入队、出队和判队空）的实现

（4）循环队列的定义和基本操作（入队、出队和判队空、队满）的实现3）栈和队列的应用4）矩阵的压缩存储

（1）特殊矩阵（对称矩阵、三角矩阵、对角矩阵）的压缩存储

（2）稀疏矩阵的压缩存储

3.树与二叉树

1）树的基本概念2）二叉树

（1）二叉树的定义及性质

（2）二叉树的顺序存储和链式存储

（3）二叉树的先序、中序、后序遍历和层序遍历运算

（4）线索二叉树的定义

3）树和森林

（1）树的存储结构

（2）树（森林）与二叉树的相互转换

（3）树和森林的遍历

4）树与二叉树的应用

（1）二叉查找树（Binary Search Tree）（2）平衡二叉树（Balanced Binary Tree 或Heigh

章节小

节

知

识

点

分

数

题型

自

定

义

子

题

型

大

小

题

编

号

题干

定义一个函数用来实现求两个整形数的

最大值。要求在主函数中输入两个整形

数，调用自定义函数实现求最大值，并

进行输出。

输入一个字母，若为大写字母，则输出

其后继字符，若为小写字母，则输出其

前驱字符，若为其他字符则原样输出

输出所有的水仙花数。所谓水仙花数，

是指这样的一些3位整数：各位数字的

立方和等于该数本身。

例如153，1+125+27=153。

1410问答题编写程序，输入一个成绩，输出该成绩的等级。成绩在85分以上为优秀，75分至85分之间为良好，60分到75分之间为及格，60分以下为不及格。

1410问答题编写一个判断奇偶数的函数，要求在主函数中输入一个整数，输出该数是奇数还是偶数的信息。

14问答题编写一密码验证程序。原始密码由用户在程序中定义。若用户输入的密码和原始密码一致，则显示：“You are right！”,否则显示”You are wrong!”

1410问答题定义sum函数和主函数，sum函数求两个整数之和，主函数实现两个整数的输入及两个数之和的输出。

1410问答题输入20个整数，统计其中非负数个数，并求非负数之和。（用数组实现）

1410问答题输入10个整数，求其中的最大值和最小值，以及这组

一、单项选择题

1．以下叙述错误的是（

）。

Ａ． 一个C源程序可由一个或多个函数组成 B． 一个C源程序必须包含一个main函数 C． C程序的基本组成单位是函数

D． 在C程序中，注释说明只能位于一条语句的后面 2．C语言中运算对象必须是整型的运算符是（

A． %= B．/ main()

{ unsigned int x=0xffff;

printf(“%u\\n”,x );}

A． -1 B． 65535 C． 32767 D． 0xFFFF 4．若有代数式

，则以下能够正确代nx?ex（其中e仅代表自然对数的底数，不是变量）

）。

3．有如下程序,程序运行后的输出结果是（

）。 ）。

C． = D． 〈=

表该代数式的C语言表达式是（

A． sqrt(abs(n^x+e^x) B． sqrt(fabs(pow(n,x)+pow(x,e))) C． sqrt(fabs(pow(n,x)+exp(x))) D． sqrt(fabs(pow(x,n)+exp(x))) 5．字符串“\\t12\\x42\\\\ab

一、单项选择题

1．以下叙述错误的是（

）。

Ａ． 一个C源程序可由一个或多个函数组成 B． 一个C源程序必须包含一个main函数 C． C程序的基本组成单位是函数

D． 在C程序中，注释说明只能位于一条语句的后面 2．C语言中运算对象必须是整型的运算符是（

A． %= B．/ main()

{ unsigned int x=0xffff;

printf(“%u\\n”,x );}

A． -1 B． 65535 C． 32767 D． 0xFFFF 4．若有代数式

，则以下能够正确代nx?ex（其中e仅代表自然对数的底数，不是变量）

）。

3．有如下程序,程序运行后的输出结果是（

）。 ）。

C． = D． 〈=

表该代数式的C语言表达式是（

A． sqrt(abs(n^x+e^x) B． sqrt(fabs(pow(n,x)+pow(x,e))) C． sqrt(fabs(pow(n,x)+exp(x))) D． sqrt(fabs(pow(x,n)+exp(x))) 5．字符串“\\t12\\x42\\\\ab

《数据结构》

Part1

一．选择

1. 组成数据的基本单位是（ ）

A）数据项 B）数据类型 C）数据元素 D）数据变量 2．算法分析的目的是（ ）

A）找出数据结构的合理性 B）研究算法的输入/输出关系 C）分析算法的效率以求改进 D）分析算法的易读性

3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ） A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（ ）

A）112 B）144 C）148 D）412 5．下面关于线性表的叙述中，错误的是（ ）

A） 顺序表使用一维数组实现的线性表 B） 顺序表必须占用一片连续的存储单元. C） 顺序表的空间利用率高于链表 D） 在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（ ）比较合适

A） 单链表 B）

《数据结构》

Part1

一．选择

1. 组成数据的基本单位是（ ）

A）数据项 B）数据类型 C）数据元素 D）数据变量 2．算法分析的目的是（ ）

A）找出数据结构的合理性 B）研究算法的输入/输出关系 C）分析算法的效率以求改进 D）分析算法的易读性

3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ） A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（ ）

A）112 B）144 C）148 D）412 5．下面关于线性表的叙述中，错误的是（ ）

A） 顺序表使用一维数组实现的线性表 B） 顺序表必须占用一片连续的存储单元. C） 顺序表的空间利用率高于链表 D） 在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（ ）比较合适

A） 单链表 B）

湖南师范大学硕士研究生入学考试自命题考试大纲

考试科目代码：[967] 考试科目名称：C语言程序设计和数据结构

一、试卷结构

1) 试卷成绩及考试时间

本试卷满分为150分，考试时间为180分钟。 2)答题方式：闭卷、笔试 3)试卷内容结构

C语言程序设计部分 80% 数据结构部分4)题型结构

a: 单项选择题，共40分 b: 程序填空题，共30分 c: 程序阅读题，共25分 d: 编程题，共45分 e: 分析题，共10分

二、考试内容与考试要求 （一）C语言程序设计部分

考试内容 1、基本知识

（1）C语言的数据类型

（2）C语言中各种类型常量的表示法 （3）各类数值型数据间的混合运算 （4）C运算符

（5）关系表达式及运算，逻辑表达式及运算 2、顺序、选择与循环结构 （1）赋值语句，格式输入与输出

20% （2）if语句，switch语句

（3）goto、while、do-while、for、break、continue语句 3、数组

（1）一维数组的定义和引用 （2）二维数组的定义和引用

（3）字符数组的定义和引用，字符串及其处理函数 4、函数

（1）函数定义与调用 （2）局部变量和全局变

实验报告一 JAVA程序设计基础及算法设计

班级________ 学号______ 姓名_____ 专业_____ 一、 实验目的：

（1） 掌握JAVA语言的语法，理解数组和对象的引用模型，理解类的封装、继承和多态 （2） 掌握类的设计方法

（3） 掌握异常处理方法和标准输出方法，了解标准输入方法 （4） 熟悉算法的描述方法、算法时间复杂度的分析和计算方法 （5） 理解数据和算法的基本概念 二、 实验内容：

1、 采用二维数据输出杨辉三角形，二维数据的结构如图1所示：

0 1 2 3 4 5 mat mat[0] 1 mat[1] 1 1 mat[2] 1 2 1 mat[3] 1 3 3 1 mat[4] 1 4 6 4 1 mat[5] 1 5 10 10 5 1

图1 杨辉三角形的二维数组结构

请粘贴源程序及运行测试结果： 源程序：

import java.util.Scanner;

public class Ex {

public static void pri( int

第10章 文件读写

C语言程序设计与数据结构

教学提示：存储在变量和数组(即内存)中的数据 是临时的，这些数据在程序运行结束后会消失，而 文件可以用来永久地保存大量的数据。如果有些数 据需要反复使用或永久保存，应该考虑使用文件来 完成。 教学要求：本章要掌握文件在读写之前必须打开， 读写结束必须关闭。文件可按只读、只写、读写、 追加四种操作方式打开，同时还必须指定文件的类 型是二进制文件还是文本文件。文件可按字节，字 符串，数据块为单位读写，文件也可按指定的格式 进行读写。文件内部的位置指针可指示当前的读写 位置，移动该指针可以对文件实现随机读写。C语言程序设计与数据结构

10.1

文件概述与文件指针

所谓“文件”是指一组相关数据的有序集合。 我们在前几章中已多次接触使用过文件，例如 源程序文件、目标文件、可执行文件、库文件 (头 文件)等。

C语言程序设计与数据结构

10.1.1 文件分类 文件通常是驻留在外部介质(如磁盘等)上的，在使 用时才调入内存中来。C语言把文件看作是由一个 个字符(字节)的数据顺序组成的。它把数据看作 是连续的字符(字节)流，这样它对文件的存取实 际上是以字符(字节)为单位的。输入输出的数据 流的开始和结束只受程序的控制而不