2007學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)考試試卷卷

1、安徽大學(xué)20 07 20 08 學(xué)年第 二 學(xué)期數(shù)據(jù)結(jié)構(gòu)考試試卷（A卷）（閉卷 時(shí)間120分鐘）一、單項(xiàng)選擇題（每小題1，共10分）1算法分析的目的是 。A找出數(shù)據(jù)結(jié)構(gòu)的合理性B分析算法的正確性C分析算法的時(shí)間和空間效率D分析算法的可讀性2帶頭結(jié)點(diǎn)的單鏈表head為空的條件是 。Ahead= =NULLBheadnext= =NULL Cheadnext = =headDhead！= NULL3棧和隊(duì)列的共同點(diǎn)是 。A先進(jìn)先出B后進(jìn)先出C只能在一端進(jìn)行插入和刪除D限制存取點(diǎn)的線性表 4. 在數(shù)組A中,每個(gè)元素占3個(gè)字節(jié),行下標(biāo)i從1到8,列下標(biāo)j從1 到10,從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器中

2、,該數(shù)組按列存放時(shí),元素A85的起始地址為 。ASA+117BSA+120CSA+144DSA+1415廣義表（a,b），c,d）的表頭是 。AaB （a）C （a,b）D （a）6若某二叉樹的 中序序列為 dgbaechf，后序序列為 gdbehfca，則先序序列是 。AabdgcefhBgdbecfhaCadbehfcgDabdgechf7若一棵哈夫曼樹的結(jié)點(diǎn)總數(shù)為2001個(gè)，則它有（ ）葉子結(jié)點(diǎn)。A999 B1000 C1001 D10028已知有向圖的鄰接表如下所示，從頂點(diǎn)v1出發(fā)，得到的DFS序列為 。AAV1，V2，V3，V4，V5BV1，V2，V3，V5，V4CV1，V3，V4，

3、V5，V2DV1，V4，V3，V5，V21324234545249折半查找法適合于存儲(chǔ)結(jié)構(gòu)為 的線性表。A順序存儲(chǔ)B散列存儲(chǔ)C二叉樹D鏈?zhǔn)酱鎯?chǔ)10設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用 。A冒泡排序法B快速排序法C堆排序法D插入排序法二、填空題（每題1 分，共10 分）1下面程序段中語(yǔ)句 x+ 的執(zhí)行次數(shù)是 。for（i=1；in；i+） y=y+1； for（j=0；j=2*（n+1）；j+） x+；2在單鏈表L中設(shè)立頭結(jié)點(diǎn)的作用是 。3 一個(gè)棧的輸入序列為1，2，3，4，得到的輸出序列4，1，2，3是 的。4引入循環(huán)隊(duì)列的目的是 。5若采用三元組壓

4、縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置，這種說(shuō)法是 。6廣義表的表尾是廣義表，這種說(shuō)法是 。7根據(jù)二叉樹的定義，n個(gè)結(jié)點(diǎn)的二叉樹的不同形態(tài)有 。8圖的DFS和BFS遍歷得到的結(jié)點(diǎn)序列不唯一，與 有關(guān)。9 用二叉排序樹查找，在最壞情形下的性能時(shí)間與 相同。10已知序列54，38，96，23，15，72，60，45，83，采用直接插入排序，將60插入到有序子區(qū)間時(shí)，為尋找插入位置需比較 次。得分得分三、分析應(yīng)用題 （每題5分，共20分） 1閱讀以下算法，按要求回答問(wèn)題。 func （int a，int n，int x） int i，j；if（x=an-1）

5、an=x；else i=0； while（x=ai）i+； for（j=n-1；j=i；j-）aj+1=aj； ai=x； n+；return n；該算法的功能是 。2 寫出以下程序段的輸出結(jié)果（隊(duì)列中的元素類型為char，EnQueue（Q，x）表示元素x進(jìn)隊(duì)Q，DeQueue（Q，x）表示隊(duì)頭元素出隊(duì)后保存在x中） void main（） char x=e, y=c ;EnQueue（Q，h）; EnQueue（Q，r）; EnQueue（Q，y）;DeQueue（Q，x）; EnQueue（Q，x）；DeQueue（Q，x）；EnQueue（Q，a）;while (!QueueEmpty

6、(Q) DeQueue（Q，y）; printf (y);Printf(x); 05054163268151349201051612 GEDCFGEDCFBAIJHIJHLMKLMK四、 解答題（每題10分，共40分） 1已知二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下圖所示：1234567891011121314151617181920eafdgcjhib 畫出二叉樹T的邏輯結(jié)構(gòu)圖； 寫出按先序、中序和后序遍歷T所得到的結(jié)點(diǎn)序列； 畫出后序線索樹。2已知一個(gè)無(wú)向圖的頂點(diǎn)集為a, b, c, d, e ,其鄰接矩陣如下所示(1) 畫出該圖的圖形； (2) 根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫

7、出相應(yīng)的遍歷序列。3設(shè)下列關(guān)鍵字構(gòu)造哈希表（hash）表，的地址范圍為017，關(guān)鍵字序列為10，24，32，17，31，30，46，47，40，63，49，計(jì)算裝填因子； 利用除留余法構(gòu)造hash函數(shù)； 利用線性探測(cè)再散列法解決沖突，構(gòu)造hash表填入下表；01234567891011121314151617 查找關(guān)鍵字32，與哪些元素比較？ 計(jì)算在等概率情形下，查找成功的ASL。4設(shè)關(guān)鍵字序列為503，087，512，061，908，170，897，275，653，426手工執(zhí)行shell排序（d1=5）和快速排序，請(qǐng)寫出第一趟排序結(jié)束時(shí)關(guān)鍵字的狀態(tài)填入下表。初始503087512061908170897275653426第一趟初始503087512061908170897275653426d1=5五、設(shè)計(jì)題（每題10分，共20分）寫出鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的