數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)總結(jié)(已修改)
2025-04-29 01:36 本頁(yè)面
【正文】 1204班 學(xué)委精心整理 數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)《數(shù)據(jù)結(jié)構(gòu)》期末考試題型及分值（1）簡(jiǎn)答題 6題*5分=30分 簡(jiǎn)要回答要點(diǎn) （2）分析題 6題*5分=30分 給出結(jié)果（3）設(shè)計(jì)題 1題*10分=10分 設(shè)計(jì)思想及結(jié)果（4）編程題 1題*10分=10分 完整代碼（5）綜合題 1題*20分=20分 抽象數(shù)據(jù)類型的定義、表示、實(shí)現(xiàn)、算法分析 {定義=功能（ADT） 表示=存儲(chǔ)結(jié)構(gòu)體 實(shí)現(xiàn)=算法（基本操作）算法分析=時(shí)間、空間復(fù)雜度}考試概念有： {一、線性表（棧隊(duì)列串?dāng)?shù)組廣義表邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)運(yùn)算結(jié)構(gòu)） 二、非線性表（集合樹圖）} 數(shù)據(jù)對(duì)象數(shù)據(jù)關(guān)系基本操作 性質(zhì)要求（設(shè)計(jì)）效率（度量） 查找：高效查找算法 排序：高效的排序算法 分析題考試題目參考 （1）123456順序建BBST （2）654321順序建BBST 簡(jiǎn)答題實(shí)例 設(shè)計(jì)題：（1）（2）數(shù)據(jù)結(jié)構(gòu)試卷（一）三、計(jì)算題（每題 6 分，共24分）1. 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A [0].next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next3572041線性表為：（78，50，40，60，34，90）2. 請(qǐng)畫出下圖的鄰接矩陣和鄰接表。3. 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7}。 E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}。 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20, 2, 5, 8, 3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。見圖124444422255285283452843 圖12 圖11四、閱讀算法（每題7分，共14分）1. LinkList mynote(LinkList L) {//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(Lamp。amp。Lnext){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－next=q；q－next=NULL； } return L； } 請(qǐng)回答下列問題： （1）說明語(yǔ)句S1的功能；查詢鏈表的尾結(jié)點(diǎn) （2）說明語(yǔ)句組S2的功能；將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）設(shè)鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。返回的線性表為（a2,a3,…,an,a1）2. void ABC(BTNode * BT){ if BT { ABC (BTleft)。 ABC (BTright)。 coutBTdata39。 39。 } } 該算法的功能是：遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹五、算法填空（共8分）二叉搜索樹的查找——遞歸算法:bool Find(BTreeNode* BST,ElemTypeamp。 item){ if (BST==NULL) return false。 //查找失敗 else { if (item==BSTdata){ item=BSTdata。//查找成功 return __ true __。} else if(itemBSTdata) return Find(___BSTleft __,item)。 else return Find(____BSTright __,item)。 }//if}六、編寫算法（共8分）統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。 int CountX(LNode* HL,ElemType x)int CountX(LNode* HL,ElemType x) { int i=0。 LNode* p=HL。//i為計(jì)數(shù)器 while(p!=NULL) { if (Pdata==x) i++。 p=pnext。 }//while, 出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) return i。 }//CountX數(shù)據(jù)結(jié)構(gòu)試卷（二）三、應(yīng)用題(36分)1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。(22，40，45，48，80，78)，(40，45，48，80，22，78)2． 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink）。qllink=p。 qrlink=prlink。 prlinkllink=q。 prlink=q。3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。2,ASL=91*1+2*2+3*4+4*2)=25/94． 設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹略5． 設(shè)有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計(jì)題(16分) 1． 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。void quickpass(int r[], int s, int t){ int i=s, j=t, x=r[s]。 while(ij){while (ij amp。amp。 r[j]x) j=j1。 if (ij) {r[i]=r[j]。i=i+1。} while (ij amp。amp。 r[i]x) i=i+1。 if (ij) {r[j]=r[i]。j=j1。} } r[i]=x。}2． 設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。typedef struct node {int data。 struct node *next。}lklist。void intersection(lklist *ha,lklist *hb,lklist *amp。hc){lklist *p,*q,*t。for(p=ha,hc=0。p!=0。p=pnext){ for(q=hb。q!=0。q=qnext) if (qdata==pdata) break。if(q!=0){ t=(lklist *)malloc(sizeof(lklist))。 tdata=pdata。tnext=hc。 hc=t。}}}數(shù)據(jù)結(jié)構(gòu)試卷（三）三、計(jì)算題(每題10分，共30分)，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1