数据结构模拟试题解析：算法与哈希表

"算法与数据结构试题及答案" 这篇文档包含了关于算法与数据结构的试题及其答案，涵盖了基础知识、判断题和选择题等多个方面。以下是这些题目涉及到的主要知识点： 1. **算法与程序的区别**：算法是一组明确的、有限的、可执行的操作步骤，它用于解决问题或完成特定任务。程序则是实现算法的代码，它是具体的、可以运行在计算机上的语言编写的指令集合。 2. **哈希表与冲突**：哈希表通过哈希函数将键映射到数组的索引上。冲突发生在两个不同的键被哈希到同一个位置时。冲突可能性与哈希函数的选择、表的大小以及键的分布有关。好的哈希函数应尽可能减少冲突。 3. **图的遍历中的访问标志数组**：在图的深度优先搜索（DFS）或广度优先搜索（BFS）中，访问标志数组用于标记某个节点是否已被访问过，以避免重复访问并确保遍历完整个图。 4. **头指针、头结点和首元素结点**：在链表中，头指针指向链表的第一个节点，即头结点；头结点并不一定是链表的第一个数据元素，可能包含额外的信息；首元素结点是指链表中第一个存储实际数据的节点。 5. **顺序队列的假溢出**：在顺序队列中，当队列的最后一个元素被访问后，若再进行入队操作，但在物理内存未满的情况下无法继续扩展，称为假溢出。解决方法通常包括动态数组的扩展或使用链式队列。 6. **判断题知识点**： - 广义表的表头和表尾：表头是第一个（最外层）括号内的部分，表尾是除去表头后的部分。 - 哈弗曼树：权值最小的结点离根结点最近是哈弗曼树（最优二叉树）的特性。 - 基数排序：高位优先（MSD）排序是基数排序的一种，从最高位开始排序。 - 平衡二叉树：任意结点左右子树高度差不超过1。 - 链表插入：在单链表中，新结点插入p后面正确操作是p->next=s; s->next=p->next。 - 抽象数据类型：定义独立于实现，仅描述逻辑特性。 - 数组存取时间：数组存取时间与下标无关，一般为常量时间。 - 邻接矩阵存储图：占用空间与节点数和边数都有关。 - 拓扑排序：按照事件最早发生时间排序。 - 字符串与字符常量：长度为1的字符串等价于单个字符。 7. **单项选择题知识点**： - 冒泡排序：基本思想是比较相邻元素并交换，直至序列有序。 - 删除有向图边：在邻接矩阵中，删除第i行元素置0即可。 - 双向循环链表为空：当头指针的next等于自身时，链表为空。 - 折半查找：在有序列表中，折半查找通过每次比较中间元素来减少查找次数，题目中11不在列表中，需要比较4次。 - 未提供选项的题目：通常涉及某种排序算法的特点或链表操作。 这些题目覆盖了算法设计、数据结构基础、图论、链表操作、队列和排序等多个核心主题，对于理解和掌握这些概念非常有帮助。