數(shù)據(jù)結(jié)構(gòu)模擬抽卷

ii一單項(xiàng)選題(每2分,共0)i（）A．單鏈表B.順序C.循環(huán)鏈表設(shè)和rs算是一有個(gè)子結(jié)點(diǎn)的完二叉樹，至多（）個(gè)結(jié)點(diǎn)。A．C．247適于動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)）A有序表B．分塊有序表C二叉排序樹．線性鏈表由一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹()其形態(tài)不一定相同，但平均查找長(zhǎng)度相同其態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同C.其態(tài)均相同，平均查找長(zhǎng)度不一定相同其態(tài)均相同，均查找長(zhǎng)度也都相同知是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若入結(jié)點(diǎn)，則行A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;由一關(guān)鍵字集合構(gòu)造的各棵二叉排序其形態(tài)不一定相同，但平均查找長(zhǎng)度相同其形態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同C.其態(tài)均相同，平均查找長(zhǎng)度不一定相同其態(tài)均相同，均查找長(zhǎng)度也都相同

與第5相同假一個(gè)有n頂點(diǎn)和條弧的有向圖用鄰接表表,刪除與某個(gè)頂點(diǎn)v相關(guān)的所有弧的時(shí)間復(fù)雜度AO(n)B．O(e)．O(n+e)D．（4種基本類型。我們的材上沒有關(guān)內(nèi)容A.B.數(shù)組C.集合D.索引在度的序表中插入個(gè)元素等率情況下的平均移動(dòng)元素的次數(shù)（）（）二判斷題(每分共10分)2，則該。)二樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等1。)一無向連通圖的生成樹是圖的極小的連通子圖）棵B1。()()()()排序樹的形態(tài)與。()

如果采用如下方法定義一維字符數(shù)組：

此題可以刪/

intmaxSize=30;char*a=newchar[maxSize];則這種數(shù)組在程序執(zhí)行過程中不能擴(kuò)充。（）使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲(chǔ)空間。）三填空題(每分共20分)設(shè)鍵字序列（17,8,13,25,24,16,3191希排序法按升序排序，用初始增4進(jìn)行趟排序后的結(jié)果是()n()條邊。則在三元組表中每個(gè)三元組元素對(duì)應(yīng)一)。()個(gè)n陣址及元素所占存儲(chǔ)單元[i][j]為()。()普姆算法適用于求（）網(wǎng)最小生成樹。設(shè)列25,36,40,45,48,56,60,68,72,85}，用折半查找方法查找36時(shí)，所需比較的次數(shù)（設(shè)鍵字序{7,12,26,30,47,58,66,70,82,90}當(dāng)用折半查找方法查找時(shí)，所需比較的次數(shù)次的關(guān)鍵字分別是（在向G的鄰接矩陣表示，j列中非零元的個(gè)數(shù)等于該頂點(diǎn)（四應(yīng)用題(每8分,共3分)已一AOV網(wǎng)如圖所示。(1)試畫出它的鄰接鏈表點(diǎn)遞減出現(xiàn)在各鄰接表中）(2)試寫出按照拓?fù)渑判蛩惴ǖ玫耐負(fù)湫蛄小1V4

V2V3V5V6閱下列算法，并回答問題：（1、Q1和Q都是隊(duì)列結(jié)構(gòu)，設(shè)隊(duì)（，0-5，1隊(duì)頭元素，寫出執(zhí)f31(&Q,&Q1,&Q2)之隊(duì)QQ1和Q的狀態(tài)；（2簡(jiǎn)述算f31的功能。（注：、EnQueue、和Q分別是隊(duì)列初始化、入列、出隊(duì)和判隊(duì)空的操作）void(Queue*Q,Queue*Q1,{inte;lnitQueuelnitQueue(!QueueEmpty(Q)){/

(Q);if(e>=0)EnQueue(Q1,e);EnQueue(Q2,e)}}對(duì)鍵字序(5，，，，，，2，7)按從小到大進(jìn)行快速排序。(1)寫出排序過程中前兩趟的劃結(jié)果；(2)快速排序是否是穩(wěn)定的排序?假一棵樹的先根序列為ABCEFIJGHKD后根序列B。畫出該樹。該題建議改為：假設(shè)一棵二叉樹的先根序列為ABCEFIJGHKD中根序列B。畫出該二叉樹。五算法設(shè)題共18）假一線性表由Fibonacci數(shù)列的前（n3項(xiàng)構(gòu)成，試以帶表頭結(jié)點(diǎn)的單鏈表作該線性表的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)算法建立該單鏈