前言
计院的夏令营侥幸过了初审，本以为走个形式而已，过了之后才知道有好多竞争对手被刷下去了。不过还是很庆幸自己能拿到这么个机会，可以说离接下来能有书读的目标更近了一步。
花了一个晚上看了一下数据结构和计算机网络，我就猜到他不会考太多教材上的东西，果不出我所料，全是大题，而且难倒了一大票人。
下面来简要记录一下笔试的题目：
1. 相反数
题意是：输入一个 0 ~ 10^5 之间的数字，要求输出这个数本身与把这个数倒过来写得到的数的和。
例如：输入1234，计算1234+4321=5555，输出5555。
当时的题目里明确要求从控制台输入输出，就随便拿scanf和printf写了一下输入操作，算法实现就是先给输入的数造一个副本，然后副本依次模10拿数字存到另一个数，然后副本除以10，存到的数乘10，直到副本为0，最后加一下。这就是最基本的方法，没啥可说的。
2. 内排序
题意是：给出一组100以内的数，输出排序后的数组，要求时间复杂度O(n)，空间复杂度O(1)。
这题一看就是计数排序，当时一想这题出的有点偏，课内根本就没讲过非比较排序，可能有一堆人会栽在这，事实好像确实如此。考场上写的时候突然发现自己用了一个额外的数组记录输出，空间就O(n)了，硬是勾掉了几行代码然后重写成覆盖到输入的空间里。后来又发现只考虑了每种数唯一的情况，又不好意思再勾了，只能写到注释里。
3. 完数和盈数
题意是：求出 2 ~ 62 之间所有的完数和盈数并输出。完数的定义是这个整数的所有因数（除了它自身）的和等于它自身，盈数则是超过它自身。
例如：6有1、2、3三个因数，它是完数。12有1、2、3、4、6五个因数，它是盈数。
这题就是考一个求因数，求出一个累加一下就行。那就取模呗，本来求因数在时间上是O(sqrt(n))，考场上脑子一抽循环到了n/2，不过数挺小的没啥差就是了，这样还不用模完再算一遍除法，没准更快（
4. 结构体变量的内排序
题意是：给出一个表示书籍信息结构体定义和一个表示顺序表的结构体定义，顺序表包含一个书籍信息的数组，书籍信息里包含一个表示书籍类别的int变量，只能取0、1和2。现在要按照这个书籍类别将顺序表里的所有书籍排序，顺序是0、1、2，要求时间复杂度O(n)，空间复杂度O(1)。
我当时就懵了，为啥一样的排序算法会考两次，一下子意识到这是个结构体，不能当数组下标使。考场上一直在想，这相当于枚举排序，完了只有3个值，有没有比较排序的方法能实现时间O(n)的。想了半小时没想出来，最后瞎写了几句什么怎么比较就行了之类的，也没写代码。
回头和某美少女码农群的大佬们交流，他们就意思这肯定还是桶排序，一个枚举一个桶。我又懵了，那不就是计数吗？？？然后又突然发现这桶还是需要O(n)的空间，怎么能直接替换回去。最后得出的结论就是记录每个枚举值的数量，然后把元素移动到对应数量的区间去，具体怎么移动也没太细想，感觉大概可以做到。
5. 栈和队列
题意是：用两个栈实现队列的入队列和出队列操作。
我日哦，我仿佛在刷面试题。考之前还真想过不会考这种玩意儿吧，还真就考了。我以为这一块怎么也得考考二叉树和堆啥的吧，就真没考。还好老子没看嘻嘻嘻嘻嘻（
入队列的话就入一个栈，出队列的话就从另一个栈出，如果用于出队列这个栈空了就把入队列的栈的所有元素依次出栈拿到这个栈来，相当于把顺序颠倒一下，然后再出栈就行了。类似的还有两个队列实现一个栈，想法是很接近的。
晚上回来我问室友这个题，他说有没有限制啥的啊，我说没有，他就说：那简单啊，有最笨的方法，你入队列往一个栈里入，出队列就把这个栈的除了最后一个全拿出来放另一个栈，然后把要的那个拿出来，再把另一个栈的全放回来。
真的牛逼，我竟看不出任何破绽，我的室友花了10秒钟就能想出一个完美符合题意的答案，虽然不是标准解法，但实在是令我佩服。
6. 图的深度遍历
题意是：给了一堆结构体定义，包括一个表示图的结构体、一个包含图邻接链表的表头数组的结构体和一个表示图邻接链表元素的结构体。现在要求提供一个算法判断这个图是不是连通的，如果是连通的就返回true，如果不连通返回false。
有点意思，当时在纸上画图，得到的结论是不连通的话就会有几个不同的区块，感觉这是废话，题目给了提示是要求使用深度遍历方法。然后图的结构体定义里包含了点的数目和边的数目，这肯定不是白给的。
其实解法挺简单的，就是用一个数组记录所有点的访问状态。然后按邻接链表的表头数组的顺序，依次以每一个表头的点为初始点深度遍历，如果通过一个表头的点遍历到了所有的点就说明图是连通的，如果没有，那就重置访问状态，然后以表头数组的下一个点为初始点重新遍历。如果通过所有的点都不能遍历到整张图上的点，那就不连通了。
后记
以上6个算法题涉及到的代码我可能抽空写一下，现在临时想不起来考场上怎么写的，不过考得其实还可以。最后计算机网络考了俩计算题，一个算信道利用率、一个算子网IP范围，这俩题一个完全不会、一个又太简单，就先不写了。