算法与数据结构试题及答案.doc

算法与数据结构试题及答案 本资源主要涵盖了算法与数据结构的相关知识点，包括简答题、判断题、单项选择题等类型，涉及到数据结构的基本概念、算法设计、数据存储和处理等方面。 一、简答题 1. 算法与程序的区别：算法是解决问题的步骤或方法，而程序是算法的实现。算法是独立于程序的，一个算法可以有多种实现方式，而一个程序只能对应一个算法。 2. 哈希表中的冲突可能性：哈希表中的冲突可能性与哈希函数的设计、键的分布和表的大小有关。为了减少冲突的可能性，需要设计良好的哈希函数和冲突解决策略。 3. 图的遍历中的访问标志数组：在图的遍历中，设置访问标志数组可以避免重复访问同一个结点，从而提高遍历效率。 4. 头指针、头结点、首元素结点的关系：头指针是指向链表第一个结点的指针，头结点是链表的第一个结点，首元素结点是链表的第一个元素。 5. 顺序队列中的假溢出：顺序队列中的假溢出是指队列中元素的个数超过了队列的容量，导致队列溢出的情况。可以通过队列的动态扩容或缩减来解决假溢出问题。 二、判断题 1. 广义表的表头和表尾：广义表(((a), b), c) 的表头是((a), b)，表尾是( c )。（正确） 2. 哈夫曼树的结点权值：在哈夫曼树中，权值最小的结点离根结点最近。（正确） 3. 基数排序：基数排序是高位优先排序法。（正确） 4. 平衡二叉树的高度差：在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过 1。（正确） 5. 单链表的插入操作：在单链表中，给定任一结点的地址 p，则可用下述语句将新结点 s 插入结点 p 的后面：p->next = s; s->next = p->next;。（正确） 6. 抽象数据类型（ADT）：抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个 ADT 的逻辑特性，不必考虑如何在计算机中实现。（正确） 7. 数组元素的下标值：数组元素的下标值越大，存取时间越长。（错误） 8. 邻接矩阵法存储图：用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（错误） 9. 拓扑排序：拓扑排序是按 AOE 网中每个结点事件的最早发生时间对结点进行排序。（正确） 10. 长度为 1 的串：长度为 1 的串等价于一个字符型常量。（正确） 三、单项选择题 1. 排序方法：排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是冒泡排序的基本思想。 2. 删除有向图的边：已知一个有向图的邻接矩阵表示，要删除所有从第 i 个结点发出的边，应该将邻接矩阵的第 i 行元素全部置为 0。 3. 双向循环链表的空条件：有一个含头结点的双向循环链表，头指针为 head, 则其为空的条件是 head->next==head。 4. 折半法查找：在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值 11，所需的关键码比较次数为 4。 5. 队列的基本运算：以下不是队列的基本运算的是从队列中删除第 i 个元素。 6. 顺序表的插入操作：在长度为 n 的顺序表的第 i 个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为 n – i + 1。 7. 线性表的存储结构：对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为用头指针表示的循环单链表。