試卷編號(hào) （A） G數(shù)據(jù)結(jié) 課 課程類別：必、限、D題計(jì)分簽總十九D題計(jì)分簽總十九八七六五四三二F—題C簽名簽名學(xué)考生注意事項(xiàng)：1、本試卷共頁，總分100120學(xué)一、單選題（2分，共22分?????? 在一個(gè)單鏈表HL中若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向 ?????? 學(xué)號(hào)p=q;p- B.p->next=q;q-學(xué)號(hào)C.p->next=q->next; D.q->next=p->next;p-由權(quán)值分別為3,8,6,2的葉子生成一 樹它的帶權(quán)路徑長度為(B) C. D.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？（A承到記過及以上分將紀(jì)，承到記過及以上分將紀(jì)，知試可以組成(B)個(gè)不同的字符串？班級(jí)A、 B、 C、 D、班級(jí)對(duì)線性表進(jìn)行二分法查找，其前提條件是線性表 方 ，并且按關(guān)鍵碼值排好軟件工程05線性表以順序方 ，并且按關(guān)鍵碼值的檢索頻率排好軟件工程05線性表以順序方 ，并且按關(guān)鍵碼值排好線性表 方 ，并且按關(guān)鍵碼值的檢索頻率排好當(dāng)利用大小為n的數(shù)組順序 個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行（B）語句修改top指針專業(yè)A、top++ B、top-- C、top=0 D專業(yè)下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是(DB.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為 煉C.樹是一種線性結(jié) D.用一維數(shù) 一棵完全二叉樹是有效 方圖一該二叉樹結(jié)點(diǎn)的前序遍歷的序列為(CA、E、G、F、A、C、D、 B、E、A、G、C、F、B、C、E、A、C、B、D、G、D、E、G、A、C、D、F、 設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有(A)條邊 序列？（C）A.54361 B.45312 C.34652 D.23415二、填空題（每空1分，共16分對(duì)于一個(gè)長度為n的順 的線性表，在表頭插入元素的時(shí)間復(fù)雜度為O(n)，在 入元素的時(shí)間復(fù)雜度 O(1)。向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是p->next=HS;

（設(shè)棧不空而且無需回收被刪除結(jié)點(diǎn)10_45_n頂點(diǎn)的有向完全圖中，包含有_n(n-1)條邊。后綴算式 2 +- 對(duì)應(yīng)的后綴算式 3XY*+2Y*3/- 時(shí)，其指針總數(shù)為2n個(gè)，其中n-1n+1 時(shí)，若選用=K%70_1_6_4_隊(duì)列的插入操作是在隊(duì)列的_隊(duì)尾進(jìn)行刪除操作是在隊(duì)列的_隊(duì) 進(jìn)LAPP-三、運(yùn)算題（共37分1（5分已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ,KBCDAFHIGJ,中序遍歷結(jié)果：KDCBIHJGF2、（5分）用于通信的電文僅由A-H八個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10。試為這八個(gè)字母設(shè)計(jì) 3（5分）知一個(gè)圖的頂點(diǎn)集V為 其共有10條邊。該圖用如下邊集數(shù) 1221225522651122233457試 算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值答案： 算法得到的最小生成樹為 (2,4)1,(2,5)2, 4（5）在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為、、5、60、3、1，29，5（9）7116（8）AOE這個(gè)工程最早可能在什么時(shí)間結(jié)束。（2Ve[i]Vl[i]（2e(l(， 速可使整個(gè)工程提前完成（4分），43V12345600鍵路徑為：、、、四、閱讀算法（共17分1、(3voidprime(int /*判斷nfor(i=2;((n%i)!=0)&&(i<sqrt(n));i++);if(i>sqrt(n))cout<<n<<"isaprimenumber"；cout<<n<<"isnotaprime}/*prime答案：時(shí)間復(fù)雜度為：O(n1/2O(sqrt(n))2、(3)voidAE(Stack&S){ intx=2*Pop(S)+Pop(S); intfor(i=0;i<5;i++)Push(S,a[i]);while(!StackEmpty(S))cout<<Pop(S)<<'';}該算法被調(diào)用后得到的輸出結(jié)果為：16 2113、(6分)LinkListmynote(LinkListL){//L是 結(jié)點(diǎn)的單鏈表的頭指if(L&&L-q=L；L=L- while(p->next)p=p->next； } }（1）（2）（1）將第一個(gè)結(jié) 到鏈表的尾部，作為新的尾結(jié)返回的線性表為4、CLtypedefstruct{int structnodevoidInsertsort(link{linkp=L- { q=L- &&q->data<=p->data){r=q;q=q->next;}u=p->next;(4) ;(5) }}答案:(1)L- pqp->next=r->nextp 五、編寫算法（共6分typedefcharDataType;/DataTypetypedefstructDataTypestructnode*lchild*rchild;/}BinTNode;typedefBinTNode*BinTreevoidun