1、詼卷 二、填空題（每空1分，共28分）1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互 ZI可的 :當(dāng)結(jié)點(diǎn)Z間存在M對N （M : N）的聯(lián)系時，稱這種結(jié)構(gòu)為.2. 隊(duì)列的插入操作是在隊(duì)列的一尾 進(jìn)行，刪除操作是在隊(duì)列的一首 進(jìn)行。3. 當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示棧空，則表示棧滿的條件是_ top=0o4. 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為 ,在表尾插入元素的時間復(fù)雜度為 。7. 二叉樹是指度為2的樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)點(diǎn)的度的總和,對一棵由算術(shù)表達(dá)式是o&對一棵二叉搜索樹進(jìn)行屮序遍歷時，得到的結(jié)點(diǎn)序列是一個 紐成的二叉語法樹進(jìn)行后序遍

2、歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的9. 對于一棵具有n個結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為 個，其小個用于指向孩子， 個指針是空閑的。10. 若對一棵完全二叉樹從 0開始進(jìn)行結(jié)點(diǎn)的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點(diǎn)存儲到A10JJ。其余類推，則 A i J元索的左孩了元素為 ，右孩子元索為，雙親元索為。11. 在線性表的散列存儲中，處理沖突的常用方法有 和兩種。三、運(yùn)算題（每題6分，共24分）1. 己知一個6x5稀疏矩陣如下所示，試:（1）寫出它的三元組線性表；0 0 0 0 00-100 0 0000-25 00 00 07 0（2）給出三元組線性表的順序存

3、儲表示。2. 設(shè)有一個輸入數(shù)據(jù)的序列是 46,25,7& 62,12,80 ，試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。03. 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點(diǎn)鄰接表中0的 邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小到大的次序鏈接的，試寫出：從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；己知一個圖的頂點(diǎn)集V利邊集E分別為:從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生 成樹；V 二1,2,3,4,5,6,7;E= ,3,2x,v6,1 ,v6,2,v6,5;若存儲它采用鄰接表，并且每個頂點(diǎn)鄰接表中的邊 結(jié)點(diǎn)都是按照終點(diǎn)序號從小到大的次序鏈接的，排序的序列。按主教 材屮介紹的拓樸

4、排序算法進(jìn)行排序，試給出得到的拓樸1. int Prime(i nt n) int i=l:int x=(i nt) sqrt (n);while (+iv=x)if (n %i=O) break;if (ix) retur n 1;else return 0;)(1) 指出該算法的功能；(2) 該算法的時間復(fù)雜度是多少?2. 寫出下述算法的功能：void AJ(adjlist GL, i nt i, i nt n) Queue Q;Ini tQueue(Q);cout?i?，visitedij=true;Qinsert(Q,i)；while( !QueueEmpty(Q) int k=QDe

5、lete(Q);edge node* p=GLkJ; while(p!=NULL) in t j=p-adjvex;if(! visited j) cout?j?rvisited |jj=true;Qin sert(QJ);)p=p- next;）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。ElemType DeleFro nt（LNode * & HL）參考答案7.圖7有序有序序列后綴表達(dá)式（或逆波二式）2n n-1n+12i+l2i+2()/2開放定址法鏈接法歸并快速運(yùn)算題（每題6分，共24分）二、填空題（每空1分，共26分）聯(lián)1.系圖尾首top或圖結(jié)2.O（ 1）構(gòu)）3.128444.

6、33O (n)5.1086.1. (1)(1,5,1),(32J),(4,5,? 2),(5 丄 5),(6,3,7)(3 分)(2)三兀組線性表的順序存儲表示如圖7示。(a) next;ElemType lemp=p-data;delete p;return temp;)試卷十三一.選擇題(30分)1. 下列程序段的時間復(fù)雜度為()。for(i=0 ；im ；i+) for(j=0 ；jt ；j+) ci|j=O；for(i=0 ；im ；i+) for(j=0 ；jt ；j+) for(k=()； kright=s ； s-lcft=p ； p-right-lcft=s ； s? righ

7、t=p? right ；(B) s-left=p ； s-right=p-right ； p-right=s ； p-right-left=s ；(C) p-right=s: p-right-left=s ； s-left=p ； s-right=p-right ；(D) s-lcft=p ； s-right=p-right ； p-right-lcft=s ； p-right=s ；7. 設(shè)輸入序列1、2、3n經(jīng)過棧作用后，輸出序列中的第一個元秦是n,則輸出序列中的第i個輸出元素是()。(A) n-i(B) n-l -i(C) n+1 -i(D)不能確定8. 設(shè)散列表中有m個存儲單元,散列函

8、數(shù)H(key)= key % p,則p最好選擇()。(A)小于等于m的最大奇數(shù)(B)小于等于m的最大素?cái)?shù)(C)小于等于m的最大偶數(shù)(D)小于等于m的最人合數(shù)9. 設(shè)在一棵度數(shù)為3的樹屮，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個， 那么度數(shù)為()的結(jié)點(diǎn)數(shù)有()個。(A)4(B)5(C)610?設(shè)完全無向圖中冇 n 個頂點(diǎn)，則該完全無向圖屮冇 () 條邊。(D)7(D) (n-l)/2(A) n(n-l)/2(B) n(n-l)(C) n(n+l)/214?設(shè)冇向無環(huán)圖G小的冇向邊集合E=(, , , ,則下列屬于該冇向圖 G的一種拓?fù)渑判蛐蛄械氖?)。(A) 1,

9、2. 3, 4(B)2, 3, 4, 1(C) 1,4, 2, 3(D) I, 2, 4, 3二.填空題(30分)1. 設(shè)指針p指向單鏈農(nóng)中結(jié)點(diǎn)A,指針s指向被插入的結(jié)點(diǎn)X,貝I在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時的操作序列為：l)s-nexl= ； 2) p-next=s ； 3) t=p-data ； 4) p-data=； 5) s-data=t;2. 設(shè)某棵完全二叉樹中有100個結(jié)點(diǎn)，則該二叉樹中有 個葉子結(jié)點(diǎn)。3?設(shè)某順序循環(huán)隊(duì)列中冇m個元素，口規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的耐一個位置，隊(duì)尾指針R指向隊(duì) 尾元素的當(dāng)前位直，則該循環(huán)隊(duì)列中最多存儲 隊(duì)列元素。6. 設(shè)一組初始記錄關(guān)鍵字序列為(20,

10、 12, 42, 31, 18, 14, 28)則根據(jù)這些記錄關(guān)鍵字構(gòu)適的二叉排序樹的平均查找長度是 。7. 設(shè)一棵二叉樹的中序遍歷序列為BDCA,后序遍歷序列為DBAC,則這棵二叉樹的前序序列為8. 設(shè)川丁 ？通信的電文僅由 8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10, 根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為 o10.設(shè)無向圖G (如右圖所示)，則其最小生成樹上所有邊的權(quán)值Z和為 五.算法設(shè)計(jì)題(20分)19/71 ?設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。2. 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù) Z前的算法。3. 設(shè)計(jì)判斷單鏈表中元素是否是遞增

11、的算法。參考答案二、填空題1. p-nextt sodala 2?50 3.m-1 4.6, 8 5.快速，堆 6?7. CBDA8. 6 9.(24, 65, 33, 8(), 70, 56, 48)10.8四.算法設(shè)計(jì)題1.設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。void sum(bitree *bt,i nt &s) if(bt!=0) s=s+bt-data; sum(bt-lchild,s); sum(bt-rchild,s);2. 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。void quickpass(i nt r, i nt s, i nt t)int i=s,j=t,x=rs;whi

12、le(ivj)(while (ij & rj%2=0)j=j-l; if(ij) ri=rj;i=i+l;while (ij & ri%2=l) i=i+l; if(in cxt=0) rctur n(l );clscfor(q=head,p=head-next; p!=0; q=p,p=p-next)if(q-datap-data) re (urn(0);return(l); 試卷十四二、填空題(48分，其中最后兩小題各 6分)L設(shè)需耍對5個不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較 次，至多需要比較次。m叉樹脂的結(jié)點(diǎn)數(shù)為 m用多重鏈衣農(nóng)示其存儲結(jié)構(gòu)，則該樹中冇 個空指針域。6. 設(shè)指針變量p

13、指向單鏈表中結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的語何序列為：q=p-next ； p-data=q? data； p-next= ； feee(q)；7. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基木類型： 、和o8. 設(shè)無向圖G屮有n個頂點(diǎn)e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍丿力時的時間復(fù)雜度為 ；用鄰接表作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時間復(fù)雜度為2?設(shè)有向圖 G中的有向邊的集合 E=, , , v4, 5, v5, 3, , ,則該圖的_個拓?fù)湫?列為o13.下而程序段的功能是建立二叉樹的算法，請?jiān)谙聞澗€處填上正確的內(nèi)容。typcdcf struct no de int data

14、;struct node *lchild; ;bitrcc;void createbitree(bitree *&bt)scanfT%c; &ch);if(ch=#):else bt=(bitree*)malloc(sizeof(bitree); bt-data=ch;crcatcbitrcc(bt-rchild);)1typedef struct p=(lklist *)malloc(sizeof(lklist);sca nfC 4%d,&(p-data);p- next=Oiif(i= l)head=q=p:else q-n ext=p;； 參考答案選擇題二、填空題1.4, 10 2.O( nl ogA n), O( n2) 3.n4.1, 2 5.n (m-l)+l 67.線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu)8.0(n2),O(n