2018年扬州大学858程序设计与数据结构考研真题试题试卷.pdf

根据给定的文件信息，我们可以推断出这份文档包含了2018年扬州大学研究生入学考试中的858程序设计与数据结构科目的真题试卷。下面将对这份试卷可能涉及的重要知识点进行详细阐述。 ### 一、程序设计基础 #### 1. 数据类型与变量 - **基本数据类型**：整型(int)、浮点型(float/double)、字符型(char)等。 - **复合数据类型**：数组(array)、结构体(struct)、联合(union)等。 - 变量声明与初始化。 #### 2. 控制结构 - **顺序结构**：按照代码书写的顺序执行。 - **选择结构**：if语句、switch语句等。 - **循环结构**：for循环、while循环、do-while循环。 #### 3. 函数 - 函数定义与调用。 - 参数传递：值传递、引用传递。 - 返回值处理。 #### 4. 指针 - 指针的概念与使用。 - 指针与数组的关系。 - 动态内存分配与释放。 ### 二、算法基础 #### 1. 基本算法思想 - **递归**：函数自身调用实现问题解决。 - **分治法**：将大问题分解为小问题解决。 - **贪心算法**：每一步都做出局部最优选择。 #### 2. 排序算法 - **冒泡排序**：两两比较相邻元素，交换位置。 - **插入排序**：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 - **选择排序**：从未排序序列中挑选最小（或最大）的元素，存放到排序序列的起始位置。 - **快速排序**：选择一个基准元素，将数组分为小于基准和大于基准的两个子数组，然后递归排序子数组。 #### 3. 查找算法 - **顺序查找**：从头到尾逐一比较。 - **二分查找**：适用于有序数组，每次将查找区间缩小一半。 - **哈希查找**：利用哈希表提高查找效率。 ### 三、数据结构 #### 1. 线性结构 - **线性表**：数组、链表。 - **栈**：后进先出(LIFO)的线性表。 - **队列**：先进先出(FIFO)的线性表。 #### 2. 非线性结构 - **树**：二叉树、平衡二叉树(AVL树)、红黑树等。 - **图**：有向图、无向图、邻接矩阵表示、邻接表表示等。 - **图的遍历**：深度优先搜索(DFS)、广度优先搜索(BFS)。 ### 四、复杂度分析 - **时间复杂度**：算法执行所需时间与输入规模之间的关系。 - **空间复杂度**：算法执行所需内存与输入规模之间的关系。 - 大O符号表示法。 2018年扬州大学858程序设计与数据结构考研真题试卷主要考察了考生在程序设计基础、算法基础以及数据结构方面的掌握程度。这些知识点是计算机科学领域不可或缺的基础，也是进一步学习高级编程语言和技术的前提。通过对这些知识点的深入理解与实践应用，可以有效提升解决问题的能力。