北京理工大學(xué)2013級數(shù)據(jù)結(jié)構(gòu)B試題(A卷)-答案模板

北京理工大學(xué)2013級數(shù)據(jù)結(jié)構(gòu)B試題(A卷)_答案模板北京理工大學(xué)2013級數(shù)據(jù)結(jié)構(gòu)B試題(A卷)_答案模板北京理工大學(xué)2013級數(shù)據(jù)結(jié)構(gòu)B試題(A卷)_答案模板一、選擇題1、從邏輯結(jié)構(gòu)上可以把數(shù)據(jù)結(jié)構(gòu)分為【C】。A、動(dòng)向結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外面結(jié)構(gòu)2、在一個(gè)長度為n的次序儲(chǔ)蓄的線性表中，向第i個(gè)元素（1in+1）以前插入一個(gè)新元素時(shí)，需要從后向前挨次后移【B】個(gè)元素。A、n-iB、n-i+1C、n-i-1D、i3、鏈表結(jié)構(gòu)不擁有以下【B】特色。A、插入和刪除無需挪動(dòng)元素B、可隨機(jī)接見鏈表中的隨意元素C、無需實(shí)現(xiàn)分派儲(chǔ)蓄空間D、所需空間與結(jié)點(diǎn)個(gè)數(shù)成正比。4、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則履行【C】。A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、p->next=s;s->next=q;5、一個(gè)棧的入棧序列是1，2，3，4，5，則棧不可以能輸出的序列是【C】。A、54321B、45321C、43512D、123456、判斷一個(gè)行列Q（元素最多為M個(gè)）為空的條件是【C】。A、Q->rear–Q->front=MB、Q->rear–Q->front-1==MC、Q->rear==Q->frontD、Q->rear+1==Q->front7、在一個(gè)鏈行列中，假定f和r分別指向隊(duì)首和隊(duì)尾，則插入s所指結(jié)點(diǎn)的運(yùn)算是【A】。A、r->next=s;r=s;B、f->next=s;f=s;C、s->next=r;r=s;D、s->next=f;f=s;8、深度為5的二叉樹至多有【A】個(gè)結(jié)點(diǎn)。A、31B、32C、16D、109、在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右側(cè)【A】。A、只有右子樹上的全部結(jié)點(diǎn)B、只有右子樹上的部分結(jié)點(diǎn)C、只有左子樹上的全部結(jié)點(diǎn)B、只有左子樹上的部分結(jié)點(diǎn)10、假如一棵完滿二叉樹有1001個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)個(gè)數(shù)為【D】。A、250B、500C、502D、49011、在一個(gè)圖中，全部極點(diǎn)的度數(shù)之和是全部邊數(shù)的【C】倍。A、1/2B、1C、2D、412、采納毗鄰表儲(chǔ)蓄的圖的深度優(yōu)先遍歷算法近似于二叉樹的【A】。1A、先序遍歷B、中序遍歷C、后序遍歷D、按層遍歷13、一個(gè)有n個(gè)極點(diǎn)的無向圖最多有【D】條邊。A、nB、n(n-1)C、2nD、n(n-1)/214、靜態(tài)查找表與動(dòng)向查找表的根本差別在于【B】。A、它們的邏輯結(jié)構(gòu)不同樣B、施加在其上的操作不同樣C、所包括的數(shù)據(jù)元素種類不同樣D、儲(chǔ)蓄實(shí)現(xiàn)不同樣樣15、次序查找合用于儲(chǔ)蓄結(jié)構(gòu)為【C】的線性表。A、哈希儲(chǔ)蓄B、壓縮儲(chǔ)蓄C、次序儲(chǔ)蓄或鏈?zhǔn)絻?chǔ)蓄D、索引儲(chǔ)蓄16、若一顆二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹必定知足【B】。A、全部結(jié)點(diǎn)均無孩子B、全部結(jié)點(diǎn)均無右孩子C、只有一個(gè)葉子結(jié)點(diǎn)D、是一顆滿二叉樹17、二叉排序樹是【B】。A、每一分支結(jié)點(diǎn)的度均為2的二叉樹B、中序遍歷獲得一升序序列的二叉樹C、按從左到右次序編號的二叉樹D、每一分支結(jié)點(diǎn)的值均小于左子樹上全部結(jié)點(diǎn)的值，又大于右子樹上全部結(jié)點(diǎn)的值18、擁有12個(gè)記錄的序列，采納冒泡排序最少的比較次數(shù)是【C】。A、1B、144C、11D、6619、堆的形狀是一棵【C】。A、二叉排序樹B、滿二叉樹C、完滿二叉樹D、均衡二叉樹20、在一個(gè)包括n個(gè)極點(diǎn)e條邊的無向圖的毗鄰矩陣中，零元素的個(gè)數(shù)為【D】。A、eB、2eC、n2-eD、n2-2e二、判斷對錯(cuò)x】1、擁有n個(gè)極點(diǎn)的連通圖最罕有n條邊。x】2、鏈表的單個(gè)結(jié)點(diǎn)內(nèi)部的儲(chǔ)蓄空間可以是不連續(xù)的?！?、棧和行列的共同點(diǎn)是只贊成在端點(diǎn)處插入和刪除元素。】4、使用循環(huán)行列可以解決行列次序儲(chǔ)蓄時(shí)的假溢出問題。x】5、要想經(jīng)過遍歷序列復(fù)原為唯一二叉樹，應(yīng)該知道其先序序列和后序序列。】6、若一個(gè)結(jié)點(diǎn)是某二叉樹子樹的中序遍歷序列的第一個(gè)結(jié)點(diǎn)，則它也必是該子樹的后序遍歷序列的第一個(gè)結(jié)點(diǎn)。x】7、完滿二叉樹可采納次序儲(chǔ)蓄結(jié)構(gòu)儲(chǔ)蓄，非完滿二叉樹則不可以。2【】8、關(guān)于一棵含有n個(gè)結(jié)點(diǎn)的完滿二叉樹，將其結(jié)點(diǎn)按從上到下且從左至右按1至n進(jìn)行編號，則對其隨意一個(gè)編號為i的結(jié)點(diǎn)，假如它有左孩子，則其左孩子結(jié)點(diǎn)的編號為2i。【】9、哈夫曼樹的全部子樹也都是哈夫曼樹?！緓】10、當(dāng)圖的邊較少而結(jié)點(diǎn)好多時(shí)，求其最小生成樹用Prim算法比用Kruskal算法效率更高。三、填空題1、向量的第一個(gè)元素的儲(chǔ)蓄地點(diǎn)是200，每個(gè)元素的長度是3，那么第6個(gè)元素的儲(chǔ)蓄地址是。答案：2152、在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，p所指結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，刪除p結(jié)點(diǎn)的語句序列是、、。答案:q=p，p=p->next，free(q)3、設(shè)貨倉有足夠的儲(chǔ)蓄空間，那么向貨倉中插入一個(gè)數(shù)據(jù)元素，即入棧的操作過程是、。答案:存入數(shù)據(jù)元素，棧頂指針加14、一般狀況下，向循環(huán)行列中插入數(shù)據(jù)元素時(shí)，需要判滿行列能否已經(jīng)滿了，判斷條件是：。答案:(rear+1)%MaxSize==front6、已知循環(huán)行列用數(shù)組data[1n]儲(chǔ)蓄元素值，front和rear分別表示隊(duì)頭和隊(duì)尾指針，則目前行列中元素的個(gè)數(shù)為。答案:(n+rear-frone)%n或(n+rear-frone)modn7、深度為k的二叉樹最多有個(gè)結(jié)點(diǎn)，深度為k的完滿二叉樹最罕有個(gè)結(jié)點(diǎn)（k≥1）。答案:2k-1，2k-18、如以{2,3,6,7,9}作為葉子結(jié)點(diǎn)的權(quán)值結(jié)構(gòu)哈夫曼樹，則其最短帶權(quán)路徑長度為。答案:5510、已知某二叉樹的中序序列和前序序列分別為42758136、12457836，則它的后序序列為。3答案:4785263112、在有n個(gè)極點(diǎn)的有向圖中，每個(gè)極點(diǎn)的度最大可達(dá)到。答案:2(n-1)13、在有序表A[118]中，采納折半查找算法查找元素值等于A[7]的元素，所比較過的元素的下標(biāo)挨次為。答案:946714、一組記錄的輸入次序?yàn)?25,38,65,90,72,14)，則利用堆排序方法成立的初始“小頂堆”為。答案:14,38,25,90,72,65四、簡答題1、設(shè)有一段正文是由字符集{a,b,c,d,e,f,g,h}構(gòu)成，正文長度為100個(gè)字符，此中每個(gè)字符在正文中出現(xiàn)的次數(shù)分別為17,12,14,4,10,9,20,3。若采納哈夫曼樹對這段文字進(jìn)行壓縮儲(chǔ)蓄，請達(dá)成以下工作：（1）結(jié)構(gòu)哈夫曼樹（規(guī)定權(quán)值較小的結(jié)點(diǎn)為左子樹）；（2）求出每個(gè)字符的哈夫曼編碼；（3）若此中一段正文的二進(jìn)制編碼序列為“”，請按（2）的哈夫曼編碼將其譯碼成原始正文。答案：（1）樹的結(jié)構(gòu)為：0891365301011620223100101g017910121417013ebfca34hd（2）編碼為a=111，b=101，c=110，d=0001，e=100，f=001，g=01，h=0000（3）上述編碼序列的對應(yīng)原文為：badegg42、一棵有11個(gè)結(jié)點(diǎn)的二叉樹的儲(chǔ)蓄狀況以以以下圖所示（此中“∧”表示空指針），left[i]和right[i]分別表示結(jié)點(diǎn)i的左、右孩子，根結(jié)點(diǎn)是序號為3的結(jié)點(diǎn)，要求：（1）畫出該二叉樹；（2）分別寫出該二叉樹的前序和中序遍歷序列。結(jié)點(diǎn)編號i1234567891011LeftChild[i]6∧7∧8∧5∧2∧∧Data[i]MFADKBLRCSERightChild[i]∧∧9∧10411∧1∧∧第2題圖答案：（1）二叉樹的結(jié)構(gòu)以以下圖：ALC0KEFM300RSB0D0（2）前序序列ALKRSECFMBD中序序列RKSLEAFCBDM3、設(shè)數(shù)據(jù)會(huì)合D={2,24,12,15,32,9,10,35,7,5}，要求：（1）挨次讀取D中的各個(gè)數(shù)據(jù)，結(jié)構(gòu)一棵二叉排序樹Bt；（2）怎樣依據(jù)此二叉樹Bt求得數(shù)據(jù)會(huì)合D的一個(gè)有序序列？并寫出該有序序列；（3）畫出在上述二叉樹中刪除結(jié)點(diǎn)“12”后獲得的二叉樹結(jié)構(gòu)。答案：（1）結(jié)構(gòu)的二叉排序樹以下：52241232915357105（2）上述二叉樹Bt的中序遍歷序列即是數(shù)據(jù)會(huì)合D的一個(gè)有序序列：2，5，7，9，10，12，15，24，32，35（3）刪除結(jié)點(diǎn)12后的二叉樹結(jié)構(gòu)為下邊隨意一種結(jié)構(gòu)：2241597105或許

32356224932710355154、用深度優(yōu)先和廣度優(yōu)先遍歷算法對以以下圖G進(jìn)行遍歷（要求從極點(diǎn)A出發(fā)），請給出深度優(yōu)先和廣度優(yōu)先遍歷序列。ABCEHFDG第4題圖答案：深度優(yōu)先序列：ABFDEGHC廣度優(yōu)先序列：ABCFDEHG5、關(guān)于以下所示的加權(quán)無向圖，寫出用Prim算法結(jié)構(gòu)最小生成樹的過程，并畫出最后獲得的最小生成樹。A3D24E9841710F5G611BC712第5題圖答案：最小生成樹的結(jié)構(gòu)過程以以以下圖所示：ADE1FGBCAD2E1FGBCA3D2E1FGA32DCBE41FG8BCA32DE41FG6BCA32DE417FG6BC五、依據(jù)指定功能，達(dá)成以下算法1、逆置帶頭結(jié)點(diǎn)的單鏈表Lvoidinverse(LinkList&L){p=L->next;L->next=NULL;while(p){succ=p->next;p->next=L->next;L->next=p;p=succ;}}92、算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符、界線符會(huì)合。operandTypeEvaluateExpression( ){InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar( );while(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP)){Push(OPND,c);c=getchar( );}elseswitch(Precede(GetTop(OPTR),c){case<:Push(OPTR,c);c=getchar( );break;case=:Pop(OPTR,x);c=getchar( );break;case>:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression3、中序遍歷遞歸算法voidInOrderTraverse(BiTreeT,Status(*Visit)(ElemTypee)){//采納二叉鏈表存貯二叉樹，visit( )是接見結(jié)點(diǎn)的函數(shù)本算法中序遍歷以T為根結(jié)點(diǎn)指針的二叉樹if(T)10{InOrderTraverse(T->lchild,Visit);Visit(T->data)；InOrderTraverse(T->rchild,Visit);}}//InOrderTraverse4、在有序表ST中折半查找法查找其重點(diǎn)字等于key的數(shù)據(jù)元素。若找到，則返回該元素在表中的地點(diǎn)，不然為0。intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if（EQ(key,ST.elem[mid].key))returnmid;elseif(LT(key,ST.elem[mid].key))high=mid-1;elselow=mid+1;}return0;}//Search_Bin六、給出以下算法的功能描繪或程序運(yùn)轉(zhuǎn)結(jié)果（一）、請描繪算法的功能1、typedefstructnode{datatypedata;structnode*link;}*LinkList;intAlgo(LinkListlist){if(list==NULL)return0;elsereturn1+Algo(list->link);11}答案：計(jì)算由list所指的線性鏈表的長度。2、voidAlgo(BiTree&p){if(!p->rchild){q=p;p=p->lchild;free(q);}elseif(!p->lchild){q=p;p=p->rchild;free(q);}else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;free(s);}}答案：從二叉排序樹中刪除結(jié)點(diǎn)p，并重接它的左或右子樹3、voidAlgo(adjlistg){inti，j，k;structvexnode*s;for(k=1;k<=n;k++){g[k].data=k;g[k].link=NULL;}printf("輸入一個(gè)偶對(弧尾和弧頭):");scanf("%d，%d"，&i，&j);while(i!=0&&j!=0){s=(structvexnode*)malloc(sizeof(vexnode));s->adjvex=j;s->next=g[i].link;g[i].link=s;printf("輸入一個(gè)偶對(弧尾和弧頭):");scanf("%d，%d"，&i，&j);12}}答案：依據(jù)用戶輸入的偶對（以輸入0表示結(jié)束）成立其有向圖的毗鄰表。（二）、請給出程序的運(yùn)轉(zhuǎn)結(jié)果4、voidmain( ){QueueQ;InitQueue(Q);charx='e',y='c';EnQueue(Q,'h');EnQueue(Q,'r');EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,'a');while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);}printf(x);}答案：char