一、单选题

第 1 题

1.无向完全图是图中每对结点之间都恰好有一条边的简单图。已知无向完全图G有7个结点，则它共有（ ）条边。

{{ select(1) }}

• 7
• 21
• 42
• 49

---

第 2 题

2.一个简单无向图有10个结点，图中当前存在40条边，请问增加（ ）条边可以成为完全图。

{{ select(2) }}

• 2
• 3
• 4
• 5

---

第 3 题

3.设简单无向图G有16条边且每个结点的度数都是2，则图G有（ ）个结点。

{{ select(3) }}

• 10
• 12
• 8
• 16

---

第 4 题

4.有向图每个结点的度等于该结点的（ ）。

{{ select(4) }}

• 入度
• 出度
• 入度和出度之和
• 入度和出度之差

---

第 4 题

5.有10个结点的无向图至少应该有（ ）条边才能确保是一个连通图。

{{ select(5) }}

• 9
• 10
• 11
• 12

---

二、程序代码填空

深度优先搜索的应用-迷宫问题

【问题描述】 有 1 个 n×n 的迷宫方格，在方格内“0”表示可以通行，“1”表示是障碍物不能通行，在（n，n）位置有一个宝箱。现在有个人在左上角（ 1 , 1 ）的位置，他在迷宫内可以向当前位置的上、下、左、右四个方向行走，能不能在迷宫里走到宝箱位置（ n，n ）。 注意：测试数据保证起点和终点均为“0”，走的过程不能走出迷宫。 【输入描述】 输入第一行为 n（2 ≤n≤10 ），表示 n×n 的方格，接下来有 n 行，每行 n 个整数， 0 表示可以行走，1 表示不能行走，每个整数之间有个空格。 【输出描述】 如果可以走到终点，输出“YES”，否则输出“NO” 【样例输入】 3 0 0 1 1 0 0 0 1 0 【样例输出】 YES

#include<bits/stdc++.h>
using namespace std;
int n,g[11][11];//地图大小 以及 地图数组 
bool flag;//标记是否找到目标，0否 1是 
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; //方向数组，定义行列的下标变化偏移量 
int vis[11][11];//标记数组，标记是否走过 
void dfs(int x,int y){ //搜索点 
	if(__①__){//到达宝箱位置（终点：右下角） 
		flag=1;//到了就把flag设置为1 
		return; 
	} 
	for(int i=0;__②__;i++){//循环枚举4个方向 
		int tx=x+dx[i],ty=y+dy[i];//目标方向的行列下标
		if(tx>0 && tx<=n && ty>0 && ty<=n && __③__ && g[tx][ty]==0){ //判断（tx,ty）不能越界 且没有被搜索过 且 没有障碍物 
			__④__;//标记去过
			dfs(tx,ty);//继续从（tx,ty）位置开始搜索 
		} 
	}
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>g[i][j];//输入地图数据 
		}
	} 
	vis[1][1]=1;
	dfs(1,1); //从左上角起点开始搜索
	if(__⑤__) cout<<"YES";
	else cout<<"NO"; 
	return 0;
}

第 6 题 ①处应该填写 {{ select(6) }}

• x<=n && y<=n
• x==n && y==n
• x>n && y>n
• x<n && y<n

---

第 7 题 ②处应该填写 {{ select(7) }}

• i<4
• i<=4
• i<5
• i<=5

---

第 8 题 ③处应该填写 {{ select(8) }}

• g[tx][ty]==1
• vis[tx][ty]==1
• g[tx][ty]==0
• vis[tx][ty]==0

---

第 9 题 ④处应该填写 {{ select(9) }}

• vis[tx][ty]=0
• vis[tx][ty]=1
• g[tx][ty]=0
• g[tx][ty]=1

---

第 10 题 ⑤处应该填写 {{ select(10) }}

• flag==1
• flag==0
• g[n][n]=0
• vis[n][n]=1

---