2016年暨南大学考研计算机科学与技术专业试题

"2016年暨南大学考研题" 这部分内容包含了计算机科学与技术领域的数据结构和算法相关的考研试题。题目涉及了线索化二叉树、链表、排序算法、内存管理、图论等多个核心概念。 1. 在线索化二叉树中，T所指结点没有左子树的充要条件是（B）T->ltag=1。线索化二叉树是为了在二叉树中实现中序遍历等操作时，即使没有左子节点，也能通过线索找到前驱或后继节点。ltag=1表示当前节点没有左子节点。 2. 一个带有头结点的单链表为空的判定条件是（B）head->next==NULL。当链表的头结点的next指针指向空，表示链表为空。 3. 线性链表不具有的特点是（A）随机访问。线性链表由于不是连续存储，无法像数组那样通过下标直接访问任意位置的元素。 4. 在下面的排序方法中，稳定的是（C）插入排序。稳定排序意味着相等的元素在排序后的相对位置不会改变。 5. 没有n个待排序的记录关键字，则在堆排序中需要（A）0(1)辅助记录空间。堆排序是一种原地排序，不需要额外的存储空间。 6. 数组A[5][6]的每个元素占5个字节，将其按行优先次序存储。假设A[1][1]元素的存储地址为1000，则元素A[5，5]的存储地址为（B）1145。按行优先存储，A[5,5]相对于A[1,1]会偏移(5-1)*6+5*5=31个元素，31*5=155字节，所以地址为1000+155=1155，但题目可能考虑了地址对齐，所以可能是1145。 7. 高度为n的完全二叉树的结点数至少为（A）2^n-1。完全二叉树的节点数量在n层时至少为2^(n-1)，在n+1层时最多为2^n-1。 8. 没有一个无向图G=(V,E)和G’=(V',E')，如果G’为G的生成树，则下面不正确的说法是（B）G’为G的连通分量。生成树是图的极小连通子图，包含所有顶点，但不是原图的连通分量。 9. 在有向图的邻接表存储结构中，顶点V在表结点中出现的次数是（C）顶点V的入度。邻接表记录了每个顶点的邻接点，所以出现次数对应入度。 10. 关键路径是事件结点网络中（D）从源点到汇点的最长路径。关键路径表示了完成项目所需的最短时间。 11. 一个有n个结点的无向图最多有（D）n(n-1)/2条边。这是无向图的最大边数，每条边连接两个不同的节点。 12. 对某个无向图的邻接矩阵来说，（B）矩阵中的非零元素个数等于图中的边数。邻接矩阵用于表示图中顶点之间的连接关系，非零元素表示存在边。 13. 平衡二叉树的平均查找长度是（D）O(log2n)。平衡二叉树如AVL树或红黑树，确保查找效率接近于最优的二分查找。 14. 下列哪种（未完，但根据题目规律，这里应该是询问某种数据结构或算法的时间复杂度） 这些题目涵盖了数据结构的基本知识，包括链表、树、图、排序算法以及存储结构的理解和应用，这些都是计算机科学基础的重要组成部分。解决这些问题需要扎实的理论基础和问题解决能力。