C++数据结构与算法上机练习题.pdf

数据结构练习题 单链表的逆置单链表的逆置 题目描述 实现单链表的逆置 输入格式 输入需要逆置的字符串 输出格式 第一行输出逆置前的字符串 第二行输出逆置后的字符串 样例输入 abcdefg 样例输出 abcdefg gfedcba include using namespace std const int N 6 typedef int DataType 类型定义 typedef struct node 单链表 DataType data struct node next LinkedNode LinkList 由数组创建单链表 LinkList CreateList DataType a N LinkedNode ListHead new LinkedNode ListHead data a 0 ListHead next NULL for int i N 1 i 1 i LinkedNode p new LinkedNode p data a i p next ListHead next ListHead next p return ListHead 输出单链表 void PrintList LinkList ListHead if NULL ListHead cout The List is empty endl else LinkedNode p ListHead while p NULL cout data next cout next ListHead pCur else LinkedNode pNext pCur next ReverseList pNext ListHead 递归逆置后继结点 pNext next pCur 将后继结点指向当前结点 pCur next NULL int main int a N 1 2 3 4 5 6 LinkedNode list CreateList a PrintList list LinkedNode pTemp list ReverseList pTemp list PrintList list return 0 中缀表达式转后缀表达式 带括号 将中缀表达式 infix expression 转换为后缀表达式 postfix expression 假设中缀表达式 中的操作数均以单个英文字母表示 且其中只包含左括号 右括号 和双目算术操作符 include include include include using namespace std int main int argc char argv int t cin t while t string str queue q stack s operation stack cin str for unsigned i 0 i A if it is letters push in the queue else if str i s push str i else if str i while s top q push s top dealing the bracket s pop s pop else if str i str i if s empty s push str i else if s top s top s top s top do q push s top s pop while s empty pop to the queue s push str i else s push str i else if str i str i if s empty s push str i else if s top s top do q push s top s pop while s empty s push str i else s push str i while s empty q push s top s pop if not empty push to the queue while q empty cout q front q pop cout it cout endl return 0 Bracket Matching 时间限制 1 秒 内存限制 256 兆 题目描述 检查输入字符串中的括号是否匹配 括号包括 输入格式 第一行是一整数 即测试样例个数 n 以下 n 行 每一行是一个长度不超过 100 个字符的字符串 输出格式 第一行是一整数 即测试样例个数 n 以下 n 行 每一行是一个长度不超过 100 的字符串 样例输入 3 a 2 1 2 2 a b 样例输出 Yes Yes No 思路 遍历字符串 遇到左括号入栈 遇到右括号 判断是否匹配 若不匹配 呵呵 若 匹配 左括号出栈 继续遍历 最后若没有未得到匹配的左括号和右括号 则视为匹配 坑爹的地方 比如你要注意 也是不匹配的 还有你要小心 aaa 这种中间 前面带有空格的字符 串 不清楚测试用例是否有 但是这只是作为字符串处理类型的题目的一个提醒 include include include using namespace std cin 对象不适合用来读入字符串对象 因为它在遇到第一个空格时就会停止录入 故对字符 串处理类型的题目 要小心字符串中间有空格的情况 另一个情况就是对于这种括号匹配的题目 如 应该是不匹配的 所以你想要通过开 6 个变量来记录 括号的个数 从而实现判断匹配与否是不可行的 如下面的代码 int main int i txcase string tocheck cin txcase 这里另一点值得注意的是 在 getline 前面如果需要使用 cin 语句 应该 在 cin 语句下一句加一个 cin ignore cin ignore while txcase int braket left 0 int braket right 0 int brace left 0 int brace right 0 int square bk left 0 int square bk right 0 getline std cin tocheck for i 0 i tocheck length i switch tocheck i case brace left break case brace right break case braket left break case braket right break case square bk left break case square bk right break debug cout for debug endl tocheck debug endl if brace left brace right else cout No endl system pause return 0 include int main stack storerof bk int i txcase string tocheck bool flag flag 用于记录是否出现下面的 for 语句的后两个 if 语句的情况 默认为不出现 cin txcase cin ignore while txcase flag false getline std cin tocheck for i 0 i tocheck length i 遍历字符串 if tocheck i tocheck i tocheck i 遇到左括号就进栈 storerof bk push tocheck i if tocheck i tocheck i tocheck i else if tocheck i else if tocheck i else flag true break elseif tocheck i tocheck i tocheck i break 走完循环之后还得判断输出 if flag else cout No endl debug cout debug endl while storerof bk empty 最后还要注意清空栈 storerof bk pop system pause return 0 叠罗汉 或许有人比较 out 不清楚这种运动的规则 简单来说 就是人叠人 第一个人站在地面 第二个人站在第一个人的肩膀 第三个人站在第二个人的肩膀 依次类推 看过杂技表演 的应该明白的 当然 是人肯定都不希望自己在下面 特别是当女朋友要找的时候 突然发现自己在罗汉 塔最底层 现在 ikuy 就恰好遇到了这个问题 Ikuy 正在玩叠罗汉游戏 突然电话响了 是 GF 的 苦于自己正在罗汉塔某个位置 没法 接电话 已经知道电话会响 X 单位时间 每次都这样 是约定 如果 ikuy 不接电话就会被 罚一顿饭 连续 3 次不接就 88 Ikuy 很郁闷 想知道自己能不能在规定时间内去接到电 话 他必须在规定时间内从罗汉塔中解脱出来 不过这时他不清楚自己的具体位置 只知道整个游戏已经进行了的过程 需要你帮忙了 已经知道过程中每个步骤是这样描述的 R 表示编号为 R 的社员爬上去了 1 表示最顶上的那个社员下来了 其中 R 是不大于 10000 的正整数 保证所有数据合法 即对于第一条命令 保证 R 此时不 在罗汉塔中 一共有 M 条命令 经过 M 条命令后得到现在的罗汉塔 开始计算时间 此时 对于第 i 层的社员 要下来 需要花费的时间是 i 1 单位时间 ikuy 要解放就必须在 他上面的所有社员 他本身都从罗汉塔上下来 哦 忘记了 ikuy 的编号是 N 现在希望你能反馈出 ikuy 是否能接到电话 备注 如果需要花费时间和 X 相等也算接到电话 Input 输入第一行为 T 表示有 T 组测试数据 对于每组测试数据格式如下 第一行为 3 个整数 N M X 意义如题目描述 接下来 M 行每行有一个整数 表示各个步骤 规定 N 不大于 10000 M 不大于 1000 X 不大于 50000 Output 对于每组测试数据 如果可以接到电话 请输出 YES 否则输出 NO 每组输出为一行 Sample Input Copy sample input to clipboard 2 3 8 5 1 1 4 3 1 2 3 1 3 8 3 1 1 4 3 1 2 3 1 Sample Output YES NO 思路 只需开一个数组 模拟整个叠罗汉的过程 一个变量记录最后操作完毕后 叠罗汉 的人数 这样确定起 ikuy 的位置也很方便 只需要 for 循环遍历数组 匹配 ikuy 的位置 剩下的就是累加咯 自己想 include include include using namespace std int main int i txcase ikuy numofcommand GFtime command cin txcase while txcase int Pyramid 1000 模拟叠罗汉的数组 int upnum 0 上去的指令数目 int pos 1 记录 ikuy 的的位置 默认不在栈内 int totaltime 0 cin ikuy numofcommand GFtime for i 0 i command if command 1 有人叠上去了 Pyramid upnum command upnum else upnum for i 0 i upnum i if Pyramid i ikuy pos i if pos 1 默认情况 不在栈内 totaltime 0 else for i pos i upnum i totaltime i if totaltime GFtime cout YES endl else cout NO endl return 0 Rails 题目描述 There is a famous railway station in PopPush City Country there is incredibly hilly The station was built in last century Unfortunately funds were extremely limited that time It was possible to establish only a surface track Moreover it turned out that the station could be only a dead end one see picture and due to lack of available space it could have only one track The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way Assume that the train arriving from the direction A has N 1000 coaches numbered in increasing order 1 2 N The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1 a2 aN Help him and write a program that decides whether it is possible to get the required order of coaches You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B You can also suppose that at any time there can be located as many coaches as necessary in the station But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station 输入格式 The input consists of blocks of lines Each block except the last describes one train and possibly more requirements for its reorganization In the first line of the block there is the integer N described above In each of the next lines of the block there is a permutation of 1 2 N The last line of the block contains just 0 The last block consists of just one line containing 0 输出格式 The output contains the lines corresponding to the lines with permutations in the input A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input Otherwise it contains No In addition there is one empty line after the lines corresponding to one block of the input There is no line in the output corresponding to the last null block of the input 样例输入 5 1 2 3 4 5 5 4 1 2 3 0 6 6 5 4 3 2 1 0 0 样例输出 Yes No Yes 题目大意 搞得这么一大串英文 是要吓死人么 给定 N 只火车 按照 1 到 N 的顺序入栈 给 你出栈顺序 要求出栈顺序是否匹配入栈顺序 输入包含多个块 每个块第一行是列车数 目 接下来是多行出栈序列 匹配输出 Yes 否则输出 No 每个块输出结束后有一个空行 NULL 块后面没有任何输出 思路 还是模拟 先把出栈序列存在表 开个 stack 来模拟入栈的操作 如果两者的头相同 就都 pop 每次 pop 之后还要检查 pop 之后的头是否再次匹配 include include include using namespace std int main list outtrain stack intrain int i numoftrain train while 1 cin numoftrain if numoftrain 0 break while 1 cin train if train 0 cout endl break outtrain push back train 初始化出栈列车顺序 for i 1 i train outtrain push back train for i 1 i numoftrain i intrain push i 若 i 与出栈序列的头匹配 则要 pop 掉 i 但是还要检查 pop 之后两者的头是否会相等 while intrain empty outtrain pop front if intrain empty cout Yes endl else cout No endl while intrain empty 每个测试用例都要用到栈和表 每次用完都要 pop 干净 intrain pop while outtrain empty outtrain pop front system pause return 0 Printer Queue 题目描述 The only printer in the computer science students union is experiencing an extremely heavy workload Sometimes there are a hundred jobs in the printer queue and you may have to wait for hours to get a single page of output Because some jobs are more important than others the Hacker General has invented and implemented a simple priority system for the print job queue Now each job is assigned a priority between 1 and 9 with 9 being the highest priority and 1 being the lowest and the printer operates as follows The first job J in queue is taken from the queue If there is some job in the queue with a higher priority than job J thenmove J to the end of the queue without printing it Otherwise print job J and do not put it back in the queue In this way all those importantmuffin recipes that the Hacker General is printing get printed very quickly Of course those annoying term papers that others are printing may have to wait for quite some time to get printed but that s life Your problem with the new policy is that it has become quite tricky to determine when your print job will actually be completed You decide to write a program to figure this out The program will be given the current queue as a list of priorities as well as the position of your job in the queue and must then calculate how long it will take until your job is printed assuming that no additional jobs will be added to the queue To simplifymatters we assume that printing a job always takes exactly one minute and that adding and removing jobs from the queue is instantaneous 输入格式 One line with a positive integer the number of test cases at most 100 Then for each test case One line with two integers n and m where n is the number of jobs in the queue 1 n 100 and m is the position of your job 0 m n 1 The first position in the queue is number 0 the second is number 1 and so on One linewith n integers in the range 1 to 9 giving the priorities of the jobs in the queue The first integer gives the priority of the first job the second integer the priority of the second job and so on 输出格式 For each test case print one line with a single integer the number of minutes until your job is completely printed assuming that no additional print jobs will arrive 样例输入 3 1 0 5 4 2 1 2 3 4 6 0 1 1 9 1 1 1 样例输出 1 2 5 题目的大意是要打印一堆 job 每个 job 有其对应的优先级 当排在最前面的 job 的优先级 不是最高的时候 不打印 把 job 移动到最后 排在最前面的是最高优先级的时候 打印 多个测试用例 每个用例输入包含 n m 代表 job 个数 和你要打印的 job 在原始队列中的 位置 接下来是一串数字 代表对应位置的 job 的优先级 你需要 figure out 指导你的 job 打印完成一共花了多长时间 每一次打印花费 1 时间 移动不耗时 include include using namespace std int main int n p q i j a 100 b 100 c bool flag 1 cin n while n c 0 cin p q for i 0 i a i b i a i sort a a p j 0 for i p 1 i 0 i while flag if b j a i j else if b j a i c break else c b j 0 flag 0 j if j p j 0 if j p j 0 这里要加一句 flag 1 cout c endl system pause return 0 猴子选大王 题目描述 猴子选大王 有 N 只猴子 从 1 N 进行编号 它们按照编号的顺时针方向 排成一个圆 圈 然后从第一只猴子开始报数 第一只猴子报 1 以后每只猴子报的数字都是它前面猴 子所报数字加 1 如果一只猴子报的数字是 M 则该猴子出列 下一只猴子重新从 1 开始 报数 剩下的猴子继续排成一个圆圈报数 直到全部的猴子都出列为止 最后一个出列的 猴子胜出 输入格式 The first line is an integer t indicating the number of test cases Then there are t lines and each line contains two positive integer N 0 N 100 and M 0 M 100 输出格式 For each test case print out the number of the Monkey King 样例输入 2 5 2 4 3 样例输出 3 1 include using namespace std class Node public Node next int monkey Node int mk Node rear monkey mk next rear void operator Node p monkey p monkey next p next int main int i numofmonkey M txcase j cin txcase while txcase cin numofmonkey M Node old NULL 用于储存要删除的节点 if numofmonkey 1 cout 1 endl else Node rear new Node 1 rear Node current rear 初始化约瑟夫环 for i 2 i next new Node i rear current current next current rear for i 0 i numofmonkey 1 i for j 1 j next current 指向要删除的节点的前一节点 删除操作 old current next current next old next delete old current current next 继续往后移 cout monkey endl system pause return 0 移动小球 Description 你有一些小球 从左到右依次编号为 1 2 3 n 你可以执行两种指令 1 或者 2 其中 1 X Y 表示把小球 X 移动到小球 Y 的左边 2 X Y 表示把小球 X 移动到小球 Y 右边 指令 保证合法 即 X 不等于 Y 例如 初始状态 1 2 3 4 5 6 的小球执行 1 1 4 后 小球 1 被移动 到小球 4 的左边 即 2 3 1 4 5 6 如果再执行 2 3 5 结点 3 将会移到 5 的右边 即 2 1 4 5 3 6 Input 第一行为一个整数 t 0 t 10 表示测试用例个数 每个测试用例的第一行为两个整数 n 1 n 500000 和 m 0 m 100000 n 表示小球的个数 m 为指令条数 以下 m 行每 行为一条指令 Output 为每个测试用例单独输出一行 从左到右输出最后序列 每个数字后面跟一个空格 Sample Input 2 6 2 1 1 4 2 3 5 5 1 2 1 5 Sample Output 2 1 4 5 3 6 2 3 4 5 1 解题思路 一开始是考虑使用双向链表来做 虽然插入和删除的操作都会很方便 但这样会 出现查找的花费的时间太长 要查找 firstball 和 secondball 的位置 事实确实如此 采用 双向链表来做最终超时了 当然也可能是代码出现了死循环的情况 如果你用双向链表 AC 了 可以分享一下你的代码 百度一下 发现很强大的方法 开一个数组记录每个小球的 左右小球的编号 模拟双向链表 这样就实现了随机访问而不需要遍历 思考之后决定使用 数组模拟双向循环链表 之所以采用循环的结构是因为这样的话 就不需要考虑操作首尾部 分小球时候 导致的特殊情况 更加方便 然后声明一个变量来记录每次操作之后首位小球 的编号 这样输出也就有着落了 代码有详细注释 具体可参考代码如下 代码一 include include include using namespace std class ball public int left int right ball array 500001 大数组不能放在 main 内 void moveball int order int first int second ball array 移动操作的函数 if order 1 array array first left right array first right array array first right left array first left array first left array second left array first right second array array second left right first array second left first else array array first left right array first right array array first right left array first left array first left second array first right array second right array array second right left first array second right first int main int i txcase numofball commandnum order first second cin txcase while txcase int head 1 head 用来跟踪表头 默认初始化为 1 cin numofball commandnum 接下来采用数组模拟双向循环链表 循环的话就可以免去在头和尾操作的特殊情 况 array 1 left numofball 初始化表头 array 1 right 2 array numofball left numofball 1 初始化表尾 array numofball right 1 for i 2 i order first second if head first moveball order first second array else if order 1 moveball order first second array else moveball order first second array 所有 order 执行完毕之后输出 for i 0 i numofball 1 i cout head head array head right cout head endl system pause return 0 代码二 include using namespace std int lefta 500100 0 作用域为整个程序 int righta 500100 0 void link int x int y 为了避免超时 新建两个数组代表第 I 个数左边和右边的数 利用相对位子的交换避免整个 数组的重新写入 int main int t int n m int x y int side int i int ball cin t while t cin n m for i 0 i side x y link lefta x righta x a b x a x b a x b x if side 1 link lefta y x link x y b x b y a b y x b y x a x y else link x righta y link y x 同理可得 for ball righta 0 ball n 1 ball righta ball 一个数的右边 输出 在右边 cout ball cout endl return 0 void link int x int y righta x y 第 x 个数的右边变成 y lefta y x 第 y 个数的左边变成 x 双栈排序 题目描述 Tom 最近在研究一个有趣的排序问题 如图所示 通过 2 个栈 S1 和 S2 Tom 希望借助以下 4 种操作实现将输入序列升序排序 操作 a 如果输入序列不为空 将第一个元素压入栈 S1 操作 b 如果栈 S1 不为空 将 S1 栈顶元素弹出至输出序列 操作 c 如果输入序列不为空 将第一个元素压入栈 S2 操作 d 如果栈 S2 不为空 将 S2 栈顶元素弹出至输出序列 如果一个 1 n 的排列 P 可以通过一系列操作使得输出序列为 1 2 n 1 n Tom 就称 P 是一个 可双栈排序排列 例如 1 3 2 4 就是一个 可双栈排序序列 而 2 3 4 1 不是 下图描述了一个将 1 3 2 4 排序的操作序列 当然 这样的操作序列有可能有几个 对于上例 1 3 2 4 是另外一个可行 的操作序列 Tom 希望知道其中字典序最小的操作序列是什么 输入格式 输入有多组 Case 每个 Case 第一行是一个整数 n n 1000 第二行有 n 个用空格隔开的正整数 构成一个 1 n 的排列 输出格式 每组 Case 输出一行 如果输入的排列不是 可双栈排序排列 输出数字 0 否则输出字 典序最小的操作序列 每两个操作之间用空格隔开 行尾没有空格 样例输入 4 1 3 2 4 4 2 3 4 1 样例输出 a b a a b b a b 0 Hit ormiss a 第一个玩家拥有全部的 52 张牌 而其他的玩家暂时没有牌在手上 b 每一个玩家各自报数 若报的数与牌堆顶上的牌数字相同即为 match c 每个玩家各自报数 各自匹配 也即是说 A 报一个数并记住 比较牌堆顶上的牌 接 着是 B 报自己的数 比较自己牌堆顶上的牌 以此下去 d 报数均从 1 开始 若没有牌在手上则不报数 待至有牌在手上时将上次所报之数加一作为 此次的报数 e 若某个玩家 非最后一个玩家 匹配了一次 也就是说报得数跟牌堆上的数字一样时 将 此牌放入下一个玩家的牌堆的最底层 如果是最后一个玩家 则丢弃该张牌 若玩家不匹 配 也就是说报得数跟牌堆上的数字不一样时 将该牌放入自己牌堆的最底层 f 记录由最后一个玩家丢弃了的牌数 到达 52 即结束 当然这结束循环的关键还要找到一 个 最大 的允许循环匹配次数 我试了很多次 至少 1 千之前的我都是 WA 模拟队列的操作 总体不难 输出最后一张牌的时候最后一个数字后面不跟空格 只有数字与数字之间有空格 include include include using namespace std int main int caseNum scanf d for int i 1 i caseNum i queue card 10 10 个玩家 int count 10 10 个玩家各自的计数 int last 10 记录最后一张牌 int players scanf d for int j 0 j 52 j int temp scanf d card 0 push temp 第一个人 for int j 0 j players j count j 0 从 1 开始计数 开始匹配 int times 0 轮数 int discard 0 最后一个人弃掉的牌 bool accomplish false while times 10000 这很纠结不知道多少才是最合适的 for int j 0 j players j if card j empty 暂时为空 continue count j 计数 if count j 14 count j 1 int temp 0 temp card j front 牌堆顶上的一张 card j pop 比较 if temp count j match if j 1 players j 是最后一个玩家 discard if card j empty 弃牌之后为空 last j temp else 不是最后一个玩家 将牌放于下一个玩家的牌堆底层 card j 1 push temp if card j empty 弃牌之后为空 last j temp else 没有匹配成功 放入自己牌堆中的底层 card j push temp times if discard 52 accomplish true break if accomplish true cout Case i for int j 0 j players j cout last j if j players 1 else cout cout endl else cout Case i unwinnable endl return 0 代码二 include include include using namespace std int main int t scanf d int k 1 while t int i int n 多出一个队列 算是偷懒 用来收集被最后一个人丢弃的卡片 queue q 11 int cd scanf d for i 0 i 52 i scanf d q 0 push cd int players 10 for i 0 i n i players i 1 bool finish false int cnt 0 13 52 毕竟总有个结束的时候嘛 其实是情况最差的一个循环 就是第一个人拿着 52 张牌不断的走一个循环 后面的人跟着做空循环 一个循 环都过来了 之后再循环也就没意义了 while cnt 13 52 for i 0 i n i if q i empty finish false if players i q i front q i push q i front else 最后一个人的时候 其实是扔给 11 号 算是扔掉了的 q i 1 push q i front cnt 1 q i pop players i players i 13 1 cnt cout Case k if finish for i 0 i n i 因为在队列空了之后 还做了一次加法 所以在这里调整过来 if players i 1 cout 13 else cout players i 1 else cout unwinnable cout endl return 0 ISBN 限制条件 时间限制 10 秒 内存限制 32 兆 题目描述 Practically every book that has been published during the past thirty years can be uniquely identified by its International Standard Book Number ISBN An example of an ISBN is 963 10 0604 2 An ISBN has 13 characters Exactly three of the 13 characters are hyphens n The first leftmost character of the ISBN is not a hyphen n The next to last character of the ISBN is a hyphen n No two hyphens occupy adjacent positions The last rightmost character is either a decimal digit 0 9 or an upper case X The nine characters which are not in the rightmost position and are not hyphens are decimal digits The rightmost character is known as the check digit It can actually be calculated from the other digits according to the following steps as each step is stated it will be illustrated using the example 963 10 0604 2 1 Assign numbers 10 9 8 as the respective weights to the first second third digit Digit9 6 3 1 0 0 6 0 4 Weight 10 9 8 7 6 5 4 3 2 2 Calculate the we