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

1、華東理工大學(xué)網(wǎng)絡(luò)學(xué)院（?？疲?shù)據(jù)結(jié)構(gòu)-ch7圖、ch9排序班級(jí) 學(xué)號(hào) 姓名 成績(jī)一、填空題（每空1分，共10分） 具有n個(gè)頂點(diǎn)的有向圖最多有_ n（n-1）條邊。 在無(wú)向圖G的鄰接矩陣中，求第i個(gè)結(jié)點(diǎn)的度的方法是求鄰接矩陣第i行非零元素之和。堆排序通常采用順序存儲(chǔ)結(jié)構(gòu)。與快速排序和堆排序相比，歸并排序的最大特點(diǎn)是，它是一種穩(wěn)定的排序方法。 具有8個(gè)頂點(diǎn)的有向完全圖有條弧。在無(wú)向圖G的鄰接矩陣A中，若Aij等于1，則Aji等于 。在一個(gè)待排序的序列中，只有很少量元素不在自己最終的正確位置上，但離他們的正確位置都不遠(yuǎn)，則使用直接插入排序方法最好。已知有向圖的鄰接矩陣，要計(jì)算i號(hào)頂點(diǎn)的入度，計(jì)算方法

2、是：將 i列元素累加。n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有n 條邊，至多有n（n-1） 條邊。二、判斷正誤（對(duì)的用”T”表示，錯(cuò)誤的用”F”表示。每小題1分，共10分）（ T）若一個(gè)有向圖的鄰接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖凇＃?F ）快速排序的速度在所有的排序方法中為最快，而且所需附加空間也最少。（ F）采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似二叉樹(shù)的按層次遍歷算法。（ T）在待排序的元素序列基本有序的前提下，效率最高的是插入排序。（ T）圖的廣度優(yōu)先遍歷類似于樹(shù)的層次遍歷。（ T）拓?fù)渑判驎r(shí)，總是在有向圖中選擇入度為0的頂點(diǎn)輸出。（ F）若要求一個(gè)稠密圖G的最小生成樹(shù)，最好用

3、Kruscal算法來(lái)求解。（ T）拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù)，則該圖一定存在回路。（ T）設(shè)有一稠密圖G，則G采用鄰接矩陣存儲(chǔ)較省空間。（ F）n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為O（n+e）。三、單項(xiàng)選擇題（每小題2分，共20分）已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是_。A 0 3 2 1 B 0 1 2 3 C 0 1 3 2 D 0 3 1 2已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是_DA 0 3 2 1 B 0 1 2 3 C 0 1 3 2 D 0 3 1 2排序時(shí)掃描待排

4、序記錄序列，順次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交換位置。這是哪種排序方法的基本思想？DA堆排序B直接插入排序C快速排序D冒泡排序 已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)該：B 。A將鄰接矩陣的第i行刪除B將鄰接矩陣的第i行元素全部置為0C將鄰接矩陣的第i列刪除D將鄰接矩陣的第i列元素全部置為0 快速排序在_情況下最容易發(fā)揮其長(zhǎng)處。A被排序的數(shù)據(jù)中含有多個(gè)相同的排序關(guān)鍵字B被排序的數(shù)據(jù)已基本有序C被排序的數(shù)據(jù)完全無(wú)序D被排序的數(shù)據(jù)中的最大值和最小值相差懸殊堆的形狀是一棵C 。A二叉排序樹(shù) B滿二叉樹(shù)C完全二叉樹(shù) D平衡二叉樹(shù)圖的深度優(yōu)先遍歷類似于樹(shù)的A 遍歷。A先序

5、 B中序 C后序 D層次有n個(gè)頂點(diǎn)的無(wú)向連通圖至少有 A 條邊。A n-1 B nC n+1 D 2n用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采_ 來(lái)實(shí)現(xiàn)算法的。A棧B隊(duì)列C樹(shù)D圖。下列幾種排序方法中，要求輔助空間最大的是 C 。A插入排序 B快速排序 C歸并排序 D選擇排序四、簡(jiǎn)答題（每小題5分，共15分）設(shè)有1000個(gè)無(wú)序元素，僅要求找出前10個(gè)最小元素，在下列排序方法中（歸并排序、基 數(shù)排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？說(shuō)明在圖的遍歷中，設(shè)置訪問(wèn)標(biāo)志數(shù)組的作用。圖中結(jié)點(diǎn)可能有多個(gè)前驅(qū)，設(shè)置訪問(wèn)標(biāo)志數(shù)組主要是為了避免重復(fù)訪問(wèn)同一個(gè)結(jié)點(diǎn)用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)

6、數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？用鄰接矩陣表示圖，矩陣元素的個(gè)數(shù)是頂點(diǎn)個(gè)數(shù)的平方，與邊的條數(shù)無(wú)關(guān)。矩陣中非零元 素的個(gè)數(shù)與邊的條數(shù)有關(guān)。五、綜合題(每小題10分，共30分。)畫(huà)出1個(gè)頂點(diǎn)、2個(gè)頂點(diǎn)、3個(gè)頂點(diǎn)、4個(gè)頂點(diǎn)和5個(gè)頂點(diǎn)的無(wú)向完全圖。試證明在n個(gè)頂點(diǎn) 的無(wú)向完全圖中，邊的條數(shù)為n(n-1)/2。在有n個(gè)頂點(diǎn)的無(wú)向完全圖中，每一個(gè)頂點(diǎn)都有一條邊與其它某一頂點(diǎn)相連，所以每一個(gè) 頂點(diǎn)有n-1條邊與其他n-1個(gè)頂點(diǎn)相連，總計(jì)n個(gè)頂點(diǎn)有n(n-1)條邊。但在無(wú)向圖中，頂點(diǎn)i 到頂點(diǎn)j與頂點(diǎn)j到頂點(diǎn)i是同一條邊，所以總共有n(n-1)/2條邊。試給出以1為起點(diǎn)的深度優(yōu)先搜索和廣度優(yōu)先搜索的遍歷序列，并給出一棵最小生成樹(shù)。深度優(yōu)先搜索序列：1 2 3 6 4 5；廣度優(yōu)先搜索：1 2 4 5 3 6最小生成樹(shù)：18給出右圖的鄰接矩陣、鄰接表表示。Edge010100001010000001010010000000000010(1)鄰接表012345六、算法設(shè)計(jì)題(15分)設(shè)計(jì)一算法，使得在盡可能少的時(shí)間內(nèi)重排數(shù)組an，將所有取負(fù)值的關(guān)鍵字放在所有取 非負(fù)值的關(guān)鍵字之前。并請(qǐng)分析算法的時(shí)間復(fù)雜度。void part(i