下载文档原格式
《数据结构》期末考试试题及答案一、单项选择题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. 请简要介绍树的基本概念及常见的树结构。
2012年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上可以把数据结构分为 C 。
A •动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2．数据结构在计算机内存中的表示是指A 。
A .数据的存储结构B .数据结构C.数据的逻辑结构D .数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A. 逻辑B .存储C.逻辑和存储D.物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。
A .数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。
A. 各结点的值如何B.结点个数的多少C.对数据有哪些运算 D .所用的编程语言实现这种结构是否方便。
6．以下说法正确的是D 。
A .数据项是数据的基本单位B. 数据元素是数据的最小单位C. 数据结构是带结构的数据项的集合D. —些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是C ，算法分析的两个主要方面是A 。
(1) A .找出数据结构的合理性 B .研究算法中的输入和输出的关系C.分析算法的效率以求改进C.分析算法的易读性和文档性(2) A .空间复杂度和时间复杂度B .正确性和简明性C.可读性和文档性 D .数据复杂性和程序复杂性8．下面程序段的时间复杂度是O(n2)s = 0；for ( I = 0；i v n；i + + )for (j = 0; j v n；j + + )s += B[i][j]；sum = s ；9．下面程序段的时间复杂度是O(n*m) 。
for ( i = 0；i v n；i + + )for (j = 0；j v m；j + + )A[i][j]二0；10．下面程序段的时间复杂度是O( log3n) 。
i = 0；while (i v = n)i = i * 3 ；11．在以下的叙述中，正确的是 B 。
数据结构期末考试题及答案一、单项选择题（每题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、b、c依次入栈，然后依次出栈，以下哪个序列不是可能的出栈序列？A. a, b, cB. b, a, cC. c, b, aD. b, c, a3. 哈希表的冲突可以通过哪种方式解决？A. 排序B. 链地址法C. 折半查找D. 二分查找4. 在二叉树中，以下哪个操作的时间复杂度是O(n)？A. 查找B. 插入C. 先序遍历D. 删除5. 以下哪个排序算法是稳定的？A. 快速排序B. 归并排序C. 堆排序D. 选择排序二、简答题（每题10分，共20分）1. 请简述什么是平衡二叉树，并说明其在数据结构中的重要性。
2. 解释什么是哈夫曼编码，并说明它在数据压缩中的应用。
三、算法题（每题15分，共30分）1. 编写一个函数，实现对链表的反转。
链表中的每个节点包含一个数据域和一个指向下一个节点的指针。
2. 给定一个未排序的整数数组，请编写一个函数，使用快速排序算法对其进行排序。
四、应用题（每题15分，共15分）1. 假设你正在设计一个在线购物平台的推荐系统，你需要使用数据结构来存储用户的行为数据。
请描述你将如何使用数据结构来优化推荐算法的性能。
五、编程题（每题15分，共15分）1. 编写一个程序，实现一个简单的文本编辑器，该编辑器支持插入、删除、查找和替换文本的功能。
请使用适当的数据结构来实现这些功能，并解释你的选择。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。
A nB n/2 C(n-1)/2 D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。
A s→link= p→link;p→link= s;B p→link = s; s→link = q;C p→link= s→link;s→link= p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A 求子串B 模式匹配 C串替换 D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（）的表示等价。
计算机科学与技术、网络工程本科《数据结构》期末考试试卷一、选择题〔单选题，每小题3分，共33分〕1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为。
A．BCDEAF B．ABDCEF C．DBACEF D．DABECF 2．在11个元素的有序表A[1…11]中进行折半查找〔⎣⎦2/)low+〕，查找元素(highA[11]时，被比较的元素的下标依次是。
A．6，8，10，11 B．6，9，10，11 C．6，7，9，11 D．6，8，9，113．由元素序列〔27，16，75，38，51〕构造平衡二叉树，则首次出现的最小不平衡子树的根〔即离插入结点最近且平衡因子的绝对值为2的结点〕为。
A．27 B．38 C．51 D．754．利用逐点插入法建立序列〔50，72，43，85，75，20，35，45，65，30〕对应的二叉排序树以后，查找元素30要进行次元素间的比较。
A．4 B．5 C．6 D．75．循环链表的主要优点是。
A．不再需要头指针了B．已知某个结点的位置后，很容易找到它的直接前驱结点C．在进行删除后，能保证链表不断开D．从表中任一结点出发都能遍历整个链表6．已知一个线性表〔38，25，74，63，52，48〕，假定采用散列函数h〔key〕=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为。
A．1．5 B．1．7 C．2．0 D．2．37．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。
A．23 B．37 C．44 D．468．在最好和最坏情况下的时间复杂度均为O〔nlogn〕且稳定的排序方法是。
A．基数排序B．快速排序C．堆排序D．归并排序9．无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，〔a，e〕，(a，c)，〔b，e〕，〔c，f〕，(f，d)，〔e，d〕}。
数据结构期末考试题及答案一、选择题（每题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分，共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. 请简要说明栈的应用场景，并给出一个具体实例。
《数据结构》试题（A卷）（考试时间：90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。
A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。
据的存3.4.5.6.7.8.A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链式存储，不必占用一片连续的存储单元。
D.线性表采用链式存储，便于插入和删除操作。
9.队列操作的原则是（）。
A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。
A.栈首B.栈尾C.栈顶D.栈底11．假设以数组A[n]存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（）。
A．（rear-front+n）%nB.rear-front+1C.(front-rear+n)%nD.(rear-front)%n12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（）。
13.构。
14.15.12在q3．放了2个字符。
4．广义表（a,b,c,d）的表尾是。
5．一棵深度为k的二叉树，最多有个结点。
6．已知有向图G=（V，E），其中:V={v1,v2,v3,v4,v5,v6,v7},E={<v1,v2>,<v1,v3>,<v1,v4>,<v2,v5>,<v3,v5>,<v3,v6>,<v4,v6>,<v5,v7>,<v6,v7>},则G的拓扑序列是______。
7.有n个顶点的连通图至少有条边。
8.1.（）23.4（）5.6.7.8.9.（）10.采用线性探测法解决冲突问题，所产生的一系列后继散列地址必须大于等于原散列址。
数据结构期末考试试题(含答案)题目一请写出快速排序算法的递归实现。
解答一public class QuickSort {public void sort(int[] arr, int low, int high) {if (low < high) {int partitionIndex = partition(arr, low, high);sort(arr, low, partitionIndex - 1);sort(arr, partitionIndex + 1, high);}}private int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}题目二请解释什么是二叉搜索树，并给出一个例子。
解答二二叉搜索树是一种有序的二叉树，其中每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值。
下面是一个二叉搜索树的例子：6/ \3 9/ \ \1 4 12题目三请写出深度优先搜索(DFS)算法的递归实现。
解答三import java.util.*;public class DFS {private int numVertices;private List<List<Integer>> adjList;public DFS(int numVertices) {this.numVertices = numVertices;adjList = new ArrayList<>();for (int i = 0; i < numVertices; i++) {adjList.add(new ArrayList<>());}}public void addEdge(int src, int dest) { adjList.get(src).add(dest);}public void DFSUtil(int start, boolean[] visited) { visited[start] = true;System.out.print(start + " ");List<Integer> neighbors = adjList.get(start);for (int neighbor : neighbors) {if (!visited[neighbor]) {DFSUtil(neighbor, visited);}}}public void DFS(int start) {boolean[] visited = new boolean[numVertices];DFSUtil(start, visited);}}以上是数据结构期末考试试题及其答案。
2012年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上可以把数据结构分为 C 。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。
A．数据的存储结构B．数据结构C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C 。
A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。
6．以下说法正确的是 D 。
A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。
（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O（n2）。
s ＝0；for（ I ＝0； i＜n； i＋＋）for（j＝0；j＜n；j＋＋）s ＋＝B[i][j]；sum ＝ s ；9．下面程序段的时间复杂度是O（n*m）。
for（ i ＝0； i＜n； i＋＋）for（j＝0；j＜m；j＋＋）A[i][j] ＝ 0；10．下面程序段的时间复杂度是O（log3n）。
i ＝ 0；while（i＜＝n）i ＝ i * 3；11．在以下的叙述中，正确的是 B 。
A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出（先进后出）D．队列的操作方式是先进后出（先进先出，尾进首出）12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。
A．数据元素具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等13．链表不具备的特点是 A 。
（顺序表是随机访问的，只要知道首元素的地址，就可以知道任意的第i个元素的地址）A．可随机访问任一结点B．插入删除不需要移动元素C．不必事先估计存储空间D．所需空间与其长度成正比14．不带头结点的单链表head为空的判定条件是 A 。
A head==NULLB head->next ＝＝NULLC．head－＞next ＝＝head D head！＝NULL15．带头结点的单链表head为空的判定条件是 B 。
A head==NULLB head->next ＝＝NULLC．head－＞next ＝＝head D head！＝NULL16．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。
A．单链表 B．给出表头指针的单循环链表C．双链表 D．带头结点的双循环链表17．需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。
A．单链表 B．静态链表C．线性链表 D．顺序存储结构（需要移动元素）动态链表不需要分配很大的空间，如果空间不足够，可以申请空间，静态链表只能使用初始化时候的空间，不能够追加空间18．非空的循环单链表head的尾结点（由p所指向）满足 C 。
A．p－＞next ＝＝ NULL B．p ＝＝ NULLC．p－＞next ＝＝head D．p ＝＝ head19．在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。
P->prior->next=s;S-prior=p->prior;S->next=p;P->prior=s;A．p－＞prior－＞priorB．p－＞prior－＞priorC．s－＞prior－＞next ＝ sD．s－＞prior－＞prior ＝ s20．如果最常用的操作是取第i个结点及其前驱，则采用 D 存储方式最节省时间。
A．单链表 B．双链表C．单循环链表D．顺序表21．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B 。
A．O（1） B．O（n）C．O（n2）D．O（nlog2n）22．在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行 B 操作与链表的长度有关。
A．删除单链表中的第一个元素B．删除单链表中的最后一个元素C．在单链表第一个元素前插入一个新元素D．在单链表最后一个元素后插入一个新元素23．与单链表相比，双链表的优点之一是 D 。
A．插入、删除操作更简单B．可以进行随机访问C．可以省略表头指针或表尾指针D．顺序访问相邻结点更灵活24．如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用 B 。
A．只有表头指针没有表尾指针的循环单链表B．只有表尾指针没有表头指针的循环单链表C．非循环双链表D．循环双链表25．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n＋1），元素的移动次数为： A 。
A．n – i ＋ 1 B．n – i C．i D．i –126．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为C 。
A．顺序表 B．用头指针表示的循环单链表C．用尾指针表示的循环单链表 D．单链表27．下述哪一条是顺序存储结构的优点? C 。
A插入运算方便 B可方便地用于各种逻辑结构的存储表示C存储密度大 D删除运算方便（需要移动元素）28．下面关于线性表的叙述中，错误的是哪一个? B 。
A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作。
C线性表采用链式存储，不必占用一片连续的存储单元D线性表采用链式存储，便于进行插入和删除操作。
29．线性表是具有n个 B 的有限序列。
A．字符B．数据元素 C．数据项D．表元素30．在n个结点的线性表的数组（顺序表）实现中，算法的时间复杂度是O （1）的操作是 A 。
A．访问第i（1＜＝i＜＝n）个结点和求第i个结点的直接前驱（1＜i＜＝n）B．在第i（1＜＝i＜＝n）个结点后插入一个新结点C．删除第i（1＜＝i＜＝n）个结点D．以上都不对31．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为C。
A．O（0） B．O（1）C．O（n）D．O（n2）32．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为C 。
（增加一个元素需要平均移动n/2个元素，删除一个元素需要平均移动n-1/2个元素）A．O（n） O（n） B．O（n） O（1）C．O（1） O（n）D．O （1） O（1）33．线性表（a1，a2，… ，an）以链式方式存储，访问第i位置元素的时间复杂度为 C 。
A．O（0） B．O（1）C．O（n）D．O（n2）34．单链表中，增加一个头结点的目的是为了 C 。
A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方便运算的实现 D．说明单链表是线性表的链式存储35．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是B 。
S->next=p->next;P->next=s;A．p－＞next＝p－＞next＝p－＞next＝s；C．p－＞next＝s－＞next＝s－＞next；p－＞next＝s36．线性表的顺序存储结构是一种 A 。
A．随机存取的存储结构B．顺序存取的存储结构C．索引存取的存储结构D．Hash存取的存储结构37．栈的特点是 B ，队列的特点是 A 。
A．先进先出 B．先进后出38．栈和队列的共同点是 C 。
A．都是先进后出 B．都是先进先出C．只允许在端点处插入和删除元素 D．没有共同点39．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。
A．edcba B．decba C．dceab D．abcde40．设有一个栈，元素依次进栈的顺序为A、B、C、D、E。
下列 C 是不可能的出栈序列。
A．A，B，C，D，E B．B，C，D，E，A C．E，A，B，C，D D．E，D，C，B，A41．以下 B 不是队列的基本运算?（队列只能队列尾插入，队列头删除）A．从队尾插入一个新元素B．从队列中删除第i个元素C．判断一个队列是否为空D．读取队头元素的值42．若已知一个栈的进栈序列是1，2，3，，n，其输出序列为p1，p2，p3，…，pn，若p1＝n，则pi为 C 。
A．i B．n－i C．n－i＋1 D．不确定43．判定一个顺序栈st（最多元素为MaxSize）为空的条件是 B 。
A．st－＞top ！top ＝＝－1C．st－＞top ！top ＝＝MaxSize44．判定一个顺序栈st（最多元素为MaxSize）为满的条件是 D 。
A．st－＞top ！top ＝＝－1C．st－＞top ！top ＝＝MaxSize45．一个队列的入队序列是1，2，3，4，则队列的输出序列是 B 。
A．4，3，2，1 B．1，2，3，4C．1，4，3，2 D．3，2，4，146．判定一个循环队列qu（最多元素为MaxSize）为空的条件是 C 。
A．qu－＞rear – qu－＞rear – qu－＞front －1＝＝MaxSizeC．qu－＞front==qu->rearfront －147．在循环队列中，若front与rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是 C 。
A．front＝＝rear＋1 B．rear＝＝front＋1 C．front＝＝rear D．front＝＝048．向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行 D 操作。
（链栈的操作和链表类似）A．h－＞next＝h ；C．s－＞next＝h－＞next＝s ；49．输入序列为ABC，可以变为CBA时，经过的栈操作为 B 。
A．push，pop，push，pop，push，pop B．push，push，push，pop， pop，popC．push，push，pop， pop，push，pop D．push，pop，push，push，pop， pop （push是压栈的意思，pop是弹出栈的意思）50．若栈采用顺序存储方式存储，现两栈共享空间V[1 m]，top[1]、top[2]分别代表第1和第2个栈的栈顶，栈1的底在V[1]，栈2的底在V[m]，则栈满的条件是 B 。
