這份題目很奇怪，操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、網(wǎng)絡(luò)基礎(chǔ)、Java、C++、數(shù)據(jù)庫、正則表達(dá)式、Linux全都考到了。記得當(dāng)初在做題的時(shí)候，我都懷疑發(fā)錯(cuò)卷子了……還好最后兩道大題都做了出來，否則很容易就掛了。

• 選擇題

• 專項(xiàng)選擇題

• 編程題1（字符串篩選）

• 編程題2（字符串有效判斷）

選擇題

1、已經(jīng)獲得除CPU以外的所有所需資源的進(jìn)程處于（）狀態(tài)：

A 就緒狀態(tài)

B 阻塞狀態(tài)

C 運(yùn)行狀態(tài)

D 活動(dòng)狀態(tài)

A

進(jìn)程的五狀態(tài)模型：

運(yùn)行態(tài)：該進(jìn)程正在執(zhí)行。

就緒態(tài)：進(jìn)程已經(jīng)做好了準(zhǔn)備，只要有機(jī)會(huì)就開始執(zhí)行。

阻塞態(tài)（等待態(tài)）：進(jìn)程在某些事情發(fā)生前不能執(zhí)行，等待阻塞進(jìn)程的事件完成。

新建態(tài)：剛剛創(chuàng)建的進(jìn)程，操作系統(tǒng)還沒有把它加入到可執(zhí)行進(jìn)程組中，通常是進(jìn)程控制塊已經(jīng)創(chuàng)建但是還沒有加載到內(nèi)存中的進(jìn)程。

退出態(tài)：操作系統(tǒng)從可執(zhí)行進(jìn)程組中釋放出的進(jìn)程，或由于自身或某種原因停止運(yùn)行。

2、某二叉樹的中序遍歷序列為32145，后序遍歷序列為32145，則前序遍歷序列為：

A 54123

B 32154

C 32541

D 54321

A

二叉樹的中序遍歷序列為 32145 ，后序遍歷序列為32145 ，可知該樹只有左子樹結(jié)點(diǎn)，沒有右子樹結(jié)點(diǎn)， 5 為根結(jié)點(diǎn)。

中序遍歷序列與后序遍歷序列相同，說明該樹只有左子樹沒有右子樹，因此該樹有 5 層，從頂向下依次為54123 。

3、若已知一個(gè)棧的入棧順序是1,2,3...,n,其輸出序列為P1,P2,P3,....Pn,若P1是n,則Pi=（）？

A  i

B n-i+1

C 不確定

D n-i

B

棧的排列遵循先進(jìn)后（即后進(jìn)先出）出的原則

因?yàn)镻1是n，是出棧的第一個(gè)數(shù)字，說明在n之前進(jìn)棧的數(shù)字都沒有出棧。所以這個(gè)順序是確定的。

還可以知道，最后出棧的一定是數(shù)字1，也就是Pn。代入這個(gè)式子，是正確的。

4、（多選題）下面協(xié)議中屬于應(yīng)用層協(xié)議的是：

A ICMP、ARP

B FTP、 TELNET

C HTTP、SNMP

D SMTP、POP3

BCD

1、物理層：以太網(wǎng) 、 調(diào)制解調(diào)器 、 電力線通信(PLC) 、SONET/SDH 、 G.709 、 光導(dǎo)纖維 、 同軸電纜、 雙絞線等。

2、數(shù)據(jù)鏈路層：Wi-Fi(IEEE  802.11)、WiMAX(IEEE 802.16) 、ATM 、 DTM 、 令牌環(huán) 、以太網(wǎng)、FDDI、 幀中繼、 GPRS 、  EVDO、HSPA 、HDLC 、 PPP 、 L2TP 、PPTP 、ISDN·STP、CSMA/CD等。

3、網(wǎng)絡(luò)層協(xié)議：IP IPv4 、IPv6、 ICMP、ICMPv6·IGMP、IS-IS 、IPsec 、ARP 、RARP 、RIP等。

4、傳輸層協(xié)議：TCP、 UDP、TLS 、 DCCP、 SCTP 、 RSVP 、OSPF 等。

5、應(yīng)用層協(xié)議：DHCP 、DNS、 FTP 、Gopher 、 HTTP、 IMAP4 、 IRC、 NNTP 、 XMPP、POP3 、SIP、 SMTP、SNMP 、SSH、TELNET 、 RPC 、RTCP 、RTP 、RTSP、SDP 、 SOAP、GTP、STUN 、NTP、SSDP 、 BGP 等。

5、下列程序段的時(shí)間復(fù)雜度是：

A O(log2n)

B O(nlog2n)

C O(n)

D O(n*n)

C

當(dāng)n<=1時(shí)執(zhí)行return 1這一個(gè)語句，每次返回上一層都執(zhí)行n*fact(n-1)這一個(gè)語句，共執(zhí)行n-1次。因此共執(zhí)行基本語句n次，時(shí)間復(fù)雜度為O(n)

6、下列排序算法中最好情況和最壞情況的時(shí)間復(fù)雜度相同的是？

A 堆排序

B 快速排序

C 冒泡排序

D 歸并排序

A  D

堆排序在最好和最壞情況下的時(shí)間復(fù)雜度均為O(nlogn)

快速排序最好和最壞情況下的時(shí)間復(fù)雜度分別為O(nlogn)和O(n^2 )

冒泡排序排序在最好和最壞情況下的時(shí)間復(fù)雜度均為O(n)O(n^2)

歸并排序在最好和最壞情況下的時(shí)間復(fù)雜度均為O(nlogn)

7、將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，最少的比較次數(shù)是？

A n

B 2n

C n-1

D 2n-1

A

歸并排序是將兩個(gè)或兩個(gè)以上的有序子表合并成一個(gè)新的有序表。在歸并排序中，核心步驟是將相鄰的兩個(gè)有序序列歸并為一個(gè)有序序列。

題目中告訴我們，有兩個(gè)各有n個(gè)元素的有序序列，要將這兩個(gè)序列歸并成一個(gè)有序序列，其方法是依次從小到大取每個(gè)序列中的元素進(jìn)行比較，將較小的放進(jìn)一個(gè)新的序列中，直到取完一個(gè)有序序列中的所有元素。再把另一個(gè)序列中剩下的元素放進(jìn)新序列的后面即可。

最好的情況是一個(gè)有序序列中的最小元素大于另一個(gè)有序序列中的所有元素，這樣只需要比較n次。

8、將遞歸算法轉(zhuǎn)換為非遞歸算法通常需要使用：

A 棧

B 隊(duì)列

C 隊(duì)列

D 廣義表

D

9、在MySql中， productname regexp '[1-3]xiaomi'的含義是：

A productname 匹配“xiaomi重復(fù)1次或5次”的字符串

B productname 匹配“xiaomi字符串前一個(gè)字符為1或3“的字符串

C productname 匹配“xiaomi重復(fù)1到3次”的字符串

D productname 匹配“xiaomi字符串前一個(gè)字符為1到3“的字符串

D

10、同個(gè)進(jìn)程的不同線程以下不能被共享的是：

A 全局變量

B 堆

C 文件句柄

D 棧

D

線程共享的進(jìn)程環(huán)境包括：

進(jìn)程代碼段、進(jìn)程的公有資源（如全局變量，利用這些共享的數(shù)據(jù)，線程很容易的實(shí)現(xiàn)相互之間的通信）、進(jìn)程打開的文件描述符、消息隊(duì)列、信號(hào)的處理器、進(jìn)程的當(dāng)前目錄、進(jìn)程用戶ID、進(jìn)程組ID

線程獨(dú)占資源：

線程ID、寄存器組的值、用戶棧、內(nèi)核棧（在一個(gè)進(jìn)程的線程共享堆區(qū)（heap））、錯(cuò)誤返回碼、線程的信號(hào)屏蔽碼、線程的優(yōu)先級(jí)

專項(xiàng)選擇題

1、下列Java函數(shù)的執(zhí)行結(jié)果是什么？

static boolean foo(charc)
{
 System.out.print(c);
    return true;
}
public static void main(string[] args){
    int i = 0;
    for(foo('B');foo('A')&&(i<2);foo('C'))
    {
  i++;
        foo('D');
    }
}

A BADCBDCB

B BACDBACD

C BADCADCA

D 運(yùn)行時(shí)拋出異常

C

1.其實(shí)foo('B');就是初始化條件，只會(huì)執(zhí)行一次，所以第一個(gè)打印的肯定是B。

2.因?yàn)閕=0;循環(huán)條件是i<2 （由此可知，循環(huán)i等于2的時(shí)候就會(huì)停止循環(huán))，所以0<2滿足條件，接著會(huì)輸出A。然后執(zhí)行i++;i就變成1了，在輸出D ，在最后輸出C。一次循環(huán)后的結(jié)果是：BADC。

3.第二次循環(huán)的開始是foo('B');是初始條件，所以不會(huì)執(zhí)行。直接從foo('A')開始，輸出A，然后i為1，且小于2，此時(shí)循環(huán)體內(nèi)再次執(zhí)行i++；i的值為2了，再次輸出D，最后輸出C。第二次循環(huán)輸出：ADC。

4.然后循環(huán)再次執(zhí)行for(foo('B');foo('A')&&(i<2);foo('C'))，直接輸出A。i的值在第二輪循環(huán)后的值變成了2，2<2不成立，終止循環(huán)，輸出A。

故輸出結(jié)果是：BADCADCA。

2、下列有關(guān)軟鏈接表述正確的是：

A 不可以對不存在的文件創(chuàng)建軟鏈接

B 不能對目錄創(chuàng)建軟鏈接

C 和普通件沒有什么不同，inode都指向同一個(gè)文件在硬量中的區(qū)塊

D 保存了其代表的文件的絕對路徑是另一種文件。在硬盤上有獨(dú)立的區(qū)塊，訪問時(shí)替代自身路徑

C

A：錯(cuò)。后半句說的是硬鏈接。硬鏈接是共同擁有同一個(gè)inode,不過是每個(gè)鏈接名不同，暫時(shí)理解成不同的文件名卻指向同一文件。一個(gè)文件每加一個(gè)硬鏈接linkcount加1。

B：錯(cuò)?？梢詫δ夸泟?chuàng)建軟鏈接。如下圖所示。

D:錯(cuò)?？梢詫Σ淮嬖诘奈募?chuàng)建軟鏈接，如下圖所示。

3、選項(xiàng)中哪一行代碼可以替換//add code here 而不產(chǎn)生編譯錯(cuò)誤？

A public abstruct void another Method(){}

B testInt = testInt * 5

C public int method();

D public abstruct void another Method(int a)

D

A:該項(xiàng)方法有abstract修飾，所以是抽象方法，由于抽象方法不能有方法體，所以A項(xiàng)錯(cuò)誤

B:類體中只能定義變量和方法，不能有其他語句，所以B項(xiàng)錯(cuò)誤

C:選項(xiàng)中的方法和類中的方法重復(fù)，所以會(huì)發(fā)生編譯異常，所以C項(xiàng)錯(cuò)誤

4、有關(guān)Java靜態(tài)初始化塊說法不正確的是：

A 用戶可以控制何時(shí)執(zhí)行靜態(tài)初始化塊

B 無法直接詞用靜態(tài)初始化塊

C 在創(chuàng)建第一個(gè)實(shí)例前，將自動(dòng)調(diào)用靜態(tài)初始化塊來初始化

D 靜態(tài)初始化塊沒有訪問修飾符和參數(shù)

A

JAVA的初始化順序：

父類的靜態(tài)成員初始化>父類的靜態(tài)代碼塊>子類的靜態(tài)成員初始化>子類的靜態(tài)代碼塊>父類的代碼塊>父類的構(gòu)造方法>子類的代碼塊>子類的構(gòu)造方法

5、（多選題）以下分別對變量a給出定義，正確的有：

A 一個(gè)有10個(gè)指針的數(shù)組，該指針指向同一個(gè)整型數(shù):int *a[10];

B 一個(gè)指向10個(gè)整型數(shù)組的指針:int ( *a)[10];

C 一個(gè)指向函數(shù)的指針，該函數(shù)有一個(gè)整型數(shù)并返回一個(gè)整型數(shù):int *a(int);

D 一個(gè)有10個(gè)指針的數(shù)組，該指針指向一個(gè)函數(shù)，該函數(shù)有一個(gè)整型參數(shù)并返回一個(gè)整型數(shù)：int ( *a[10])(int);

ABD

C改為：int (*a)(int)

指針數(shù)組：首先是一個(gè)數(shù)組，數(shù)組里面的元素都是指針；（存儲(chǔ)指針的數(shù)組）

數(shù)組指針：首先是一個(gè)指針，指針指向一個(gè)一維數(shù)組；（指向數(shù)組的指針）

函數(shù)指針：一定要理解，回調(diào)中經(jīng)常使用函數(shù)指針；

指針函數(shù)：就是一個(gè)普通函數(shù)，只是返回值是指針形式；

6、（多選題）下列敘述正確的是：

A 指針可以為空，引用不能為空。

B 不存在指向空值的引用，但是存在指向空值的指針

C 引用必須被初始化，但是指針不必

D 指針初化后不能被改變，引用可以改變所指對象

ABC

D：引用初始化以后不能被改變,指針可以改變所指的對象

7、下列關(guān)于C++容器描述錯(cuò)誤的是：

A list類型支持雙向順序訪問，在list中任何位置插入刪除都很快

B deque類型支持快速順序訪間，在頭尾插入／刪除速度很快

C C++標(biāo)準(zhǔn)庫map的底層實(shí)現(xiàn)為紅黑樹

D vector類型在每次調(diào)用 pushback時(shí)都在棧上開辟新內(nèi)存

B

deque：雙端隊(duì)列。支持快速隨機(jī)訪問。在頭尾位置插入/刪除速度很快。

8、（多選題）C++中，下列數(shù)據(jù)類型的轉(zhuǎn)換，哪個(gè)可能會(huì)發(fā)生信息丟失？

A int -> double

B int -> long

C long -> float

D int -> char

CD

精度丟失只會(huì)發(fā)生在從大范圍到小范圍的轉(zhuǎn)換

32位編譯器：

char      short      int      long      float      double      指針

1                 2            4          4             4              8            4

64位編譯器：

char      short      int      long      float      double      指針

1                 2           4           8            4              8             8

9、在Java中，要使某個(gè)類能被同一個(gè)包中的其他類訪問，但不能被這個(gè)包以外的類訪問，可以：

A 使用 private關(guān)鍵字

B 讓該類不使用任何關(guān)鍵字

C 使用public關(guān)鍵字

D 使用protected關(guān)鍵字

B

default和protected的區(qū)別是：

前者只要是外部包，就不允許訪問。

后者只要是子類就允許訪問，即使子類位于外部包。

總結(jié)：default拒絕一切包外訪問；protected接受包外的子類訪問

10、（多選題）list和vector的區(qū)別有哪些？

A vector擁有一段連續(xù)的內(nèi)存空間，因此支持隨機(jī)存取，如果需要高效的隨即存取，而不在乎插入和刪除的效率，使用 vector.

B list擁有一段不連續(xù)的內(nèi)存空間，因此支持隨機(jī)存取，如果需要大量的插入和刪除，而不關(guān)心隨即存取，則應(yīng)使用list

C 已知需要存儲(chǔ)的元素時(shí)，使用list較好

D 如果需要任意位置插入元素，使用 vector較好

AB

C:已知需要存儲(chǔ)的元素時(shí),vector要好

D:如果需要任意位置插入元素，list要好

編程題1：字符串篩選

給定一個(gè)字符串，需要去除所有之前曾經(jīng)出現(xiàn)過的字符，只保留第一次出現(xiàn)的字符。

樣例輸入：hello,welcome to xiaomi

樣例輸出：helo,wcmtxia

思路：

1. 首先需要定義兩個(gè)數(shù)組，分別為“輸入的字符串?dāng)?shù)組”old[ ] 以及 “輸出的字符串?dāng)?shù)組” new[ ]；

2. 取old數(shù)組中的第一個(gè)字符去和new數(shù)組中的每一個(gè)字符串相比較是否相同，若出現(xiàn)相同，則取old數(shù)組的下一個(gè)字符再次與new中每一個(gè)字符相比較，若都不相同則存入new的數(shù)組中；

3. 最后輸出數(shù)組new；

代碼：

#include <stdio.h>
void killsame(char *o, char *n)
{
  int i=0, j, k=0;
  int label;
  
  while(o[i] != '\0')
  {
   label = 1;
   for(j=0; j<i; j++)
   {
    if (o[i] == n[j])
     label = 0;  //一旦相同標(biāo)志位置0
   }
   if(label)  // 不相等
    n[k++]=o[i];
   i++;
  } 
  n[k]='\0';  //結(jié)尾給\0
  puts(n);  //輸出
}

int main(void)
{
  printf('Please input a string you want:\n');
  char old[126]; 
  char new[126];
  scanf('%s',old);
  killsame(old, new);//去重
  return 0;
}

編程題2：字符串有效判斷

給定一個(gè)只包括''(',')’,'{','}','[',']'的字符串，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號(hào)必須使用相同類型的右括號(hào)閉合

2. 左括號(hào)必須以正確的順序閉合

注意：空字符串可被認(rèn)為是有效字符串。

輸入描述：待判斷的字符串，多個(gè)字符串需換行輸入

輸出描述：每個(gè)字符串的判斷結(jié)果，多個(gè)結(jié)果需換行輸出

樣例輸入：

() [] {}

([)]

{[]}

樣例輸出：

true

false

true

思路：

棧先入后出特點(diǎn)恰好與本題括號(hào)排序特點(diǎn)一致，所以用棧來實(shí)現(xiàn)。

當(dāng)左括號(hào)出現(xiàn)的時(shí)候入棧，當(dāng)右括號(hào)出現(xiàn)的出棧，如果匹配就繼續(xù)，不匹配就錯(cuò)誤。

當(dāng)字符串遍歷完成之后，棧內(nèi)仍有字符串就錯(cuò)誤。

用一個(gè)數(shù)組進(jìn)行和一個(gè)記錄棧頂值的int進(jìn)行了棧的模擬，代碼很簡單，很好理解。

代碼：