



全文預(yù)覽已結(jié)束
下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
班級(jí) 姓名 學(xué)籍號(hào) 考 考 生 答 題 不 得 超 過 此 密 封 線編號(hào):QMSD/JWC-21-01數(shù)據(jù)結(jié)構(gòu)期 中 試卷( 2008 / 2009 學(xué)年度第 一 學(xué)期)用卷班級(jí)07計(jì)信2五班用卷人數(shù)39命 題 人徐英審核人王香菊核 對(duì) 人徐英 一、選擇題(1*30=30)1、算法指的是( )。A、計(jì)算機(jī)程序B、解決問題的計(jì)算方法C、排序算法D、解決問題的有限運(yùn)算序列2、數(shù)據(jù)的不可分割的基本單位是( )。A、元素B、結(jié)點(diǎn)C、數(shù)據(jù)類型D、數(shù)據(jù)項(xiàng)3、某線性表采用順序存儲(chǔ)結(jié)構(gòu),每個(gè)元素占4個(gè)存儲(chǔ)單元,首地址為100,則第12個(gè)元素的存儲(chǔ)地址為( )。A、144B、145C、147D、1484、設(shè)線性表L=(a1,a2,an),下列關(guān)于線性表的敘述正確的是( )。A、每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B、線性表中至少要有一個(gè)元素C、表中元素排列順序必須按由小到大或由大到小D、除第一個(gè)和最后一個(gè)元素外,其余每個(gè)元素都有且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼5、對(duì)線性表,在下列情況下應(yīng)當(dāng)采用鏈表表示的是( )。A、經(jīng)常需要隨機(jī)地存取元素B、經(jīng)常需要進(jìn)行插入和刪除操作C、表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D、表中元素的個(gè)數(shù)不變D、順序訪問相鄰結(jié)點(diǎn)更加靈活6、帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空的條件是( )。A、L= =NULLB、Lnext= =NULLC、Lprior= =NULLD、Lnext= =L7、下面關(guān)于線性表的敘述錯(cuò)誤的是( )。A、若用數(shù)組表示,表中諸元素的存儲(chǔ)位置是連在一起的B、若用鏈表表示,便于插入和刪除操作C、若用鏈表表示,不需要占用一片相鄰的存儲(chǔ)空間D、表的插入和刪除操作僅允許在表的一端進(jìn)行8、單鏈表的每個(gè)結(jié)點(diǎn)中包括一個(gè)指針link,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。現(xiàn)要將指針q指向的新結(jié)點(diǎn)插入到指針p指向的單鏈表結(jié)點(diǎn)之后,下面的操作序列中( )是正確的。A、q=plink;plink= qlink;B、plink= qlink;q=plink;C、qlink= plink;plink=q;D、plink= q;qlink= plink;9、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí),結(jié)點(diǎn)的存儲(chǔ)地址( )。A、必須是不連續(xù)的B、連續(xù)與否均可C、必須是連續(xù)的D、和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)10、在單鏈表中,指針p指向元素為x的結(jié)點(diǎn),實(shí)現(xiàn)“刪除x的后繼”的語句是( )。A、p =pnext;B、pnext=pnextnext;C、pnext=p;D、p=pnextnext;11、若已知一個(gè)棧的進(jìn)棧序列是1,2,3n,其輸出序列是p1,p2,p3pn,若p1=3,則p2為( )。A、可能是2B、一定是2C、可能是1D、一定是112、設(shè)初始輸入序列為1,2,3,4,5,利用一個(gè)棧產(chǎn)生輸出序列,下列( )序列是不可能通過棧產(chǎn)生的。A、1,2,3,4,5B、5,3,4,1,2C、4,3,2,1,5D、3,4,5,2,113、設(shè)棧S的初始狀態(tài)為空,6個(gè)元素入棧的順序?yàn)閑1,e2,e3,e4,e5和e6。若出棧的順序是e2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該是( )。A、6B、4C、3D、214、4個(gè)元素a1,a2,a3和a4依次入棧,入棧過程中允許棧頂元素出棧,假設(shè)某一時(shí)刻棧的狀態(tài)是a3(棧頂),a2,a1(棧底),則不可能的出棧序列是( )。A、a4,a3,a2,a1B、a3,a2,a4,a1C、a3,a1,a4,a2D、a3,a4,a2,a115、向順序棧中壓入新元素時(shí),應(yīng)當(dāng)( )。A、先移動(dòng)棧頂指針,再存入元素B、先存入元素,再移動(dòng)棧頂指針C、先后次序無關(guān)緊要D、同時(shí)進(jìn)行16、棧和隊(duì)列的共同點(diǎn)是( )。A、都是先進(jìn)先出B、都是先進(jìn)后出C、只允許在端點(diǎn)處插入和刪除元素D、沒有共同點(diǎn)17、下列關(guān)于線性表、棧和隊(duì)列的敘述,錯(cuò)誤的是( )。A、線性表是給定的n(n必須大于零)個(gè)元素組成的序列B、線性表允許在表的任何位置進(jìn)行插入和刪除操作C、棧只允許在一端進(jìn)行插入和刪除操作D、隊(duì)列允許在一端進(jìn)行插入在另一端進(jìn)行刪除18、設(shè)一個(gè)棧的輸入序列為A,B,C,D,則借助一個(gè)棧所得到輸出序列不可能是( )。A、A,B,C,DB、D,C,B,AC、A,C,D,BD、D,A,B,C19、從一個(gè)順序隊(duì)列中刪除元素時(shí),首先要( )。A、前移一位隊(duì)首指針B、后移一位隊(duì)首指針C、取出隊(duì)首指針?biāo)肝恢蒙系脑谼、取出隊(duì)尾指針?biāo)肝恢蒙系脑?0、下列有關(guān)樹的概念錯(cuò)誤的是( )。A、一棵樹中只有一個(gè)無前驅(qū)的結(jié)點(diǎn)B、一棵樹的度為樹中各個(gè)結(jié)點(diǎn)的度數(shù)之和C、一棵樹中,每個(gè)結(jié)點(diǎn)的度數(shù)之和等于結(jié)點(diǎn)總數(shù)減1D、一棵樹中每個(gè)結(jié)點(diǎn)的度數(shù)之和與邊的條數(shù)相等21、在一棵非空二叉樹的中序遍歷序列中,根結(jié)點(diǎn)的右邊( )。A、只有右子樹上的所有結(jié)點(diǎn)B、只有右子樹上的部分結(jié)點(diǎn)C、只有左子樹上的部分結(jié)點(diǎn)D、只有左子樹上的所有結(jié)點(diǎn)22、下面關(guān)于二叉樹的敘述正確的是( )。A、一棵二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1B、一棵二叉樹中的結(jié)點(diǎn)個(gè)數(shù)大于0C、二叉樹中任何一個(gè)結(jié)點(diǎn)要么是葉,要么恰有兩個(gè)子女D、二叉樹中任何一個(gè)結(jié)點(diǎn)的左子樹和右子樹上的結(jié)點(diǎn)個(gè)數(shù)一定相等23、已知某二叉樹的后序遍歷序列是DACBE,中序遍歷序列是DEBAC,則它的前序遍歷序列是( )。A、ACBEDB、DEABCC、DECABD、EDBCA24、如果一棵二叉樹中所有結(jié)點(diǎn)的值都大于其左子樹中所有結(jié)點(diǎn)的值,且小于其右子樹中所有結(jié)點(diǎn)的值,現(xiàn)欲得到各個(gè)結(jié)點(diǎn)值的遞增序列,采用的方法是( )。A、前序遍歷B、后序遍歷C、中序遍歷D、層次遍歷25、設(shè)二叉樹根結(jié)點(diǎn)的層次為0,一棵樹深為h的滿二叉樹中結(jié)點(diǎn)個(gè)數(shù)是( )。A、2hB、2h-1C、2h -1D、2h+1 -126、有關(guān)二叉樹的下列說法正確的是( )。A、二叉樹的度為2B、一棵二叉樹的度可以小于2C、二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2D、任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為227、樹的基本遍歷策略可分為先根遍歷和后根遍歷;二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里,我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹,其中結(jié)論( )是正確的。A、樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B、樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C、樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D、以上都不對(duì)28、深度為5的二叉樹至多有( )個(gè)結(jié)點(diǎn)。A、16B、32C、31D、1029、對(duì)一個(gè)滿二叉樹,m個(gè)樹葉,n個(gè)結(jié)點(diǎn),深度為h,則( )。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-130、在下列存儲(chǔ)形式中,( )不是樹的存儲(chǔ)形式。A、雙親表示法B、孩子鏈表表示法C、孩子兄弟表示法D、順序存儲(chǔ)表示法題號(hào)123456789101112131415答案題號(hào)161718192021222324252627282930答案二、填空題(1*25=25)1、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要分為 和 兩種。2、算法的5個(gè)重要特性是:輸入、輸出、可行性、確定性和 。3、算法的時(shí)間復(fù)雜度取決于 和特處理的數(shù)據(jù)的初態(tài)。4、線性表中 稱為表的長度。5、在雙向鏈表中,每個(gè)結(jié)點(diǎn)有兩個(gè)指針域,一個(gè)指向 ,另一個(gè)指向 。6、在一個(gè)單鏈表中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指的結(jié)點(diǎn)時(shí),可以執(zhí)行如下操作:(1)snext= ;(2)pnext= ;7、針對(duì)線性鏈表的基本操作有很多,但其中最基本的4種操作分別為 、刪除、查找和排序。8、棧中元素的進(jìn)出原則是 。9、隊(duì)列中元素的進(jìn)出原則是 。10、假設(shè)以S和X分別表示進(jìn)棧和退棧操作,則對(duì)輸入序列a,b,c,d,e進(jìn)行一系列棧操作SSXSXSSXXX之后,得到的輸出序列為 。11、設(shè)棧S初始狀態(tài)為空,隊(duì)列Q的初始狀態(tài)如下圖所示。 a1a2a3a4隊(duì)頭 隊(duì)尾對(duì)棧S和隊(duì)列Q進(jìn)行以下兩步操作:(1)刪除Q中的元素,將刪除的元素插入S,直到Q為空;(2)依次將S中的元素插入Q,直到S為空。在上述兩步操作后,隊(duì)列Q的狀態(tài)是 。12、有一棵樹如圖所示,請(qǐng)回答以下問題:k1k2k3k4k5k6k7(1)這根樹的根結(jié)點(diǎn)是_;(2)這根樹的葉子結(jié)點(diǎn)是_;(3)結(jié)點(diǎn)k3的度是_;(4)這根樹的度是_;(5)這根樹的深度是_;(6)結(jié)點(diǎn)k3的孩子結(jié)點(diǎn)是_;(7)結(jié)點(diǎn)k3的雙親結(jié)點(diǎn)是_;13、在一棵二叉樹中,葉子結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2,則有n0=_。14、二叉樹如圖所示,回答下面問題。(1)其中序遍歷序列為_。(2)其先序遍歷序列為_。(3)其后序遍歷序列為_。三、綜合題(4+4+6+6+10+10+5=45)1、寫出將循環(huán)鏈表A和循環(huán)鏈表B合并成一個(gè)循環(huán)鏈表A的主要操作語句。2、寫出在雙向鏈表中的P結(jié)點(diǎn)前插入一個(gè)S結(jié)點(diǎn)的主要操作語句。3、已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA。畫
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 泵類銷售員崗位面試問題及答案
- 保安隊(duì)長崗位面試問題及答案
- 自動(dòng)化測試工程師崗位面試問題及答案
- 游戲數(shù)值策劃師崗位面試問題及答案
- 浙江省麗水市四校聯(lián)考2025屆高二下化學(xué)期末達(dá)標(biāo)檢測試題含解析
- 安徽師范大學(xué)附中2025屆高二下化學(xué)期末達(dá)標(biāo)檢測試題含解析
- 2025屆山西省同煤一中聯(lián)盟校高一下化學(xué)期末聯(lián)考試題含解析
- 2025屆浙江寧波市北侖區(qū)高二化學(xué)第二學(xué)期期末達(dá)標(biāo)檢測模擬試題含解析
- 公用澡堂制度管理辦法
- 幼兒園戶外活動(dòng)管理:現(xiàn)狀與對(duì)策探討
- 棧橋?qū)m?xiàng)施工方案
- 高三英語一輪復(fù)習(xí)人教版(2019)必修第一至三冊(cè)一詞多義和熟詞生義清單
- 高溫作業(yè)引發(fā)的電氣事故
- 肝癌疑難病例護(hù)理討論
- 旅游規(guī)劃與國土空間開發(fā)
- 檔案整理及數(shù)字化服務(wù)方案
- 土力學(xué)與地基基礎(chǔ)(課件)
- 全國居民身份證前6位查詢電子檔
- 公司變更登記(備案)申請(qǐng)書
- 2023年醫(yī)技類-超聲醫(yī)學(xué)(副高)考試歷年真題集錦附答案
- 《經(jīng)濟(jì)學(xué)基礎(chǔ)》課程標(biāo)準(zhǔn)
評(píng)論
0/150
提交評(píng)論