2022 初赛

考虑由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（）个非零元素。

A.N-$1$

B.N

C.N+$1$

D.N$^2$

解析：

一道计算题，我们得知道有向连通图的定义是：

• 图的边有方向，只能按箭头方向从一点到另一点，如果图G中任意两个顶点都是连通的，则称图G是有向连通图。

既然任意两个顶点都是连通的，那么每一个顶点的度（包括入度与出度）都不为零。所以选B。

错误原因：

对图的掌握不扎实，基本都忘记各种定义了。好好补补吧。

---

以下对数据结构的表述不恰当的一项为（）。

A.图的深度优先遍历算法常使用的数据结构为栈。

B.栈的访问原则为后进先出，队列的访问原则是先进先出。

C.队列常常被用于广度优先搜索算法。

D.栈与队列存在本质不同，无法用栈实现队列。

解析：

一道概念题，用两个栈可以模拟队列：

第一个栈顶元素为队列的队头，第二个栈顶元素为队列的队尾。所以选D。

错误原因：

没有想到深度优先遍历算法的根本——栈。就盲目的选择了A。

---

一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则abcab有（）个内容互不相同的子串。

A.$12$

B.$13$

C.$14$

D.$15$

解析：

一道枚举题。枚举每种可能即可：

$0$个字符（$1$个）：$\phi$

$1$个字符（$3$个）：a，b，c

$2$个字符（$3$个）：ab，bc，ca

$3$个字符（$3$个）：abc，bac，cab

$4$个字符（$2$个）：abca，bcab

$5$个字符（$1$个）：abcab

那么答案就是$1+3+3+3+2+1=13$。所以选择B。

错误原因：

没有想到空串$\phi$的情况，下次要细心，仔细回想老师教的知识点。

谢谢