數(shù)據(jù)結(jié)構(gòu)代碼課程類別必

專業(yè)班級(jí)學(xué)學(xué)生簽試卷編號(hào) 數(shù)據(jù)結(jié) 課 課程類別：題—二三四五六七八九十總題題—二三四五六七八九十總題得考生注意事項(xiàng)：1、本試卷共7頁(yè)，總分 分，考試時(shí)間120分鐘一、選擇題2，共30 假設(shè)某算法語(yǔ)句總的執(zhí)行次數(shù)為T(n)=6n4+n3+n2,那么該算法的時(shí)間復(fù)雜性量級(jí)為(C 線性表采用順序結(jié)構(gòu)時(shí)，其地址 必須是連續(xù) B)部分地址必須是連續(xù)C)一定是不連續(xù) D)連續(xù)與否均可從物理結(jié)構(gòu)上可以把數(shù)據(jù)結(jié)構(gòu)分為（B B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) 在順序線性表（a1,a2,···,a29,a30）中，在a20之前插入一個(gè)新的結(jié)點(diǎn)，需 B) C) D)結(jié)點(diǎn)的單循環(huán)鏈表為空的條件是 棧S最多能容納4個(gè)元素?，F(xiàn)在6個(gè)元素按A、B、C、D、E、F的順序進(jìn) B) B)A、F、E、D、C、C)C、B、E、D、A、 D)C、D、B、F、E、深度為K的二叉樹(shù)最多有( )個(gè)結(jié)點(diǎn) 2K 2Kn個(gè)頂點(diǎn)的無(wú)向完全圖的弧數(shù)為 )n(n- n(n-1)在一個(gè)圖中，圖的邊數(shù)等于所有頂點(diǎn)的度數(shù)之和的 )倍 圖的廣度優(yōu)先遍歷類似于二叉樹(shù)的（ 先序遍 B)中序遍 C)層次遍 D)后序遍在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，其結(jié)點(diǎn)總數(shù)為 不確 D)2n-100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)136B) D)利用逐點(diǎn)插入法建立序列(50，72，43，85，5，20，35，5，65，3)對(duì)應(yīng)的二叉排序樹(shù)以后，查找元素35要進(jìn)行（A ）元素間的比較。4 5 7 10在順序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找關(guān)鍵碼值 鏈表適用于（ 順 二分 順序，也能二分 D)隨二、填空題（每空1分,20分通常是以算法執(zhí)行所耗費(fèi)的時(shí) 和所占用的空間來(lái)判斷一個(gè)算法的優(yōu)劣隊(duì)列中允許進(jìn)行刪除的一端 隊(duì) n個(gè)頂點(diǎn)的連通圖的生成樹(shù) n- 條邊后綴算式 2 +-6 /*的值為_(kāi) _。中綴算式（8--4*Y/7對(duì)應(yīng)的后綴算式為8XY*-4 若要求一個(gè)稀疏圖G的最小生成樹(shù)，最好用克魯斯卡爾個(gè)點(diǎn)若進(jìn)棧序列為a,b,c，則通過(guò)入出棧操作可能得到的a,個(gè)點(diǎn)1這棵樹(shù)的根結(jié)點(diǎn)是（9）A1這棵樹(shù)的葉子結(jié)點(diǎn) 結(jié)點(diǎn)A3的度 （11）這棵樹(shù)的度 這棵樹(shù)的深度 結(jié)點(diǎn)A3的 （14）結(jié)點(diǎn)A3的父結(jié)點(diǎn) （15）葉678個(gè)結(jié)點(diǎn)，則共有葉假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18，則它的最小深度為 ，最大深度為 若要求一個(gè)稠密圖G的最小生成樹(shù)，最好 普里 算法來(lái)求解n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣，則空間復(fù)雜度 三、構(gòu)造題(每 分，共34分DS（5分DS=(D, D={a,b,c,d,e,f R={TT={<a,b>,<c,b>,<d,c>,<d,f>,<e,d>,<f,a>,<f,e>（5分）（10分（10012345001234505726圖 圖給定網(wǎng)G3G的最小生成樹(shù)，畫出其邏輯結(jié)構(gòu)圖（4分四、編程題（共16分1、寫一算法，從順序表中插入自第i個(gè)元素開(kāi)始的k（已知給定抽象數(shù)據(jù)類型及算法參數(shù)，ka中，請(qǐng)補(bǔ)充完成下面算法typedefStruct{int