下载文档原格式
数据结构期末试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构和链式存储结构的主要区别在于：A. 数据元素的存储关系B. 数据元素的存储空间C. 数据元素的存储顺序D. 数据元素的存储位置答案：A2. 下列关于栈的描述中，错误的是：A. 栈是一种后进先出（LIFO）的数据结构B. 栈只能进行插入和删除操作C. 栈顶元素可以被访问D. 栈可以进行顺序存储和链式存储答案：B3. 在二叉树的遍历算法中，不使用递归算法的遍历方式是：A. 前序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：D4. 哈希表的冲突解决方法中，不包括以下哪种：A. 开放定址法B. 链地址法C. 线性探测法D. 排序法答案：D5. 在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于：A. 搜索的顺序B. 存储结构C. 遍历的深度D. 遍历的宽度答案：A6. 快速排序算法的时间复杂度最坏情况下为：A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C7. 下列关于二叉搜索树的描述中，正确的是：A. 每个节点的左子树只包含小于该节点的键值B. 每个节点的右子树只包含大于该节点的键值C. 以上两个选项都正确D. 以上两个选项都不正确答案：C8. 在非递归的二叉树遍历算法中，通常需要使用的数据结构是：A. 栈B. 队列C. 链表D. 数组答案：A9. 一个有n个顶点的无向图，其边数最多为：A. nB. n(n-1)/2C. n(n+1)/2D. n^2答案：B10. 一个长度为n的数组进行归并排序时，需要的辅助空间大小为：A. O(1)B. O(n)C. O(nlogn)D. O(n^2)答案：B二、填空题（每题2分，共10分）1. 在数据结构中，______是一种特殊的线性表，它的元素个数是固定的。
答案：数组2. 链表中，每个节点包含数据域和______。
数据结构c语言期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构和非线性结构的区别在于（）。
A. 结构中元素的个数B. 结构中是否包含子结构C. 结构中元素之间是否有一对一关系D. 结构中元素之间是否有一对多关系答案：C2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。
A. 存储密度高B. 存储密度低C. 插入和删除操作快D. 存储空间可以动态分配答案：A3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数为（）。
A. i-1B. n-iC. n-i+1D. n-i-1答案：B4. 栈的运算遵循（）原则。
A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：C5. 在二叉树的前序遍历中，访问顺序为（）。
A. 根-左-右B. 左-根-右C. 左-右-根D. 右-左-根答案：A6. 哈希表的冲突解决方法中，链地址法是（）。
A. 将所有元素存储在同一个存储单元B. 将所有元素存储在同一个链表中C. 将所有元素存储在同一个数组中D. 将所有元素存储在同一个链表的同一个位置答案：B7. 在图的遍历中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。
A. 遍历的顺序不同B. 遍历的起点不同C. 遍历的路径不同D. 遍历使用的存储结构不同答案：D8. 快速排序算法的时间复杂度为（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B9. 归并排序算法的时间复杂度为（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B10. 在二叉搜索树中，查找一个元素的时间复杂度为（）。
A. O(n)B. O(logn)C. O(n^2)D. O(1)答案：B二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的时间复杂度通常用______来描述。
答案：大O符号2. 线性表的两种基本操作是插入和______。
数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 执行算法所需要的计算工作量B. 执行算法所需要的存储空间C. 执行算法所需要的时间D. 执行算法所需要的内存大小答案：A2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。
A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态分配D. 存储空间利用率高答案：B3. 栈的基本运算中，不包括（）。
A. 入栈B. 出栈C. 取栈顶元素D. 排序答案：D4. 在二叉树的遍历中，先序遍历的顺序是（）。
A. 先根后子B. 先子后根C. 先左后右D. 先右后左答案：A5. 哈希表解决冲突的方法不包括（）。
A. 分离链接法B. 线性探测法C. 链地址法D. 二分查找法答案：D6. 一个图的邻接矩阵表示法中，若第i行第j列的元素为1，则表示（）。
A. 顶点i和顶点j之间有一条边B. 顶点i和顶点j之间没有边C. 顶点i和顶点j之间有n条边D. 顶点i和顶点j之间有m条边答案：A7. 在查找算法中，二分查找法适用于（）。
A. 线性表B. 哈希表C. 树形结构D. 图结构答案：A8. 快速排序算法的时间复杂度在最坏情况下是（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C9. 一个有n个顶点的无向图，其边数最多为（）。
A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B10. 以下哪个不是排序算法（）。
A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序答案：D二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的空间复杂度是指算法执行过程中所需要的___________。
答案：存储空间2. 线性表的链式存储结构中，每个节点包含___________和___________。
答案：数据元素，指针3. 栈的特点是___________，___________。
数据结构期末考试试题及答案一、选择题（每题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. 网络流2. 下面哪个数据结构用于实现广度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆3. 下面哪个数据结构用于实现深度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆4. 下面哪个数据结构用于实现快速排序算法？A. 栈B. 队列C. 散列表D. 堆5. 下面哪个数据结构用于实现优先队列？A. 栈B. 队列C. 散列表D. 堆6. 下面哪个数据结构用于实现哈希表？A. 栈B. 队列C. 散列表D. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。
2. 二叉树的节点最多有______个子节点。
3. 堆是一种特殊的______。
4. 散列表的查找效率取决于______。
5. 图的遍历算法包括______和______。
6. 快速排序算法的平均时间复杂度为______。
7. 哈希表中的冲突解决方法有______和______。
8. 最小树算法包括______和______。
9. 最短路径算法包括______和______。
10. 并查集算法用于解决______问题。
第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。
2. 请简述二叉搜索树的特点。
3. 请简述哈希表的原理。
4. 请简述图的深度优先搜索算法。
5. 请简述最小树算法的原理。
第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。
《数据结构》期末考试试卷试题及答案一、选择题（每题5分，共20分）1. 下列哪个不是线性结构？A. 栈B. 队列C. 图D. 数组2. 下列哪个不是栈的基本操作？A. 入栈B. 出栈C. 查找D. 判断栈空3. 下列哪个不是队列的基本操作？A. 入队B. 出队C. 查找D. 判断队列空4. 下列哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 环二、填空题（每题5分，共20分）5. 栈是一种______结构的线性表，队列是一种______结构的线性表。
6. 图的顶点集记为V(G)，边集记为E(G)，则无向图G=(V(G),E(G))，有向图G=(______，______)。
7. 树的根结点的度为______，度为0的结点称为______。
8. 在二叉树中，一个结点的左子结点是指______的结点，右子结点是指______的结点。
三、简答题（每题10分，共30分）9. 简述线性表、栈、队列、图、树、二叉树的基本概念。
10. 简述二叉树的遍历方法。
11. 简述图的存储结构及其特点。
四、算法题（每题15分，共30分）12. 编写一个算法，实现栈的入栈操作。
13. 编写一个算法，实现队列的出队操作。
五、综合题（每题20分，共40分）14. 已知一个无向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<4,5>}，画出图G，并给出图G的邻接矩阵。
15. 已知一个二叉树，其前序遍历序列为ABDCE，中序遍历序列为DBACE，请画出该二叉树，并给出其后序遍历序列。
答案部分一、选择题答案1. C2. C3. C4. D二、填空题答案5. 后进先出先进先出6. V(G),E(G)7. 0 叶结点8. 左孩子右孩子三、简答题答案9. （1）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。
数据结构期末考试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么数据结构来实现？A. 链表B. 数组C. 栈D. 队列答案：B2. 以下哪个是二叉树的性质？A. 每个节点最多有两个孩子B. 每个节点最多有三个孩子C. 每个节点最多有四个孩子D. 每个节点最多有五个孩子答案：A3. 在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的区别是什么？A. DFS使用队列，BFS使用栈B. DFS使用栈，BFS使用队列C. DFS和BFS都使用栈D. DFS和BFS都使用队列答案：B...20. 以下哪个排序算法的时间复杂度为O(n^2)？A. 冒泡排序B. 选择排序C. 插入排序D. 所有上述排序算法答案：D二、简答题（每题10分，共30分）1. 简述链表和数组的区别。
答案：链表和数组都是用来存储数据的线性数据结构。
数组是连续的内存空间，可以随机访问，但插入和删除操作效率较低；链表由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针，不支持随机访问，但插入和删除操作较为高效。
2. 什么是递归？请给出一个递归算法的例子。
答案：递归是一种算法设计技术，它允许函数调用自身来解决问题。
递归通常包含基本情况和递归情况。
例如，计算阶乘的递归算法：f(n) = n * f(n-1)，其中基本情况是f(1) = 1。
...三、算法设计题（每题25分，共50分）1. 给定一个整数数组，请设计一个算法找出数组中的第k大元素。
答案：可以采用快速选择算法，类似于快速排序的划分过程，通过随机选择一个元素作为基准，将数组分为两部分，一部分包含比基准大的元素，另一部分包含比基准小的元素。
然后根据k与基准元素的位置关系，决定是继续在左侧子数组还是右侧子数组中进行查找。
2. 描述如何使用哈希表解决字符串匹配问题。
答案：哈希表可以用于实现字符串匹配的KMP算法。
首先，构建模式字符串的前缀函数，该函数用于记录模式字符串中每个位置的最长相同前缀和后缀的长度。
数据结构复习题（课程代码 252259）一、填空题（本大题共40小题）1.队列中是按照______先进先出______的原则进行数据元素的增删。
2.___栈__又称为LIFO表。
3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为___2i+1___。
4.存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。
5.在串S=“structure”中，以r为首字符的子串有_9_个。
6.设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[1][1]的地址是___208____。
7.在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n个顶点的有向完全图中，包含有__ n(n-1)______条边。
8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____（12，40）（）（74）（23,55，63）____。
9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____增加1______。
10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，整个堆排序过程的时间复杂度为__ O(nlog2n)______。
11.在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。
12.一棵深度为5的满二叉树中的结点数为_______31_______个。
13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。
14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子树____查找。
15._____拓朴排序______可以判断出一个有向图中是否有环。
数据结构期末考试题及答案一、选择题（每题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、二叉树的深度为k，则二叉树最多有（ C ）个结点。
A. 2kB. 2k-1C. 2k-1D. 2k-12、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。
A. R[2i-1]B. R[2i+1]C. R[2i]D. R[2/i]3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。
A. a在b的右方B. a在b的左方C. a是b的祖先D. a是b的子孙4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。
A. adbceB. decabC. debacD. abcde5、在一棵具有5层的满二叉树中结点总数为（ A ）。
A. 31B. 32C. 33D. 166、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。
A. 能B. 不能7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。
A. 3B. 2C. 4D. 58、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。
A. 67B. 68C. 69D. 709、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。
A. 98B. 99C. 50D. 4810、表达式a*(b+c)-d的后缀表达式是（ B ）。
A. abcd+-B. abc+*d-C. abc*+d-D. -+*abcd11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。
A. DBFEACB. DFEBCAC. BDFECAD. BDEFAC12、树最适合用来表示（ C ）。
A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ）A. A*B+C/D-E+FB. AB*C+D/E-F+C. ABC+*DE-F+/D. ABCDED*+/-+14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。
A. 不发生改变B. 发生改变C. 不能确定D. 以上都不对15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。
A. 15B. 16C. 17D. 4716、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。
A. 51B. 23C. 53D. 74二、判断题（ ）1、存在这样的二叉树，对它采用任何次序的遍历，结果相同。
（ ）2、中序遍历一棵二叉排序树的结点，可得到排好序的结点序列。
（ ）3、对于任意非空二叉树，要设计其后序遍历的非递归算法而不使用堆栈结构，最适合的方法是对该二叉树采用三叉链表。
（ ）4、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。
（ T ）5、一个含有n 个结点的完全二叉树，它的高度是⎣log 2n ⎦＋1。
（ T ）6、完全二叉树的某结点若无左孩子，则它必是叶结点。
三、填空题1、具有n 个结点的完全二叉树的深度是 ⎣log 2n ⎦+1 。
2、哈夫曼树是其树的带权路径长度 最小 的二叉树。
3、在一棵二叉树中，度为0的结点的个数是n0，度为2的结点的个数为n2，则有 n0= N2+1 。
4、树内各结点度的 最大值 称为树的度。
四、综合题1、假设用于通讯的电文仅由8个字母A 、B 、C 、D 、E 、F 、G 、H 组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
请为这8个字母设计哈夫曼编码。
65111932623032381001710721A H C F D B E G 00011100001111 A 000B 101C 10000D 1001E 11F 10001G 01H 0012、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL 。
215611187341230WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=693、已知一棵二叉树的先序序列：ABDGJEHCFIKL ；中序序列：DJGBEHACKILF 。
画出二叉树的形态。
AL K I H F C E J GD B数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的① 、数据信息在计算机中的② 以及一组相关的运算等的课程。
① A ．操作对象 Ｂ．计算方法 Ｃ．逻辑结构 Ｄ．数据映象② A ．存储结构 Ｂ．关系 Ｃ．运算 Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D ，R ），其中D 是① 的有限集合，R 是D 上的② 有限集合。
① A ．算法 Ｂ．数据元素 Ｃ．数据操作 Ｄ．数据对象② A ．操作 Ｂ．映象 Ｃ．存储 Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成 。
A ．动态结构和静态结构 Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构 Ｄ．内部结构和外部结构4. 算法分析的目的是① ，算法分析的两个主要方面是② 。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是① ，它必具备输入、输出和② 等五个特性。
① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括 、 和 三种类型，树形结构和图形结构合称为 。
2. 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。
3. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以 。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。
5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。
7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。
for (i=0;i<n;i++)for (j=0;j<n; j++)A[i][j]=0;8. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。
for (i=0;i<n;i++)for (j=0; j<i; j++)A[i][j]=0;9. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。
s=0;for (i=0;i<n;i++)for (j=0;j<n;j++)for (k=0;k<n;k++)s=s+B[i][j][k];sum=s;10. 分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是__ __。
i=s=0;while (s<n){ i++;s+=i; //s=s+i}11. 分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是__ __。
i=1;while (i<=n)i=i*2;1.3 算法设计题1.试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值.2.试写一算法,求出n个数据中的最大值。
写出最大语句频度，该算法的时间复杂度。
习题答案1.1 1. C , A2. B,D3. C4. C, A5. C,B1.2 1. 线性结构、树形结构、图形结构，非线性结构2. 没有、1、没有、13. 前驱、1、后续、任意多个4. 任意多个5. 一对一、一对多、多对多6. 有穷性、确定性、可行性、输入、输出7. 最大语句频度：n2，时间复杂度：. O (n2)8. 最大语句频度：n (n+1)/2 ，时间复杂度：. O (n2)9. 最大语句频度：n3，时间复杂度：. O (n3)10. 最大语句频度：n，时间复杂度：. O (n)11. 最大语句频度：log2n，时间复杂度：. O (log2n )习题2 线性表2.1 单项选择题1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是__ __。
A. 110B. 108C. 100D. 1202. 线性表的顺序存储结构是一种__ _的存储结构，而链式存储结构是一种__ _的存储结构。
A．随机存取 B．索引存取 C．顺序存取 D．散列存取3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法__ _。
A. 正确B. 不正确4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址__ _。
A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以5. 在以下的叙述中，正确的是__ _。
A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构6. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法__ _。
A. 正确B. 不正确7. 不带头结点的单链表head为空的判定条件是____。
A. head= =NULLB. head->next= =NULLC. head->next= =headD. head!=NULL8. 带头结点的单链表head为空的判定条件是____。
A. head= =NULLB. head->next= =NULLC. head->next= =headD. head!=NULL9. 非空的循环单链表head的尾结点（由p所指向）满足____。
A. p->next= =NULLB. p= =NULLC. p->next= =headD. p= =head10. 在双向循环链表的p所指结点之后插入s所指结点的操作是____。
