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

1、說明：1）個(gè)別答案有問題的話，直接與我聯(lián)系；2）沒有講過的內(nèi)容不要做！ 數(shù)據(jù)結(jié)構(gòu)練習(xí)題數(shù)據(jù)結(jié)構(gòu)練習(xí)題（15章）一、選擇題1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ c ）兩大類。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;i+) x=x+1;a o(2n) bo(n) co(n2) do(log2n) 4、下面關(guān)于線性表的敘述中，錯誤的是哪一個(gè)？（ b

2、 ）a線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。b線性表采用順序存儲，便于進(jìn)行插入和刪除操作。c線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。d線性表采用鏈接存儲，便于插入和刪除操作。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、下面的敘述不正確的是（ bc ）a線性表在鏈?zhǔn)酱鎯r(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比 b. 線性表在鏈?zhǔn)酱鎯r(shí)，查

3、找第i個(gè)元素的時(shí)間同i的值無關(guān)c. 線性表在順序存儲時(shí)，查找第i個(gè)元素的時(shí)間同i 的值成正比d. 線性表在順序存儲時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)8、 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ c ）(1=inext=s;s-next=p-next; b s-next=p-next;p-next=s;cp-next=s;p-next=s-next; d p-next=s-next;p-next=s;10、對于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ b ）ahead=null bheadnext=null cheadne

4、xt=head dhead!=null11、 一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第i（1=inext-next=l _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è)元素的存儲地址為100，若按行優(yōu)先順序存儲，則元素a66存儲地址為_352_。 四、算法與應(yīng)用題1. 設(shè)線性

5、表存放在向量aarrsize的前elenum個(gè)分量中且遞增有序，試寫一算法將x插入到線性表的適當(dāng)位置，以保持線性表的有序性并分析其時(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(aix & i=0)ai+1=ai; i- -;ai+1=x;return true;/寫的還是比較粗糙，有待進(jìn)一步改進(jìn)/2005年4月19日2.已知帶頭結(jié)點(diǎn)的動

6、態(tài)單鏈表l中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫一算法將值x為的結(jié)點(diǎn)插入到表l中，使l仍然有序。/線性表的單鏈表存儲結(jié)構(gòu) typedef 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(“動態(tài)空間分配不成功”)； exit(-1);s-data=x; q=l; p=l-next; while

7、( p!=null & p-data next; s-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 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-next;w

8、hile(p-next!=s) q=p; p=p-next;q-next =s;delete p;五、程序填空題1、 下面是用c語言編寫的對不帶頭結(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、對單鏈表中元素按插入方法排序的c語言描述算法如下，其中l(wèi)為鏈表頭結(jié)點(diǎn)指針。請?zhí)畛渌惴ㄖ袠?biāo)出的空白處，完成其功能。（10分）typedef struct no

9、de 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-datadata) r=q; q=q-next; u=p-next; (4)_ p-next=q _ ; (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ù)

10、為（ d ）a5 b6 c7 d82. 設(shè)森林f對應(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è)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ e ）a 250 b 500 c254 d505 e以上答案都不對 6. 有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（ d ）。a不確定 b2n

11、 c2n+1 d2n-17. 一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（ a ）alogn+1 blogn+1 clogn dlogn-18深度為h的滿m叉樹的第k層有（ a）個(gè)結(jié)點(diǎn)。(1=k=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在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為

12、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對應(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）23814395657834311717107552337415

13、342242919231113（2）（7（23）6557 4（171113）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)abcdeghf3二叉樹存儲結(jié)構(gòu)同上題，以下程序?yàn)榍蠖鏄渖疃鹊倪f歸算法，請?zhí)羁胀晟浦?int depth(bitree bt) /*bt為根結(jié)點(diǎn)的指針*/int hl,hr; if (bt=null) return(1)_ 0_); hl=depth(bt

14、-lchild); hr=depth(bt-rchild); if(2) hlhr _) (3)_ hr=hl_； return(hr+1); 4線索二叉樹有數(shù)據(jù)域data，左右孩子域lchild和rchild，左右標(biāo)志ltag及rtag，規(guī)定標(biāo)志為1對應(yīng)的孩子域是線索，0則為指向孩子的指針。規(guī)定在儲存線索二叉樹時(shí)，完成下面中序線索化過程。（存儲線索二叉樹，不增加頭結(jié)點(diǎn)，只在原有的由tree指向的二叉樹中增加線索，此處也不考慮c語言的具體語法與約定，線索化前所有的標(biāo)志tag都是0）。/* pre是同tree類型相同的指針，初值是null */thread_inorder (tree) if(t

15、ree!=null) thread_inorder(1) tree-lchild _); if(tree-lchild=(2) null_) tree-ltag=1; tree-lchild=pre; if(3) pre-rchild_ = null) (4) pre-rtag=1_; (5) pre-rchild=tree _;pre=tree; thread-inorder(6) tree-rchild _); 5、已知一棵滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)為20到40之間的素?cái)?shù)，此二叉樹的葉子結(jié)點(diǎn)有多少個(gè)？（請給出具體的推理過程）解： 166、一棵共有n個(gè)結(jié)點(diǎn)的樹，其中所有分支結(jié)點(diǎn)的度均為k，求該樹中葉

16、子結(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)的連通無向圖，其邊的個(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 ）倍，在

17、一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ c ）倍。a1/2 b2 c1 d45下列哪一種圖的鄰接矩陣是對稱矩陣？（ 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), (a,c), (b,e), (c,f), (f,d), (e,d)， 對該圖進(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下面哪一方法

18、可以判斷出一個(gè)有向圖是否有環(huán)（回路）：（ b ） a深度優(yōu)先遍歷 b. 拓?fù)渑判?c. 求最短路徑 d. 廣度優(yōu)先遍歷9. 在圖采用鄰接表存儲時(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（n+c） c. o（n*n） d. o（n*n*n）11已知有向圖g=(v,e)，其中v=v1,v2,v3,v4,v5,v6,v7，e=,g的拓?fù)湫蛄惺牵?a ）。av1,v3,v4,v6,v2,v5,v7 bv1,v3,v2,v6,v4,v5,

19、v7cv1,v3,v4,v5,v2,v6,v7 dv1,v2,v5,v3,v4,v6,v712若一個(gè)有向圖的鄰接距陣中,主對角線以下的元素均為零,則該圖的拓?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中有弧 bg中有一條從vi到vj的路徑 cg中沒有弧 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)鍵

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

21、網(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.該邊加入t2。上述算

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

23、頂點(diǎn)號從 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;in;i+) indegreei= (1)_ _0_) for(i=0,in;i+) for (j=0;jn; j+) indegreei+=array(2)_ i_(3)_ _j_; topsort (array,indegree,n) count= (4)_

24、0_) for (i=0;in;i+) if (5)_ indegreei=0_) push(i) while (check( ) vex=pop( ); printf(vex); count+; for (i=0;in;i+) k=array(6)_ vexi;_ if (7)_ k!=0_) indegreei-; if (8)_ indegreei=0_ ) push(i); if( countn) printf(“圖有回路”)； 2設(shè)g=(v,e)以鄰接表存儲，如圖所示，試畫出圖的深度優(yōu)先和廣度優(yōu)先生成樹。解：12345123453下圖表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上

25、的權(quán)表示架設(shè)線路花費(fèi)的代價(jià)，如何選擇能溝通每個(gè)城市且總代價(jià)最省的n-1條線路，畫出所有可能的選擇。1365421656111818136542165611解：4、對下面的有向圖，試?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. 堆排序，冒泡排序 b. 快速排序，堆排序 c. 直接選擇排序，歸并排序 d. 歸并排序，冒泡排序

26、3下面的排序算法中，不穩(wěn)定的是（ cdf ） a.起泡排序 b.折半插入排序 c.簡單選擇排序 d.希爾排序 e.基數(shù)排序 f.堆排序。4對一組數(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希爾排序 b. 堆排序 c. 選擇排序 d. 歸并排序 6. 下列排序算法中，占用輔助

27、空間最多的是：(a ) a. 歸并排序 b. 快速排序 c. 希爾排序 d. 堆排序7用直接插入排序方法對下面四個(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對下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是（a ）。a 21,25,5,17,9,2

28、3,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ù)一定要以順序方式存儲。 （ ）2排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（ ）3直接選擇排序算法在最好情況下的時(shí)間復(fù)雜度為o（n）。（ ）4在待排數(shù)據(jù)基本有序的情況下，快速排序

29、效果最好。（ ）5快速排序總比選擇排序快。（）填空1若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的_比較_和記錄的_移動_。2關(guān)鍵碼序列（ q，h，c，y，q，a，m，s，r，d，f，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 _。 作業(yè)題1下面的排序算法的思想是：第一趟比較將最小的元素放在r1中，最大的元素放在rn中，第二趟比較將次小的放在r2中，將次大的

30、放在rn-1中，,依次下去，直到待排序列為遞增序。（注：）代表兩個(gè)變量的數(shù)據(jù)交換）。void sort(sqlist &r,int n) i=1;while(1) i n/2_) min=max=i;for (j=i+1;(2)_ j=n-i+1_ ;+j) if(3)_ rj.keyrmax.key) max=j; if(4)_ min!=i_) rmin ri;if(max!=n-i+1)if (5)_ max=i _) rmin rn-i+1; else (6) rmaxrn-i+1_); i+;/sort 2快速排序是在所有情況下，排序速度最快嗎？為什么？在何種情況下使用此排序法最好？

31、解：不是，已經(jīng)有序情況下不適用，適用于基本無序的情況。3、以上所列的排序方法，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？對不穩(wěn)定的方法舉出反例。4、設(shè)計(jì)一算法，使得在盡可能少的時(shí)間內(nèi)重排數(shù)組，將所有取負(fù)值的關(guān)鍵字放在所有取負(fù)值關(guān)鍵字之前?？焖倥判虻囊惶伺判颍喊殃P(guān)鍵字改成跟零比較5、判別以下序列是否為堆？若不是，則把它調(diào)整為堆 1）100，86，48，73，35，39，42，57，66，21 2）12，70，33，65，24，56，48，92，86，33 3）103，97，56，38，66，23，42，12，30，52，06，20 4）05，56，20，23，40，38，29，61，35，76，28，100

32、第九章選擇題1、 對n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長度為(a ) a（n+1）/2 b. n/2 c. n d. （1+n）*n /22. 下面關(guān)于二分查找的敘述正確的是 ( d ) a. 表必須有序，表可以順序方式存儲，也可以鏈表方式存儲 c. 表必須有序，而且只能從小到大排列b. 表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型 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