1、第 1 页 ，共 4 页浙浙 江江 理理 工工 大大 学学20162016 年硕士学位研究生招生入学考试试题年硕士学位研究生招生入学考试试题考试科目考试科目：数据结构与数据库技术数据结构与数据库技术代码代码：938（请考生在答题纸上答题请考生在答题纸上答题，在此试题纸上答题无效在此试题纸上答题无效）第一部分第一部分：数据结构数据结构（本部分共本部分共 90 分分）一、 程序设计题 （按得分最高的 4 小题计分， 本题得分最多不超过 90 分）1已知单链表 lnode 结构如下，其头结点为 head，data 为结点的值域。试编写程序算法，使用一次循环求出该单链表中 data 域的最大值和次大值
2、。 （本题 20 分）struct lnode int data;struct lnode *next;2已知二叉树的根结点为 t，其二叉链表结构如下：struct node int data;struct node *lch, *rch;这里，data 为结点的值域，lch 为结点的左孩子，rch 为结点的右孩子。试编写一个非递归函数，利用中序遍历算法，判断 data 值为 x 的这个结点是否存在兄弟节点。（本题 25 分）3. 试编写程序，实现数据的简单选择排序算法，并分析算法的时间复杂度。 （本题20 分）4. 试编写程序算法，采用单链表作为存储结构（结构如下定义） ，实现直接插入排序算
3、法，并进行算法时间复杂度分析。 （本题 25 分）struct nodeint data;struct node *next; lnode;第 2 页 ，共 4 页5. 设有一组关键字 47, 55, 15 ,42, 94, 17, 5, 80 ，写出经过下列各种排序后得到的关键字序列。 （本题共 25 分）1）经过第一轮快速排序后得到的序列。 （8 分）2）经过第二轮希尔排序（d2=2）后得到的序列。 （8 分）3）采用堆排序形成堆，当堆中第一个元素被输出后，经过调整和恢复堆，这时对堆进行层次遍历，输出得到的序列。 （9 分）6已知线性表 56, 80, 17, 34, 28, 75, 67
4、, 51, 97 ，计算下列不同存储结构中查找一个结点的平均查找长度。 （本题共 25 分）使用散列存储，散列函数为 h(k)=k%11，散列地址空间为 010，采用线性探查法解决冲突，计算结点的平均查找长度。 （15 分）使用二叉排序树存储，即以上述序列构造一个二叉排序树，计算该二叉排序树上结点的平均查找长度。 （10 分）第二部分：数据库技术（本部分共 60 分）二、解答题（每小题 10 分，按得分最高的 6 小题计分，本题得分最多不超过 60 分）数据库 Sales 用来存放某企业销售数据，它有 4 张表，Products 表用来存储产品信息，Customers 表用来存储客户信息，Or
5、ders 表用来存储订单信息，OrderItems 表用来存储订单明细信息，各表结构如下：1Products 表结构：列名类型长度规则中文说明ProductID数值型8主键产品编码ProductName字符型30非空产品名称Category字符型20非空产品类别QuantityPerUnit字符型20非空规格型号UnitPrice数值型8, 2成本单价第 3 页 ，共 4 页Products 表记录举例：ProductIDProductNameCategoryQuantityPerUnitUnitPrice1ChaiBeverages10 boxes x 20 bags18.202ChangB
6、everages24 12 oz bottles19.503Aniseed SyrupCondiments12 550 ml bottles10.254Chef Antons Gumbo MixCondiments36 boxes21.3514TofuProduce40-100 g pkgs23.2577Escargots de BourgogneSeafood24 pieces13.252Customers 表结构：列名类型长度规则中文说明CustomerID字符型5主键客户编码CustomerName字符型50非空客户名称Address字符型60单位地址City字符型20所在城市Custo
7、mers 表记录举例：CustomerIDCustomerNameAddressCityALFKIAlfreds FutterkisteObere Str. 57BerlinANATRAna Trujillo Emparedados y heladosAvda. De la Constitucin 222Mxico D.F.ANTONAntonio Moreno TaqueraMataderos2312Mxico D.F.AROUTAround the Horn120 Hanover Sq.London3Orders 表结构：列名类型长度规则中文说明OrderID数值型8主键订单编号Custo
8、merID字符型5非空，外键客户编码OrderDate日期型8非空订单日期RequiredDate日期型8要货日期ShippedDate日期型8发货日期Orders 表记录举例：OrderIDCustomerIDOrderDateRequiredDateShippedDate10248VINET2009-07-042009-08-012009-08-1610249TOMSP2009-07-052009-08-162009-08-1610250HANAR2009-08-082009-09-052009-09-0710251VINET2009-08-112009-09-152009-09-12第
9、4 页 ，共 4 页4OrderItems 表结构：列名类型长度规则中文说明OrderID数值型8外键订单编号ProductID数值型8外键产品编码UnitPrice数值型8,2两位小数，单价大于 0销售单价Quantity数值型8非空，默认为 0销售数量Amount数值型12,2计算列（=unitprice*quantity）销售额OrderItems 表记录举例：OrderIDProductIDUnitPriceQuantityAmount10248111412.5175.001024842910.493.601024872345.6190.401024914189.5171.001024
10、9514240.451698.901025041710.2571.7510250514235.251480.501. 使用 SQL 语句，完成以下各项功能（注：必要时一个小题可以用多条语句去实现）在客户表 Customers 中检索哪些客户其名称中包含“en”或“th”这两个字符串。根据产品表 Products 数据， 统计列出 Beverages 类产品中单价最低的这些产品的信息。根据各表数据，统计列出 2009 年度“Around the Horn”的这个客户购买“Tofu”的这个产品的销售额。根据各表数据，统计列出哪些客户 2009 年度没有购买过“Tofu”这个产品。根据产品表 Products 数据，统计列出“Tofu”这个产品的单价在所有产品中的排名名次（从大到小排序） 。根据各表数据，统计列出 2009 年度销售额排名前 30%的这些客户的信息。根据各表数据， 统计哪些客户 2008 年度和 2009 年度销售额都在当年排名前 30%，列出这些客户的编码和名称。检索哪些客户 2009 年度 16 月份每个月都有销售订单记录。2. 使用关系代数，完成以下各项查询检索哪些客户 2009 年度购买过“Tofu”这个产品，要求列出客户编码和名称。检索哪些客户购买过名称为“Tofu”和“Longlife Tofu”这两个产品。
