1、若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时
背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选
若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s<0或虽然
s>0但物品数n<1,则无解。
（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true
（2）s,n-1 // Knap←Knap(s,n-1)
2、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
3、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A
的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。
4、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
2015年福建省专升本考试计算机科学类专业基础课考试大纲
C 语言程序设计（ 100 分）
一、考试要求： 1 ． 对 C 语言的语法、语义有较好的理解。
2 ． 能熟练地阅读 C 源程序，并具有初步分析程序的能力。
3 ． 初步掌握结构化程序设计的方法和技巧，能从分析问题入手，设计可行的算法，进
而用 C 语言编写结构良好的面向过程的程序。 4 ． 通过上机实验，掌握程序的调试和测试方法。
二、 考试内容
第一章 C 语言概述 • 了解 C 语言的发展、特点；
• 掌握 C 程序的基本结构；
3. 掌握 TURBO C 环境下 C 程序的上机步骤。
第二章 算法 • 理解算法的概念；
• 了解算法的表示方法；
• 理解组成结构化程序的三种基本 控制 结构；
4. 了解结构化程序设计的过程；
第三章 数据类型、运算符与表达式 • 了解 C 语言中数据类型的分类；
• 掌握整型、实型、字符型、字符串常量的表示方法；
• 掌握符号常量的定义和使用；
• 掌握变量的定义、初始化；
• 掌握算术、赋值、复合赋值、自增、自减、逗号运算符及表达式；
6. 掌握各类数值型数据间的混合运算。
第四章 输入输出 • 掌握赋值语句及使用；
• 了解字符输入输出（ get char 函数和 putchar 函数） ；
3. 掌握格式输入输出（ scanf 函数和 printf 函数） 。
第五章 选择结构 • 掌握关系、逻辑运算符及表达式；
• 掌握 if 语句的三种形式；
• 掌握 switch 语句及 break 语句的使用 ；
4. 要求能编写含有 if 语句嵌套结构的 程序。
第六章 循环结构 • 掌握 while 语句及应用；
• 掌握 do-while 语句及应用；
• 掌握 for 语句及应用；
• 掌握 break 语句在循环中的作用；
• 了解 continue 语句在循环中的作用；
6. 要求能编写含有二重循环结构的程序。 第七章 数组 • 掌握一维数组的定义、初始化及元素引用；
第1页
2015年上半年 数据库系统工程师 下午试卷 案例
第1题
【说明】某大学为进一步推进无纸化考试，欲开发一考试系统。系统管理员能够创建包括专业方向、课程编号、任课教师等相关考试基础信息，教师和学生进行考试相关的工作。系统与考试有关的主要功能如下。
（1）考试设置。教师制定试题（题目和答案），制定考试说明、考试时间和提醒时间等考试信息
，录入参加考试的学生信息，并分别进行存储。
（2）显示并接收解答。根据教师设定的考试信息，在考试有效时间内向学生显示考试说明和题目
，根据设定的考试提醒时间进行提醒，并接收学生的解答。
（3）处理解答。根据答案对接收到的解答数据进行处理，然后将解答结果进行存储。
（4）生成成绩报告。根据解答结果生成学生个人成绩报告，供学生查看。
（5）生成成绩单。对解答结果进行核算后生成课程成绩单供教师查看。
（6）发送通知。根据成绩报告数据，创建通知数据并将通知发送给学生；根据成绩单数据，创建通知数据并将通知发送给教师。
现采用结构化方法对考试系统进行分析与设计，获得如图1-1所示的上下文数据流图和图1-2所示的 0 层数据流图。
问题1.1 使用说明中的词语．给出图1-1中的实体E1-E2的名称。
问题1.2 使用说明中的词语，给出图1-2中的数据存储D1-D4的名称。
问题1.3 根据说明和图中词语，补充图1-2中缺失的数据流及其起点和终点。
问题1.4 图1-2所示的数据流图中，功能（6）发送通知包含创建通知并发送给学生或老师。请分解图 1-2 中加工（6），将分解出的加工和数据流填入答题纸的对应栏内。（注：数据流的起点和终点须使用加工的名称描述）
第2页
第2题
【说明】某大型集团公司的数据库的部分关系模式如下：
员工表：EMP（Eno,Ename，Age，Sex, Title)，各属性分别表示员工工号、姓名、年龄、性别和职称级别，其中性别取值为“男”“女”；
三级数据库技术真题2015年(1)
(总分100,考试时间90分钟)
一、单选题
1. 在数据库应用系统的需求分析阶段，确定系统吞吐量的工作属于______。
A. 数据处理需求分析 B. 业务规则需求分析
C. 性能需求分析 D. 安全性需求分析
2. 在一个ER图中，包含三个实体集，两个二元一对多联系，两个二元多对多联系，以及一个一元多对多联系。将该ER图转化为关系模型后，得到的关系模式个数是______。
A. 4个 B. 5个
C. 6个 D. 7个
3. DFD建模方法由数据项、处理、数据存储以及外部项组成。下列关于DFD表示方法的说法，错误的是______。
A. 数据流用箭头表示 B. 处理用矩形框表示
C. 数据存储用圆角矩形框表示 D. 外部项用菱形表示
4. IDEF1X是一种常用数据建模方法。下列关于IDEF1X标定型联系的表示实例，正确的是______。
A．
B．
C．
D．
5. 下列关于各种索引的说法，正确的是______。
A. 主索引一定是聚集索引 B. 聚集索引一定是主索引
C. 有序索引只适合范围查询 D. 散列索引只适合点查询
6. 连接操作是数据库中非常耗时的操作。下面列出了数据库中一些提高性能的做法：
Ⅰ．增加冗余列，也就是将一个表的列复制到另外一个表中
Ⅱ．反规范化，也就是降低表的规范化程度
Ⅲ．在相关列上建立索引
Ⅳ．将表组织为聚集文件
以上做法中，能提高连接操作性能或减少连接操作的是______。
A. 仅Ⅰ、Ⅱ和Ⅲ B. 仅Ⅰ、Ⅱ和Ⅳ
C. 仅Ⅱ、Ⅲ和Ⅳ D. 全部都是
7. 已知有关系：员工(员工名,性别,出生日期,工资,部门名)，对该关系有如下查询操作：
SELECT部门名,SUM(工资) FROM员工
WHERE性别="男" AND 出生日期 IS NOT NULL
GROUP BY 部门名
三级数据库技术真题2015年(2)
(总分：100.00，做题时间：90分钟)
一、单选题(总题数：30，分数：40.00)
1.在数据库应用系统需求分析阶段，需要分析系统应具有的性能指标。下列不属于数据库应用系统性能指标的是______。
（分数：1.00）
A.最大用户并发数
B.系统吞吐量
C.每TPS代价值
D.数据库增长速度 √
解析：[解析] 数据库应用系统的性能需求分析包括数据操作响应的时间或数据访问响应时间，系统吞吐量、允许并发访问的最大用户数、每TPS代价值。故答案为D项。
2.设在一个学校信息系统的ER图中，有教师、项目、学生三类实体，一名教师可以负责多个项目，每个项目只能有一个负责人，一名教师可以参与多个项目，一个学生只能参与一个项目，一个项目可以有多个学生和教师参与。将该ER图转化为关系模型后，得到的关系模式个数是______。
（分数：1.00）
A.4个 √
B.5个
C.6个
D.7个
解析：[解析] 根据题意，本题中存在3个实体，2个联系即教师和项目之间是多对多联系，项目和学生之间是一对多联系。在从ER图转换为关系模式时，实体转换为独立的模式，多对多联系转换为关系模式，一对多联系中一端并入到多端的实体中。因此本题中有3个实体转换的模式，1个多对多联系转换的关系模式，一共可以得到4个关系模式。故答案为A项。
3.DFD建模方法由四种基本元素组成，其中使用矩形框来表示的元素是______。
（分数：1.00）
A.数据流
B.处理 √
C.数据存储
D.外部项
解析：[解析] 在DFD中，数据流用箭头表示，处理用矩形框表示，数据存储用圆角矩形框表示，外部项用圆角框或者平行四边形框表示。故答案为B项。
4.从功能角度可以将数据库应用系统划分为四个层次，其中数据访问层设计的主要工作是______。
（分数：1.00）
A.进行人机界面设计
B.把业务活动表示为系统构件
