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

1、一、選擇題1、從邏輯結(jié)構(gòu)上可以把數(shù)據(jù)結(jié)構(gòu)分為【 C 】。A、動態(tài)結(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、在一個長度為n的順序存儲的線性表中，向第i個元素（1£i£n+1）之前插入一個新元素時，需要從后向前依次后移【 B 】個元素。A、n-iB、n-i+1C、n-i-1D、i3、鏈表結(jié)構(gòu)不具有下列【 B 】特點。A、插入和刪除無需移動元素B、可隨機訪問鏈表中的任意元素C、無需實現(xiàn)分配存儲空間D、所需空間與結(jié)點個數(shù)成正比。4、在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行【C 】。A、s-&

2、gt;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、一個棧的入棧序列是1，2，3，4，5，則棧不可能輸出的序列是【 C 】。A、54321B、45321C、43512D、123456、判斷一個隊列Q（元素最多為M個）為空的條件是【 C 】。A、Q->rear Q->front = MB、Q->rear Q->front -1 =MC

3、、Q->rear = Q->frontD、Q->rear + 1 = Q->front7、在一個鏈隊列中，假設(shè)f和r分別指向隊首和隊尾，則插入s所指結(jié)點的運算是【 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 】個結(jié)點。A、31B、32C、16D、109、在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊【 A 】。A、只有右子樹上的所有結(jié)點B、只有右子樹上的部分結(jié)點C、只有左子樹上的所有結(jié)點B、只有左子樹

4、上的部分結(jié)點10、如果一棵完全二叉樹有1001個結(jié)點，則其葉子結(jié)點個數(shù)為【 D 】。A、250B、500C、502D、49011、在一個圖中，所有頂點的度數(shù)之和是所有邊數(shù)的【 C 】倍。A、1/2B、1C、2D、412、采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的【 A 】。A、先序遍歷B、中序遍歷C、后序遍歷D、按層遍歷13、一個有n個頂點的無向圖最多有【D】條邊。A、nB、n(n-1)C、2nD、n(n-1)/214、靜態(tài)查找表與動態(tài)查找表的根本區(qū)別在于【 B 】。A、它們的邏輯結(jié)構(gòu)不同B、施加在其上的操作不同C、所包含的數(shù)據(jù)元素類型不同D、存儲實現(xiàn)不一樣15、順序查找適用于存儲結(jié)構(gòu)

5、為【 C 】的線性表。A、哈希存儲B、壓縮存儲C、順序存儲或鏈式存儲D、索引存儲16、若一顆二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足【 B 】。A、所有結(jié)點均無孩子B、所有結(jié)點均無右孩子C、只有一個葉子結(jié)點D、是一顆滿二叉樹17、二叉排序樹是【 B】。A、每一分支結(jié)點的度均為2的二叉樹B、中序遍歷得到一升序序列的二叉樹C、按從左到右順序編號的二叉樹D、每一分支結(jié)點的值均小于左子樹上所有結(jié)點的值，又大于右子樹上所有結(jié)點的值18、具有12個記錄的序列，采用冒泡排序最少的比較次數(shù)是【 C 】。A、1B、144C、11D、6619、堆的形狀是一棵【 C 】。A、二叉排序樹B、滿二

6、叉樹C、完全二叉樹D、平衡二叉樹20、在一個包含n個頂點e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為【 D 】。A、eB、2eC、n2-eD、n2-2e二、判斷對錯【 x 】1、具有n個頂點的連通圖至少有n條邊?！?x 】2、鏈表的單個結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的?！?Ö 】3、棧和隊列的共同點是只允許在端點處插入和刪除元素?！?Ö 】4、使用循環(huán)隊列可以解決隊列順序存儲時的假溢出問題。【 x 】5、要想通過遍歷序列還原為惟一二叉樹，應(yīng)當知道其先序序列和后序序列?！?Ö 】6、若一個結(jié)點是某二叉樹子樹的中序遍歷序列的第一個結(jié)點，則它也必是該子樹的后序遍歷序列的第

7、一個結(jié)點?！?x 】7、完全二叉樹可采用順序存儲結(jié)構(gòu)存儲，非完全二叉樹則不能?！?Ö 】8、對于一棵含有n個結(jié)點的完全二叉樹，將其結(jié)點按從上到下且從左至右按1至n進行編號，則對其任意一個編號為i的結(jié)點，如果它有左孩子，則其左孩子結(jié)點的編號為2i。【 Ö 】9、哈夫曼樹的所有子樹也都是哈夫曼樹。【 x 】10、當圖的邊較少而結(jié)點較多時，求其最小生成樹用Prim算法比用Kruskal算法效率更高。三、 填空題1、向量的第一個元素的存儲地址是200，每個元素的長度是3，那么第6個元素的存儲地址是 。答案：2152、在一個帶頭結(jié)點的單鏈表中，p所指結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點

8、，刪除p結(jié)點的語句序列是 、 、 。答案: q=p，p=p->next，free(q)3、設(shè)堆棧有足夠的存儲空間，那么向堆棧中插入一個數(shù)據(jù)元素，即入棧的操作過程是 、 。答案: 存入數(shù)據(jù)元素，棧頂指針加1 4、一般情況下，向循環(huán)隊列中插入數(shù)據(jù)元素時，需要判滿隊列是否已經(jīng)滿了，判斷條件是： 。答案: (rear+1)%MaxSize = front6、已知循環(huán)隊列用數(shù)組data1n存儲元素值，front和rear分別表示隊頭和隊尾指針，則當前隊列中元素的個數(shù)為 。答案: (n+rear-frone)%n或(n+rear-frone) mod n7、深度為k的二叉樹最多有 個結(jié)點，深度為k的

9、完全二叉樹最少有 個結(jié)點（k1）。答案: 2k-1，2k-18、如以2,3,6,7,9作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其最短帶權(quán)路徑長度為 。答案: 5510、已知某二叉樹的中序序列和前序序列分別為42758136、12457836，則它的后序序列為 。答案: 4785263112、在有n個頂點的有向圖中，每個頂點的度最大可達到 。答案: 2(n-1) 13、在有序表A118中，采用折半查找算法查找元素值等于A7的元素，所比較過的元素的下標依次為 。答案: 9 4 6 714、一組記錄的輸入順序為(25,38,65,90,72,14)，則利用堆排序方法建立的初始“小頂堆”為 。答案: 14,

10、38,25,90,72,65 四、簡答題1、設(shè)有一段正文是由字符集a, b, c, d, e, f, g, h組成，正文長度為100個字符，其中每個字符在正文中出現(xiàn)的次數(shù)分別為17, 12, 14, 4, 10, 9, 20, 3。若采用哈夫曼樹對這段文字進行壓縮存儲，請完成如下工作：（1）構(gòu)造哈夫曼樹（規(guī)定權(quán)值較小的結(jié)點為左子樹）；（2）求出每個字符的哈夫曼編碼；（3）若其中一段正文的二進制編碼序列為“10111100011000101”，請按（2）的哈夫曼編碼將其譯碼成原始正文。答案：（1） 樹的結(jié)構(gòu)為：fhdaebcg11111110000000343120093736161012142

11、2175389（2）編碼為a=111，b=101，c=110，d=0001，e=100，f=001，g=01，h=0000（3）上述編碼序列的對應(yīng)原文為：badegg2、一棵有11個結(jié)點的二叉樹的存儲情況如下圖所示（其中“”表示空指針），lefti和righti分別表示結(jié)點i的左、右孩子，根結(jié)點是序號為3的結(jié)點，要求：（1）畫出該二叉樹；（2）分別寫出該二叉樹的前序和中序遍歷序列。結(jié)點編號i1234567891011LeftChildi67852DataiMFADKBLRCSERightChildi9104111第2題圖答案： （1）二叉樹的結(jié)構(gòu)如圖所示：743RSE3KLAC0F0M0B0D

12、0（2） 前序序列 ALKRSECFMBD中序序列 RKSLEAFCBDM3、設(shè)數(shù)據(jù)集合D=2, 24, 12, 15, 32, 9, 10, 35, 7, 5，要求：（1）依次讀取D中的各個數(shù)據(jù)，構(gòu)造一棵二叉排序樹Bt；（2）如何根據(jù)此二叉樹Bt求得數(shù)據(jù)集合D的一個有序序列？并寫出該有序序列；（3）畫出在上述二叉樹中刪除結(jié)點“12”后得到的二叉樹結(jié)構(gòu)。答案：（1）構(gòu)造的二叉排序樹如下：7912243251510352（2）上述二叉樹Bt的中序遍歷序列即是數(shù)據(jù)集合D的一個有序序列：2，5，7，9，10，12，15，24，32，35（3）刪除結(jié)點12后的二叉樹結(jié)構(gòu)為下面任意一種結(jié)構(gòu)：791524

13、32510352或者791524325103524、用深度優(yōu)先和廣度優(yōu)先遍歷算法對下圖G進行遍歷（要求從頂點A出發(fā)），請給出深度優(yōu)先和廣度優(yōu)先遍歷序列。BFDECHGA第4 題圖答案：深度優(yōu)先序列：ABFDEGHC 廣度優(yōu)先序列：ABCFDEHG 5、對于如下所示的加權(quán)無向圖，寫出用Prim算法構(gòu)造最小生成樹的過程，并畫出最后得到的最小生成樹。DA3E429148710FG5116BC12第5題圖答案：最小生成樹的構(gòu)造過程如下圖所示：1AGEFCBD21AGEFCBD231AGEFCBD2431AGEFCBD26431AGEFCBD726431AGEFCBD五、按照指定功能，完成下列算法1、逆

14、置帶頭結(jié)點的單鏈表 Lvoid inverse(LinkList &L) p=L->next; L->next=NULL; while ( p) succ=p->next; p->next=L->next; L->next=p; p = succ; 2、算術(shù)表達式求值的算符優(yōu)先算法。設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧，OP為運算符、界限符集合。operandType EvaluateExpression( ) InitStack(OPTR); Push (OPTR, #); InitStack(OPND); c=getchar( ); wh

15、ile ( 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)

16、); break; /switch /whilereturn GetTop(OPND); /EvaluateExpression3、中序遍歷遞歸算法void InOrderTraverse ( BiTree T , Status ( * Visit ) ( ElemType e ) ) / 采用二叉鏈表存貯二叉樹， visit( )是訪問結(jié)點的函數(shù) / 本算法中序遍歷以T為根結(jié)點指針的二叉樹 if ( T ) InOrderTraverse ( T->lchild, Visit ); Visit ( T->data )； InOrderTraverse ( T->rchild

17、, Visit ); /InOrderTraverse4、在有序表ST中折半查找法查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則返回該元素在表中的位置，否則為0。int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; while (low <= high) mid = (low + high) / 2; if （EQ (key , ST.elemmid.key) ) return mid; else if ( LT (key , ST.elemmid.key) ) high = mid - 1; else

18、low = mid + 1; return 0; / Search_Bin六、給出下列算法的功能描述或程序運行結(jié)果（一）、請描述算法的功能1、typedef struct nodedatatype data;struct node *link; *LinkList;int Algo(LinkList list)if(list=NULL)return 0;elsereturn 1+Algo(list->link);答案：計算由list所指的線性鏈表的長度。2、void Algo ( BiTree &p ) if ( ! p->rchild ) q = p; p = p->

19、;lchild; free(q); else if ( ! 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; else q->lchild = s->lchild; free(s); 答案：從二叉排序樹中刪除結(jié)點p，并重接它的左或右子樹3、void

20、Algo(adjlist g) int i，j，k; struct vexnode *s; for (k=1;k<=n;k+) gk.data=k; gk.link=NULL; printf("輸入一個偶對(弧尾和弧頭):"); scanf("%d，%d"，&i，&j); while (i!=0 && j!=0) s=(struct vexnode *)malloc(sizeof(vexnode); s->adjvex=j; s->next=gi.link; gi.link=s; printf("

21、;輸入一個偶對(弧尾和弧頭):"); scanf("%d，%d"，&i，&j); 答案：根據(jù)用戶輸入的偶對（以輸入0表示結(jié)束）建立其有向圖的鄰接表。（二）、請給出程序的運行結(jié)果4、void main()Queue Q; InitQueue(Q);char x='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