2022年上海电机学院专升本程序设计与数据结构考试大纲

2022年上海电机学院专升本程序设计与数据结构考试大纲发布，《高级语言程序设计》和《数据结构》课程是计算机类专业及相关专业的必修课程。

2022年上海电机学院专升本程序设计与数据结构考试大纲

一、 课程的性质与地位

《高级语言程序设计》和《数据结构》课程是计算机类专业及相关专业的必修课程。通过这两门课程的学习，使学生掌握C程序设计的基本概念和程序设计的思想和编程技巧;具备使用C语言开发小型软件系统的能力;为后续学习计算机操作系统原理、编译原理、数据库原理等课程打下坚实基础。并培养学生计算思维能力，提高学生分析问题和解决问题的能力。

二、考试内容

(一)C程序设计部分

1.C语言程序的结构

(1)程序的构成，main()函数和其他函数。

(2)头文件、数据说明，函数的开始和结束标志以及程序中的注释。

2.数据类型及其运算

(1)C的数据类型(基本类型、构造类型、指针类型、无值类型)及其定义方法。

(2)C运算符的种类、运算优先级和结合性。

(3)不同类型数据间的转换与运算。

(4)C表达式类型(赋值表达式、算术表达式、关系表达式、逻辑表达式、条件表达式、逗号表达式)和求值规则。

3.控制结构

(1)顺序结构、选择结构、循环结构

(2)用if和switch语句实现选择结构程序设计。

(3)用for、while和do-while实现循环结构程序设计。

(4)continue语句和break语句。

4.数组

(1)一维数组和二维数组的定义、初始化和数组元素的引用。

(2)字符串与字符数组。

5.函数

(1)函数的定义、类型和返回值。

(2)形式参数与实在参数，参数值传递。

(3)函数的调用、嵌套调用、递归调用。

(4)局部变量和全局变量，变量的存储类别，变量的作用域和生存期。

6.指针

(1)地址与指针变量的概念，指针变量的引用。

(2)一维、二维数组和字符串的地址以及指向变量、数组、字符串、函数、结构体的指针变量的定义。通过指针引用以上各类型数据。

(3)指针作为函数参数、返回指针值的函数。

(4)指针数组。

7.结构体与共同体

(1)用typedef说明一个新类型。

(2)结构体和共用体类型数据的定义和成员的引用。

(3)动态内存管理，单向链表的建立，结点数据的输出、删除与插入。

8.文件操作

(1)文件类型指针(FILE类型指针)。

(2)文件的打开与关闭(fopen()，fclose())。

(3)文件的读写(fputc()，fgetc()，fputs()，fgets()，fread()，fwrite()，fprintf()，fscanf()函数的应用)，文件的定位(rewind()，fseek()函数的应用)。

(二)数据结构部分

1.数据结构的研究内容

(1)数据的逻辑结构与存储结构。

(2)算法和算法分析。

2.线性表

(1)线性表的定义与运算。

(2)线性表的顺序存储与链式存储结构。

3.栈和队列

(1)栈和队列的定义与运算。

(2)栈和队列的存储和实现。

4.串

(1)串的定义与存储。

(2)串运算的实现：求串长、串连接、求子串、串比较、插入子串、删除子串、模式匹配。

5.多维数组和广义表

(1)特殊矩阵的压缩存储：对称矩阵、三角矩阵。

(2)稀疏矩阵的存储

(3)广义表的定义和运算

6.树和二叉树

(1)树的定义和术语。

(2)二叉树的性质、遍历、转换和应用。

(3)哈夫曼树及哈夫曼编码。

7.图

(1)图的定义和术语。

(2)图的存储：邻接矩阵、邻接表。

(3)图的遍历：深度优先搜索、广度优先搜索。

(3)图的连通性：无向图的连通分量和生成树。

(4)最短路径、拓扑排序、关键路径。

8.查找

(1)顺序查找、二分查找和分块查找。

(2)动态查找表：二叉排序树、平衡二叉树。

(3)哈希表的构造与处理冲突的方法。

9.排序

(1)插入排序：直接插入排序、二分插入排序、希尔排序。

(2)交换排序：冒泡排序、快速排序。

(3)选择排序：简单选择排序、堆排序。

(4)归并排序。

三、参考教材

1.C程序设计部分

《C程序设计教程与实验》(第3版) 清华大学出版社，吉顺如主编

《C程序设计习题集与课程设计指导》(第2版)电子工业出版社，吉顺如主编

2.数据结构部分

《实用数据结构基础》中国铁道出版社，陈元春等编著

四、考试题型

题型包含选择题、程序填空题、改错题、应用题、编程题等。