理工大學指揮自動化學院試卷
考試科目： 第4 章圖結構隊別專業
學號姓名考試日期年月日
1.單項選擇題（每題2分，共36分）
【1】在乙個無向圖中，所有頂點的度數之和等於所有邊數的倍。
a．1／2b．1c．2d．4
【2】在乙個有向圖中，所有頂點的入度之和等於所有頂點的出度之和的倍。
a．1／2b．1c．2d．4
【3】乙個有n個頂點的無向圖最多有條邊。
a．nb．n(n-1c．n(n-1)/2 d．2n
【4】具有4個頂點的無向完全圖有條邊。
a．6b．12c．16d．20
【5】具有6個頂點的無向圖至少應有條邊才能確保是乙個連通圖。
a．5b．6c．7d．8
【6】在乙個具有n個頂點的無向圖中，要連通全部頂點至少需要條邊。
a．nb．n+1c．n-1d．n/2
【7】對於乙個具有n個頂點的無向圖，若採用鄰接矩陣表示，則該矩陣的大小是 。
a．nb．(n-1)2c．n-1d．n2
【8】對於乙個具有n個頂點和e條邊的無向圖，若採用鄰接表表示，則表頭向量的大小為 ① ：所有鄰接表中的結點總數是 ② 。
①a．nb．n+1c．n-1d．n+e
②a．e/2b．ec．2ed．n+e
【9】對某個無向圖的鄰接矩陣來說
a．第i行上的非零元素個數和第i列的非零元素個數一定相等
b．矩陣中的非零元素個數等於圖中的邊數
c．第i行上，第i列上非零元素總數等於頂點vi的度數
d．矩陣中非全零行的行數等於圖中的頂點數
【10】已知乙個圖如圖所示，若從頂點a出發按深度搜尋法進行遍歷，則可能得到的一種頂點序列為 ① ；按廣度搜尋法進行遍歷，則可能得到的一種頂點序列為 ② 。
①a．a，b，e，c，d，fb．a，c，f，e，b，d
c．a，e，b，c，f，dd．a，e，d，f，c，b
②a．a，b，c，e，d，fb．a，b，c，e，f，d
c．a，e，b，c，f，dd．a，c，f，d，e，b
【11】已知一有向圖的鄰接表儲存結構如圖所示。
（1）根據有向圖的深度優先遍歷演算法，從頂點v1出發，所得到的頂點序列是 ① 。
a．v1，v2，v3，v5，v4b．v1，v2，v3，v4，v5
c．v1，v3，v4，v5，v2d．v1，v4，v3，v5，v2
（2）根據有向圖的廣度優先遍歷演算法，從頂點v1出發，所得到的頂點序列是 ② 。
a．v1，v2，v3，v4，v5b．v1，v3，v2，v4，v5
c．v1，v2，v3，v5，v4d．v1，v4，v3，v5，v2
【12】採用鄰接表儲存的圖的深度優先遍歷演算法類似於二叉樹的 。
a．先序遍歷 b．中序遍歷 c．後序遍歷 d．按層遍歷
【13】採用鄰接表儲存的圖的廣度優先遍歷演算法類似於二叉樹的 。
a．先序遍歷 b．中序遍歷 c．後序遍歷 d．按層遍歷
【14】乙個圖中包含k個連通分量，若按深度優先搜尋方法訪問所有結點，則必須呼叫次深度優先遍歷演算法。
a．kb．1c．k-1d．k+1
【15】任何乙個無向連通圖的最小生成樹 。
a．有一棵或多棵 b．只有一棵 c．一定有多棵 d．可能不存在
【16】以下說法中不正確的是 。
a．無向圖中的極大連通子圖稱為連通分量
b．連通圖的廣度優先搜尋中一般要採用佇列來暫存剛訪問過的頂點
c．圖的深度優先搜尋中一般要採用棧來暫存剛訪問過的頂點
d．有向圖的遍歷不可採用廣度優先搜尋方法
【17】判定乙個有向圖是否存在迴路，除了可以利用拓撲排序方法外，還可以用 。
a．求關鍵路徑的方法b．求最短路徑的dijkstra方法
【18】下面不正確的說法是 。
(1)求從指定源點到其餘各頂點的dijkstra最短路徑演算法中弧上權值可以為負值。 (2)利用dijkstra演算法求所有不同頂點對的最短路徑的演算法時間為o(n3)(圖用鄰接矩陣表示)。
(3)利用floyd演算法求每個不同頂點對的演算法中允許弧上的權值為負，但不能有權之和為負的回徑。
a．(1)、(2)、(3) b．(1) c．(1)、(3d．(2)、(3)
2.填空題（每題12分，共26分）
【1】在n個頂點的無向圖中，若邊數》n-1，則該圖必是連通圖。此斷言是的。
【2】有向圖g有n個頂點{v1，v2，…，vn)，它的鄰接矩陣為a，a[il[j]=1表示從vi到vj存在鄰接關係，而a[i][j]=0則不存在。故g中頂點vi的度為 ① ，而 ② 為所有通過vk的存在形為的路徑個數之和。
【3】n個頂點的連通圖至少條邊。
【4】在無向圖g的鄰接矩陣a中，若a[i][j]等於1，則a[j][i]等於
【5】乙個圖的 ① 表示法是惟一的，而 ② 表示法是不惟一的。
【6】g是乙個非連通無向圖，共有28條邊，則該圖至少有個頂點。
【7】具有10個頂點的無向圖，邊的總數最多為
【8】在有n個頂點的有向圖中，每個頂點的度最大可達
【9】已知圖g的鄰接表如圖所示，其從頂點v1出發的深度優先搜尋序列為 ① ，其從頂點v1出發的廣度優先搜尋序列為 ② 。
【10】已知乙個圖的鄰接矩陣表示，計算第i個結點的入度的方法是
【11】已知乙個圖的鄰接矩陣表示，刪除所有從第i個結點出發的邊的方法是
【12】圖的深度優先搜尋序列和廣度優先搜尋序列不是惟一的。此斷言是的。
【13】如果含n個頂點的圖形成乙個環，則它有棵生成樹。
【14】對n個頂點的連通圖來說，它的生成樹一定有條邊。
【15】對於如圖所示的圖，用普里姆演算法從頂點1開始求最小生成樹，按次序產生的邊為 ① ，共 ② 條邊；用克魯斯卡爾演算法產生的邊次序是 ③ 。(注：邊用(i,j)的形式表示。
)【16】設圖g有n個頂點和e條邊，採用鄰接矩陣儲存，則拓撲排序演算法的時間複雜度為
【17】求最小生成樹的克魯斯卡爾演算法的時間複雜度為 ① ，它對 ② 圖較為適合。
【18】若乙個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲有序序列必定存在。此斷言是的。
【19】設有向圖g如圖所示。
（1）寫出所有的拓撲序列
（2）新增邊後，則僅可能有惟一的拓撲序列。
3.簡答題（共23分）
【1】（3分）從占用的儲存空間來看，對於稠密圖和稀疏圖，採用鄰接矩陣和鄰接表哪個更好些?
《第4章命題與證明》2023年測試卷
一 選擇題 共10小題，每小題4分，滿分40分 1 4分 下列語句不是命題的是 2 4分 如下圖，可判斷ab cd的條件是 3 4分 點到直線的距離是指 4 4分 若三角形的乙個內角等於另外兩個內角之差，則這個三角形是 5 4分 如下圖，在 abc中，ad平分外角 cae，b 30 cad 65 則...
第4章選擇結構
1 下列程式的輸出結果是 include main printf a d,b d n a,b 2 下列程式的輸出結果是 include main 3.下列程式在執行時輸入9後輸出結果是什麼 include main 4.下列程式的輸出結果是 include main printf a d,b d n...
第4章順序結構
第4章流程控制語句 順序結構 1.在銀行存款，設存款金額p 2000元，存款期限n 5年，年利率r 0.05，程式設計計算5年後的本利和。要求小數點後三位，四捨五入。計算在銀行存款的本利和公式為 p1 p 1 r n2.編寫程式，將26個字母按逆序輸出 3.編寫程式，將 河北經貿大學 按逆序輸出4....