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

1、一、選擇題1、從邏輯結(jié)構(gòu)上可以把數(shù)據(jù)結(jié)構(gòu)分為【 C 】。A、動(dòng)態(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、在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，向第i個(gè)元素（1£i£n+1）之前插入一個(gè)新元素時(shí)，需要從后向前依次后移【 B 】個(gè)元素。A、n-iB、n-i+1C、n-i-1D、i3、鏈表結(jié)構(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-&

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、一個(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

3、、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、只有左子樹

4、上的部分結(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 】。A、先序遍歷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)態(tài)查找表的根本區(qū)別在于【 B 】。A、它們的邏輯結(jié)構(gòu)不同B、施加在其上的操作不同C、所包含的數(shù)據(jù)元素類型不同D、存儲(chǔ)實(shí)現(xiàn)不一樣15、順序查找適用于存儲(chǔ)結(jié)構(gòu)

5、為【 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、滿二

6、叉樹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)處插入和刪除元素?！?Ö 】4、使用循環(huán)隊(duì)列可以解決隊(duì)列順序存儲(chǔ)時(shí)的假溢出問題。【 x 】5、要想通過遍歷序列還原為惟一二叉樹，應(yīng)當(dāng)知道其先序序列和后序序列?！?Ö 】6、若一個(gè)結(jié)點(diǎn)是某二叉樹子樹的中序遍歷序列的第一個(gè)結(jié)點(diǎn)，則它也必是該子樹的后序遍歷序列的第

7、一個(gè)結(jié)點(diǎn)?！?x 】7、完全二叉樹可采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，非完全二叉樹則不能?！?Ö 】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。【 Ö 】9、哈夫曼樹的所有子樹也都是哈夫曼樹。【 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)

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

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

10、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)制編碼序列為“10111100011000101”，請(qǐng)按（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）上述編碼序列的對(duì)應(yīng)原文為：badegg2、一棵有11個(gè)結(jié)點(diǎn)的二叉樹的存儲(chǔ)情況如下圖所示（其中“”表示空指針），lefti和righti分別表示結(jié)點(diǎn)i的左、右孩子，根結(jié)點(diǎn)是序號(hào)為3的結(jié)點(diǎn)，要求：（1）畫出該二叉樹；（2）分別寫出該二叉樹的前序和中序遍歷序列。結(jié)點(diǎn)編號(hào)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中的各個(gè)數(shù)據(jù)，構(gòu)造一棵二叉排序樹Bt；（2）如何根據(jù)此二叉樹Bt求得數(shù)據(jù)集合D的一個(gè)有序序列？并寫出該有序序列；（3）畫出在上述二叉樹中刪除結(jié)點(diǎn)“12”后得到的二叉樹結(jié)構(gòu)。答案：（1）構(gòu)造的二叉排序樹如下：7912243251510352（2）上述二叉樹Bt的中序遍歷序列即是數(shù)據(jù)集合D的一個(gè)有序序列：2，5，7，9，10，12，15，24，32，35（3）刪除結(jié)點(diǎn)12后的二叉樹結(jié)構(gòu)為下面任意一種結(jié)構(gòu)：791524

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

14、置帶頭結(jié)點(diǎn)的單鏈表 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ù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符、界限符集合。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é)點(diǎn)的函數(shù) / 本算法中序遍歷以T為根結(jié)點(diǎn)指針的二叉樹 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六、給出下列算法的功能描述或程序運(yùn)行結(jié)果（一）、請(qǐng)描述算法的功能1、typedef struct nodedatatype data;struct node *link; *LinkList;int Algo(LinkList list)if(list=NULL)return 0;elsereturn 1+Algo(list->link);答案：計(jì)算由list所指的線性鏈表的長(zhǎng)度。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é)點(diǎn)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("輸入一個(gè)偶對(duì)(弧尾和弧頭):"); 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、;輸入一個(gè)偶對(duì)(弧尾和弧頭):"); scanf("%d，%d"，&i，&j); 答案：根據(jù)用戶輸入的偶對(duì)（以輸入0表示結(jié)束）建立其有向圖的鄰接表。（二）、請(qǐng)給出程序的運(yùn)行結(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