數(shù)據(jù)結(jié)構(gòu)試卷A(2012專升本).doc

線訂裝鄭州輕工業(yè)學(xué)院 / 學(xué)年 第 學(xué)期 試卷專業(yè)年級(jí)及班級(jí)姓名學(xué)號(hào)2012-2013學(xué)年第一學(xué)期期末考試試卷數(shù)據(jù)結(jié)構(gòu)試卷A 一、選擇題（每題2分，共30分）1一種抽象數(shù)據(jù)類型包括數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和【 】三部分。A數(shù)據(jù)抽象 B基本操作 C數(shù)據(jù)元素 D類型說(shuō)明2在一個(gè)長(zhǎng)度為n的順序表中插入一個(gè)元素的算法的時(shí)間復(fù)雜度為【 】。AO（1）B（log n）CO（n）DO（n2）3. 指針p1和p2分別指向兩個(gè)無(wú)頭結(jié)點(diǎn)的非空單循環(huán)鏈表中的尾結(jié)點(diǎn)，要將兩個(gè)鏈表鏈接成一個(gè)新的單循環(huán)鏈表，應(yīng)執(zhí)行的操作為【 】。Ap1next=p2next; p2next=p1next;Bp2next=p1next; p1next=p2next;Cp=p2next; p1next=p; p2next=p1next;Dp=p1next; p1next= p2next; p2next=p;4設(shè)棧的初始狀態(tài)為空，入棧序列為1，2，3，4，5，6，若出棧序列為2，4，3，6，5，1，則操作過(guò)程中棧中元素個(gè)數(shù)最多時(shí)為【 】。A2個(gè)B3個(gè)C4個(gè)D6個(gè)5隊(duì)列的特點(diǎn)是【 】。A允許在表的任何位置進(jìn)行插入和刪除B只允許在表的一端進(jìn)行插入和刪除C允許在表的兩端進(jìn)行插入和刪除D只允許在表的一端進(jìn)行插入，在另一端進(jìn)行刪除6設(shè)有一個(gè)二維數(shù)組A1020，按行存放于一個(gè)連續(xù)的存儲(chǔ)空間中，A00的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字節(jié)，則A62的地址為【 】。A226 B322 C341 D342線訂裝鄭州輕工業(yè)學(xué)院 / 學(xué)年 第 學(xué)期 試卷專業(yè)年級(jí)及班級(jí)姓名學(xué)號(hào)7遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為【 】的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D線性表8在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是【 】。A折半查找 B二叉排序樹(shù)查找 C散列查找 D順序查找9對(duì)有序表進(jìn)行折半查找成功時(shí)，元素比較的次數(shù)【 】。A僅與表中元素的值有關(guān) B僅與表的長(zhǎng)度和被查元素的位置有關(guān)C僅與被查元素的值有關(guān) D僅與表中元素按升序或降序排列有關(guān)10快速排序執(zhí)行兩趟之后，已經(jīng)到位的元素個(gè)數(shù)是【 】。A1B3CD11下列序列不為堆的是【 】。 A75, 45, 65, 30, 15, 25 B75, 65, 45, 30, 25, 15 C75, 65, 30, l5, 25, 45 D75, 45, 65, 25, 30, 1512森林轉(zhuǎn)換為二叉樹(shù)后，從根結(jié)點(diǎn)開(kāi)始一直沿著右子樹(shù)下去，一共有4個(gè)結(jié)點(diǎn)，表明【 】。A 森林有4棵樹(shù) B 森林的最多深度為4C 森林的第一棵樹(shù)有4層 D森林有4個(gè)結(jié)點(diǎn)13關(guān)鍵路徑是AOE網(wǎng)中【 】。A從始點(diǎn)到終點(diǎn)的最短路徑 B從始點(diǎn)到終點(diǎn)的最長(zhǎng)路徑 C從始點(diǎn)到終點(diǎn)的邊數(shù)最多的路徑 D從始點(diǎn)到終點(diǎn)的邊數(shù)最少的路徑14有數(shù)據(jù)57，35，40，19，45，24，100，從空二叉樹(shù)開(kāi)始逐個(gè)插入數(shù)據(jù)來(lái)形成二叉排序樹(shù)，若希望高度最小，則應(yīng)選擇下面哪個(gè)序列插入【 】。A45，24，57，19，40，100，35 B40，24，19，35，57，45，100 C19，24，35，40，45，57，100 D35，24，19，40，45，100，5715下列哪一個(gè)選項(xiàng)不是圖1所示的有向圖的拓?fù)渑判虻慕Y(jié)果【 】。BACDEFAAFBCDE BFABCDECFACBDE DFADBCE圖1二、應(yīng)用題（6題，共50分）1（4分）線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，而是鏈表。試問(wèn)：（1）如果有n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)的改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？（2）若線性表的總數(shù)基本穩(wěn)定，其很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？ 2.（8分）已知一棵二叉樹(shù)的中序遍歷結(jié)果為GDHBAECIF，后序遍歷結(jié)果為GHDBEIFCA，請(qǐng)畫出該二叉樹(shù)，并寫出其先序遍歷序列3(12分）根據(jù)下圖所示的無(wú)向帶權(quán)圖回答下列問(wèn)題：（1）寫出它的鄰接矩陣（按照字母序依次存放）。（2）畫出其最小生成樹(shù)（給出生成最少生成樹(shù)過(guò)程的示意圖）。（3）給出從頂點(diǎn)a出發(fā)深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷該圖的頂點(diǎn)序列（多個(gè)頂點(diǎn)可以選擇按字母序）。4.（10分） 假定用于通信的電文僅有8個(gè)字母C1，C2，.，C8組成，各字母在電文中出現(xiàn)的頻率分別為5, 25, 3, 6, 10, 11, 36, 4，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼樹(shù)，并計(jì)算該哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。5（10分）設(shè)有一組關(guān)鍵字29, 1, 13, 15, 56, 20, 87, 27, 69, 9, 10, 74。哈希函數(shù)為H（key)=key%17，采用線性探測(cè)法解決沖突。試在0-18的哈希地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算成功查找的平均查找長(zhǎng)度。6（6分）將下面的二叉樹(shù)轉(zhuǎn)換為一棵樹(shù)。三、編程題（2題，每題10分，共20分）1（5分）在順序表中求值為X的元素個(gè)數(shù)。typedef structelemtype *elem;int length;int listsize;SqList; int Count_Num(SqList L,elemtype X)int n=0; （請(qǐng)完成）return n;2（7分）設(shè)在一個(gè)帶表頭結(jié)點(diǎn)的單鏈表中所有元素結(jié)點(diǎn)的數(shù)據(jù)值按遞增順序排列，試完成下列函數(shù)，刪除表中所有大于min，小于max的元素（若存在）。 typedef struct LNode ElemType data; struct LNode *next; LNode，*LinkList; void rangeDelete (LinkList L, ElemType min, ElemType max ) LNode * pr ，*p ； pr = L，p= L-next； （請(qǐng)完成） 3. （8分）給出算法分別求出二叉樹(shù)的葉結(jié)點(diǎn)、度為1的結(jié)點(diǎn)、度為2的結(jié)