2017年大连理工大学电子信息与电气工程学部810数(7)

【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。

22．两个长度不相同的串有可能相等。（ ）

【答案】

【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。

23．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）

【答案】×

【解析】例如起泡排序是稳定排序，将4，3，2，1按起泡排序排成升序序列，第一趟变成3，2，1，4，此时3就朝向最终位置的相反方向移动。

24．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）

【答案】

【解析】对于链式存储，数据元素之间的存储地址不一定是相邻的，即结点的存储空间可以是不连续的。而结点内部的存储空间需要是连续的，因为它是一个完整的数据。

25．通常使用队列来处理函数或过程的调用。（ ）

【答案】

【解析】经常使用栈来处理函数或过程的调用。

26．二叉树中序线索化后，不存在空指针域。（ ）

【答案】×

【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。

27．在链队列中，即使不设置尾指针也能进行入队操作。（ ）

【答案】

【解析】因为存在头指针，根据链表的性质，根据头指针可以找到为指针。

三、算法设计题

28．按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点的路径

//设有向图有n个顶点

到顶点

【答案】算法如下：