第 1 页 ，共 4 页浙 江 理 工 大 学2016年硕士学位研究生招生入学考试试题考试科目：数据结构与数据库技术 代码：938（请考生在答题纸上答题，在此试题纸上答题无效）第一部分：数据结构（本部分共90分）一、程序设计题（按得分最高的4小题计分，本题得分最多不超过90分）1已知单链表lnode结构如下，其头结点为head，data为结点的值域。试编写程序算法，使用一次循环求出该单链表中data域的最大值和次大值。（本题20分）structlnodeintdata;structlnode*next;2已知二叉树的根结点为t，其二叉链表结构如下：structnodeintdata;structnode*lch,*rch;这里，data为结点的值域，lch为结点的左孩子，rch为结点的右孩子。试编写一个非递归函数，利用中序遍历算法，判断data值为x的这个结点是否存在兄弟节点。（本题25分）3. 试编写程序，实现数据的简单选择排序算法，并分析算法的时间复杂度。（本题20分）4. 试编写程序算法，采用单链表作为存储结构（结构如下定义），实现直接插入排序算法，并进行算法时间复杂度分析。（本题25分）structnode intdata;structnode*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,51,97，计算下列不同存储结构中查找一个结点的平均查找长度。（本题共25分）使用散列存储，散列函数为h(k)=k%11，散列地址空间为010，采用线性探查法解决冲突，计算结点的平均查找长度。（15分）使用二叉排序树存储，即以上述序列构造一个二叉排序树，计算该二叉排序树上结点的平均查找长度。（10分）第二部分：数据库技术（本部分共60分）二、解答题（每小题10分，按得分最高的6小题计分，本题得分最多不超过60分）数据库Sales用来存放某企业销售数据，它有4张表，Products表用来存储产品信息，Customers表用来存储客户信息，Orders表用来存储订单信息，OrderItems表用来存储订单明细信息，各表结构如下：1Products表结构：列名 类型 长度 规则 中文说明ProductID 数值型 8 主键 产品编码ProductName 字符型 30 非空 产品名称Category 字符型 20 非空 产品类别QuantityPerUnit 字符型 20 非空 规格型号UnitPrice 数值型 8,2 成本单价第 3 页 ，共 4 页Products表记录举例：ProductID ProductName Category QuantityPerUnit UnitPrice1 Chai Beverages 10boxes x20bags 18.202 Chang Beverages 2412ozbottles 19.503 AniseedSyrup Condiments 12550mlbottles 10.254 ChefAntonsGumboMix Condiments 36boxes 21.35 14 Tofu Produce 40-100gpkgs 23.25 77 Escargots deBourgogne Seafood 24pieces 13.252Customers表结构：列名 类型 长度 规则 中文说明CustomerID 字符型 5 主键 客户编码CustomerName 字符型 50 非空 客户名称Address 字符型 60 单位地址City 字符型 20 所在城市Customers表记录举例：CustomerID CustomerName Address CityALFKI Alfreds Futterkiste Obere Str.57 BerlinANATR Ana Trujillo Emparedados yhelados Avda.DelaConstitución222 México D.F.ANTON Antonio Moreno Taquería Mataderos 2312 México D.F.AROUT AroundtheHorn 120HanoverSq. London 3Orders表结构：列名 类型 长度 规则 中文说明OrderID 数值型 8 主键 订单编号CustomerID 字符型 5 非空，外键 客户编码OrderDate 日期型 8 非空 订单日期RequiredDate 日期型 8 要货日期ShippedDate 日期型 8 发货日期Orders表记录举例：OrderID CustomerID OrderDate RequiredDate ShippedDate10248 VINET 2009-07-04 2009-08-01 2009-08-1610249 TOMSP 2009-07-05 2009-08-16 2009-08-1610250 HANAR 2009-08-08 2009-09-05 2009-09-0710251 VINET 2009-08-11 2009-09-15 2009-09-12 第 4 页 ，共 4 页4OrderItems表结构：列名 类型 长度 规则 中文说明OrderID 数值型 8 外键 订单编号ProductID 数值型 8 外键 产品编码UnitPrice 数值型 8,2 两位小数，单价大于0 销售单价Quantity 数值型 8 非空，默认为0 销售数量Amount 数值型 12,2 计算列（=unitprice*quantity） 销售额OrderItems表记录举例：OrderID ProductID UnitPrice Quantity Amount10248 11 14 12.5 175.0010248 42 9 10.4 93.6010248 72 34 5.6 190.4010249 14 18 9.5 171.0010249 51 42 40.45 1698.9010250 41 7 10.25 71.7510250 51 42 35.25 1480.50 1. 使用SQL语句，完成以下各项功能（注：必要时一个小题可以用多条语句去实现）在客户表Customers中检索哪些客户其名称中包含“en”或“th”这两个字符串。根据产品表Products数据，统计列出Beverages类产品中单价最低的这些产品的信息。根据各表数据，统计列出2009年度“AroundtheHorn”的这个客户购买“Tofu”的这个产品的销售额。根据各表数据，统计列出哪些客户2009年度没有购买过“Tofu”这个产品。根据产品表Products数据，统计列出“Tofu”这个产品的单价在所有产品中的排名名次（从大到小排序）。根据各表数据，统计列出2009年度销售额排名前30%的这些客户的信息。根据各表数据，统计哪些客户2008年度和2009年度销售额都在当年排名前30%，列出这些客户的编码和名称。检索哪些客户2009年度16月份每个月都有销售订单记录。2. 使用关系代数，完成以下各项查询检索哪些客户2009年度购买过“Tofu”这个产品，要求列出客户编码和名称。检索哪些客户购买过名称为“Tofu”和“Longlife Tofu”这两个产品。