2020.10.17 笔试题错题反思

背景

星期六下午前往了佛山南海参加某公司的笔试；有几道题我明显没有做出来的，在此复习，并重新更正一下。

面试官对我的评价是：工作时间不长，但基础较好，知识面也比较广；但安卓驱动岗位的基础薄弱（后续有待加强）。

谢谢面试官对我的评价，这两年的主动学习没有白费。

错题

求stack的增长方向

原题：设计一个函数，获知stack是向高地址增长还是低地址增长。

思路：

判断栈的增长需要依赖函数的调用，那么我需要实现2个函数，通过在一个函数中调用另外一个函数，根据各函数中变量的地址来判断增长方向。但是因为自己怀疑程序的内存分布都是随机的，因此这道题我最后放弃了作答。

事后查阅了有关资料以及做了验证，发现我之前的思路是正确的。

解答：

#include <stdio.h>

void * get_var_in_fun_address(void) {
    int i;
    static long long * p;
    p = (long long *)&i;
    return p;
}

void * check_if_stack_grow_up (void) {
    int var;
    long long * p1 = (long long *)&var;
    long long * p2 = get_var_in_fun_address();
    printf("%p : %p
", p1, p2);
    if( p1 - p2 > 0) { // 向下增长
        printf("Down
");
    }else {
        printf("UP
");
    }
}

int main(int argc, char *argv[])
{
    check_if_stack_grow_up();
    return 0;
}

运行结果：

0xffffcbfc : 0xffffcbbc
Down

优化：由于题目要求以一个函数完成这样的实现，考虑使用递归（多调用自身1次）或者传参辅助判断。原理都是类似的。

反转一条单链表

题目：反转一条单链表

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路：完成链表各个结点之间的交换，注意保存下一个节点的地址。链表的操作（尤其是单链表）一直是我薄弱的地方，之前学习链表的时候，实现了删除、交换、插入等操作以后，就将其封装作为接口，没有再去深究其中的东西了。因此，这道题会错的原因很大程度上归咎于没有定期复习一些底层原理，以为会了的东西就没在去看了。

解答：在网上学到了几种的解答思路。

递归虽然简洁，但是应该避免使用（建议改为尾递归，或者自定义栈）。

解法：头删再头插

原理：在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即反转结果。

#include <stdio.h>
struct node {
        struct node *next;
};

struct node *reverseList(struct node* head) {
        struct node *newHead = NULL;
        struct node *node;
        while (head != NULL) {
                //1. 对之前的链表做头删
                node = head;
                head = head->next;
                //2. 对新链表做头插
                node->next = newHead;
                newHead = node;
        }
        return newHead;
}

int main(int argc, char *argv[])
{
    int i;
    // 构造一条链表
    struct node  head;
    struct node  node[5];
    struct node  *p;
    head.next = &node[0];
    printf("%p
", &head);
    for (i = 0; i +1< 5; ++i) {
        node[i].next = &(node[i+1]);
        printf("%p->%p
", &node[i], node[i].next);
    }
	// 反转，并打印结果
    p = reverseList(&head);
    while(p)
    {
        printf("%p
", p);
        p = p->next;
    }
    return 0;
}

解法：迭代反转链表

从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，另其指向前一个节点。

#include <stdio.h>
struct node {
        struct node *next;
};

//迭代反转法，head 为无头节点链表的头指针
struct node * reverse_iteration(struct node * head) {
    struct node * beg = NULL;
    struct node * mid = head;
    struct node * end = head->next;
        if (head == NULL || head->next == NULL) {
                return head;
        }

    while (1)
    {
        //修改 mid 所指节点的指向
        mid->next = beg;

        if (end == NULL) { // 到尾部则退出
            break;
        }

        //整体向后移动 3 个指针
        beg = mid;
        mid = end;
        end = end->next;
    }
    //最后修改 head 头指针的指向
    head = mid;
    return head;
}

int main(int argc, char *argv[])
{
    int i;
    // 构造一条链表
    struct node  head;
    struct node  node[5];
    struct node  *p;
    head.next = &node[0];
    printf("%p
", &head);
    for (i = 0; i +1< 5; ++i) {
        node[i].next = &(node[i+1]);
        printf("%p->%p
", &node[i], node[i].next);
    }
	// 反转，并打印结果
    //p = reverseList_header_insert(&head);
    p = reverse_iteration(&head);
    while(p)
    {
        printf("%p
", p);
        p = p->next;
    }

    return 0;
}

根据遍历结果还原二叉树

题目：二叉树中如何根据已知的两种遍历方法，求出第三种遍历的结果。

思路：这道题我是之前复习数据结构的时候遇到的。关键在于，找到根节点。但这道题没有做出来的原因在于，我忘记了“中序遍历”、“后序遍历”这些定义对应树遍历顺序。

TCP/UDP传输优缺点

题目：TCP/UDP传输的优缺点。

思路：之前理解错题意了。事后想起来题目应该想问的是TCP与UDP传输的优缺点。

解答：

优点：
- TCP是面向连接的协议，安全可靠；
- UDP使用简单，而且能够支持组播，广播，传输开销比TCP小（因为TCP需要握手）
缺点：
- TCP传输开销较大，容易被握手攻击
- UDP是一种尽力传输，不可靠，需要额外的机制保证数据的有效性。

OSI网络模型

题目：OSI网络模型是怎么样的。

思路：考察网络知识概念，我把TCP/IP与OSI分层混淆了，而且还记错了各层的顺序。之前整理过有关的博客，现在笔试题做成这样，真的很惭愧。

解答：网络OSI七层模型及各层作用与 TCP/IP

RGMII与SGMII的区别

题目：面试官询问过我的工作以后，问起我们在MAC中用了什么接口，我回答的是RGMII。但后续他抛出的这个问题，我确实没有详细去了解过。

解答：连接PHY-MAC的接口：MII,RMII,SMII,GMII,RGMII,SGMII

其他错题

因为不小心而做错的题目。