浙江理工大学考研专业课试题938数据结构与数据库技术2017.pdf

1、第 1 页 ，共 4 页 浙浙 江江 理理 工工 大大 学学 20172017 年硕士研究生招生考试初试试题年硕士研究生招生考试初试试题 考试科目：考试科目： 数据结构与数据库技术数据结构与数据库技术 代码：代码： 938 （请考生在答题纸上答题，在此试题纸上答题无效）（请考生在答题纸上答题，在此试题纸上答题无效） 第一部分：数据结构（本部分共 90 分） 一、程序设计题 1已知单链表 lnode 结构如下，其头结点为 head，data 为结点的值域。假设单链表中已存在若干个结点，试编写程序算法，输入一个整数，在单链表中找到首个值比它大的结点，在该结点之前插入这个整数。如果找不到值比它大的结

2、点，则将该整数插入到链表的尾部。 （本题 20 分） struct lnode int data; struct lnode *next; 2已知二叉树的根结点为 t，其二叉链表结构如下： struct node int data; struct node *lch, *rch; 这里，data 为结点的值域，lch 为结点的左孩子，rch 为结点的右孩子。试编写一个非递归的程序算法，将树中每个结点的左孩子值与右孩子进行交换，使得左孩子值总是不大于右孩子值。 （本题 25 分） 3.试编写一个程序算法，在一个根结点为 t 的二叉排序树中查找某个关键字 k，计算查找这个关键字所需要的次数，并分析

3、算法的时间复杂度（最大查找长度和平均查找长度） 。 （本题 25 分） 4. 对于一组关键字 rn，有一种排序算法的思想如下：第一趟比较将最小的元素放在 r1中，最大的元素放在 rn中；第二趟比较将次小的放在 r2中，将次大的放在rn-1中，依次下去，直到待排序列为递增序列为止。试编写程序实现上述算法。（本题 20 分） 第 2 页 ，共 4 页 第二部分：数据库技术（本部分共 60 分，每小题 10 分） 数据库 Sales 用来存放某企业销售数据，它有 4 张表，Products 表用来存储商品信息，Customers 表用来存储客户信息，Orders 表用来存储订单信息，OrderIte

4、ms 表用来存储订单明细信息，各表结构如下： 1Products 表结构： 列名 类型 长度 规则 中文说明 ProductID 数值型 8 主键 商品编码 ProductName 字符型 30 非空 商品名称 Category 字符型 20 非空 商品类别 QuantityPerUnit 字符型 20 非空 规格型号 UnitPrice 数值型 8, 2 成本单价 Products 表记录举例： ProductID ProductName Category QuantityPerUnit UnitPrice 1 Chai Beverages 10 boxes x 20 bags 18.20

5、2 Chang Condiments 24 12 oz bottles 19.50 3 Aniseed Syrup Condiments 12 550 ml bottles 10.25 4 Chef Antons Gumbo Mix Beverages 36 boxes 21.35 14 Tofu Produce 40-100 g pkgs 23.25 77 Escargots de Bourgogne Seafood 24 pieces 13.25 2Customers 表结构： 列名 类型 长度 规则 中文说明 CustomerID 字符型 5 主键 客户编码 CustomerName 字

6、符型 50 非空 客户名称 Country 字符型 20 客户所在国家 City 字符型 20 客户所在城市 Address 字符型 80 客户地址 Customers 表记录举例： CustomerID CustomerName Country City Address ALFKI Alfreds Futterkiste Germany Berlin Obere Str. 57 ANATR Ana Trujillo Emparedados y helados Mexico Mexico D.F. Avda. de la Constitucion 2222 ANTON Antonio More

7、no Taqueria Mexico Mexico D.F. Mataderos 2312 AROUT Around the Horn UK London 120 Hanover Sq. BERGS Berglunds snabbkop Sweden Luleo Berguvsvogen 8 BLAUS Blauer See Delikatessen Germany Mannheim Forsterstr. 57 第 3 页 ，共 4 页 BLONP Blondesddsl p re et fils France Strasbourg 24, place Kleber BOLID Bolido

8、 Comidas preparadas Spain Madrid C/ Araquil, 67 BONAP Bon app France Marseille 12, rue des Bouchers BOTTM Bottom-Dollar Markets Canada Tsawassen 23 Tsawassen Blvd. 3Orders 表结构： 列名 类型 长度 规则 中文说明 OrderID 数值型 8 主键 订单编号 CustomerID 字符型 5 非空，外键 客户编码 OrderDate 日期型 8 非空 订单日期 RequiredDate 日期型 8 要货日期 ShippedD

9、ate 日期型 8 发货日期 Orders 表记录举例： OrderID CustomerID OrderDate RequiredDate ShippedDate 10248 VINET 2009-07-04 2009-08-01 2009-08-16 10249 TOMSP 2009-07-05 2009-08-16 2009-08-16 10250 HANAR 2009-08-08 2009-09-05 2009-09-07 10251 VINET 2009-08-11 2009-09-15 2009-09-12 4OrderItems 表结构： 列名 类型 长度 规则 中文说明 Ord

10、erID 数值型 8 外键 订单编号 ProductID 数值型 8 外键 商品编码 UnitPrice 数值型 8,2 两位小数，单价大于 0 销售单价 Quantity 数值型 8 非空，默认为 0 销售数量 Amount 数值型 12,2 计算列（=unitprice*quantity） 销售额 OrderItems 表记录举例： OrderID ProductID UnitPrice Quantity Amount 10248 11 14 12.5 175.00 10248 42 9 10.4 93.60 10248 72 34 5.6 190.40 10249 14 18 9.5 1

11、71.00 10249 51 42 40.45 1698.90 10250 41 7 10.25 71.75 10250 51 42 35.25 1480.50 第 4 页 ，共 4 页 试使用 SQL 语句，完成以下各项功能（注：必要时一个小题可以用多条语句去实现） 1） 检索哪些商品的名称中有而且只包含有一个“er”字符串。 2）检索单价排名最高的前 10 个商品中，有哪些商品属于 Beverages 类别。 3） 检索计算Around the Horn这个客户2009年购买Tofu这个商品的销售量和销售额。（提示：使用聚合函数） 4）检索所有德国客户中（其 Country 列值为“Germany” ）哪些客户没有购买过 Tofu这个商品。（提示：使用子查询） 5）检索销售额最大的前 30%的客户中，哪些客户购买 Tofu 这个商品的次数最多。（提示：使用子查询） 6）创建一个存储过程或用户定义函数，输入一个客户编码，返回这个客户销售额在所有客户销售额中的排名名次。 （提示：可以使用排名函数）