2008數(shù)據(jù)結(jié)構(gòu)試卷

你一定要堅(jiān)強(qiáng)，即使受過傷，流過淚，也能咬牙走下去。因?yàn)?，人生，就是你一個(gè)人的人生。==============================================================================PAGE命運(yùn)如同手中的掌紋，無論多曲折，終掌握在自己手中==============================================================學(xué)院商學(xué)院專業(yè)班級(jí)學(xué)號(hào)姓名○○○○…………評(píng)卷密封線………………密封線內(nèi)不要答題，密封線外不準(zhǔn)填寫考生信息，違者考試成績(jī)按0分處理………………評(píng)卷密封線…………中南大學(xué)考試試卷2009~2010學(xué)年2學(xué)期數(shù)據(jù)結(jié)構(gòu)課程時(shí)間100分鐘48學(xué)時(shí)，3學(xué)分，閉卷，總分100分，占總評(píng)成績(jī)70%題號(hào)一二三四五六七八九十合計(jì)得分評(píng)卷人復(fù)查人（注：直接在試卷上答題?。。。┑梅衷u(píng)卷人一、填空題(本題20分，每空1分)1.以折半查找方法查找一個(gè)線性表時(shí)，此線性表必須是__________存儲(chǔ)的________表。2.內(nèi)部排序分為插入、交換、選擇、_______、_______排序五類。3.在長(zhǎng)度為n的順序表中，刪除第i個(gè)元素時(shí)需要移動(dòng)元素的個(gè)數(shù)為_______。4.假設(shè)以數(shù)組Q[0..m-1]存放循環(huán)隊(duì)列的元素,若判斷隊(duì)空的條件為“rear==front”，則判斷隊(duì)滿的條件為。5.棧的操作特點(diǎn)為____；若已知進(jìn)棧序列為123456，則能否得到345612____、123456____、216534____的出棧序列(能/不能)。6.若給定數(shù)組T[0..7]的各元素值分別為：a,b,c,d,e,f,g,h，按這些值建立的完全二叉樹的先序遍歷結(jié)果序列為______,中序遍歷結(jié)果序列為______，后序遍歷結(jié)果序列為______。7.深度為7的滿二叉樹有___個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個(gè)數(shù)為_________。8.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，該線性表宜采用_______存儲(chǔ)結(jié)構(gòu)。9.中綴表達(dá)式A-(B+C/D)*E的前綴形式是______，其后綴形式是______。10.在頭指針為head的帶頭結(jié)點(diǎn)的單鏈表的第一個(gè)元素結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)q的主要操作步驟是___________；____________（設(shè)各結(jié)點(diǎn)的指針域?yàn)閘ink）。得分評(píng)卷人二、計(jì)算題（5分）1.已知一棵度為m的樹中有：n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…，nm個(gè)度為m的結(jié)點(diǎn)，求該樹中葉結(jié)點(diǎn)的個(gè)數(shù)。（5分）三、四、得分評(píng)卷人三、構(gòu)圖題(本題35分)1.假設(shè)字符集SET={a,b,c,d,e,f,g,h}中各字符的使用頻度分別是｛0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10｝。試用哈夫曼（huffman）算法設(shè)計(jì)一套二進(jìn)制編碼。要求：（1）畫出哈夫曼樹；（要求有完整構(gòu)造過程）（2）給出SET中各字符的編碼表。（10分）2.從空樹起，依次插入關(guān)鍵字48，18，27，45，42，46，22，47；構(gòu)造一棵二叉排序樹。畫出該二叉排序樹；（5分）3.寫出下面這棵普通樹的先根及后根遍歷結(jié)果，并將之轉(zhuǎn)化為二叉樹。（要求：畫出轉(zhuǎn)化過程）（10分）①②③④⑤⑥⑦⑧⑨學(xué)院商學(xué)院專業(yè)班級(jí)學(xué)號(hào)姓名○○○○…………評(píng)卷密封線………………密封線內(nèi)不要答題，密封線外不準(zhǔn)填寫考生信息，違者考試成績(jī)按0分處理………………評(píng)卷密封線…………4.寫出序列{46，56，38，40，80，36，75，66，84，24}按快速排序方法的第一趟排序過程及其它各趟排序結(jié)果。（10分）（結(jié)果按非降序排列?。┑梅衷u(píng)卷人四、Hash表（本題15分）1.設(shè)有關(guān)鍵字序列K=19，01，23，14，55，20，84，27，68，11，10，77；存放在地址空間為100～116的散列表中，試設(shè)計(jì)哈希函數(shù)，使之沒有沖突或沖突盡可能少。（3分）2.設(shè)有哈希函數(shù)H（K）=K%11，將關(guān)鍵字序列{18,27,30,39,15,5,49,12}定位在0～10的地址空間。（1）用線性探測(cè)法處理沖突以構(gòu)造哈希表，畫出其定位后的地址空間；并計(jì)算其ASLsucc值。（2）用鏈地址法處理沖突以構(gòu)造哈希表，畫出其定位后的地址空間；并計(jì)算其ASLsucc值。（12分）（注：ASLsucc為成功查找時(shí)的平均查找長(zhǎng)度。）得分評(píng)卷人五、算法設(shè)計(jì)題（本題25分）1.已知帶頭結(jié)點(diǎn)的單鏈表中元素包含有三類字符：字母（大、小寫均有）、數(shù)字、其它字符；設(shè)計(jì)構(gòu)造三個(gè)以單鏈表表示的線性