PAGE1注意：填寫內(nèi)容不要超出以上格式,第二頁的邊距和第一頁一樣出題人(簽名)：__________室負責人(簽名)：_________東華大學(xué)2010~2011學(xué)年第1學(xué)期期末試題踏實學(xué)習，弘揚正氣；誠信做人，誠實考試；作弊可恥，后果自負。課程名稱數(shù)據(jù)結(jié)構(gòu)使用專業(yè)計算機科學(xué)與技術(shù)類班級_____________________姓名________________學(xué)號__________試題得分一二三四五六七八九十總分一、單項選擇題（每空2分，本題共40分）數(shù)據(jù)結(jié)構(gòu)是（D）。A、數(shù)據(jù) B、數(shù)據(jù)對象C、數(shù)據(jù)對象上的關(guān)系 D、由數(shù)據(jù)對象和其上的關(guān)系構(gòu)成的二元組2一個算法應(yīng)該是（

B）。A．程序

B．問題求解步驟的描述

C．數(shù)據(jù)結(jié)構(gòu)+程序

D．以上都不對3線性表是具有n個（C）的有限序列（n>0）。A．表元素

B．字符

C．數(shù)據(jù)元素

D．數(shù)據(jù)項

E．信息項4衡量查找算法好壞的依據(jù)是（A）。A．關(guān)鍵字和給定值進行過比較的記錄個數(shù)的平均值

B．占用的輔助空間C．數(shù)據(jù)元素移動次數(shù)

D．上述說法都不對5.穩(wěn)定的排序算法是（D）。A．排序后數(shù)據(jù)元素的個數(shù)不變

B．排序后數(shù)據(jù)元素的位置不變C．排序后數(shù)據(jù)元素間的關(guān)系不變

D．上述說法都不對6．若一個鏈棧的棧頂指針用top表示，當進行退棧時所進行的指針操作為(A)。A.top->next=top;B.top=top->next;C.top=top->data;D.top->next=top->next->next;7．連續(xù)存儲設(shè)計時，存儲單元的地址（

A）。A.一定連續(xù)

B．一定不連續(xù)

C．不一定連續(xù)

D．部分連續(xù)，部分不連續(xù)8．以下屬于邏輯結(jié)構(gòu)的是（

C

）。A．順序表

B.哈希表

C.有序表

D.

單鏈表9一個n個頂點的連通無向圖，其最小生成樹的邊數(shù)為（A）。A．n-1B．nC．n+1D．nlogn；10．有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（D）。A．不確定B．2nC．2n+1D．2n-111．在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：（

C

）。A．p->next=s->next;p->next=s;

B．p->next=s;p->next=s->next;C．s->next=p->next;p->next=s;

D．p->next=s;s->next=p->next;12．引入線索二叉樹的目的是（A）A．加快查找結(jié)點的前驅(qū)或后繼的速度

B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親

D．使二叉樹的遍歷結(jié)果唯一13．下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（

B

）。A．關(guān)鍵活動不按期完成就會影響整個工程的完成時間B．任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成C．所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成D．某些關(guān)鍵活動提前完成，那么整個工程將會提前完成.14.若需在O(nlogn)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（C）。A.快速排序B.堆排序C.歸并排序D.直接插入排序15.關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（A）。A．從源點到匯點的最長路徑B．從源點到匯點的最短路徑C．最長回路D．最短回路16.當一個有N個頂點的有向圖用鄰接矩陣A表示時，頂點Vi的度是（D）。A．B．C．D．+17.對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為(A)A．（N+1）/2B.N/2C.ND.[（1+N18.將一棵樹t轉(zhuǎn)換為孩子—兄弟鏈表表示的二叉樹h，則t的后根序遍歷是h的（B）A．前序遍歷B．中序遍歷C．后序遍歷D.層次遍歷19.具有12個關(guān)鍵字的有序表，折半查找的平均查找長度（A）A.3.1B.4C.2.520.在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是（C）。A.p->prior=q;q->next=p;p->prior->next=q;q->prior=q；B.p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;C.q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;D.q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;二、綜合應(yīng)用題(4分+5分+6分+6分+4分,本題共25分)1．有5個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？2．假設(shè)一棵二叉樹的前序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請畫出該樹。3．依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序樹(1)試畫出生成之后的二叉排序樹;(2)對該二叉排序樹作中序遍歷，試寫出遍歷序列;(3)假定每個元素的查找概率相等，試計算該二叉排序樹的平均查找長度。4．請問快速排序適合采用什么樣的存儲結(jié)構(gòu)，并簡要說明理由。5．試證明在一個有n個頂點的完全圖中，生成樹的數(shù)目至少有2n-1-1。三、算法題(5分+15分+15分,本題共35分)1.請?zhí)羁胀瓿上旅媲驢uffman樹的帶權(quán)路徑長度（WPL）的類C算法。[說明]其中ht為樹的根結(jié)點的指針，S為工作棧，Clearstack(S)、Push(S,p)、Pop(S)和Emptystack(S)分別為置?？铡⒅羔榩進棧、出棧和判?？盏暮瘮?shù)。Typedeffloatweight;Typedefstructnode{weightw;structnode*Lchild,*Rchild,*parent;}hnode,*hlinkweightCal_WPL(hlinkht)//求Huffman樹的WPL{hlinkp;weightnum=0.0;Clearstack(S);(1);While(!Emptystack(S)){P=Pop(S);while((2)_____)｛if((3)_____)num+=p->w;if((4)_____)Push(S,p->Rchild);(5)_____;}}return(num);}2.已知不帶頭結(jié)點的線性鏈表list，鏈表中結(jié)點構(gòu)造為（data、next），其中data為數(shù)據(jù)域，next為指針域。請寫一算法，將該鏈表按結(jié)點數(shù)據(jù)域的值的大小從小到大重新鏈接。要求鏈接過程中不得使用除該鏈表以外的任何鏈結(jié)點空間。3.二叉樹以鏈方式存儲，有三個域，數(shù)據(jù)域data，左右孩子域lchild,rchild。樹根由tree指向。請編寫算法要求按層次從上到下，同層次從左到右遍歷樹。4．請寫出算法根據(jù)完全二叉樹的順序存儲結(jié)構(gòu)，構(gòu)造其二叉鏈表結(jié)構(gòu)。

20092010學(xué)年第一學(xué)期期末試題踏實學(xué)習，弘揚正氣；誠信做人，誠實考試；作弊可恥，后果自負課程名稱數(shù)據(jù)結(jié)構(gòu)使用專業(yè)計算機班級計算機科學(xué)與技術(shù)類姓名學(xué)號試題得分一二三四五六七八九十總分一、選擇1、2、3、4、5、6、