浙江理工大学-938数据结构与数据库技术【2016】考研真题
2023-06-21
999+
132.57KB
4 页
侵权投诉
第1页 ，共 4页
浙江理工大学
2016 年硕士学位研究生招生入学考试试题
考试科目：数据结构与数据库技术 代码：938
（请考生在答题纸上答题，在此试题纸上答题无效）
第一部分：数据结构（本部分共 90 分）
一、程序设计题（按得分最高的 4小题计分，本题得分最多不超过 90 分）
1．已知单链表 lnode 结构如下，其头结点为 head，data 为结点的值域。试编写程序
算法，使用一次循环求出该单链表中 data 域的最大值和次大值。（本题 20 分）
struct lnode {
int data;
struct lnode *next;
}
2．已知二叉树的根结点为 t，其二叉链表结构如下：
struct node {
int data;
struct node *lch, *rch;
}
这里，data 为结点的值域，lch 为结点的左孩子，rch 为结点的右孩子。试编写一个
非递归函数，利用中序遍历算法，判断 data 值为 x的这个结点是否存在兄弟节点。
（本题 25 分）
3. 试编写程序，实现数据的简单选择排序算法，并分析算法的时间复杂度。（本题
20 分）
4. 试编写程序算法，采用单链表作为存储结构（结构如下定义），实现直接插入排
序算法，并进行算法时间复杂度分析。（本题 25 分）
struct node {
int data;
struct node *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，散列地址空间为 0~10，采用线性探查法
解决冲突，计算结点的平均查找长度。（15 分）
②使用二叉排序树存储，即以上述序列构造一个二叉排序树，计算该二叉排序树上
结点的平均查找长度。（10 分）
第二部分：数据库技术（本部分共 60 分）
二、解答题（每小题 10 分，按得分最高的 6小题计分，本题得分最多不
超过 60 分）
数据库 Sales 用来存放某企业销售数据，它有 4张表，Products 表用来存储产品
信息，Customers 表用来存储客户信息，Orders 表用来存储订单信息，OrderItems 表
用来存储订单明细信息，各表结构如下：
1．Products 表结构：
列名 类型 长度 规则 中文说明
ProductID 数值型 8主键 产品编码
ProductName 字符型 30 非空 产品名称
Category 字符型 20 非空 产品类别
QuantityPerUnit 字符型 20 非空 规格型号
UnitPrice 数值型 8, 2 成本单价
标签： #浙江理工大学
摘要：
展开>>
收起<<
第1页，共4页浙江理工大学2016年硕士学位研究生招生入学考试试题考试科目：数据结构与数据库技术代码：938（请考生在答题纸上答题，在此试题纸上答题无效）第一部分：数据结构（本部分共90分）一、程序设计题（按得分最高的4小题计分，本题得分最多不超过90分）1．已知单链表lnode结构如下，其头结点为head，data为结点的值域。试编写程序算法，使用一次循环求出该单链表中data域的最大值和次大值。（本题20分）structlnode{intdata;structlnode*next;}2．已知二叉树的根结点为t，其二叉链表结构如下：structnode{intdata;structnode*...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
