# 2018-NUAA-Data-Structrue-Experiments-design
## 2018 数据结构八次上机实验和课程设计
### 八次上机实验(2018年版):
《数据结构》上机实验题目
(共8次,每次上机4小时)
第一阶段(线性部分)
《数据结构》第1上机题 (线性表练习)
1.编程实现书P19 ADT List 基本操作12个:
(1)用顺序存储结构实现; (2)用链式存储结构实现;
2.设元素值为整型的线性表L,分别采用顺序结构和链式结构存储,编写程序,实现线性表的就地逆置(习题集P18 2.21, 2.22)。
3.输入正整数n、m(m\<n),设有n个人坐成一圈,从第1个人开始循环报数,报到m的人出列,然后再从下一个人开始报数,报到m的人又出列,如此重复,直到所有的人都出列为止。要求用链式结构和顺序结构实现,按出列的先后顺序输出每个人的信息。
4.CSP题目 学生排队
问题描述
体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排,学号小的排在前面,然后进行多次调整。一次调整小明可能让一位同学出队,向前或者向后移动一段距离后再插入队列。
例如,下面给出了一组移动的例子,例子中学生的人数为8人。
0)初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8;
1)第一次调整,命令为"3号同学向后移动2",表示3号同学出队,向后移动2名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8;
2)第二次调整,命令为"8号同学向前移动3",表示8号同学出队,向前移动3名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7;
3)第三次调整,命令为"3号同学向前移动2",表示3号同学出队,向前移动2名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
小明记录了所有调整的过程,请问,最终从前向后所有学生的学号依次是多少?
请特别注意,上述移动过程中所涉及的号码指的是学号,而不是在队伍中的位置。在向后移动时,移动的距离不超过对应同学后面的人数,如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时,移动的距离不超过对应同学前面的人数,如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。
输入格式
输入的第一行包含一个整数n,表示学生的数量,学生的学号由1到n编号。
第二行包含一个整数m,表示调整的次数。
接下来m行,每行两个整数p, q,如果q为正,表示学号为p的同学向后移动q,如果q为负,表示学号为p的同学向前移动-q。
输出格式
输出一行,包含n个整数,相邻两个整数之间由一个空格分隔,表示最终从前向后所有学生的学号。
样例输入
8
3
3 2
8 -3
3 -2
样例输出
1 2 4 3 5 8 6 7
问题分析:这个问题可以通过顺序结构或(双向或单向)链表实现,但对于移动元素较多的情况,应采用哪种存储结构更优呢?
选做题:习题集 1.19 1.20 2.19
《数据结构》第2上机题 (线性表练习)
1、设元素值为整型的线性表L,分别采用顺序结构和链式结构存储,编写程序,用插入排序算法实现线性表的表排序。
2.设元素值为整型的线性表A,、B,分别采用顺序结构和链式结构存储,编写程序,实现下列功能:假设以递增有序排列的线性表A和B 分别表示两个集合,现要求在A的空间上构成一个新线性表C,其元素为A和B元素的交集,且表C中的元素也是依值递增有序排列。
3.CSP题目
**问题描述**** :**先输入一个十进制整数n,再输入n个正整数,求它们相邻数之差可知是否为上升或下降,由上升转下降或由下降转上升为折点,求折点数。
**问题分析**** :**如果一个点的值比左右两个都大或都小,则为折点。
样例输入:
5
1 3 5 2 1
For(int i=1;i\<n-1;i++)
{
If((a[i-1]\<a[i]&&a[i]\>a[i+1])||(a[i-1]\>a[i]&&a[i]\<a[i+1]))
A++;
}
样例输出
1
样例输入:
6
3 5 1 7 8 4
样例输出
3
4.CSP题目
**问题描述**** :**首先输入正整数n,接着输入n个正整数,如果其中存在一个数,比该数大的个数等于比该数小的个数,则输出该数,如果不存在则输出-1。
**问题分析**** :**这个问题可以用排序来实现。
样例输入:
6
9 7 257 8
样例输出
7
样例输入:
5
9 5 257
样例输出
-1
选做题:习题集 2.24 2.29 2.30
《数据结构》 第3次上机题(线性表复习,栈与队列练习)
1.编程实现书P45 ADT Stack 基本操作9个,用顺序存储结构实现;
2.编程实现书P59 ADT Queue 基本操作9个,用链式存储结构实现;
3、 利用栈操作实现八皇后问题求解。
4.、CSP题目
问题描述
在某图形操作系统中,有 N 个窗口,每个窗口都是一个两边与坐标轴分别平行的矩形区域。窗口的边界上的点也属于该窗口。窗口之间有层次的区别,在多于一个窗口重叠的区域里,只会显示位于顶层的窗口里的内容。
当你点击屏幕上一个点的时候,你就选择了处于被点击位置的最顶层窗口,并且这个窗口就会被移到所有窗口的最顶层,而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口,则系统会忽略你这次点击。
现在我们希望你写一个程序模拟点击窗口的过程。
输入格式
输入的第一行有两个正整数,即 N 和 M。(1 ≤ N ≤ 10,1 ≤ M ≤ 10)
接下来 N 行按照从最下层到最顶层的顺序给出 N 个窗口的位置。 每行包含四个非负整数 x1, y1, x2, y2,表示该窗口的一对顶点坐标分别为 (x1, y1) 和 (x2, y2)。保证 x1 \< x2, y1 \< y2。
接下来 M 行每行包含两个非负整数 x, y,表示一次鼠标点击的坐标。
题目中涉及到的所有点和矩形的顶点的 x, y 坐标分别不超过 2559 和 1439。
**问题分析**** :**这个问题可以用链式线性表来实现。
输出格式:输出包括 M 行,每一行表示一次鼠标点击的结果。如果该次鼠标点击选择了一个窗口,则输出这个窗口的编号(窗口按照输入中的顺序从 1 编号到 N);如果没有,则输出"IGNORED"(不含双引号)。
样例输入
3 4
0 0 4 4
1 1 5 5
2 2 6 6
1 1
0 0
4 4
0 5
样例输出
2
1
1
IGNORED
样例说明
第一次点击的位置同时属于第 1 和第 2 个窗口,但是由于第 2 个窗口在上面,它被选择并且被置于顶层。
第二次点击的位置只属于第 1 个窗口,因此该次点击选择了此窗口并将其置于顶层。现在的三个窗口的层次关系与初始状态恰好相反了。
第三次点击的位置同时属于三个窗口的范围,但是由于现在第 1 个窗口处于顶层,它被选择。
最后点击的 (0, 5) 不属于任何窗口。
选做题:习题集 2.32 2.37 2.38
《数据结构》 第4次上机题(线性结构练习)
1.输入稀疏矩阵,建立稀疏矩阵三元组顺序结构,实现转置(1、2);
2. CSP题目
问题描述:首先输入正整数n(n\<10000),接着输入n个正整数(最大值为10000),对于这n个数,统计输出其中的相邻数对(差值为1的数对),相同数据只被统计一次。
**问题分析**:这个看似是一个n个数与n个数进行比较(O(n^2))的问题,能
没有合适的资源?快使用搜索试试~ 我知道了~
NUAA 2018 数据结构八次上机实验和课程设计.zip
共619个文件
cpp:145个
exe:138个
txt:97个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 7 浏览量
2024-02-24
09:36:46
上传
评论
收藏 58.31MB ZIP 举报
温馨提示
NUAA 2018 数据结构八次上机实验和课程设计
资源推荐
资源详情
资源评论
收起资源包目录
NUAA 2018 数据结构八次上机实验和课程设计.zip (619个子文件)
未命名3.cpp 15KB
shop.cpp 13KB
6.cpp 12KB
BTree.cpp 12KB
1.cpp 11KB
Store.cpp 11KB
算术表达式求值.cpp 10KB
数据结构6-1.cpp 10KB
8.cpp 10KB
数据结构5-1.cpp 9KB
Huffman.cpp 8KB
6.cpp 8KB
字典_new.cpp 8KB
sortCmp.cpp 7KB
字典.cpp 7KB
jsonEncode.cpp 7KB
5.cpp 7KB
3.cpp 6KB
数据结构5-2.cpp 6KB
迷宫.cpp 6KB
数据结构1-1_链式.cpp 5KB
graph.cpp 5KB
4.cpp 5KB
4.cpp 5KB
数据结构6-649.cpp 5KB
2.cpp 5KB
数据结构5-2_old.cpp 5KB
publicKeyBox.cpp 5KB
shop.cpp 5KB
数据结构8-2-3-4.cpp 5KB
5.cpp 4KB
数据结构7-1.cpp 4KB
数据结构1-1_顺序.cpp 4KB
数据结构8-1.cpp 4KB
Test.cpp 4KB
main.cpp 4KB
简洁版.cpp 4KB
csp.cpp 4KB
3.cpp 3KB
数据结构6-662.cpp 3KB
数据结构6-3.cpp 3KB
Maze.cpp 3KB
数据结构5-3.cpp 3KB
数据结构6-660.cpp 3KB
main.cpp 3KB
数据结构5-645.cpp 3KB
数据结构-230.cpp 3KB
数据结构6-2.cpp 3KB
第二个csp.cpp 3KB
魔法优惠券.cpp 2KB
数据结构6-4.cpp 2KB
数据结构5-4.cpp 2KB
main.cpp 2KB
数据结构5-642.cpp 2KB
Message.cpp 2KB
csp.cpp 2KB
数据结构7-2.cpp 2KB
数据结构3-1.cpp 2KB
链表插入.cpp 2KB
数据结构1-2_链式.cpp 2KB
未命名3.cpp 2KB
数据结构2-2_链式.cpp 2KB
未命名1.cpp 2KB
数据结构2-229.cpp 2KB
数据结构3-2.cpp 2KB
数据结构2-224.cpp 2KB
朋友圈.cpp 2KB
数据结构4-3.cpp 2KB
csp.cpp 2KB
2.cpp 2KB
第一题.cpp 2KB
数据结构1-4.cpp 2KB
main.cpp 1KB
main.cpp 1KB
8.cpp 1KB
数据结构1-3.cpp 1KB
数据结构8-1032.cpp 1KB
数据结构3-238.cpp 1KB
数据结构8-5.cpp 1KB
数据结构7-3.cpp 1KB
main.cpp 1KB
main.cpp 1KB
Stack.cpp 1KB
未命名4.cpp 1KB
归并.cpp 1KB
数据结构3-4.cpp 1KB
数据结构2-1_链式.cpp 1KB
数据结构1-2_顺序.cpp 1KB
数据结构4-1-2.cpp 1KB
main.cpp 1KB
数据结构2-2_顺序.cpp 1KB
未命名12.cpp 1KB
随机数生成.cpp 1KB
main.cpp 1KB
main.cpp 1KB
main.cpp 1KB
main.cpp 1KB
数据结构1-219.cpp 1KB
数据结构3-237.cpp 1009B
数据结构4-1-1.cpp 965B
共 619 条
- 1
- 2
- 3
- 4
- 5
- 6
- 7
资源评论
LeapMay
- 粉丝: 3w+
- 资源: 2305
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功