版權(quán)使用警告:本內(nèi)容由圣才電子書提供,付費(fèi)購(gòu)買閱讀后,僅供個(gè)人或單位內(nèi)部學(xué)習(xí)、參考,不能作為商業(yè)用途使用
文檔簡(jiǎn)介
第一部分考研真題精選(部分視頻講解)
一、單項(xiàng)選擇題
1若元素a,b,c,d,e,f依次進(jìn)棧,允許進(jìn)棧、退棧操作交替進(jìn)行,但不允許連續(xù)三次進(jìn)行退棧操作,則不可能得到的出棧序列是()。[計(jì)算機(jī)統(tǒng)考(408)2010年研]
A.d,c,e,b,f,a
B.c,b,d,a,e,f
C.b,c,a,e,f,d
D.a(chǎn),f,e,d,c,b
【答案】D查看答案
【解析】4個(gè)選項(xiàng)所給序列的進(jìn)、出棧操作序列分別為:
選項(xiàng)A:Push,Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Pop
選項(xiàng)B:Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Push,Pop
選項(xiàng)C:Push,Push,Pop,Push,Pop,Pop,Push,Push,Pop,Push,Pop,Pop
選項(xiàng)D:Push,Pop,Push,Push,Push,Push,Push,Pop,Pop,Pop,Pop,Pop
按照題目要求,不允許連續(xù)三次進(jìn)行退棧操作,所以選項(xiàng)D所給序列為不可能得到的出棧順序。
2若一棵二叉樹(shù)的前序遍歷序列為a,e,b,d,c,后序遍歷序列為b,c,d,e,a,則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)()。[計(jì)算機(jī)統(tǒng)考(408)2012年研]
A.只有e
B.有e、b
C.有e、c
D.無(wú)法確定
【答案】A查看答案
【解析】由題目可知,若一棵二叉樹(shù)的前序遍歷序列為a,e,b,d,c,后序遍歷序列為b,c,d,e,a,其中a為這棵二叉樹(shù)的根結(jié)點(diǎn),接下來(lái),在前序遍歷的第二個(gè)結(jié)點(diǎn)為e,而后序遍歷的倒數(shù)第二個(gè)結(jié)點(diǎn)為e,說(shuō)明a的孩子結(jié)點(diǎn)只有e。
3循環(huán)隊(duì)列放在一維數(shù)組A[0..M-1]中,end1指向隊(duì)頭元素,end2指向隊(duì)尾元素的后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作,隊(duì)列中最多能容納M-1個(gè)元素。初始時(shí)為空,下列判斷隊(duì)空和隊(duì)滿的條件中,正確的是()。[計(jì)算機(jī)統(tǒng)考(408)2014年研]
A.隊(duì)空:end1==end2;隊(duì)滿:end1==(end2+1)modM
B.隊(duì)空:end1==end2;隊(duì)滿:end2==(end1+1)mod(M-1)
C.隊(duì)空:end2==(end1+1)modM;隊(duì)滿:end1==(end2+1)modM
D.隊(duì)空:end1==(end2+1)modM;隊(duì)滿:end2==(end1+1)mod(M-1)
【答案】A查看答案
【解析】在循環(huán)隊(duì)列中,在少用一個(gè)元素空間的前提下,可約定入隊(duì)前,測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針,若相等,則隊(duì)滿。而隊(duì)空的條件還是首尾指針是否相等。
4已知關(guān)鍵字序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入關(guān)鍵字3,調(diào)整后的小根堆是()。[計(jì)算機(jī)統(tǒng)考(408)2009年研]
A.3,5,12,8,28,20,15,22,19
B.3,5,12,19,20,15,22,8,28
C.3,8,12,5,20,15,22,28,19
D.3,12,5,8,28,20,15,22,19
【答案】A查看答案
【解析】在堆中插入一個(gè)元素后,將不再滿足堆的性質(zhì)。為了使其成為新堆,需要重新調(diào)整剩余元素的位置。具體過(guò)程如圖(1)~(5)所示,(1)為原堆,(2)為插入3后,(3)、(4)為調(diào)整過(guò)程,(5)為調(diào)整后的小根堆。
5下列選項(xiàng)中,不能構(gòu)成折半查找中關(guān)鍵字比較序列的是()。[計(jì)算機(jī)統(tǒng)考(408)2015年研]
A.500,200,450,180
B.500,450,200,180
C.180,500,200,450
D.180,200,500,450
【答案】A查看答案
【解析】折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu),而且表中元素按關(guān)鍵字有序排列。折半查找的關(guān)鍵字序列滿足:對(duì)每一個(gè)關(guān)鍵字,其后面的所有關(guān)鍵字序列或者都小于等于該關(guān)鍵字或者都大于等于該關(guān)鍵字。A項(xiàng)錯(cuò)誤,第三次比較的關(guān)鍵字為450,說(shuō)明待查關(guān)鍵字位于200~450間,所以第四次比較時(shí)不會(huì)遇到關(guān)鍵字180。
6已知字符串S為“abaabaabacacaabaabcc”,模式串t為“abaabc”,采用KMP算法進(jìn)行匹配,第一次出現(xiàn)“失配”(s[i]!=t[i])時(shí),i=j(luò)=5,則下次開(kāi)始匹配時(shí),i和j的值分別是()。[計(jì)算機(jī)統(tǒng)考(408)2015年研]
A.i=1,j=0
B.i=5,j=0
C.i=5,j=2
D.i=6,j=2
【答案】C查看答案
【解析】模式匹配(KMP)算法對(duì)普通的暴力匹配的改進(jìn)在于:每當(dāng)匹配過(guò)程中匹配失敗時(shí),主串(本題為S)的指針(i)不需要回溯,而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串(t)向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后,繼續(xù)進(jìn)行比較。模式串“滑動(dòng)”的距離是由模式串(t)本身決定的,即t的子串t[0…j-1]中前綴串和后綴串相等的最長(zhǎng)長(zhǎng)度。本題中第一次失配i=5,字串為“abaab”,其相等且最長(zhǎng)的前后綴為“ab”,一次下一個(gè)j=2。
7下列關(guān)于無(wú)向連通圖特性的敘述中,正確的是()。[計(jì)算機(jī)統(tǒng)考(408)2009年研]
Ⅰ.所有的頂點(diǎn)的度之和為偶數(shù)
Ⅱ.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1
Ⅲ.至少有一個(gè)頂點(diǎn)的度為1
A.只有Ⅰ
B.只有Ⅱ
C.Ⅰ和Ⅱ
D.Ⅰ和Ⅲ
【答案】A查看答案
【解析】在圖中,頂點(diǎn)的度TD(Vi)之和與邊的數(shù)目滿足關(guān)系式:
其中,n為圖的總結(jié)點(diǎn)數(shù),e為總邊數(shù)。因此,Ⅰ項(xiàng)正確。對(duì)于Ⅱ、Ⅲ項(xiàng)中的特性不是一般無(wú)向連通圖的特性,可以輕松地舉出反例?!爸辽儆幸粋€(gè)頂點(diǎn)的度為1”的反例如下圖(1)所示,“邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1”的反例如下圖(2)所示。
8下列敘述中,不符合m階B樹(shù)定義要求的是()。[計(jì)算機(jī)統(tǒng)考(408)2009年研]
A.根結(jié)點(diǎn)最多有m棵子樹(shù)
B.所有葉結(jié)點(diǎn)都在同一層上
C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列
D.葉結(jié)點(diǎn)之間通過(guò)指針鏈接
【答案】D查看答案
【解析】B樹(shù)就是指B-樹(shù)。根據(jù)B-樹(shù)的定義,m階B-樹(shù)中每個(gè)結(jié)點(diǎn)最多有m個(gè)分支,因此,根結(jié)點(diǎn)最多有m棵子樹(shù),A項(xiàng)正確;B-樹(shù)中所有葉結(jié)點(diǎn)都在最底層,位于同一層,B項(xiàng)正確;結(jié)點(diǎn)內(nèi)各關(guān)鍵字互不相等且有序排列,C項(xiàng)正確。但是,所有葉子結(jié)點(diǎn)之間通過(guò)指針鏈接,是B+樹(shù)的定義,而B(niǎo)-樹(shù)中沒(méi)有。因此,D項(xiàng)是錯(cuò)誤的。
9排序過(guò)程中,對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中,每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是()。[計(jì)算機(jī)統(tǒng)考(408)2012年研]
Ⅰ.簡(jiǎn)單選擇排序
Ⅱ.希爾排序
Ⅲ.快速排序
Ⅳ.堆排
Ⅴ.二路歸并排序
A.僅Ⅰ、Ⅲ、Ⅳ
B.僅Ⅰ、Ⅱ、Ⅲ
C.僅Ⅱ、Ⅲ、Ⅳ
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 還建房購(gòu)房協(xié)議書
- 集團(tuán)公司信息安全管理制度
- 高考數(shù)學(xué)理科二輪總復(fù)習(xí)練習(xí)第四篇 回歸教材糾錯(cuò)例析幫你減少高考失分點(diǎn)5
- 三分鐘的演講稿范文合集10篇
- (食品安全)食品廢棄物處置制度
- 企業(yè)員工愛(ài)崗敬業(yè)演講稿
- 范文端午節(jié)日記錦集六篇
- 范文新學(xué)期計(jì)劃八篇
- 上課吃東西檢討書
- 倉(cāng)儲(chǔ)課程設(shè)計(jì)問(wèn)題
- 2024年房產(chǎn)贈(zèng)與合同范本(31篇)
- 數(shù)獨(dú)比賽“六宮”練習(xí)題(96道)
- 人教版小學(xué)英語(yǔ)單詞表(完整版)
- DL-T 1476-2023 電力安全工器具預(yù)防性試驗(yàn)規(guī)程
- 小學(xué)科學(xué)蘇教版六年級(jí)上冊(cè)全冊(cè)教案(2023秋新課標(biāo)版)
- 管道支架選型計(jì)算
- 2019年蘇州市中小學(xué)生健康體檢表模板
- 2_海綿城市自評(píng)估報(bào)告28#地塊
- 上海市重點(diǎn)建設(shè)項(xiàng)目社會(huì)穩(wěn)定風(fēng)險(xiǎn)評(píng)估咨詢收費(fèi)辦法
- 相似三角形常見(jiàn)模型總結(jié)
- (最新整理)GB_T18685-2017_普通螺紋搓制和滾制前的毛坯直徑
評(píng)論
0/150
提交評(píng)論