徐英數(shù)據(jù)結(jié)構(gòu)期中考試.doc

班級(jí) 姓名 學(xué)籍號(hào) 考 考 生 答 題 不 得 超 過(guò) 此 密 封 線(xiàn)編號(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、解決問(wèn)題的計(jì)算方法C、排序算法D、解決問(wèn)題的有限運(yùn)算序列2、數(shù)據(jù)的不可分割的基本單位是（ ）。A、元素B、結(jié)點(diǎn)C、數(shù)據(jù)類(lèi)型D、數(shù)據(jù)項(xiàng)3、某線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占4個(gè)存儲(chǔ)單元，首地址為100，則第12個(gè)元素的存儲(chǔ)地址為（ ）。A、144B、145C、147D、1484、設(shè)線(xiàn)性表L=（a1，a2，an），下列關(guān)于線(xiàn)性表的敘述正確的是（ ）。A、每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B、線(xiàn)性表中至少要有一個(gè)元素C、表中元素排列順序必須按由小到大或由大到小D、除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼5、對(duì)線(xiàn)性表，在下列情況下應(yīng)當(dāng)采用鏈表表示的是（ ）。A、經(jīng)常需要隨機(jī)地存取元素B、經(jīng)常需要進(jìn)行插入和刪除操作C、表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D、表中元素的個(gè)數(shù)不變D、順序訪問(wèn)相鄰結(jié)點(diǎn)更加靈活6、帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空的條件是（ ）。A、L= =NULLB、Lnext= =NULLC、Lprior= =NULLD、Lnext= =L7、下面關(guān)于線(xiàn)性表的敘述錯(cuò)誤的是（ ）。A、若用數(shù)組表示，表中諸元素的存儲(chǔ)位置是連在一起的B、若用鏈表表示，便于插入和刪除操作C、若用鏈表表示，不需要占用一片相鄰的存儲(chǔ)空間D、表的插入和刪除操作僅允許在表的一端進(jìn)行8、單鏈表的每個(gè)結(jié)點(diǎn)中包括一個(gè)指針link，它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)?，F(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、線(xiàn)性表采用鏈?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的后繼”的語(yǔ)句是（ ）。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)生輸出序列，下列（ ）序列是不可能通過(guò)棧產(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依次入棧，入棧過(guò)程中允許棧頂元素出棧，假設(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、先后次序無(wú)關(guān)緊要D、同時(shí)進(jìn)行16、棧和隊(duì)列的共同點(diǎn)是（ ）。A、都是先進(jìn)先出B、都是先進(jìn)后出C、只允許在端點(diǎn)處插入和刪除元素D、沒(méi)有共同點(diǎn)17、下列關(guān)于線(xiàn)性表、棧和隊(duì)列的敘述，錯(cuò)誤的是（ ）。A、線(xiàn)性表是給定的n（n必須大于零）個(gè)元素組成的序列B、線(xiàn)性表允許在表的任何位置進(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)樹(shù)的概念錯(cuò)誤的是（ ）。A、一棵樹(shù)中只有一個(gè)無(wú)前驅(qū)的結(jié)點(diǎn)B、一棵樹(shù)的度為樹(shù)中各個(gè)結(jié)點(diǎn)的度數(shù)之和C、一棵樹(shù)中，每個(gè)結(jié)點(diǎn)的度數(shù)之和等于結(jié)點(diǎn)總數(shù)減1D、一棵樹(shù)中每個(gè)結(jié)點(diǎn)的度數(shù)之和與邊的條數(shù)相等21、在一棵非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊（ ）。A、只有右子樹(shù)上的所有結(jié)點(diǎn)B、只有右子樹(shù)上的部分結(jié)點(diǎn)C、只有左子樹(shù)上的部分結(jié)點(diǎn)D、只有左子樹(shù)上的所有結(jié)點(diǎn)22、下面關(guān)于二叉樹(shù)的敘述正確的是（ ）。A、一棵二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1B、一棵二叉樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)大于0C、二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)要么是葉，要么恰有兩個(gè)子女D、二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)一定相等23、已知某二叉樹(shù)的后序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是（ ）。A、ACBEDB、DEABCC、DECABD、EDBCA24、如果一棵二叉樹(shù)中所有結(jié)點(diǎn)的值都大于其左子樹(shù)中所有結(jié)點(diǎn)的值，且小于其右子樹(shù)中所有結(jié)點(diǎn)的值，現(xiàn)欲得到各個(gè)結(jié)點(diǎn)值的遞增序列，采用的方法是（ ）。A、前序遍歷B、后序遍歷C、中序遍歷D、層次遍歷25、設(shè)二叉樹(shù)根結(jié)點(diǎn)的層次為0，一棵樹(shù)深為h的滿(mǎn)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)是（ ）。A、2hB、2h-1C、2h -1D、2h+1 -126、有關(guān)二叉樹(shù)的下列說(shuō)法正確的是（ ）。A、二叉樹(shù)的度為2B、一棵二叉樹(shù)的度可以小于2C、二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2D、任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為227、樹(shù)的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹(shù)的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹(shù)轉(zhuǎn)化得到的二叉樹(shù)叫做這棵樹(shù)對(duì)應(yīng)的二叉樹(shù)，其中結(jié)論（ ）是正確的。A、樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷序列相同B、樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同C、樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列相同D、以上都不對(duì)28、深度為5的二叉樹(shù)至多有（ ）個(gè)結(jié)點(diǎn)。A、16B、32C、31D、1029、對(duì)一個(gè)滿(mǎn)二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h，則（ ）。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-130、在下列存儲(chǔ)形式中，（ ）不是樹(shù)的存儲(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、線(xiàn)性表中 稱(chēng)為表的長(zhǎng)度。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ì)線(xiàn)性鏈表的基本操作有很多，但其中最基本的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、有一棵樹(shù)如圖所示，請(qǐng)回答以下問(wèn)題：k1k2k3k4k5k6k7（1）這根樹(shù)的根結(jié)點(diǎn)是_；（2）這根樹(shù)的葉子結(jié)點(diǎn)是_；（3）結(jié)點(diǎn)k3的度是_；（4）這根樹(shù)的度是_；（5）這根樹(shù)的深度是_；（6）結(jié)點(diǎn)k3的孩子結(jié)點(diǎn)是_；（7）結(jié)點(diǎn)k3的雙親結(jié)點(diǎn)是_；13、在一棵二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0=_。14、二叉樹(shù)如圖所示，回答下面問(wèn)題。（1）其中序遍歷序列為_(kāi)。（2）其先序遍歷序列為_(kāi)。（3）其后序遍歷序列為_(kāi)。三、綜合題（4+4+6+6+10+10+5=45）1、寫(xiě)出將循環(huán)鏈表A和循環(huán)鏈表B合并成一個(gè)循環(huán)鏈表A的主要操作語(yǔ)句。2、寫(xiě)出在雙向鏈表中的P結(jié)點(diǎn)前插入一個(gè)S結(jié)點(diǎn)的主要操作語(yǔ)句。3、已知一棵二叉樹(shù)的中序序列和后序序列分別為BDCEAFHG和DECBHGFA。畫(huà)