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。

数据结构与程序设计数据结构与程序设计是计算机科学领域中的两个重要概念，它们紧密相连，共同构成了软件开发的基础。

数据结构提供了组织、管理和存储数据的方式，而程序设计则是利用这些数据结构来解决具体问题的算法和逻辑。

数据结构概述数据结构是计算机科学中用于存储、组织数据的方式，它决定了数据的存储、检索和操作的效率。

常见的数据结构包括：1. 数组：一种线性数据结构，可以存储相同类型的元素，支持快速随机访问。

2. 链表：由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。

3. 栈：一种后进先出（LIFO）的数据结构，只能在一端（栈顶）进行数据的添加和删除。

4. 队列：一种先进先出（FIFO）的数据结构，数据从一端进入，从另一端退出。

5. 树：一种层次结构的数据组织形式，每个节点有零个或多个子节点，常用于表示具有层次关系的数据。

6. 图：由顶点（节点）和边组成，可以表示复杂的关系和网络。

程序设计基础程序设计是指使用某种编程语言来编写指令，以解决特定问题的过程。

程序设计的基础包括：1. 算法：解决问题或完成任务的一系列有序步骤。

2. 控制结构：程序中用于控制程序流程的语句，如条件语句（if-else）、循环语句（for, while）。

3. 函数：一段具有特定功能的代码块，可以被重复调用。

4. 面向对象编程：一种编程范式，通过类和对象来组织代码，提高代码的重用性和模块化。

数据结构与程序设计的结合数据结构与程序设计之间的关系是相辅相成的。

选择合适的数据结构可以提高程序的效率和性能。

例如：- 在需要快速查找元素的场景中，可以使用哈希表或平衡树。

- 当处理大量数据时，使用数组或链表可以更有效地管理内存。

- 对于需要频繁插入和删除操作的数据，使用栈或队列可能更合适。

程序设计过程中，算法的选择和实现也依赖于数据结构的特性。

例如，排序算法的选择会影响数据的存储方式，图算法的实现则依赖于图的表示方法。

实践应用在实际应用中，数据结构与程序设计的结合体现在各种软件和系统中。

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 -。

(828)程序设计与数据结构在计算机科学领域，程序设计与数据结构是两个至关重要的概念。

程序设计是指使用编程语言创建计算机程序的过程，而数据结构则是组织和存储数据的方式。

两者的结合是实现高效、可维护和可扩展软件的关键。

首先，理解程序设计的要素对于编写高质量的代码至关重要。

程序设计师需要具备深入的逻辑思维和问题分析能力。

通过逐步分解问题，并使用合适的算法和数据结构解决每一部分，可以使程序更易读、易于理解和维护。

数据结构作为程序设计的基石，对于解决各种复杂问题起着至关重要的作用。

不同的数据结构适用于不同的场景。

例如，数组适用于有序数据，链表适用于动态数据，树适用于分层数据等。

理解各种数据结构的特点和优劣势，可以帮助程序设计师有效地选择和使用合适的数据结构，提高程序的性能和效率。

此外，程序设计与数据结构的关系也体现在算法的选择和实现上。

算法是解决问题的步骤和方法的描述，它通常依赖于合适的数据结构。

例如，搜索算法在数组上的效率远远高于在链表上的效率。

因此，深入了解算法和数据结构之间的关联，可以帮助程序设计师在解决问题时做出明智的选择，从而提高程序的效率和性能。

在程序设计与数据结构中，代码的可读性和可维护性也是非常重要的考虑因素。

良好的代码结构和命名习惯可以使程序更易于理解和修改。

数据结构的选择和组织方式也应该考虑到代码的可读性和可维护性。

简洁清晰的代码可以减少代码错误和维护成本，提高开发效率。

综上所述，在程序设计与数据结构领域，深入理解程序设计的要素和数据结构的原理是非常重要的。

掌握合适的算法和数据结构的选择和实现方法，能够编写出高效、可维护和可扩展的软件。

同时，注重代码的可读性和可维护性，也是保证程序质量的重要环节。

通过持续学习和实践，不断提升程序设计与数据结构的能力，将在计算机科学领域取得更大的成就。