- A+
所属分类：计算机科学技术题库
答案查询网公众号已于近期上线啦
除基本的文字搜题外，准备上线语音搜题和拍照搜题功能！微信关注公众号【答案查询网】或扫描下方二维码即可体验。
【◆参考答案◆】：B
(2)【◆题库问题◆】：[单选] 删除一单向链表中P指针所指向结点的后继结点，正确的操作是（）。
A．p->next=p->next->next
B．p=p->next
C．p->next=p
D．p->next->next=p->next
A．p->next=p->next->next
B．p=p->next
C．p->next=p
D．p->next->next=p->next
【◆参考答案◆】：A
(3)【◆题库问题◆】：[单选] 一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（）。
A．*S->top=e；S->top++；
B．S->top++；*S->top=e；
C．*S->top=e
D．S->top=e；
A．*S->top=e；S->top++；
B．S->top++；*S->top=e；
C．*S->top=e
D．S->top=e；
【◆参考答案◆】：A
(4)【◆题库问题◆】：[判断题] 取线性表的第i个元素的时间同i的大小有关
A．正确
B．错误
A．正确
B．错误
【◆参考答案◆】：正确
(5)【◆题库问题◆】：[单选] 数据结构在计算机内存中的表示是指（）。
A．数据的存储结构
B．数据结构
C．数据的逻辑结构
D．数据元素之间的关系
A．数据的存储结构
B．数据结构
C．数据的逻辑结构
D．数据元素之间的关系
【◆参考答案◆】：A
(6)【◆题库问题◆】：[填空题] n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为（）；若采用邻接表存储，该算法的时间复杂度为（）。
【◆参考答案◆】：O(n2) O(n+e)
(7)【◆题库问题◆】：[单选] n个顶点的完全有向图中含有（）。
A．n-1条有向边
B．n条有向边
C．n（n-1）/2条有向边
D．n（n-1）条有向边
A．n-1条有向边
B．n条有向边
C．n（n-1）/2条有向边
D．n（n-1）条有向边
【◆参考答案◆】：D
(8)【◆题库问题◆】：[判断题] 在表结构中最常用的是线性表，栈和队列不太常用。
A．正确
B．错误
A．正确
B．错误
【◆参考答案◆】：正确
【◆答案解析◆】：不一定吧？调用子程序或函数常用，CPU中也用队列。
(9)【◆题库问题◆】：[问答题] 具有n个顶点的强连通图至少有多少条边？这样的图应该是什么形状？
【◆参考答案◆】：
具有n个顶点的强连通图至少有n条边，这样的图是一个由n个顶点构成的环。
强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通，因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧，每个顶点的入度和出度至少各为1，即顶点的度至少为2，这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得：边数=2×n/2=n。
具有n个顶点的强连通图至少有n条边，这样的图是一个由n个顶点构成的环。
强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通，因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧，每个顶点的入度和出度至少各为1，即顶点的度至少为2，这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得：边数=2×n/2=n。
(10)【◆题库问题◆】：[问答题] 具有n个顶点的有向无环图最多有多少条边？
【◆参考答案◆】：
具有n个顶点的有向无环图最多有n×（n—1）/2条边。
这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，„，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有（n-1）+（n-2）+„+2+1=n×（n-1）/2条边。
具有n个顶点的有向无环图最多有n×（n—1）/2条边。
这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，„，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有（n-1）+（n-2）+„+2+1=n×（n-1）/2条边。
