前端程序員面試分類真題21簡答題1.

給定一個沒有排序的鏈表，去掉其重復(fù)項，并保留原順序，例如鏈表1-＞3-＞1-＞5-＞5-＞7，去掉重復(fù)項后變?yōu)?-＞3-＞5-＞7。正確答案：通過雙重循環(huán)直接（江南博哥）在鏈表上進(jìn)行刪除操作。外層循環(huán)用一個指針從第一個結(jié)點開始遍歷整個鏈表，然后內(nèi)層循環(huán)用另外一個指針遍歷其余結(jié)點，將與外層循環(huán)遍歷到的指針?biāo)附Y(jié)點的數(shù)據(jù)域相同的結(jié)點刪除，如下圖所示。

雙重循環(huán)的刪除演示

假設(shè)外層循環(huán)從outerCur開始遍歷，當(dāng)內(nèi)層循環(huán)指針innerCur遍歷到上圖虛線所框的位置(outerCur.data==innerCur.data)時，需要把innerCur指向的結(jié)點刪除。具體步驟如下：

(1)用tmp記錄待刪除結(jié)點的地址。

(2)為了能夠在刪除tmp結(jié)點后繼續(xù)遍歷鏈表中其余的結(jié)點，使innerCur指向它的后繼結(jié)點：innerCur=innerCur.next。

(3)從鏈表中刪除tmp結(jié)點。

實現(xiàn)代碼如下所示。

//鏈表結(jié)點

functionnode(id,data){

this.id=id;

//結(jié)點id

this.data=data;

//結(jié)點數(shù)據(jù)

this.next=null;

//下一結(jié)點

}

//單鏈表

functionlinkList(id,data){

this.header=newnode(id,data);

//鏈表頭結(jié)點

}

linkLtotype={

addLink:function(node){

//添加結(jié)點數(shù)據(jù)

varcurrent=this.header;

while(current.next!=null){

if(current.next,id＞node.id){

break;

}

current=current.next;

}

node.next=current.next;

current.next=node;

},

clear:function(){

//清空鏈表

this.header=null;

},

getLinkList:function(){

//獲取鏈表

varcurrent=this.header;

if(current,next==null){

console.log("鏈表為空");

return;

}

vartxt="";

while(current.next!=null){

txt+=current.next.data+"";

if(current.next.next==null){

break;

}

current=current.next;

}

console.log(txt);

},

removeDup:function(){

//刪除帶頭結(jié)點的無序單鏈表中重復(fù)的結(jié)點

varhead=this.header;

if(head==null||head.next==null)

return;

varouterCur=head.next,

//外層循環(huán)指針,指向鏈表的第一個結(jié)點

innerCur=null,

//內(nèi)層循環(huán)用來遍歷ourterCur后面的結(jié)點

innerPre=null,

//innerCur的前驅(qū)結(jié)點

tmp=null;

//用來指向被刪除結(jié)點的指針

for(;outerCur!=null;outerCur=outerCur.next){

for(innerCur=outerCur.next,innerPre=outerCur;innerCur!=null;){

//找到重復(fù)的結(jié)點并刪除

if(outerCur.data==innerCur.data){

tmp=innerCur;

innerPre.next=innerCur.next;

innerCur=innerCur.next;

}else{

innerPre=innerCur;

innerCur=innerCur.next;

}

}

}

}

};

varlists=newlinkList();

lists.addLink(newnode(1,1));

lists.addLink(newnode(2,3));

lists.addLink(newnode(3,1));

lists.addLink(newnode(4,5));

lists.addLink(newnode(5,5));

lists.addLink(newnode(6,7));

console.log("刪除重復(fù)結(jié)點前:");

Iists.getLinkList();

//131557

console.log("刪除重復(fù)結(jié)點后:");

lists.removeDup();

lists.getLinkList();

//1357

//釋放鏈表所占的空間

lists.clear();[考點]鏈表

2.

給定兩個單鏈表，鏈表的每個結(jié)點代表一位數(shù)，計算兩個數(shù)的和。例如：輸入鏈表(3-＞1-＞5)和鏈表(5-＞9-＞2)，輸出：8-＞0-＞8，即513+295=808，注意個位數(shù)在鏈表頭。正確答案：對鏈表中的結(jié)點直接進(jìn)行相加操作，把和存儲到新的鏈表對應(yīng)的結(jié)點中，同時還要記錄結(jié)點相加后的進(jìn)位，如下圖所示。

結(jié)點相加

使用這個方法需要注意如下幾個問題：①每組結(jié)點進(jìn)行相加后需要記錄其是否有進(jìn)位；②如果兩個鏈表H1與H2的長度不同(長度分別為L1和L2，且L1＜L2)，當(dāng)對鏈表的第L1位計算完成后，接下來只需要考慮鏈表L2剩余的結(jié)點值(需要考慮進(jìn)位)；③對鏈表所有結(jié)點都完成計算后，還需要考慮此時是否還有進(jìn)位，如果有進(jìn)位，則需要增加新的結(jié)點，此結(jié)點的數(shù)據(jù)域為1。實現(xiàn)代碼如下所示。

//鏈表結(jié)點

functionnode(id,name){

this.id=id;

//結(jié)點id

=name;

//結(jié)點名稱

this.next=null;

//下一結(jié)點

}

//單鏈表

functionlinkList(id,name){

this.header=newnode(id,name);

//鏈表頭結(jié)點

}

linkLtotype={

addLink:function(node){

//添加結(jié)點數(shù)據(jù)

varcurrent=this.header;

while(current.next!=null){

if(current.next.id＞node.id){

break;

}

current=current.next;

}

node.next=current.next;

current.next=node;

},

clear:function(){

//清空鏈表

this.header=null;

},

getLinkList:function(){

//獲取鏈表

varcurrent=this.header;

if(current.next==null){

console.log("鏈表為空");

return;

}

vartxt="";

while(current.next!=null){

txt+=+"";

if(current.next.next==null){

break;

}

current=current.next;

}

console.log(txt);

}

};

/*

**函數(shù)功能:兩個帶頭結(jié)點的單鏈表所代表的數(shù)相加

**輸入?yún)?shù):h1:第一個鏈表;h2:第二個鏈表

**返回值:相加后鏈表的頭結(jié)點

*/

functionadd(h1,h2){

h1=h1.header;

h2=h2.header;

if(h1==null||h1.next==null)

returnh2;

if(h2=null||h2.next==null)

returnh1;

varc=0,//用來記錄進(jìn)位

sum=0,

//用來記錄兩個結(jié)點相加的值

p1=h1.next,

//用來遍歷h1

p2=h2.next,

//用來遍歷h2

tmp=null,

//用來指向新創(chuàng)建的存儲相加和的結(jié)點

resultHead=newlinkList(),

//相加后鏈表頭結(jié)點

p=resultHead;

//用來指向鏈表resultHead最后一個結(jié)點

while(p1&&p2){

tmp=newlinkList();

sum=++c;

tmp,=sum%10;

//兩結(jié)點相加和

c=Math.floor(sum/10);

//進(jìn)位

p.header.next=tmp;

p=tmp;

p1=p1.next;

p2=p2.next;

}

//鏈表h2比h1長,接下來只需要考慮h2剩余結(jié)點的值

if(p1==null){

while(p2){

tmp=newlinkList();

sum=+c;

=sum%10;

c=Math.floor(sum/10);

p.header.next=tmp;

p=tmp;

p2=p2.next;

}

}

//鏈表h1比h2長,接下來只需要考慮h1剩余結(jié)點的值

if(p2==null){

while(p1){

tmp=newlinkList();

sum=+c;

=sum%10;

c=Math.floor(sum/10);

p.header.next=tmp;

p=tmp;

p1=p1.next;

}

}

//如果計算完成后還有進(jìn)位,則增加新的結(jié)點

if(c==1){

tmp=newlinkList();

=1;

p.header.next=tmp;

}

returnresultHead;

}

varhead1=newlinkList(),

head2=newlinkList();

for(vari=1;i＜7;1++){

head1.addLink(newnode(i,i+2));

}

varnum=0;

for(i=9;i＞4;1--){

head2.addLink(newnode(num,i));

num++;

}

console.log("Head1:");

head1.getLinkList();

//345678

console.log("Head2;");

head2.getLinkList();

//98765

console.log("相加后:");

varaddResult=add(head1,head2),

txt="";

while(addResult!=null){

if(addR)

txt+=addR+"";

addResult=addResult.header.next;

}

console.log(txt);

//233339

//釋放鏈表所占的空間

head1.clear();

head2.clear();[考點]鏈表

3.

給定鏈表L0-＞L1-＞L2-＞…-＞Ln-1-＞Ln，把鏈表重新排序為L0-＞Ln-＞L1-＞Ln-1-＞L2-＞Ln-2-＞…。要求：①在原來鏈表的基礎(chǔ)上進(jìn)行排序，即不能申請新的結(jié)點；②只能修改結(jié)點的next域，不能修改數(shù)據(jù)域。正確答案：主要思路如下所列：

(1)找到鏈表的中間結(jié)點。

(2)對鏈表的后半部分子鏈表進(jìn)行逆序。

(3)把鏈表的前半部分子鏈表與逆序后的后半部分子鏈表進(jìn)行合并，合并的思路為從兩個鏈表中各取一個結(jié)點進(jìn)行合并。實現(xiàn)方法如下圖所示。

重新排序思路

實現(xiàn)代碼如下所示。

//鏈表結(jié)點

functionnode(id,data){

this.id=id;

//結(jié)點id

this.data=data;

//結(jié)點數(shù)據(jù)

this.next=null;

//下一結(jié)點

}

//單鏈表

functionlinkList(id,data){

this.header=newnode(id,data);

//鏈表頭結(jié)點

}

linkLtotype={

addLink:function(node){

//添加結(jié)點數(shù)據(jù)

varcurrent=this.header;

while(current.next!=null){

if(current.next.id＞node.id){

break;

}

current=current.next;

}

node.next=current,next;

current,next=node;

},

clear:function(){

//清空鏈表

this.header=null;

},

getLinkList:function(){

//獲取鏈表

varcurrent=this.header;

if(current.next==null){

console.log("鏈表為空");

return;

}

vartxt="";

while(current.next!=null){

txt+=current.next.data+"";

if(current.next.next==null){

break;

}

current=current.next;

}

console.log(txt);

},

/*

**函數(shù)功能:找出鏈表的中間結(jié)點,把鏈表從中間分成兩個子鏈表

**輸入?yún)?shù):head,鏈表頭結(jié)點

**返回值:指向鏈表中間結(jié)點的指針

*/

FindMiddleNode:function(head){

if(head==null||head.next==null)

returnhead;

varfast=head,

//快指針每次走兩步

slow=head,

//慢指針每次走一步

slowPre=head;

//當(dāng)fast到鏈表尾部時,slow恰好指向鏈表的中間結(jié)點

while(fast!=null&&fast.next!=null){

slowPre=slow;

slow=slow.next;

fast=fast.next.next;

}

//把鏈表分成兩個獨立的子鏈表

slowPre.next=null;

returnslow;

},

/*

**函數(shù)功能:對不帶頭結(jié)點的單鏈表進(jìn)行翻轉(zhuǎn)

**輸入?yún)?shù):head,指向鏈表頭結(jié)點

*/

Reverse:function(head){

if(head==null||head.next==null)

returnhead;

varpre=head,

//前驅(qū)結(jié)點

cur=head.next,

//當(dāng)前結(jié)點

next=cur.next;

//后繼結(jié)點

pre.next=null;

//使當(dāng)前遍歷到的結(jié)點cur指向其前驅(qū)結(jié)點

while(cur!=null){

next=cur.next;

cur.next=pre;

pre=cur;

cur=cur.next;

cur=next;

}

returnpre;

},

/*

**函數(shù)功能:對鏈表進(jìn)行排序

*/

Reorder:function(){

varhead=this.header;

//指向鏈表頭結(jié)點

if(head==null||head.next==null)

return;

varcur1=head.next,

//前半部分鏈表的第一個結(jié)點

mid=this.FindMiddleNode(head.next),

cur2=this.Reverse(mid),

//后半部分鏈表逆序后的第一個結(jié)點

tmp=null;

//合并兩個鏈表

while(cur1.next!=null){

tmp=cur1.next;

cur1.next=cur2;

cur1=tmp;

tmp=cur2.next;

cur2.next=cur1;

cur2=tmp;

}

cur1.next=cur2;

}

};

varlists=newlinkList();

for(vari=1;i＜8;i++){

lists.addLink(newnode(i,i));

}

console.log("排序前:");

lists.getLinkList();

//1234567

lists.Reorder();

console.log("排序后:");

lists.getLinkList();

//1726354

//釋放鏈表所占的空間

lists.clear();[考點]鏈表

4.

找出單鏈表中的倒數(shù)第k個元素，例如給定單鏈表：1-＞2-＞3-＞4-＞5-＞6-＞7，則單鏈表的倒數(shù)第3(即k=3)個元素為5。正確答案：由于單鏈表只能從頭到尾依次訪問鏈表的各個結(jié)點，所以，如果要找鏈表的倒數(shù)第k個元素，也只能從頭到尾進(jìn)行遍歷查找。在查找過程中，設(shè)置兩個指針，讓其中一個指針比另一個指針先前移k步，然后兩個指針同時往前移動。循環(huán)到先行的指針值為null時，另一個指針?biāo)傅奈恢镁褪撬业奈恢谩３绦虼a如下所示。

//鏈表結(jié)點

functionnode(id,data){

this.id=id;

//結(jié)點id

this.data=data;

//結(jié)點數(shù)據(jù)

this.next=null;

//下一結(jié)點

}

//單鏈表

functionlinkList(id,data){

this.header=newnode(id,data);

//鏈表頭結(jié)點

}

linkLtotype={

addLink:function(node){

//添加結(jié)點數(shù)據(jù)

varcurrent=this.header;

while(current.next!=null){

if(current.next.id＞node.id){

break;

}

current=current.next;

}

node.next=current.next;

current.next=node;

},

clear:function(){

//清空鏈表

this.header=null;

},

getLinkList:function(){

//獲取鏈表

varcurrent=this.header;

if(current.next==null){

console.log("鏈表為空");

return;

}

vartxt="";

while(current.next!=null){

txt+=current.next.data+"";

if(current.next,next==null){

break;

}

current=current.next;

}

console.log(txt);

},

FindLastK:function(k){

//找出鏈表倒數(shù)第k個結(jié)點

varhead=this.header;

if(head==null||head.next==null)

returnhead;

varslow=null,

fast=null;

slow=fast=head.next;

for(vari=0;i＜k&&fast;++i){

//前移k步

fast=fast.next;

}

//判斷k是否已超出鏈表長度

if(i＜k)

returnnull;

while(fast!=null){

slow=slow.next;

fast=fast.next;

}

returnslow;

}

};

varlists=newlinkList();

for(vari=1;i＜8;i++){

lists.addLink(newnode(i,i));

}

console.log("鏈表:");

lists.getLinkList();

//1234567

console.log("鏈表倒數(shù)第3個元素為:");

varresult=lists.FindLastK(3);

console.log(result.data);

//5

//釋放鏈表所占的空間

lists.clear();[考點]鏈表

5.

隊列和棧有什么區(qū)別?正確答案：棧與隊列是在程序設(shè)計中被廣泛使用的兩種重要的線性數(shù)據(jù)結(jié)構(gòu)，它們都是在一個特定范圍的存儲單元中存儲的數(shù)據(jù)，這些數(shù)據(jù)都可以重新被取出使用。與線性表相比，它們的插入和刪除操作受到了更多的約束和限定，故又被稱為限定性的線性表結(jié)構(gòu)。兩者不同的是，棧就像一個很窄的桶，先存進(jìn)去的數(shù)據(jù)只能最后被取出來，是LIFO(LastInFirstOut，后進(jìn)先出)，它將進(jìn)出順序逆序，即先進(jìn)后出，后進(jìn)先出，棧結(jié)構(gòu)如下圖1所示。隊列像日常排隊買東西的人的“隊列”，先排隊的人先買，后排隊的人后買，是FIFO(FirstInFirstOut，先進(jìn)先出)，它保持進(jìn)出順序一致，即先進(jìn)先出，后進(jìn)后出，隊列結(jié)構(gòu)如下圖2所示。

圖1棧結(jié)構(gòu)示意圖

圖2隊列結(jié)構(gòu)示意圖

需要注意的是，有時在數(shù)據(jù)結(jié)構(gòu)中還有可能出現(xiàn)按照大小排隊或按照一定條件排隊的數(shù)據(jù)隊列，這時的隊列屬于特殊隊列，就不一定按照“先進(jìn)先出”的原則讀取數(shù)據(jù)了。[考點]棧和隊列

6.

實現(xiàn)一個棧的數(shù)據(jù)結(jié)構(gòu)，使其具有以下方法：壓棧、彈棧、取棧頂元素、判斷棧是否為空以及獲取棧中元素個數(shù)。正確答案：在采用數(shù)組來實現(xiàn)棧的時候，主要面臨的問題是給數(shù)組申請多大的存儲空間比較合理，因為在使用棧的時候并不確定以后棧中需要存放的數(shù)據(jù)元素的個數(shù)，申請多了會造成空間的浪費，而申請少了則會導(dǎo)致不夠用。為了便于理解，這里采用的方法是給定一個初始值，假如這個值是10，那么就先申請能存儲10個元素的數(shù)組作為棧的存儲空間。在后期使用的過程中如果空間不夠用了，再擴(kuò)大這個空間。實現(xiàn)思路如下圖所示。

數(shù)組模擬的棧結(jié)構(gòu)

從圖中能夠看出，可以把數(shù)組的首地址當(dāng)作棧底，同時記錄棧中元素的個數(shù)size，可見，根據(jù)棧底指針和size就可以計算出棧頂?shù)牡刂妨恕＜僭O(shè)數(shù)組首地址為arr，從圖中可以看出，壓棧的操作其實是把待壓棧的元素放到數(shù)組Arr[size]中，然后執(zhí)行size++操作；同理，彈棧操作其實是取數(shù)組中的Arr[size-1]元素，然后執(zhí)行size--操作。根據(jù)這個原理可以非常容易地實現(xiàn)棧，示例代碼如下所示。

//創(chuàng)建一個空數(shù)組作為棧

varstack=[];

//獲取棧頂元素

functiongetTop(stack){

returnstack[stack.length-1];

}

//向數(shù)組壓入一個元素

stack.push(1);

stack.push(2);

//輸出棧頂元素

console.log(getTop(stack));

//2

//讓棧頂元素出棧

stack.pop();

console.log(getTop(stack));

//1[考點]棧和隊列

7.

實現(xiàn)一個隊列的數(shù)據(jù)結(jié)構(gòu)，使其具有入隊列、出隊列、查看隊列首尾元素、查看隊列大小等功能。正確答案：下圖給出了一種最簡單的實現(xiàn)方式，用front來記錄隊列首元素的位置，用rear來記錄隊列尾元素往后一個位置。入隊列的時候只需要將待入隊列的元素放到數(shù)組下標(biāo)為rear的位置，同時rear++，出隊列的時候只需要執(zhí)行front++即可。

數(shù)組模擬的隊列結(jié)構(gòu)

為了簡化實現(xiàn)過程，下面代碼定義的隊列最大的空間為10，實現(xiàn)代碼如下所示。

functionqueue(){

this.queueList=[];

this.size=0;

}

totype={

enQueue:function(data){

//入隊操作

this.queueList[this.size++]=data;

returnthis;

},

outQueue:function(){

//出隊操作

if(!this.isEmpty()){

--this.size;

varfront=this.queueList.splice(0,1);

returnfront[0];

}

returnfalse;

},

getQueue:function(){

//獲取隊列

returnthis.queueList;

},

getFront:function(){

//獲取隊頭元素

if(!this.isEmpty()){

returnthis.queueList[0];

}

returnfalse;

},

getRear:function(){

//獲取隊尾元素

if(!this.isEmpty()){

varlen=this.queueList.length;

returnthis.queueList[len-1];

}

returnfalse;

},

getSize:function(){

//獲取隊列的長度

returnthis.size;

},

isEmpty:function(){

//檢測隊列是否為空

return()===this.size;

}

};

varqueue=newqueue();

queue.enQueue(1);

queue.enQueue(2);

console.log("隊列頭元素為:",queue.getFront());

//1

console.log("隊列尾元素為:",queue.getRear());

//2

console.log("隊列大小為:",queue.getSize());

//2[考點]棧和隊列

8.

翻轉(zhuǎn)(也叫顛倒)棧的所有元素，例如輸入棧{1,2,3,4,5}，其中，1在棧頂，翻轉(zhuǎn)之后的棧為{5,4,3,2,1}，其中，5在棧項。正確答案：最容易想到的辦法是申請一個額外的隊列，先把棧中的元素依次出棧放到隊列里，然后把隊列里的元素按照出隊列的順序入棧，這樣就可以實現(xiàn)棧的翻轉(zhuǎn)，這種方法的缺點是需要申請額外的空間存儲隊列，因此，空間復(fù)雜度較高。下面介紹一種空間復(fù)雜度較低的遞歸方法。

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

圖1翻轉(zhuǎn)棧的遞歸過程

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

此外，由于棧的后進(jìn)先出的特點，使得只能取棧頂?shù)脑亍Ｒ虼耍褩５椎脑匾苿拥綏ｍ斠残枰f歸調(diào)用才能完成，主要思路為：把不包含該棧頂元素的子棧棧底元素移動到子棧的棧頂，然后把棧頂?shù)脑嘏c子棧棧頂?shù)脑?其實就是與棧頂相鄰的元素)進(jìn)行交換。

圖2子棧的遞歸過程

為了容易理解遞歸調(diào)用，可以認(rèn)為在進(jìn)行遞歸調(diào)用的時候，子棧已經(jīng)實現(xiàn)把棧底元素移動到棧頂。在圖2中為了把棧{1,2,3,4,5}的棧底元素5移動到棧頂，首先對子棧{2,3,4,5}進(jìn)行遞歸調(diào)用，調(diào)用的結(jié)果為{5,2,3,4}，然后將子棧棧頂元素5與棧頂元素1進(jìn)行交換得到棧{5,1,2,3,4}，從而把棧底元素移動到了棧頂。示例代碼如下。

functionLNode(){

this.mElem=null;

this.mNext=null;

}

functionStackLinked(){

this.mNext=null;

//頭"指針",指向棧頂元素

this.mLength=0;

//棧內(nèi)元素個數(shù)

}

StackLtotype={

/**

*判斷棧是否為空棧

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

*/

getlsEmpty:function(){

returnthis.mNext==null;

},

/**

*將所有元素出棧

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

*/

getAllPopStack:function(){

vare=[];

if(!this.getIsEmpty()){

while(this.mNext!=null){

e.push(this.mNext.mElem);

this.mNext=this.mNext.mNext;

}

}

this.mLength=0;

returne;

},

/**

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

*@returnint

*/

getLength:function(){

returnthis.mLength;

},

/**

*元素入棧

*@parammixede入棧元素值

*@returnvoid

*/

push:function(e){

varnewLn=newLNode();

newLn.mElem=e;

newLn.mNext=this.mNext;

this.mNext=newLn;

this,mLength++;

},

/**

*元素出棧

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

*/

pop:function(){

if(this.getIsEmpty()){

returnfalse;

}

varp=this.mNext,

e=p,mElem;

this.mNext=p.mNext;

this.mLength--;

returntrue;

},

/**

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

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

*/

getAllElem:function(){

varsldata=[],

p;

if(!this.getlsEmpty()){

p=this,mNext;

while(p!=null){

sldata.push(p.mElem);

p=p.mNext;

}

}

returnsldata;

},

/**

*返回棧頂元素

*@returnelement返回棧頂元素

*/

top:function(){

if(this.getIsEmpty()){

returnfalse;

}

varlist=this.getAllElem();

returnlist[0];

},

/**

*把棧底元素移動到棧頂

*/

move_bottom_to_top:function(){

if(this,getIsEmpty())

return;

vartop1=this.top(),

top2;

this.pop();

//彈出棧頂元素

if(!this.getIsEmpty()){

//遞歸處理不包含棧頂元素的子棧

this.move_bottom_to_top();

top2=this.top();

this.pop();

//交換棧項元素與子棧棧頂元素

this.push(top1);

this.push(top2);

}else{

this.push(top1);

}

},

/**

*翻轉(zhuǎn)棧

*/

reverse_stack:function(){

if(this.getIsEmpty())

return;

//把棧底元素移動到棧頂

this.move_bottom_to_top();

vartop=this.top();

this.pop();

//遞歸處理子棧

this.reverse_stack();

this.push(top);

}

};

varstack=newStackLinked();

stack.push('5');

stack.push('4');

stack.push('3');

stack.push('2');

stack.push('1');

stack.reverse_stack();

console.log("翻轉(zhuǎn)后的出棧順序為:");

vartxt="";

while(!stack.getIsEmpty()){

txt+=stack.top()+"";

stack.pop();

}

console.log(txt);

//54321[考點]棧和隊列

9.

輸入兩個整數(shù)序列，其中一個序列表示棧的push(入)順序，判斷另一個序列有沒有可能是對應(yīng)的pop(出)順序。正確答案：假如輸入的push序列是1、2、3、4、5，那么3、2、5、4、1就有可能是一個pop序列，但5、3、4、1、2就不可能是它的一個pop序列。

主要思路是使用一個棧來模擬入棧順序，具體步驟如下：

(1)把push序列依次入棧，直到棧頂元素等于pop序列的第一個元素，然后棧頂元素出棧，pop序列移動到第二個元素。

(2)如果棧頂繼續(xù)等于pop序列現(xiàn)在的元素，則繼續(xù)出棧并將pop序列后移；否則對push序列繼續(xù)入棧。

(3)如果push序列已經(jīng)全部入棧，但是pop序列未全部遍歷，而且棧頂元素不等于當(dāng)前pop元素，那么這個序列不是一個可能的出棧序列。如果棧為空，而且pop序列也全部被遍歷過，則說明這是一個可能的pop序列。下圖給出一個合理的pop序列判斷過程。

pop序列的判斷過程

在圖中，(1)～(3)三步，由于棧頂元素不等于pop序列的第一個元素3，因此，1、2、3依次入棧；當(dāng)3入棧后，棧頂元素等于pop序列的第一個元素3，因此，第(4)步執(zhí)行3出棧；然后指向pop序列的第二個元素2，且棧頂元素等于pop序列的當(dāng)前元素，因此，第(5)步執(zhí)行2出棧；再接著由于棧頂元素4不等于當(dāng)前pop序列5，因此，接下來的(6)和(7)兩步分別執(zhí)行4和5入棧；緊接著由于棧頂元素5等于pop序列的當(dāng)前值，因此，第(8)步執(zhí)行5出棧；接下來(9)和(10)兩步棧頂元素都等于當(dāng)前pop序列的元素，因此，都執(zhí)行出棧操作；最后棧為空，同時pop序列都完成了遍歷，說明{3,2,5,4,1}是一個合理的出棧序列。實現(xiàn)代碼如下所示。

functionLNode(){

this.mElem=null;

this.mNext=null;

}

functionStackLinked(){

this.mNext=null;

//頭"指針",指向棧頂元素

this.mLength=0;

//棧內(nèi)元素個數(shù)

}

StackLtotype={

/**

*判斷棧是否為空棧

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

*/

getIsEmpty:function(){

returnthis.mNext==null;

},

***

*將所有元素出棧

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

*/

getAllPopStack:function(){

vare=[];

if(!this.getIsEmpty()){

while(this.mNext!=null){

e.push(this.mNext.mElem);

this.mNext=this.mNext.mNext;

}

}

this,mLength=0;

returne;

},

/**

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

*@returnint

*/

getLength:function(){

returnthis.mLength;

},

/**

*元素入棧

*@parammixede入棧元素值

*@returnvoid

*/

push:function(e){

varnewLn=newLNode();

newLn.mElem=e;

newLn.mNext=this.mNext;

this.mNext=newLn;

this.niLength++;

},

/**

*元素出棧

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

*/

pop:function()(

if(this.getIsEmpty()){

returnfalse;

}

varp=this.mNext,

e=p.mElem;

this.mNext=p.mNext;

this.mLength--;

returntrue;

},

/**

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

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

*/

getAllElem:function(){

varsldata=[],

p;

if(!this.getIsEmpty())

{

p=this.mNext;

while(p!=null){

sldata.push(p.mElem);

p=p.mNext;

}

}

returnsldata;

},

/**

*返回棧頂元素

*@returnelement返回棧頂元素

*/

top:function(){

if(this.getIsEmpty()){

returnfalse;

}

varlist=this.getAllElem();

returnlist[0];

}

};

/**

*根據(jù)入棧序列判斷出棧后和另一個的出棧序列是否相等

*/

functionisPopSerial(push,pop){

if(push.getIsEmpty()||pop.getIsEmpty())

returnfalse;

varpushLen=push,getLength(),

popLen=pop.getLength();

if(pushLen!=popLen)

returnfalse;

varpushIndex=0,

popIndex=0,

stack=newStackLinked(),

pushList=push.getAllElem(),

popList=pop.getAllElem();

while(pushIndex＜pushLen){

//把push序列依次入棧,直到棧頂元素等于pop序列的第一個元素

stack.push(pushList[pushIndex]);

pushIndex++;

//棧頂元素出棧,pop序列移動到下一個元素

while(!stack.getIsEmpty()&&stack.top()==popList[popIndex]){

stack.pop();

popIndex++;

}

}

//棧為空,且pop序列中元素都被遍歷過

returnstack.getIsEmpty()&&popIndex==popLen;

}

varstackPUSH=newStackLinked(),

stackPOP=newStackLinked(),

push=";

for(vari=1;i＜=5;1++){

stackPUSH.push(i);

push+=i;

}

stackPOP.push(5);

stackPOP.push(2);

stackPOP.push(1);

stackPOP.push(4);

stackPOP.push(3);

console.log(isPopSerial(stackPUSH,stackPOP));

//true[考點]棧和隊列

10.

如何用O(l)的時間復(fù)雜度求棧中最小元素?正確答案：由于棧具有后進(jìn)先出的特點，因此，push和pop只能對棧頂元素進(jìn)行操作。可以用另外一個變量來記錄棧底的位置，通過遍歷棧中所有的元素找出最小值，但是這種方法的時間復(fù)雜度為O(N)。那么如何才能用O(l)的時間復(fù)雜度求出棧中最小的元素呢?

在算法設(shè)計中，經(jīng)常會采用空間換取時間的方式來降低時間復(fù)雜度，也就是說采用額外的存儲空間來降低操作的時間復(fù)雜度。具體而言，在實現(xiàn)的時候使用兩個棧結(jié)構(gòu)，一個棧用來存儲數(shù)據(jù)，另外一個棧用來存儲棧的最小元素。實現(xiàn)思路如下：如果當(dāng)前入棧的元素比原來棧中的最小值還小，則把這個值壓入保存最小元素的棧中；在出棧的時候，如果當(dāng)前出棧的元素恰好為當(dāng)前棧中的最小值，保存最小值的棧頂元素也出棧，使得當(dāng)前最小值變?yōu)楫?dāng)前最小值入棧之前的那個最小值。為了簡單化，可以在棧中保存整數(shù)類型。代碼實現(xiàn)如下所示。

functionNode(){

this.data=null;

this.min=null;

}

functionMin_Stack(a){

var_this=this;

this.data=[];

this.top=0;

a.forEach(function(value,key){

_this.push(value);

});

}

Min_Stotype={

push:function(i){

varnode=newNode();

node.data=i;

/**

*此處設(shè)置每個節(jié)點的min值,設(shè)置方法為,若棧為空,

*當(dāng)前元素data則為當(dāng)前節(jié)點的min,

*若棧非空,則當(dāng)前元素data與前一個節(jié)點的min值比較,

*取其小者作為當(dāng)前節(jié)點的min。

*/

if(this.top==0){

min=node.data;

}else{

min=this.data[this.top-1].min＜node.data?

this.data[this.top-1].min:

node.data;

}

node.min=min;

this.data.push(node);

this.top++;

returnnode;

},

pop:function(){

varr=this.data[--this.top];

this.data.splice(this.top,1);

returnr;

},

get_min:function(){

returnthis.data[this.top-1].min;

}

};

vara=[5],

min_stack=newMin_Stack(a);

console.log("棧中最小值為:",min_stack.get_min());

//5

min_stack.push(6);

console.log("棧中最小值為:",min_stack.get_min());

//5

min_stack.push(2);

console.log("棧中最小值為:",min_stack.get_min());

//2

min_stack.pop();

console.log("棧中最小值為:",min_stack.get_min());

//5[考點]棧和隊列

11.

如何用兩個棧模擬隊列操作?正確答案：題目要求用兩個棧來模擬隊列，假設(shè)使用棧A與棧B模擬隊列Q，其中A為插入棧，B為彈出棧。再假設(shè)A和B都為空，可以認(rèn)為棧A提供入隊列的功能，棧B提供出隊列的功能。

要入隊列，入棧A即可，而出隊列則需要分兩種情況考慮：

(1)如果棧B不為空，則直接彈出棧B的數(shù)據(jù)。

(2)如果棧B為空，則依次彈出棧A的數(shù)據(jù)，放入棧B中，再彈出棧B的數(shù)據(jù)。

代碼實現(xiàn)如下所示。

vararr1=[],

//棧A

arr2=[];

//棧B

functionpush(node){

arr1.push(node);

}

functionpop(){

if(arr2.length＞0){

returnarr2.pop();

}

while(arr1.length＞0){

arr2.push(arr1.pop());

}

returnarr2.pop();

}

push(1);

push(2);

console.log("隊列首元素為:",pop());//1

console.log("隊列首元素為:",pop());//2[考點]棧和隊列

12.

什么叫二叉樹?正確答案：二叉樹(BinaryTree)也稱為二分樹、二元樹或?qū)Ψ謽涞龋莕(n≥0)個有限元素的集合，該集合或者為空、或者由一個稱為根(root)的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當(dāng)集合為空時，稱該二叉樹為空二叉樹。

在二叉樹中，一個元素也稱作一個結(jié)點。二叉樹的遞歸定義為：二叉樹或者是一棵空樹，或者是一棵由一個根結(jié)點和兩棵互不相交的分別稱作根結(jié)點的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是一棵二叉樹。[考點]二叉樹

13.

一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是多少?正確答案：二叉樹的公式：n=n0+n1+n2=n0+n1+(n0-1)=2×n0+n1-1。而在完全二叉樹中，n1只能取0或1。若n1=1，則2×n0=1001，可推出n0為小數(shù)，不符合題意；若n1=0，則2×n0-1=1001，則n0=501。所以，答案為501。[考點]二叉樹

14.

如果根的層次為1，具有61個結(jié)點的完全二叉樹的深度為多少?正確答案：根據(jù)二叉樹的性質(zhì)，具有n個結(jié)點的完全二叉樹深度為[log2n]+1，因此，含有61個結(jié)點的完全二叉樹深度為6層。所以，答案為6。[考點]二叉樹

15.

在具有100個結(jié)點的樹中，其邊的數(shù)目為多少?正確答案：在一棵樹中，除了根結(jié)點之外，每一個結(jié)點都有一條入邊，因此，總邊數(shù)應(yīng)該是100-1，即99條。所以，答案為99。[考點]二叉樹

16.

什么是平衡二叉樹?正確答案：平衡二叉樹(Balanced.BinaryTree)又被稱為AVL樹，它是一棵空樹或它的左右兩個子樹的深度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。[考點]二叉樹

17.

如何用JavaScript實現(xiàn)二叉樹?正確答案：使用數(shù)組構(gòu)造一棵二叉樹，將二叉樹的每個結(jié)點存儲到數(shù)組中，數(shù)組的鍵名代表二叉樹的結(jié)點，數(shù)組的鍵值代表二叉樹的結(jié)點值。初始化時，創(chuàng)建一個指定長度的二叉樹，設(shè)置數(shù)組的第一個值為根結(jié)點。代碼實現(xiàn)如下所示。

/**

*用數(shù)組表示的二叉樹

*/

functionBinaryTree(size,root){

this.size=size;

this.array=[];

for(i=0;i＜size;i+){

this.array[i]=i;

}

this.array[0]=root;

}

BinaryTtotype={

searchNode:function(nodeCode){

//查詢結(jié)點

if(nodeCode＞=this.size||nodeCode＜0){

returnfalse;

}

returnthis.array[nodeCode];

},

addNode:function(nodeCode,place,nodeValue){

//增加樹結(jié)點

jf(nodeCode＜this.size||nodeCode＜0){

returnfalse;

}

//當(dāng)添加左孩子時,索引加1;當(dāng)添加右孩子時,索引加2

varindex=place==0?(nodeCode+1):(nodeCode+2);

//存在nodeCode這個結(jié)點就結(jié)束接下來的添加操作

if(this.array[nodeCode+1]){

returnfalse;

}

//新結(jié)點在相應(yīng)位置補(bǔ)值

if(nodeCode＞=this.size){

for(vari=this.size;i＜nodeCode+1;i++){

this.array[i]=i;

}

this.size=index;

}

this.array[index]=nodeValue;

},

deleteNode:function(nodeCode){

//刪除樹結(jié)點

if(nodeCode＞=this.size||nodeCode＜0){

returnfalse;

}

this.array.splice(nodeCode,1);

},

showTree:function(){//遍歷樹

vartxt="";

this.array.forEach(function(value,key){

txt+=value+"";

});

console.log(txt);

}

};

//產(chǎn)生一個以2為根結(jié)點,9個子結(jié)點的二叉樹

varBinaryTree=newBinaryTree(10,2);

console.log("初始化的二叉樹:");

BinaryTree.showTree();

//2123456789

console,log("搜索根結(jié)點:");

console.log(BinaryTree.searchNode(0));//2

BinaryTree.addNode(10,1,0);

console.log("增加0結(jié)點后的二叉樹:");

BinaryTree.showTree();

//2123456789100

BinaryTree.deleteNode(1);

//刪除根結(jié)點的下一個結(jié)點

console.log("刪除根結(jié)點下一個結(jié)點后的二叉樹:");

BinaryTree,showTree();

//223456789100[考點]二叉樹

18.

如何把一個有序整數(shù)數(shù)組放到二叉樹中?正確答案：如果要把一個有序的整數(shù)數(shù)組放到二叉樹中，那么所構(gòu)建出來的二叉樹必定也是一棵有序的二叉樹。鑒于此，實現(xiàn)思路為：取數(shù)組的中間元素作為根結(jié)點，將數(shù)組分成兩部分，對數(shù)組的兩部分用遞歸的方法分別構(gòu)建左右子樹。如下圖所示。

數(shù)組構(gòu)建二叉樹的過程

如圖所示，首先取數(shù)組的中間結(jié)點6作為二叉樹的根結(jié)點，把數(shù)組分成左右兩部分，然后對于數(shù)組的左右兩部分子數(shù)組分別運(yùn)用同樣的方法進(jìn)行二叉樹的構(gòu)建，例如對于左半部分子數(shù)組，取中間結(jié)點3作為樹的根結(jié)點，再把數(shù)組分成左右兩部分。以此類推，就可以完成二叉樹的構(gòu)建，實現(xiàn)代碼如下所示。

varprintTxt="";

//要在控制臺輸出的文本

/**

*二叉樹的定義

*用指定的值構(gòu)建二叉樹,并定義左右子樹

*@parammixedkey

結(jié)點值

*@parammixedleft

左子樹結(jié)點

*@parammixedright

右子樹結(jié)點

*/

functionBinaryTree(key,left,right){

this.key=key||null;

this.left=left;

this.right=right;

}

BinaryTtotype={

/**

*檢測當(dāng)前結(jié)點是否是葉子結(jié)點

*@returnboolean當(dāng)結(jié)點非空并且有兩個空的子樹時為true,否則為false

*/

isLeaf:function(){

return!this.isEmpty()&&

this.left.isEmpty()&&

this.right.isEmpty();

},

/**

*檢測結(jié)點是否為空

*@returnboolean如果結(jié)點為空返回true,否則為false

*/

isEmpty:function(){

returnthis.key===null;

},

getKey:function(){

//讀取結(jié)點值

if(this.isEmpty()){

returnfalse;

}

returnthis.key;

},

attachKey:function(obj){

//給結(jié)點指定值

if(!this.isEmpty())

returnfalse;

this.key=obj;

this.left=newBinaryTree();

this.right=newBinaryTree();

},

detachKey:function(){

//刪除結(jié)點值,使得結(jié)點為空

if(!this.isLeaf())

returnfalse;

this.key=null;

this.left=null;

this.right=null;

returnthis.key;

},

getLeft:function(){

//讀取左子樹

if(this.isEmpty())

returnfalse;

returnthis.left;

},

getRight:function(){

//讀取右子樹

if(this.isEmpty())

returnfalse;

returnthis.right;

},

preorderTraversal:function(){

//前序遍歷

if(this.isEmpty()){

return;

}

printTxt+="+this.getKey();

this.getLeft().preorderTraversal();

this.getRight().preorderTraversal();

},

inorderTraversal:function(){

//中序遍歷

if(this,isEmpty()){

return;

}

this.getLeft().inorderTraversal();

printTxt+="+this.getKey();

this.getRight().inorderTraversal();

},

postorderTraversal:function(){

//后序遍歷

if(this,isEmpty()){

return;

}

this.getLeft().postorderTraversal();

this.getRight().postorderTraversal();

printTxt+="+this.getKey();

},

insert:function(obj){

//給二叉排序樹插入指定值

if(this.isEmpty()){

this.attachKey(obj);

return;

}

vardiff=pare(obj);

if(diff＜0)

this.getLeft().insert(obj);

elseif(diff＞0)

this.getRight().insert(obj);

},

compare:function(obj){

//當(dāng)前結(jié)點值與傳入的值做比較

returnobj-this.getKey();

}

};

vararr=[1,2,3,4,5,6,7,8,9,10],

txt=arr.reduce(function(accumulator,current,index,array){

returnaccumulator+""+current;

});

console.log("數(shù)組:",tXt);

//12345678910

varroot=newBinaryTree();

/**

*對數(shù)組的兩部分用遞歸的方法分別構(gòu)建左右子樹

*/

functionsetTree(arr,root){

varlen=arr.length;

if(len＜2){

root.insert(arr[0]);

return;

}

varmiddle=Math.floor(len/2),

left=arr.slice(0,middle),

//數(shù)組的左邊部分

right=arr.slice(middle+1);

//數(shù)組的右邊部分

root.insert(arr[middle]);

//添加中間結(jié)點

setTree(left,root.left);

//左子樹

if(len＞2)

setTree(right,root.right);

//右子樹

}

setTree(arr,root);

root.inorderTraversal();

//中序遍歷

console.log("轉(zhuǎn)換成樹的中序遍歷為:",printTxt);//12345678910[考點]二叉樹

19.

假設(shè)存在以下省市區(qū)結(jié)構(gòu)的數(shù)組，需要按多層級結(jié)構(gòu)排序輸出，請使用JavaScript代碼實現(xiàn)該功能。

varitems=[

{'id':1,'pid':0,'name':'江西省'},

{'id':2,'pid':0,'name':'黑龍江省'},

{'id':3,'pid':1,'name':'南昌市'},

{'id':4,'pid':2,'name':'哈爾濱市'},

{'id':5,'pid':2,'name':'雞西市'},

{'id':6,'pid':4,'name':'香坊區(qū)'},

{'id':7,'pid':4,'name':'南崗區(qū)'},

{'id':8,'pid':6,'name':'和興路'},

{'id':9,'pid':7,'name':'西大直街'},

{'id':10,'pid':8,'name':'東北林業(yè)大學(xué)'},

{'id':11,'pid':9,'name'