it筆試題目
it行業(yè)是信息技術(shù)產(chǎn)業(yè),也是現(xiàn)代熱門求職行業(yè)。it的筆試題目有哪些呢?
it筆試題目(1)
1、有一個(gè)名人和很多平民在一塊,平民都認(rèn)識這個(gè)名人,但是這個(gè)名人不認(rèn)識任何一個(gè)平民,任意兩個(gè)平民之間是否認(rèn)識是未知的,請?jiān)O(shè)計(jì)一個(gè)算法,快速找個(gè)這個(gè)人中的那個(gè)名人。 已知已經(jīng)實(shí)現(xiàn)了一個(gè)函數(shù) bool know(int a,int b) 這個(gè)函數(shù)返回true的時(shí)候,表明a認(rèn)識b,返回false的時(shí)候表明a不認(rèn)識b。
思路:首先將n個(gè)人分為n/2組,每一組有2個(gè)人,然后每個(gè)組的兩個(gè)人調(diào)用這個(gè)know函數(shù),假設(shè)為know(a,b),返回true的時(shí)候說明a認(rèn)識b,則a肯定不是名人,a可以排除掉了,依次類推,每個(gè)組都調(diào)用這個(gè)函數(shù)依次,那么n個(gè)人中就有n/2個(gè)人被排除掉了,數(shù)據(jù)規(guī)模將為n/2。同理在剩下的n/2個(gè)人中在使用這個(gè)方法,那么規(guī)模就會將為n/4,這樣所有的遍歷次數(shù)為n/2+n/4+n/8+........ 這個(gè)一個(gè)等比數(shù)列,時(shí)間復(fù)雜度為o(n)。
2、進(jìn)程切換需要注意哪些問題?
保存處理器PC寄存器的值到被中止進(jìn)程的私有堆棧; 保存處理器PSW寄存器的值到被中止進(jìn)程的私有堆棧; 保存處理器SP寄存器的值到被中止進(jìn)程的進(jìn)程控制塊;
保存處理器其他寄存器的值到被中止進(jìn)程的私有堆棧; 自待運(yùn)行進(jìn)程的進(jìn)程控制塊取SP值并存入處理器的寄存器SP; 自待運(yùn)行進(jìn)程的私有堆棧恢復(fù)處理器各寄存器的值;
自待運(yùn)行進(jìn)程的私有堆棧中彈出PSW值并送入處理器的PSW; 自待運(yùn)行進(jìn)程的私有堆棧中彈出PC值并送入處理器的PC。
3、輸入一個(gè)升序數(shù)組,然后在數(shù)組中快速尋找兩個(gè)數(shù)字,其和等于一個(gè)給定的值。
這個(gè)編程之美上面有這個(gè)題目的,很簡單的,用兩個(gè)指針一個(gè)指向數(shù)組前面,一個(gè)指向數(shù)組的后面,遍歷一遍就可以了。
4、判斷一個(gè)自然數(shù)是否是某個(gè)數(shù)的平方。當(dāng)然不能使用開方運(yùn)算。
方法1:
遍歷從1到N的數(shù)字,求取平方并和N進(jìn)行比較。
如果平方小于N,則繼續(xù)遍歷;如果等于N,則成功退出;如果大于N,則失敗退出。
復(fù)雜度為O(n^0.5)。
方法2:
使用二分查找法,對1到N之間的數(shù)字進(jìn)行判斷。
復(fù)雜度為O(log n)。
方法3:
由于
(n+1)^2
=n^2 + 2n + 1,
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到這些項(xiàng)構(gòu)成了等差數(shù)列(每項(xiàng)之間相差2)。
所以我們可以比較 N-1, N - 1 - 3, N - 1 - 3 - 5 ... 和0的關(guān)系。
如果大于0,則繼續(xù)減;如果等于0,則成功退出;如果小于 0,則失敗退出。
復(fù)雜度為O(n^0.5)。不過方法3中利用加減法替換掉了方法1中的乘法,所以速度會更快些。
例如:3^2 = 9 = 1 + 2*1+1 + 2*2+1 = 1 + 3 + 5
4^2 = 16 = 1 + 2*1 + 1 + 2*2+1 + 2*3+1
int square(int n)
{
int i = 1;
n = n - i;
while( n > 0 )
{
i += 2;
n -= i;
}
if( n == 0 ) //是某個(gè)數(shù)的平方
return 1;
else //不是某個(gè)數(shù)的平方
return 0;
}
it筆試題目(2)
一、算法設(shè)計(jì)
1、設(shè)rand(s,t)返回[s,t]之間的隨機(jī)小數(shù),利用該函數(shù)在一個(gè)半徑為R的圓內(nèi)找隨機(jī)n個(gè)點(diǎn),并給出時(shí)間復(fù)雜度分析。
思路:這個(gè)使用數(shù)學(xué)中的極坐標(biāo)來解決,先調(diào)用[s1,t1]隨機(jī)產(chǎn)生一個(gè)數(shù)r,歸一化后乘以半徑,得到R*(r-s1)/(t1-s1),然后在調(diào)用[s2,t2]隨機(jī)產(chǎn)生一個(gè)數(shù)a,歸一化后得到角度:360*(a-s2)/(t2-s2)
2、為分析用戶行為,系統(tǒng)常需存儲用戶的一些query,但因query非常多,故系統(tǒng)不能全存,設(shè)系統(tǒng)每天只存m個(gè)query,現(xiàn)設(shè)計(jì)一個(gè)算法,對用戶請求的query進(jìn)行隨機(jī)選擇m個(gè),請給一個(gè)方案,使得每個(gè)query被抽中的概率相等,并分析之,注意:不到最后一刻,并不知用戶的總請求量。
思路:如果用戶查詢的數(shù)量小于m,那么直接就存起來。如果用戶查詢的數(shù)量大于m,假設(shè)為m+i,那么在1-----m+i之間隨機(jī)產(chǎn)生一個(gè)數(shù),如果選擇的是前面m條查詢進(jìn)行存取,那么概率為m/(m+i),如果選擇的是后面i條記錄中的查詢,那么用這個(gè)記錄來替換前面m條查詢記錄的概率為m/(m+i)*(1-1/m)=(m-1)/(m+i),當(dāng)查詢記錄量很大的時(shí)候,m/(m+i)== (m-1)/(m+i),所以每個(gè)query被抽中的概率是相等的。
3、C++ STL中vector的相關(guān)問題:
(1)、調(diào)用push_back時(shí),其內(nèi)部的內(nèi)存分配是如何進(jìn)行的?
(2)、調(diào)用clear時(shí),內(nèi)部是如何具體實(shí)現(xiàn)的?若想將其內(nèi)存釋放,該如何操作?
vector的工作原理是系統(tǒng)預(yù)先分配一塊CAPACITY大小的空間,當(dāng)插入的數(shù)據(jù)超過這個(gè)空間的時(shí)候,這塊空間會讓某種方式擴(kuò)展,但是你刪除數(shù)據(jù)的時(shí)候,它卻不會縮小。
vector為了防止大量分配連續(xù)內(nèi)存的開銷,保持一塊默認(rèn)的尺寸的內(nèi)存,clear只是清數(shù)據(jù)了,未清內(nèi)存,因?yàn)関ector的capacity容量未變化,系統(tǒng)維護(hù)一個(gè)的默認(rèn)值。
有什么方法可以釋放掉vector中占用的全部內(nèi)存呢?
標(biāo)準(zhǔn)的解決方法如下
template < class T >
void ClearVector( vector< T >& vt )
{
vector< T > vtTemp;
veTemp.swap( vt );
}
事實(shí)上,vector根本就不管內(nèi)存,它只是負(fù)責(zé)向內(nèi)存管理框架acquire/release內(nèi)存,內(nèi)存管理框架如果發(fā)現(xiàn)內(nèi)存不夠了,就malloc,但是當(dāng)vector釋放資源的時(shí)候(比如destruct), stl根本就不調(diào)用free以減少內(nèi)存,因?yàn)閮?nèi)存分配在stl的底層:stl假定如果你需要更多的資源就代表你以后也可能需要這么多資源(你的list, hashmap也是用這些內(nèi)存),所以就沒必要不停地malloc/free。如果是這個(gè)邏輯的話這可能是個(gè)trade-off
一般的STL內(nèi)存管理器allocator都是用內(nèi)存池來管理內(nèi)存的,所以某個(gè)容器申請內(nèi)存或釋放內(nèi)存都只是影響到內(nèi)存池的剩余內(nèi)存量,而不是真的把內(nèi)存歸還給系統(tǒng)。這樣做一是為了避免內(nèi)存碎片,二是提高了內(nèi)存申請和釋放的效率——不用每次都在系統(tǒng)內(nèi)存里尋找一番。
二、系統(tǒng)設(shè)計(jì)
正常用戶端每分鐘最多發(fā)一個(gè)請求至服務(wù)端,服務(wù)端需做一個(gè)異常客戶端行為的過濾系統(tǒng),設(shè)服務(wù)器在某一刻收到客戶端A的一個(gè)請求,則1分鐘內(nèi)的客戶端任何其它請求都需要被過濾,現(xiàn)知每一客戶端都有一個(gè)IPv6地址可作為其ID,客戶端個(gè)數(shù)太多,以至于無法全部放到單臺服務(wù)器的內(nèi)存hash表中,現(xiàn)需簡單設(shè)計(jì)一個(gè)系統(tǒng),使用支持高效的過濾,可使用多臺機(jī)器,但要求使用的機(jī)器越少越好,請將關(guān)鍵的設(shè)計(jì)和思想用圖表和代碼表現(xiàn)出來。
三、求一個(gè)全排列函數(shù):
如p([1,2,3])輸出:
[123]、[132]、[213]、[231]、[321]、[323]
求一個(gè)組合函數(shù)
如p([1,2,3])輸出:
[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]
這兩問可以用偽代碼。
it筆試題目(3)
1、對于一個(gè)內(nèi)存地址是32位、內(nèi)存頁是8KB的系統(tǒng)。0X0005F123這個(gè)地址的頁號與頁內(nèi)偏移分別是多少。
2、如果X大于0并小于65536,用移位法計(jì)算X乘以255的值為: (X<<8)-X
X<<8-X是不對的,因?yàn)橐莆贿\(yùn)算符的優(yōu)先級沒有減號的優(yōu)先級高,首先計(jì)算8-X為0,X左移0位還是8。
3、一個(gè)包含n個(gè)節(jié)點(diǎn)的四叉樹,每個(gè)節(jié)點(diǎn)都有四個(gè)指向孩子節(jié)點(diǎn)的指針,這4n個(gè)指針中有 3n+1 個(gè)空指針。
4、以下兩個(gè)語句的區(qū)別是:第一個(gè)動(dòng)態(tài)申請的空間里面的值是隨機(jī)值,第二個(gè)進(jìn)行了初始化,里面的值為0
int *p1 = new int[10];
int *p2 = new int[10]();
5、計(jì)算機(jī)在內(nèi)存中存儲數(shù)據(jù)時(shí)使用了大、小端模式,請分別寫出A=0X123456在不同情況下的首字節(jié)是,大端模式:0X12 小端模式:0X56 X86結(jié)構(gòu)的計(jì)算機(jī)使用 小端 模式。
一般來說,大部分用戶的操作系統(tǒng)(如windows, FreeBsd,Linux)是小端模式的。少部分,如MAC OS,是大端模式 的。
6、在游戲設(shè)計(jì)中,經(jīng)常會根據(jù)不同的游戲狀態(tài)調(diào)用不同的函數(shù),我們可以通過函數(shù)指針來實(shí)現(xiàn)這一功能,請聲明一個(gè)參數(shù)為int *,返回值為int的函數(shù)指針:
int (*fun)(int *)
7、下面程序運(yùn)行后的結(jié)果為:to test something
char str[] = "glad to test something";
char *p = str;
p++;
int *p1 = static_cast(p);
p1++;
p = static_cast(p1);
printf("result is %s\n",p);
8、在一冒險(xiǎn)游戲里,你見到一個(gè)寶箱,身上有N把鑰匙,其中一把可以打開寶箱,假如沒有任何提示,隨機(jī)嘗試,問:
(1)恰好第K次(1=
(2)平均需要嘗試多少次。
這個(gè)就是求期望值 由于每次打開寶箱的概率都是1/n,則期望值為: 1*(1/n)+2*(1/n)+3*(1/n)+......+n*(1/n) = (n+1)/2
it筆試題目(4)
1、對于如下程序:
#include
using namespace std;
class A
{
public:
A()
{
cout<<"A"<
}
};
int main(void)
{
A a[4], b,*p;
}
會輸出多少個(gè)A?( C )
A、2 B、3 C、5 D、6
p只是一個(gè)對象指針,并沒有指向一個(gè)對象的內(nèi)存空間,所以沒有調(diào)用構(gòu)造函數(shù)。
2、頭文件中的 ifndef/define/endif 有什么作用?
答:防止該頭文件被重復(fù)引用,避免變量、類型等被重新定義。
3、const 有什么用途?(請至少說明兩種)
答:(1)可以定義 const 常量。
(2)const可以修飾函數(shù)的參數(shù)、返回值,甚至函數(shù)的定義體。被const修飾的東西都受到強(qiáng)制保護(hù),可以預(yù)防意外的變動(dòng),能提高程序的健壯性。
4、如下的字符串函數(shù),用于生存一個(gè)字符串 ”連接號碼異常” ,并返回它的指針
char* strfun()
{
char str[20];
strcpy(str, “連接號碼異!);
printf(“%s \n”, str); //printf語句1
return str;
}
void main()
{
char *pstr = strfun();
printf("%s \n", pstr); //printf語句2
}
問題1 : printf語句1和printf語句2哪個(gè)能在屏幕上正在打印出來?
問題2 : 如果不能正常在屏幕上打印出字符串,請說明原因。
問題3 : 如果不修改strfun的聲明,請問該如何修改上述程序的錯(cuò)誤。
答:
問題1:語句1可以正常打印,語句2不能正常打印;
問題2:語句2使用的指針?biāo)赶虻膬?nèi)存空間str[20],在函數(shù)strfun返回時(shí)已經(jīng)被釋放了;
問題3:可以將函數(shù)strfun中的語句char str[20];改為char *str = new char[20];
5、下面是交換兩個(gè)double型數(shù)據(jù)的函數(shù),
void swap( double* p1, double* p2 )
{
double *p;
*p = *p1;
*p1 = *p2;
*p2 = *p;
}
void main()
{
double a = 0.1;
double b = 0.2;
swap( &a, &b );
}
請找出上述代碼的錯(cuò)誤,指出錯(cuò)誤的原因,并改正。
答:函數(shù)swap中混淆了double型指針與double型變量的差別,對于一個(gè)未初始化的指針訪問其內(nèi)存空間是非常危險(xiǎn)的。對swap函數(shù)修改如下:
void swap( double* p1, double* p2 )
{
double p;
p = *p1;
*p1 = *p2;
*p2 =p;
}
6、在電信業(yè)務(wù)的后臺處理程序中,經(jīng)常會涉及到處理字符串,除了用char *處理字符串之外,C++還為我們提供了封裝了的字符串類string,其本質(zhì)也是用一個(gè)動(dòng)態(tài)數(shù)組來保存字符串,類String的原型為:
class String
{
public:
String(const char *str = NULL); // 普通構(gòu)造函數(shù)
String(const String &other); // 拷貝構(gòu)造函數(shù)
~String(void); // 析構(gòu)函數(shù)
String & operate =(const String &other); // 賦值函數(shù)
private:
char *m_data; // 用于保存字符串
};
請編寫String的上述4個(gè)函數(shù)普通構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)。
代碼如下:
class String
{
private:
char *m_data;
public:
String();
String(const char *str = NULL);
String(const String &other);
~String(void);
String & operator =(const String &other);
};
String::String()
{
m_data = NULL;
}
String::String(const char *str = NULL) //帶一個(gè)指針的普通構(gòu)造函數(shù)
{
if(str == NULL)
{
m_data = new char[1];
assert(m_data != NULL);
*m_data = '\0';
}
else
{
int length=strlen(str);
m_data = new char[length+1];
assert(m_data != NULL);
strcpy(m_data,str);
}
}
String::String(const String &other) //拷貝構(gòu)造函數(shù)
{
m_data = new char[other.length+1];
assert(m_data != NULL);
strcpy((*this).m_data,other.m_data);
}
String::~String(void) //析構(gòu)函數(shù)
{
if(m_data != NULL)
{
delete m_data;
m_data = NULL;
}
}
String & String::operator=(const String &other) //賦值函數(shù)
{
if(&other != this)
{
delete [](*this).m_data;
(*this).m_data = new char[other.length+1];
assert((*this).m_data != NULL);
strcpy((*this).m_data,other.m_data);
}
}
【it筆試題目】相關(guān)文章:
比亞迪筆試題目09-24
沃爾瑪筆試題目08-25
社聯(lián)筆試題目11-02
盛大筆試題目06-10
日立電梯筆試題目08-03
常見軟件筆試題目05-03
文員必考的筆試題目05-27
文秘筆試題目及答案07-20
京東應(yīng)聘筆試題目06-05
網(wǎng)易java筆試題目07-24