1、第 1 页 ，共 5 页 浙浙 江江 理理 工工 大大 学学 20152015 年硕士学位研究生招生入学考试试题年硕士学位研究生招生入学考试试题 考试科目：数据结构与数据库技术考试科目：数据结构与数据库技术 代码：代码：938 （请考生在答题纸上答题，在此试题纸上答题无效）（请考生在答题纸上答题，在此试题纸上答题无效） 第一部分：数据结构（本部分共第一部分：数据结构（本部分共 90 分）分） 从下面从下面 6 题中任选题中任选 4 题解答，按得分最高的题解答，按得分最高的 4 题给分，本部分合计得分题给分，本部分合计得分不超过不超过 90 分。分。 1已知一个线性表以单向链表结构存储，其头指针
2、为 head，结点的存储结构定义如下： typedef struct node int data; struct node *next; lnode; 这里，结点的数值域为 data，指针域为 next。试编写程序算法，逐个输出单向链表中的所有节点值，并求出节点值的最大值。 （本题 25 分） 2已知二叉树的根结点为 t，其二叉链表存储结构定义如下： typedef struct node char data; struct node *lch,*rch; tnode ; 这里，data 为结点的名称，lch 为结点的左孩子，rch 为节点的右孩子。试编写程序，利用中序（中根）遍历算法（递归或
3、非递归均可） ，判断节点名称为“x”的这个结点是否为叶子结点。 （本题 20 分） 3. 已知数组存储的有序表 r 共有 n 条记录，其存储结构如下： typedef struct int key; char *title; sequence; 第 2 页 ，共 5 页 这里，key 为记录的关键字值，title 为记录的名称。试编写程序，使用折半（二分）查找算法，查找并输出关键字值为 x 的这条记录对应的名称（即 title 值） ，并分析该算法的时间复杂度。 （本题 20 分） 4. 试编写一个函数，实现关键字的冒泡排序算法，并详细分析该算法的时间复杂度。（本题 25 分） 5. 给定一组
4、正整数序列 4，2，3，9，7，8 ，试完成下列两小题： （本题共 20 分） 构造该整数序列组成的二叉排序树，并给出该二叉树的中序（中根）遍历与后序（后根）遍历结果。 （12 分） 以上述整数序列为权重值，构造其对应的哈夫曼（Huffman）树，并计算其带权路径长度（即 WPL）值。 （8 分） 6解答题（本题包含两个小题，共 20 分） 已知有向图 G 的顶点 v= v1,v2,v3,v4,v5,v6 ，其邻接链表如下图 1 所示。从顶点 v1 出发，试分别给出该有向图的深度优先遍历和广度优先遍历结果。 （10 分） v1 v2 v5 v4 v2 v3 v5 v3 v6 v4 v5 v4
5、v6 v3 v6 图 1. 有向图 G 的邻接链表 已知一组关键字序列 15，92，124，5，27，28，18，6，36，34，30，26，32，259 ，将其用散列函数 H(key)=key % 11（%为取余数运算）按顺序散列到哈希（HASH）表 HT（0 : 10）中，用链地址法解决冲突。假设查找每一个元素的概率相同，试计算查找该哈希表中任一元素的平均查找长度。 （10 分） 第 3 页 ，共 5 页 第二部分：数据库技术（本部分共 60 分，每小题 10 分） 从下面从下面 10 个个题中任选题中任选 6 题解答， 按得分最高的题解答， 按得分最高的 6 题给分， 本部分合计得题给分
6、， 本部分合计得分不超过分不超过 60 分。分。 数据库 Sales 用来存放某企业销售数据，它有 4 张表，Products 表用来存储产品信息，Customers 表用来存储客户信息，Orders 表用来存储订单信息，OrderItems 表用来存储订单明细信息，各表结构如下： 1Products 表结构： 列名列名 类型类型 长度长度 规则规则 中文说明中文说明 ProductID 数值型 8 主键 产品编码 ProductName 字符型 30 非空 产品名称 Category 字符型 20 非空 产品类别 QuantityPerUnit 字符型 20 非空 规格型号 UnitPric
7、e 数值型 8, 2 成本单价 Products 表记录举例： ProductID ProductName Category QuantityPerUnit UnitPrice 1 Chai Beverages 10 boxes x 20 bags 18.20 2 Chang Beverages 24 12 oz bottles 19.50 3 Aniseed Syrup Condiments 12 550 ml bottles 10.25 4 Chef Antons Gumbo Mix Condiments 36 boxes 21.35 14 Tofu Produce 40-100 g pk
8、gs 23.25 15 Genen Shouyu Produce 24 - 250 ml bottles 15.5 77 Escargots de Bourgogne Seafood 24 pieces 13.25 2Customers 表结构： 列名列名 类型类型 长度长度 规则规则 中文说明中文说明 CustomerID 字符型 5 主键 客户编码 CustomerName 字符型 50 非空 客户名称 Address 字符型 60 单位地址 City 字符型 20 所在城市 Customers 表记录举例： CustomerID CustomerName Address City ALF
9、KI Alfreds Futterkiste Obere Str. 57 Berlin ANATR Ana Trujillo Emparedados y helados Avda. De la Constituci n 222 M xico D.F. ANTON Antonio Moreno Taquer a Mataderos 2312 M xico D.F. AROUT Around the Horn 120 Hanover Sq. London WILMK Wilman Kala Keskuskatu 45 Helsinki WOLZA Wolski Zajazd ul. Filtrow
10、a 68 Warszawa 第 4 页 ，共 5 页 3Orders 表结构： 列名列名 类型类型 长度长度 规则规则 中文说明中文说明 OrderID 数值型 8 主键 订单编号 CustomerID 字符型 5 非空，外键 客户编码 OrderDate 日期型 8 非空 订单日期 RequiredDate 日期型 8 要货日期 ShippedDate 日期型 8 发货日期 Orders 表记录举例： OrderID CustomerID OrderDate RequiredDate ShippedDate 10248 VINET 2009-07-04 2009-08-01 2009-08-
11、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 11526 HUNGO 2009-12-31 2010-02-13 11527 BONAP 2009-12-31 2010-03-10 4OrderItems 表结构： 列名列名 类型类型 长度长度 规则规则 中文说明中文说明 OrderID 数值型 8 外键 订单编号 ProductID 数值型 8 外键 产品编码 Un
12、itPrice 数值型 8,2 两位小数，单价大于 0 销售单价 Quantity 数值型 8 非空，默认为 0 销售数量 Amount 数值型 12,2 计算列（=unitprice*quantity） 销售额 OrderItems 表记录举例： OrderID ProductID Quantity UnitPrice Amount 10248 11 14 12.50 175.00 10248 42 9 10.40 93.60 10248 72 34 5.60 190.40 10249 14 18 9.50 171.00 10249 51 42 40.45 1698.90 10250 41
13、7 10.25 71.75 10250 51 42 35.25 1480.50 10250 65 80 19.28 1542.40 10251 22 60 21.55 1293.00 10251 57 35 20.00 700.00 10251 65 42 22.65 951.30 11526 12 76 51.30 3898.80 11526 33 34 3.85 130.90 11526 46 80 16.25 1300.00 11526 47 72 12.80 921.60 11527 31 55 16.86 927.30 11527 44 120 26.25 3150.00 11527
14、 67 75 18.90 1417.50 第 5 页 ，共 5 页 1. 使用 SQL 语句，完成以下各项功能（注：必要时一个小题可以用多条语句去实现） 利用产品表，检索 Seafood 这类产品中产品名称包含“fish”这一字符串的所有产品信息。 利用订单表，检索客户编码为“ANTON”的这个客户 2009 年 10 月份所有订单的订单号和订单日期。 利用多表连接，统计列出 2009 年产品名称为“tofu”的这个产品的销售量和销售额的合计值。 利用多表连接，统计列出 2009 年各个月份销售额的合计值，并按销售额从大到小排列。 利用多表连接，列出 2009 年 10 月份哪些客户购买了产品名称为“Tofu”的这个产品，要求列出客户编码和客户名称。 利用多表连接，检索 2009 年 10 月份哪些产品没有销售记录，要求列出产品编码和产品名称。 创建一个用户定义函数，输入一个客户编码，返回该客户的销售额在所有客户中的排名名次。 2. 使用关系代数，完成以下各项查询 检索产品表中单价在1020元之间的所有Seafood类别的产品， 要求列出产品编码、产品名称、产品类别和单价。 检索 2009 年购买过“Tofu”这个产品的那些客户的信息，要求列出客户编码和客户名称。 检索哪些客户没有购买过“Tofu”或“Chang”这两个产品，要求列出其客户编码和客户名称。
