首頁 - 網(wǎng)校 - 萬題庫 - 直播 - 雄鷹網(wǎng)校 - 團購 - 書城 - 模考 - 學(xué)習(xí)通 - 導(dǎo)航 -
首頁網(wǎng)校萬題庫直播雄鷹網(wǎng)校團購書城?論壇實用文檔作文大全寶寶起名
2015中考
法律碩士
2015高考
MBA考試
2015考研
MPA考試
在職研
中科院
考研培訓(xùn)
專升本
自學(xué)考試 成人高考
四 六 級
GRE考試
攻碩英語
零起點日語
職稱英語
口譯筆譯
申碩英語
零起點韓語
商務(wù)英語
日語等級
GMAT考試
公共英語
職稱日語
新概念英語
專四專八
博思考試
零起點英語
托福考試
托業(yè)考試
零起點法語
雅思考試
成人英語三級
零起點德語
等級考試
華為認(rèn)證
水平考試
Java認(rèn)證
職稱計算機 微軟認(rèn)證 思科認(rèn)證 Oracle認(rèn)證 Linux認(rèn)證
公 務(wù) 員
導(dǎo)游考試
物 流 師
出版資格
單 證 員
報 關(guān) 員
外 銷 員
價格鑒證
網(wǎng)絡(luò)編輯
駕 駛 員
報檢員
法律顧問
管理咨詢
企業(yè)培訓(xùn)
社會工作者
銀行從業(yè)
教師資格
營養(yǎng)師
保險從業(yè)
普 通 話
證券從業(yè)
跟 單 員
秘書資格
電子商務(wù)
期貨考試
國際商務(wù)
心理咨詢
營 銷 師
司法考試
國際貨運代理人
人力資源管理師
廣告師職業(yè)水平
衛(wèi)生資格 執(zhí)業(yè)醫(yī)師 執(zhí)業(yè)藥師 執(zhí)業(yè)護士
會計從業(yè)資格
基金從業(yè)資格
統(tǒng)計從業(yè)資格
經(jīng)濟師
精算師
統(tǒng)計師
會計職稱
法律顧問
ACCA考試
初級會計職稱
資產(chǎn)評估師
高級經(jīng)濟師
注冊會計師
高級會計師
美國注冊會計師
審計師考試
國際內(nèi)審師
注冊稅務(wù)師
理財規(guī)劃師
一級建造師
安全工程師
設(shè)備監(jiān)理師
公路監(jiān)理師
公路造價師
二級建造師
招標(biāo)師考試
物業(yè)管理師
電氣工程師
建筑師考試
造價工程師
注冊測繪師
質(zhì)量工程師
巖土工程師
注冊給排水
造價員考試
注冊計量師
環(huán)保工程師
化工工程師
暖通工程師
咨詢工程師
結(jié)構(gòu)工程師
城市規(guī)劃師
材料員考試
消防工程師
監(jiān)理工程師
房地產(chǎn)估價
土地估價師
安全評價師
房地產(chǎn)經(jīng)紀(jì)人
投資項目管理師
環(huán)境影響評價師
土地登記代理人
寶寶起名
繽紛校園
實用文檔
入黨申請
英語學(xué)習(xí)
思想?yún)R報
作文大全
工作總結(jié)
求職招聘 論文下載 直播課堂
您現(xiàn)在的位置: 考試吧 > 軟件水平考試 > 復(fù)習(xí)資料 > 程序員 > 正文

2015年軟件水平考試程序員精選題(3)

考試吧整理“2015年軟件水平考試程序員精選題(3)”供考生參考,更多軟件水平考試資訊和備考資料請關(guān)注考試吧軟件水平考試網(wǎng)。

  判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果[折疊]

  題目:輸入一個整數(shù)數(shù)組,判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。如果是返回true,否則返回false。

  例如輸入5、7、6、9、11、10、8,由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果:

  8

  / \

  6 10

  / \ / \

  5 7 9 11

  因此返回true。

  如果輸入7、4、6、5,沒有哪棵樹的后序遍歷的結(jié)果是這個序列,因此返回false。

  分析:這是一道trilogy的筆試題,主要考查對二元查找樹的理解。

  在后續(xù)遍歷得到的序列中,最后一個元素為樹的根結(jié)點。從頭開始掃描這個序列,比根結(jié)點小的元素都應(yīng)該位于序列的左半部分;從第一個大于跟結(jié)點開始到跟結(jié)點前面的一個元素為止,所有元素都應(yīng)該大于跟結(jié)點,因為這部分元素對應(yīng)的是樹的右子樹。根據(jù)這樣的劃分,把序列劃分為左右兩部分,我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹。

  參考代碼:

  using namespace std;

  ///////////////////////////////////////////////////////////////////////

  // Verify whether a squence of integers are the post order traversal

  // of a binary search tree (BST)

  // Input: squence - the squence of integers

  // length - the length of squence

  // Return: return ture if the squence is traversal result of a BST,

  // otherwise, return false

  ///////////////////////////////////////////////////////////////////////

  bool verifySquenceOfBST(int squence[], int length)

  {

  if(squence == NULL || length <= 0)

  return false;

  // root of a BST is at the end of post order traversal squence

  int root = squence[length - 1];

  // the nodes in left sub-tree are less than the root

  int i = 0;

  for(; i < length - 1; ++ i)

  {

  if(squence[i] > root)

  break;

  }

  // the nodes in the right sub-tree are greater than the root

  int j = i;

  for(; j < length - 1; ++ j)

  {

  if(squence[j] < root)

  return false;

  }

  // verify whether the left sub-tree is a BST

  bool left = true;

  if(i > 0)

  left = verifySquenceOfBST(squence, i);

  // verify whether the right sub-tree is a BST

  bool right = true;

  if(i < length - 1)

  right = verifySquenceOfBST(squence + i, length - i - 1);

  return (left && right);

  }

上一頁  1 2 

  相關(guān)推薦:

  2015年軟考信息技術(shù)處理員考前知識點總結(jié)匯總

  2015年軟件水平考試《程序員》提高練習(xí)題匯總

  2015軟件水平考試《程序員》知識點總結(jié)匯總

文章搜索
軟件水平考試欄目導(dǎo)航
版權(quán)聲明:如果軟件水平考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請與我們聯(lián)系800@exam8.com,我們將會及時處理。如轉(zhuǎn)載本軟件水平考試網(wǎng)內(nèi)容,請注明出處。
Copyright © 2004- 考試吧軟件水平考試網(wǎng) All Rights Reserved 
中國科學(xué)院研究生院權(quán)威支持(北京)
在線模擬試題
考證通關(guān)殺器
考試最新資訊
學(xué)
一次通關(guān)技巧