《938数据结构与数据库技术-浙江理工大学》由会员分享，可在线阅读，更多相关《938数据结构与数据库技术-浙江理工大学（8页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 7 页浙江理工大学浙江理工大学二二 OO 八年硕士学位研究生招生入学考试试题八年硕士学位研究生招生入学考试试题考试科目：考试科目：数据数据结结构与数据构与数据库库技技术术 代码：代码：938（* 请考生在答题纸上答题，在此试题纸上答题无效）请考生在答题纸上答题，在此试题纸上答题无效）第一部分、数据第一部分、数据结结构构(共共 90 分分)一、选择填空题（每空格一、选择填空题（每空格 3 分，本题共分，本题共 60 分）分）1已知已知单链单链表表结结点的存点的存储结储结构如下：构如下：struct node int data; struct node *next; ;这这里，里，
2、单链单链表的表的头头指指针为针为 head, 数据域数据域为为 data，指，指针针域域为为 next。 。试试在下列在下列 AJ 中中选择选择一个正确答案，填入相一个正确答案，填入相应应的空格的空格处处，分，分别实现别实现下列四小下列四小题题的算法功能，注意各个的算法功能，注意各个小小题题之之间间没有没有联联系。系。1）将）将单链单链表中表中值值相同的多余相同的多余结结点点删删除。除。void test1(struct node *head) struct node *p,*q,*r;p=head;while (p!=NULL) r=p;(1) while (q!=NULL) if (q-d
3、ata=p-data) (2) else r=q;q=q-next; (3) 第 2 页 共 7 页2）将）将值为值为 y 的的结结点插入到点插入到值为值为 x 的的结结点之后，如果点之后，如果值为值为 x 的的结结点不存在，点不存在，则则将其插入将其插入到到单链单链表的表尾。表的表尾。void test2(struct node *head,int x,int y) struct node *p,*q,*r;r=(struct node *)malloc(sizeof(struct node);r-data=y; int sgn=0;p=head;while (p!=NULL)(4) p=p
4、-next; if (sgn=1) (5) else (6) q-next=r; 3）假）假设设在上述在上述单链单链表表结结点的存点的存储结储结构中增加另一个指构中增加另一个指针针域域 prior，将，将该单链该单链表改造成表改造成双向循双向循环链环链表表(假假设该单链设该单链表中至少有一个表中至少有一个结结点点)。 。void test3(struct node *head) struct node *p,*q;p=head;while (p!=NULL) q=p-next;if (q!=NULL) (7) else (8) head-prior=p;break; p=p-next; 第 3
5、 页 共 7 页4）若采用）若采用单链单链表表结结构去存构去存储储一个堆一个堆栈栈，分，分别实现别实现在堆在堆栈栈中入中入栈栈和出和出栈栈一个元素的算一个元素的算法。法。 void test4(struct node *head,int x) struct node *p;p=(struct node *)malloc(sizeof(struct node);p-data=x;p-next=head;(9) int test5(struct node *head) struct node *p;if (head!=NULL) p=head;(10) x=p-data;return(x); el
6、se exit(1); 本题选项：本题选项：(A)head=head-next;(A)head=head-next; (B)head=p;(B)head=p; (C)q=p;(C)q=p; (D)q-prior=p;(D)q-prior=p;(E)q=p-next;(E)q=p-next; (F)p-next=head;(F)p-next=head; (G)p=p-next;(G)p=p-next; (H)r-next=p;(H)r-next=p; (I)r-next=q-next;(I)r-next=q-next; (J)r-next=NULL;(J)r-next=NULL;2已知二叉已知二
7、叉树结树结点的点的链链表存表存储结储结构如下：构如下：struct node char data;struct node *lch,*rch; ;这这里，里，树结树结点的数据域点的数据域为为 data，左孩子指，左孩子指针针域域为为 lch，右孩子指，右孩子指针针域域为为 rch，根，根结结点所在点所在链结链结点的指点的指针针由由 BT 给给出。出。试试在下列在下列 AJ 中中选择选择一个正确答案，填入相一个正确答案，填入相应应的空的空格格处处，分，分别实现别实现下列两个小下列两个小题题的算法功能，注意各个小的算法功能，注意各个小题题之之间间没有没有联联系。系。第 4 页 共 7 页1）利用中
8、序遍）利用中序遍历历算法，算法，查查找二叉找二叉树树 BT 中中值为值为 x 的的这这个个结结点的双点的双亲亲、左孩子及右孩子。、左孩子及右孩子。void test6(struct node *BT,char x) struct node *p,*q,*s100;struct node *x1,*x2,*x3;int top=0;x1=x2=x3=NULL;p=BT;while (top!=0)|(p!=NULL) if (p!=NULL) while(p!=NULL) top+;stop=p;p= (11) else p=stop;(12) if (p-data=x) (13) =p-lch
9、; (14) =p-rch; q=p;p=p-rch; if (p!=NULL) if(x1!=NULL) printf(“结点结点 x 的双亲是的双亲是:%cn“,x1-data);else printf(“结点结点 x 是树根是树根n“);if(x2!=NULL) printf(“结点结点 x 的左孩子是的左孩子是:%cn“,x2-data);else printf(“结点结点 x 无左孩子无左孩子n“);if(x3!=NULL) printf(“结点结点 x 的右孩子是的右孩子是%cn“,x3-data);else printf(“结点结点 x 无右孩子无右孩子n“);2）假）假设设上述
10、二叉上述二叉树树 BT 为为一个二叉排序一个二叉排序树树， ，实现实现在在该该二叉排序二叉排序树树中插入一个中插入一个结结点点 s 的的第 5 页 共 7 页算法。算法。 void test7(struct node *BT,struct node *s) struct node *p,*q;if (BT=NULL) BT=s;else (16) while (p!=NULL) q=p;if (s-datadata) (17) else (18) if(s-datadata) (19) else (20) 本题选项：本题选项：(A)x1(A)x1 (B)x2(B)x2 (C)x3(C)x3 (
11、D)p=p-lch;(D)p=p-lch; (E)p=p-rch;(E)p=p-rch; (F)p-lch;(F)p-lch; (G)p=BT;(G)p=BT; (H)q-lch=s;(H)q-lch=s; (I)q-rch=s;(I)q-rch=s; (J)top-;(J)top-;三、算法程序设计题（每小题三、算法程序设计题（每小题 15 分，本题共分，本题共 30 分）分）1 设设哈希函数哈希函数为为 HT，解决冲突的方法，解决冲突的方法为为外外链链地址法，哈希函数采用除留余数法地址法，哈希函数采用除留余数法(k%p， ，k 为为待待删删除的关除的关键键字，字，p 为为小于基本哈希表容量
12、小于基本哈希表容量 m 的的质质数数)。若哈希表中某个。若哈希表中某个位置上的位置上的 key 域域值为值为零，零，则则表示表示该该位置未被占用。位置未被占用。试编试编写程序，写程序，实现实现从用哈希表中从用哈希表中删删除关除关键键字字 k 的算法（注意需要判断关的算法（注意需要判断关键键字是否存在）。字是否存在）。define m 100; struct node int key;struct node *next;HTm;void test1(struct node HT,int k,int p)2 试编试编写程序，写程序，实现实现用用单链单链表表示的数据表表示的数据简单选择简单选择排序，
13、并分析算法的排序，并分析算法的时间时间复复杂杂度。度。第 6 页 共 7 页这这里里结结点的数据域点的数据域为为 data，指，指针针域域为为 next， ，单链单链表的表的头结头结点点为为 head。 。struct node int data;struct node *next; ;void test2(struct node *head)第二部分、数据第二部分、数据库库技技术术(共共 60 分分)解答题（本题共解答题（本题共 8 小题，可以选择小题，可以选择 6 小题解答，每小题小题解答，每小题 10 分，按得分最高的分，按得分最高的 6 小题小题计分。本题共计分。本题共 60 分）分）
14、数据数据库库 STU 用来存放某用来存放某专业专业学生的考学生的考试试成成绩绩，它有三，它有三张张表表,表表 students 用来存放学生的用来存放学生的 基本信息；表基本信息；表 subjects 用来存放用来存放课课程的基本信息及程的基本信息及该课该课程的平均考程的平均考试试成成绩绩，其中平均成，其中平均成绩绩是是 未知的，需要根据其它表未知的，需要根据其它表汇总汇总得到；表得到；表 scores 用来存放每个学生各用来存放每个学生各门课门课程的考程的考试试成成绩绩。 。这这三三张张 表的表的结结构分构分别别如下：如下：表表 students 的结构：的结构：列名列名类类型型长长度度规则
15、规则列名的中文含列名的中文含义义stu_id字符型字符型8主键、索引主键、索引学号学号name字符型字符型10非空非空姓名姓名sex字符型字符型2非空，男或女，默认值为非空，男或女，默认值为“男男”性别性别class字符型字符型2自动计算，自动计算，(取学号的取学号的 5-6 位为班级代码位为班级代码)班级号班级号表表 students 记录举例：记录举例：stu_idnamesexclass01540101陈文忠陈文忠男男0101540102金志明金志明男男0101540201韩国英韩国英女女0201540201汤江民汤江民男男02表表 subjects 的结构：的结构：列名列名类类型型长长度度规则规则列名的中文含列名的中文含
