騰訊 2021年軟件開發工程師(程序員)崗面試題

小編:管理員 362閱讀 2021.06.19

第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   <filename.h> 和 #include “filename.h”,以下說法錯誤的是(  )。

   

A  #include <filename.h>只搜索標準庫路徑

B  #include “filename.h”只搜索用戶工作路徑

C  #include <filename.h>搜索范圍比#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 <typename T1, typename T2>

B  template <class T1, T2>

C  template <class T1, class T2>

D  template <typename T1; typename T2>



答案: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 <iostream>   

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;  

}  


關聯標簽: