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

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