CSE3860C期末考试试卷(B卷).pdf

1 北京化工大学北京化工大学 2013 2014 年第一学期年第一学期 软件技术基础 期末考试试卷 软件技术基础 期末考试试卷 班级 班级 学号 学号 姓名 姓名 分数 分数 题号题号 一一 二二 三三 四四 五五 六六 总分总分 得分得分 判断题答案填写判断题答案填写 编号 1 2 3 4 5 6 7 8 答案 选择题答案填写选择题答案填写 编号 1 2 3 4 5 6 7 8 9 10 答案 填空题答案填写填空题答案填写 1 2 3 4 5 6 7 8 一 判断题一 判断题 共共8分 每题分 每题1分分 1 线性表中的所有元素都有一个前驱元素和后继元素 2 图的两种遍历方式分别是深度优先遍历和广度优先遍历 3 在链表上可以实现折半查找算法 4 快速排序是一种不稳定的排序方法 5 原语是一种不可分割的操作 6 在现代操作系统中 死锁的发生是可以预测的 7 数据模型是数据库设计的核心 8 E R 图是进行数据库需求分析的有效工具 2 二 选择题二 选择题 共共20分 每空分 每空2分分 1 对一个算法的评价 不包括如下 方面的内容 A 健壮性和可读性 B 并行性 C 正确性 D 时空复杂度 2 栈和队列的共同特点是 A 只允许在端点处插入和删除元素 B 都是先进后出 C 都是先进先出 D 没有共同点 3 二叉树的第 k 层的结点数最多为 A 2k 1 B K 1 C K 1 D 2k 1 4 设一棵完全二叉树中有 65 个结点 则该完全二叉树的深度为 A 8 B 7 C 6 D 5 5 有如下二叉树遍历程序 实现的遍历为 void traverse BTNode bt if bt traverse bt left traverse bt right print bt data A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历 6 下面的调度算法中 进程调度算法适合多用户分时系统 A 先来先服务 B 轮转法 C 可抢占优先级 D 优先级 7 产生系统死锁的原因可能是由于 A 进程释放资源 B 一个进程进入死循环 C 多个进程竞争 资源出现了循环等待 D 多个进程竞争共享型设备 8 关系数据库具有严格的数学基础 主要基于 理论来处理数据 A 集合代数 B 分析方法 C 统计分析 D 布尔格 9 DBMS 通常可以向 申请所需计算机资源 A 数据库 B 操作系统 C 计算机硬件 D 应用程序 10 数据模型的三要素是 A 外模式 模式和内模式 B 层次模型 网络模型和关系模型 3 C 实体 属性和联系 D 数据结构 数据操作和完整性约束 三 填空题三 填空题 共共16分 每空分 每空2分分 1 常见的算法设计方法包括列举法 归纳法 递推法 和回溯法等 2 在链式线性表中第 idx 个数据元素之前插入数据元素 elem int insert LinkedList LL int idx ElemType elem llnode p s int j 开辟新结点空间开辟新结点空间 s llnode malloc sizeof llnode if s NULL return ERROR s data elem if idxlength LL return ERROR 寻找第寻找第 i 1 个结点个结点 for p LL head j 0 pj 将新结点插入到链表中将新结点插入到链表中 return OK 3 为了有效应用 Hash 查找技术 必须解决的两个问题是 和 4 进程由程序 数据和 组成 5 一次只允许一个进程访问的资源叫 6 SQL 语言的主要功能包括四个方面 分别是 查询 操纵和控制 四 问答题四 问答题 共共24分 每题分 每题6分分 1 什么是数据结构 它和算法有何关系 2 将关键字序列 9 31 26 19 1 13 2 11 27 16 5 21 依次填入长度为 13 的 Hash 表中 设 Hash 函数为 key mod 13 采用线性开放定址法来解决冲突 试求 Hash 表建立过程中各关键字冲突的次数 3 什么是进程 说明进程各状态是如何转化的 4 什么是 E R 图 构成 E R 图的基本要素是什么 五 程序设计题五 程序设计题 使用伪使用伪C语言描述 共语言描述 共20分分 1 编程实现折半查找算法 10 分 2 编程实现快速排序算法 10 分 4 六 数据库应用题六 数据库应用题 共共12分分 北京化大高科技有限公司人力资源部采用关系数据库来管理职员信息 使用的 关系模式如下所示 Employees 表结构 列名 数据类型 长度 是否允许为空 说明 EmployeeID char 6 否 员工编号 主键 Name char 10 否 姓名 Birthday datetime 8 否 出生日期 Sex bit 1 否 性别 默认值为 1 Address varchar 40 是 地址 Zip char 6 是 邮编 Phone char 12 是 电话号码 Email varchar 30 是 电子邮件 DeptID char 3 否 员工部门号 外键 Department 表结构 列名 数据类型 长度 是否允许为空 说明 DeptID char 3 否 部门编号 主键 DeptName char 20 否 部门名 要求唯一 Note text 文本 16 是 备注 Salary 表结构 列名 数据类型 长度 是否允许为空 说明 EmployeeID char 6 否 员工编号 主键 Income float 8 否 收入 要求输入的数据 大于 0 Outcome float 8 否 支出 试采用 SQL 语言完成下面的查询要求