某知名互聯(lián)網(wǎng)金融企業(yè)PHP工程師面試筆試真題及答案

某知名互聯(lián)網(wǎng)金融企業(yè)PHP工程師面試筆試真題及答案一、選擇題1、S市共有AB兩個區(qū)，人口比例為3:5，據(jù)歷史統(tǒng)計，A區(qū)的犯罪率為0.01%，B區(qū)的犯罪率為0.015%，現(xiàn)有一起新案件發(fā)生在S市，那么案件發(fā)生在A區(qū)的可能性是______

A．37.5%

B．32.5%

C．28.6%

D．26.1%

2、有如下代碼：

functiondouble($a){

return$a*$a;

}

$c=double(5);

則變量c的數(shù)據(jù)類型為______

A．Int

B．Float

C．Double

D．String

3、GMT時區(qū)下的時間戳與你所在時區(qū)下的時間戳的秒數(shù)差距是______

A．取決于你所在時區(qū)與GMT時區(qū)的時間差

B．沒有差別

C．只當你也在GMT時區(qū)時才會相同

D．永遠不會相同

4、下面程序的運行結(jié)果是______

＜?php

$nextWeek=time()+(7*24*60*60);

echo'Now:'.date('Y-m-d')."\\n";

echo'NextWeek:'.date('Y-m-d',$nextWeek)."\\n";

?＞

A．得到今天的日期(月-日)

B．得到今天的日期(年-月-日)與下周的日期(年-月-日)

C．得到現(xiàn)在的時間(小時-分-秒)

D．得到現(xiàn)在到下周的時間間隔

5、以下能匹配字符串PHP|architect的正則表達式是______

A．.*

B．...|.........

C．\d{3}\|\d{8}

D．[az]{3}\|[az]{9}

E．[a-z][a-z][a-z]\|\w{9}

6、以下無法在PHP4中實現(xiàn)的面向?qū)ο蟮母拍钍莀_____

①抽象類

②Final類

③public、private、protected(PPP)方法

④接口

A．抽象類

B．PPP方法

C．PPP方法和接口

D．以上所有都不可用

E．以上所有都可用

7、以下有關PHP高級特性的說法中，正確的是______

A．可以定義一個類去實現(xiàn)預定義接口Iterator，然后就能像訪問數(shù)組一樣訪問這個類創(chuàng)建的對象

B．spla_utoload_register()提供了一種更加靈活的方式來實現(xiàn)類的自動加載，不再建議使用autoload()函數(shù)

C．PHP在對象中調(diào)用一個不可訪問方法時，invoke()方法會被自動調(diào)用

D．匿名函數(shù)也叫閉包函數(shù)，常用作回調(diào)函數(shù)參數(shù)的值，但是不能作為變量的值來使用

8、以下沒有PHP擴展庫的DBMS是______

A．MySQL

B．IBMDB/2

C．PostgreSQL

D．MicrosoftSQLServer

E．以上都不對

9、以下代碼能正確在瀏覽器中顯示圖片的是______

A．＜?php

$img=imagecreatefromjpeg("images/scce.jpg");

imagejpeg($img);

imagedestroy($img);

?＞

B．＜?php

header("content-type:image/jpeg");

$img=imagecreatefromjpeg("images/scce.jpg");

imagejpeg($img);

imagedestroy($img);

?＞

C．＜?php

header("content-type:image/jpeg");

$img=imagecreatefromfile("images/scce.jpg");

imageout($img);

imagedestroy($img);

?＞

D．＜?php

header("content-type:image/jpeg");

$img=imageopen("images/scce.jpg");

imagejpeg($img);

imagedestroy($img);

?＞

10、如果php.ini配置允許，那么下面選項中，fopen()函數(shù)不支持的網(wǎng)絡協(xié)議是______

A．HTTP

B．ftp

C．mailD．zlib

二、填空題11、array_push()函數(shù)的作用是______。

12、更改mysq1的表字段名的標準語法為______。

13、JS表單彈出對話框函數(shù)是______，獲得輸入焦點函數(shù)是______。

14、在PHP中，“+”操作符的功能包括______、______。

15、＜?phpecho1+2+"3+4+5";?＞程序的運行結(jié)果為______。

三、簡答題16、請說明在php.ini中safe_mode開啟之后對于PHP系統(tǒng)函數(shù)的影響。

17、什么是數(shù)據(jù)庫三級封鎖協(xié)議?

18、什么是觀察者模式?

19、面向?qū)ο髱状笤瓌t是什么?

20、SVN與Git的區(qū)別是什么?它們的工作流程是什么?使用Git有什么好處?怎樣處理沖突?Git中基本的命令有哪些?

四、編程題21、給定一臺有m個存儲空間的機器，有n個請求需要在這臺機器上運行，第i個請求計算時需要占R[i]空間，計算結(jié)果需要占O[i]個空間(O[i]＜R[i])。請設計一個算法，判斷這n個請求能否全部完成?若能，給出這n個請求的安排順序。

22、寫一個函數(shù)，盡可能高效地從一個標準url里取出文件的擴展名。例如，/abc/de/fg.php?id=1需要取出php或.php。

23、翻轉(zhuǎn)(也叫顛倒)棧的所有元素，例如，輸入棧(1，2，3，4，5)，其中，1處在棧頂，翻轉(zhuǎn)之后的棧為(5，4，3，2，1)，其中，5處在棧頂。

有一個MySQL數(shù)據(jù)庫表payment記錄用戶購買訂單，表結(jié)構(gòu)如下：

TABLEpayment(

idintunsignedAUTO_INCREMENT,

useridintunsignedcomment'用戶id',

quantitysmallintunsignedcomment'本次購買產(chǎn)品數(shù)量',

pay_timetimestampcomment'購買時間',

PRIMARYKEY(id)

)

用戶每訪問成功付款一筆訂單(從進入到離開)，就會向這個表增加一條記錄，記錄用戶的ID(user_id)，以及購買的產(chǎn)品數(shù)量。比如：“208，2”，表示208這個用戶購買2個產(chǎn)品。24、請寫出一個SQL語句挑出用戶(id=100)最近購買的10條訂單。25、請寫出一個SQL語句挑出用戶(id=100)最近購買的第10～20條訂單(共10個)。26、請寫出一個SQL語句挑出購買產(chǎn)品數(shù)最多的10個用戶(user_id)和對應購買的產(chǎn)品總數(shù)。

答案:

一、選擇題

1、C[解析]

根據(jù)題目意思可知，假設A區(qū)的人數(shù)為3X，那么，B區(qū)人口數(shù)為5X，A區(qū)犯罪的人數(shù)為3X*0.01%，B區(qū)犯罪的人數(shù)為5X*0.015%。A區(qū)犯罪的可能性=(A區(qū)犯罪人數(shù))/(A區(qū)犯罪人數(shù)+B區(qū)犯罪人數(shù))=(3X*0.01%)/(3X*0.01%+5X*0.015%)=28.6%。

所以，本題的答案為C。2、A[解析]

向double()函數(shù)內(nèi)傳入數(shù)字5，它的類型為Int，函數(shù)內(nèi)5*5得到25返回給$c，兩個Int類型的數(shù)相乘結(jié)果還是Int類型，因此$c的類型為Int。

所以，本題的答案為A。3、B[解析]GMT叫格林尼治時間，其本身就是時間戳，任何時區(qū)下的當前時間都是相同的，當前時間是一個絕對的時間點，不存在秒數(shù)的差距。選項B正確。

所以，本題的答案為B。4、B[解析]time()函數(shù)可以獲取當前的時間戳，而時問戳是以秒為計算的。所以$nextWeek獲取的是從當前時間開始7天的時間秒數(shù)，即下一周時間。可以通過date()函數(shù)輸出當前時間格式或指定時間戳的時間格式。所以now對應的是今天的日期，而nextweek對應的是下周的時間。且格式為Y對應年，m對應月，d對應日。選項B正確。

所以，本題的答案為B。5、E[解析]

對于選項A，“.*”可以表示匹配任意字符，雖然能夠匹配題目中的條件字符串，但是相對于E的正則表達式來說并不規(guī)范，選項A錯誤。

對于選項B，并不存在這一正則表達式，選項B錯誤。

對于選項C，“\d”表示的是匹配數(shù)字，選項C錯誤。

對于選項D，該表達式的“[aZ]”格式不對，選項D錯誤。

對于選項E，“[a-z]”表示匹配a-z中的任意一個字母，“\|”表示轉(zhuǎn)義“|”符，“\w”表示匹配字母或數(shù)字或下劃線或漢字，“{9}”表示只能是9位。對于題目中的匹配字符串，該正則可以匹配，選項E正確。

所以，本題的答案為E。6、D[解析]

在PHP4.0的概念中，抽象類、final類、public、private、protected(PPP)方法都沒有實現(xiàn)。選項D正確。

所以，本題的答案為D。7、B[解析]

對于選項A，只有ArrayAccess能夠提供像訪問數(shù)組一樣訪問這個對象的接口，不能定義一個類或預定義接口Iterator去實現(xiàn)這個功能。選項A錯誤。

對于選項B，因為可以通過spla_utoload_register()函數(shù)創(chuàng)建autoload函數(shù)的隊列，按定義順序逐個執(zhí)行，比__autoload()只可以定義一次使用更方便，所以不建議使用autoload()函數(shù)。選項B正確。

對于選項C，__call方法是在創(chuàng)建一個類實例化后就可以直接調(diào)用對象使用，當調(diào)用的方法不可訪問或沒有權(quán)限訪問時，會自動調(diào)用__call方法。選項C錯誤。

對于選項D，匿名函數(shù)是可以賦值給變量的。選項D錯誤。

所以，本題的答案為B。8、E[解析]PHP支持大部分的數(shù)據(jù)庫連接使用。對于PostgreSQL和MySQL數(shù)據(jù)庫，PHP都擁有對應的擴展庫。訪問IBMDB/2可以用ODBC擴展，訪問MicrosoftSQLServer可以用TDS和mssql擴展。選項E正確。

所以，本題的答案為E。9、B[解析]

當瀏覽器中顯示圖片時，首先需要使用Header函數(shù)來發(fā)送頭信息，設置文件的內(nèi)容，這里可以通過Header("content-type:image/jpeg")設定內(nèi)容為一張jpeg的圖片，然后使用imagecreatefromjpeg()函數(shù)來顯示jpeg圖片或者創(chuàng)建一個新圖像，再通過imagejpeg()函數(shù)生成對應的jpeg格式圖片，最后用imagedestroy($img)清除圖片資源。選項B正確。

對于選項A，沒有通過Header函數(shù)聲明是圖片，選項A錯誤。

對于選項C，不存在imageout()函數(shù)生成圖片，選項C錯誤。

對于選項D，不存在imageopen()函數(shù)打開圖片，選項D錯誤。

所以，本題的答案為B。10、C[解析]

因為fopen()函數(shù)可以打開文件或者URL，所以格式為HTTP，ftp的網(wǎng)頁路徑可以打開，zlib的文件格式也是可以打開的。但是不支持打開mail函數(shù)查看郵件。選項C正確。

所以，本題的答案為C。二、填空題11、將一個或多個元素壓入數(shù)組的末尾。12、altertable表名change原名新名新類型[first|after]。[解析]

修改表字段名：altertable表名CHANGE原字段名新字段名類型：

修改字段類型：altertable表名MODIFY字段名類型：

增加一個字段：altertable表名addCOLUMN字段名類型NOTNULL(或DEFAULTNULL)；新增一個字段默認不為空(或默認為空)；

刪除一個字段：altertable表名DROPCOLUMN字段名；13、alert()、prompt()、confirm()；focus()。14、數(shù)組數(shù)據(jù)合并、變量數(shù)據(jù)相加。[解析]“+”操作符可以實現(xiàn)數(shù)組的合并，但是合并遵循如下的規(guī)則：如果兩個數(shù)組存在相同的key，那么結(jié)果保留前面數(shù)組中的值，而丟棄掉后面數(shù)組中的值，如下例所示：

$a=array(

1=＞'a',

);

$b=array(

2=＞'b',

1=＞'c'

);

$c=$a+$b;

vat_dump($c);

程序的運行結(jié)果為

array(2){

[1]=＞

string(1)"a"

[2]=＞

string(1)"b"

}

“+”最常使用的功能就是實現(xiàn)變量數(shù)據(jù)的相加。15、6。[解析]

首先運行1+2結(jié)果為3，在執(zhí)行+"3+4+5";的時候會強制把這個字符串轉(zhuǎn)換為整數(shù)，這個字符串轉(zhuǎn)換后的整數(shù)為3，因此最終運行結(jié)果為3+3=6。三、簡答題16、PHP中的save_mode開啟后，可以提供一個安全的共享環(huán)境，它主要對系統(tǒng)的操作、文件、權(quán)限設置等產(chǎn)生影響。但該模式在PHP5.4.0以后已經(jīng)被廢除。該模式會對以下的函數(shù)產(chǎn)生影響：

1)首先是與操作文件系統(tǒng)有關的函數(shù)，這些函數(shù)訪問文件時會被限制，例如，ckdir()、move_uploaded_file()、chgrp()、parse_ini_file()、chown()、rmdir()、copy()、rename()、fopen()、require()、highlight_file()、show_source()、include()、symlink()、link()、touch()、mkdir()、unlink()等函數(shù)。

2)其次還有一些其他的函數(shù)也會有影響，例如，exec()、shell_exec()、pasathru()、system()、popen()等。

17、眾所周知，基本的封鎖類型有兩種：排它鎖(X鎖)和共享鎖(S鎖)。所謂X鎖是事務T對數(shù)據(jù)A加上X鎖時，只允許事務T讀取和修改數(shù)據(jù)A。所謂S鎖是事務T對數(shù)據(jù)A加上S鎖時，其他事務只能再對數(shù)據(jù)A加S鎖，而不能加X鎖，直到T釋放A上的S鎖。若事務T對數(shù)據(jù)對象A加了S鎖，則T就可以對A進行讀取，但不能進行更新(S鎖因此又稱為讀鎖)，在T釋放A上的S鎖以前，其他事務可以再對A加S鎖，但不能加X鎖，從而可以讀取A，但不能更新A。

在運用X鎖和S鎖對數(shù)據(jù)對象加鎖時，還需要約定一些規(guī)則，例如，何時申請X鎖或S鎖、持鎖時間、何時釋放等，稱這些規(guī)則為封鎖協(xié)議(LockingProtocol)。對封鎖方式規(guī)定不同的規(guī)則，就形成了各種不同的封鎖協(xié)議。一般使用三級封鎖協(xié)議，也稱為三級加鎖協(xié)議。該協(xié)議是為了保證正確地調(diào)度事務的并發(fā)操作。三級加鎖協(xié)議是事務在對數(shù)據(jù)庫對象加鎖、解鎖時必須遵守的一種規(guī)則。下面分別介紹這三級封鎖協(xié)議。

一級封鎖協(xié)議：事務T在修改數(shù)據(jù)R之前必須先對其加X鎖，直到事務結(jié)束才釋放。事務結(jié)束包括正常結(jié)束(COMMIT)和非正常結(jié)束(ROLLBACK)。一級封鎖協(xié)議可以防止丟失修改，并保證事務T是可恢復的。使用一級封鎖協(xié)議可以解決丟失修改問題。在一級封鎖協(xié)議中，如果僅僅是讀數(shù)據(jù)不對其進行修改，是不需要加鎖的，它不能保證可重復讀和不讀“臟”數(shù)據(jù)。

二級封鎖協(xié)議：一級封鎖協(xié)議加上事務T在讀取數(shù)據(jù)R之前必須先對其加S鎖，讀完后方可釋放S鎖。二級封鎖協(xié)議除防止了丟失修改，還可以進一步防止讀“臟”數(shù)據(jù)。但在二級封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放S鎖，所以它不能保證可重復讀。

三級封鎖協(xié)議：一級封鎖協(xié)議加上事務T在讀取數(shù)據(jù)R之前必須先對其加S鎖，直到事務結(jié)束才釋放。三級封鎖協(xié)議除防止了丟失修改和不讀“臟”數(shù)據(jù)外，還進一步防止了不可重復讀。

18、觀察者模式(也被稱為發(fā)布/訂閱模式)提供了避免組件之間緊密耦合的另一種方法，它將觀察者和被觀察的對象分離開。在該模式中，一個對象通過添加一個方法(該方法允許另一個對象，即觀察者注冊自己)使本身變得可觀察。當可觀察的對象更改時，它會將消息發(fā)送到已注冊的觀察者。這些觀察者使用該信息執(zhí)行的操作與可觀察的對象無關，結(jié)果是對象可以相互對話，而不必了解原因。

例如，用戶界面可以作為一個觀察者，業(yè)務數(shù)據(jù)是被觀察者，用戶界面觀察業(yè)務數(shù)據(jù)的變化，發(fā)現(xiàn)數(shù)據(jù)變化后，就顯示在界而上。而向?qū)ο笤O計的一個原則是，系統(tǒng)中的每個類將重點放在某一個功能上，而不是其他方而。一個對象只做一件事情，并且將它做好。觀察者模式在模塊之間劃定了清晰的界限，提高了應用程序的可維護性和重用性。

示例代碼如下：

＜?php

//觀察者接口

interfaceInterfaceObserver

{

functiononListen($sender,$args);

functiongetObserverName();

}

//可被觀察者接口

interfaceInterfaceObservable

{

functionaddObserver($observer);

functionremoveObserver($observer_name);

}

//觀察者抽象類

abstractclassObserverimplementsInterfaceObserver

{

protected$observer_name;

functiongetObserverName()

{

return$this-＞observer_name;

}

functiononListen($sender,$args)

{}

}

//可被觀察類

abstractclassObservableimplementsInterfaceObservable

{

protected$observers=array();

publicfunctionaddObserver($observer)

{

if($observerinstanceofInterfaceObserver)

{

$this-＞observers[]=$observer;

}

}

publicfunctionremoveObserver($observer_name)

{

foreach($this-＞observersas$index=＞$observer)

{

if($observer-＞getObserverName()===$observer_name)

{

array_splice($this-＞observers,$index,1);

return;

}

}

}

}

//模擬一個可以被觀察的類

classAextendsObservable

{

publicfunctionaddListener($listener)

{

foreach($this-＞observersas$observer)

{

$observer-＞onListen($this,$listener);

}

}

}

//模擬一個觀察者類

classBextendsObserver

{

protected$observer_name='B';

publicfunctiononListen($sender,$args)

{

var_dump($sender);

echo"＜br＞";

var_dump($args);

echo"＜br＞";

}

}

//模擬另外一個觀察者類

classCextendsObserver

{

protected$observer_name='C';

publicfunctiononListen($sender,

$args)

{

var_dmnp($sender);

echo"＜br＞";

var_dump($args);

echo"＜br＞";

}

}

$a=newA();

//注入觀察者

$a-＞addObserver(newB());

$a-＞addObserver(newC());

//可以看到觀察到的信息

$a-＞addListener('D');

//移除觀察者

$a-＞removeObserver('B');

?＞

19、面向?qū)ο蟠嬖谖宕蠡驹瓌t，分別是單一職責原則、開放封閉原則、替換原則、依賴倒置原則和接口隔離原則。

(1)單一職責原則

所謂單一職責原則，即一個類最好只做一件事，以提高內(nèi)聚性來減少引起變化的原因，單一原則是低耦合、高內(nèi)聚在面向?qū)ο笤瓌t上的引申。

(2)開放封閉原則

軟件的功能應該是可擴展的，盡可能減少修改，因為修改程序可能會對原來的程序造成影響。雖然建議盡可能不修改程序，但是允許通過添加功能來減少修改。

(3)替換原則

只有子類能夠替換基類，在繼承機制的約束規(guī)范中，子類替換基類時，可以保證運行期內(nèi)識別子類，保證繼承復用。

(4)依賴倒置原則

高層模塊不依賴底層模塊，二者都依賴于抽象，抽象不依賴于實體，而實體依賴于抽象。模塊間的依賴是通過抽象方法發(fā)生的，實現(xiàn)類中不發(fā)生直接的依賴關系，而依賴關系是通過接口或抽象類產(chǎn)生的。即接口或抽象類不依賴于實現(xiàn)類，而實現(xiàn)類依賴于接口和抽象類。這種依賴倒置原則可以有效地減少類之間的耦合性，提高系統(tǒng)的穩(wěn)定性，減少并發(fā)引起的風險，提高代碼的可讀性和可維護性。

(5)接口隔離原則

建議開發(fā)使用多個小的、專門的接口，避免使用一個大的總接口。即每一個功能有一個專門的功能接口，需要用到才調(diào)用，不需要全部功能匯總到一個接口，這樣可以提高代碼的靈活性，降低類之間的耦合性，提高穩(wěn)定性。

20、SVN和Git的區(qū)別如下：

1)SVN屬于集中化的版本控制系統(tǒng)，使用起來更像是檔案倉庫，支持并行讀寫，支持代碼的版本化管理，可以對代碼進行取出、導入、更新、分支、還原、改名和合并等。

而SVN和Git一樣都有一個版本庫或服務器，被使用時是分布式模式，每個開發(fā)人員從中心版本庫或服務器上下載代碼到自己的機器，然后自己有專屬的版本庫，可以對這個版本庫進行開發(fā)管理。

2)SVN是按文件進行存儲，而Git是把內(nèi)容按元數(shù)據(jù)方式存儲。

3)SVN有一個全局的版本號，而Git沒有。

4)Git的內(nèi)容完整性比SVN完整。Git對內(nèi)容存儲主要使用的是SHA-1哈希算法，確保了代碼內(nèi)容的完整性，即使遇到硬盤或網(wǎng)絡故障對代碼的損害都可以降低。

5)在Git上的分支可以很快速地在工作目錄下和分支間進行切換，然后發(fā)現(xiàn)未合并的分支可以進行合并。而SVN的分支相當于版本庫中的另一個目錄，合并需要手動輸入命令完成。

使用Git的好處有代碼庫占的空間小，對程序源代碼進行差異化的版本管理，存在多個分支代碼開發(fā)等。

在提交代碼到Git中遇到?jīng)_突時，可以根據(jù)開發(fā)者的反饋進行判斷，如果是主開發(fā)者發(fā)現(xiàn)兩個開發(fā)者之間的沖突，那么可以讓他們白行解決沖突，讓其中一個人先提交代碼。如果是主開發(fā)者可以自己解決的問題，那么就自己解決沖突再上傳。

Git中主要使用的基本命令有：

1)通過Gitclone'版本庫地址'把項目復制到本地。

2)通過Gitadd.可以將代碼的修改全部修改提交到本地暫存區(qū)。

3)通過Gitcommit-m'注釋'使用commit命令提交添加到緩存區(qū)的文件到本地倉庫。

4)通過Gitpush將本地分支更新的部分推送到遠程主機上。四、編程題21、這道題的主要思路為，首先對請求按照R[i]-O[i]由大到小進行排序，然后按照由大到小的順序進行處理，如果按照這個順序能處理完，則這n個請求能被處理完，否則處理不完。那么請求i能完成的條件是什么呢?在處理請求i的時候前面所有的請求都已經(jīng)處理完成，那么它們所占的存儲空間為O[0]+O[1]+…+O[i-1]，剩余的存儲空間left為left=m-(O[0]+O[1]+…+O[i-1])，要使請求i能被處理完，則必須滿足left≥R[i]，只要剩余的存儲空間能存放R[i]，那么在請求處理完成后就可以刪除請求，從而把處理的結(jié)果放到存儲空間中，由于O[i]＜R[i]，此時必定有空間存放O[i]。

至于為什么用R[i]-O[i]由大到小的順序來處理，來看下面的分析：

假設第一步處理R[i]-O[i]最大的值。使用歸納法(假設每一步都取剩余請求中R[i]-O[i]最大的值進行處理)，假設n=k時能處理完成，那么當n=k+1時，由于前k個請求是按照R[i]-O[i]從大到小排序的，在處理第k+1個請求時，此時需要的空間為A=O[1]+…+O[i]+…+O[k]+R[k+1]，只有A≤m的時候才能處理第k+1個請求。假設把第k+1個請求和前面的某個請求i交換位置，即不按照R[i]-O[i]由大到小的順序來處理，在這種情況下，第k+1個請求已經(jīng)被處理完成，接著要處理第i的請求，此時需要的空間為B=O[1]+…+O[i-1]+O[k+1]+O[i+1]+…+R[i]，如果B＞A，則說明按順序處理成功的可能性更大(越往后處理剩余的空間越小，請求需要的空間越小越好)；如果B＜A，則說明不按順序更好。根據(jù)R[i]-O[i]有序的特點可知：R[i]-O[i]≥R[k+1]-O[k+1]，即O[k+1]+R[i]≥O[i]+R[k+1]，所以，B≥A，因此，可以得出結(jié)論：方案B不會比方案A更好。即方案A是最好的方案，也就是說，按照R[i]-O[i]從大到小排序處理請求，成功的可能性最大。如果按照這個序列都無法完成請求序列，那么任何順序都無法實現(xiàn)全部完成，實現(xiàn)代碼如下：

＜?php

functionswap(&$a,&$b)

{

$temp=$a;

$a

=$b;

$b

=$temp;

}

/*按照R[i]-O[i]由大到小進行排序*/

functionbubbleSort(&$R,&$O,$len)

{

for($i=0;$i＜$len-1;++$i)

{

for($j=$len-1;$j＞$i;--$j)

{

if($R[$j]-$O[$j]＞$R[$j-1]-$O[$j-1])

{

swap($R[$j],$R[$j-1]);

swap($O[$j],$O[$j-1]);

}

}

}

}

functionschedule(&$R,&$O,$len,$M)

{

bubbleSort($R,$O,$len);

$left=$M;//剩余可用的空間數(shù)

$i;

for($i=0;$i＜$len;$i++)

{

if($left＜$R[$i])

//剩余的空間無法繼續(xù)處理第i個請求

{

returnfalse;

}

else

//剩余的空間能繼續(xù)處理第i個請求，處理完成后將占用O[i]個空間

{

$left-=$O[$i];

}

}

returntrue;

}

$R=[10,15,23,20,6,9,7,16];

$O=[2,7,8,4,5,8,6,8];

$N=8;

$M=50;

$i;

$schedueResult=schedule($R,$O,$N,$M);

if($schedueResult)

{

printf("按照如下請求序列可以完成:\n");

for($i=0;$i＜$N;$i++)

{

printf("{%d,%d}",$R[$i],$O[$i]);

}

}

else

{

printf("無法完成調(diào)度\n");

}

?＞

程序的運行結(jié)果為

按照如下請求序列可以完成：{20,4}{23,8}{10,2}{15,7}{16,8}{6,5}{9,8}{7,6}

算法性能分析：這個算法的時間復雜度為O(N^2)。

22、方法1：

functiongetExt($url){

$arr=parse_url($url);

$file=basename($arr['path']);

$ext=explode(".",$file);

return$ext[1];

}

方法2：

functiongetExt($url){

$url=basename($url);

$pos1=strpos($url,".");

$pos2=strpos($url,"?");

if(strstr($url,"?”)){

returnsubstr($url,$pos1+1,$pos2-$pos1-1);

}else{

returnsubstr($url;$pos1);

}

}

23、最容易想到的辦法是申請一個額外的隊列，先把棧中的元素依次出棧放到隊列里，然后把隊列里的元素按照出隊列順序入棧，這樣就可以實現(xiàn)棧的翻轉(zhuǎn)，這種方法的缺點是需要申請額外的空間存儲隊列，因此，空間復雜度較高。下面介紹一種空間復雜度較低的遞歸的方法。

遞歸程序有兩個關鍵因素需要注意：遞歸定義和遞歸終止條件。經(jīng)過分析后，很容易得到該問題的遞歸定義和遞歸終止條件。遞歸定義：將當前棧的最底元素移到棧頂，其他元素順次下移一位，然后對不包含棧頂元素的子棧進行同樣的操作。終止條件：遞歸下去，直到棧為空。遞歸的調(diào)用過程如下圖所示。

在上圖中，對于棧(1，2，3，4，5)進行翻轉(zhuǎn)的操作：首先把棧底元素移動到棧頂?shù)玫綏?5，1，2，3，4)，然后對不包含棧頂元素的子棧進行遞歸調(diào)用(對子棧元素進行翻轉(zhuǎn))，子棧(1，2，3，4)翻轉(zhuǎn)的結(jié)果為(4，3，2，1)，因此，最終得到翻轉(zhuǎn)后的棧為(5，4，3，2，1)。

此外，由于棧的后進先出的特點，使得只能取棧頂?shù)脑?，因此，要把棧底的元素移動到棧頂也需要遞歸調(diào)用才能完成，主要思路：把不包含該棧頂元素的子棧棧底的元素移動到子棧的棧頂，然后把棧頂?shù)脑嘏c子棧棧頂?shù)脑?其實就是與棧頂相鄰的元素)進行交換，如下圖所示。

為了容易理解遞歸調(diào)用，可以認為在進行遞歸調(diào)用的時候，子棧已經(jīng)實現(xiàn)了把棧底元素移動到了棧項，在上圖中為了把棧(1，2，3，4，5)的棧底元素5移動到棧頂，首先對子棧(2，3，4，5)進行遞歸調(diào)用，調(diào)用的結(jié)果為(5，2，3，4)，然后對子棧頂元素5，與棧頂元素1進行交換，得到棧(5，1，2，3，4)，實現(xiàn)了把棧底元素移動到了棧頂。

示例代碼如下：

＜?php

header("content-type:text/html;charset=utf-8");

classLNode{

public$mElem;

public$mNext;

publicfunction__construct(){

$this-＞mElem=NULL;

$this-＞mNext=NULL;

}

}

classStackLinked{

//頭“指針”，指向棧頂元素

public$mNext;

publicstatic$mLength;

/**

*初始化棧

*

*@returnvoid

*/

publicfunction__construct(){

$this-＞mNext=NULL;

self::$mLength=0;

}

/**

*判斷棧是否空棧

*

*@returnboolean如果為空棧返回true，否則返回false

*/

publicfunctiongetIsEmpty(){

if($this-＞mNext==NULL){

returntrue;

}else{

returnfalse;

}

}

/**

*將所有元素出棧

*

*@returnarray返回所有棧內(nèi)元素

*/

publicfunctiongetAllPopStack(){

$e=array();

if(!$this-＞getIsEmpty()){

while($this-＞mNext!=NULL){

$e[]=$this-＞mNext-＞mElem;

$this-＞mNext=$this-＞mNext-＞mNext;

}

}

self::$mLength=0;

return$e;

}

/**

*返回棧內(nèi)元素個數(shù)

*

*@returnint

*/

publicstaticfunctiongetLength(){

returnself::$mLength;

}

/**

*元素進棧

*

*@parammixed$e進棧元素值

*@returnboolean進棧成功返回true

**/

publicfunctionpush($e){

$newLn=newLNode();

$newLn-＞mElem=$e;

$newLn-＞mNext=$this-＞mNext;

$this-＞mNext=&$newLn;

self:;$mLength++;

returntrue;

}

/**

*元素出棧

*

*@returnboolean出棧成功返回true，否則返回false

**/

publicfunctionpop(){

if($this-＞getIsEmpty()){

returnfalse;

}

$p=$this-＞mNext;

$e=$p-＞mElem;

$this-＞mNext=$p-＞mNext;

self::$mLength--;

returntrue;

}

/**

*返回棧內(nèi)所有元素

*

*@returnarray棧內(nèi)所有元素組成的一個數(shù)組

*/

publicfunctiongetAllElem(){

$sldata=array();