1、用鄰接矩陣法儲存乙個圖所需的儲存單元數目與圖的邊數有關。( )
2、有e條邊的無向圖，在鄰接表中有e個結點。（ ）3、強連通圖的各頂點間均可達。
4、無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣。（ ）
5、乙個網（帶權圖）都有唯一的最小生成樹。( )
6、最小生成樹問題是構造連通網的最小代價生成樹。( )
7、關鍵路徑是aoe網中從源點到終點的最長路徑。（ ）
8、在aoe圖中，關鍵路徑上活動的時間延長多少，整個工程的時間也就隨之延長多少。
9、n個頂點的完全有向圖的邊數為n(n-1
10、稀疏圖的儲存結構採用鄰接表比較合適。（ ）
11、在圖g的最小生成樹t中，可能會有某條邊的權值超過未選邊的權值。
1．具有4個頂點的無向完全圖有（ ）條邊。
a．6 b．12 c．16 d．20
2．下列哪一種圖的鄰接矩陣是對稱矩陣？（ ）
a．有向圖b．無向圖c．aov網d．aoe網
3、在圖採用鄰接表儲存時，求最小生成樹的 prim 演算法的時間複雜度為( )。
a. o(n) b. o(n+e) c. o(n2) d. o(n3)
4、(1). 求從指定源點到其餘各頂點的迪傑斯特拉（dijkstra）最短路徑演算法中弧上權不能為負的原因是在實際應用中無意義；
(2). 利用dijkstra求每一對不同頂點之間的最短路徑的演算法時間是o(n3) ；（圖用鄰接矩陣表示）
(3). floyd求每對不同頂點對的演算法中允許弧上的權為負，但不能有權和為負的迴路。
上面不正確的是（ ）。
a．(1),(2),(3b．(1c．(1),(3d．(2),(3)
5、下列說法不正確的是（ ）。
a．圖的遍歷是從給定的源點出發每乙個頂點僅被訪問一次
b．遍歷的基本演算法有兩種：深度遍歷和廣度遍歷
c．圖的深度遍歷不適用於有向圖d．圖的深度遍歷是乙個遞迴過程
1、判斷乙個無向圖是一棵樹的條件是
2、圖的最短路徑演算法中演算法適於求解單源點到其餘各頂點的最短路徑演算法適於求解每對頂點間的最短路徑。
3、g是乙個非連通無向圖，共有28條邊，則該圖至少有______個頂點。
4、在有n個頂點的有向圖中，每個頂點的度最大可達______。
5、有n個頂點的有向圖，至少需要量______條弧才能保證是連通的。
6、在圖g的鄰接表表示中，每個頂點鄰接表中所含的結點數，對於無向圖來說等於該頂點的______；對於有向圖來說等於該頂點的______。
7、對於乙個具有n個頂點e條邊的無向圖的鄰接表的表示，則表頭向量大小為______，鄰接表的邊結點個數為______。
8、求圖的最小生成樹有兩種演算法，______演算法適合於求稀疏圖的最小生成樹。
1、按下圖所示，畫出它的廣度優先生成樹和深度優先生成樹
1、快速排序是一種穩定的排序方法。（ ）
2、在任何情況下，歸併排序都比簡單插入排序快。（ ）
3、當待排序的元素很大時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間複雜度的主要因素。（ ）
4、內排序要求資料一定要以順序方式儲存。（ ）
5、直接選擇排序演算法在最好情況下的時間複雜度為o（n
6、快速排序總比簡單排序快。( )
1．在已知待排序檔案已基本有序的前提下，效率最高的排序方法是
a．直接插入排序 b．直接選擇排序 c．快速排序d．歸併排序
2．下列排序方法中，哪乙個是穩定的排序方法？（ ）
a．直接選擇排序 b．折半插入排序 c．希爾排序 d．快速排序
3、比較次數與排序的初始狀態無關的排序方法是( )。
a．直接插入排序 b．起泡排序 c．快速排序 d．簡單選擇排序
4、對一組資料（84，47，25，15，21）排序，資料的排列次序在排序的過程中的變化為
（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. 選擇b. 冒泡c. 快速d. 插入
5、快速排序方法在（ ）情況下最不利於發揮其長處。
a. 要排序的資料量太大 b. 要排序的資料中含有多個相同值
c. 要排序的資料個數為奇數 d. 要排序的資料已基本有序
6、用某種排序方法對線性表進行排序，各趟排序結束時的結果為：
20，21，15，25，84，27，68，35，47
15，20，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84 ；則採用的排序方法為（ ）。
a．直接插入排序 b．希爾排序 c．快速排序 d．選擇排序
1、排序演算法的時間複雜度可用演算法執行中的次數及次數來衡量。
2、直接插入排序用監視哨的作用是
3、設用希爾排序對陣列進行排序，給出的步長（也稱增量序列）依次是4，2，1則排序需趟，寫出第一趟結束後，陣列中資料的排列次序
4、分別採用堆排序，快速排序，氣泡排序和歸併排序，對初態為有序的表，則最省時間的是演算法，最費時間的是演算法。
資料結構1800第八章
青島大學 2000 十 10分 中國人民大學 2000 一 1 4分 7 組織成迴圈鍊錶的可利用空間表附加什麼條件時，首次適配策略就轉變為最佳適配策略？北方交通大學 1998 四 8分 8 已知乙個大小為512個字長的儲存，假設先後有6個使用者申請大小分別為23，45，52，100，11和19的儲存...
資料結構第八章排序
第八章排序 1.當檔案區域性有序或檔案長度較小的情況下，最佳的排序方法是 a 直接插入排序 b 直接選擇排序 c 氣泡排序 d 歸併排序 2.當初始序列已按鍵值有序時，用直接插入演算法進行排序，需要比較的次數為 a n 1 b log2n 注 2是下標 c 2log2n 注 後乙個2是下標 d n2...
第八章,華工資料結構試卷,電信學院
8.1選擇題 1 順序查詢法適合於儲存結構為 b 的線性表。a 雜湊儲存b 順序儲存或鏈結儲存 c 壓縮儲存d 索引儲存 2 對線性表進行折半查詢時，要求線性表必須 c a 以順序方式儲存b 以鏈結方式儲存 c 以順序方式儲存，且結點按關鍵字有序排序 d 以鏈結方式儲存，且結點按關鍵字有序排序 3 ...