46家名企笔试题集：编程与算法挑战

"46家公司笔试题.pdf" 这些题目涵盖了多个IT领域的知识点，主要涉及C++编程、算法与数据结构、操作系统以及编程基础。下面将针对每个题目提供的信息进行详细解答。 1. Sony笔试题 - 完成程序 这是一个打印星号图案的程序，可以看出它是一个典型的递归或循环结构。在空白处，可以使用嵌套循环来实现。一个可能的解决方案是： ```c for (i = 0; i < N; i++) { for (j = 0; j < N - i - 1; j++) printf(" "); for (k = 0; k < 2 * i + 1; k++) printf("*"); printf("\n"); } ``` 这里使用两个循环，外层循环控制行数，内层第一个循环打印空格，第二个循环打印星号。 2. 完成程序 - 实现对数组的降序排序 这个问题需要实现一个排序函数，可以选择冒泡排序、选择排序、插入排序等简单排序算法，或者是更高效的快速排序、归并排序等。这里使用冒泡排序作为示例： ```c void sort() { int temp; for (int i = 0; i < sizeof(array) / sizeof(array[0]) - 1; i++) { for (int j = 0; j < sizeof(array) / sizeof(array[0]) - 1 - i; j++) { if (array[j] < array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } ``` 这个函数通过两层循环不断比较相邻元素并交换位置，从而达到降序排序的效果。 3. 费波那契数列 费波那契数列的第n项可以通过递归或动态规划来计算。递归虽然直观，但效率低，因为它会重复计算很多相同的子问题。这里给出一个非递归的解决方案： ```c int Pheponatch(int N) { int fib[N + 1]; fib[0] = 0; fib[1] = 1; for (int i = 2; i <= N; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } return fib[N]; } ``` 这个程序创建了一个足够大的数组，存储了前N+1项的费波那契数，然后返回第N项。 4. 找出程序错误并改正 这个程序中存在一个未定义的函数`append`，并且没有正确地初始化`TNode`类型的指针`root`。首先需要定义`append`函数，这里假设它接收一个整数并将其添加到二叉树中。为了初始化`root`，可以在`main`函数开始时分配一个新节点： ```c #include<stdio.h> #include<malloc.h> typedef struct{ TNode*left; TNode*right; int value; }TNode; TNode*root=NULL; void append(TNode**node, int N) { // 假设这是一个简单的二叉树添加节点的函数 } int main() { root = (TNode*)malloc(sizeof(TNode)); // 初始化根节点 root->value = 0; // 为根节点赋值，避免未初始化的警告 append(&root, 63); append(&root, 45); // ... } ``` 这里仅给出了修复`append`函数调用的框架，具体实现取决于你需要如何构建二叉树。 这些题目体现了在面试和笔试中常见的编程基础、算法和数据结构理解，以及对于特定语言（如C++）特性的掌握。在准备IT行业的笔试和面试时，深入理解这些基础知识至关重要。