腾讯笔试题回顾：数据结构与C编程基础挑战

"这篇资料包含了腾讯历年笔试题中的一些数据结构和C语言相关的问题，旨在测试应聘者的基础知识和逻辑思维能力。题目涵盖了宏定义、输出文件信息、高精度算法、链表操作、树的序列化、位运算、数组指针等多方面知识，同时也涉及到操作系统中的某些概念，如进程调度。" 1. **宏定义比较两个数的大小**： 在C语言中，可以使用`#define`来创建宏，比较两个数`a`和`b`的大小而不使用`>`, `<`或`if`语句。例如，可以定义一个宏`MAX(a, b)`，利用异或和与操作实现： ```c #define MAX(a, b) (((a) ^ ((a) ^ (b)) & -(a) < (b))) ``` 这个宏会返回较大的数。 2. **输出源文件标题和当前行号**： 在C语言中，这通常涉及到预处理器宏，如`__FILE__`和`__LINE__`。这两个宏在编译时会被替换为包含源文件名的字符串和当前源代码行号的整数值。 ```c #include <stdio.h> int main() { printf("当前文件名: %s, 当前行号: %d\n", __FILE__, __LINE__); return 0; } ``` 3. **高精度乘法**： 高精度乘法可以通过扩展十进制算法实现，即将每个数字拆分为多个位，然后逐位相乘并累加。例如，Karatsuba算法或Toom-Cook算法可以用来高效地处理大整数乘法。 4. **病毒编写**： 这个问题不鼓励在实际环境中编写病毒代码，因为这违反了网络安全原则。然而，了解病毒的基本原理，如自我复制、隐藏和传播机制，对于安全编程是有用的。 5. **过桥问题**： 这是一个经典的优化问题，可以使用图论中的最短路径算法解决，例如Dijkstra算法。关键在于找到每次两个人组合的最优策略，以最小化总时间。 6. **链表交叉归并**： 归并两个链表而不使用额外空间，可以采用迭代或递归的方式，每次比较头节点并连接较小的一个到结果链表，然后移动较小链表的头节点到下一个节点，直到一个链表为空。 7. **MFC树序列化**： MFC（Microsoft Foundation Classes）提供了序列化机制，用于将对象状态保存到文件或内存中。将树控件（如CTreeCtrl）序列化到数组或链表，需要定义一个继承自CObject的类，覆盖Serialize成员函数。 8. **位运算**： `a^b<<2`涉及位运算的优先级，`<<`（左移）的优先级高于`^`（异或）。先进行左移操作，然后再异或。 9. **参数个数**： 函数调用`fun((exp1,exp2),(exp3,exp4,exp5))`实际上有两个参数，因为逗号运算符在括号中产生了多个表达式。 10. **希尔排序和冒泡排序**： 希尔排序是一种改进的插入排序，平均速度通常比冒泡排序快。 11. **二分查找**： 二分查找适用于顺序存储的有序数组，不适用于链式存储。 12. **顺序查找的时间复杂度**： 顺序查找的平均时间复杂度为O(n)。 13. **指针和数组**： 表达式`*p=NULL;`声明了一个指针并将其设置为NULL。`*p=new char[100];`分配了100个字符的空间。`sizeof(p)`会返回指针的大小，通常是4字节（对于32位系统）或8字节（对于64位系统），而不是分配的字符数组的大小。 这些题目反映了腾讯笔试对基础编程技能和逻辑思维的重视，对于准备面试的应聘者来说，这些都是需要掌握的基础知识。