数据结构上机实践课程(2018年秋)题解

jxtxzzw edited 1 年,4 月前

如果有其他题目需要题解,请在评论区留言。

检索表

编号 名称 难度 来源 出题人 题解 备注
0001 A+B Problem Naive 题库 题库
0002 A+B Problem Templated Naive 题库 题库 模板题
0003 数据结构开课啦 Naive 新题 jxtxzzw 查看讨论区 填空题
1001 线性表插入删除操作 Naive 新题 10165102128
1002 线性表的比较 Easy 新题 10165102128
1003 线性表插入删除操作 Easy 新题 Robin
1004 环形双向链表的删除操作 Medium 新题 10165102128
1005 线性表去重 Easy 新题 Robin
1006 线性表顺序查找 Naive 新题 Robin
1007 线性表二分查找 Easy 新题 Robin
1008 经典的猜数游戏 Medium 题库 题库 jxtxzzw的EOJ博客:EOJ-3342-交互题初体验 经典的二分查找
1009 环形队列 Easy 新题 Robin
1010 医疗调度系统 Hard 新题 jxtxzzw 本博客文末附题解
1011 循环打印 Medium 新题 10165102128
1012 查词典 Medium 新题 Robin
1013 欣赏书法 Hard 新题 Robin Robin的EOJ博客:数据结构 1013 欣赏书法题解
1014 座位分配 Medium 新题 10165102128
1015 银行排队夹塞 Hard 新题 10165102128 本博客文末附题解
1016 玩具谜题 Medium 题库 题库
1017 题库整理 Medium 新题 Robin
1018 铁路调度 Hard 新题 jxtxzzw
1019 可旋栈 Medium 题库 题库
1020 波兰表达式 Hard 题库 题库
1021 一元多项式乘法 Super 题库 题库
1022 表达式 Super 题库 题库
1023 迷宫 Hard 新题 jxtxzzw
1024 皇后问题 Medium 题库 题库
1025 皇后问题(SPJ) Medium 新题 jxtxzzw
1026 百万皇后 Super 新题 jxtxzzw 跳转到jxtxzzw个人博客 局部搜索,随机算法
1027 游程长度编码 Easy 题库 题库
1028 方言翻译 Hard 新题 jxtxzzw
1029 统计字符串个数 Naive 题库 题库
1030 字串排序 Naive 题库 题库
1031 删除子串 Naive 题库 题库
1032 构造字典序最小字符串 Naive 题库 题库
1033 字符串的交织 Naive 题库 题库
1034 字符串替换 Medium 题库 题库
1035 字符串消除 Easy 题库 题库
1036 反转字符串 Medium 题库 题库
1037 最长连续公共子序列 Medium 题库 题库
1038 最长回文子串 Easy 题库 题库
1039 字符串模式匹配简单匹配 Naive 新题 Robin
1040 字符串模式匹配KMP算法 Hard 新题 Robin
1041 字符串模式匹配BM算法 Medium 新题 Robin
1042 GPS数据处理 Hard 新题 jxtxzzw 本博客文末附题解
1043 网址的替换 Hard 新题 jxtxzzw 本博客文末附题解
1044 密码碰撞 Medium 题库 题库 博客入口
1045 稀疏矩阵三元组转化 Naive 题库 题库
1046 三元组稀疏矩阵相加 Easy 题库 题库
1047 冒泡排序 Easy 新题 10165102128
1048 插入排序 Naive 新题 Robin
1049 选择排序 Naive 新题 Robin
1050 选择排序(构造) Super 新题 jxtxzzw
1051 快速排序 Easy 新题 Robin
1052 快速排序的优化 Medium 新题 Robin
1053 统计工龄 Naive 新题 jxtxzzw
1054 排名汇总 Medium 新题 10165102128
1055 成绩排序 Easy 新题 Robin
1056 恢复古诗 Hard 新题 jxtxzzw 恢复古诗
1057 数组排序 Naive 题库 题库
1058 二维数组排序 Easy 题库 题库
1059 鞍点 Naive 题库 题库
1060 树的双亲存储法 Medium 题库 题库
1061 树的层号表示法 Easy 新题 Robin
1062 还原二叉树 Easy 新题 jxtxzzw
1063 目录树 Super 新题 jxtxzzw 随课程进度逐步开放
1064 最小权值路径 Medium 新题 Robin
1065 二叉树路径和 Super 新题 10165102128 随课程进度逐步开放
1066 下落的小球 Medium 新题 10165102128 随课程进度逐步开放
1067 平衡二叉树 Medium 新题 Robin 随课程进度逐步开放
1068 二叉搜索树 Medium 新题 jxtxzzw 随课程进度逐步开放
1069 圆上相交弦 Super 题库 题库 进入jxtxzzw个人博客阅读 红黑树
1070 最优二叉搜索树 Easy 题库 题库 随课程进度逐步开放
1071 寻找EMB富豪 Hard 新题 jxtxzzw 随课程进度逐步开放 堆排序,在线处理
1072 树种统计 Easy 新题 jxtxzzw
1073 Windows消息队列 Medium 新题 jxtxzzw
1074 Huffman树的最小外部加权值 Medium 题库 题库
1075 构造Huffman树 Super 新题 jxtxzzw 随课程进度逐步开放
1076 Huffman解密 Medium 新题 Robin 随课程进度逐步开放
1077 朋友圈 Medium 新题 jxtxzzw 随课程进度逐步开放
1078 Virtual Friends Easy 题库 题库 随课程进度逐步开放
1079 小强的烦恼 Medium 题库 题库 随课程进度逐步开放
1080 食物链 Medium 题库 题库 随课程进度逐步开放
1081 华师大卫星照片 Easy 题库 题库
1082 哥尼斯堡的七桥问题 Medium 新题 jxtxzzw 随课程进度逐步开放
1083 地下迷宫探索 Medium 新题 jxtxzzw
1084 最短路径 Medium 新题 jxtxzzw 随课程进度逐步开放
1085 路由器 Easy 题库 题库
1086 Arbitrage Easy 题库 题库
1087 六度空间 Medium 新题 jxtxzzw
1088 组网计划 Medium 题库 题库
1089 哈利·波特的考试 Medium 新题 10165102128
1090 寻找航海路线 Hard 题库 题库 随课程进度逐步开放
1091 公路村村通 Easy 新题 jxtxzzw
1092 Building Roads Easy 题库 题库
1093 Hub Connection plan Easy 题库 题库
1094 旅游规划 Medium 新题 10165102128
1095 城市间紧急救援 Hard 新题 jxtxzzw 随课程进度逐步开放
1096 检查点 Super 新题 jxtxzzw 随课程进度逐步开放
1097 酒精饮料 Hard 新题 jxtxzzw 随课程进度逐步开放
1098 任务调度问题 Medium 新题 jxtxzzw 随课程进度逐步开放
1099 关键活动 Hard 新题 jxtxzzw 随课程进度逐步开放
1100 旅行商问题 Super 新题 jxtxzzw 跳转到jxtxzzw个人博客 随机算法
9001 异常的葡萄 Super 新题 jxtxzzw 弃用题,无题解,有疑问私聊jxtxzzw 聚类
9002 电子邮件地址验证 Super 新题 jxtxzzw 弃用题,无题解,有疑问私聊jxtxzzw 字符串处理

医疗调度系统

对于一个给定的队列,在默认情况下,每次都是第一个元素出队且加入到队尾,即依次变成,之后是……

但是当遇到E 命令时,需要将指定的元素(无论他处在队列的什么位置)强行移动到队首,例如对于上述情况下,如果要求E 5,那么元素移动到队首,队列变成,下次要求出队的时候,应该是出队并且移动到队尾。

写一个程序实现这个过程,并针对输入数据模拟输出出队的每一个元素。

需要注意的是E命令只是强行移动到队首,不需要输出,只有N命令需要输出。

可能会有连续的E命令操作多个人到队首,或者连续E同一个人(甚至就已经是队首的人)。

具体的实现上,当遇到N命令时,输出队首元素。

int x = queue.peek();
queue.pop();
queue.add(x);

当遇到E指令时,将给定元素移动到队首。

int index_of_element = queue.find(x);
queue.delete(index_of_element);
queue.addToFront(x);

由于每个人的编号是唯一的,所以可以很容易地找到需要提前的人现在在什么位置,然后将它提前到队首。

如果是用链表实现的,找到这个人以后,直接修改前后元素的指针即可。

x->prev->next = x->next
x->next->prev = x->prev
head->next = x
x->prev = head

如果是用数组实现的,找到这个人以后,将他移动到队首,一种方法是移动数组剩下所有的元素,另一种方法是用来表示这种情况,当遍历到数组元素值为时,跳过即可。

while(que[pos] == 0)
    pos++;
for(int j = BEGIN; j < END;j++)
    if(que[j] == X)
        que[j] = 0;

不少同学在第5组测试数据错误,注意这组数据只有个人,在一系列EN操作后,不少同学把号居民弄丢了,只剩下了号居民。

银行排队夹塞

理解题意以后,发现和 其实是类似的,也是一个可以让某些元素提前的队列。

这里模拟的是一个银行排队的队列,正常情况下,每次队首的元素出队,办理业务以后这个元素就没有了。

但是,后面的 可以找到在他前面的、是自己朋友的人 帮忙办事情,那么,当 办理完自己的业务的时候,会顺便把 的事情一起办完。

这时候,可以认为, 从队列后面某个位置,插队到了 的后面, 办理业务的时间是他们两个人各自办理业务的时间的和,办理业务后两个人同时消失。

那么,处理的逻辑就是,每次队首元素出队,表示队首这个人已经办理完毕,接下来从队列后面某个位置找一个人,把他提前到队首。

这个人,默认情况下应该是当前队首出队前,队列中的第二个元素,由于此人已经办理业务(元素出队),所以原来队列中的第二个元素自动成为队首,是下一个办理业务的人。

但是现在考虑“夹塞”,那么这个人就应该是当前队首出队这个人的朋友,他要在队列中找一个到达时间不晚于自己离开时间的自己的朋友,把他提前到自己的后面,如果找不到这样一个朋友,就按顺序找自己后面这个人。

不断循环,直到队列为空。

核心代码以及需要注意的地方如下:

for(i = 0 to n) { // 寻找一个到达时间不晚于自己办理结束时间的朋友
    if(visited[i]) continue; // 已经办理过的人
    if(arrive[i] > last) break; // 后面的人都是自己办理完业务才会到达的
    if(friend) { // 例如HashMap一一对应,或者数组、映射、count等都可以
        // 入队,标记为已处理;
        // 更新数据
        sum += last - arrive[i];
        last += process[i];
        break;
    }
}
// 如果没找到朋友,则取下一个人
sum += max(0, last - arrive[i]); // 等待时间可能为 0(窗口空闲一段时间)

GPS 数据处理

因为本题是实际生活中的情况,所有数据都是完全真实的,所以不可避免的会有各种可能的情况(例如 GPS 传输时候少了两个 ,,例如不同的设备终端在时间的处理上对秒的精度不同……)。

所以 it is your responsibility to 处理输入,而不是由出题人事先准备好完美是数据就等着你去推导数学公式去做,这与算法竞赛的数据不同。

那么对于本题来说,我特意提醒了 3 次,请再次注意:每个字段的大小(长度)不一,并不能认为字段的大小就如上述例句一样。

对于部分同学提出的意见,要求题干中基于全局的字段3和5的描述应换为『整数部分.小数部分』就不会理解错了,我给出如下答复。

我确实在出题之初就考虑过这个问题,是不是要给一组样例提醒同学们,但是后来经过查阅资料,发现确实按照无线电通讯标准GPRMC的要求,是hhmmss.sss,只是部分终端在实现的时候并没有严格按照这个标准。由此,我并没有修改题面。

但是本题的数据来源是 100% 真实的,所有的数据都是真实的 GPS 传输的数据,所以,你可能会遇到hhmmss.ss的情况。

同时,有些字段未必会在所有的终端中被统计,或者,就算本地统计了,也未必会发送到 GPS 数据上,因此,你会遇到很多字段为空,即两个,中间并不是如预期那样有信息,而是会出现,,,,的可能。

同时,有可能,有些数据传着传着就丢了。

那么,这道题应该怎么做呢?

所以,首先你应该判断这是不是一条$GPRMC,即判断字符串是不是以$GPRMC开头。

然后,你要去看看字段的个数是不是满足要求,即,的个数是不是满足要求。

取出各个字段唯一的方法,是用,分隔,而不能用加上一个长度来获取。

对于正确取出各个字段之后的结果,你要去看是不是已定位的,即是不是A,然后计算校验值。

for (int i = 2; i <= st.lastIndexOf('*') - 1; i++)
    tmp = tmp ^ st.charAt(i);

检查校验值是不是正确。

if (Integer.parseInt(st.substring(st.lastIndexOf('*') + 1), 16) == (tmp % 65536))

如果以上步骤都成立,取出表示时间的那个字段,然后换算成北京时间。

System.out.printf("%02d:%s:%s\n", (Integer.parseInt(ans.substring(0, 2)) + 8) % 24, ans.substring(2, 4), ans.substring(4, 6));

更多信息可以阅读讨论区

网址的替换

因为本题是实际生活中的情况,与 GPS 那题类似,所有数据都是完全真实的,所以不可避免的会有各种可能的情况(例如 GPS 传输时候少了两个,,例如用户输入网址的时候懒得前后加空格……)。

所以 it is your responsibility to 处理输入,而不是由出题人事先准备好完美是数据就等着你去推导数学公式去做,这与算法竞赛的数据不同。

本题题面描述已经非常清楚了,只要按照题目要求一步步做,提取出难度,然后按照格式输出就可以了。

如果是完全正常的数据,那么,只要取出难度字段和题目编号,然后,按照给定网址的格式,格式化输出对应的题目编号和难度,之后照抄即可。

但是,往往会有人不按照标准格式写文档。

(现在知道为什么文档格式一定要严格按照规范了吧,你会给很多人带来成倍成倍的工作量)

对于更多特殊情况的处理,请阅读讨论区

Comments

Kevin_K

炸表*2

LUSTRE
[已删除]
jxtxzzw

这种情况一定是你的本地环境的问题,如果你输出答案正确,那只是凑巧正确,因为本题只要求输出yes或者no

OJ环境一定是没问题的。

看你的代码

for(; pin<n; pin++)
{

    if(stack[top-1]==in[pin])
    {
        pop();
        pin++;
    }
    else
        break;
}

例如,4321,你会先做if,然后pin++,然后到了for循环的自增,pin++

这里的pin++加了 次显然是错误的

可以输出看看

printf("current pin = %d\n", pin);
if(pin==n)
    printf("yes\n");
else
    printf("no\n");

不等于 , 于是输出的是 no

请再次检查你的本机环境,因为这个pin值你是可以用手动推导的,画张图,只有四列火车,还是很容易发现问题的。

10175102204

求解1094 test4卡住了.. 请帮忙看一下 谢谢~

jxtxzzw

与楼上6324upup提出的问题一致,以后请先阅读评论区再发问题。

output
3717
answer
3716
checker's comment
wrong answer: line 1 differ - expected: '3716', found: '3717'
John_Snow

求问助教1049三元组稀疏矩阵相加的魔鬼test2数据是啥

jxtxzzw

7881 + 7454 = 11557 ????
加法都错了估计程序有大问题,发给你们助教去检查吧

John_Snow

那最后一组数据是不是输出三元组的数量很多啊,10^10都满的话也太大了

jxtxzzw

很多。
100000 100000 1000000

John_Snow

请问1080朋友圈的case3咋整,开的邻接矩阵不到30000就溢出。

deerbean

发生啥事……

LUSTRE
[已删除]
jxtxzzw

这题已经给过题解了。

Kevin_K

表炸了。emm~

John_Snow
[已删除]
jxtxzzw

没有要注意的地方,大规模数据。如有疑问问助教。

ultmaster

置顶提示。

LUSTRE

求助!!1068第一组数据

jxtxzzw

大规模随机数据,注意可能多行.

LUSTRE

有注意到多行的问题 还是没有通过第一组 设想了很多情况但还是找不到问题 求助!!

jxtxzzw

问助教

LUSTRE

好的!

Zoey

请助教大大帮忙看一下1066 第33个数据点是为什么出错了呢23333

jxtxzzw

大规模随机数据,这组数据不是特殊数据,不予公开。如有疑问请携代码联系助教。

Zoey

哦好的。谢谢

LUSTRE
[已删除]
jxtxzzw

大规模完全随机的数据,不是特殊情况

桑榆非晚

请问做过1054的最后一组数据有什么玄机吗,心塞ing,最后一组过不去,呜呜呜

jxtxzzw

没有特殊情况。该题考察的是归并排序。需要注意得分相同的考生按照考号顺序递增输出。你的代码在处理得分相同的考生时输出顺序有误。

Saitama

建议修改1040测试数据或时限,说是要用kmp,直接用朴素也a得过去。

jxtxzzw

感谢你的建议,我会处理的。本题数据用的就是朴素方法那组数据。但不是要求输出失败链接值了,朴素不能输出失败链接值吧?这相当于只能用kmp了。

10175102204

请问1005第12组测试数据究竟有什么玄机
过不去啊

Kevin_K

末尾的空格……吧?

10175102204

的确是末尾的空格....

jxtxzzw

现在首尾的空格和换行都不会测了。
之前应该是数据本身的问题,已修复,1005稍后会全部重测。

Phenom

六度空间这个题的数据好松啊。。说的N=10^4结果floyd就能过了

jxtxzzw

可能是测评机的性能太强了

6324upup

求问1058二维数组排序的输出格式有什么特别么,我自己测试的都没问题但是第一个测试点就过不去。

jxtxzzw

没有特别的格式。你就是排序错了。

6324upup

请问下1030字串排序的第六组数据除了长度是满的还有什么特别的么,一直过不去啊。。

jxtxzzw

没有什么特别。
你输出了奇怪的东西a12345678qwertyuioplkjhg

10175102138

请问助教,1017题我的代码在取高校数为1时是错误的,怎么却AC了

jxtxzzw

有可能数据里面根本就没有高校数为1的情况。如有疑问请找助教。

6324upup

请问下助教1091公村路路通test4一直过不去,是哪里出错了啊,是连通性判断错了还是路径和哪边算错了。

jxtxzzw

output
3717
answer
3716
checker’s comment
wrong answer: line 1 differ - expected: ‘3716’, found: ‘3717’

LUSTRE

求助1063树的双亲存储 之前test12之后的数据超时了
于是换了种方法
但是现在test2过不了 请问下test2的数据

jxtxzzw

你自己比原来的那个代码啊,那个不是都过了test12了吗

LUSTRE

主要两个代码思路完全不一样的 新的这个第二组是runtime error 估计是有什么特殊情况

jxtxzzw

并不是什么特殊情况呀,要是特殊情况早就给你提示了,它就是完全随机的数据 –b
964 -1 932 652 637 729 269 316 794 190 881 674 ……
这是前面若干,后面还有很多,贴不出来的,也没有什么规律……

LUSTRE

好滴!我再看看

徐梓翔Justinn

求助学长,可以帮忙看下我的1102第三组数据错在哪里了么

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

徐梓翔Justinn

可以麻烦学长提供一下1102的第三组数据嘛,测试总是对的,自己查错难度稍稍有点大

jxtxzzw

加我QQ或者发我邮箱,数据太大没法贴在评论这里

jxtxzzw

输出少了,你只是输出了6->11,这只是其中一个,还有其他的关系

徐梓翔Justinn

好的 谢谢 我再看一下

6324upup
[已删除]
6324upup

好的终于过了。多谢提醒

jxtxzzw

字符串处理的地方错了,你仔细想想,\0是应该在max_length吗?还是?

LUSTRE

求助助教!!1059第五组数据 显示runtime error
(我知道这道题给过解析 sorry 但是卡在瓶颈找不到bug 需要帮助)

jxtxzzw

古诗碎片数
1 1

例如数据
1 1
12345

这类特殊情况需要考虑

LUSTRE

好的 谢谢谢谢 搞定了

LUSTRE

求助!1066目录树第四组数据

jxtxzzw

非特殊数据,可考虑所有文件同级的情况,如有疑问请问助教。

LUSTRE

1066修改了之后现在又卡在第26组数据了。。
还有一个问题 是1053选择排序构造 提示里说3607可以买判决书 但是现在买不了了
谢谢!!

jxtxzzw

应该一直可以买……

LUSTRE

就是我点那个购买完整测评报告,它会跳转到一个访问受限的页面。

jxtxzzw

请向管理老师反馈

桑榆非晚

请问1010的第二组测试数据是什么啊…

jxtxzzw

不提供完整的数据。第二组数据是人数非常多(例如100000000)但是操作数非常少的情况,请自行检查。

妈耶

1001第八组数据总是过不了

jxtxzzw
cmd==1&&cnt<10000

你的cnt<10000是想干嘛?操作数的值为就直接往里插入。
线性表又没有最大长度,指的是线性表初始大小。
对于第8组数据,完全可以长度为10000的线性表,先执行5000个插入,再执行删除。

jxtxzzw

第8组数据是,长度为10000的线性表,一上来先执行若干个插入操作,随后再进行删除。

Kevin_K

你好!我想请教一下我1078#构造Huffman树第一个点为什么会没有通过验证函数.
当然考虑到输出顺序的原因,我没有先把树建好,而是输出与树分开操作,所以我写了一个dfs函数来验证自己的树,但依然不知道问题所在.
上文中提到的输出验证结果和验证程序全都在我最近一发提交的注解里.
我想问一下我哪里弄错了,谢谢!(注:程序中怕撞变量名(现在想想好像不可能撞)加了前缀,前缀可以直接统一删了)

jxtxzzw

已修复。原 Special Judge 在处理 “当这是非叶子节点你可以自行定义(不关心非叶子节点的值)” 时欠考虑了。抱歉浪费了你不少的时间。我的锅。(当然你可以让助教背锅,他没验题……)

LUSTRE
[已删除]
jxtxzzw

1018铁路调度,第一组数据即样例数据

jxtxzzw

4 4321 显然输出结果应该是 yes ,但是你输出的是 no。你测试出来对的?你本地有问题吧。

10175102224

请问助教1057最后一个测试点,测不出出了什么问题

jxtxzzw

不是特殊情况只是一组大规模随机数据

宅男不十分H

我就是不太懂那个等待时间到底是怎么算的
就是帮朋友做事情的这个人的等待时间是他的事务处理时间与他所有能帮到的朋友的时间之和吗?
被帮的朋友的事情一旦完成之后就立即离开队伍了是吗?

jxtxzzw

办理完业务你还留着干嘛......完成之后就离开队伍。
对于”等待”时间,你的理解出现严重偏差,生活经验严重不足。
甲到了,办理30分钟业务,则等待0分钟,办理30分钟。乙第10分钟到,则他需要等待甲办理完他才能办理,所以等待时间是20分钟。
我不认为这个上面存在理解上的歧义,不知道你到底哪里没想明白?

宅男不十分H

还有就是办理事物所花费的时间算不算自己的等待时间呢?

酱饼

请问1086 最短路径的test12是哪里出错了

jxtxzzw

点A到点B的直接相连的路径不止一条,且长度不一定相等

酱饼

多谢!原来一直以为只要在输入时更新最小权值就行,原来计算路径数也要考虑到这个条件。。

宅男不十分H

请问助教这个银行排队加塞不是可以一个人帮多个朋友办事情吗?

jxtxzzw

可以,一个人可以帮所有朋友办事,需要注意朋友必须在他(他们)办理完业务离开银行之前到达银行。

酱饼
[已删除]
jxtxzzw

大规模随机数据,应该没包含什么特殊的边界值

徐梓翔Justinn

求助助教学长 1087最短路径那一题的最后一组数据一直过不了 可以麻烦你帮我看一下问题出在哪里吗

jxtxzzw

最短路径条数错了

徐梓翔Justinn

吼的 谢谢你

你当前正在回复 博客/题目
存在问题!