数据结构上机考试题目

操作题：

1、 使用jsp完成一个java web项目，实现用户登录功能，三个页面

登录页面login.jsp,登录逻辑处理页面loginSubmit.jsp，欢迎页面welcome.jsp。

用户在登录页面输入用户名和密码，如果用户名为”admin”，密码为”123”，则登录成功跳转到欢迎页面，如果失败，停留在登录页面。（无须连接数据库）

2、 使用jsp+servlet完成一个java web项目，实现用户登录功能，两个页面，一个servlet。

登录页面login.jsp,欢迎页面welcome.jsp,登录逻辑loginservlet。用户在登录页面输入用户名和密码，如果用户名为”admin”，密码为”123”，则登录成功跳转到欢迎页面，如果失败，停留在登录页面。

3、 使用jsp完成一个java web项目，实现用户登录功能，三个页面

登录页面login.jsp,登录逻辑处理页面loginSubmit.jsp，欢迎页面welcome.jsp。

用户在登录页面输入用户名和密码，如果数据库中存在，则登录成功跳转到欢迎页面，如果失败，停留在登录页面。（须连接数据库，sqlserver和access均可） 4、 使用jsp+servl

题目

--1、查找员工的编号、姓名、部门和出生日期，如果出生日期为空值， --显示日期不详,并按部门排序输出,日期格式为yyyy-mm-dd。

--2、查找与喻自强在同一个单位的员工姓名、性别、部门和职称

--3、按部门进行汇总，统计每个部门的总工资

--4、查找商品名称为14寸显示器商品的销售情况， --显示该商品的编号、销售数量、单价和金额

--5、在销售明细表中按产品编号进行汇总，统计每种产品的销售数量和金额

--6、按客户编号统计每个客户1996年的订单总金额

--7、查找有销售记录的客户编号、名称和订单总额

--8、查找在1997年中有销售记录的客户编号、名称和订单总额

--9、查找一次销售最大的销售记录

--10、查找至少有3次销售的业务员名单和销售日期

--11、用存在量词查找没有订货记录的客户名称

--12、使用左外连接查找每个客户的客户编号、名称、订货日期、订单金额 --订货日期不要显示时间，日期格式为yyyy-mm-dd --按客户编号排序，同一客户再按订单降序排序输出

--13、查找16M DRAM的销售情况，要求显示相应的销售员的姓名、 --性别，销售日期、销售数量和金额，其中性别用男、女表示

题目

--1、查找员工的编号、姓名、部门和出生日期，如果出生日期为空值， --显示日期不详,并按部门排序输出,日期格式为yyyy-mm-dd。

--2、查找与喻自强在同一个单位的员工姓名、性别、部门和职称

--3、按部门进行汇总，统计每个部门的总工资

--4、查找商品名称为14寸显示器商品的销售情况， --显示该商品的编号、销售数量、单价和金额

--5、在销售明细表中按产品编号进行汇总，统计每种产品的销售数量和金额

--6、按客户编号统计每个客户1996年的订单总金额

--7、查找有销售记录的客户编号、名称和订单总额

--8、查找在1997年中有销售记录的客户编号、名称和订单总额

--9、查找一次销售最大的销售记录

--10、查找至少有3次销售的业务员名单和销售日期

--11、用存在量词查找没有订货记录的客户名称

--12、使用左外连接查找每个客户的客户编号、名称、订货日期、订单金额 --订货日期不要显示时间，日期格式为yyyy-mm-dd --按客户编号排序，同一客户再按订单降序排序输出

--13、查找16M DRAM的销售情况，要求显示相应的销售员的姓名、 --性别，销售日期、销售数量和金额，其中性别用男、女表示

题目

--1、查找员工的编号、姓名、部门和出生日期，如果出生日期为空值， --显示日期不详,并按部门排序输出,日期格式为yyyy-mm-dd。

--2、查找与喻自强在同一个单位的员工姓名、性别、部门和职称

--3、按部门进行汇总，统计每个部门的总工资

--4、查找商品名称为14寸显示器商品的销售情况， --显示该商品的编号、销售数量、单价和金额

--5、在销售明细表中按产品编号进行汇总，统计每种产品的销售数量和金额

--6、按客户编号统计每个客户1996年的订单总金额

--7、查找有销售记录的客户编号、名称和订单总额

--8、查找在1997年中有销售记录的客户编号、名称和订单总额

--9、查找一次销售最大的销售记录

--10、查找至少有3次销售的业务员名单和销售日期

--11、用存在量词查找没有订货记录的客户名称

--12、使用左外连接查找每个客户的客户编号、名称、订货日期、订单金额 --订货日期不要显示时间，日期格式为yyyy-mm-dd --按客户编号排序，同一客户再按订单降序排序输出

--13、查找16M DRAM的销售情况，要求显示相应的销售员的姓名、 --性别，销售日期、销售数量和金额，其中性别用男、女表示

题目

--1、查找员工的编号、姓名、部门和出生日期，如果出生日期为空值， --显示日期不详,并按部门排序输出,日期格式为yyyy-mm-dd。

--2、查找与喻自强在同一个单位的员工姓名、性别、部门和职称

--3、按部门进行汇总，统计每个部门的总工资

--4、查找商品名称为14寸显示器商品的销售情况， --显示该商品的编号、销售数量、单价和金额

--5、在销售明细表中按产品编号进行汇总，统计每种产品的销售数量和金额

--6、按客户编号统计每个客户1996年的订单总金额

--7、查找有销售记录的客户编号、名称和订单总额

--8、查找在1997年中有销售记录的客户编号、名称和订单总额

--9、查找一次销售最大的销售记录

--10、查找至少有3次销售的业务员名单和销售日期

--11、用存在量词查找没有订货记录的客户名称

--12、使用左外连接查找每个客户的客户编号、名称、订货日期、订单金额 --订货日期不要显示时间，日期格式为yyyy-mm-dd --按客户编号排序，同一客户再按订单降序排序输出

--13、查找16M DRAM的销售情况，要求显示相应的销售员的姓名、 --性别，销售日期、销售数量和金额，其中性别用男、女表示

《数据结构》上机实验题目 （共8次，每次上机4小时）

第一阶段（线性部分）

《数据结构》第1上机题 （线性表练习） 1．编程实现书P19 ADT List 基本操作12个：

（1） 用顺序存储结构实现； （2）用链式存储结构实现； 2．编程实现顺序表和单链表的就地逆置（习题集P18 2.21 2.22）。

《数据结构》第2上机题 （线性表练习）

1．分别用顺序结构和单链表结构编程实现下列功能：假设以两个元素依值递增有序排列的线性表A和B 分别表示两个集合，现要求在A的空间上构成一个新线性表C，其元素为A和B元素的交集，且表C中的元素也是依值递增有序排列（习题集P18 2.25 2.26）；

2．设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起作用前，频度域freq的值均初始化为零，而当对链表进行一次LOCATE(L,x)的操作之后，被访问的结点（即元素值等于x的节点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编程实现之（习题集P19 2.38）。

《数据结构》 第3

《数据结构》上机实验题目 （共8次，每次上机4小时）

第一阶段（线性部分）

《数据结构》第1上机题 （线性表练习） 1．编程实现书P19 ADT List 基本操作12个：

（1） 用顺序存储结构实现； （2）用链式存储结构实现； 2．编程实现顺序表和单链表的就地逆置（习题集P18 2.21 2.22）。

《数据结构》第2上机题 （线性表练习）

1．分别用顺序结构和单链表结构编程实现下列功能：假设以两个元素依值递增有序排列的线性表A和B 分别表示两个集合，现要求在A的空间上构成一个新线性表C，其元素为A和B元素的交集，且表C中的元素也是依值递增有序排列（习题集P18 2.25 2.26）；

2．设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起作用前，频度域freq的值均初始化为零，而当对链表进行一次LOCATE(L,x)的操作之后，被访问的结点（即元素值等于x的节点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编程实现之（习题集P19 2.38）。

《数据结构》 第3

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。

一、单项选择题（每小题1.5分，共计30分）

1. 数据结构是指 。 A. 一种数据类型 B. 数据的存储结构

C. 一组性质相同的数据元素的集合

D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为 。

void fun(int n) { }

int i=1; while (i<=n)

i++;

A. O(n) B. O(n)

C. O(nlog2n) D. O(log2n)

3. 在一个长度为n的有序顺序表中删除元素值为x的元素时，在查找元素x时采用二分查找，此时的时间复杂度为 。

A. O(n) C. O(n2)

B. O(nlog2n) D. O(n)

4. 在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为 。

A. O(n)

B. O(n)

C. O(nlog2n) D. O(n2) 5. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是 。

A.top++;s

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。

一、单项选择题（每小题1.5分，20小题，共计30分）

1. 以下数据结构中 属非线性结构。 A.栈 B.串 2. 以下算法的时间复杂度为 。

void func(int n) { int i=0,s=0; while (s<=n) { i++; s=s+i; } }

C.队列 D.平衡二叉树

A. O(n)

B. O(n) D. O(log2n)

C. O(nlog2n)

3. 在一个双链表中，删除p所指节点（非首、尾节点）的操作是 。 A.p->prior->next=p->next;p->next->prior=p->prior; B.p->prior=p->prior->prior;p->prior->prior=p; C.p->next->prior=p;p->next=p->next->next;

D.p->next=p->prior->prior;p->prior=p->prior->prior;

4. 设n个元素进栈序列是1、2、3、…、n，其输出序列是p1、p2、…、pn，若p1=3，则p2的值为 。

A.一定是2

1． 已知长度为n的线性表L采用顺序存储结构，编写一个时间复杂度为O(n)，空间复杂度

为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

2． 用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中数据都是由小

到大顺序排列的，且这(m+n)个数据中没有相重的。设计一个算法将些两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中。

3． 已知线性表{a0,a1,……,an-1}按顺序存储，且每个元素都是不相等的整数。设计把所有

的奇数移到所有的偶数前边的算法（要求时间最少，辅助空间最少）。 4． 输入一组整型元素序列，建立单链表。

5． 写出在带头结点的单向链表l中删除第i个结点的算法。

6． 编写算法,将带头结点的单链表拆分成一个奇数链表和一个偶数链表。

7． 设C={a1,b1,a2,b2,……,an,bn}为一线性表，采用带头结点的Hc单链表存放，编写一个

就地算法，将其拆分成两个线性表，使得：A={a1,a2,…..,an} C={b1,b2,….,bn} 8． 编写出判断带头结点的双向循环链表L是否对称相等的算法。 9． 设计一算法，将一带头结点的数据域依次为a1,a2,…,an(n>=3)的单