2. 考研
  3. 在网络编程中，如果URL参数中含有特殊字符，如空格、“#”等，可能导致服务器端无法获得正确的参数值，需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在“％”后面跟上ASCⅡ码的两位十六进制的表示。比如空格的ASCⅡ码是32，即十六进制的0×20，

在网络编程中，如果URL参数中含有特殊字符，如空格、“#”等，可能导致服务器端无法获得正确的参数值，需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在“％”后面跟上ASCⅡ码的两位十六进制的表示。比如空格的ASCⅡ码是32，即十六进制的0×20，

admin2017-04-28  32
问题 在网络编程中，如果URL参数中含有特殊字符，如空格、“#”等，可能导致服务器端无法获得正确的参数值，需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在“％”后面跟上ASCⅡ码的两位十六进制的表示。比如空格的ASCⅡ码是32，即十六进制的0×20，因此空格被替换为“％20”。再比如“#”的ASCⅡ码为35，即十六进制的0×23，它在URL中被替换为“％23”。请设计一个时间和空间上尽可能高效的算法，把字符串中的每个空格替换为“％20”。例如输入“We are happy．”，则输出“We％20are％20happy．”。要求：
说明你所设计算法的时间复杂度和空间复杂度。注：要求考生在原来的字符串上做替换，即字符串后面有足够多的空余内存。
选项
答案空间复杂度分析：最坏情况下，字符串中有n个空格，而替换后每个空格变成3个字符，其余字符不变。所以，替换后总的字符数不会超过3n个，故空间复杂度为O(n)。 时间复杂度分析：可以把整个算法分成两步：第．步是统计字符串中空格的数目，这一步只需要对整个字符串扫描一次，所以时间复杂度是O(n)；第二步是对字符串进行替换。由于知道了空格的个数，因此每个位置的字符就唯一地确定下来了。空间复杂度分析已经证明了替换后的字符串长度是O(n)级别的，所以替换的过程也是O(n)的。而每一步中维护两个指针的代价是O(l)的，所以总的维护代价是O(n)，故整个算法的时间复杂度为O(n)。
解析
转载请注明原文地址:https://jikaoti.com/ti/nIfjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)