n 个顶点的无向图和有向图,采用邻接矩阵表示,如何判断以下问题:图中有多少条边?任Р 意两个顶点 i 和 j 之间是否有边相连?任意一个顶点的度是多少?(7 分) Р 2.判别下列序列是否为堆(小根堆或大根堆), 若不是, 则将其调整为堆(8 分): Р ( 1 )( 100,86,48,73,35,39,42,57,66,21) Р (2)( 12,70,33,65,24,56,48,92,86,33) Р (3)( 05,23,20,35,28,38,29,61,56,76,40,100) Р 3.设 A 和 B 均为下三角矩阵,每一个都有 n 行 n 列。因此在下三角区域中各有 n(n+1)/2 个无素。另设Р 有一个二维数组 C,它有 n 行 n +1 列。试设计一个方案,将两个矩阵 A 和 B 中的下三角区域元素存Р 放于同一个 C 中。要求将 A 的下三角区域中的元素存放于 C 的下三角区域中,B 的下三角区域中的Р 元素转置后存放于 C 的上三角区域中。并给出计算 A 的矩阵元素 aij 和 B 的矩阵元素 bij 在 C 中的存Р 放位置下标的公式。( 5 分) Р二、已知 f 为单链表的表头指针,链表中存储的都是整型数据,试设计算法将此链表的结点按照递增次序Р 进行就地排序。( 15 分) Р三、给出中序线索二叉树的结点结构,试编写在不使用栈和递归的情况下先序遍历中序线索二叉树的算法。Р (20 分) Р四、设关键字是一个由 26 个小写字母组成的字符串,哈希表的长度为 26。试编写算法,建立哈希表,并Р 以第一个字符的字典顺序输出哈希表中的所有关键字。设哈希函数为 hash(x)=x 中的第一个字符在字Р 典顺序中的序号,采用线性探测再散列法来解决冲突。( 假设函数 f(x)能够计算出 x 中的第一个字符在Р 字典顺序中的序号。)( 20 分) Р 1
全文预览
