1、第 1 页 ，共 7 页浙浙 江江 理理 工工 大大 学学20182018 年硕士研究生招生考试初试试题年硕士研究生招生考试初试试题考试科目：数据结构与数据库技术考试科目：数据结构与数据库技术代码：代码：938（请考生在答题纸上答题，在此试题纸上答题无效）（请考生在答题纸上答题，在此试题纸上答题无效）第一部分：数据结构（本部分共第一部分：数据结构（本部分共 9090 分）分）一、单项选择题一、单项选择题（每小题每小题 3 分，本题共分，本题共 36 分分)1. 下列程序段所代表的算法的时间复杂度为。i=1;while(irear-next=HQ-front(B)HQ-front-next=HQ
2、-rear(C)HQ-front=HQ-rear(D)HQ-front-next=HQ-rear-next5. 在一个栈顶指针为 HS 的链栈中插入一个*s 结点时，应执行的操作为。(A)HS-next=s;s-next=HS-next;(B)s-next=HS-next; HS-next=s;(C)s-next=HS; HS=s;(D)s-next=HS; HS=HSnext;6. 有一组数值13, 21, 32, 17, 26，用以构造哈夫曼树，则其带权路径长度 WPL值为。(A)241(B)248(C)252(D)2707. 假设结点序列为50,30,90,60,95,70,48,18，
3、以此构成一棵二叉排序树，则在该二叉排序树上查找一个结点的平均查找长度为。(A)11/4(B)21/4(C)19/8(D)5/28. 假定对共有 144 个元素的线性表进行分块查找，若将表均匀地分为 x 块（每块元素个数相同） 。假设块查找和块内查找均采用顺序查找法，则在等概率情况下，若要使分块查找的平均查找长度 ASL 最小，则分块数 x 的值应为。(A)11(B)12(C)13(D)149. 已知一个带权图的顶点集 V 和边集 G 分别如下，则该图的最小生成树的权值为。第 2 页 ，共 7 页V=1, 2, 3, 4, 5, 6, 7, 8;E=(3,1)6， (3,4)7， (3,7)5，
4、 (1,2)3， (1,4)4， (4,7)8， (4,5)4， (7,8)5， (2,6)3，(2,5)5, (5,8)8, (5,6)5, (8,6)6,(A)24(B)29(C)30(D)3110. 当待排序的关键字个数 n 很小，且初始排列为逆序时，采用下列排序方法中的，算法的时间复杂度最小。(A)直接插入排序(B)简单选择排序(C)冒泡排序(D)快速排序11. 已知一个待散列存储的线性表17,80,56,34,26,75,67,51,93，散列函数为h(k)=k%11，散列地址空间为 010。若采用线性探查法解决冲突，则平均查找长度为。(A)4/3(B)13/9(C)17/9(D)1
5、9/912. 已知一组记录的关键字值为46,74,18,53,14,20,40,38,86， 按快速排序方法对该序列进行一趟排序后的结果是。(A)38,14,18,20,40,46,53,74,86(B)38,40,18,20,14,46,53,74,86(C)14,20,40,38,18,46,74,53,86(D)18,14,20,40,38,46,74,53,86二、程序填空题（每个空格二、程序填空题（每个空格 2 分，本题共分，本题共 24 分）分）1. 下列程序是将两个有序的单链表 lnode1 和 lnode2 合并成一个依然有序的单链表，试在下列空白处填入正确语句。typedef
6、 struct nodeint data;/数据域struct node *next;/指针域linklist;void sort(linklist *lnode1, linklist *lnode2)linklist *p1,*p2,*tmp;p1=lnode1;p2=(1);while(p1-next!=null & p2!=null)if (p1-next-datap2-data) tmp=(2);p2-next=p1-next;(3)=p2;p2=tmp;else p1=p1-next;if (p2!=null)(4);第 3 页 ，共 7 页2. 下列程序在单链表 head 上实现简
7、单选择排序算法，其中调用函数 GetMinKey，试在下列空白处填入正确语句。typedef struct nodeint data;/数据域struct node *next;/指针域linklist;linklist GetMinKey(linklist r)linklist minp;/minp 是较小值的指针minp = r;while(r-next!=null)if (minp-datar-next-data)minp = r-next;r = r-next;return minp; /返回较小值的指针void SelectSort(linklist head)linklist q,
8、 p=head-next;int temp;for(; p-next!=NULL; p=p-next)(5)=GetMinKey(6);if (p-data!=q-data)temp = p-data;（7）;（8）;3. 已知二叉排序树的根节点为 t，左孩子和右孩子分别为 lch 和 rch。下列程序将一个结点 x 插入到二叉排序树中，试在下列空白处填入正确语句。typedef struct node int data;struct node *lch, *rch;snode;snode *insert(snode *t, int x)snode *p, *q, *s;s=(snode *)
9、malloc(sizeof(snode);第 4 页 ，共 7 页s-data=x;if (t=null)(9);elsep=(10);while (p!=null) q=p;if (11)p=p-lch;else p=p-rch;if (12)q-lch=x;elseq-rch=x;return (t);三、三、程序设计题（本题程序设计题（本题 30 分分，任选，任选 2 小题小题解答，每小题解答，每小题 15 分，分，按得分按得分最高的最高的 2 小题小题计分）计分）1. 已知一颗二叉树的根节点为 t，其二叉链表存储结构定义如下。试编写程序，按照中序遍历非递归算法，计算 x 这个结点（数值
10、域为 x）之后输出的其它结点的个数。typedef struct node int data;/数值域struct node *lch,*rch; tnode ;这里，data 为结点数值域，lch 为结点的左孩子，rch 为结点的右孩子。2. 已知一个线性表以单链表结构存储， 单链表的头指针为 head， 结点结构定义如下：typedef struct nodeint data;/数值域struct node *next; lnode;试将该单链表中所有的奇数排在所有偶数之前。要求时间复杂度尽可能地少，结果仍放在原来的单链表中。3. 设哈希函数为HT， 解决冲突的方法为外链地址法， 哈希函数
11、采用除留余数法(k%p，k 为待删除的关键字，p 为小于基本哈希表容量 m 的质数)。若哈希表中某个位置上的 key 域值为零，则表示该位置未被占用。试编写程序，实现从用哈希表中删除关键字 k 的算法。第 5 页 ，共 7 页第二部分：数据库技术（本部分共 60 分，每小题 10 分。任选6小题解答，按得分最高的6小题计分，本部分合计得分不超过60分）数据库 Sales 用来存放某企业销售数据，它有 4 张表，Products 表用来存储商品信息，Customers 表用来存储客户信息，Orders 表用来存储订单信息，OrderItems 表用来存储订单明细信息，各表结构如下：1Produc
12、ts 表结构：列名类型长度规则中文说明ProductID数值型8主键商品编码ProductName字符型30非空商品名称Category字符型20非空商品类别QuantityPerUnit字符型20非空规格型号UnitPrice数值型8, 2成本单价Products 表记录举例：ProductIDProductNameCategoryQuantityPerUnitUnitPrice1ChaiBeverages10 boxes x 20 bags18.202ChangCondiments24 12 oz bottles19.503Aniseed SyrupCondiments12 550 ml
13、bottles10.254Chef Antons Gumbo MixBeverages36 boxes21.3514TofuProduce40-100 g pkgs23.2577Escargots de BourgogneSeafood24 pieces13.252Customers 表结构：列名类型长度规则中文说明CustomerID字符型5主键客户编码CustomerName字符型50非空客户名称Country字符型20客户所在国家City字符型20客户所在城市Address字符型80客户地址Customers 表记录举例：CustomerIDCustomerNameCountryCity
14、AddressALFKIAlfreds FutterkisteGermanyBerlinObere Str. 57ANATRAna Trujillo Emparedados yheladosMexicoMexico D.F.Avda. de la Constitucion 2222ANTONAntonio Moreno TaqueriaMexicoMexico D.F.Mataderos2312AROUTAround the HornUKLondon120 Hanover Sq.第 6 页 ，共 7 页BERGSBerglunds snabbkopSwedenLuleoBerguvsvogen
15、 8BLAUSBlauer See DelikatessenGermanyMannheimForsterstr. 57BLONPBlondesddsl pre et filsFranceStrasbourg24, place KleberBOLIDBolido Comidas preparadasSpainMadridC/ Araquil, 67BONAPBon appFranceMarseille12, rue des BouchersBOTTMBottom-Dollar MarketsCanadaTsawassen23 Tsawassen Blvd.3Orders 表结构：列名类型长度规则
16、中文说明OrderID数值型8主键订单编号CustomerID字符型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-0
17、8-112009-09-152009-09-124OrderItems 表结构：列名类型长度规则中文说明OrderID数值型8外键订单编号ProductID数值型8外键商品编码UnitPrice数值型8,2两位小数，单价大于 0销售单价Quantity数值型8非空，默认为 0销售数量Amount数值型12,2计算列（=unitprice*quantity）销售额OrderItems 表记录举例：OrderIDProductIDUnitPriceQuantityAmount10248111412.5175.001024842910.493.601024872345.6190.4010249141
18、89.5171.0010249514240.451698.901025041710.2571.7510250514235.251480.50第 7 页 ，共 7 页试编写 SQL 语句，完成以下各项功能（注：必要时一个小题可以用多条语句去实现）1) 根据订单明细表（OrderItems）结构，在该表中插入一条记录，各列数值如下。注意：这里有些列是不能赋值的。2) 将商品表中价格最低的前 20%个商品涨价 25%。3) 检索哪些商品的名称中包含“to”这个字符串而且其单价超过所有商品单价的平均值。4) 从 Condiments 类商品中随机提取一个商品， 计算 2008 年这个商品的销售额在同类
19、商品中的排名名次。5) 统计检索 2008 年度哪些客户的销售额超过 Around the Horn 这个客户销售额的1.5 倍。6) 统计检索哪些客户购买 tofu 这个商品的金额最多，要求查询结果中包含客户名称。7) 统计 2008 年哪些客户购买了 tofu 这个商品但没有购买 longlife tofu 这个商品。8) 创建一个存储过程，从订单表中提取检索其中的一部分记录，例如从订单表的第51 行开始提取后面的 10 行记录。要求输入两个整数start 和limit，检索订单表中从start 行开始的后limit 行记录（提示：可以使用 not in 或排名函数rownumber()）
