精選數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)總結(jié)

精選數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)總結(jié)1204班學(xué)委精心整理數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)?數(shù)據(jù)結(jié)構(gòu)?期末考試題型及分值〔1〕簡(jiǎn)答題6題*5分=30分簡(jiǎn)要答復(fù)要點(diǎn) 〔2〕分析題6題*5分=30分給出結(jié)果〔3〕設(shè)計(jì)題1題*10分=10分設(shè)計(jì)思想及結(jié)果〔4〕編程題1題*10分=10分完整代碼〔5〕綜合題1題*20分=20分抽象數(shù)據(jù)類型的定義、表示、實(shí)現(xiàn)、算法分析{定義=功能〔ADT〕表示=存儲(chǔ)結(jié)構(gòu)體實(shí)現(xiàn)=算法〔根本操作〕算法分析=時(shí)間、空間復(fù)雜度}考試概念有：1.數(shù)據(jù)結(jié)構(gòu){一、線性表〔棧-隊(duì)-列-串-數(shù)組-廣義表-邏輯結(jié)構(gòu)-存儲(chǔ)結(jié)構(gòu)-運(yùn)算結(jié)構(gòu)〕二、非線性表〔集合-樹(shù)-圖〕}2.抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象-數(shù)據(jù)關(guān)系-根本操作3.算法性質(zhì)-要求〔設(shè)計(jì)〕-效率〔度量〕4.實(shí)例查找：高效查找算法排序：高效的排序算法分析題考試題目參考〔1〕1-2-3-4-5-6順序建BBST〔2〕6-5-4-3-2-1順序建BBST簡(jiǎn)答題實(shí)例設(shè)計(jì)題：〔1〕〔2〕數(shù)據(jù)結(jié)構(gòu)試卷〔一〕三、計(jì)算題〔每題6分，共24分〕在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A[0].next，試寫(xiě)出該線性表。A01234567data605078903440next3572041線性表為：〔78，50，40，60，34，90〕請(qǐng)畫(huà)出以下圖的鄰接矩陣和鄰接表。一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。用克魯斯卡爾算法得到的最小生成樹(shù)為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.畫(huà)出向小根堆中參加數(shù)據(jù)4,2,5,8,3時(shí)，每參加一個(gè)數(shù)據(jù)后堆的變化。見(jiàn)圖1244444222552852834528434444422255285283452843圖12圖11四、閱讀算法〔每題7分，共14分〕LinkListmynote(LinkListL){//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L->next){q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}請(qǐng)答復(fù)以下問(wèn)題：〔1〕說(shuō)明語(yǔ)句S1的功能；查詢鏈表的尾結(jié)點(diǎn)〔2〕說(shuō)明語(yǔ)句組S2的功能；將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)〔3〕設(shè)鏈表表示的線性表為〔a1,a2,…,an〕,寫(xiě)出算法執(zhí)行后的返回值所表示的線性表。返回的線性表為〔a2,a3,…,an,a1〕voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<<BT->data<<'';}}該算法的功能是：遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)五、算法填空〔共8分〕二叉搜索樹(shù)的查找——遞歸算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失敗else{if(item==BST->data){item=BST->data;//查找成功return__true__;}elseif(item<BST->data)returnFind(___BST->left__,item);elsereturnFind(____BST->right__,item);}//if}六、編寫(xiě)算法〔共8分〕統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。intCountX(LNode*HL,ElemTypex)intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i為計(jì)數(shù)器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)returni;}//CountX數(shù)據(jù)結(jié)構(gòu)試卷〔二〕三、應(yīng)用題(36分)設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，那么分別給出第4趟簡(jiǎn)單項(xiàng)選擇擇排序和第4趟直接插入排序后的結(jié)果。(22，40，45，48，80，78)，(40，45，48，80，22，78)設(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〕。q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比擬次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。2,ASL=91*1+2*2+3*4+4*2)=25/9設(shè)一棵樹(shù)T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法〔二叉鏈表〕表示出該樹(shù)的存儲(chǔ)結(jié)構(gòu)并將該樹(shù)轉(zhuǎn)化成對(duì)應(yīng)的二叉樹(shù)。樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹(shù)略設(shè)有無(wú)向圖G，要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程。四、算法設(shè)計(jì)題(16分)設(shè)有一組初始記錄關(guān)鍵字序列〔K1，K2，…，Kn〕，要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩局部，其中左半局部的每個(gè)關(guān)鍵字均小于Ki，右半局部的每個(gè)關(guān)鍵字均大于等于Ki。設(shè)有一組初始記錄關(guān)鍵字序列〔K1，K2，…，Kn〕，要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩局部，其中左半局部的每個(gè)關(guān)鍵字均小于Ki，右半局部的每個(gè)關(guān)鍵字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}}}數(shù)據(jù)結(jié)構(gòu)試卷〔三〕三、計(jì)算題(每題10分，共30分)1.二叉樹(shù)的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫(huà)出此二叉樹(shù)，并畫(huà)出它的后序線索二叉樹(shù)。2．待散列的線性表為〔36，15，40，63，22〕，散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H〔K〕=Kmod7，假設(shè)發(fā)生沖突采用線性探查法處理，試：H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….沖突H(15)=15mod7=1;….沖突H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;….沖突〔1〕計(jì)算出每一個(gè)元素的散列地址并在以下圖中填寫(xiě)出散列表：`01234566336152240〔2〕求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度。ASL=3．序列〔10，18，4，3，6，12，1，9，18，8〕請(qǐng)用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(18,18)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,10,12,18,181,3,4,6,8,9,10,12,18,18四、算法設(shè)計(jì)題(每題15分，共30分)設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->next){for(q=p->next,s=q;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}數(shù)據(jù)結(jié)構(gòu)試卷〔四〕三、計(jì)算題(每題10分，共30分)1、畫(huà)出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲(chǔ)結(jié)構(gòu)。2、以下圖所示的森林：(1)求樹(shù)〔a〕的先根序列和后根序列；(1)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；(2)求森林先序序列和中序序列；ABCDEF;BDEFCA；〔3〕將此森林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；(2)ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；3、設(shè)散列表的地址范圍是[0..9]，散列函數(shù)為H〔key〕=〔key2+2〕MOD9,并采用鏈表處理沖突，請(qǐng)畫(huà)出元素7、4、5、3、6、2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6四、算法設(shè)計(jì)題(每題10分，共30分)設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫(xiě)字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫(xiě)字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p->next;p->next=0;if(p->data>='A'&&p->data<='Z'){p->next=ha;ha=p;}elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;}}}設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹(shù)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹(shù)。#definen10typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);}voidcreatebsttree(bitree*&bt){inti;for(i=1;i<=n;i++)bstinsert(bt,random(100));}數(shù)據(jù)結(jié)構(gòu)試卷〔五〕三、應(yīng)用題(32分)設(shè)某棵二叉樹(shù)的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹(shù)的的后序遍歷序列。DEBCA設(shè)無(wú)向圖G〔如右圖所示〕，給出該圖的最小生成樹(shù)上邊的集合并計(jì)算最小生成樹(shù)各邊上的權(quán)值之和。E={(1,5),(5,2),(5,3),(3,4)},W=10設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時(shí)的平均查找長(zhǎng)度。ASL=(1*1+2*2+3*4)/7=17/7設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=kmod7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計(jì)算出用線性探測(cè)法和鏈地址法作為解決沖突方法的平均查找長(zhǎng)度。ASL1=7/6，ASL2=4/3四、算法設(shè)計(jì)題(28分)設(shè)計(jì)判斷兩個(gè)二叉樹(shù)是否相同的算法。設(shè)計(jì)判斷兩個(gè)二叉樹(shù)是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}數(shù)據(jù)結(jié)構(gòu)試卷〔六〕四、算法設(shè)計(jì)題(20分)設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;elselow=mid+1;}return(0);}設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}}3.在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head->next==0)return;elsefor(q=head,p=head->next;p!=0;p=q->next){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;if(s==q->next)q=p;else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}}}數(shù)據(jù)結(jié)構(gòu)試卷〔七〕四、算法設(shè)計(jì)題(20分)設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單項(xiàng)選擇擇排序算法。設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單項(xiàng)選擇擇排序算法。voidsimpleselectsorlklist(lklist*&head){lklist*p,*q,*s;intmin,t;if(head==0||head->next==0)return;for(q=head;q!=0;q=q->next){min=q->data;s=q;for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}}設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。voidsubstring(chars[],longstart,longcount,chart[]){longi,j,length=strlen(s);if(start<1||start>length)printf("Thecopypositioniswrong");elseif(start+count-1>length)printf("Toocharacterstobecopied");else{for(i=start-1,j=0;i<start+count-1;i++,j++)t[j]=s[i];t[j]='\0';}}設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}數(shù)據(jù)結(jié)構(gòu)試卷〔八〕四、算法設(shè)計(jì)題(20分)設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[]){inti,j;glinklistnode*p;for(i=0;i<=n-1;i++)g2[i].firstarc=0;for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}}數(shù)據(jù)結(jié)構(gòu)試卷〔九〕五、算法設(shè)計(jì)題(20分)設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]%2==0)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]%2==1)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。intisriselk(lklist*head){if(head==0||head->next==0)return(1);elsefor(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);return(1);}數(shù)據(jù)結(jié)構(gòu)試卷〔十〕三、算法設(shè)計(jì)題(22分)設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。bitree*bstsearch1(bitree*t,intkey){bitree*p=t;while(p!=0)if(p->key==key)return(p);elseif(p->key>key)p=p->lchild;elsep=p->rchild;return(0);}設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。voidadjustheap(intr[],intn){intj=n,i=j/2,temp=r[j-1];while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;}r[j-1]=temp;}數(shù)據(jù)結(jié)構(gòu)試卷〔一〕參考答案三、計(jì)算題〔每題6分，共24分〕線性表為：〔78，50，40，60，34，90〕鄰接矩陣：鄰接表如圖11所示：圖11用克魯斯卡爾算法得到的最小生成樹(shù)為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20見(jiàn)圖1244444222552852834528434444422255285283452843圖12讀算法〔每題7分，共14分〕〔1〕查詢鏈表的尾結(jié)點(diǎn)〔2〕將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)〔3〕返回的線性表為〔a2,a3,…,an,a1〕遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。法填空〔每空2分，共8分〕trueBST->leftBST->right編寫(xiě)算法〔8分〕intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i為計(jì)數(shù)器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)returni;}//CountX數(shù)據(jù)結(jié)構(gòu)試卷〔二〕參考答案四、算法設(shè)計(jì)題設(shè)有一組初始記錄關(guān)鍵字序列〔K1，K2，…，Kn〕，要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩局部，其中左半局部的每個(gè)關(guān)鍵字均小于Ki，右半局部的每個(gè)關(guān)鍵字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}}}數(shù)據(jù)結(jié)構(gòu)試卷〔三〕參考答案三、計(jì)算題1．2、H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….沖突H(15)=15mod7=1;….沖突H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;….沖突〔1〕01234566336152240〔2〕ASL=3、(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(18,18)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,10,12,18,181,3,4,6,8,9,10,12,18,18四、算法設(shè)計(jì)題設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->next){for(q=p->next,s=q;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}數(shù)據(jù)結(jié)構(gòu)試卷〔四〕參考答案三、計(jì)算題1．2．(1)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；3．H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6四、算法設(shè)計(jì)題設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫(xiě)字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p->next;p->next=0;if(p->data>='A'&&p->data<='Z'){p->next=ha;ha=p;}elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;}}}設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹(shù)。#definen10typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);}voidcreatebsttree(bitree*&bt){inti;for(i=1;i<=n;i++)bstinsert(bt,random(100));}數(shù)據(jù)結(jié)構(gòu)試卷〔五〕參考答案四、算法設(shè)計(jì)題設(shè)計(jì)判斷兩個(gè)二叉樹(shù)是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}數(shù)據(jù)結(jié)構(gòu)試卷〔六〕參考答案四、算法設(shè)計(jì)題設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;elselow=mid+1;}return(0);}設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}}在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head->next==0)return;elsefor(q=head,p=head->next;p!=0;p=q->next){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;if(s==q->next)q=p;else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}}}數(shù)據(jù)結(jié)構(gòu)試卷〔七〕參考答案四、算法設(shè)計(jì)題設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單項(xiàng)選擇擇排序算法。voidsimpleselectsorlklist(lklist*&head){lklist*p,*q,*s;intmin,t;if(head==0||head->next==0)return;for(q=head;q!=0;q=q->next){min=q->data;s=q;for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}}設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。voidsubstring(chars[],longstart,longcount,chart[]){longi,j,length=strlen(s);if(start<1||start>length)printf("Thecopypositioniswrong");elseif(start+count-1>length)printf("Toocharacterstobecopied");else{for(i=start-1,j=0;i<start+count-1;i++,j++)t[j]=s[i];t[j]='\0';}}設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);