某公司算法岗笔试题（部分）

今天参加了第一次笔试，准备的不是很好，分享几道题。

## 1.选择题：

int i=1;
const int j=1;
下列错误的是：
const int *p1=&i;
const int *p1=&j;
int * const p1=&i;
int * const p2=&j;

本题考察了const和指针：

/*
* @Author: lenovouser
* @Date:   2020-07-23 21:41:23
* @Last Modified by:   lenovouser



* @Last Modified time: 2020-07-23 22:00:00



*/
#include <exception>
#include <iostream>
int main(int argc, char const *argv[])
{
    int i=1;
    const int j=1;

    const int *p1=&i;

    const int *p2=&j;

    int * const p3=&i;

    int * const p4=&j;



    return 0;
}

结果：

Compilation Failed

/usercode/file.cpp: In function ‘int main(int, const char**)’:
/usercode/file.cpp:26:21: error: invalid conversion from ‘const int*’ to ‘int*’ [-fpermissive]
     int * const p4=&j;
                     ^

居然只有最后一个是错的。首先前两个是指const int的指针，后两个是int的const指针，因为&j是一个const int的指针，不能赋值给int*，因为右边到左边需要补充一些性质。我会认为第一个也是错的，不过其实int的指针可以转为const int的指针，这样是多到少，需要丢弃一些性质。

#include <exception>
#include <iostream>
int main(int argc, char const *argv[])
{
    int i=1;
    const int j=1;

    const int *p1=&i;
    std::cout<<p1<<std::endl<<&i;

    const int *p2=&j;

    int * const p3=&i;

    // int * const p4=&j;



    return 0;
}

输出：

0x7fffefb4d380
0x7fffefb4d380

但是*p1无法赋值，而i可以赋值：

#include <iostream>
int main(int argc, char const *argv[])
{
    int i=1;
    const int j=1;

    const int *p1=&i;
    std::cout<<p1<<std::endl<<&i;
    i=2;
    *(&i)=3;
    *p1=2;

    const int *p2=&j;

    int * const p3=&i;

    // int * const p4=&j;



    return 0;
}

结果：

Compilation Failed

/usercode/file.cpp: In function ‘int main(int, const char**)’:
/usercode/file.cpp:24:8: error: assignment of read-only location ‘* p1’
     *p1=2;
        ^

 

#include <iostream>
int main(int argc, char const *argv[])
{
    int i=1;
    const int j=1;

    const int *p1=&i;
    // std::cout<<p1<<std::endl<<&i;
    i=2;
    *(&i)=3;
    std::cout<<i<<" "<<(p1==&i);
    // *p1=2;

    const int *p2=&j;

    int * const p3=&i;

    // int * const p4=&j;



    return 0;
}

3 1
好吧，这个应该就是编译器已经认定了p1是const int的指针，它的内容不可以改变，根本不核实*p1的类型。是我没考虑清楚。

## 2.选择题

#include <iostream>
int f(int n)
{
    int cnt=0;
    while(n)
    {
        cnt++;
        n=n&(n-1);
        
    }
    return cnt;
}
int main(int argc, char const *argv[])
{
    int m=1222;
    const int n=m;
    int i=n;

    std::cout<<f(i);
    return 0;
}

5

看来应该是只有指针才有const*不能到*的转换，当然可以借助强制类型转换，参考https://blog.csdn.net/alidada_blog/article/details/83536149

这个题其实是在1222=010011000110，计算这个数的1的个数。

1222=010011000110

1221=010011000011

与一次就会少一个1。

## 3选择题

#include <iostream>
char* f(char a[100])
{
    char b[10];
   return b;
}
int main(int argc, char const *argv[])
{
    char *p;
   p= f(p);
    
    p="123";
    std::cout << p << std::endl;
    return 0;
}

问这代码有错没：

123

/usercode/file.cpp: In function ‘char* f(char*)’:
/usercode/file.cpp:6:10: warning: address of local variable ‘b’ returned [-Wreturn-local-addr]
     char b[10];
          ^
/usercode/file.cpp: In function ‘int main(int, const char**)’:
/usercode/file.cpp:14:6: warning: deprecated conversion from string constant to ‘char*’ [-Wwrite-strings]
     p="123";
      ^

我用的编译器暂时没看出来有错。

 

## 4程序：

输入1,2,3,4,5，让这个数组循环右移3位，输出3,4,5,1,2。

#include<vector>
#include <iostream>
#include <numeric>
void shift(int* a,int step,int len)
{
  int b[5];
  for (int i = 0; i < len; ++i)
  {
    int temp=(i+step)% len;
    b[temp]=a[i];
  }

    for (int i = 0; i < len; ++i)
  {
    std::cout<<b[i]<<" ";
  }
}
int main(int argc, char const *argv[])
{
    int a[5]={1,2,3,4,5};
    int step=3;
    int len=5;
    shift(a,step,len);
    return 0;
}

 

这个也不算难。

 

## 5 编程：输入年月日，输出本日是这年的第几天，要求少于1000ms，内存小于256MB，例如输入2012,1,1 输出1。闰年规则：

1.能被4整除不能被100整除

2.能被400整除

任一即可。另外年份大于1小于3000，如果有错误输入，输出invalid paramter。

 

#include<vector>
#include <iostream>
#include <numeric>
void f(unsigned int y,unsigned int m,unsigned int  d)
{
    std::vector<unsigned int> n1{31,29,31,30,31,30,31,31,30,31,30,31} ;
    std::vector<unsigned int> n2{31,28,31,30,31,30,31,31,30,31,30,31} ;
    if (y==0 || y>3000 || m==0 || m>12 || d==0|| d>31)
    {
        std::cout<<"invalid parameter";
    }
    else
    {
        if (!(y%400) || (!(y%4) && (y%100)))
        {
            if (d>n1[m-1])
            {
                std::cout<<"invalid parameter";
            }
            else
            {
                std::cout<< std::accumulate(n1.begin(),n1.begin()+m-1,0)+d;
            }
        }
        else
        {
            if (d>n2[m-1])
            {
                std::cout<<"invalid parameter";
            }
            else
            {
                std::cout<< std::accumulate(n2.begin(),n2.begin()+m-1,0)+d;
            }
        }
    }

}
int main(int argc, char const *argv[])
{
    unsigned int y,m,d;
    char c;
    std::cin>>y>>c>>m>>c>>d;
    f(y,m,d);
    return 0;
}

 

这个代码有一定的应对错误输入的能力，但是很少，不过够用了。思路是先把闰年和平年的分别存成表格查询，这样减少判断的次数。

 

## 6.选择 

如果一个链表最常用的操作是在末尾插入节点和删除尾节点，选用哪种链表最省时间

A 单链表

B 带头节点的双向循环链表

C 带头节点的单向循环链表

 

如果是插入和删除尾节点都需要知道前驱节点，因为需要改前驱节点的next指针，单链表肯定不行。因为它查找前驱节点只能遍历查找，双向链表可以。

ps：头节点的好处：

1. 处理起来方便。例如，对在第一元素结点前插入结点和删除第一结点操作与其他结点的操作就统一了。
2. 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

 

 

## 7剩下还有一些逻辑推理题。

 

## 8,填空题，已知二叉树的后序遍历和中序遍历求前序遍历。

 

这部分以前没接触过。

 

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

在二叉树的遍历中存在三种较为常用的遍历方式：前序遍历、中序遍历、后序遍历。

前序遍历的顺序是根节点，左子树，右子树，一般是递归遍历。中序是左根右，后序是左右根。

 

 这个递归比较好看的。

 

中序遍历顺序 左->根->右：ebadf。

 

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

显然是左根右，中序。

 

前：ABDGCEF

中：DBGAECF

 

 

如何找根节点，前后序遍历都很好找。

中：CDBAEFG

题目解析：

1，先序遍历的第一个节点肯定是根节点，所以A为该二叉树的根节点。

2，中序遍历中根节点左侧的节点全是根节点左子树的节点，根节点右侧的节点全是根节点的右子树。所以我们可以分成 DCB（左） | A（根） | EFG（右）。

3，递归使用上述两个步骤，可以画出整个二叉树。

 

 

接着，铭记总的方针

1. 找到根节点，确定左子树，确定右子树 （最重要）

2. 对左子树进行递归分析

3.对右子树进行递归分析

---

一、已知先序、中序遍历，求后序遍历

例：

先序遍历:         GDAFEMHZ

中序遍历:         ADEFGHMZ

思路分析：

1. 根据先序遍历的特点——中左右，第一个元素一定是根节点，所以立刻确定G是根节点。

2. 既然确定了G是根节点，再根据中序遍历的特点——左中右，在根节点G之前的ADEF就是左子树，根节点G之后的HMZ就是右子树。

3.接着分析左子树（思路和第1，2步一样）。把左子树的所有元素（即ADEF这四个元素）在先序遍历和中序遍历中的顺序拿出来进行比较。

先序的顺序是DAFE（中左右），中序遍历是ADEF（左中右）。

通过先序特点得出D是左子树的节点，通过中序特点确定唯一一个在D左边的A是左子树中的左叶子，右边的是EF。

观察EF的相对位置，在先序（中左右）是FE，在中序（左中右）EF，所以得出EF的关系是左中。

到此得出左子树的形状

 

 

4.接着分析右子树（思路和第1，2步一样），把右子树的元素（HMZ）在先序遍历和中序遍历中的顺序拿出来进行比较。

先序的顺序是MHZ（中左右），中序遍历是HMZ（左中右）。

根据先序遍历的特点确定M是右子树的节点，根据中序遍历的特点确定H是左叶，Z是右叶。

所以右子树的形状

 

5.于是得出了整棵树的形状

 

那么后序遍历就是AEFDHZMG

---

二、已知中序和后序遍历，求前序遍历

中序遍历:       ADEFGHMZ

后序遍历:       AEFDHZMG

思路分析：（记住方针是一样的）

1.根据后序遍历的特点（左右中），根节点在结尾，确定G是根节点。根据中序遍历的特点（左中右），确定ADEF组成左子树，HMZ组成右子树。

2.分析左子树。ADEF这四个元素在后序遍历（左右中）中的顺序是AEFD，在中序遍历（左中右）中的顺序是ADEF。根据后序遍历（左右中）的特点确定D是左子树的节点，根据中序遍历（左中右）的特点发现A在D前面，所以A是左子树的左叶子，EF则是左子树的右分枝。

EF在后序（左右中）和中序（左中右）的相对位置是一样的，所以EF关系是左右或者左中，排除左右关系（缺乏节点），所以EF关系是左中。

到此得出左子树的形状 

 

3. 分析右子树。HMZ这三个元素在中序遍历（左中右）的顺序是HMZ，在后序遍历（左右中）的顺序是HZM。根据后序遍历（左右中）的特点，M在尾部，即M是右子树的节点。再根据中序遍历（左中右）的特点，确定H（M的前面）是右子树的左叶子，Z（M的后面）是右子树的右叶子。

所以右子树的形状 

 

4. 最后得出整棵树的形状

 

那么先序遍历就是GDAFEMHZ .

---

三、已知前序、后序遍历，求中序遍历

这种情况，可能无法还原出唯一的二叉树，因为无法唯一确定根节点的左右子树。

 

## 还有：

#include<vector>
#include <iostream>

int main(int argc, char const *argv[])
{
    std::cout<<int(double(3/2)+0.9);   

    return 0;
}

 

这个输出的是1。因为3/2是整除，int是截尾取整，直接舍弃小数点后的。

 

## 总结

其实不算很难，但是自己的熟练度不够，第一次笔试慌乱，答得不好。