百度2010年校园招聘软件测试笔试题.doc

【百度2010年校园招聘软件测试笔试题】中的主要知识点集中在软件测试的基础理论、C++编程以及算法设计上。下面将详细阐述这些内容。 1. **树的遍历算法**： 树是一种非线性数据结构，深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的遍历方法。 - **深度优先遍历**：DFS通常从根节点开始，沿着树的深度方向进行访问，直到达到叶子节点，然后回溯到最近的未访问节点，再向下探索。非递归实现通常使用栈来辅助，依次将节点压入栈中，出栈并访问，直到栈空。 - **广度优先遍历**：BFS从根节点开始，按层次逐层访问所有节点。非递归实现常用队列，先访问根节点，然后将其所有子节点入队，接着访问队首节点，将它的子节点入队，以此类推。 2. **C++编程错误与改进**： 给定的`create`函数用于动态分配内存，而`compute`函数则处理输入和计算。存在以下问题： - 在`create`函数中，应该返回`new`操作的结果，而不是返回0或-1。 - `compute`函数中，`if(create(comps,num)=0)`的比较操作符错误，应该是`if(create(comps,num)==0)`。 - 应该在`create`函数的开头添加`#include <new>`，以便使用`new`操作符。 - 对于`comps`的释放，应该在`compute`函数结束前添加`delete[] comps;`，以防止内存泄漏。 3. **大型项目组件编译问题**： 这是一个典型的拓扑排序问题，可以使用拓扑排序算法解决。构建一个有向图表示组件间的依赖关系，然后对这个图进行拓扑排序。具体步骤包括： - 初始化一个空栈和一个空列表，列表用来存储已排序的组件。 - 计算每个组件的入度，即依赖它的组件数量。 - 将入度为0的组件放入栈中。 - 只要栈不为空，就取出栈顶组件，将其添加到已排序列表中，并更新其依赖组件的入度。 - 如果所有组件都能被成功添加到已排序列表，说明不存在循环依赖，否则存在循环依赖，无法完成编译。时间复杂度为O(N+E)，其中N是组件数量，E是边的数量。 4. **寻找最长连续数字串**： 实现`maxContinuNum`函数，可以使用双指针技术。从字符串的开始位置，用两个指针分别指向当前连续数字串的起始和结束位置，同时维护一个变量记录最长连续数字串的长度。遇到非数字字符时，更新最长数字串并移动起始指针。将最长数字串复制到`outputstr`。函数时间复杂度为O(N)，其中N是输入字符串的长度。 通过以上分析，我们可以看到，这份笔试题涵盖了数据结构、算法和C++语言基础，旨在考察应聘者的软件测试和编程能力。