科目代码
828
科目名称
数据结构及程序设计
试卷总分
150
考试时间
3小时
参考书目
详见我校研招网招生专业目录
考试内容
一、程序设计
1、C语言基本数据类型及定义、数据运算及表达式
2、算法流程图表示
3、程序基本结构（顺序、分支、循环）、基本输入输出
4、函数、参数、返回值及其定义与使用
5、复杂数据类型（数组、指针、结构体、共用体等及其复合）的定义与使
用
二、数据结构与算法概述
1、数据结构的基本概念和术语
2、算法的描述和算法分析
三、线性表
1、线性表的定义
2、线性表的存储结构及基本操作
3、线性表的应用
四、栈和队列
1、栈和队列的定义
2、栈和队列的存储结构及基本操作
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、顺序文件、索引文件、索引顺序文件、直接存取文件、多重链表文件、
倒排文件等的基本存取方法。
1 2013年上海海事大学攻读硕士学位研究生入学考试试题
（重要提示：答案必须做在答题纸上，做在试题上不给分）
考试科目： 数据结构及程序设计
一、填空题（本题共20个空，每空1分，共20分）
1． 结构化程序由顺序、 （1） 和 （2） 三种基本结构组成
2． 设 int n=3; 则 ++n+1＝＝5 的结果是___ _(3) ____
3． 已知x=22,c=’A’,y=0, 则表达式（x>=y && c<’B’&&!y）的值为 (4) 。
4． 若自定义函数要求返回一个值，则在函数体内应有一条____(5)______语句；若自定义函
数要求不返回值，则应在该函数说明时加一个类型说明符 (6) 。
5. 当a=2,b=3,c=4时，执行下面语句后，a、b、c的值分别为 (7) 、 (8) 、 (9) 。
if (a>c)
b=a;a=c;c=b;
6.c中，字符串”hello”的长度为 (10) ，占用字节的内存数为 (11) 。
7.设sq 为一个顺序存储的栈，变量top指示栈顶元素的位置。作进栈操作时，必须判别
(12) 。如果把栈顶元素取到X中，需执行下列语句： (13) 。
8. 在单链表中，若要在指针P所指结点后插入指针S所指结点，则需执行下列语句：
S-〉next= P-〉next； (14) ；
9．在带有头结点的双链表L中，指针P所指结点是第一个元素结点的条件是 (15) 。
10．串中任意个连续的字符组成的子序列称为该串的 (16) 。
11．遍历图的方法通常有两种： (17) 和 (18) 。
12. （19） 是文件中可存取的基本单位， （20） 是文件中可使用的最小单位。
二、单项选择题（本题共10小题，每小题2分，共20分）
1. c中，转义字符是以( )开头的。
A． % B.\ C. & D.#
2．下列定义变量的语句中错误的是（ ）
A. int _int； B. double int_ ；C. char For； D.float US$；
上海海事大学2016年物流工程学院硕士研究生招生专业目录
电气工程（学术型）
01电机与电器02电力系统及其自动化
04电力电子与电力传动
05电工理论与新技术
40
①101思想政治理论
②201英语一
③301数学一
④820电路原理
《电路(第5版)》邱关源，高等教育出版社
515电力电子技术或516电力传动控制系统或554自动控制原理
电力电子技术：《电力电子技术（第5版）》王兆安，机械工业出版社；电力传动控制系统：《电力
传动控制系统》汤天浩，机械工业出版社；《电力拖动自动控制系统（第4版）》阮毅，机械工业出版社；
《自动控制原理》孙亮、杨鹏，北京工业大学出版社
080200机械工程（学术型）
01机械制造及其自动化
02机械电子工程
03机械设计及理论
35
①101思想政治理论
②201英语一
③301数学一
④805工程力学
《工程力学》单辉祖谢传锋合编，高等教育出版社，2004年1月第1版
下列科目中任选一门：
521机械设计基础或518微机原理或工程测试技术
《机械设计基础（第四版）》，杨可桢、程光蕴主编，高等教育出版社；《微机原理与接口技术》冯
博琴，清华大学出版社2002年；《机械工程测试技术基础》熊试波、黄长艺机械工业出版社，2011
081101控制理论与控制工程
01复杂系统控制与优化
02系统建模、分析与控制
03控制理论与应用
04电磁测量与机器视觉
20①101思想政治理论
②201英语一
③301数学一
④804自动控制原理
自动控制原理（第5版），胡寿松，科学出版社
518微机原理或519电子技术
微机原理：《微机原理与接口技术》冯博琴，清华大学出版社
电子技术：《电子技术基础》康华光，高等教育出版社
1.电路原理
2.计算机控制系统
1.电路原理：《电路》（第4版）邱关源高等教育出版社；
2.计算机控制系统：《计算机控制系统》(第2版)王锦标清华大学出版社文章来源：文彦考研
2016年全国硕士研究生入学统一考试计算机历年真题
一、单项选择题：1~40 小题，每小题2 分，共80 分。下列每题给出的四个选项中，只有一个选项符合试题要求。
1. 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n 的降序链表，则最坏情况下的时间复杂度是
A. O(n) B. O(m.n) C. O(min(m,n)) D. O(max(m,n))
2. 一个栈的入栈序列为1, 2,3, ,n ，其出栈序列是1 2 3 , , , , n p p p p 。若2 p . 3，则3 p 可能取值的个数是
A. n .3 B. n . 2 C. n .1 D. 无法确定
3. 若将关键字1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0 的分支结点的个数是
A. 0 B. 1 C. 2 D. 3
4. 已知三叉树T 中6 个叶结点的权分别是2，3，4，5，6，7，T 的带权(外部)路径长度最小是
A. 27 B. 46 C. 54 D. 56
5. 若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y，则X 的右线索指向的是
A. X 的父结点 B. 以Y 为根的子树的最左下结点
C. X 的左兄弟结点Y D. 以Y 为根的子树的最右下结点
6. 在任意一棵非空二叉排序树T1 中，删除某结点v 之后形成二叉排序树T2，再将v
插入T2 形成二叉排序树T3。下列关于T1 与T3 的叙述中，正确的是 I. 若v 是T1 的叶结点，则T1 与T3 不同
II. 若v 是T1 的叶结点，则T1 与T3 相同
III. 若v 不是T1 的叶结点，则T1 与T3 不同
IV. 若v 不是T1 的叶结点，则T1 与T3 相同
A. 仅I、III B. 仅I、IV C. 仅II、III D. 仅II、IV
