下载文档原格式
数据结构期末试题及答案一、单项选择题（每题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. 链表中，每个节点包含数据域和______。
数据结构期末考试试题及答案一、选择题（每题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. 编写一个函数，实现链表的插入操作。
数据结构期末考试复习题资料一．单项选择题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．在一棵高度为k 的满二叉树中，结点总数为（）。
A．2k-1 B．2k C．2k-1 D．⎣log 2 k ⎦+ 17.在下列存储形式中，哪一个不是树的存储形式？（）A．双亲链表表示法B．孩子链表表示法C．孩子兄弟链表表示法D．顺序存储表示法8．n 个结点的完全有向图含有边的数目为（）。
A．n*n B．n*(n+1) C．n/2 D．n*(n-1）9．n 个顶点的强连通图至少有（）条边。
A．n B．n-1 C．n+1 D．n(n-1)10、高度为k 的二叉树的最大结点数为（）。
A、2kB、2k-1C、2k–1D、2k-1–111、下列哪一种图的邻接矩阵是对称矩阵？（）A、有向图B、无向图C、AOV 网D、AOE 网12、在下列存储形式中，哪一个不是树的存储形式？（）A、双亲表示法B、孩子表示法C、孩子兄弟表示法D、顺序存储表示法13、下面哪一方法可以判断出一个有向图是否有环。
（）A、深度优先遍历B、拓扑排序C、求最短路径D、广度优先遍历14.适用于折半查找的表的存储方式及元素排列要求为（）。
A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序15、一个算法应该是（）。
A、程序B、特定问题求解步骤的描述C、要满足五个基本特性D、A 和C16、算法分析的两个主要方面是（）。
（完整版）数据结构复习题（附答案）⼀、算法设计题（每题15分，共60分）答题要求：①⽤⾃然语⾔说明所采⽤算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。
1、有⼀个带头结点的单链表，每个结点包括两个域，⼀个是整型域info，另⼀个是指向下⼀个结点的指针域next。
假设单链表已建⽴，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留⼀个。
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个⼈按顺时针⽅向围坐成⼀圈，现从第s个⼈开始按顺时针⽅向报数，数到第m个⼈出列，然后从出列的下⼀个⼈重新开始报数，数到第m的⼈⼜出列，…，如此重复直到所有的⼈全部出列为⽌。
现要求采⽤循环链表结构设计⼀个算法，模拟此过程。
4、编程实现单链表的就地逆置。
23．在数组 A[1..n]中有n个数据，试建⽴⼀个带有头结点的循环链表，头指针为h，要求链中数据从⼩到⼤排列，重复的数据在链中只保存⼀个.5、设计⼀个尽可能的⾼效算法输出单链表的倒数第K个元素。
3、假设以I和O分别表⽰⼊栈和出栈操作。
栈的初态和终态均为空，⼊栈和出栈的操作序列可表⽰为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为⾮法序列。
（15分）（1）下⾯所⽰的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出⼀个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存⼊⼀维数组中）。
5、设从键盘输⼊⼀整数的序列：a1, a2, a3，…，an,试编写算法实现：⽤栈结构存储输⼊的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（⼊栈满等）给出相应的信息。
设有⼀个背包可以放⼊的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。
数据结构期末考试题及答案一、选择题（每题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算法。
首先，构建模式字符串的前缀函数，该函数用于记录模式字符串中每个位置的最长相同前缀和后缀的长度。
“数据结构”期末考试试题一、单选题(每小题2分，共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一>next＝HL一>next;HL一>next＝p；2．n个顶点的强连通图中至少含有( )。
A.n—l条有向边B.n条有向边C.n(n—1)／2条有向边D.n(n一1)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。
A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。
A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。
A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、——和——四种。
2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。
3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。
4．在一棵高度为h的3叉树中，最多含有——结点。
5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。
7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。
一、单选题1. 从物理上可以把数据结构分为（B）两大类。
A. 动态结构、静态结构B. 顺序结构、链式结构C. 线性结构、非线性结构D. 初等结构、构造型结构2. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C ）(1≤i≤n+1)。
A. O(0)B. O(1)C. O(n)D. O(n2)3. 链表不具有的特点是（B）。
A. 插入、删除不需要移动元素B. 可随机访问任一元素C. 不必事先估计存储空间D. 所需空间与线性长度成正比4. 下列排序算法中(C)排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A. 选择B. 起泡C. 归并D. 堆5. 在下列排序算法中，哪一个算法的时间复杂度与初始排序无关（D ）。
A. 插入排序B. 起泡排序C. 快速排序D. 选择排序6. 一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素是i，则第j个输出元素是（D）。
A. i-j-1B. i-jC. j-i+1D. 不确定7. 输入序列为ABC，可以变为BCA时，经过的栈操作为（D ）。
A. push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,push,pop,push,pop,pop8. 有六个元素6 5 4 3 2 1 的顺序进栈，下列（C ）不是合法的出栈序列。
A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 69. 串的长度是指（B ）。
A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数10. 设二维数组A[1.. m,1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为( A)。
数据结构复习题及答案数据结构习题一、名词解释1.数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度。
2.线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。
3.栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。
4.树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL、哈夫曼编码。
5.图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。
6.查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。
7、排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2路归并。
一、填空题1.数据结构是研究数据的_逻辑结构__和___物理结构__，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。
算法的效率包括时间和空间两个方面，分别称为___时间复杂度____和__空间复杂度___。
2.数据的基本单元是__数据元素__，数据的最小单元是__数据项_。
3.算法是对特定问题求解___步骤___的一种描述，是指令的有限序列。
4.一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为O（n3）_。
5.一个算法具有5个特性：确定性、可行性、有穷性、输入和输出。
6.算法机能的阐发和怀抱，能够从算法的工夫庞大度和空间庞大度来评判算法的好坏。
7.数据的逻辑布局包孕调集布局、线性布局、树形布局和图型布局四品种型。
8.数据布局在计较机中的表示称为数据的物理布局，它能够采用__按次存储___或__链式存储_两种存储方法。
9.线性表有两种存储布局，划分为按次存储和链式存储。
习题一绪论习题答案1.1 1. AB2. BD3. C4. AB5. CA6. CB7. B8. D9. B 10. B1.2 1. 线性结构、树形结构、图形结构、非线性结构2. 没有、1、没有、13. 前驱、1、后续、任意多个4. 任意多个5. 一对一、一对多、多对多6. 有穷性、确定性、可行性、输入、输出7. O（m*n）8. O (n 1 2)9. O (n2)10. log3n1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。
①A．操作对象Ｂ．计算方法Ｃ．逻辑存储Ｄ．数据映象②A．结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②有限集合。
①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．逻辑结构②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成①。
A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 线性表的顺序存储结构是一种①的存储结构，线性表的链式存储结构是一种②的存储结构。
A．随机存取B．顺序存取C．索引存取D．散列存取5. 算法分析的目的是①，算法分析的两个主要方面是②。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性6. 计算机算法指的是①，它必具备输入、输出和②等五个特性。
①A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性7. 线性表的逻辑顺序与存储顺序总是一致的，这种说法①。
A. 正确B. 不正确8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址①。
A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以9. 在以下的叙述中，正确的是①。
A.线性表的线性存储结构优于链表存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式和先进后出10. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法①。
A. 正确B. 不正确1.2 填空题（将正确的答案填在相应的空中1. 数据逻辑结构包括①、②和③三种类型，树形结构和图形结构合称为④。
2. 在线性结构中，第一个结点①前驱结点，其余每个结点有且只有②个前驱结点；最后一个结点③后续结点，其余每个结点有且只有④个后续结点。
3. 在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点，叶子结点没有③结点，其余每个结点的后续结点可以④。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以①。
5. 线性结构中元素之间存在①关系，树形结构中元素之间存在②关系，图形结构中元素之间存在③关系。
6. 算法的五个重要特性是____ ____ ____ ____ ____。
7. 下面程序段的时间复杂度是①。
for (i=0;i<n;i++)for (j=0;j<m;j++)A[i][j]=0;8. 下面程序段的时间复杂度是①。
i=s=0;while (s<n){ i++; /*i=i+1*/s+=i; /*s=s+1*/}9. 下面程序段的时间复杂度是①。
s=0;for (i=0;i<n;i++)for (j=0;j<n;j++)s+=B[i][j];sum=s;10. 下面程序段的时间复杂度是①。
i=1;while (i<=n)i=i*3;1.3 算法设计题:1. 试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值.习题二顺序表示(线性表、栈和队列)习题答案2.1 1. B 2. C3. C4. A5. B6. D7. BA8. B9. C10. A 11. A 12. C 13. A 14. C2.2 1. 线性、任何、栈顶、队尾、队首 2. n-i+13. n-i4.先移动栈顶指针，后存入元素5. 先取出元素，后移动栈顶指针6.前一个位置7. 先移动队首元素，后取出元素8. n-1 9. 不可能的10. 可能的2.1 单项选择题1. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____。
A. 110B. 108C. 100D. 1202. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。
A. edcbaB. decbaC. dceabD. abcde3. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。
A. iB. n=iC. n-i+1D. 不确定4. 栈结构通常采用的两种存储结构是____。
A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构5. 判定一个栈ST（最多元素为m0）为空的条件是____。
A. ST—> top !=0B. ST—> top= =0C. ST—> top !=m0D. ST—> top= =m06. 判定一个栈ST（最多元素为m0）为栈满的条件是____。
A. ST—> top！=0B. ST—> top= =0C. ST—> top！=m0D. ST—> top= =m07. 栈的特点是____，队列的特点是____。
A. 先进先出B. 先进后8. 一个队列的入列序列是1，2，3，4，则队列的输出序列是____ 。
A. 4，3，2，1B. 1，2，3，4C. 1，4，3，2D. 3，2，4，19. 判定一个队列QU（最多元素为m0）为空的条件是____。
A.QU—>rear—QU—>front= =m0B.QU—>rear—QU—>front-1= =m0C.QU—>front= =QU—>rearD.QU—>front= =QU—>rear+110. 判定一个队列QU（最多元素为m0, m0+1= =Maxsize）为满队列的条件是____。
A.((QU—>rear-QU—>front)+ Maxsize)% Maxsize = =m0B.QU—>rear—QU—>front-1= =m0C.QU—>front= =QU—>rearD.QU—>front= =QU—>rear+111. 判定一个循环队列QU（最多元素为m0）为空的条件是____。
A.QU—>front= =QU—>rearB.QU—>front！=QU—>rearC.QU—>front= =（QU—>rear+1）%m0D.QU—>front！=（QU—>rear+1）%m012. 判定一个循环队列QU（最多元素为m0）为满队列的条件是____。
A.QU—>front= =QU—>rearB.QU—>front！=QU—>rearC.QU—>front= =（QU—>rear+1）%m0D.QU—>front！=（QU—>rear+1）%m013. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。
A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front14. 栈和队列的共同点是____。
A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点2.2 填空题（将正确的答案填在相应的空中）1.向量、栈和队列都是____结构，可以在向量的____位置插入和删除元素；对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。
2.向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动____个元素。
3.向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动____个元素。
4.向栈中压入元素的操作是____。
5.对栈进行退栈时的操作是____。
6.在一个循环队列中，队首指针指向队首元素的____。
7.从循环队列中删除一个元素时，其操作是____。
8.在具有n个单元的循环队列中，队满时共有____个元素。
9.一个栈的输入序列是12345，则栈的输出序列43512是____。
10.一个栈的输入序列是12345，则栈的输出序列12345是____。
2.3 算法设计题:设顺序表va中的数据元数递增有序。
试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2,…. a n）逆置为(a n, a n-1,…., a1)。
按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节例3—1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+E↑F习题三链表（线性表、栈和队列）习题答案3.1 1. A 2. B 3. C4. D5. C6. B7. A 9. D10. B 11.C 12. C 13.D3.2 1. 线性表 2. 双链表3. 前驱结点、后续结点4. p—＞next、s—＞data、t5. p—＞next—＞next6. head—＞next= =NULL7. p—＞next、s8. p—＞next= head9. HS= =NULL11.O(1)、O（n）3.1 单项选择题1. 不带头结点的单链表head为空的判定条件是____。
A. head= =NULLB. head—＞next= =NULLC. head—＞next= =headD. head!=NULL2. 带头结点的单链表head为空的判定条件是____。
A. head= =NULLB. head—＞next= =NULLC. head—＞next= =headD. head!=NULL3. 非空的循环单链表head的尾结点（由p所指向）满足____。
A. p—＞next= =NULLB. p= =NULLC. p—＞next= =headD. p= =head4. 在循环双链表的p所指结点之后插入s所指结点的操作是____。
