腾讯 2021年软件开发工程师（程序员）岗面试题

第1题：

 一、单选题

在一个单链表中，若p所指的结点不是最后结点，在p所指结点之后插进s所指结点，则应执行操纵

A  s->next=p;p->next=s

B  s->next=p->next;p->next=s

C  s->next=p->next;p=s

D  p->next=s;s->next=p

答案：B

解析：基本的链表操作

第2题：

 在下列排序方法中，不稳定的方法有

A  归并排序与基数排序

B  插进排序与希尔排序

C  堆排序与快速排序

D  选择排序与冒泡排序

答案： C

解析：不稳定排序的意思是在排序过程中，相等的两个数比较之后不会改变其原来的位置，即不需要交换。

常见的稳定排序有：

冒泡排序，插入排序，归并排序，基数排序。

常见的不稳定排序有：

选择排序，堆排序，希尔排序，快速排序。

第3题：

 在多级存储体系中，“Cache-主存”结构的作用是解决（ ）的题目。

  

A  主存容量不足

B  辅存与CPU 速度不匹配

C  主存与辅存速度不匹配

D  主存与CPU速度不匹配

答案：D

解析：存储系统分层方面的内容

第4题：

 在需要经常查找结点的先驱与后继的场合中，使用（  ）比较合适。

       

A  单链表

B  双向链表

C  循环链表

D  链栈

答案：B

解析：单链表的实现只有一个指向后继的指针。

想要查询前驱和后继，就要两个指针，使用双向链表比较合适

第5题：

 带头结点的单链表head为空的判定条件（  ）

          

A  head==NULL

B  head->next==NULL

C  head->next==head

D  head!=NULL

答案：B

解析：注意是带头结点，如果不带头结点就选A

第6题：

 将一个递回算法改为对应的非递回算法时，通常需要使用（  ）。

    

A  优先队列

B  队列

C  循环队列

D  栈

答案：D

解析：递归之所以可以采用非递归方法实现是因为可以用栈的方式  
如果你采用递归时 是由系统管理函数栈  
而要写成非递归时必须由你自已来管理一个栈.

第7题：

 SQL语言集数据查询、数据操纵、数据定义和数据控制功能于一体，语句INSERT、DELETE、UPDATE实现（ ）功能。

      

A  数据查询

B  数据控制

C  数据定义

D  数据操纵

答案：D

解析：

DDL：数据库模式定义语言，关键字：create

DML：数据操纵语言，关键字：Insert、delete、update

DCL：数据库控制语言 ，关键字：grant、remove

DQL：数据库查询语言，关键字：select

第8题：

 设某种二叉树有如下特点：每个结点要么是叶子结点，要么有2棵子树。假如一棵这样的二叉树中有m（m>0）个叶子结点，那么该二叉树上的结点总数为（ ）。

       

A  2m+1

B  2m-1

C  2(m-1)

D  2m

答案：B

解析：

出度为0的结点为m

出度为2的结点 = 出度为0的结点 - 1 = m - 1

题目中说：每个结点要么是叶子结点，要么有2棵子树  

所以没有出度为1的结点

总结点数为：2m - 1

答案：B

第9题：

 TCP/IP协议栈的网络层的主要功能是通过（ ）来完成的。

 

A  IP协议

B  TCP协议

C  以太网协议

D  IGP协议

 答案：A

解析：网络层是IP协议

TCP协议是传输层

第10题：

 实现不同的作业处理方式（如：批处理、分时处理、实时处理等），主要是基于操纵系统对（）治理采取了不同的策略。

  

A  处理机

B  存储

C  数据库

D  文件

答案：A.

解析：实现不同的作业处理方式（如批处理、分时处理、实时处理等主要是基于操作系统对处理机管理采用了不同的策略。

第11题：

 下面关于编译系统和解释系统的观点中，错误的是

  

A  解释程序不产生目标代码，它直接执行源程序或源程序的内部形式

B  使用编译系统时会区分编译阶段和运行阶段

C  一般来说，编译系统的比较复杂，开发和维护费用都大。相反，解释系统比较简单，可移植性好，适合于以交互形式执行程序

D  一般来说，建立在编译基础上的系统在执行速度上要优于建立在解释执行基础上的系统

答案：A

解析：不是直接执行，而是转换成机器可识别码之后才能执行

第12题：

 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。由于散列函数不是一对一的关系，所以选择好的（ ）方法是散列文件的关键。

 

A  散列函数

B  除余法中的质数

C  冲突处理

D  散列函数和冲突处理

答案：D

第13题：

 衡量查找算法效率的主要标准是（  ）。

 

A  元素个数

B  所需的存储量

C  均匀查找长度

D  算法难易程度

答案：C

第14题：

 对于#include    和 #include “filename.h”，以下说法错误的是（  ）。

   

A  #include 只搜索标准库路径

B  #include “filename.h”只搜索用户工作路径

C  #include 搜索范围比#include “filename.h”小

D  两者可能等价

答案：B

解析：#include""从当前工作路径开始搜索，然后扩展到标准库路径。  

第15题：

 类定义的外部，可以被访问的成员有（ ）。

 

A  所有类成员

B  private或protected的类成员

C  public的类成员

D  public或private的类成员

答案：C

解析：

public: 公有访问，类外部可访问；

private：私有访问，类本身成员函数可访问；

protected：保护访问，类本身以及派生子类可访问

第16题：

 中断响应时间是指（  ）。

   

A  从中断处理开始到中断处理结束所用的时间

B  从发出中断请求到中断处理结束所用的时间

C  从发出中断请求到进进中断处理所用的时间

D  从中断处理结束到再次中断请求的时间

答案：C

解析：从发出中断请求到进进中断处理所用的时间

第17题：

 TCP/IP模型的体系结构中，ICMP协议属于（ ）。

 

A  应用层

B  网络层

C  数据链路层

D  传输层

答案：B

解析：ICMP协议划分不是很明显，但一般认为是IP协议的一部分，即网络层

第18题：

 下列描述的不是链表的优点是（  ）

 

A  逻辑上相邻的结点物理上不必邻接

B  插进、删除运算操纵方便，不必移动结点

C  所需存储空间比线性表节省

D  无需事先估计存储空间的大小

答案：C

解析：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。

由于链表需要存储数据元素的数据域和指针域，故所需存储空间不必线性表节省

第19题：

 二、不定项选择

下列的模板说明中，正确的有（  ）

   

A  template

B  template

C  template

D  template

答案：AC

解析：

D的分号是错的；
B的参数T2前加class 或者typename

第20题：

 （  ）面向对象程序设计语言不同于其他语言的主要特点。

 

A  继承性

B  消息传递

C  多态性

D  封装性

答案：A C D

第21题：

 三、填空题

阅读下列函数说明和C代码，将应填进（n）处的字句写在答题纸的对应栏内。
【说明】设有一个带表头结点的双向循环链表L,每个结点有4个数据成员：指向先驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0.每当在链表上进行一次L.Locate（x）操纵时，令元素值x的结点的访问频度freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
【函数】
void Locate(int &x)
{
<  结点类型说明 >
*p = first->next;
while (p != first && ____-) p = p->next;
if (p != first)
{
____________ ;
<  结点类型说明 >
*current = p;
current->prior->next = current->next;
current->next->prior = current->prior;
p = current->prior;
while (p != first &&____________ ) p = p->prior;
current->next = __________________ ;
current->prior = p;
p->next->prior = current;
p->next = __________________ ;
}
else
printf(“Sorry. Not find!\n”);  \*没找到*\
}

 p->freq++

p->data!=x

current->freq>p->freq

p->next

current

第22题：

 四、问答题

“背包题目”的基本描述是：有一个背包，能盛放的物品总重量为S,设有N件物品，其重量分别为w1，w2，…，wn，希望从N件物品中选择若干物品，所选物品的重量之和恰能放进该背包，即所选物品的重量之和即是S。递归和非递归解法都能求得“背包题目”的一组解，试写出“背包题目”的非递归解法

 

// ---------------------------------------------------   

//  注1: 一般要求一个解,此程序是得到所有解   

//  注2: 由于32位unsigned int限制,最多32个物品                           

// ---------------------------------------------------   

  

#include "stdafx.h"   

#include    

using   namespace  std;  

  

// 物品总数   

const   int  N_ITEM = 5;  

  

// 背包能装的重量   

const   int  BAG = 15;  

  

// 初始化每个物品的重量   

int  item[N_ITEM] = {2, 3, 5, 7, 8};  

  

// 标记数组   

int  flag[N_ITEM] = {0, 0, 0, 0, 0};  

  

// 结果计数器   

int  resultCount = 0;  

  

// 打印结果   

void  Print();  

  

int  main()  

{  

    // 打印已知条件   

    cout << "BAG Weight:"  << BAG << endl;  

    cout << "Item Number:"  << N_ITEM << endl;  

  

    for  ( int  i=0; i!=N_ITEM; i++)  

    {  

        cout << "Item."  << i+1 <<  " W="  << item[i] <<  "\t" ;  

    }  

  

    cout << endl;  

  

    unsigned int  count = 0;  

    unsigned int  all_count = 1;  

  

    for  ( int  i=0; i!=N_ITEM; i++)  

    {  

        all_count *= 2;//all_count记录可能解的个数   

    }  

  

    while  (1)  

    {  

        // 模拟递归...列举所有flag数组可能   

        // 其实就这个for循环是关键   

        for  ( int  i=0; i!=N_ITEM; i++)  

        {  

            if  ( 0 == flag[i] )  

            {  

                flag[i] = 1;  

                continue ;  

            }             

            else    

            {  

                flag[i] = 0;  

                break ;  

            }  

        }  

          

        // 本次重量,初始化0   

        int  temp = 0;  

  

        // 按标记计算所有选中物品重量和   

        for  ( int  i=0; i!=N_ITEM; i++)  

        {  

            if  ( 1 == flag[i] )  

            {  

                temp += item[i];  

            }  

        }  

  

        // 满足背包重量就打印   

        if  ( temp == BAG )  

        {  

            resultCount++;  

            Print();  

        }         

  

        // 如果遍历了所有情况就break掉while(1)循环   

        count++;  

        if  (count == all_count)  

        {  

            break ;  

        }  

    }  

  

    return  0;  

}  

  

void  Print()  

{  

    cout << "Result "  << resultCount << endl;  

  

    for  ( int  i=0; i!=N_ITEM; i++)  

    {  

        if  ( 1 == flag[i] )  

        {  

            cout << "Item."  << i+1 <<  "  Weight:"  << item[i] <<  "\t" ;  

        }  

    }  

  

    cout << endl;  

}