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

班級 姓名 學(xué)籍號 考 考 生 答 題 不 得 超 過 此 密 封 線編號：QMSD/JWC-21-01數(shù)據(jù)結(jié)構(gòu)期 中 試卷（ 2008 / 2009 學(xué)年度第 一 學(xué)期）用卷班級07計信2五班用卷人數(shù)39命 題 人徐英審核人王香菊核 對 人徐英 一、選擇題（1*30=30）1、算法指的是（ ）。A、計算機程序B、解決問題的計算方法C、排序算法D、解決問題的有限運算序列2、數(shù)據(jù)的不可分割的基本單位是（ ）。A、元素B、結(jié)點C、數(shù)據(jù)類型D、數(shù)據(jù)項3、某線性表采用順序存儲結(jié)構(gòu)，每個元素占4個存儲單元，首地址為100，則第12個元素的存儲地址為（ ）。A、144B、145C、147D、1484、設(shè)線性表L=（a1，a2，an），下列關(guān)于線性表的敘述正確的是（ ）。A、每個元素都有一個直接前驅(qū)和一個直接后繼B、線性表中至少要有一個元素C、表中元素排列順序必須按由小到大或由大到小D、除第一個和最后一個元素外，其余每個元素都有且只有一個直接前驅(qū)和一個直接后繼5、對線性表，在下列情況下應(yīng)當(dāng)采用鏈表表示的是（ ）。A、經(jīng)常需要隨機地存取元素B、經(jīng)常需要進行插入和刪除操作C、表中元素需要占據(jù)一片連續(xù)的存儲空間D、表中元素的個數(shù)不變D、順序訪問相鄰結(jié)點更加靈活6、帶頭結(jié)點的雙向循環(huán)鏈表L為空的條件是（ ）。A、L= =NULLB、Lnext= =NULLC、Lprior= =NULLD、Lnext= =L7、下面關(guān)于線性表的敘述錯誤的是（ ）。A、若用數(shù)組表示，表中諸元素的存儲位置是連在一起的B、若用鏈表表示，便于插入和刪除操作C、若用鏈表表示，不需要占用一片相鄰的存儲空間D、表的插入和刪除操作僅允許在表的一端進行8、單鏈表的每個結(jié)點中包括一個指針link，它指向該結(jié)點的后繼結(jié)點。現(xiàn)要將指針q指向的新結(jié)點插入到指針p指向的單鏈表結(jié)點之后，下面的操作序列中（ ）是正確的。A、q=plink；plink= qlink；B、plink= qlink；q=plink；C、qlink= plink；plink=q；D、plink= q；qlink= plink；9、線性表采用鏈式存儲時，結(jié)點的存儲地址（ ）。A、必須是不連續(xù)的B、連續(xù)與否均可C、必須是連續(xù)的D、和頭結(jié)點的存儲地址相連續(xù)10、在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的語句是（ ）。A、p =pnext；B、pnext=pnextnext；C、pnext=p；D、p=pnextnext；11、若已知一個棧的進棧序列是1，2，3n，其輸出序列是p1，p2，p3pn，若p1=3，則p2為（ ）。A、可能是2B、一定是2C、可能是1D、一定是112、設(shè)初始輸入序列為1，2，3，4，5，利用一個棧產(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個元素入棧的順序為e1，e2，e3，e4，e5和e6。若出棧的順序是e2，e4，e3，e6，e5，e1，則棧S的容量至少應(yīng)該是（ ）。A、6B、4C、3D、214、4個元素a1，a2，a3和a4依次入棧，入棧過程中允許棧頂元素出棧，假設(shè)某一時刻棧的狀態(tài)是a3（棧頂），a2，a1（棧底），則不可能的出棧序列是（ ）。A、a4，a3，a2，a1B、a3，a2，a4，a1C、a3，a1，a4，a2D、a3，a4，a2，a115、向順序棧中壓入新元素時，應(yīng)當(dāng)（ ）。A、先移動棧頂指針，再存入元素B、先存入元素，再移動棧頂指針C、先后次序無關(guān)緊要D、同時進行16、棧和隊列的共同點是（ ）。A、都是先進先出B、都是先進后出C、只允許在端點處插入和刪除元素D、沒有共同點17、下列關(guān)于線性表、棧和隊列的敘述，錯誤的是（ ）。A、線性表是給定的n（n必須大于零）個元素組成的序列B、線性表允許在表的任何位置進行插入和刪除操作C、棧只允許在一端進行插入和刪除操作D、隊列允許在一端進行插入在另一端進行刪除18、設(shè)一個棧的輸入序列為A，B，C，D，則借助一個棧所得到輸出序列不可能是（ ）。A、A，B，C，DB、D，C，B，AC、A，C，D，BD、D，A，B，C19、從一個順序隊列中刪除元素時，首先要（ ）。A、前移一位隊首指針B、后移一位隊首指針C、取出隊首指針?biāo)肝恢蒙系脑谼、取出隊尾指針?biāo)肝恢蒙系脑?0、下列有關(guān)樹的概念錯誤的是（ ）。A、一棵樹中只有一個無前驅(qū)的結(jié)點B、一棵樹的度為樹中各個結(jié)點的度數(shù)之和C、一棵樹中，每個結(jié)點的度數(shù)之和等于結(jié)點總數(shù)減1D、一棵樹中每個結(jié)點的度數(shù)之和與邊的條數(shù)相等21、在一棵非空二叉樹的中序遍歷序列中，根結(jié)點的右邊（ ）。A、只有右子樹上的所有結(jié)點B、只有右子樹上的部分結(jié)點C、只有左子樹上的部分結(jié)點D、只有左子樹上的所有結(jié)點22、下面關(guān)于二叉樹的敘述正確的是（ ）。A、一棵二叉樹中葉子結(jié)點的個數(shù)等于度為2的結(jié)點個數(shù)加1B、一棵二叉樹中的結(jié)點個數(shù)大于0C、二叉樹中任何一個結(jié)點要么是葉，要么恰有兩個子女D、二叉樹中任何一個結(jié)點的左子樹和右子樹上的結(jié)點個數(shù)一定相等23、已知某二叉樹的后序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是（ ）。A、ACBEDB、DEABCC、DECABD、EDBCA24、如果一棵二叉樹中所有結(jié)點的值都大于其左子樹中所有結(jié)點的值，且小于其右子樹中所有結(jié)點的值，現(xiàn)欲得到各個結(jié)點值的遞增序列，采用的方法是（ ）。A、前序遍歷B、后序遍歷C、中序遍歷D、層次遍歷25、設(shè)二叉樹根結(jié)點的層次為0，一棵樹深為h的滿二叉樹中結(jié)點個數(shù)是（ ）。A、2hB、2h-1C、2h -1D、2h+1 -126、有關(guān)二叉樹的下列說法正確的是（ ）。A、二叉樹的度為2B、一棵二叉樹的度可以小于2C、二叉樹中任何一個結(jié)點的度都為2D、任何一棵二叉樹中至少有一個結(jié)點的度為227、樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹，其中結(jié)論（ ）是正確的。A、樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B、樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C、樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D、以上都不對28、深度為5的二叉樹至多有（ ）個結(jié)點。A、16B、32C、31D、1029、對一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h，則（ ）。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-130、在下列存儲形式中，（ ）不是樹的存儲形式。A、雙親表示法B、孩子鏈表表示法C、孩子兄弟表示法D、順序存儲表示法題號123456789101112131415答案題號161718192021222324252627282930答案二、填空題（1*25=25）1、數(shù)據(jù)的存儲結(jié)構(gòu)主要分為 和 兩種。2、算法的5個重要特性是：輸入、輸出、可行性、確定性和 。3、算法的時間復(fù)雜度取決于 和特處理的數(shù)據(jù)的初態(tài)。4、線性表中 稱為表的長度。5、在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向 ，另一個指向 。6、在一個單鏈表中的p所指結(jié)點之前插入一個s所指的結(jié)點時，可以執(zhí)行如下操作：（1）snext= ；（2）pnext= ；7、針對線性鏈表的基本操作有很多，但其中最基本的4種操作分別為 、刪除、查找和排序。8、棧中元素的進出原則是 。9、隊列中元素的進出原則是 。10、假設(shè)以S和X分別表示進棧和退棧操作，則對輸入序列a，b，c，d，e進行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為 。11、設(shè)棧S初始狀態(tài)為空，隊列Q的初始狀態(tài)如下圖所示。 a1a2a3a4隊頭 隊尾對棧S和隊列Q進行以下兩步操作：（1）刪除Q中的元素，將刪除的元素插入S，直到Q為空；（2）依次將S中的元素插入Q，直到S為空。在上述兩步操作后，隊列Q的狀態(tài)是 。12、有一棵樹如圖所示，請回答以下問題：k1k2k3k4k5k6k7（1）這根樹的根結(jié)點是_；（2）這根樹的葉子結(jié)點是_；（3）結(jié)點k3的度是_；（4）這根樹的度是_；（5）這根樹的深度是_；（6）結(jié)點k3的孩子結(jié)點是_；（7）結(jié)點k3的雙親結(jié)點是_；13、在一棵二叉樹中，葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則有n0=_。14、二叉樹如圖所示，回答下面問題。（1）其中序遍歷序列為_。（2）其先序遍歷序列為_。（3）其后序遍歷序列為_。三、綜合題（4+4+6+6+10+10+5=45）1、寫出將循環(huán)鏈表A和循環(huán)鏈表B合并成一個循環(huán)鏈表A的主要操作語句。2、寫出在雙向鏈表中的P結(jié)點前插入一個S結(jié)點的主要操作語句。3、已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA。畫