年數(shù)據(jù)結(jié)構(gòu)試題含部分答案

：裝訂線工業(yè)大學(xué)考試試卷A課程名稱:考試時(shí)間20期四200577~二三四總一選擇題（共12）【c】1.[A]不必事先估 空 [B]所需空間與表的長(zhǎng)度成正[C]可以隨 任一結(jié) [D]插入和刪除不需要移動(dòng)元【b2.12345[A] [B] [C] [D]【d】3.若將66的上三角矩陣A（下標(biāo)從1起計(jì)）的上三角元素按行優(yōu)先 一維數(shù)組b中，且b[1]=A11，那末A34在b中的下標(biāo)是[A] [B] [C] [D]【c】4.21512[A] [B] [C] [D]【c5.[A]入 [B]出[C]入度與出度之 [D]入度與出度的均【b6.BB+樹的敘述中，[ABB+[BBB+[CBB+[DBB+【a】7.平均時(shí)間復(fù)雜度為O(nlogn[A][B]

O(nlog

[C]快速排 平均O(nlogn)[D]排

【a8.ISAMVSAM[A]索引文 [B]散列文 [C]多關(guān)鍵字文 [D]順序文裝訂線二題（共12裝訂線（rear（b,((),c)6619nn(n-1) 在有15個(gè)互不相同元素的有序表A[1.15]A[7]的元素的下標(biāo)依次為,,,7。三題（共3617.（6）設(shè)哈希函數(shù)為H(k)=kMOD11，用二次探測(cè)法處理。請(qǐng)畫出依次插入元素29，15，48，47，23，41，73，37后，該哈希表的狀態(tài)，在各元素下面標(biāo)出其次數(shù)，并求出查找成功的平均查找長(zhǎng)度。0123456789次數(shù)40001200查找成功的平均查找長(zhǎng)度18（5 結(jié)構(gòu)裝訂線19.（10）G裝訂線G=(V,V={a,b,c,d,e,fE={<c,e>,<d,e>,<f,d>,<f,e>GG20.（6）插入4，6和7 插入10 插入14插入16 插入18 插入1221（9TT

裝訂線 裝訂線四.算法題（共40分22.（6）Q1，3，5，2，4，6)寫出調(diào)用算法f22(Q)Qf22(Q)的功能:將隊(duì)列Qvoidf22(Queue&Q){if(!Empty(Q)){ElemTypee;DeQueue(Q,e);EnQueue(Q,}}23（6分）算法f23對(duì) 結(jié)點(diǎn)單鏈表L進(jìn)行簡(jiǎn)單選擇排序。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)voidf23(LinkListL)①p=L- while(p!=NULL){q=p->next;r=p;while(q!=NULL){if(②r->data<q->data )r=q;}if(r!=p)}③p=p- }}24（6 結(jié)構(gòu)f24(T)Tf24(T)T

F 裝訂線裝訂線intf24(CSTreeT)if(!T->firstchild)returnelsefor(p=T->firstchild;p;p=p->nextsibling)c+=f24(p);return裝訂線裝訂線}}（6分）二叉樹 typedefstructBiTNode{ BiTNode*lchild,}BiTNode,f25(T)對(duì)二叉樹T中所有結(jié)點(diǎn)執(zhí)行如下操作：如果結(jié)點(diǎn)沒有左孩子但有右voidf25(BiTreeT)if( ) if(③!T->lchild&&T- )T->lchild=T->rchild;T->rchild=NULL;}}}（6分）圖的鄰接 typedef ode ode*nextarc; typedefstructVertexType VNode,AdjList[MAX_VERTEX_NUM];typedefstruct} LocateVex(g,v)在圖g中查找頂點(diǎn)v的位置，若存在，則返回所在位置，intLocateVex(ALGraphg,VertexTypev){inti=① while(i<g.vexnum&& g. if( )returnelsereturn-}裝訂線裝訂線

10分某倉(cāng)庫(kù)用一個(gè) 結(jié)點(diǎn)的循環(huán)鏈表L typedefstructGoods}Goods, 結(jié)點(diǎn)的循環(huán)鏈表Lc。voidf26(GoodsList&L,GoodsList&Lc,int{GoodsLc=(Goods*)malloc(sizeof(Goods)