數(shù)據(jù)結(jié)構(gòu)練習(xí)1

1、數(shù)據(jù)結(jié)構(gòu)作業(yè)一、設(shè) n 為整數(shù)，利用大“O”記號，求下列程序段的時(shí)間復(fù)雜度1、 i=0;k=0;Do k=k*10*i;i+; while (i<n);/ T(n)=O(n)2、 i=1;j=0;while(i+j<=n)if(i>j)j+;elsei+;/ T(n)=O(n)3、 x=n;/n>1while (x>=(y+1)*(y+1)y+;/ T(n)=O(n )4、 x=91;y=100;while (y>0)if (x>100)x=x-10; y- -;elsex+;/ T(n)= 常數(shù) =O(1)二、選擇題1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C

2、）兩大類。A動態(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、在下面的程序段中，對x 的賦值語句的頻度為（C）for (i=1;i<=n;i+)for (j=1;j<=n;j+)x=x+1;2DnA O(2n)B O(n)CO(n ) O(log 2 )4、下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（B）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。1D線性表采用鏈接存儲

3、，便于插入和刪除操作。5 、某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ D ）存儲方式最節(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、下面的敘述不正確的是（B 、 C）A線性表在鏈?zhǔn)酱鎯r(shí)，查找第i 個(gè)元素的時(shí)間同i 的值成正比B. 線性表在鏈?zhǔn)酱鎯r(shí)，查找第i 個(gè)元素的時(shí)間同 i 的值無關(guān)C. 線性表在順序存儲時(shí)，查找第i 個(gè)元素的時(shí)間同 i 的值成正比D. 線性表在順序存儲時(shí)，查找第i 個(gè)元素的時(shí)間同 i 的值無關(guān)8、 若長度為

4、n 的線性表采用順序存儲結(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）。A p->next=s;s->next=p->next;B s->next=p->next;p->next=s;C p->next=s;p->next=s->next;D p->next=s->next;p->next=s;10、對于一個(gè)頭指針為head 的帶頭結(jié)點(diǎn)

5、的單鏈表，判定該表為空表的條件是（B）A head=NULL B head next=NULLC head next=headD head!=NULL11、 一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第i （ 1<=i<=n ）個(gè)元素是（ B）。A.不確定B. n-i+1C. iD. n-i12、 有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧， 問下列哪一個(gè)不是合法的出棧序列？（ C）A.543612B.453126C.346521D.23415613、設(shè)有三個(gè)元素X，Y，Z 順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到的出棧排列是( C)。A XYZB. YZXC

6、. ZXYD. ZYX14、 假設(shè)以數(shù)組 Am 存放循環(huán)隊(duì)列的元素 , 其頭尾指針分別為 front 和 rear ，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ A ）。A (rear-front+m)%mB rear-front+1C (front-rear+m)%mD (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的值分別為多少？( B )A.1 和5B.2和4C.4和2D.5和116、下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（B）A串是字符的有限序列B空串是

7、由空格構(gòu)成的串C模式匹配是串的一種重要運(yùn)算D 串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?7、設(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，2數(shù)組從內(nèi)存首地址 BA開始順序存放， 當(dāng)用以列為主存放時(shí)， 元素 A5 ，8 的存儲首地址為 ( B ) 。A. BA+141B. BA+180C. BA+222D. BA+22519、廣義表 A=(a,b,(c,d),(e,(f,g),則下面表達(dá)式的值為（D ）。Head

8、(Tail(Head(Tail(Tail(A)A. (g)B. (d)C. cD. d三、判斷題1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(錯(cuò) )2、順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。(錯(cuò) )3、線性表采用鏈表存儲時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。( 對 )4、線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。(錯(cuò) )5、一個(gè)稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把 m和 n 的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。（錯(cuò)）6、所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。（錯(cuò) ）四、填空題1、當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和

9、刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用順序存儲結(jié)構(gòu)。2、線性表 L=（ a1,a2,an ）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動元素的個(gè)數(shù)是(n-1)/2。3、對于一個(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)。4、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L 中只有一個(gè)元素結(jié)點(diǎn)的條件是：L->next=L->prior( 或 L->prior->prior=L)5、一個(gè)棧的輸入序列是：1， 2， 3 則不可能的棧輸出序列是3,1,2。

10、6、用 S 表示入棧操作， X 表示出棧操作，若元素入棧的順序?yàn)?234 ，為了得到 1342 出棧順序，相應(yīng)的 S 和 X 的操作串為SXSSXSXX。7、隊(duì)列又稱作先進(jìn)先出表。8、組成串的數(shù)據(jù)元素只能是字符。9、設(shè)有 C 語言描述的二維數(shù)組A1020,其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲地址為100，若按行優(yōu)先順序存儲，則元素A66存儲地址為352。五、算法設(shè)計(jì)題1、請?jiān)O(shè)計(jì)一算法：已知順序表L ，表中元素為整型且遞增有序，現(xiàn)有一值為e 的元素要插入 L表，使插入后L 表仍然有序。2. 已知帶頭結(jié)點(diǎn)的動態(tài)單鏈表L 中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫一算法將值x 為的結(jié)點(diǎn)插入到表 L 中，使

11、 L 仍然有序。3. 設(shè)計(jì)一算法，逆置帶頭結(jié)點(diǎn)的動態(tài)單鏈表L。4. 在長度大于1 的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。s 為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)*s 的直接前趨結(jié)點(diǎn)。1、方法一 :#define LIST_INIT_SIZE 1003#define LISTINCREMENT 10Status sqlist_insert(sqlist &L, int e) int *p, *newbase;if (L.length=L.listsize)/空間不夠 , 需重新申請 newbase=(int *)realloc(L.elem, (L.listsize+Listi

12、ncrement) *sizeof(int) );if (!newbase)exit(overflow);L.elem=newbase;L.listsize+=listincrement; /新基址和存儲容量for (p=L.elem+L.length;p>=L.elem && *p>e;-p ) /從表尾開始比較和移動*(p+1)=*p;*(p+1)=e;+L.length;Return ok方法二 :Status sqlist_insert(sqlist &L, int e) int i, *newbase;if (L.length=L.listsize

13、)/空間不夠 , 需重新申請 newbase=(int *)realloc(L.elem, (L.listsize+Listincrement) *sizeof(int) );if (!newbase)exit(overflow);L.elem=newbase;L.listsize+=listincrement; /新基址和存儲容量for (i=L.length-1;i>=0 && L.elemi>e;-i ) /從表尾開始比較和移動L.elemi+1=L.elemi;L.elemi+1=e;+L.length;Return ok2、方法一：Void Linklis

14、t_insert(linklist &L, int e) linklist p,pre;pre=L; p=L->next;/pre是 p 的直接前驅(qū)while(p&&p->data<x)p=p->next;s=(linklist)malloc(sizeof(LNode)s->data=e;s->next=p;/s插在 pre 的后面， p 的前面4pre->next=s;方法二：Void Linklist_insert(linklist &L, int e) linklist p=L;while(p->next&a

15、mp;&p->next->data<x)/p的后繼與 x進(jìn)行比較p=p->next;s=(linklist)malloc(sizeof(LNode)s->data=e;s->next=p->next;/s插在 p 的后面p->next=s;3、Void linklist_reverse(linklist &L) linklist p,q;P=L->next;L->next=NULL;While(p) q=p->next;p->next=L->next;/p插在頭結(jié)點(diǎn)L 的后面L->next=p;

16、p=q;4、Void linklist_delete(linklist s) linklist p;p=s;while(p->next->next!=s)p=p->next;free(p->next)；刪除 p 的后繼p->next=s;p的后繼為s六、程序填空題不帶頭結(jié)點(diǎn)的單鏈表L 進(jìn)行就地逆置的算法，用L 返回逆置后的鏈表的頭指針。void reverse（ linklist &L） p=null； q=L；while （q！ =null ） (1);q->next=p； p=q； (2)_ ; (3)_;5/（ 1） L=L->next

17、(2)q=s(3) L=P第六章樹選擇題1已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E ，后綴形式為ABC*+DE/-，其前綴形式為 ( D )A -A+B*C/DEB. -A+B*CD/EC -+*ABC/DED. -+A*BC/DE2算術(shù)表達(dá)式 a+b* （ c+d/e ）轉(zhuǎn)為后綴表達(dá)式后為（B）A ab+cde/*Babcde/+*+C abcde/*+D abcde*/+3.設(shè)樹 T 的度為4，其中度為1，2，3 和 4 的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 則 T 中的葉子數(shù)為（ D）A 5B 6C7D 84.設(shè)森林 F 對應(yīng)的二叉樹為B，它有 m個(gè)結(jié)點(diǎn)， B 的根為 p,p的右子樹結(jié)點(diǎn)

18、個(gè)數(shù)為 n, 森林 F 中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（A）A m-n B m-n-1C n+1 D條件不足，無法確定5若一棵二叉樹具有10 個(gè)度為 2 的結(jié)點(diǎn)， 5 個(gè)度為1 的結(jié)點(diǎn)，則度為0 的結(jié)點(diǎn)個(gè)數(shù)是（ B ）A 9B 11C15D不確定6具有 10 個(gè)葉結(jié)點(diǎn)的二叉樹中有（B）個(gè)度為2 的結(jié)點(diǎn)，A 8B9C 10Dll7一棵完全二叉樹上有1001 個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（E）A 250B 500C254 D505E以上答案都不對8.有 n 個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（D）。A不確定B 2nC 2n+1D 2n-19.一棵具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（A）A logn

19、+1B logn+1C lognD logn-110深度為 h 的滿 m叉樹的第 k 層有（ A ）個(gè)結(jié)點(diǎn)。 (1=<k=<h)k-1BkCh-1DhA m m-1 m m-111在一棵高度為k 的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（C）A 2k-1B 2kC 2k-1D log2 k+112對二叉樹的結(jié)點(diǎn)從1 開始進(jìn)行連續(xù)編號，要求每個(gè)結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的左右孩子中， 其左孩子的編號小于其右孩子的編號， 可采用 ( C ) 次序的遍歷實(shí)現(xiàn)編號。A先序B.中序C.后序D.從根開始按層次遍歷13樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的( B).A.先序序列B.中序序列C.

20、后序序列14已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac ,它的前序遍歷是 （ D）。A acbedB decabC deabcD cedba15二叉樹的先序遍歷和中序遍歷如下：先序遍歷： EFHIGJK；中序遍歷 : HFIEJKG。該二叉樹根的右子樹的根是：( C )6A、 EB、 FC 、 GD 、 H16 n 個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（C）A 2nB n lC n lD n17下述編碼中哪一個(gè)不是前綴碼（B）。A（ 00，01，10，11） B （ 0，1，00，11） C （ 0，10，110，111） D （ 1，01，000，001）18從下列有關(guān)樹

21、的敘述中, 選出 5 條正確的敘述（C,D,F,H,I）A二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn), 而樹無此限制 , 因此二叉樹是樹的特殊情況。B當(dāng) K 1 時(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采用二叉樹鏈表作樹的存儲結(jié)構(gòu), 樹的前序周游和其相應(yīng)的二叉樹的前序周游的結(jié)果是一樣的。I哈夫曼樹是帶權(quán)路徑最短的樹, 路徑上權(quán)值較大的結(jié)點(diǎn)離

22、根較近。J用一維數(shù)組存儲二叉樹時(shí), 總是以前序周游存儲結(jié)點(diǎn)。判斷題1完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。( 對 )2.二叉樹只能用二叉鏈表表示。（錯(cuò)）3在二叉樹的第i 層上至少有 2i-1個(gè)結(jié)點(diǎn) (i>=1)（錯(cuò)）4度為二的樹就是二叉樹。（錯(cuò)）5.在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點(diǎn)。錯(cuò)）填空題：1具有 256 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為9。2已知一棵度為3 的樹有 2 個(gè)度為 1 的結(jié)點(diǎn)， 3 個(gè)度為 2 的結(jié)點(diǎn)， 4 個(gè)度為 3 的結(jié)點(diǎn)，則該樹有12個(gè)葉子結(jié)點(diǎn)。3在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為N0, 度為 2 的結(jié)點(diǎn)的個(gè)數(shù)為N2,則有 N0=N 2+

23、14已知二叉樹有50 個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是99。5一個(gè)有 2001 個(gè)結(jié)點(diǎn)的完全二叉樹的高度為11。6設(shè) F 是由 T1,T2,T3 三棵樹組成的森林, 與 F 對應(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)。7如某二叉樹有20 個(gè)葉子結(jié)點(diǎn)， 有 30 個(gè)結(jié)點(diǎn)僅有一個(gè)孩子， 則該二叉樹的總結(jié)點(diǎn)數(shù)為69 。算法應(yīng)用題1、已知一棵度為m 的樹中有 n1 個(gè)度為 1 的結(jié)點(diǎn)， n2 個(gè)度為2 的結(jié)點(diǎn)， nm 個(gè)度為 m 的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？2、已知一棵滿二叉樹的結(jié)點(diǎn)

24、個(gè)數(shù)為20到40之間的素?cái)?shù)，此二叉樹的葉子結(jié)點(diǎn)有多少個(gè)？（請給出具體的推理過程）3、請采用順序存儲方式和鏈?zhǔn)酱鎯Ψ绞?，分別寫出下圖所示二叉樹的存儲結(jié)構(gòu)。A7BCDEFGH4、求出上圖所示二叉樹的前序、中序和后序序列。5、以二叉鏈表做存儲結(jié)構(gòu)，試編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。6、設(shè)一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列：ABDFCEGH中序遍歷序列：BFDAGEHC（ 1）畫出這棵二叉樹。（ 2）畫出這棵二叉樹的后序線索樹。7 、假設(shè)一個(gè)二叉樹的兩種遍歷如下：前序： ABFGCHDEIJLK中序： FGBHCDILJKEA畫出這棵二叉樹以及它的中序線索樹；8、給定一

25、組權(quán)值3， 27， 7，8， 14，23， 6， 12（ 1）試畫出用 Huffman 算法建造的 Huffman 樹；（ 2）求 Huffman 編碼和平均編碼長度（考慮概率）9、已知一棵二叉樹的中序和后序序列如下：中序： GLDHBEIACJFK后序：LGHDIEBJKFCA(1) 給出這棵二叉樹：(2) 轉(zhuǎn)換為對應(yīng)的森林：10、將下列森林轉(zhuǎn)化為二叉樹。11、求上述森林的前序和中序序列。第七章圖選擇題1設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（B）條邊。A n-1B n(n-1)/2C n(n+1)/2D 0En22一個(gè) n 個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為（A ）。A n-1B nC n

26、+1D nlogn ；3一個(gè)有 n 個(gè)結(jié)點(diǎn)的圖，最少有（B）個(gè)連通分量，最多有（D）個(gè)連通分量。A 0B 1C n-1D n4在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（B）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（C ）倍。A 1/2B 2C 1D 45下列哪一種圖的鄰接矩陣是對稱矩陣？（B）A有向圖B無向圖CAOV網(wǎng)D AOE網(wǎng)6當(dāng)一個(gè)有 N 個(gè)頂點(diǎn)的圖用鄰接矩陣A 表示時(shí)，頂點(diǎn)Vi 的度是（ B）。nnnnnA i, j A i , jAj , iA i, j A j,iA i 1B j 1C i 1D i 1+j 187下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（

27、回路）： ( B )A深度優(yōu)先遍歷B.拓?fù)渑判駽.求最短路徑D.廣度優(yōu)先遍歷8.在圖采用鄰接表存儲時(shí)，求最小生成樹的Prim算法的時(shí)間復(fù)雜度為( B )。A. O(n)B. O(n+e)C. O(n2)D. O(n3)9. 求解最短路徑的 Floyd 算法的時(shí)間復(fù)雜度為 ( D ) 。A O（n）B. O（ n+c）C. O（ n*n ）D. O（ n*n*n ）10若一個(gè)有向圖的鄰接距陣中, 主對角線以下的元素均為零, 則該圖的拓?fù)溆行蛐蛄校ˋ ）。A存在B不存在11一個(gè)有向無環(huán)圖的拓?fù)渑判蛐蛄校˙）是唯一的。A一定B不一定12. 在有向圖 G的拓?fù)湫蛄兄校?若頂點(diǎn) Vi 在頂點(diǎn) Vj 之前

28、，則下列情形不可能出現(xiàn)的是 （ D ）。A G中有弧 <Vi ， Vj>B G中有一條從 Vi到 Vj 的路徑C G中沒有弧 <Vi,Vj>D G中有一條從 Vj到 Vi 的路徑13.在用鄰接表表示圖時(shí)，拓?fù)渑判蛩惴〞r(shí)間復(fù)雜度為( B )。A. O(n)B. O(n e)C. O(n*n)D. O(n*n*n)14.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（A）。A從源點(diǎn)到匯點(diǎn)的最長路徑B從源點(diǎn)到匯點(diǎn)的最短路徑C最長回路D最短回路15下列關(guān)于 AOE網(wǎng)的敘述中，不正確的是（B）。A關(guān)鍵活動不按期完成就會影響整個(gè)工程的完成時(shí)間B任何一個(gè)關(guān)鍵活動提前完成，那么整個(gè)工程將會提前完成C所有的關(guān)

29、鍵活動提前完成，那么整個(gè)工程將會提前完成D某些關(guān)鍵活動提前完成，那么整個(gè)工程將會提前完成判斷題1.有 e 條邊的無向圖，在鄰接表中有e 個(gè)結(jié)點(diǎn)。（錯(cuò)）2.有向圖的鄰接矩陣是對稱的。（錯(cuò)）3任何無向圖都存在生成樹。 （錯(cuò)）4.不同的求最小生成樹的方法最后得到的生成樹是相同的. （錯(cuò) ）5. 有環(huán)圖也能進(jìn)行拓?fù)渑判颉?（ 錯(cuò)）6. 關(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條弧。3 n 個(gè)頂點(diǎn)的連通無向圖，其邊的條數(shù)至少為n-1。4N 個(gè)頂點(diǎn)的連通圖用鄰

30、接矩陣表示時(shí) , 該矩陣至少有 無向圖： 2(n-1) ；有向圖： n 個(gè)非零元素。5構(gòu)造連通網(wǎng)最小生成樹的兩個(gè)典型算法是普里姆算法、克魯斯卡爾算法。6. 有一個(gè)用于 n 個(gè)頂點(diǎn)連通帶權(quán)無向圖的算法描述如下：（ 1）設(shè)集合 T1 與 T2，初始均為空；9（ 2）在連通圖上任選一點(diǎn)加入T1；（ 3）以下步驟重復(fù) n-1 次：a. 在 i 屬于 T1， j 不屬于 T1 的邊中選最小權(quán)的邊；b. 該邊加入 T2。上述算法完成后， T2 中共有n-1條邊，該算法稱普里姆算法算法，T2 中的邊構(gòu)成圖的最小生成樹。7AOV網(wǎng)中 , 頂點(diǎn)表示活動,弧表示活動間的優(yōu)先關(guān)系。AOE網(wǎng)中 , 頂點(diǎn)表示事件,弧表

31、示活動。8. 當(dāng)一個(gè) AOV網(wǎng)用鄰接表表示時(shí)，可按下列方法進(jìn)行拓?fù)渑判?。?1）查鄰接表中入度為零的頂點(diǎn)，并進(jìn)棧；（ 2）若棧不空，則輸出棧頂元素Vj ，并退棧；查Vj 的直接后繼Vk，對 Vk 入度處理，處理方法是Vk 的入度減1，如為零則進(jìn)棧；（ 3）若?？諘r(shí)，輸出頂點(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)，說明有環(huán)路，否則拓?fù)渑判蛲瓿?。算法?yīng)用題1、對 n 個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣表示，如何判別下列有關(guān)問題1）圖中有多少條邊？2）任意兩個(gè)頂點(diǎn)i 和 j 是否有邊相連？3）任意一個(gè)頂點(diǎn)的度是多少？2設(shè) G=(V,E) 以鄰接表存儲，試寫出深度優(yōu)先和廣度優(yōu)先序列。3、已知一無向圖的鄰接矩陣如下，求該圖從頂點(diǎn)V

32、 1 出發(fā)的廣度優(yōu)先遍歷和深度優(yōu)先遍歷序列。00100100001001100101001101110001000101100101010104下圖表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費(fèi)的代價(jià)，如何選擇能溝通每個(gè)城市且總代價(jià)最省的n-1 條線路，畫出所有可能的選擇。5、對下面的有向圖，試?yán)肈IJKSTRA 算法從頂點(diǎn)1 到其它頂點(diǎn)的最短路徑，并寫出執(zhí)行該16算法過程中每次循環(huán)的狀態(tài)。1221519114631463365181010v2v52015v43042v110415v610v36、對下面的 AOE 網(wǎng)，求出各項(xiàng)活動的最早開始時(shí)間e(i)和最遲開始時(shí)間l

33、(i) ，并回答：工程完成的最短時(shí)間是多少？哪些是關(guān)鍵活動？V44V63V2545V72v10653V9v112634V3V5V87下圖是帶權(quán)的有向圖G的鄰接表表示法，求：（ 1）以結(jié)點(diǎn) V1 出發(fā)深度遍歷圖 G所得的結(jié)點(diǎn)序列；（ 2）以結(jié)點(diǎn) V1 出發(fā)廣度遍歷圖 G所得的結(jié)點(diǎn)序列；（ 3）從結(jié)點(diǎn) V1 到結(jié)點(diǎn) V8 的最短路徑；（ 4）從結(jié)點(diǎn) V1 到結(jié)點(diǎn) V8 的關(guān)鍵路徑。第九章查找選擇題1、 對 n 個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長度為( A )A（ n+1） /2B. n/2C. nD. （1+n） *n /22. 下面關(guān)于二分查找的敘述正確的是( D )

34、A. 表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B. 表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型C. 表必須有序，而且只能從小到大排列D. 表必須有序，且表只能以順序方式存儲3. 二叉查找樹的查找效率與二叉樹的( （ 1） C)有關(guān) , 在 ( （ 2)C ）時(shí)其查找效率最低(1): A.高度B.結(jié)點(diǎn)的多少C.樹型D.結(jié)點(diǎn)的位置(2): A.結(jié)點(diǎn)太多B.完全二叉樹C.呈單枝樹D.結(jié)點(diǎn)太復(fù)雜。4. 若采用鏈地址法構(gòu)造散列表，散列函數(shù)為H（ key ） =key MOD 17，則需 ( （ 1） A) 個(gè)鏈表。這些鏈的鏈?zhǔn)字羔槝?gòu)成一個(gè)指針數(shù)組，數(shù)組的下標(biāo)范圍為( （2）C)（1） A17

35、B. 13C. 16D.任意（2） A0至 17B. 1至 17C. 0至 16D.1至16判斷題1 Hash 表的平均查找長度與處理沖突的方法無關(guān)。( 錯(cuò))112. 若散列表的負(fù)載因子 <1，則可避免碰撞的產(chǎn)生。 （錯(cuò)）3. 就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大。（錯(cuò)）填空題1.在順序表（ 8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù)為4 .算法應(yīng)用題1.設(shè)有一組關(guān)鍵字9,01,23,14,55,20,84,27，采用哈希函數(shù)：H（ key） =key mod 7，表長為 10，用開放

36、地址法的二次探測再散列方法Hi=(H(key)+di) mod 10解決沖突。要求：對該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長度。2. 已知散列表的地址空間為 A0.11 ，散列函數(shù) H（ k） =k mod 11 ，采用線性探測法處理沖突。請將下列數(shù)據(jù)25,16,38,47,79,82,51,39,89,151,231依次插入到散列表中，并計(jì)算出在等概率情況下查找成功時(shí)的平均查找長度。、對長度為20 的有序表進(jìn)行二分查找，試畫出它的一棵判定樹，并求等概率情況下的平均查找長度。、設(shè)散列表的長度為15，散列函數(shù)H （ K ） =K%13 ，給定的關(guān)鍵字序列為20， 16， 29， 82，37， 02， 06， 28， 55， 39， 23， 10，試寫出分別用拉鏈法和線性探測法解決沖突時(shí)所構(gòu)造的散列表