下载文档原格式
《数据结构》期末考试试题及答案一、单项选择题1. 数据结构是计算机科学的基础学科之一。
下列哪个选项正确描述了数据结构的定义？A. 数据结构是一种计算机程序B. 数据结构是一种存储和组织数据的方法C. 数据结构是一种人工智能技术D. 数据结构是一种操作系统答案：B2. 链表和数组是常见的数据结构，它们之间的主要区别是：A. 数组可以存储不同类型的数据，而链表只能存储相同类型的数据B. 数组的元素在内存中是连续存储的，而链表的元素在内存中是分散存储的C. 链表可以随机访问元素，而数组只能顺序访问元素D. 链表的插入和删除操作更高效，而数组的访问操作更高效答案：B3. 在二叉树中，每个节点最多可以有多少个子节点？A. 1B. 2C. 3D. 无限多个答案：B二、填空题1. 假设有一组数据 [5, 8, 3, 2, 9]，按照从小到大的顺序进行冒泡排序的过程中，经过三次交换后的结果是__2__，__3__，__5__，__8__，__9__。
2. 请完成以下代码，实现栈的入栈和出栈操作：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():return self.stack.pop()def is_empty(self):# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False ```答案：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():def is_empty(self):return len(self.stack) == 0# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False```三、简答题1. 请简要介绍树的基本概念及常见的树结构。
数据结构期末考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 编写代码的时间B. 代码的长度C. 执行代码所需的时间D. 执行代码所需的指令条数2. 下列关于队列的描述，错误的是（）。
A. 队列是先进先出（FIFO）的线性表B. 队列允许在一端进行插入操作C. 队列的插入操作称为入队D. 队列的删除操作称为出栈3. 对于长度为n的有序数组，使用二分查找法查找一个元素的平均时间复杂度是（）。
A. O(n)B. O(n^2)C. O(log n)D. O(1)4. 在图的遍历中，深度优先搜索（DFS）使用的数据结构是（）。
A. 栈B. 队列C. 链表D. 数组5. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决冲突的方法？（）A. 开放寻址法B. 链地址法C. 线性探测法D. 排序法6. 一个完全二叉树共有700个节点，它的最大节点数是（）。
A. 700B. 701C. 1400D. 14017. 快速排序算法的最坏情况发生在（）。
A. 每次选择的基准都是最大值B. 数据已经有序C. 数据已经完全逆序D. 所有数据元素相等8. 在一个具有n个节点的二叉搜索树中，最坏情况下查找一个元素的时间复杂度是（）。
A. O(n)B. O(log n)C. O(n^2)D. O(1)9. 堆排序算法中，将一个堆调整为最大堆或最小堆的过程称为（）。
A. 堆调整B. 堆构建C. 堆分解D. 堆维护10. 以下哪个不是B树的特性？（）A. 所有键值都存储在内部节点和叶子节点中B. 所有叶子节点都在同一层上C. 每个内部节点至多有m个子节点D. 每个内部节点的非叶子子节点都至少有m/2个子节点二、简答题（每题5分，共30分）1. 什么是递归？请举例说明递归算法的应用场景。
2. 请简述图的邻接矩阵和邻接表两种存储方式的优缺点。
3. 解释什么是平衡二叉树，并说明它为什么在实际应用中很重要。
数据结构期末考试试题及答案一、选择题1. 以下哪种数据结构是线性存储结构？A. 树B. 图C. 栈D. 队列答案：C2. 在链表中，如果一个节点既没有前驱也没有后继，那么这个节点被称作什么？A. 首节点B. 尾节点C. 中间节点D. 孤立节点答案：B3. 树的度是指什么？A. 树中节点的个数B. 树中最大的层次数C. 树的分支数D. 树的节点的度的最大值答案：C4. 在二叉搜索树中，若要查找给定值的节点，当查找失败时应返回的值是？A. -1B. 0C. 1D. 该值本身答案：A5. 快速排序算法的时间复杂度最坏情况下是多少？A. O(n)B. O(nlogn)C. O(n^2)D. O(n!)答案：C二、填空题1. 在顺序表中，元素的物理位置相邻的特点是________，这使得顺序表在________操作上具有较高的效率。
答案：连续性；访问2. 链表相比顺序表的优势在于它能够动态地________存储空间，并且________操作不需要移动大量元素。
答案：分配和释放；插入与删除3. 栈是一种________的数据结构，只允许在________进行插入和删除操作。
答案：后进先出；栈顶4. 图的遍历算法主要有两种，分别是________和________。
答案：深度优先搜索；广度优先搜索5. 哈夫曼树是一种特殊的二叉树，它常用于数据压缩，其构建过程是基于________原则。
答案：最小权值三、简答题1. 请简述数组和链表的优缺点。
答案：数组通过索引直接访问元素，访问速度快，但大小固定，插入和删除操作需要移动大量元素。
链表元素通过指针连接，可以动态分配大小，插入和删除效率高，但访问速度较慢，因为需要从头开始遍历。
2. 什么是二叉树的前序遍历、中序遍历和后序遍历？答案：二叉树的前序遍历是先访问根节点，然后遍历左子树，最后遍历右子树。
中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。
后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。
数据结构期末考试试卷及答案一、选择题（每题2分，共20分）1. 下面哪一项不是数据结构的基本类型？（）A. 线性结构B. 树形结构C. 集合结构D. 图形结构答案：C2. 在链表中，存储元素的数据域称为（），存储下一个元素地址的域称为（）。
A. 节点，指针B. 指针，节点C. 数据域，指针域D. 指针域，数据域答案：C3. 下面哪种排序算法的平均时间复杂度最高？（）A. 冒泡排序B. 快速排序C. 堆排序答案：A4. 在二叉树中，具有n个节点的完全二叉树的深度至少是（）A. log2nB. log2(n+1)C. log2n+1D. log2(n-1)答案：C5. 下面哪种树的节点中不包含任何关键字？（）A. 二叉搜索树B. 哈希树C. 平衡二叉树D. B树答案：B6. 下面哪个算法不是用来解决排序问题的？（）A. 快速排序B. 冒泡排序C. 二分查找答案：C7. 下面哪种数据结构的存储方式不是顺序存储？（）A. 线性表B. 栈C. 队列D. 树答案：D8. 下面哪种算法的时间复杂度是O(nlogn)？（）A. 冒泡排序B. 快速排序C. 插入排序D. 选择排序答案：B9. 下面哪个算法不是用来解决查找问题的？（）A. 二分查找B. 顺序查找C. 快速排序D. 哈希查找答案：C10. 下面哪个算法不是用来解决图论问题的？（）A. 深度优先搜索B. 广度优先搜索C. 最短路径算法D. 快速排序答案：D二、填空题（每题2分，共20分）11. 在线性表中，插入和删除操作的时间复杂度是______。
答案：O(n)12. 在链表中，插入和删除操作的时间复杂度是______。
答案：O(1)13. 快速排序的平均时间复杂度是______。
答案：O(nlogn)14. 堆排序的平均时间复杂度是______。
答案：O(nlogn)15. 二分查找的时间复杂度是______。
答案：O(logn)16. 在二叉树中，度为0的节点数等于度为2的节点数加______。
数据结构考试试题题库一、选择题1. 在数据结构中，线性表是按照什么顺序存储数据的？A. 随机B. 无序C. 有序D. 连续2. 栈（Stack）是一种遵循哪种原则的数据结构？A. 先进先出（FIFO）B. 先进后出（LIFO）C. 后进先出（LILO）D. 随机访问3. 哈希表（Hash Table）的主要优点是什么？A. 存储空间大B. 访问速度快C. 易于排序D. 易于扩展二、简答题1. 请简述数组和链表的区别。
2. 什么是二叉树？请描述二叉树的几种遍历方法。
三、计算题1. 给定一个单链表，编写一个算法来删除链表中的重复元素。
2. 假设有一个数组，其中包含n个元素，编写一个算法来找到数组中的第k小的元素。
四、应用题1. 描述如何使用队列来实现一个打印任务调度系统。
2. 请解释二叉搜索树（BST）的插入操作，并给出相应的算法实现。
五、编程题1. 编写一个C++函数，实现对一个给定的整数数组进行排序。
2. 编写一个Python函数，实现对一个二叉树进行层次遍历。
六、论述题1. 讨论图的两种存储结构：邻接矩阵和邻接表，并比较它们的优缺点。
2. 解释什么是递归，并给出一个使用递归解决实际问题的例子。
结束语数据结构的学习不仅仅是对概念的理解，更重要的是能够将这些概念应用到实际问题的解决中。
通过本题库的练习，希望能够加深你对数据结构的理解和应用能力。
请注意，这只是一个示例题库，实际的考试题库可能会包含更多的题目和不同的题型。
考生应根据具体的课程内容和考试要求来准备。
数据结构期末考试题及答案一、选择题（每题2分，共10题）1. 数据结构是指（）A. 存储和组织数据的方式B. 对数据进行计算和处理的方法C. 数据的物理表示形式D. 数据的逻辑结构答案：A. 存储和组织数据的方式2. 在数据结构中，栈是一种（）A. 先进先出的数据结构B. 后进先出的数据结构C. 随机存取的数据结构D. 按键值查找的数据结构答案：B. 后进先出的数据结构3. 下列哪种数据结构不支持随机访问？（）A. 队列B. 栈C. 数组D. 链表答案：D. 链表4. 在二叉树中，每个节点最多可以有几个子节点？（）A. 0B. 1C. 2D. 无限多答案：C. 25. 在图的表示方法中，邻接矩阵适用于（）A. 稠密图B. 稀疏图C. 有向图D. 无向图答案：A. 稠密图6. 下列排序算法中，最坏情况时间复杂度为O(nlogn)的是（）A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序答案：C. 快速排序7. 广度优先搜索算法用于（）A. 求最短路径B. 求全排列C. 求最小生成树D. 求图的连通分量答案：A. 求最短路径8. 哈希表的查找时间复杂度为（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A. O(1)9. AVL树是一种（）A. 无序树B. 有序树C. 平衡树D. 非平衡树答案：C. 平衡树10. 以下哪个不属于基本的查找算法？（）A. 二分查找B. 插值查找C. 散列查找D. 顺序查找答案：C. 散列查找二、填空题（每题4分，共4题）11. 下列不是线性表的是（）答案：二叉树12. 在冒泡排序中，每一轮的比较次数是________答案：n-113. 在堆排序中，堆的建立时间复杂度为________答案：O(n)14. 从一个顶点到其余各顶点的最短路径算法是________答案：Dijkstra算法三、简答题（每题10分，共3题）15. 请简要说明栈的应用场景，并给出一个具体实例。
数据结构期末考试试题及答案一、选择题1. 在数据结构中，以下哪种数据结构是“先进先出”（FIFO）的？A. 栈B. 队列C. 链表D. 堆答案：B2. 哪种数据结构具有类似现实生活中“洋葱”的结构？A. 链表B. 树C. 图D. 堆答案：B3. 在常见的排序算法中，以下哪个算法具有最好的时间复杂度？A. 快速排序B. 插入排序C. 冒泡排序D. 选择排序答案：A4. 以下哪个数据结构可以解决“最短路径”问题？A. 队列B. 链表C. 树D. 图答案：D5. 在二叉搜索树中，节点的左子树的值都小于节点的值，右子树的值都大于节点的值。
这种特点被称为：A. 平衡性B. 完全性C. 左倾性D. 有序性答案：D二、填空题1. 在栈的操作中，插入元素的操作被称为______。
答案：push2. 哈希表通过______的方式快速查找元素。
答案：散列3. 在链表中，指向链表头部的指针被称为______。
答案：头指针4. 在图的遍历算法中，使用队列的遍历方式被称为______。
答案：广度优先搜索5. 大O表示法中，表示最坏情况下时间复杂度的记号是______。
答案：O三、简答题1. 请简要说明栈和队列的特点及应用场景。
答：栈是一种先进后出（FILO）的数据结构，只能在栈顶进行插入和删除操作。
栈的应用场景包括函数调用、表达式求值、撤销操作等。
队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。
队列的应用场景包括多线程任务调度、消息队列等。
2. 简要描述堆排序的思想和步骤。
答：堆排序是一种基于二叉堆的排序算法。
首先，将待排序序列构建成一个大顶堆；然后，将堆顶元素与最后一个元素交换，即将最大元素放到已排序部分的末尾；接着，重新调整堆，将剩余元素重新构建成大顶堆；重复以上步骤，直到所有元素排序完成。
四、编程题请使用C语言实现一个二叉树的前序遍历算法。
```c#include <stdio.h>#include <stdlib.h>struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};void preorderTraversal(struct TreeNode* root) {if (root != NULL) {printf("%d ", root->val); // 先访问根节点preorderTraversal(root->left); // 再遍历左子树preorderTraversal(root->right); // 最后遍历右子树}}int main() {// 构建二叉树struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));struct TreeNode* node1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = 1;node1->val = 2;node2->val = 3;root->left = node1;root->right = node2;node1->left = NULL;node1->right = NULL;node2->left = NULL;node2->right = NULL;// 调用前序遍历函数preorderTraversal(root);return 0;}```本文介绍了数据结构期末考试的试题及答案，涵盖了选择题、填空题、简答题和编程题等不同题型。
数据结构考试试题题库一、选择题1. 在数据结构中，栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的任意位置插入和删除元素B. 只能在表的一端进行插入和删除操作C. 只能在表的两端进行插入和删除操作D. 只能在表的中间进行插入和删除操作答案：B2. 假设有一个单链表，头结点的指针域为head，链表中每个结点包含一个数据域data和指向下一个结点的指针域next。
若要删除指针p所指向的结点，以下哪个操作是正确的？A. p = p->nextB. p->next = p->next->nextC. p = p->next->nextD. p = NULL答案：B3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根节点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根节点，最后遍历右子树C. 先遍历右子树，然后访问根节点，最后遍历左子树D. 同时遍历左子树和右子树答案：A4. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再哈希法D. 排序法答案：D5. 快速排序算法的时间复杂度在最好、最坏和平均情况下分别是：A. O(n log n), O(n^2), O(n)B. O(n), O(n log n), O(n^2)C. O(n log n), O(n), O(n log n)D. O(n^2), O(n log n), O(n)答案：A二、简答题1. 请简述什么是图，并说明图的两种基本表示方法。
答案：图是一种数据结构，由顶点（或称为节点）和边组成。
图可以表示为有向图或无向图。
图的两种基本表示方法为邻接矩阵和邻接表。
邻接矩阵是一个二维数组，其元素表示顶点之间的连接关系；邻接表则使用链表存储每个顶点的邻接点。
2. 什么是二叉搜索树（BST）？请简述其特点。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。
数据结构考试题及答案一、选择题1. 下列哪种数据结构是一种线性结构？A. 树B. 栈C. 图D. 队列答案：B. 栈2. 以下哪种不是二叉树的遍历方式？A. 先序遍历B. 层序遍历C. 后序遍历D. 中序遍历答案：B. 层序遍历3. 在队列中，哪种操作不是O(1)时间复杂度的？A. 入队B. 出队C. 判空D. 获取队首元素答案：D. 获取队首元素二、填空题4. 二叉查找树的中序遍历结果为_______。
答案：升序排列的序列5. 栈的特点是_______进，_______出。
答案：后进，先出6. 图中两点间存在边则称它们为_______。
答案：邻接点三、简答题7. 请简要介绍一下栈和队列的应用场景及区别。
答：栈和队列都是常用的数据结构，栈适合用于实现括号匹配、表达式求值等场景，而队列常用于实现广度优先搜索、缓存队列等。
栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构。
8. 什么是哈希表？它的优缺点分别是什么？答：哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构。
其优点是能够快速查找、插入、删除元素，时间复杂度接近O(1)；缺点是可能发生哈希冲突，导致性能下降。
四、综合题9. 给定以下无向图的邻接矩阵表示，请写出图的深度优先搜索（DFS）遍历路径。
```0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0```答：起始节点为0，路径：0 - 1 - 3 - 210. 写出以下树的层序遍历结果。
```1/ \2 3/ \ / \4 5 6 7```答：1 - 2 - 3 - 4 - 5 - 6 - 7以上就是数据结构考试题及答案，希望对您有所帮助。
如果有不清楚的地方，欢迎随时向老师询问。
祝您考试顺利！。
数据结构期末考试试卷及答案一、选择题（每题2分，共20分）1. 下列哪一个不是线性结构的特点？A. 有且只有一个根结点B. 每个结点最多有一个前驱和一个后继C. 有多个根结点D. 有且只有一个叶子结点答案：C2. 在单链表中，头结点的作用是（）A. 作为链表的起点B. 作为链表的终点C. 存储链表中的数据元素D. 作为链表中的第一个元素答案：A3. 在顺序表中，插入一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：B4. 下列哪种排序算法的平均时间复杂度最高？A. 冒泡排序B. 快速排序C. 直接插入排序D. 希尔排序答案：C5. 在二叉树中，具有3个结点的二叉树有（）种不同的形态。
A. 2B. 3C. 4D. 5答案：C6. 下列哪种情况不适合使用哈希表？A. 查找速度快B. 数据量较大C. 数据量较小D. 数据元素关键字分布均匀答案：C7. 在图的遍历过程中，下列哪种遍历方法属于深度优先遍历？A. 广度优先遍历B. 深度优先遍历C. 混合遍历D. 随机遍历答案：B8. 下列哪种数据结构不适用于实现栈？A. 顺序表B. 链表C. 树D. 图答案：C9. 在双向链表中，删除一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A10. 下列哪种情况不适合使用队列？A. 数据元素先进先出B. 数据元素后进先出C. 数据元素随机进出D. 数据元素按顺序进出答案：B二、填空题（每题2分，共20分）1. 线性表是具有______个数据元素的有限序列。
答案：n2. 在单链表中，每个结点包含两个域：数据域和______域。
答案：指针3. 在顺序表中，插入一个元素的时间复杂度是______。
答案：O(n)4. 快速排序的平均时间复杂度为______。
答案：O(nlogn)5. 哈希表中的冲突指的是______。
答案：不同的关键字对应同一存储位置6. 在图的遍历过程中，深度优先遍历算法使用的数据结构是______。
绪论一、填空题1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。
2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。
3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。
4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。
5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。
6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。
7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。
二、选择题1.数据的不可分割的基本单位是(D)。
A.元素B.结点C.数据类型D.数据项*2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。
A.正确B.不正确C.不确定D.无法选择3.线性结构是指数据元素之间存在一种(D)。
A.一对多关系B.多对多关系C.多对一关系D.一对一关系4.在数据结构中，从逻辑上可以把数据结构分成(A)。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构5.线性表若采用链式存储结构时，要求内存中可用存储单元的地址( D)。
A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以三、简答题1.算法的特性是什么。
答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构一、填空题1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。
2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。
3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。
4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。
5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。
6.子串的定位操作通常称做串的(模式匹配)。
7.设目标T=‘abccdcdccbaa’，模式P=‘cdcc’则第(六)次匹配成功。
8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top(--)；进栈操作时要执行的语句序列中有S->top(++)。
9.顺序表中逻辑上相邻元素的物理位置(一定)紧邻；单链表中逻辑上相邻元素的物理位置(不一定)紧邻。
10.在(循环)链表中，从任何一结点出发都能访问到表中的所有结点。
11.栈和队列均是(运算受限)的线性表，栈的特点是(先进后出后进先出)；队列的特点是(先进先出后进后出)。
12.通常，在程序中使用的串可分为串常量和串变量；而串按存储方式又可分为(定长顺序存储)和(堆分配存储)。
13.循环队列头指针front指向队头元素，队尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为Queuelen。
在循环队列中，队空标志为(front==rear)，队满标志为(（rear+1）%max==front)。
当rear>=front时，队列长度为(rear-front)，当rear<front时，队列长度为(rear-front+max)。
14.在一个长度为n的线性表中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动(n-i+1)个元素。
15.在具有n个单元的循环队列中，队满时共有(n-1)个元素。
16.带有一个头结点的单链表Head为空的条件是(Head->next==null)。
17.在一个单链表中删除指针p所指向结点的后继结点时，需要把(p->next->next)值赋给p->next指针域。
18.一个顺序循环队列存于a[M]中，假定队首和队尾指针分别为front和rear，则判断队空的条件为( ==，判断队满的条件为(（+1）%M==。
19.在双向链表中，每个结点有两个指针域，一个指向其(前驱) 结点，另一个指向其(后继)结点，最后一个结点的(后继结点)指针域为空。
*20. 若 D=((a ， (b ， c)) ， e ， a) ，则 Head( D )=( ) ，Tail( D )=( )，Head(Tail( D ))=( )。
（本人不会）21.在循环链表中，每个结点有(一个)个指针域，指向其(后继)结点，最后一个结点的指针域(为空)。
*22. 若 S=(a ， (b ， c) ， e ， d) ，则 Head( S )=( ) ，Tail( S )=( )，Head(Tail( S ))=( )。
（本人不会）二、选择题1.在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q 与p之间插入一个s所指的结点，则执行(A)。
A.s->link=p->link; p->link=s; >link=s; s->link=q;>link=s->link; s->link=p; >link=s; s->link=p;2.对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。
若在逻辑上看一个环，则队列中元素的个数(A)。
+R-F C.(R-F+1)mod n D.(n+R-F)mod n3.如下陈述中正确的是(A)。
A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串4.若让元素1，2，3依次进栈，则出栈次序不可能出现(C)的情况。
，2，1 ，1，3 ，1，2 ，3，25.判定一个队列QU（最多元素为m0）为空的条件是(C)。
>rear-QU->front==m0 >rear-QU->front-1==m0>front==QU->rear >front==QU->rear+16.设目标串S=‘abcdef’，模式串p=‘de’，则第(C)次匹配成功。
7.设字符串s1=‘ABCDEFG’，S2=‘PQRST’，T，sub1，sub2为空串。
则运算s=Concat(T ，SubString(sub1 ，s1 ， 2 ，SubLength(s2))，SubString(sub2，s1，SubLength(s2)，2)) 后的串T 值为( D)。
A.‘BCDEF’B.‘BCDEFG’C.‘BCPQRST’D.‘BCDEFEF’8.一个顺序线性表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是( B)。
9.非空的循环单链表head的尾结点（由p所指向）满足(C)。
>next==NULL ==NULL>next==head ==head10.在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时(C)。
=f->next; =r->next;=f->next; =r->next;11.在一个长度为n的线性表中，删除值为x的元素时，需要比较元素和移动元素的总次数为(C)。
A.(n+1)/2 2 +112.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改(B)个指针域的值。
13.线性结构中，每个结点(C)。
A.无直接前驱B.只有一个直接前驱和个数不受限制的直接后继C.只有一个直接前驱和后继D.有个数不受限制的直接前驱和后继14.队列是限定在(D)进行操作的线性表。
A.中间B.队头C.队尾D.端点15.设串S1=“ABCDEFG”，S2=“PQRST”，函数StrCat(x,y)返回x和y串的连接串，函数StrSub(S，i，j)返回串S的从序号i 的字符开始的j个字符组成的子串，StrLen(S)返回串S的长度，则StrCat(StrSub(S1，2，StrLen(S2))，StrSub(S1，StrLen (S2)，2))的结果串是(D)。
16.学生成绩表是一种(C)结构。
A.图形B.树形C.线性D.集合17.在一个链队中，假设f和r分别为队首和队尾指针，则插入s 所指结点的运算时(C)。
>next=s; f=s; >next=s; r=s; >next=r; r=s; >next=f;f=s;18.向顺序表中的i位置处插入元素，下面哪项能够准确的表明i的位置是合法的。
(D)<=1||i>l->length+1 >=1>=l->length+1 <=i<=l->length+119.设线性链表中结点的结构为（data，next），已知指针q所指结点是指针p所指结点的直接后继，若在*q和*p之间插入结点*s，则应执行(A)操作。
>next=p->next; p->next=s; >next=s; s->next=p;>next=s->next; s->next=p; >next==s; s->next=q;20.一个栈的入栈序列为a，b，c，d，e，则出栈序列不可能的是(C)。
21.如果以链表作为栈的存储结构，则出栈操作时(B)。
A.必须判别栈是否满B.必须判别栈是否为空C.必须判别栈元素类型D.可不做任何判断22.设有两个串p和q，求q在p中首次出现的位置的运算称为 (B)。
A.连接B.模式匹配C.求子串D.求串长指向线性链表中的某一结点，则在线性链表的表尾插入结点S的语句序列是(A)。
(p->next!=NULL) p=p->next; p->next=s; s->next=N ULL;(p!=NULL) p=p->next; p->next=s; s->next=NULL;(p->next!=NULL) p=p->next; s->next=p;p->next=NULL;(p!=NULL) p=p->next->next;->next;p->next=s;s->next=p24.向顺序栈中压入新元素时，应当(A)。
A.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D.同时进行25.假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为(D)。
f+1==r +1==f ==0 ==r26.栈的插入和删除操作在(A)进行。
A.栈顶B.栈底C.任意位置D.指定位置27.栈和队列的共同点是(C)。
