(828)程序设计与数据结构

广西大学2021年硕士研究生入学考试《程序设计与数据结构（828）》考试大纲与参考书目试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。

二、答题方式答题方式为闭卷、笔试。

三、试卷内容结构考试内容为C语言程序设计基础、面向对象程序设计、数据结构、算法设计与分析。

四、试卷题型结构1. 判断题（10分）2. 单项选择题（40分）3. 填空题（20分）4. 综合题（45分）5. 编程题（35分）考试内容和考试要求1、计算机程序设计基本知识（1）源代码、目标代码、可执行程序、头文件、静态库、动态链接库/共享库；（2）预编译、编译、链接；（3）标准输入/输出、输入输出重定向、管道；（4）编译和解释型程序及其常见实例。

2、结构化程序设计方法（1）C语言基础、常量、变量、基本数据类型、运算符、表达式、分支选择控制结构、循环控制结构；（2）函数、递归、文件I/O；（3）结构、数组、指针、字符串处理、变量存储、内存管理、位运算、指向函数的指针；（4）预处理器、多模块程序设计、流程图、规范程序设计。

3、面向对象程序设计OOP方法（1）OOP基本思想、类、对象、属性、方法；（2）重载/覆盖、封装、继承/派生、多态、模板；（3）异常处理等；（4）C++基础、命名空间、C++字符串处理；（5）类图。

4、数据结构和算法（1）线性表、链表、栈、队列、串、树、图；（2）排序、查找。

5、算法设计与分析（1）算法描述、算法复杂性分析；（2）递归与分支策略、动态规划、贪心算法、回溯法等常见算法设计策略；（3）算法优化策略。

参考书目1 《C语言程序设计（第2版）》，何钦铭、颜晖著，高等教育出版社，20122 《数据结构C语言版》，严蔚敏、吴伟民编著，清华大学出版社，20073 《算法设计与分析（第2版）》，王晓东著，清华大学出版社，20124 《程序设计教程:用c++语言编程(第2版)》，陈家骏、郑滔著，机械工业出版社，2009。

828《数据结构与操作系统》考试大纲一、考试的基本要求要求考生比较系统地理解数据结构的基本概念和基础知识，从逻辑结构、存储结构和数据操作（算法）等三个方面掌握线性表、树、图等常用的数据结构；掌握在各种常用数据结构上实现高效的查找和排序算法；能够正确分析算法的时间和空间复杂性；能够针对较复杂的应用问题，选择合适的数据结构，并设计有效的算法。

要求考生比较系统地掌握操作系统各要素的基本概念、基本原理和方法，对操作系统如何管理和控制计算机系统的所有硬件和软件资源以达到方便用户、提高资源的使用效率有较深入的了解。

要求考生具有较强的抽象思维能力、逻辑推理能力、软件设计和实现能力以及综合运用所学的知识分析问题和解决问题的能力。

二、考试方式和考试时间考试方式为闭卷考试，试卷总分为150分（其中，数据结构90分，操作系统60分），考试时间为3小时。

三、参考书目（仅供参考）《数据结构与算法》（第四版），廖明宏，郭福顺，张岩，李秀坤，高等教育出版社，2007年《计算机操作系统》(第三版)，汤小丹，梁红兵，哲凤屏，汤子瀛，西安电子科技大学出版社，2007年四、试题类型：主要包括编程题、计算题、综合题等类型，并根据每年的考试要求做相应调整。

五、考试内容及要求第一部分数据结构-线性表掌握：线性表的逻辑结构、存储结构及描述方式；顺序表的定义、插入、删除；单链表、双向链表和循环链表的定义、插入、删除；顺序栈、链栈的表示、入栈和出栈操作；顺序队列、链队列的表示、入队和出队操作；循环队列的队空和队满的判断；串的定义、逻辑结构和存储结构，串的KMP模式匹配算法；广义表的定义；矩阵的压缩存储的概念以及有关计算方法；稀疏矩阵的三元组表示方法。

熟悉：线性结构的定义和特点；顺序表和单链表的组织方法、特点、算法和性能分析；单链表、双向链表和循环链表之间的区别；栈和队列的定义；栈和队的特点；顺序栈和链栈上基本运算的实现和简单算法设计；链队上基本运算的实现和简单算法设计；串的基本运算，串的传统匹配方法；多维数组的定义以及逻辑结构；广义表的链表表示和算法；特殊矩阵的非零元下标与数组下标的对应关系。

828程序设计与数据结构一、前言计算机程序设计与数据结构是计算机科学的两个基本领域。

程序设计是指在计算机上创建运行程序的过程，而数据结构则是指程序操作的数据的组织、管理和存储方式。

这两个领域的知识是计算机科学和软件工程必不可少的基础。

本文将介绍一个名为“828程序设计与数据结构”的课程，该课程是一门计算机科学和软件工程的基础课程，代码为CS828。

二、课程概述“828程序设计与数据结构”是一门对数据结构和算法进行深入学习的课程。

在课程中，学生将学习如何设计有效的算法，如何通过数据结构来实现这些算法以及如何评估它们的性能。

本课程将首先介绍常见的数据结构，例如链表、堆、栈和队列，并讨论这些数据结构的优点和缺点。

随后，将介绍算法的概念，并通过一些实际例子来展示如何将这些算法应用于各种问题中。

三、课程目标该课程有以下几个主要目标：1.学习算法和数据结构的基本概念，掌握不同数据结构的应用和特点。

2.了解不同算法和数据结构的时间和空间复杂度，熟悉基本的算法分析技术。

3.掌握算法设计技能和动态规划思想，能够设计并实现有效的算法。

4.能够应用所学算法和数据结构解决实际问题，熟悉常用算法的应用场景。

四、教学内容一、基本数据结构1. 数组2. 链表3. 栈和队列4. 树5. 堆二、基本算法1. 排序2. 查找3. 字符串问题三、高级算法1. 动态规划2. 贪心算法3. 分治算法四、应用案例1. 图算法的应用2. 算法在自然语言处理中的应用3. 机器学习和数据挖掘算法的应用五、教学方法该课程主要采用讲授和实践相结合的教学方法。

课堂上，老师将通过演示例子和讲解相关知识来介绍算法和数据结构的基础，并通过练习来反复强化这些概念。

实践活动将包括编程练习、解决实际问题和完成项目，以帮助学生巩固所学内容并提高实践能力。

六、考核方式该课程的考核方式将包括作业、课堂练习、小组项目和期末考试。

学生需要认真完成作业和课堂练习，并积极参与小组项目，体现出对知识的掌握和综合能力。

2018年上海海事大学攻读硕士学位研究生入学考试
试题
（重要提示：答案必须做在答题纸上，做在试题上不给分）考试科目代码828 考试科目名称数据结构及程序设计一．判断题（本题10分，每小题1分）
1．线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

2．单链表从任何一个结点出发，都能访问到所有结点。

3．单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。

4．若在采用链式存储结构线性表中，元素按值有序，则该线性表可以采用折半查找法查找元素。

5．一个栈的输入序列为1, 2, 3, …, n，其输出序列的第二个元素为n的输出序列的个数有n-1种。

6．设串S的长度为n，则S的子串个数为n(n+1)/2。

7．若一个广义表的表头为空表，则此广义表亦为空表。

8．二叉树中除叶节点外，任一节点x，其左子树根节点的值小于该节点(x)的值，其右子树根节点的值大于该节点(x)的值，则此二叉树一定是二叉排序树。

9．网络的最小代价生成树是唯一的。

10．（99, 86, 46, 70, 34, 39, 45, 58, 66, 10 ）是堆。

二．填空题（本题20分，每空2分）
1．一个栈的输入序列是：1、2、3，则不可能的栈输出序列是⑴。

- 2018试题1/6 -。

3、栈和队列的应用
五、串
1、串的定义
2、串的存储结构及基本操作
3、串的应用
六、数组和广义表
1、数组和广义表的定义
2、数组和广义表的存储结构及基本操作
3、矩阵的压缩存储
4、数组和广义表的应用
七、树和二叉树
1、树的定义和基本操作
2、二叉树的定义、性质和存储结构及基本操作
3、遍历二叉树和线索二叉树
4、树和森林（存储结构、遍历、与二叉树的互相转换）
5、哈夫曼树及其应用
八、图
1、图的定义
2、图的存储结构
3、图的遍历
4、图的连通性（连通分量、最小生成树）
5、图的拓扑排序、关键路径、最短路径
九、查找
1、顺序表、有序表的查找及其分析
2、二叉排序树和平衡二叉树、B树
3、散列（Hash）表的定义、Hash函数的构造方式、冲突处理和Hash表的查找及其分析
十、内部排序
1、内部排序的基本概念
2、各种（插入类、交换类、选择类、归并类、基数排序）内部排序方法及其分析比较
3、外部排序的基本概念与方法
十一、文件
1、有关文件的基本概念
2、顺序文件、索引文件、索引顺序文件、直接存取文件、多重链表文件、倒排文件等的基本存取方法。

2017年上海海事大学攻读硕士学位研究生入学考试试题（重要提示：答案必须做在答题纸上，做在试题上不给分）
考试科目代码828 考试科目名称数据结构及程序设计
一．判断题（本题10分，每小题1分）
1．链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。

2．能够在链式存储的有序表上进行折半查找，其时间复杂度与在顺序存储的有序表上相同。

3．使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

4．任何一棵二叉树的叶结点在先序、中序、后序三种遍历中的相对次序是相同的。

5．数据结构的抽象操作的定义与具体实现有关。

6．对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。

7．如果无向图中每个顶点的度都大于等于2，则该图中必有回路。

8．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

9．若让元素1、2、3依次进栈，则出栈次序1、3、2是不可能出现的情况。

10．对平衡二叉树进行中序遍历，可得到结点的有序排列。

二．填空题（本题20分，每空2分）
1．下面程序的功能是实现冒泡排序算法，请在下划线处填上正确的语句。

void bubble(int r[n]) {
for ( i=1; i<=n-1; i++) {
- 2017试题1/6 -。

目　录第一部分　历年考研真题汇编2006年南京工业大学计算机科学与技术学院828数据结构与操作系统考研真题第二部分　兄弟院校真题汇编2014年山东科技大学信息科学与工程学院830数据结构与操作系统考研真题2012年山东科技大学信息科学与工程学院838数据结构与操作系统考研真题2011年山东科技大学信息科学与工程学院827数据结构与操作系统考研真题2010年山东科技大学信息科学与工程学院827数据结构与操作系统考研真题第一部分　历年考研真题汇编2006年南京工业大学计算机科学与技术学院828数据结构与操作系统考研真题南京工业大学耍堕年硕士研究生入学考试试卷（A）〈本试题150分、3小时）考试科目：数据埃构与操作系统诸应学科、专业：计算机应用技术（注意：所有答题内容均余写在答鬼地上，在试卷上答题-独无效！）第-部分,数据结构（共90分）一、选择题（每小题2分，共20分）1＞数据的存储结构有廉序、健式、族引和四种疆条形式.丸线性 B.树形C,散列D一图监2、计算机体法必^具备输入、输出和尊5个特性。

A,易读性、稳定性和安全性B可行性、可移植性和可扩充性C,牖定性、有穷性和秘定性可行性、确定性和有穷性3、指出下列时间要杂度最耶的级别是________.A.对数阶Ofhfcn）B.线性阶&n）C,指数阶。

（2"）D,平方阶0（『）4、己知模式串P='ABAABC',其next函数值是*A.011213B.012223C0LH22D,0112215、数组A中，行下标i义卜列下总j从1-10.每个元素的长度为3个字节，从首地址SA开始连续存糖.慢数组核列存放时，元素A”的起始地址为=A.SA+141B.SA+1S0C SA+222 D.SA+226、设无向图的顼点个数为n,聊谖无向图最多有________条辿.A.n;B.tt（n+l）/2C n（n-L）/2D n-17、将序列（50.72.43.85,73.20,35,45.65.30）构造为二叉排序树，杏找元素35重进行________次元素间的比较.A.10B.7C.5D.4一』、除度《设根的层次为L）的完全二又树至少有一^结点.七X尹C i*-T一 D.2W—-—----------------———9、下述几种排序方法中，能完成对突数数绍进行榆定捧序的是_______•,A、归弁样序 B.堆排序 C.快速排虏 D.痿数择序I。

2018年上海海事大学攻读硕士学位研究生入学考试
试题
（重要提示：答案必须做在答题纸上，做在试题上不给分）考试科目代码828 考试科目名称数据结构及程序设计一．判断题（本题10分，每小题1分）
1．线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

2．单链表从任何一个结点出发，都能访问到所有结点。

3．单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。

4．若在采用链式存储结构线性表中，元素按值有序，则该线性表可以采用折半查找法查找元素。

5．一个栈的输入序列为1, 2, 3, …, n，其输出序列的第二个元素为n的输出序列的个数有n-1种。

6．设串S的长度为n，则S的子串个数为n(n+1)/2。

7．若一个广义表的表头为空表，则此广义表亦为空表。

8．二叉树中除叶节点外，任一节点x，其左子树根节点的值小于该节点(x)的值，其右子树根节点的值大于该节点(x)的值，则此二叉树一定是二叉排序树。

9．网络的最小代价生成树是唯一的。

10．（99, 86, 46, 70, 34, 39, 45, 58, 66, 10 ）是堆。

二．填空题（本题20分，每空2分）
1．一个栈的输入序列是：1、2、3，则不可能的栈输出序列是⑴。

- 2018试题1/6 -。

“程序设计与数据结构”教学大纲课程名称：程序设计与数据结构英文名称：Program Design and Data Structure学时：96学分：6课程类型：必修课程性质：专业基础课适用专业：自动化（交通信息工程及控制）先修课程：计算机科学与编程导论开课学期：第1、2学期开课院系：信息科学与技术学院一、课程的教学目标与任务本课程培养学生较熟练地掌握C语言程序设计的基本技能，掌握各种基本数据结构和算法。

通过本课程的学习，掌握C语言基础知识；掌握简单算法和数据结构的基本设计方法；掌握复杂数据结构（例如栈和队列以及链表）的含义并能简单应用，建立程序设计的思想，培养学生的问题解决能力和实际编程能力；了解并初步掌握当前软件行业公认的程序设计风格和编程实践。

学生应掌握各种基本数据结构的概念、实现方法及涉及的基本算法，并能用这些数据结构和算法解决相关的应用问题，为进一步学习相关学科打下坚实的基础。

通过本课程的学习。

重点是阐述程序设计思想和各种数据结构及其相关算法，培养学生分析问题和使用程序和数据结构解决问题的能力。

二、本课程与其它课程的联系和分工“计算机科学与编程导论”是本课程的先修课程。

具体分工是:由计算机科学与编程导论课程建立对计算机的基本认识，了解软件的构成及分类，了解程序的运行原理和过程；由本课程介绍程序设计基础和软件开发方法，C语言的基本语法和语义（包括变量、简单数据类型、表达式和语句、输入和输出基础、顺序、条件和循环控制结构、函数定义、函数调用和参数传递等关于程序设计的基本要素），基本数据结构和算法，使用C语言进行程序设计的方法以及使用程序解决问题的方法。

与本课程关联的有相同学期开设的“程序语言设计实验”独立实验课，此外，为增强软件开发能力，在短二期设置相应的能力训练实践课程“软件基础训练”。

本课程为计算机学科的多个后续课程打下基础，如计算机网络、课外创新实践等。

三、课程内容及基本要求第一部分：C语言程序设计（一）计算机与程序设计概述（2学时）主要内容：（1）计算机软件分类（2）计算机语言（3）程序执行的原理和过程（4）软件开发方法1.基本要求了解计算机软件的分类以及计算机语言的分类；理解程序执行的原理和过程；了解基本的软件开发方法和应用软件的开发方法。