期末數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)習(xí)題含答案

1、 數(shù)據(jù)結(jié)構(gòu)練習(xí)題數(shù)據(jù)結(jié)構(gòu)練習(xí)題（15章）一、選擇題1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。A動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2、以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（ D ）？ A廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串3、在下面的程序段中，對(duì)x的賦值語句的頻度為（ C ）for (i=1;i<=n;i+)for (j=1;j<=n;i+) x=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 4、下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ B ）A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。

2、B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。5、某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ D ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6、 靜態(tài)鏈表中指針表示的是（ B ）. A 內(nèi)存地址 B數(shù)組下標(biāo) C下一元素地址 D左、右孩子地址7、下面的敘述不正確的是（ BC ）A線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比 B. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)C. 線性表在順序存儲(chǔ)時(shí)

3、，查找第i個(gè)元素的時(shí)間同i 的值成正比D. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)8、 若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ C ）(1<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2) 9、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：（ B ）。Ap->next=s;s->next=p->next; B s->next=p->next;p->next=s;Cp->next=s;p->next=s->next; D

4、p->next=s->next;p->next=s;10、對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ B ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL11、 一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）個(gè)元素是（ B ）。A. 不確定 B. n-i+1 C. i D. n-i12、 有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？（ C ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4

5、 6 5 2 1 D. 2 3 4 1 5 6 13、 設(shè)有三個(gè)元素X，Y，Z順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到的出棧排列是( C )。AXYZ B. YZX C. ZXY D. ZYX14、 假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ A ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m15、 若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別

6、為多少？( B ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 16、下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（ B ）A串是字符的有限序列 B空串是由空格構(gòu)成的串->(空格串是由空格組成的)C模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)17、設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ C ）A求子串 B聯(lián)接 C匹配 D求串長18、 設(shè)有數(shù)組Ai,j，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A5，8的存儲(chǔ)首地址為( B )。30*61

7、80A. BA+141 B. BA+180 C. BA+222 D. BA+22519、已知廣義表L=（x,y,z），a，（u，t，w），從L表中取出原子項(xiàng)t的運(yùn)算是（ D ）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）20、廣義表A=(a,b,(c,d),(e,(f,g),則下面式子的值為（ D ）。Head(Tail(Head(Tail(Tail(A)A. (g) B. (d) C. c D. d二、判斷題1、 數(shù)據(jù)元素是數(shù)

8、據(jù)的最小單位。( × )2、算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級(jí)語言來描述，則算法實(shí)際上就是程序了。( Y ) 3、 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。( × )4、線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。( × )5、線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。( × )6、一個(gè)稀疏矩陣Am*n采用三元組形式表示， 若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。（ × ） 7、所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。（

9、 × ）三、填空題1、數(shù)據(jù)的物理結(jié)構(gòu)包括 數(shù)據(jù)元素 的表示和 關(guān)系 的表示。2、當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_順序_存儲(chǔ)結(jié)構(gòu)。3、線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_(n-1)/2_。4、對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_O(1)_,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_ O(n)_。5、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是：_L->next->next=L

10、 _6、一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是_3 1 2_。7、用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_ SXSSXSXX_。8、_隊(duì)列_又稱作先進(jìn)先出表。9、組成串的數(shù)據(jù)元素只能是_字符_。 10、設(shè)有C語言描述的二維數(shù)組A1020,其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為100，若按行優(yōu)先順序存儲(chǔ)，則元素A66存儲(chǔ)地址為_352_。(沒說明，則下標(biāo)從0開始) 四、算法與應(yīng)用題1. 設(shè)線性表存放在向量Aarrsize的前elenum個(gè)分量中且遞增有序，試寫一算法將x插入到線性表的適當(dāng)位置，以保持線性表

11、的有序性并分析其時(shí)間復(fù)雜度。#define arrsize 100bool sortinsert(Elemtype A,int elenum , Elemtype x)int i;if(elenum = = arrsize) printf(“該數(shù)組向量已滿”)； return false;i=elenum-1;while(Ai>x && i>=0)Ai+1=Ai; i- -;Ai+1=x;return true;/ 2.已知帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫一算法將值x為的結(jié)點(diǎn)插入到表L中，使L仍然有序。/線性表的單鏈表存儲(chǔ)結(jié)構(gòu) typedef

12、 struct Lnode ElemType data; struct Lnode *next; LNode , *LinkList;LinkList sortinsert(LinkList L,int x) /* 帶頭結(jié)點(diǎn)*/ LinkList p,q, s; s=(LinkList)malloc(sizeof(LNode); if(!s) printf(“動(dòng)態(tài)空間分配不成功”)； exit(-1);s->data=x; q=L; p=L->next; while ( p!=NULL && p->data <x) q=p;p=p->next; s

13、->next=q->next; q->next=s ; return L; 3.在長度大于1的單循環(huán)鏈表L中，既無頭結(jié)點(diǎn)也無頭指針。s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)*s的直接前趨結(jié)點(diǎn)。/條件是長度大于一#include <iostream>using namespace std;typedef struct Lnode ElemType data; struct Lnode *next; LNode , *LinkList;bool delete_prior(LinkList s)LinkList p;LinkList q;q=s;p=s->

14、next;while(p->next!=s) q=p; p=p->next;q->next =s;delete p;五、程序填空題1、 下面是用c語言編寫的對(duì)不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當(dāng)?shù)恼Z句。void reverse（linklist &L）p=null；q=L；while（q！=null） (1) L=L->next ; q->next=p；p=q；(2) q=L _ ; (3) L=p； 2、對(duì)單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結(jié)點(diǎn)指針。請(qǐng)?zhí)畛渌惴ㄖ袠?biāo)出的空白

15、處，完成其功能。（10分）typedef struct node int data; struct node *next; linknode,*link;void Insertsort(link L) link p,q,r,u; p=L->next; (1) L->next=NULL _; while(2)_ p!=NULL _) r=L; q=L->next; while(3) q!=NUll _&& q->data<=p->data) r=q; q=q->next; u=p->next; (4)_ p->next=q _

16、 ; (5)_ r->next= p_; p=u; 第六章練習(xí)選擇題1. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ D ）A5 B6 C7 D82. 設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（ A ）Am-n Bm-n-1 Cn+1 D條件不足，無法確定3若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（B ）A9 B11 C15 D不確定4具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有（ B ）個(gè)度為2的結(jié)點(diǎn)， A8 B9 C10 Dll5一棵完全二叉樹上有1001個(gè)

17、結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ E ）A 250 B 500 C254 D505 E以上答案都不對(duì) 6. 有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（ D ）。A不確定 B2n C2n+1 D2n-17. 一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（ A ）Aëlognû+1 Blogn+1 Cëlognû Dlogn-18深度為h的滿m叉樹的第k層有（ A）個(gè)結(jié)點(diǎn)。(1=<k=<h) Amk-1 Bmk-1 Cmh-1 Dmh-19在一棵高度為k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（ C）A2k-1 B2k C2k-1 Dëlog2kû+

18、110對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用( C )次序的遍歷實(shí)現(xiàn)編號(hào)。A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷11樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的( B ). A. 先序序列 B. 中序序列 C. 后序序列12已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ D ）。 Aacbed Bdecab Cdeabc Dcedba13二叉樹的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹根的

19、右子樹的根是： CA、 E B、 F C、 G D、 H 14對(duì)于前序遍歷與中序遍歷結(jié)果相同的二叉樹為（F）;對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹為（B）。A一般二叉樹 B只有根結(jié)點(diǎn)的二叉樹 C根結(jié)點(diǎn)無左孩子的二叉樹 D根結(jié)點(diǎn)無右孩子的二叉樹 E所有結(jié)點(diǎn)只有左子數(shù)的二叉樹 F所有結(jié)點(diǎn)只有右子樹的二叉樹15一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ C ）A所有的結(jié)點(diǎn)均無左孩子B所有的結(jié)點(diǎn)均無右孩子C只有一個(gè)葉子結(jié)點(diǎn)D是任意一棵二叉樹16. 引入二叉線索樹的目的是（ A ）A加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B為了能在二叉樹中方便的進(jìn)行插入與刪除C為了能方便的找到

20、雙親 D使二叉樹的遍歷結(jié)果唯一17n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（ C ）A2n Bnl Cnl Dn18（ C）的遍歷仍需要棧的支持.A前序線索樹 B中序線索樹 C后序線索樹 19二叉樹在線索后，仍不能有效求解的問題是（ D ）。A前（先）序線索二叉樹中求前（先）序后繼 B中序線索二叉樹中求中序后繼C中序線索二叉樹中求中序前驅(qū) D后序線索二叉樹中求后序后繼 20由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（ D ）A2 B3 C4 D5 21下述編碼中哪一個(gè)不是前綴碼（ B ）。A（00，01，10，11） B（0，1，00，11） C（0，10，110，111） D（1，01，000，

21、001）22從下列有關(guān)樹的敘述中,選出5條正確的敘述(共5分) （ CDFHI ）A二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn),而樹無此限制,因此二叉樹是樹的特殊情況。B當(dāng)K1時(shí)高度為K的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。C用樹的前序周游和中序周游可以導(dǎo)出樹的后序周游。D線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。E將一棵樹轉(zhuǎn)換成二叉樹后,根結(jié)點(diǎn)沒有左子樹。F一棵含有N個(gè)結(jié)點(diǎn)的完全二叉樹,它的高度是ëLOG2Nû+1。G在二叉樹中插入結(jié)點(diǎn),該二叉樹便不再是二叉樹。H采用二叉樹鏈表作樹的存儲(chǔ)結(jié)構(gòu),樹的前序周游和其相應(yīng)的二叉樹的前序周游的結(jié)果是一樣的。I哈夫曼樹是帶權(quán)路徑最短的樹,路徑上

22、權(quán)值較大的結(jié)點(diǎn)離根較近。J用一維數(shù)組存儲(chǔ)二叉樹時(shí),總是以前序周游存儲(chǔ)結(jié)點(diǎn)。判斷題1完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。2. 二叉樹只能用二叉鏈表表示。×3在二叉樹的第i層上至少有2i-1個(gè)結(jié)點(diǎn)(i>=1) ×4度為二的樹就是二叉樹。×5. 在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點(diǎn)。填空題：1如某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)數(shù)為_69_。2具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_9_。3已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹有_12_個(gè)葉子結(jié)點(diǎn)。4在一棵二叉

23、樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為N2,則有N0 =_ N2 _+ 1_5已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是_99_。6一個(gè)有2001個(gè)結(jié)點(diǎn)的完全二叉樹的高度為_11_。7設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對(duì)應(yīng)的二叉樹為B,已知T1,T2,T3的結(jié)點(diǎn)數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有_n1-1_個(gè)結(jié)點(diǎn)，右子樹中有_n2+n3_個(gè)結(jié)點(diǎn)。作業(yè)題1、給定一組權(quán)值2,3,5,7,11,13,17,19,23,29，31，37，41，（1）試畫出用Huffman算法建造的Huffman樹；（2）求平均編碼長度（）考慮概率解：（1）238143

24、95657834311717107552337415342242919231113（2）（7×（23）6×55×7 4×（176613）3×（313741291923）/ 2382、設(shè)一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列： A B D F C E G H 中序遍歷序列： B F D A G E H C（1）畫出這棵二叉樹。（2）畫出這棵二叉樹的后序線索樹。解：（1）ABCDEGHF(2)后序遍歷為：F D B G H E C AABCDEGHF3二叉樹存儲(chǔ)結(jié)構(gòu)同上題，以下程序?yàn)榍蠖鏄渖疃鹊倪f歸算法，請(qǐng)?zhí)羁胀晟浦?int dept

25、h(bitree bt) /*bt為根結(jié)點(diǎn)的指針*/int hl,hr; if (bt=NULL) return(1)_ 0_); hl=depth(bt->lchild); hr=depth(bt->rchild); if(2) hl>hr _) (3)_ hr=hl_； return(hr+1); 4線索二叉樹有數(shù)據(jù)域data，左右孩子域lchild和rchild，左右標(biāo)志ltag及rtag，規(guī)定標(biāo)志為1對(duì)應(yīng)的孩子域是線索，0則為指向孩子的指針。規(guī)定在儲(chǔ)存線索二叉樹時(shí)，完成下面中序線索化過程。（存儲(chǔ)線索二叉樹，不增加頭結(jié)點(diǎn)，只在原有的由tree指向的二叉樹中增加線索，此處

26、也不考慮c語言的具體語法與約定，線索化前所有的標(biāo)志tag都是0）。/* pre是同tree類型相同的指針，初值是null */thread_inorder (tree) if(tree!=null) thread_inorder(1) tree->lchild _); if(tree->lchild=(2)_ NULL_) tree->ltag=1; tree->lchild=pre; if(3) tree->rchild_ = null) (4) tree->rtag=1_; (5) tree->rchild=tree _;pre=p; thread

27、-inorder(6)_ tree->rchild _); 5、已知一棵滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)為20到40之間的素?cái)?shù)，此二叉樹的葉子結(jié)點(diǎn)有多少個(gè)？（請(qǐng)給出具體的推理過程）解： 166、一棵共有n個(gè)結(jié)點(diǎn)的樹，其中所有分支結(jié)點(diǎn)的度均為K，求該樹中葉子結(jié)點(diǎn)的個(gè)數(shù)。7. 假設(shè)一個(gè)二叉樹的兩種遍歷如下：前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA畫出這棵二叉樹以及它的中序線索樹；解：AB FCLJHGDIEKAB FCLJHGDIEK第七章練習(xí)選擇題1設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ B ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En22一個(gè)n個(gè)頂點(diǎn)的連

28、通無向圖，其邊的個(gè)數(shù)至少為（ A ）。An-1 Bn Cn+1 Dnlogn；3一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（ B ）個(gè)連通分量，最多有（ D ）個(gè)連通分量。A0 B1 Cn-1 Dn4在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ B ）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ C ）倍。A1/2 B2 C1 D45下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（ B ）A有向圖 B無向圖 CAOV網(wǎng) DAOE網(wǎng)6當(dāng)一個(gè)有N個(gè)頂點(diǎn)的圖用鄰接矩陣A表示時(shí)，頂點(diǎn)Vi的度是（B ）。A B C D+ 7無向圖G=(V,E),其中：V=a,b,c,d,e,f, E=(a,b),(a,e),

29、 (a,c), (b,e), (c,f), (f,d), (e,d)， 對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（ D ）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b8下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）：（ B ） A深度優(yōu)先遍歷 B. 拓?fù)渑判?C. 求最短路徑 D. 廣度優(yōu)先遍歷9. 在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的 Prim 算法的時(shí)間復(fù)雜度為( B )。A. O(n) B. O(n+e) C. O(n2) D. O(n3)10. 求解最短路徑的Floyd算法的時(shí)間復(fù)雜度為(D )。AO（n） B. O（

30、n+c） C. O（n*n） D. O（n*n*n）11已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>,G的拓?fù)湫蛄惺牵?A ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V712若一個(gè)有向

31、圖的鄰接距陣中,主對(duì)角線以下的元素均為零,則該圖的拓?fù)溆行蛐蛄校?A ）。 A存在 B不存在13一個(gè)有向無環(huán)圖的拓?fù)渑判蛐蛄校?B ）是唯一的。A一定 B不一定14. 在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（ D ）。 AG中有弧<Vi，Vj> BG中有一條從Vi到Vj的路徑 CG中沒有弧<Vi,Vj> DG中有一條從Vj到Vi的路徑15. 在用鄰接表表示圖時(shí)，拓?fù)渑判蛩惴〞r(shí)間復(fù)雜度為( B )。A. O(n) B. O(ne) C. O(n*n) D. O(n*n*n)16. 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ A ）。A從源點(diǎn)到匯點(diǎn)的最長

32、路徑 B從源點(diǎn)到匯點(diǎn)的最短路徑C最長回路 D最短回路17下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（ B ）。A關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成判斷題1. 有e條邊的無向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)。（ × ）2. 有向圖的鄰接矩陣是對(duì)稱的。（ × ）3任何無向圖都存在生成樹。（ × ）4. 不同的求最小生成樹的方法最后得到的生成樹是相同的.（ × ）5. 有環(huán)圖也能進(jìn)行拓?fù)渑判颉＃?× ）6.

33、 關(guān)鍵路徑是AOE網(wǎng)中從源點(diǎn)到終點(diǎn)的最長路徑。（ ）填空題1具有10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為_45_。2. 在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要_ n _條弧。3n個(gè)頂點(diǎn)的連通無向圖，其邊的條數(shù)至少為_n-1_。4N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有_2(n-1)_個(gè)非零元素。5構(gòu)造連通網(wǎng)最小生成樹的兩個(gè)典型算法是_普里姆算法、克魯斯卡爾算法_。6. 有一個(gè)用于n個(gè)頂點(diǎn)連通帶權(quán)無向圖的算法描述如下：（1）設(shè)集合T1與T2，初始均為空；（2）在連通圖上任選一點(diǎn)加入T1；（3）以下步驟重復(fù)n-1次：a.在i屬于T1，j不屬于T1的邊中選最小權(quán)的邊；b.該

34、邊加入T2。上述算法完成后，T2中共有_n-1_條邊，該算法稱_普里姆算法_算法，T2中的邊構(gòu)成圖的_最小生成樹_。7AOV網(wǎng)中,結(jié)點(diǎn)表示_活動(dòng)_,邊表示_聯(lián)系_。AOE網(wǎng)中,結(jié)點(diǎn)表示_事件_,邊表示_活動(dòng)_。8. 當(dāng)一個(gè)AOV網(wǎng)用鄰接表表示時(shí)，可按下列方法進(jìn)行拓?fù)渑判?。?）查鄰接表中入度為_零_的頂點(diǎn)，并進(jìn)棧；（2）若棧不空，則輸出棧頂元素Vj，并退棧；查Vj的直接后繼Vk，對(duì)Vk入度處理，處理方法是_ Vk 的入度減1，如為0則入棧_；（3）若?？諘r(shí)，輸出頂點(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)，說明有_環(huán)路_，否則拓?fù)渑判蛲瓿?。作業(yè)題1n個(gè)頂點(diǎn)的有向圖用鄰接矩陣array表示，下面是其拓?fù)渑判蛩?/p>

35、法，試補(bǔ)充完整。注：（1）圖的頂點(diǎn)號(hào)從 0開始計(jì)； （2）indegree 是有n個(gè)分量的一維數(shù)組，放頂點(diǎn)的入度；（3）函數(shù) crein 用于算頂點(diǎn)入度； （4）有三個(gè)函數(shù)push(data),pop( ),check( )其含義為數(shù)據(jù) data進(jìn)棧，退棧和測試棧是否空（不空返回1，否則0）。 crein( array ,indegree,n) for (i=0;i<n;i+) indegreei= (1)_ _0_) for(i=0,i<n;i+) for (j=0;j<n; j+) indegreei+=array(2)_ i_(3)_ _j_; topsort (arr

36、ay,indegree,n) count= (4)_ 0_) for (i=0;i<n;i+) if (5)_ indegreei=0_) push(i) while (check( ) vex=pop( ); printf(vex); count+; for (i=0;i<n;i+) k=array(6)_ vexi;_ if (7)_ k!=0_) indegreei-; if (8)_ indegreei=0_ ) push(i); if( count<n) printf(“圖有回路”)； 2設(shè)G=(V,E)以鄰接表存儲(chǔ)，如圖所示，試畫出圖的深度優(yōu)先和廣度優(yōu)先生成樹。解

37、：12345123453下圖表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費(fèi)的代價(jià)，如何選擇能溝通每個(gè)城市且總代價(jià)最省的n-1條線路，畫出所有可能的選擇。1365421656111818136542165611解：4、對(duì)下面的有向圖，試?yán)肈IJKSTRA算法從頂點(diǎn)1到其它頂點(diǎn)的最短路徑，并寫出執(zhí)行該算法過程中每次循環(huán)的狀態(tài)。v4v2v6v5v1v310101015430420215第十章選擇題1下面給出的四種排序法中( D )排序法是不穩(wěn)定性排序法。 A. 插入 B. 冒泡 C. 二路歸并 D. 堆排序2下列排序算法中，其中（ D ）是穩(wěn)定的。 A. 堆排序，冒泡排序

38、B. 快速排序，堆排序 C. 直接選擇排序，歸并排序 D. 歸并排序，冒泡排序3下面的排序算法中，不穩(wěn)定的是（ CDF ） A.起泡排序 B.折半插入排序 C.簡單選擇排序 D.希爾排序 E.基數(shù)排序 F.堆排序。4對(duì)一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 則采用的排序是 (A )。 A. 選擇 B. 冒泡 C. 快速 D. 插入5. 在下面的排序方法中，輔助空間為O（n）的是( D ) 。 A希爾排序

39、 B. 堆排序 C. 選擇排序 D. 歸并排序 6. 下列排序算法中，占用輔助空間最多的是：(A ) A. 歸并排序 B. 快速排序 C. 希爾排序 D. 堆排序7用直接插入排序方法對(duì)下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是（ C ）。A 94,32,40,90,80,46,21,69 B 32,40,21,46,69,94,90,80C 21,32,46,40,80,69,90,94 D 90,69,80,46,21,32,94,408直接插入排序在最好情況下的時(shí)間復(fù)雜度為（ B ） A O(logn) B O(n) C O(n*logn) D O(n2)9對(duì)下列關(guān)鍵字序列用快

40、速排序法進(jìn)行排序時(shí)，速度最快的情形是（A ）。A 21,25,5,17,9,23,30 B25,23,30,17,21,5,9C 21,9,17,30,25,23,5 5,9,17,21,23,25,3010下列四個(gè)序列中，哪一個(gè)是堆（ C ）。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15判斷1內(nèi)排序要求數(shù)據(jù)一定要以順序方式存儲(chǔ)。 （ × ）2排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（ 

41、5; ）3直接選擇排序算法在最好情況下的時(shí)間復(fù)雜度為O（N）。（× ）4在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。（ × ）5快速排序總比選擇排序快。（）填空1若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的_比較_和記錄的_移動(dòng)_。2關(guān)鍵碼序列（ Q，H，C，Y，Q，A，M，S，R，D，F(xiàn)，X），要按照關(guān)鍵碼值遞增的次序進(jìn)行排序，若采用初始步長為4的Shell排序法，則一趟掃描的結(jié)果是_ Q A C S Q D F X R H M Y _；若采用以第一個(gè)元素為分界元素的快速排序法，則掃描一趟的結(jié)果是_ F H C D M A Q S R Q Y X

42、_。 作業(yè)題1下面的排序算法的思想是：第一趟比較將最小的元素放在r1中，最大的元素放在rn中，第二趟比較將次小的放在r2中，將次大的放在rn-1中，,依次下去，直到待排序列為遞增序。（注：<->）代表兩個(gè)變量的數(shù)據(jù)交換）。void sort(SqList &r,int n) i=1;while(1) i< n/2_) min=max=1;for (j=i+1;(2)_ j<=n-i+1_ ;+j) if(3)_ rj.key<rmin.key _) min=j; else if(rj.key>rmax.key) max=j; if(4)_ min!=

43、j_) rmin < - >rj;if(max!=n-i+1)if (5)_ max=j _) rmin < - > rn-i+1; else (6) rmax<->rm-i+1_); i+;/sort 2快速排序是在所有情況下，排序速度最快嗎？為什么？在何種情況下使用此排序法最好？解：不是，已經(jīng)有序情況下不適用，適用于基本無序的情況。3、以上所列的排序方法，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？對(duì)不穩(wěn)定的方法舉出反例。4、設(shè)計(jì)一算法，使得在盡可能少的時(shí)間內(nèi)重排數(shù)組，將所有取負(fù)值的關(guān)鍵字放在所有取負(fù)值關(guān)鍵字之前?？焖倥判虻囊惶伺判颍喊殃P(guān)鍵字改成跟零比較5、以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)直接選擇排序，寫出它的算法。6、判別以下序列是否為堆？若不是，則把它調(diào)整為堆 1）100，86，48，7