【正文】 hild,*rchild。q=snext。p=pnext) { for(q=pnext,s=q。void delredundant(lklist *amp。typedef int datatype。H(40)=40 mod 7=5。 H１(22)=(1+1) mod 7=2。 tdata=pdata。p=pnext){ for(q=hb。void intersection(lklist *ha,lklist *hb,lklist *amp。}2. 設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。 r[i]x) i=i+1。 if (ij) {r[i]=r[j]。void quickpass(int r[], int s, int t){ int i=s, j=t, x=r[s]。//i為計(jì)數(shù)器 while(p!=NULL) { if (Pdata==x) i++。} r[j1]=temp。 while (i=1) if (temp=r[i1])break。 return(0)。bitree *bstsearch1(bitree *t, int key){ bitree *p=t。} if(ha==0) snext=hb。 else {snext=hb。 s=ha。 while(ha!=0 amp。}數(shù)據(jù)結(jié)構(gòu)試卷（十）三、算法設(shè)計(jì)題(22分)1． 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。elsefor(q=head,p=headnext。} } r[i]=x。amp。 r[j]%2==0) j=j1。設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。s){ if(bt!=0) {s=s+btdata。 g[j].firstarc=p。 g[i].firstarc=p。j=n1。i++) g2[i].firstarc=0。void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){int i,j。}glinklistnode。}gadjmatrix。}}2. 設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。void countnode(bitree *bt,int amp。 else if (btkeyx) level(btlchild,x)。 struct node *lchild,*rchild。}}3. 設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。 istart+count1。void substring(char s[ ], long start, long count, char t[ ]){ long i,j,length=strlen(s)。 sdata=qdata。 p!=0。 q!=0。head){ lklist *p,*q,*s。sdata=t。 pnext=snext。s!=qnext。 if (head==0 || headnext==0) return。inorder(btrchild)。}bitree。設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。 else if(r[mid].keyk) high=mid1。}。}數(shù)據(jù)結(jié)構(gòu)試卷（六）四、算法設(shè)計(jì)題(20分)１． 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。}。ha=hanext。 hb!=0) if(hadatahbdata){if(s==0) hc=s=ha。void mergelklist(lklist *ha,lklist *hb,lklist *amp。 else if (bt1==0 || bt2==0 ||bt1data!=bt2data) return(0)。} bitree。ASL1=7/6，ASL2=4/3四、算法設(shè)計(jì)題(28分)1． 設(shè)計(jì)判斷兩個(gè)二叉樹(shù)是否相同的算法。}數(shù)據(jù)結(jié)構(gòu)試卷（五）三、應(yīng)用題(32分)1. 設(shè)某棵二叉樹(shù)的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹(shù)的的后序遍歷序列。bt){ int i。btlchild=btrchild=0。}bitree。}3. 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹(shù)。 swapbitree(btrchild)。} bitree。} }}2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。) {pnext=hb。 amp。) {pnext=ha。 amp。p=head) { head=pnext。hc){ lklist *p。}lklist。設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。 BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)； (2) 求森林先序序列和中序序列；ABCDEF。 else printf(not parent)。 i=r。 preorder(btrchild,x)。 return。 int r=0,f=0,flag=0。typedef struct node {datatype data。q=snext。p=pnext) { for(q=pnext,s=q。void delredundant(lklist *amp。typedef int datatype。 ….沖突（1）計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表： ` 0 1 2 3 4 5 66336152240（2）求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度。 H１(15)=(1+1) mod 7=2。2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）= K mod 7，若發(fā)生沖突采用線性探查法處理，試：H(36)=36 mod 7=1。 tdata=pdata。p=pnext){ for(q=hb。void intersection(lklist *ha,lklist *hb,lklist *amp。設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。 if (ij) {r[j]=r[i]。i=i+1。 while(ij){while (ij amp。E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程。 prlink=q。(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）。//i為計(jì)數(shù)器 while(p!=NULL) { if (Pdata==x) i++。 else return Find(____BSTright __,item)。 item){ if (BST==NULL) return false。 ABC (BTright)。見(jiàn)圖124444422255285283452843 圖12 圖11四、閱讀算法（每題7分，共14分）1. LinkList mynote(LinkList L) {//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(Lamp。3. 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7}。 A 0 1 2 3 4 5 6 7 data605078903440next3572041線性表為：（78，50，40，60，34，90）2. 請(qǐng)畫出下圖的鄰接矩陣和鄰接表。用克魯斯卡爾算法得到的最小生成樹(shù)為： (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ù)后堆的變化。返回的線性表為（a2,a3,…,an,a1）2. void ABC(BTNode * BT){ if BT { ABC (BTleft)。 } } 該算法的功能是：遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)五、算法填空（共8分）二叉搜索樹(shù)的查找——遞歸算法:bool Find(BTreeNode* BST,ElemTypeamp。} else if(itemBSTdata) return Find(___BSTleft __,item)。 LNode* p=HL。 }//CountX數(shù)據(jù)結(jié)構(gòu)試卷（二）三、應(yīng)用題(36分)1． 設(shè)一組初始記錄關(guān)鍵字序列為(45