南京理工2014计算机真题：数据结构与链表算法详解

南京理工大学2014年的877计算机专业课程真题包含了数据结构、链表操作、矩阵存储、二叉树遍历以及B-树和线索二叉树的相关知识点。让我们逐一解析： 1. 数据结构部分： - 程序段的时间复杂度考察：给定的函数`function(int n)`通过指数级增长计算2的n次方，时间复杂度为O(log2n)，因为每次循环都将`i`翻倍，直到达到`n`。因此，正确答案是C。 2. 链表操作： - 计算循环单链表数据结点个数：正确的算法是第一个选项，`i=0; p=head; while(p!=NULL) {i++; p=p->next;}`。此算法遍历整个链表，计数结点个数。 3. 矩阵与二叉树： - 对称矩阵的压缩存储：对于n阶对称矩阵，采用压缩存储方式时，下三角部分的元素存储位置可以通过行优先顺序和索引公式得出，即`j*(j+1)/2 + i - 1`，因此正确答案是A。 4. 二叉树遍历： - 结点m和n的相对位置：在前序遍历中n在m之前但在后序遍历中n在m之后，说明n在m的左子树中，并且是m的后继，即n是m的左兄弟，所以答案是C。 5. B-树： - 非空m阶B-树性质：非根结点至少有m/2棵子树，这是B-树的基本性质之一，选项A正确。 6. 线索二叉树： - 结点K的直接前驱：在中序线索二叉树中，如果结点K有左孩子但不是根节点，它的直接前驱是K的左子树中最靠左边的结点，答案是A。 7. 森林到二叉树的转换： - 转换后的二叉树根结点的右子树：从第一棵树开始，根结点的右子树将包含第二棵树和第三棵树的所有结点，即`n2 + n3`，答案是A。 8. 平衡二叉树调整： - 插入25后引起不平衡：平衡二叉树（如AVL或红黑树）在插入后可能会失去平衡。在这种情况下，通常需要通过旋转操作来调整，但题目没有具体说明如何调整，只是提及不平衡，所以这部分没有直接的答案。 总结起来，这份真题覆盖了数据结构中的时间复杂度分析、链表操作、矩阵存储、二叉树遍历、B-树特性以及线索二叉树的特定规则等核心知识点，有助于理解这些概念并准备相关考试。