數(shù)據(jù)結(jié)構(gòu)ab

1、本試卷共12頁(yè)第1頁(yè)本試卷共12頁(yè)第2頁(yè)學(xué)院學(xué)院2009―2010學(xué)年度第二學(xué)期學(xué)年度第二學(xué)期《數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)》期末試卷期末試卷A卷課程歸屬部門：課程歸屬部門：計(jì)算機(jī)與信息工程學(xué)院計(jì)算機(jī)與信息工程學(xué)院試卷適用范圍：試卷適用范圍：09計(jì)算機(jī)各專業(yè)計(jì)算機(jī)各專業(yè)題號(hào)一二三四五總分得分1.程序和算法在原則上沒有區(qū)別，所以在在討論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。（）2.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。（）3.順序表結(jié)

2、構(gòu)適宜進(jìn)行順序存取，而鏈表適宜進(jìn)行隨機(jī)存取。（）4.空棧就是所有元素都為0的棧。（）5.隊(duì)列是限制在兩端進(jìn)行操作的線性表。（）6串是n個(gè)字母的有限序列。（）7.樹結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)只有一個(gè)直接前驅(qū)。（）8.在完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必然是葉子結(jié)點(diǎn)。（）9.二叉樹的遍歷是指按某種順序訪問二叉樹中的所有結(jié)點(diǎn)。（）10.帶權(quán)路徑長(zhǎng)度最小的二叉樹稱為哈夫曼樹。（）1數(shù)據(jù)有邏輯結(jié)構(gòu)和兩種結(jié)構(gòu)。2在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為。3

3、設(shè)r指向單鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn)，需執(zhí)行的三條語(yǔ)句是___________；r=srnext=null。4在隊(duì)列中存取數(shù)據(jù)應(yīng)遵循的原則是。5在一個(gè)鏈隊(duì)列中，若隊(duì)首指針為front，隊(duì)尾指針rear，則判斷該隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件為。6在空串和空格串中，長(zhǎng)度不為0的是。7在一個(gè)具有n個(gè)單元的順序棧中，假定以地址高端（即下標(biāo)為n的單元）作為棧底，以top作為棧頂指針，則當(dāng)向棧中壓入一個(gè)元素時(shí)，top的變化是

4、top＝_________。8設(shè)一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：ABDECFGH，中序遍歷序列為：DEBAFCHG，則二叉樹中葉結(jié)點(diǎn)是。9數(shù)據(jù)的邏輯結(jié)構(gòu)除了集合以外，還包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和。10給定如右圖二叉樹，其前序遍歷序列為：。1算法分析的兩個(gè)主要方面是（）。A空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡(jiǎn)明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性2算法能正確的實(shí)現(xiàn)預(yù)定功能的特性稱為算法的（）A健壯性B易讀性C正確性D高效性3在具有

5、n個(gè)結(jié)點(diǎn)的單向鏈表中，實(shí)現(xiàn)（）的操作，其算法的時(shí)間復(fù)雜度是O（n）。A遍歷鏈表或求鏈表的第i個(gè)結(jié)點(diǎn)B.在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C.刪除開始結(jié)點(diǎn)D.刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn)4在單鏈表中，增加頭結(jié)點(diǎn)的目的是（）。A使單鏈表至少有一個(gè)結(jié)點(diǎn)B標(biāo)志表中首結(jié)點(diǎn)的位置C方便運(yùn)算的實(shí)現(xiàn)D說明該單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)5帶頭結(jié)點(diǎn)的鏈棧LS的示意圖如下，棧頂元素是（）HABCLSAHBACBDC6引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是（）。A

6、.出隊(duì)B.入隊(duì)C.取隊(duì)頭元素D.取隊(duì)尾元素7隊(duì)列Q，經(jīng)過下列運(yùn)算后，再執(zhí)行Qempty(Q)的值是（）。InitQueue(Q)(初始化隊(duì)列)；InQueue(Qa)；InQueue(Qb)；OutQueue(Qx)；ReadQueue(Qx)；AaBbC0D18串的模式匹配是指（）。A判斷兩個(gè)串是否相等B.找某字符在主串中第一次出現(xiàn)的位置C.對(duì)兩個(gè)串比較大小D.找某子串在主串中第一次出現(xiàn)在的第一個(gè)位置9設(shè)串S1=“ABCDEFG“S2

7、=“PQRST“則ConcatStr(SubStr(S12LenStr(S2))SubStr(S1LenStr(S2)2))。A.BCDEFB.BCDEFEFC.BCPQRSTD.BCDEFG10樹最適合用來表示（）。A有序數(shù)據(jù)元素B無序數(shù)據(jù)元素得分評(píng)卷人一、判斷題（每題1分，共10分）得分評(píng)卷人二、填空題（每空2分，共20分）得分評(píng)卷人三、選擇題（每題2分，共40分）院系:________班級(jí):__________姓名:_______

8、_______學(xué)號(hào):_____________…….……………………….密…………………封…………………線…………………………ABCEFGH本試卷共12頁(yè)第5頁(yè)本試卷共12頁(yè)第6頁(yè)3.假定用一個(gè)循環(huán)單鏈表表示一個(gè)循環(huán)隊(duì)列，該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針rear，試填空完成向循環(huán)隊(duì)列中插入一個(gè)元素為x的結(jié)點(diǎn)的函數(shù)。typedefstructqueuenode定義隊(duì)列的存儲(chǔ)結(jié)構(gòu)intdatastructqueuenodenextquInQueue(

9、qurearintx)向隊(duì)列插入元素為x的函數(shù)quheadss=1sdata=2if(rear==NULL)循環(huán)隊(duì)列為空，則建立一個(gè)結(jié)點(diǎn)的循環(huán)隊(duì)列rear=srearnextelsehead=3循環(huán)隊(duì)列非空，則將s插到后面rearnext=4rear=s5=head4根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。F=（D，R），其中：D=50，25，64，57，82，36，75，55，R=1將圖a中的二叉樹轉(zhuǎn)換成森林（2分），