山东科技大学
2018年硕士研究生入学考试试题
考试科目：数据结构与操作系统 科目代码：823
《数据结构》部分
一、简答题（30分，每题5分）
1、串、数组、广义表从元素间关系上可以看成线性结构，它们与
一般意义上的线性表相比有何特殊性？
2、借助栈可以实现更复杂的操作，请简述如何利用栈实现对表达
式中括号是否匹配的检验。
3、基于关键字比较的查找算法所能达到最优时间复杂度是？能否
设计一种与问题规模无关的查找算法？请给出基本思路。
4、图的广度优先遍历与树的何种遍历策略相似？请给出简单解释。
5、《数据结构》中经常采用“树形化组织”的方式来整理数据，
比如折半查找表、二叉排序树、大顶堆/小顶堆等，请简述这样
做的优点。
6、何为稳定的排序方法？何为不稳定的排序方法？哪些排序算法
是不稳定的？
二、综合应用题（40分，每题10分）
1、假设用于通信的电文共有8个字母A,B,C,D,E,F,G,H组成，字
母在电文中出现的频率分别是{0.2，0.04，0.06，0.02，0.12，
0.24，0.25，0.07}。
①试为这8个字符设计哈夫曼编码；
②试设计另一种由二进制表示的等长编码方案；。
一、简答题（每小题4分，共20分）1 请简述数据库系统的组成。
2 请简要比较自主存取控制和强制存取控制的异同。
3 请叙述参照完整性检查和违约处理的基本原理。
4 ER图向关系模型转换的基本规则有哪些？5 恢复的实现技术有哪些？二、（共45分）某超市数据库的关系模式包括商品表Product、订单表Order、订单细节表Detail和供应商表Supplier，详细描述见各表。
商品表Product字段名称 含义 数据类型 约束pno 商品编号 int 主键pname 商品名称 Varchar(100)price 价格 Numberic(9,2)type 商品类别 char(10)sno 供应商编号 int 外键，引用Supplier表订单表 Order字段名称 含义 数据类型 约束ono 订单编号 int 主键odate 订单产生时的日期时间,格式为年‐月‐日 时:Datetime分:秒，例如2016‐11‐11 13:50:23订单细节表 Detail字段名称 含义 数据类型 约束dno 订单细节编号 int 主键ono 订单编号 int 外键，引用Order表pno 商品编号 int 外键，引用Product表Quantity 销售数量 Numberic(5,2)sellingprice 销售单价 Numberic(9,2)供应商表Supplier字段名称 含义 数据类型 约束sno 供应商编号 int 主键sname 供应商名称 Varchar(100)address 地址 Varchar(100)contacts 联系人 Varchar(100)zip 邮政编码 char(6)求解下列问题：1 请用关系代数表示下列查询（15分）（1）查询价格小于等于100.00的商品的供应商名称。
（2）查询在2016年没有任何商品销售的供应商名称。
（3）查询联系人为“张山”的供应商编号、名称与地址。
2 请用SQL语言表示下列查询（15分）(1)查询包含“手机”类商品的订单的编号与日期。
