1 最壞情況下，合并兩個大小為n的已排序數組所需要的比較次數為2n-1。
2 聲明一個指向含有10個元素的數組的指針，其中每個元素是一個函數指針，該函數的傳回值是int，參數是int*，正确的是（） <code>int ((int *)[10])*p</code>
3 任何一個非空廣義表其表頭可能是原子，也可能是清單，而其表尾必定是清單。
4 若廣義表ls（n>=1)非空，則a1是ls的表頭，其餘元素組成的表(a2,…an)稱為ls的表尾。
5 從兩個方向搜尋雙連結清單，比從一個方向搜尋雙連結清單的方差要小
6 stl容器是線程不安全的。當容量不夠時，vector内部記憶體擴充方式是翻倍。std::stack預設是用deque實作的
7 一台剛剛接入網際網路的web伺服器第一次被通路到時，不同協定的發生順序是arp -> dns -> http。
8 輸出結果
答案：a = 10, *p = 20
9 用十進制計算30!（30的階乘），将結果轉換成3進制進行表示的話，該進制下的結果末尾會有__個0。
答案：n/3+n/9+n/27=14
10 二查搜尋樹中序周遊一定是有序的
11 作為特使，你需要組織a/b兩國元首相約在杭州蕭山機場交換一份重要檔案（假設交換檔案不需要時間）。約定兩國飛機在晚上的20點至24點這4個小時會面，a國的飛機如果到了，會等待1個小時，b國的飛機如果到了，會等待2個小時，如果假設兩架飛機在這段時間内降落機場的機率是均勻分布的，那麼能順利完成交換的機率是__。
解析：
設x為a到達的時間 y為b到達的時間
則
ok花圖像求出面積比
12 小趙和小錢二人分别從寝室和圖書館同時出發，相向而行。過了一段時間後二人在中途相遇，小趙繼續向圖書館前進，此時：若小錢繼續向寝室前進，則當小趙到達圖書館時，小錢離寝室還有600米；若小錢立即折返向圖書館前進，則當小趙到達圖書館是，小錢離圖書館還有150米。那麼圖書館與寝室間的距離是__。
設小趙，小錢速度分别位v1，v2，相遇前後時間為t1,t2。則可以得到：
( v1-v2 )(t 1+ t 2) = 600
( v 1 -v 2 )t2 = 150
v 2 t 1 = v 1 t 2
解得v 1： v 2 = 3:1，t 1： t 2 = 3:1， 則總距離s = v 1( t 1+ t 2 ) = 900
13 一張1024×640分辨率的圖檔，假定每個像素用16位色彩表示，用位圖檔案（bitmap）格式存儲，則這張圖檔檔案需要占用多大的存儲空間__。
答案：
<code>1024*640*16 bit = 1024*640*16/8 b = 1024*640*16/8/1024 kb = 1280kb</code>
14 <code>char *p[10]</code> 是指針數組,數組裡存放了10個指針,在64位系統下指針占8個位元組,是以<code>sizeof(p) = 10 * 8 = 80.</code>
<code>char (*p1)[10]</code>是數組指針,p1是一個指向存放10個char類型的數組的指針,是以<code>sizeof(p1) = 8.</code>
15 求最小生成樹的prim和kruskal都是漂亮的貪心算法。
16 設有一個n行n列的對稱矩陣a,将其下三角部分按行存放在一個一維數組b中,<code>a[0][0]</code>存放于b[0]中,那麼第i行的對角元素<code>a[i][i]</code>存放于b中()處
答案：<code>a[i][i]</code>是第i+1行第i+1列元素,是第<code>1+2+...+(i+1)=[(i+1)*(i+2)/2]</code>個元素，又因為起始坐标是0。是以存放在<code>[(i+1)*(i+2)/2]-1=[ (i+3)*i/2 ]</code>處
17 <code>int a[2][3]={1,2,3,4,5,6}</code>;,則<code>a[1][0]</code>和<code>*(*(a+1)+1)</code>的值分别是（）
答案：4 5
18 一個有序數列，序列中的每一個值都能夠被2或者3或者5所整除，這個序列的初始值從1開始，但是1并不在這個數列中。求第1500個值是多少？
2、3、5的最小公倍數是30。[ 1, 30]内符合條件的數有22個。如果能看出[ 31, 60]内也有22個符合條件的數，那問題就容易解決了。也就是說，這些數具有周期性，且周期為30.
第1500個數是：1500/22=68 1500%68=4。也就是說：第1500個數相當于經過了68個周期，然後再取下一個周期内的第4個數。一個周期内的前4個數：2,3,4,5。
故，結果為68*30=2040+5=2045
19 一個5*4的矩陣，有多少個長方形？
解析：5的排列 乘以 4的排列 （5+4+3+2+1）×（4+3+2+1）=15×10=150個矩形
21 which statement is true for the class java.util.arraylist?
the elements in the collection are ordered.
22 并不是所有的操作符都能被重載。除了 . ， .* ， :: ， ? : ， sizeof ， typeid 這幾個運算符不能被重載，其他運算符都能被重載。
23 下列的模闆說明中，正确的有（ ）
24 in c++, which of the following keyword(s) can be used on both a variable and a function?
答案：static, extern, const
25 which of the following statement(s) equal(s) value 1 in c programming language?
26 ipv4
在ip位址3種主要類型裡，各保留了3個區域作為私有位址，其位址範圍如下：
a類位址：10.0.0.0～10.255.255.255 b類位址：172.16.0.0～172.31.255.255 c類位址：192.168.0.0～192.168.255.255
27 二分查找算法
隻能用于數組；隻能在已經排序的數組上進行查找；最壞情況下時間複雜度是 o(logn).
28 指令
ping指令通過發送icmp資料包檢測網絡層是否連通 tracert是用來跟蹤路由的指令 telnet指令式通過telnet協定和另一主機相聯。 ipconfig是檢視ip位址資訊
29 路由器轉發資料包到非直接網段的過程中，依靠下列哪一個選項來尋找下一跳位址( )
答案：ip封包頭部
路由器工作在osi的網絡層，轉發的資料包是ip封包。
ip封包的頭部有源ip和目的ip
路由器根據目的ip計算出ip所在的網段，根據網段轉發到不同的端口。
如果在路由表中沒有該網段的轉發端口，則轉發至預設路由端口
30 調用動态連接配接庫的函數有哪幾種方法？
調用一個dll中的函數有兩種方法：
載入時動态連結（load-time dynamic linking），子產品非常明确調用某個導出函數，使得他們就像本地函數一樣。這需要連結時連結那些函數所在dll的導入庫，導入庫向系統提供了載入dll時所需的資訊及dll函數定位。 運作時動态連結（run-time dynamic linking），運作時可以通過loadlibrary或loadlibraryex函數載入dll。dll載入後，子產品可以通過調用getprocaddress擷取dll函數的出口位址，然後就可以通過傳回的函數指針調用dll函數了。如此即可避免導入庫檔案了。
一般有兩種調用方式：
1、靜态調用。将編譯之後的dll和所對應的lib檔案放到要調用它們的工程所在路徑，然後添加如下代碼：
<code>#pragma comment(lib,"dege.lib")</code>
<code>extern "c" __declspec(dllimport) funca(//參數);</code>
然後可以直接使用funca函數了，跟普通函數一樣。這個其實是一個靜态庫，因為你很可能沒有lib檔案，是以建議使用第二種方式：
2、動态調用。
31 wm_quit消息的用途是什麼？一個普通的windows視窗能收到的最後一條消息是什麼？
wm_quit通知程式退出，一般情況下在主線程中會有一個循環如下：
如果getmessage獲得的是wm_quit消息，getmessage便會傳回false，導緻while循環退出，一般情況下，程式也會退出。windows視窗不會受到wm_quit消息。
普通windows視窗能收到的最後一條消息時wm_destroy。
32 arraylists和linkedlist的差別
arraylist是實作了基于動态數組的資料結構，linkedlist基于連結清單的資料結構。 對于随機通路get和set，arraylist覺得優于linkedlist，因為linkedlist要移動指針。 對于新增和删除操作add和remove，linedlist比較占優勢，因為arraylist要移動資料。 arraylist的空間浪費主要展現在在list清單的結尾預留一定的容量空間，而linkedlist的空間花費則展現在它的每一個元素都需要消耗相當的空間。
32 若串<code>s=’software’</code>，其子串數目為(包括空串)：
長度為1的，8個；長度為2的，7個；長度為3的，6個；長度為4的，5個；…
…于是 總共是1+2+..+8=36,再加上空字元串，37。
33 串是一種特殊的線性表,其特殊性展現在()
資料元素是一個字元
34 若初始序列為gbfcdae，那麼隻會少需要<code>[5]</code>次兩兩交換，才能使該序列變為abcdefg。任給一個自由a–g這7個字母組成的排列，最壞的情況下需要至少<code>[6]</code>次兩兩交換，才能使序列變為abcdefg。
35 下列哪兩個資料結構，同時具有較高的查找和删除性能？（）
avl樹、hash表
36 下述哪一條是順序存儲結構的優點?()
存儲密度大
37 廣義表()和(())不同。前者是長度為0的空表，對其不能做求表頭和表尾的運算；而後者是長度為l的非空表(隻不過該表中惟一的一個元素是空表)，對其可進行分解，得到的表頭和表尾均是空表()
38 集合與線性表的差別是是否允許元素重複
39 下列哪個算法是對一個list排序的最快方法（）
二分插入排序
40 基于比較的排序的時間複雜度下限是多少?
o(nlogn)
41 假設網絡帶寬是128mb/s，網絡單向延時為100ms, 1000個用戶端(單線程)同時向伺服器傳輸64kb大小的檔案，每個請求大小為64kb，伺服器磁盤并發寫入速度30mb/s，在傳輸過程中，伺服器吞吐量為30mb/s ，單個請求響應時間為 700 ms
42 如果信号量的目前值為－4，則表示系統中在該信号量上有（4）個程序等待。
43 早期的os主要追求的是（系統的效率）
44 存儲管理方法中，（段頁式存儲管理）使用者可采用覆寫技術。
45 下列的程序狀态變化中，哪些是不可能發生的？
等待→運作
46 在存儲管理中，采用覆寫與交換技術的目的是（減少程式占用的主存空間）。
47 如何減少換頁錯誤？
通路局部性（locality of reference）滿足程序要求
48 （）就是能從這許多查詢政策中找出最有效的查詢執行計劃的一種處理過程。
查詢優化
49 應盡量避免在 where 子句中使用 or 來連接配接條件，否則将導緻引擎放棄使用索引而進行全表掃描
50 linux 有三個檢視檔案的指令，若希望在檢視檔案内容過程中可以用光标上下移動來檢視檔案内容，應使用指令。
less
51 下列檔案中，包含了主機名到ip位址的映射關系的檔案是： /etc/hosts。
52 下述是linux下多線程程式設計常用的pthread庫提供的函數名和意義，說法正确的有？
pthread_create 建立一個線程 pthread_join用來等待一個線程的結束 pthread_mutex_init 初始化一個線程互斥鎖 pthread_exit結束一個線程
53 下列關于makefile描述正确的有？
makefile檔案儲存了編譯器和連接配接器的參數選項 主要包含了五個東西：顯式規則、隐晦規則、變量定義、檔案訓示和注釋 預設的情況下，make指令會在目前目錄下按順序找尋檔案名為“gnumakefile”、“makefile”、“makefile”的檔案， 找到了解釋這個檔案
54 從n個數裡面找最大的兩個數理論最少需要比較()
n+ logn -2
55 對n個記錄的線性表進行快速排序為減少算法的遞歸深度,以下叙述正确的是()
每次分區後,先處理較短的部分
56 堆排序的時間複雜度是（），堆排序中建堆過程的時間複雜度是（）。
o(n log n),(n)
57 堆肯定是一棵平衡二叉樹()
錯
58 既希望較快的查找又便于線性表動态變化的查找方法是()
索引順序查找
59 which statement declares a variable a which is suitable for referring to an array of 50 string objects?
在java 中，聲明一個數組時，不能直接限定數組長度，隻有在建立執行個體化對象時，才能對給定數組長度.。
60 在一個容量為25的循環隊列中，若頭指針front=18，尾指針rear=9，則該循環隊列中共有 16 個元素。
61 現有一完全的p2p共享協定，每次兩個節點通訊後都能擷取對方已經擷取的全部資訊，現在使得系統中每個節點都知道所有節點的檔案資訊，共17個節點，假設隻能通過多次兩個對等節點之間通訊的方式，則最少需要（30）次通訊
2n - 4
62 線程安全的map在jdk 1.5及其更高版本環境 有哪幾種方法可以實作?
63 基于哈希的索引和基于樹的索引有什麼差別?
hash索引僅滿足“=”、“in”和“<=>”查詢，不能使用範圍查詢 hash索引無法被用來進行資料的排序操作 對于組合索引，hash 索引在計算 hash 值的時候是組合索引鍵合并後再一起計算 hash 值，而不是單獨計算 hash 值，是以通過組合索引的前面一個或幾個索引鍵進行查詢的時候，hash 索引也無法被利用 hash 索引遇到大量hash值相等的情況後性能并不一定就會比b-tree索引高
64 有一個數組（53,83,18,59,38,35），依次将其存儲在hash表中，其中哈希函數為h(k)=k%7,如采用線性探測（每次向後查找1位）的方式解決沖突，則該hash表上查找38,35,53通路hash表的表項次數分别為5 ， 2 ， 1 。
65 散列函數有一個共同性質，即函數值應按（）取其值域的每一個值。
同等機率
66 設有n個關鍵字具有相同的hash函數值，則用線性探測法把這n個關鍵字映射到hash表中需要做幾次線性探測？
n*(n-1)/2
67 假設把整數關鍵字k hash到有n個槽的散清單，以下哪些散列函數比較合适（）
h(k)=(k+random(n))mod n，其中random(n)傳回0到n-1的整數
68 拉鍊法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，是以平均查找長度較短
69 下列哪兩個資料結構，同時具有較高的查找和删除性能？（）
avl樹
hash表
70 采用開址定址法解決沖突的哈希查找中,發生集聚的原因主要是()
解決沖突的算法選擇不好
71 任何二叉樹中度為0的結點比度為2的結點多一個
72 求解最短路徑的floyd算法的時間複雜度為()
<code>o(n*n*n)</code>
73 所有的aov網都有一個拓撲序列
74 設t是由n個結點構成的二叉樹,其中,葉子結點個數為n0,次數為2的結點個數為n2,則有:
n0=n2+1
75 下面哪個是無線網絡協定（c）
a、adsl b、100baset c、wimax d、1000baset
76 android的ipc（程序通訊）主要采用以下哪個？（c）
a、socket b、pipe c、binder d、signal
77 在函數f中，本地變量a和b的構造函數(constructor)和析構函數(destructor)的調用順序是:
答案：a構造 b構造 b析構 a析構
78 在c++, 下列哪一個可以做為對象繼承之間的轉換
<code>dynamic_cast</code>
79 是用輾轉相除法來計算兩個非負數之間的最大公約數：
我們假設x,y中最大的那個數的長度為n，x>y，基本運算時間複雜度為o(1)，那麼該程式的時間複雜度為（ ）
o(logy)
80 一棵有124個葉節點的完全二叉樹，最多有（ 248）個節點。
n0 = n2 + 1，于是度為2的結點個數123個
完全二叉樹中度為1結點個數最多1個
是以該完全二叉樹中結點最多有123 + 1 + 124 = 248個
81 在cpu和記憶體之間增加cache的作用是（ ）
解決記憶體速度低于cpu的性能問題
82 假設整數0x12345678 存放在記憶體位址0x0開始的連續四個位元組中 (即位址0x0到 0x3). 那麼在以little endian位元組序存儲的memory中,位址0x3的地方存放的位元組是:
0x12
83 代碼生成階段的主要任務是（ ）
把中間代碼變換成依賴具體機器的目标代碼
84 詞法分析器用于識别（ ）
單詞
85 作業系統采用分頁式存儲管理(paging)方法，要求( )
每個程序擁有一張頁表，但隻要執行程序的頁表駐留在記憶體中，其他程序的頁表不必駐留在記憶體中
86 linux中調用write發送網絡資料傳回n(n>0)表示（ ）
本地已發送n個位元組
87 http 應答中的 500 錯誤是：
403：禁止通路； 404：找不到該頁面； 503：伺服器繁忙； 500：内部伺服器通路出錯。
88 red hat linux 9.0的安裝方式有哪些?
從軟體安裝來源可以分為:CD光牒、硬碟、nfs伺服器、ftp伺服器、http伺服器
89 下列哪個算法是對一個list排序的最快方法（）
快速排序——不需要随機通路
90 應用程式ping發出的是什麼封包（）
icmp請求封包
91 文法分析器可以用于（）
識别文法錯誤
92 如果在一個建立了tcp連接配接的socket上調用recv函數，傳回值為0，則表示（）
對端關閉了連接配接
93 下述哪種情況會提出中斷請求（）
在鍵盤輸入過程中，每按一次鍵
94 x86體系結構在保護模式下中有三種位址，請問一下那種說法是正确的？
虛拟位址先經過分段機制映射到線性位址，然後線性位址通過分頁機制映射到實體位址
95 将一顆有100個結點的完全二叉樹從根這一層開始，進行廣度周遊編号，那麼編号最小的葉節點的編号是（51）
解析：100/2+1=51
96 快排在完全無序的情況下效果最好，時間複雜度為o（nlogn）,在有序情況下效果最差，時間複雜度為o(n^2)
97 假設把整數關鍵碼k散列到有n個槽的散清單，以下那些散列函數是好的散列函數？
h(k)=k mod n
98 采用開址定址法解決沖突的哈希查找中,發生集聚的原因主要是()
99 棧是從高位址向低位址增長的。
100 程序阻塞的原因不包括__時間片切換__。
包括的有等待i/o，程序sleep，等待解鎖
![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)