浙江理工2017-2019研考数据结构试卷991：数据结构与链表详解

浙江理工大学2017-2019年研究生入学考试试卷，代码991，主要考察的是数据结构相关知识。这份试卷包含了一组关于数据结构和算法的单选题，旨在测试考生对于基础概念的理解和应用能力。 1. 第一部分是单选题，总分为30分，涵盖了链表的基本操作。例如，不带头结点的单链表为空的判定条件是当`simpleList->next==null`，因为这意味着当前结点没有下一个结点。在处理线性表时，考虑到插入和删除操作的效率，选项A（单链表）在最后一个结点后插入或删除较为方便，因为无需移动其他结点。插入操作涉及修改头结点或尾指针，具体实现取决于链表的类型，如选项C中的`S->next=top;top=S;`表示将新结点插入到栈顶。 2. 数组和线性表之间的区别在于，一维数组的长度通常固定，而线性表的长度可以根据需要动态调整。选项A正确，前者长度固定，后者长度可变。 3. 对于矩阵存储，对称矩阵下三角部分的存储优化是关键。由于下三角部分是对角线以下的元素，因此元素`aij`在数组中的下标计算为`i(i-1)/2+j-1`，对应选项A。 4. 在线索化二叉树中，判断一个结点没有左子树的充要条件是该结点的左指针为`null`且左标志`ltag`可能为1或0，选项C结合了这两个条件，是最准确的表述。 5. 有序树转换成二叉树后，原树的后序遍历顺序在新树中保持不变，因此选项C正确，后序遍历的性质在树的形态变换中依然成立。 6. 判定有向图是否存在回路，除了拓扑排序，还可以使用深度优先搜索（DFS）或广度优先搜索（BFS），但题目中提及的是另一种方法，可能是基于图的递归关系或边的计数，但具体选项未给出，需要进一步分析。 这份试卷提供了丰富的数据结构理论和实践题目的考核，考察了学生对链表、矩阵存储、线索化二叉树以及图论基本概念的深入理解和运用能力。对于准备参加浙江理工大学研究生入学考试的考生来说，掌握这些知识点至关重要。