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

一、選擇題1、從邏輯構(gòu)造上能夠把數(shù)據(jù)構(gòu)造分為【C】。A、動(dòng)向構(gòu)造和靜態(tài)構(gòu)造B、緊湊構(gòu)造和非緊湊構(gòu)造C、線性構(gòu)造和非線性構(gòu)造D、內(nèi)部構(gòu)造和外面構(gòu)造2、在一個(gè)長(zhǎng)度為n的序次儲(chǔ)藏的線性表中，向第i個(gè)元素（1in+1）從前插入一個(gè)新元素時(shí)，需要從后向前依次后移【B】個(gè)元素。A、n-iB、n-i+1C、n-i-1D、i3、鏈表構(gòu)造不擁有以下【B】特點(diǎn)。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)，則執(zhí)行【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è)隊(duì)列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è)鏈隊(duì)列中，假設(shè)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)的右邊【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、它們的邏輯構(gòu)造不一樣B、施加在其上的操作不一樣C、所包含的數(shù)據(jù)元素種類不一樣D、儲(chǔ)藏實(shí)現(xiàn)不一樣樣15、序次查找適用于儲(chǔ)藏構(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、按從左到右序次編號(hào)的二叉樹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二、判斷對(duì)錯(cuò)x】1、擁有n個(gè)極點(diǎn)的連通圖最少有n條邊。x】2、鏈表的單個(gè)結(jié)點(diǎn)內(nèi)部的儲(chǔ)藏空間能夠是不連續(xù)的。】3、棧和隊(duì)列的共同點(diǎn)是只贊同在端點(diǎn)處插入和刪除元素?！?、使用循環(huán)隊(duì)列能夠解決隊(duì)列序次儲(chǔ)藏時(shí)的假溢出問題。x】5、要想經(jīng)過遍歷序列還原為獨(dú)一二叉樹，應(yīng)當(dāng)知道其先序序列和后序序列?！?、若一個(gè)結(jié)點(diǎn)是某二叉樹子樹的中序遍歷序列的第一個(gè)結(jié)點(diǎn)，則它也必是該子樹的后序遍歷序列的第一個(gè)結(jié)點(diǎn)。x】7、完好二叉樹可采用序次儲(chǔ)藏構(gòu)造儲(chǔ)藏，非完好二叉樹則不能夠。2【】8、對(duì)于一棵含有n個(gè)結(jié)點(diǎn)的完好二叉樹，將其結(jié)點(diǎn)按從上到下且從左至右按1至n進(jìn)行編號(hào)，則對(duì)其任意一個(gè)編號(hào)為i的結(jié)點(diǎn)，若是它有左孩子，則其左孩子結(jié)點(diǎn)的編號(hào)為2i?！尽?、哈夫曼樹的所有子樹也都是哈夫曼樹。【x】10、當(dāng)圖的邊較少而結(jié)點(diǎn)很多時(shí)，求其最小生成樹用Prim算法比用Kruskal算法效率更高。三、填空題1、向量的第一個(gè)元素的儲(chǔ)藏地址是200，每個(gè)元素的長(zhǎng)度是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)隊(duì)列中插入數(shù)據(jù)元素時(shí)，需要判滿隊(duì)列可否已經(jīng)滿了，判斷條件是：。答案:(rear+1)%MaxSize==front6、已知循環(huán)隊(duì)列用數(shù)組data[1n]儲(chǔ)藏元素值，front和rear分別表示隊(duì)頭和隊(duì)尾指針，則當(dāng)前隊(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)值構(gòu)造哈夫曼樹，則其最短帶權(quán)路徑長(zhǎng)度為。答案:5510、已知某二叉樹的中序序列和前序序列分別為42758136、12457836，則它的后序序列為。3答案:4785263112、在有n個(gè)極點(diǎn)的有向圖中，每個(gè)極點(diǎn)的度最大可達(dá)到。答案:2(n-1)13、在有序表A[118]中，采用折半查找算法查找元素值等于A[7]的元素，所比較過的元素的下標(biāo)依次為。答案:946714、一組記錄的輸入序次為(25,38,65,90,72,14)，則利用堆排序方法建立的初始“小頂堆”為。答案:14,38,25,90,72,65四、簡(jiǎn)答題1、設(shè)有一段正文是由字符集{a,b,c,d,e,f,g,h}組成，正文長(zhǎng)度為100個(gè)字符，其中每個(gè)字符在正文中出現(xiàn)的次數(shù)分別為17,12,14,4,10,9,20,3。若采用哈夫曼樹對(duì)這段文字進(jìn)行壓縮儲(chǔ)藏，請(qǐng)完成以下工作：（1）構(gòu)造哈夫曼樹（規(guī)定權(quán)值較小的結(jié)點(diǎn)為左子樹）；（2）求出每個(gè)字符的哈夫曼編碼；（3）若其中一段正文的二進(jìn)制編碼序列為“”，請(qǐng)按（2）的哈夫曼編碼將其譯碼成原始正文。答案：（1）樹的構(gòu)造為：0891365301011620223100101g017910121417013ebfca34hd（2）編碼為a=111，b=101，c=110，d=0001，e=100，f=001，g=01，h=0000（3）上述編碼序列的對(duì)應(yīng)原文為：badegg42、一棵有11個(gè)結(jié)點(diǎn)的二叉樹的儲(chǔ)藏情況以以下列圖所示（其中“∧”表示空指針），left[i]和right[i]分別表示結(jié)點(diǎn)i的左、右孩子，根結(jié)點(diǎn)是序號(hào)為3的結(jié)點(diǎn)，要求：（1）畫出該二叉樹；（2）分別寫出該二叉樹的前序和中序遍歷序列。結(jié)點(diǎn)編號(hào)i1234567891011LeftChild[i]6∧7∧8∧5∧2∧∧Data[i]MFADKBLRCSERightChild[i]∧∧9∧10411∧1∧∧第2題圖答案：（1）二叉樹的構(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ù)，構(gòu)造一棵二叉排序樹Bt；（2）如何依照此二叉樹Bt求得數(shù)據(jù)會(huì)集D的一個(gè)有序序列？并寫出該有序序列；（3）畫出在上述二叉樹中刪除結(jié)點(diǎn)“12”后獲取的二叉樹構(gòu)造。答案：（1）構(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后的二叉樹構(gòu)造為下面任意一種構(gòu)造：2241597105也許

32356224932710355154、用深度優(yōu)先和廣度優(yōu)先遍歷算法對(duì)以下列圖G進(jìn)行遍歷（要求從極點(diǎn)A出發(fā)），請(qǐng)給出深度優(yōu)先和廣度優(yōu)先遍歷序列。ABCEHFDG第4題圖答案：深度優(yōu)先序列：ABFDEGHC廣度優(yōu)先序列：ABCFDEHG5、對(duì)于以下所示的加權(quán)無向圖，寫出用Prim算法構(gòu)造最小生成樹的過程，并畫出最后獲取的最小生成樹。A3D24E9841710F5G611BC712第5題圖答案：最小生成樹的構(gòu)造過程以以下列圖所示：ADE1FGBCAD2E1FGBCA3D2E1FGA32DCBE41FG8BCA32DE41FG6BCA32DE417FG6BC五、依照指定功能，完成以下算法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ù)元素。若找到，則返回該元素在表中的地址，否則為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)行結(jié)果（一）、請(qǐng)描述算法的功能1、typedefstructnode{datatypedata;structnode*link;}*LinkList;intAlgo(LinkListlist){if(list==NULL)return0;elsereturn1+Algo(list->link);11}答案：計(jì)算由list所指的線性鏈表的長(zhǎng)度。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è)偶對(duì)(弧尾和弧頭):");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è)偶對(duì)(弧尾和弧頭):");scanf("%d，%d"，&i，&j);12}}答案：依照用戶輸入的偶對(duì)（以輸入0表示結(jié)束）建立其有向圖的毗鄰表。（二）、請(qǐng)給出程序的運(yù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);}答案：char5、#defin