2022秋数据结构平时实验题目¶
第一次¶
模拟栈¶
Description
用数组实现一个字符串的栈.
栈大小为10.
Input 第一行为操作次数k.
之后每一行为一次操作
操作类型有push 和 pop, push 操作之后带有入栈元素.
Output 从栈顶到栈底访问 k 次操作之后的栈中元素.
注意:输出结果之间用空格隔开.
Sample Input 1
3 push aa push bb pop Sample Output 1
aa
括号匹配¶
Description
输入一串字符串，其中有普通的字符与括号组成（包括‘（’、‘）’、‘[’,']'）,要求验证括号是否匹配，如果匹配则输出0、否则输出1.
Input 字符串长度<=100
Output 验证括号是否匹配，如果匹配则输出0、否则输出1.
Sample Input 1
dfa(sdf)df[dfds(dfd)] Sample Output 1
0
第二次¶
CircularQueue¶
Description
向队列中插入若干个元素（循环队列最大容量为8），访问并移除队列中的所有元素.（当插入元素大于队列最大容量时输出This queue is overflow!）
必须用循环队列实现!
Input 输入：要插入的元素的个数
要插入的每一个元素的值
Output 输出：访问移除的每一个元素的值
Sample Input 1
5 6 2 3 8 7 Sample Output 1
6 2 3 8 7
寻找最近的相同字母位置¶
Description
寻找最近的相同字母位置
Input
输入:第一行输入字母矩阵的大小 m * n.
第二行输入要查找的字母坐标.
之后输入 m * n 个字母.
m < 10, n < 10.
Output 输出: 距离查找字母最近的相同字母坐标.(坐标从(0,0) 开始)
找不到输出-1 -1
Sample Input 1
3 2 1 1 q w a x x a Sample Output 1
2 0
第三次¶
约瑟夫环¶
Description
n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。
Input 输入 n，m
Output 优胜者的编号
Sample Input 1
7 4 Sample Output 1
2
第四次¶
递归求子集合的个数¶
Description
给定n个元素的集合（1,2.....n），写递归程序实现求集合大小（集合中元素个数）为k的子集合的总数
Input n，k
Output 满足条件的子集合个数
Sample Input 1
10 2 Sample Output 1
45
递归排序¶
Description
写递归程序将一个数组从小到大排序
（其他方法不给分）
Input 第一行为数组的元素个数n
第二行为n个数
Output 输出排好序的数组
Sample Input 1
5 2 3 4 1 5 Sample Output 1
1 2 3 4 5
第五次¶
八皇后问题¶
Description
按照国际象棋的规则，皇后可以攻击与之处在同一行或者同一列或同一斜线上的棋子，八皇后问题研究的是如何将八个皇后放置在8*8的棋盘上，并且使皇后彼此之间不能相互攻击。
Input 无
Output 求满足提交的解决方案有多少个
Sample Input 1
无 Sample Output 1
满足条件的个数
递归求解链表最小值¶
Description
给钉一个存放n(0<n<=10000)个整数的链表（链表自己实现），请使用递归的方法求解链表的最小值，其他实现方法不得分。
Input 链表元素个数n
n个数
Output 最小值
Sample Input 1
10 3 4 5 7 8 6 2 1 12 19 Sample Output 1
1
第六次¶
实现二分搜索，在有序数组中有重复元素时，找到所有重复元素。¶
Description
给定一个有序数组，实现二分搜索方法，找到所有和目标相同的元素，以从小到大的顺序返回下标。
Input 第一行为数组的长度n
第二行为n个元素
第三行为要查找的目标元素m
Output 从小到大输出所有匹配的元素在数组中的下标，如果没有匹配的元素则输出Not Found
Sample Input 1
5 1 2 2 3 4 2 Sample Output 1
1 2 Sample Input 2
5 1 2 3 4 5 6 Sample Output 2
Not Found
迷宫问题¶
Description
求解迷宫问题，并打印出一条迷宫问题从入口到出口的路径
Input
给定m*n的矩阵 （迷宫）
矩阵元素，0表示该位置可以到达，1表示无法到达。
起点坐标
终点坐标
Output 输出途径位置的坐标，如果找不到一条路径输出No path found!
Sample Input 1
10 10 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 8 8 Sample Output 1
(1,1) (2,1) (3,1) (4,1) (5,1) (5,2) (5,3) (6,3) (6,4) (6,5) (7,5) (8,5) (8,6) (8,7) (8,8)
第七次¶
利用哈希表求两数之和¶
Description
给定一个整数数组和一个整数目标值， 利用哈希表找该数组中和为目标值的那两个整数，并返回它们的数组下标。（假设仅有一对整数满足和为目标值的条件）
Input 第一行：数组元素个数n
第二行：目标值target
第三行：n个数组元素
Output 和为目标值的两个整数的数组下标
Sample Input 1
4 9 2 7 11 15 Sample Output 1
0 1
第八次¶
最小栈¶
Description
设计最小栈结构，支持push， pop，getMin操作（时间复杂度要求为O(1))。
(提示：可以使用两个栈完成)
Input 第一行为操作次数k.
之后每一行为一次操作
操作类型有push ， pop和getMin, push 操作之后带有入栈元素.
Output 每次getmin操作输出当前状态下栈内的最小值
Sample Input 1
6 push 1 pop push 2 getMin push 0 getMin Sample Output 1
2 0 整数划分 题目描述见本目录下的图片 要求：用递归求解。
Input n m (用空格隔开)
Output 计算n的m划分的个数
Sample Input 1
6 4 Sample Output 1
9
搜索旋转排序数组¶
Description
整数数组nums按升序排列，数组中的值互不相同。
在传递给函数之前，nums在预先未知的某个下标k(0≤k<nums.length)上进行了旋转，使数组变为[nums[k],nums[k+1],..., nums[0],nums[1],..., nums[k-1]]（下标从0开始计数）。例如，[0,1,2,3,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。
给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。
要求：时间复杂度为O(log n)（如，二分搜索方法）
Input 第一行：数组元素个数n (n < 10000)
第二行：数组nums[]
第二行：目标值m
Output 该目标值的在数组中的索引；若不存在，则输出-1
Sample Input 1
7 4 5 6 7 0 1 2 0 Sample Output 1
4