單選題

題號	題目	答案
1	具有5個頂點的有向完全圖有多少條弧？	20
2	在N個頂點的無向圖中，所有頂點的度之和不會超過頂點數(shù)的多少倍？	N?1
3	如果G是一個有28條邊的非連通無向圖，那么該圖頂點個數(shù)最少為多少？	9
4	若一個有向圖用鄰接矩陣表示，則第i個結(jié)點的入度就是（）；已知一個有向圖的鄰接矩陣表示,則計算i個結(jié)點的出度的方法是（）	第i列的非零元素個數(shù) ；求矩形第i行非零元素之和
5	設(shè)無向圖的頂點個數(shù)為N，則該圖最多有多少條邊？	N(N?1)/2
6	對于給定的有權(quán)無向圖G，下列哪個說法是正確的？	D
7	下列有關(guān)圖的敘述中，有幾句是對的？	4句
8	給定有向圖的鄰接矩陣如下圖，頂點2（編號從0開始）的出度和入度分別是：	0, 2
9	對于給定的有向圖如下，其鄰接表為：
10	給出如下圖所示的具有 7 個結(jié)點的網(wǎng) G，哪個選項對應(yīng)其正確的鄰接矩陣？

選擇題題解

3、連通無向圖構(gòu)成條件:邊 = 頂點數(shù) * ( 頂點數(shù)-1 ) /2
所以28個條邊的連通無向圖頂點數(shù)最少為8個
所以28條邊的非連通無向圖為9個(加入一個孤立點)

函數(shù)題（沒什么參考性，不用仔細看）

6-1 鄰接矩陣存儲圖的深度優(yōu)先遍歷 (50分)

試實現(xiàn)鄰接矩陣存儲圖的深度優(yōu)先遍歷。

函數(shù)接口定義：

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );

其中MGraph是鄰接矩陣存儲的圖，定義如下：

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;  /* 頂點數(shù) */
    int Ne;  /* 邊數(shù)   */
    WeightType G[MaxVertexNum][MaxVertexNum]; /* 鄰接矩陣 */
};
typedef PtrToGNode MGraph; /* 以鄰接矩陣存儲的圖類型 */

函數(shù)DFS應(yīng)從第V個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖Graph，遍歷時用裁判定義的函數(shù)Visit訪問每個頂點,。當(dāng)訪問鄰接點時，要求按序號遞增的順序,。題目保證V是圖中的合法頂點,。

輸入樣例：給定圖如下

5

輸出樣例：

DFS from 5: 5 1 3 0 2 4 6

代碼

#include <stdio.h>

typedef enum {false, true} bool;
#define MaxVertexNum 10  /* 最大頂點數(shù)設(shè)為10 */
#define INFINITY 65535   /* ∞設(shè)為雙字節(jié)無符號整數(shù)的最大值65535*/
typedef int Vertex;      /* 用頂點下標(biāo)表示頂點,為整型 */
typedef int WeightType;  /* 邊的權(quán)值設(shè)為整型 */

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;  /* 頂點數(shù) */
    int Ne;  /* 邊數(shù)   */
    WeightType G[MaxVertexNum][MaxVertexNum]; /* 鄰接矩陣 */
};
typedef PtrToGNode MGraph; /* 以鄰接矩陣存儲的圖類型 */
bool Visited[MaxVertexNum]; /* 頂點的訪問標(biāo)記 */

MGraph CreateGraph(); /* 創(chuàng)建圖并且將Visited初始化為false；裁判實現(xiàn)，細節(jié)不表 */

void Visit( Vertex V )
{
    printf(" %d", V);
}

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );


int main()
{
    MGraph G;
    Vertex V;

    G = CreateGraph();
    scanf("%d", &V);
    printf("DFS from %d:", V);
    DFS(G, V, Visit);

    return 0;
}

/* 你的代碼將被嵌在這里 */
// 深度優(yōu)先代碼部分
void DFS(MGraph Graph, Vertex V, void(*Visit)(Vertex))
{
Visited[V] = true;
Visit(V);
for (int i = 0; i < Graph->Nv; i++)
{
if (Graph->G[V][i]<INFINITY&&!Visited[i])
{
DFS(Graph, i, Visit);
}
}

}