大专考试数据结构题一、单项选择题（每题5分，共30分）1.以下说法正确的是（）。A．连能分量是无向图中的极小连通子图B．强连通分量是有向图中的极大强连通子图C．在一个有向图

　　大专考试数据结构题

　　一、单项选择题（每题5分，共30分）

　　1.以下说法正确的是（）。

　　A．连能分量是无向图中的极小连通子图

　　B．强连通分量是有向图中的极大强连通子图

　　C．在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧

　　D．对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图

　　2.求解最短路径的Floyd算法的时间复杂度为()。

　　A．O（n）B．O（n+c）

　　C．O（n*n）D．O（n*n*n）

　　3.采用邻接表存储的图，其广度优先遍历类似于二叉树的（）。

　　A．按层次遍历B．中序遍历

　　C．后序遍历D．先序遍历

　　4.假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判断队空的条件为（）。

　　A．front+1==rearB．rear+1==front

　　C．front==0D．front==rear

　　5.从一个顺序循环队列中删除元素时，首先需要（）。

　　A．前移队首指针B．后移队首指针

　　C．取出队首指针所指位置上的元素D．取出队尾指针所指位置上的元素

　　二、填空题（每空2分，共20分）

　　1.在栈的运算中，栈的插入操作称为_________或_________，栈的删除操作称为或_________。

　　2.当栈满的时候，再进行入栈操作就会产生_________，这种情况的溢出称为_________；当栈空的时候，如果再进行出栈操作，也会_________，这种情况下的溢出称为_________。

　　3.串中字符的个数称为串的。

　　4.一个连通图的　是一个极小连通子图。

　　三、算法（10分）

　　请阅读下列算法，回答问题

　　PROCEDUREsort（r，n）

　　BEGIN

　　FORi:=2TOnDO

　　BEGIN

　　x:=r(i)；r(O):=x；j:=i-1；

　　WHILEx.key