数据结构下发习题2014.pdf

第一部分 数据结构 一 选择题 1 对一个算法的评价 不包括如下 B 方面的内容 A 健壮性和可读性 B 并行性 C 正确性 D 时空复杂度 2 对线性表 在下列哪种情况下应当采用链表表示 B A 经常需要随机地存取元素 B 经常需要进行插入和删除操作 C 表中元素需要占据一片连续的存储空间 D 表中元素的个数不变 3 一个栈的输入序列为 1 2 3 则下列序列中不可能是栈的输出序列的是 C A 2 3 1 B 3 2 1 C 3 1 2 D 1 2 3 4 算法指的是 D A 计算机程序 B 解决问题的计算方法 C 排序算法 D 解决问题的有限运算序列 5 线性表采用链式存储时 结点的存储地址 B A 必须是不连续的 B 连续与否均可 C 必须是连续的 D 和头结点的存储地址相连续 6 设数据结构 A D R 其中 D 1 2 3 4 R r r 则数据结构 A 是 C A 线性结构 B 树型结构 C 图型结构 D 集合 7 二叉树中第 i i 1 层上的结点数最多有 C 个 A 2i B 2i C 2i 1 D 2i 1 8 设指针变量 p 指向单链表结点 A 则删除结点 A 的后继结点 B 需要的操作为 A A p next p next next B p p next C p p next next D p next p 9 设指针变量 p 指向单链表中结点 A 若删除单链表中结点 A 则需要修改指针的操作序 列为 A A q p next p data q data p next q next free q B q p next q data p data p next q next free q C q p next p next q next free q D q p next p data q data free q 10 设输入序列是 1 2 3 n 经过栈的作用后输出序列的第一个元素是 n 则输出 序列中第 i 个输出元素是 C A n i B n 1 i C n 1 i D 不能确定 11 设一条单链表的头指针变量为 head 且该链表没有头结点 则其判空条件是 A A head 0 B head next 0 C head next head D head 0 12 深度为 k 的完全二叉树中最少有 B 个结点 A 2k 1 1 B 2k 1 C 2k 1 1 D 2k 1 13 设指针变量 top 指向当前链式栈的栈顶 则删除栈顶元素的操作序列为 D A top top 1 B top top 1 C top next top D top top next 14 队列是一种 A 的线性表 A 先进先出 B 先进后出 C 只能插入 D 只能删除 15 由权值分别为 11 8 6 2 5 的叶子结点生成一棵哈夫曼树 它的带权路径长度为 B A 24 B 71 C 48 D 53 16 设某棵二叉树的中序遍历序列为 ABCD 前序遍历序列为 CABD 则后序遍历该二叉 树得到序列为 A A BADC B BCDA C CDAB D CBDA 17 设某完全无向图中有 n 个顶点 则该完全无向图中有 A 条边 A n n 1 2 B n n 1 C n2 D n2 1 18 设某有向图中有 n 个顶点 则该有向图对应的邻接表中有 B 个表头结点 A n 1 B n C n 1 D 2n 1 19 设无向图 G 中有 n 个顶点 e 条边 则其对应的邻接表中的表头结点和表结点的个数分 别为 D A n e B e n C 2n e D n 2e 20 设某强连通图中有 n 个顶点 则该强连通图中至少有 C 条边 A n n 1 B n 1 C n D n n 1 21 设某无向图有 n 个顶点 则该无向图的邻接表中有 b 个表头结点 A 2n B n C n 2 D n n 1 22 设无向图 G 中有 n 个顶点 则该无向图的最小生成树上有 b 条边 A n B n 1 C 2n D 2n 1 23 设按照从上到下 从左到右的顺序从 1 开始对完全二叉树进行顺序编号 则编号为 i 结 点的左孩子结点的编号为 b A 2i 1 B 2i C i 2 D 2i 1 24 程序段 s i 0 do i i 1 s s i while inext 0 C head next head D head 0 26 设某棵二叉树的高度为 10 则该二叉树上叶子结点最多有 c A 20 B 256 C 512 D 1024 27 设指针变量 top 指向当前链式栈的栈顶 则删除栈顶元素的操作序列为 d A top top 1 B top top 1 C top next top D top top next 28 数据的最小单位是 a A 数据项 B 数据类型 C 数据元素 D 数据变量 29 设一个有序的单链表中有 n 个结点 现要求插入一个新结点后使得单链表仍然保持有序 则该操作的时间复杂度为 d A O log2n B O 1 C O n2 D O n 30 设一棵 m 叉树中度数为 0 的结点数为 N0 度数为 1 的结点数为 Nl 度数为 m 的 结点数为 Nm 则 N0 c A Nl N2 Nm B l N2 2N3 3N4 m 1 Nm C N2 2N3 3N4 m 1 Nm D 2Nl 3N2 m 1 Nm 31 设连通图 G 中的边集 E a b a e a c b e e d d f f c 则 从顶点 a 出发可以得到一种深度优先遍历的顶点序列为 b A abedfc B acfebd C aebdfc D aedfcb 32 设输入序列是 1 2 3 n 经过栈的作用后输出序列的第一个元素是 n 则输出 序列中第 i 个输出元素是 c A n i B n 1 i C n 1 i D 不能确定 33 设一组权值集合 W 2 3 4 5 6 则由该权值集合构造的哈夫曼树中带权路径长 度之和为 d A 20 B 30 C 40 D 45 34 设一条单链表的头指针变量为 head 且该链表没有头结点 则其判空条件是 a A head 0 B head next 0 C head next head D head 0 35 设二叉树的先序遍历序列和后序遍历序列正好相反 则该二叉树满足的条件是 d A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子 36 深度为 k 的完全二叉树中最少有 b 个结点 A 2k 1 1 B 2k 1 C 2k 1 1 D 2k 1 37 设指针变量 front 表示链式队列的队头指针 指针变量 rear 表示链式队列的队尾指针 指 针变量 s 指向将要入队列的结点 X 则入队列的操作序列为 c A front next s front s B s next rear rear s C rear next s rear s D s next front front s 38 设某无向图中有 n 个顶点 e 条边 则建立该图邻接表的时间复杂度为 a A O n e B O n2 C O ne D O n3 39 设某哈夫曼树中有 199 个结点 则该哈夫曼树中有 个叶子结点 A 99 B 100 C 101 D 102 40 设用邻接矩阵 A 表示有向图 G 的存储结构 则有向图 G 中顶点 i 的入度为 b A 第 i 行非 0 元素的个数之和 B 第 i 列非 0 元素的个数之和 C 第 i 行 0 元素的个数之和 D 第 i 列 0 元素的个数之和 二 判断题二 判断题 20 分分 1 不论是入队列操作还是入栈操作 在顺序存储结构上都需要考虑 溢出 情况 对 2 完全二叉树中的叶子结点只可能在最后两层中出现 对 3 哈夫曼树中没有度数为 1 的结点 对 4 对连通图进行深度优先遍历可以访问到该图中的所有顶点 对 5 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列 对 6 由树转化成二叉树 该二叉树的右子树不一定为空 错 7 线性表中的所有元素都有一个前驱元素和后继元素 错 8 调用一次深度优先遍历可以访问到图中的所有顶点 错 9 满二叉树一定是完全二叉树 完全二叉树不一定是满二叉树 对 10 设一棵二叉树的先序序列和后序序列 则能够唯一确定出该二叉树的形状 错 11 设一棵树 T 可以转化成二叉树 BT 则二叉树 BT 中一定没有右子树 对 12 线性表的顺序存储结构比链式存储结构更好 错 三 填空题 1 队列的插入操作是在队列的 尾 进行 删除操作是在队列的 首 进行 2 对于一棵具有 n 个结点的二叉树 用二叉链表存储时 其指针总数为 2n 个 其中 n 1 个用于指向孩子 n 1 个指针是空闲的 3 对于一个具有 n 个顶点和 e 条边的有向图和无向图 在其对应的邻接表中 所含边结点分 别有 e 个和 2e 个 4 数据的逻辑结构被分为 集合 线性 树 和 图 四种 5 二叉树的前序遍历结点访问顺序是 abdgcefh 中序遍历的结点访问顺序是 dgbaechf 则 其后序遍历的结点访问顺序是 6 设完全有向图中有 n 个顶点 则该完全有向图中共有 n n 1 条有向条 设完全无向图 中有 n 个顶点 则该完全无向图中共有 n n 1 2 条无向边 7 设一棵三叉树中有 50 个度数为 0 的结点 21 个度数为 2 的结点 则该二叉树中度数为 3 的结点数有 14 个 8 高度为 h 的完全二叉树中最少有 2h 1 个结点 最多有 2h 1 个结点 9 设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF 则该二叉树的前序遍历 序列为 ABDECF 中序遍历序列为 DBEAFC 后序遍历序列为 DEBFCA 10 设一棵完全二叉树有 128 个结点 则该完全二叉树的深度为 8 有 64 个叶子结 点 11 设有向图 G 的存储结构用邻接矩阵 A 来表示 则 A 中第 i 行中所有非零元素个数之和 等于顶点 i 的 出度 第 i 列中所有非零元素个数之和等于顶点 i 的 入度 12 for i 1 t 1 s 0 inext p next p next s 设结点的指针域为 next 14 设无向图 G 中有 n 个顶点 则该无向图中每个顶点的度数最多是 n 1 4 设二叉树中度数为 0 的结点数为 50 度数为 1 的结点数为 30 则该二叉树中总共有 129 个结点数 15 设 F 和 R 分别表示顺序循环队列的头指针和尾指针 则判断该循环队列为空的条件为 F R 三 应用题 1 设完全二叉树的顺序存储结构中存储数据 ABCDE 要求给出该二叉树的链式存储结构 并给出该二叉树的前序 中序和后序遍历序列 解答 链式存储结构自己画图表示 前序 ABDEC 中序 DBEAC 后序 DEBCA 2 设给定一个权值集合 W 3 5 7 9 11 要求根据给定的权值集合构造一棵哈夫曼树 并计算哈夫曼树的带权路径长度 WPL 解答 哈夫曼树自己画图表示 WPL 78 四 算法设计题 1 统计出单链表 HL 中结点的值等于给定值 X 的结点数 int CountX LNode HL ElemType x 答 int CountX LNode HL ElemType x int i 0 LNode p HL i 为计数器 while p NULL if P data x i p p next while 出循环时 i 中的值即为 x 结点个数 return i CountX 第二部分 数据库及其应用基础 一 选择题 1 数据是信息的载体 信息是数据的 A 符号化表示 B 载体 C 内涵 D 抽象 2 通常所说的数据库系统 DBS 数据库管理系统 DBMS 和数据库 DB 三者之 间的关系是 A DBMS 包含 DB 和 DBS B DB 包含 DBS 和 DBMS C DBS 包含 DB 和 DBMS D 三者都不对 3 在数据库的三级模式结构中 描述数据库全局逻辑模式和特性的是 A 外模式 B 内模式 c 存储模式 D 模式 4 下列三个模式之间存在的映像关系正确的是 A 外模式 内模式 B 外模式 模式 C 模式 外模式 D 内模式 外模式 5 DBMS 是 A 应用程序 B 数据库系统 C 操作系统 D 在操作系统支持下的系统软件 6 数据库管理系统实现对数据库中的数据的插入 删除 修改等操作 这类功能是 A 数据操纵功能 B 数据定义功能 C 数据控制功能 D 数据管理功能 7 数据库三级模式的划分有利于保持数据库的 A 数据独立性 B 结构规范性 C 数据安全性 D 数据可操作性 8 在数据库的体系结构中 数据库存储的改变会引起 的改变 A 外模式 B 内模式 C 存储模式 D 模式 9 为了使数据库的模式保持不变 从而不必修改应用程序 必须通过改变模式与内模式 之间的映像来实现 使数据库具有 A 数据独立性 B 逻辑独立性 c 物理独立性 D 操作独立性 10 BS 是采用了数据库技术的计算机系统 DBS 是一个集合体 包含数据库 计算机硬 件 软件和 A 系统分析员 B 程序员 C 数据库管理员 D 操作员 11 在 Access 数据库中 专用于打印的是 A 表 B 查询 C 报表 D 页 12 在 Access 数据库中 对数据表进行统计的是 A 汇总查询 B 动作查询 C 选择查询 D 删除查询 13 在 Access 数据库中 对数据表求列平均值的是 A 汇总查询 B 动作查询 C 选择查询 D 追加查询 14 在 SQL 中 实现数据检索的语句是 A SELECT B INSERT C UPDATE D DEIETE 15 在 SQL 查询中 GROUPBY 语句用于 A 选择行条件 B 对查询进行排序 C 列表 D 分组条件 16 在 SQL 语言中 修改表结构的语句是 A CREATE B ALERT C UPDATE D SELECT 17 内部计算函数 sum 的意思是求所在字段内所有的值的 A 和 B 平均值 C 最小值 D 第一个值 18 条件语句 WHERE 工资额 1000 的意思是 A 工资大于 1000 元的记录 B 将工资大于 1000 元的记录删除 C 拷贝字段工资大于 1000 元的记录 D 将字段工资大于 1000 元的记录进行替换 19 用表 学生名单 创建新表 学生名单 2 所使用的查询方式是 A 汇总查询 B 动作查询 C 选择查询 D SQL 查询 20 在查询中统计某列中值的个数应使用 函数 A SUM B MAX C COUNTD AVG 21 下列关于窗体的说法中错误的是 A 窗体主要用来输入数据 B 窗体可以显示来自多个数据表中的数据 C 用户可以利用窗体对数据库中的相关数据进行添加 删除和修改 D 窗体每次可以浏览多条记录 22 以下不属于报表组成区域的是 A 报表页眉 B 主体 C 文本框 D 页面页眉 23 Access 报表的数据源来自 A 表 B 查询 C 报表 D 表和查询 二 填空题 1 数据是信息的 信息是数据的 2 在数据库的三级模式结构中 描述数据库全局逻辑结构和特性的是 3 是一个以同一的方式管理 维护数据库中的数据的一系列软件的集合 4 数据库三级模式体系结构的划分 有利于保持数据库的 5 数据库管理系统通常提供授权功能来控制不同用户访问数据库的权限 这主要是为了 实现数据库的 6 不同的实体是根据 的不同区分的 7 E R 模型是数据库设计的工具之一 用于建立数据库的 模型 8 就是对有异常的关系进行分解以消除异常的过程 9 数据流图是描述系统中数据流程的图形工具 表达了 的关系 1 0 是系统中数据的详细描述 是各类数据属性的清单 11 数据库管理系统最常用的模型有三种 分别是 和 12 在关系模型中 把现实世界的数据组织成一张张的二维表 这些表格称为 13 设关系模式 R 是第二范式 且每个非主属性都不传递依赖于 R 的主码 则称 R 是 的模式 14 分析建立数据库的必要性和可行性是数据库设计中 阶段的任务 15 需求分析阶段的主要成果是 它由数据流图和数据字典两部分组成 16 把 E R 图按照一定的转换规则 转换为与具体的 DBMS 所支持的数据模型相符合的 逻辑结构是 阶段的工作 17 的任务是对于给定的逻辑模型选取一个最适合应用环境的物理结构 l 8 是根据物理设计的结果产生一个具体的数据库和它的应用程序的过程 19 Access 2003 是一个 型数据库管理系统 20 Access 2003 的一个数据库存放在 个文件中 21 Access 2003 的数据库文件的扩展名为 22 Access 2003 是一个小型数据库管理系统 最多能为 台计算机组成的小型网络 服务 23 Access 2003 的对象包括 页 宏和模块 24 Access 提供三种创建表的方法 分别是使用向导创建表 和通过输入数据创 建表 25 如果在创建表中建立字段 姓名 其数据类型应当是 26 教学管理系统数据库 教学管理系统 mdb 中有 student lesson 和 test 三张表 表的结 构如下 表名 student 结构 表名 lesson 结构 表名 test 结构 对下面的 SQL 查询语句进行填空 1 显示所有学生的学号 姓名 系别 学号 姓名 系别 FROM 2 显示籍贯为天津的学生的姓名 性别 系别 籍贯 SEI ECT 姓名 性别 系别 籍贯 FROM student 籍贯 3 查询选修了 A02 号课程的学生的学号和成绩 查询结果按成绩升序排列 字段名称 字段类型 字段大小 学号 文本 7 姓名 文本 8 性别 是 否 1 系别 文本 10 籍贯 文本 20 字段名称 字段类型 字段大小 课程号 文本 3 课程名称 文本 20 字段名称 字段类型 字段大小 学号 文本 7 课程号 文本 3 成绩 数字 SEI CT 学号 成绩 FROM test WHERE A02 成绩 4 查询参加了三门以上 包括三门 课程考试的学生学号 SELECT 学号 FROMtest 学号 count 木 3 5 查询以 平均分 为标题的课程号为 B01 课程的平均分 SELECT 成绩 平均分 FROM test WHERE 课程号 B01 6 查询计算机系所有学生的学号 姓名 课程名称 成绩 SEt ECT student 学号 姓名 课程名称 成绩 FROM student lesson test WHERE 系别 计算机 lesson 课程号 test 课程 号 and 7 查询课程名称为 英语 并且英语成绩在 80 分以上 包括 80 分 的学生的学号 姓名 课 程名称和成绩 并按成绩降序排列 27 出版系统数据库中有作者 出版社和图书三张表 表的结构如下 表名 作者 结构 表名 出版社 结构 表名 结构 字段名称 字段类型 字段大小 作者编号 文本 5 作者姓名 文本 8 联系电话 文本 12 城市 文本 20 字段名称 字段类型 字段大小 出版社编号 文本 4 出版社名称 文本 20 城市 文本 10 字段名称 字段类型 字段大小 图书编号 文本 6 书名 文本 20 类别 文本 10 出版社编号 文本 4 作者编号 文本 5 价格 数字 4 完成下面的 sQL 查询语句 1 查询价格在 50 元以上图书的数量及其平均价格 2 查询最高和最低的图书价格 3 计算图书价格的总和 4 计算各类图书的平均价格 结果显示图书的类别及其平均价格 5 计算各类图书的平均价格 结果显示平均价格在 30 元以下的图书的类别及其平均价格 6 按图书的出版日期降序列出书名及其价格 7 按作者所在的城市列出作者的姓名 联系电话和城市 8 查询图书的书名及其出版社名称 9 查询 少儿类 的图书的图书编号 书名 作者和出版社 查询结果按图书编号升序显 示 四 操作题 1 假定一个部门的数据库包括如下信息 员工信息 员工号 姓名 性别 所在部门 部门信息 部门名称 部门主管 服务客户 部门所有员工 客户信息 客户号 客户名称 客户地址 画出这个数据库的 E R 图 参考答案 一 选择题 1 C 2 C 3 B 4 B 5 D 6 A 7 A 8 B 9 C 10 C 11 C 12 C 13 C 14 A 15 D 16 B 17 A 18 A 19