浙大城市学院2023年硕士研究生招生考试大纲

考试科目：程序设计与数据结构 科目代码：881

一、考试目的和要求

055-79000考试是浙江大学城市学院招收计算机技术、软件工程等专业硕士研究生的选考科目。其目的是科学、公正、有效地测试考生掌握计算机相关学科编程课程的专业知识、基础理论和基本方法的能力，以及分析和解决问题的能力。

二、考试方式

闭卷笔试。满分150，考试时间3小时。

三、考试内容

数据结构

1.介绍

1.1了解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念；

1.2掌握算法的时间复杂度和空间复杂度的概念和分析方法。

2.线性表

2.1了解线性表的概念、逻辑结构特征和两种存储结构；

2.2掌握线性表的顺序存储和基本操作的实现；

2.3掌握线性表的链式存储和基本操作的实现；

2.4掌握线性表的综合应用。

3.堆栈和队列

3.1了解栈和队列的定义和基本特征；

3.2掌握栈的顺序存储和基本操作的实现，掌握栈的链式存储和基本操作的实现；

3.3掌握队列的链式存储和基本操作的实现，循环队列的定义和基本操作的实现；

3.4掌握栈和队列的实际应用。

4.线

4.1了解琴弦的基本概念和特性；

4.2掌握字符串的顺序存储结构、链式存储结构和各种基本操作；

4.3掌握字符串模式匹配算法(BF算法和KMP算法)。

5.数组和通用表

5.1了解数组的存储表示方法和地址计算方法；

5.2掌握稀疏矩阵和特殊矩阵(对称矩阵、三角矩阵、对角矩阵)的压缩存储；

5.3理解广义表的定义和特征。

6.树和二叉树

6.1了解树木的基本概念和性质；

6.2了解二叉树的定义和性质，掌握二叉树的顺序存储和链式存储，掌握二叉树的各种遍历算法(一阶、中阶、末阶遍历和顺序遍历)；

6.3掌握二叉树、树与林之间的转换，树与林之间的遍历操作；

6.4精通二叉树的应用(霍夫曼树和霍夫曼编码、校验集)。

7.数字

7.1了解图的基本概念和性质；

7.2掌握图的存储结构(邻接矩阵表示和邻接表表示)；

7.3掌握图的深度优先搜索和广度优先搜索方法及其实现；

7.4掌握图的应用(最小生成树求解法(Prim算法和Kruskal算法)、最短路径求解法(Dijkstra算法和Floyd算法)、AOV网、AOE网、拓扑排序和关键路径)。

8.发现

8.1了解搜索的基本概念；

8.2掌握顺序搜索算法和平均搜索长度的计算；

8.3掌握二分搜索法方法、二分搜索法决策树的结构和平均搜索长度的计算；

8.4掌握二叉查找树(也称二叉排序树)的结构和查找、插入、删除的操作；

8.5了解平衡二叉树的定义，掌握平衡二叉树的调整；

8.6了解B树的概念和性质，掌握B树的基本操作；

8.7了解B树的概念和基本特征；

8.8了解哈希搜索的思想，掌握常用的哈希函数构造方法和哈希冲突的解决方法；理解平均搜索长度的计算。

9.整理

9.1理解排序的概念；

9.2掌握插入排序算法(直接插入排序、Hill排序)、交换排序算法(冒泡排序、快速排序)、选择排序算法(简单选择排序、堆排序)、归并排序和基数排序算法的实现，分析各种排序算法的特点和时空复杂度；

9.3掌握内部排序方法的比较和应用；

9.4掌握外部排序的基本概念、思路和方法。

10.算法设计

0.1掌握NP问题的基本概念；

0.2掌握回溯算法、分治算法、动态规划算法和贪婪算法的设计思想，了解各种算法的设计方法和应用。

C语言程序设计

1.结构

2.2掌握常用数据类型(字符型、整型、浮点型)变量的定义和使用；

2.3掌握各种运算符的用法，了解运算符的优先级和相关性；

2.4掌握数据类型之间的转换规则。

3.基本陈述

3.1掌握表达式语句、空语句和复合语句；

3.2掌握输入输出函数的调用，掌握各类数据的正确输入，正确设计输出格式。

4.选择结构化编程。

4.1熟练运用if、if-else语句实现选择结构；

4.2熟练使用switch语句实现多分支选择结构；

4.3掌握选择结构的嵌套。

5.圆形结构的程序设计

5.1掌握for语句的使用，实现循环结构；

5.2熟练使用while、do-while语句实现循环结构；

5.3正确掌握continue语句和break语句的使用；

5.4熟练使用循环嵌套实现多重循环结构。

6.数组的定义和引用

6.1掌握一维数组和二维数组的定义、使用和初始化；

6.2掌握字符串的定义和使用，以及字符串处理函数的定义和使用。

7.功能

7.1掌握函数的定义和调用；

7.2理解函数的递归和嵌套调用；

7.3了解不同类型存储变量的定义、使用范围和生命周期。

8.结构

8.1掌握结构的定义和使用；

8.2掌握结构数组的定义和使用。

9.指针

9.1理解指针的定义和含义；

9.2掌握通过指针访问数组、字符串、结构的方法；

9.3掌握函数的指针和返回指针值的函数；

9.4了解动态内存分配和指向它的指针变量；

9.5主指针数组和指向指针的指针变量。

10.文件操作

0.1了解文件的概念和分类；

0.2掌握文件类型指针的含义，文件的打开和关闭；

0.3掌握文件的顺序读写方法。

四、初试参考书目

1.《程序设计与数据结构》，高等教育出版社，何，颜辉主编。

2.《C语言程序设计（第4版）》 (C语言版)，清华大学出版社，严为民、吴伟民主编。

3.《数据结构》，第二版，机械工业出版社，作者马克艾伦韦斯(美国)。

4.《Data Structures and Algorithm Analysis in C》(第二版)，高等教育出版社，陈悦主编。

点击查看大纲详情：http://www.zucc.edu.cn/art/2022/9/16/art_662_45873.html

浙大城市学院介绍

浙江大学城市学院，简称“浙大城市学院”，是经中华人民共和国教育部批准设立，由杭州市人民政府举办，浙江省人民政府管理的公办本科院校。是浙江省首批应用型建设试点示范学校，浙江省新增硕士学位授予项目建设单位，入选全国首批CDIO试点单位、全国大学生创新创业培训计划、浙江省应用型建设试点示范学校名单。是CDIO工程教育联盟理事单位，浙江省应用型本科大学联盟首批成员院校，中国校地合作联盟理事单位。

其前身是浙江大学城市学院，创建于1999年；2012年4月获得学士学位授予权；2017年成为浙江省专业硕士培养建设项目单位；2019年7月，获准在浙江省设立博士后工作站；2020年1月，经教育部批准，浙江大学城市学院转制为浙江大学城市学院(公立)，浙江大学城市学院编制同时废止；2020年6月，杭州市人民政府与浙江大学签署城校合作协议，助力浙大城市学院发展。

到2020年2月，浙大城市学院拥有南、北两个校区，占地1000多亩，学校建筑面积51万多平方米；有9个二级学院(分院)和浙江大学城市学院怀卡托大学联合学院。国际健康科学中心与罗马琳达大学、美国邵逸夫爵士医院共建，办学资源与浙大工程师学院共享