下载文档原格式
一、单项选择题（本大题共71小题，每小题2分，共142分）1、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。
（）A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}标准答案：C2、广义表（（a）,a）的表头是（）。
（）A．aB．bC．(a)D．((a))标准答案：C3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（）。
（）A．80B．100C．240D．270标准答案：C4、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。
（）A．HL=p；p->next=HL；B．p->next=HL；HL=p；C．p->next=HL；p=HL；D．p->next=HL->next；HL->next=p；标准答案：B5、一个具有n个顶点的无向完全图的边数为（）。
（）A．(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)标准答案：B6、如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。
下列选项中，（）就是不稳定的排序方法。
（）A．起泡排序B．归并排序C．直接插入法排序D．简单选择排序标准答案：D7、按照二叉树的定义，具有3个结点的二叉树有（）种。
（）A．3B．4C．5D．6标准答案：C8、设有1000个元素，用二分法查找时，最大比较次数是（）。
（）A．1B．7C．10D．25标准答案：C9、树适合用来表示（）。
（）A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据标准答案：C10、设有两个串p和q，求p在q中首次出现的位置的运算称作（）。
数据结构试题集(包含答案-完整版)数据结构试题集（包含答案-完整版）1. 单选题1) 数据结构是一种（）。
a) 存储结构b) 算法c) 数据模型d) 网络答案：c) 数据模型解析：数据结构是一种用于组织和存储数据的方式，描述了数据之间的关系以及对数据的操作。
2) 以下哪种数据结构可以通过索引直接访问元素？a) 链表b) 队列c) 栈d) 数组答案：d) 数组解析：数组是一种线性数据结构，可以通过索引直接访问指定位置的元素。
2. 多选题1) 哪些数据结构属于非线性结构？（）a) 队列b) 树c) 栈d) 图答案：b) 树d) 图解析：线性结构中的元素存在一对一的关系，非线性结构中的元素存在一对多或多对多的关系，树和图属于非线性结构。
2) 下列哪些操作可以在栈上进行？（）a) 入栈b) 出栈c) 查找d) 删除答案：a) 入栈b) 出栈解析：栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
3. 简答题1) 请简要介绍线性表和非线性表。
答案：线性表是数据元素的一个有限序列，元素之间存在一对一的关系。
非线性表是指元素之间存在一对多或多对多的关系，如树和图。
2) 请解释什么是时间复杂度和空间复杂度。
答案：时间复杂度是衡量算法执行效率的度量，表示算法的运行时间随输入规模增长的速度。
空间复杂度是指算法执行过程中所需的存储空间随输入规模增长的速度。
4. 编程题题目：实现一个栈，包含push、pop和getMin三个操作，要求时间复杂度为O(1)。
答案：class MinStack:def __init__(self):self.stack = []self.min_stack = []def push(self, x):self.stack.append(x)if not self.min_stack or x <= self.min_stack[-1]:self.min_stack.append(x)def pop(self):if self.stack.pop() == self.min_stack[-1]:self.min_stack.pop()def getMin(self):return self.min_stack[-1]解析：在栈的基础上，使用一个辅助栈min_stack来记录当前栈中的最小值。
《数据结构》题库及答案一、选择题1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。
a. 随机存储；b.顺序存储；c. 索引存取；d. HASH 存取2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。
a. edcba;b. decba;c. dceab;d.abcde3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。
a. 4,3,2,1;b. 1,2,3,4;c. 1,4,3,2;d.3,2,4,14．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。
a. s->nxet=p->next; p->next=s;b. p->next=s->next; s->next=p;c. q->next=s; s->next=p;d. p->next=s; s->next=q;5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。
a.联接b.模式匹配c.求子串d.求串长6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。
a. 90b.180c.240d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。
a. p->lch==NULLb. p->ltag==1c. p->ltag==1且p->lch=NULLd. 以上都不对8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______A 、（A ，B ，C ，D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ）9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。
第一章绪论一．单项选择题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．在定义ADT时，除数据对象和数据关系外，还需说明_______。
A. 数据元素B. 算法C. 基本操作D. 数据项7．计算算法的时间复杂度是属于一种_______。
A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法8．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_______。
A. n2B. nlognC. nD. logn9．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_______。
A. O(1)B. O(n)C. O(200n)D. O(nlog2n)10．有如下递归函数fact(a)，其时间复杂度为_________。
int fact(int a){if(n==0)retrun 1;elsereturn(n*fact(n-1));}A. O(n)B. O(n2)C. O(n3)D. O(n4)11．线性表若采用链式存储结构时，要求内存中可用存储单元的地址_______。
数据结构考试试题题库一、选择题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. 解释什么是递归，并给出一个使用递归解决实际问题的例子。
结束语数据结构的学习不仅仅是对概念的理解，更重要的是能够将这些概念应用到实际问题的解决中。
通过本题库的练习，希望能够加深你对数据结构的理解和应用能力。
请注意，这只是一个示例题库，实际的考试题库可能会包含更多的题目和不同的题型。
考生应根据具体的课程内容和考试要求来准备。
数据结构题库及答案详解一、选择题1. 在数据结构中，线性结构的特点是什么？A. 结构中存在唯一的开始结点和终端结点B. 结构中所有结点的前驱和后继都存在C. 结构中所有结点都只有一个直接前驱和一个直接后继D. 结构中存在多个开始结点和终端结点答案：C2. 栈是一种特殊的线性表，其特点是：A. 先进先出B. 先进后出C. 可以同时在两端进行插入和删除操作D. 只能在一端进行插入和删除操作答案：D3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根结点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根结点，最后遍历右子树C. 先遍历右子树，然后访问根结点，最后遍历左子树D. 先遍历左右子树，最后访问根结点答案：A二、填空题4. 在图的遍历中，______算法可以避免重复访问同一顶点。
5. 哈希表的冲突可以通过______方法来解决。
答案：4. 深度优先搜索（DFS）5. 链地址法或开放地址法三、简答题6. 简述排序算法中的快速排序算法的基本原理。
答案：快速排序算法是一种分治算法，它通过选择一个元素作为“基准”，然后将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。
然后对这两个子数组递归地应用快速排序算法。
7. 解释什么是递归，并给出一个递归函数的例子。
答案：递归是一种在函数中调用自身的编程技术。
递归函数必须有一个明确的终止条件，以避免无限递归。
例如，计算阶乘的递归函数如下：```int factorial(int n) {if (n == 0) return 1; // 终止条件return n * factorial(n - 1); // 递归调用}```四、编程题8. 编写一个函数，实现单链表的反转。
答案：```c// 假设ListNode是链表节点的定义ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;ListNode* next = NULL;while (curr != NULL) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转指针prev = curr; // 移动prevcurr = next; // 移动curr}return prev; // 新的头节点}```9. 给定一个整数数组，请实现一个函数来找到数组中的最长连续子序列的长度。
数据结构试题库及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用（）来存储。
A. 链表B. 栈C. 队列D. 数组答案：D2. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序答案：C3. 在二叉树的遍历算法中，先访问根节点，然后遍历左子树，最后遍历右子树的遍历方式是（）。
A. 先序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：A4. 哈希表的冲突解决方法不包括以下哪种？A. 链地址法B. 线性探测法C. 二分查找法D. 再散列法答案：C5. 在图的遍历算法中，广度优先搜索（BFS）使用的辅助数据结构是（）。
A. 栈B. 队列C. 堆D. 链表答案：B6. 下列关于堆的描述中，错误的是（）。
A. 堆是一种特殊的完全二叉树B. 堆中的每个节点的值都大于其子节点的值C. 堆可以用于实现优先队列D. 堆的插入操作的时间复杂度为O(log n)答案：B7. 在一个长度为n的数组中，使用二分查找算法查找一个元素的最坏情况下的时间复杂度是（）。
A. O(1)B. O(n)C. O(n^2)D. O(log n)答案：D8. 以下哪个数据结构不是线性结构？A. 链表B. 栈C. 队列D. 二叉树答案：D9. 以下哪个算法是动态查找表？A. 直接索引B. 顺序查找C. 二分查找D. 哈希表答案：D10. 在图的表示方法中，邻接矩阵表示法的缺点是（）。
A. 占用空间大B. 占用空间小C. 插入和删除操作复杂D. 遍历操作复杂答案：A二、填空题（每题2分，共20分）1. 在一个长度为n的数组中，使用顺序查找算法查找一个元素的时间复杂度为________。
答案：O(n)2. 一个具有n个节点的完全二叉树的高度为________。
答案：log2(n) + 1（向上取整）3. 一个长度为n的链表，删除一个节点的时间复杂度为________。
答案：O(1)4. 在图的表示方法中，邻接表表示法的缺点是________。
第 1 章 绪论一、选择题1. 算法的计算量的大小称为计算的（ ）。
【北京邮电大学 2000 二、 3( 20/8 分） 】A . 效 率B.复杂性C.现实性 D. 难度2. 算法的时间复杂度取决于（ ）【 中科院计算所 1998 二、 1（ 2 分）】A.问题的规模B. 待处理数据的初态C. A 和 B3. 计算机算法指的是（ 1），它必须具备（ 2） 这三个特性。
（1） A ．计算方法 B. 排序方法 C. 解决问题的步骤序 列 D. 调度方法（2） A ．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全 性B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 误的 6.下面说法错误的是（）【南京理工大学 2000 一、 2 （1.5 分）】（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模 n 下，复杂度0（n ）的算法在时间上总是优于复杂度 0（2"）的算法（ 3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（ 4）同一个算法，实现语言的级别越高，执行效率就越低A . （1） B.（1）,（2）7. 从逻辑上可以把数据结构分为（ 4（ 2 分）】A .动态结构、静态结构 C.线性结构、非线性结构 8. 以下与数据的存储结构无关的术语是（ 分）】A . 循 环 队 列 表 D. 栈9. 以下数据结构中，哪一个是线性结构（ 分）】A . 广 义 表C.（1）,（4）D.（3））两大类。
【武汉交通科技大学 1996 B.顺序结构、链式结构D.4．【南京理工大学 一个算法应该是（ A .程序性5. 1999 一、 1（ 2 分） 【武汉交通科技大学 ）。
【中山大学 1998 二、B .问题求解步骤的描述D. A 和 C.下面关于算法说法错误的是（A. 算法最终必须由计算机程序实现 1996 一、1（ 4 分）】1（2 分）】 C.要满足五个基本特 ）【南京理工大学2000 一、 1（ 1.5 分）】D. 以上几个都是错）。
数据结构考试试题题库一、选择题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. 元素之间存在一对一或多对多关系答案：A2. 栈（Stack）是一种特殊的线性表，其特点是：A. 只能在一端进行插入和删除操作B. 可以在两端进行插入和删除操作C. 只能在一端进行插入操作，另一端进行删除操作D. 可以在任意位置进行插入和删除操作答案：A3. 在二叉树中，度为1的节点数目为2，度为0的节点数目也为2，该二叉树的节点总数是：A. 5B. 6C. 7D. 8答案：B二、简答题1. 请简述什么是哈希表，并说明其主要优点。
答案：哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。
其主要优点包括：平均情况下，查找、插入和删除操作的时间复杂度为O(1)，即常数时间内完成操作；空间效率高，能够存储大量数据。
2. 描述图的深度优先搜索（DFS）算法的基本思想。
答案：深度优先搜索算法的基本思想是从一个顶点开始，尽可能深地搜索图的分支。
搜索过程中使用一个栈来保存路径上的顶点。
当搜索到一个顶点时，先访问该顶点，然后依次搜索其所有未被访问过的邻接顶点。
如果当前顶点的所有邻接顶点都被访问过，则回溯到上一个顶点，继续搜索其他邻接顶点。
三、应用题1. 给定一个无向图，使用邻接表表示，请编写一个算法找出图中的所有连通分量。
答案：首先，创建一个访问过的顶点集合。
然后，从图中任意一个未被访问的顶点开始，执行深度优先搜索（DFS）。
每次DFS完成后，就找到了一个连通分量。
重复这个过程，直到所有顶点都被访问过，即可找到图中的所有连通分量。
2. 假设有一个数组，需要频繁地进行查找、插入和删除操作，请设计一个适合这种场景的数据结构，并说明其优势。
答案：对于这种场景，可以使用平衡二叉搜索树（如AVL树或红黑树）。
这些数据结构可以保证在最坏情况下，查找、插入和删除操作的时间复杂度为O(log n)。
2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷)一、应用题(3小题,共24分)1．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。
【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。
其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。
2．已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)=［ i/2 」(取下整数) ，其中i为关键码中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。
【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2采用链地址法处理冲突，得到的开散列表如下：平均查找长度=(1×7+2×4+3×1)/12=18/123．分析下面各程序段的时间复杂度（1）s1(int n){ int p=1,s=0;for (i=1;i<=n;i++){ p*=i;s+=p; }return(s);} ——O(n)（2）s2(int n)x=0;y=0;For (k=1;k<=n;k++) x++;For (i=1;i<=n;i++)For (j=1;j<=n;j++)y++; ——O(n2)1．下述算法的功能是什么?（1）（1）返回结点*p的直接前趋结点地址。
（2）交换结点*p和结点*q（p和q的值不变）。
1．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。
【解答】构造的哈夫曼树如图所示。
W PL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1202．已知散列函数H(k)=k mod 12，键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用链表法处理冲突，试构造散列表。
【解答】H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3,H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10构造的开散列表如下：3．分析下面各程序段的时间复杂度（1）for (i=0;i<n;i++)for (j=0;j<m;j++)A[i][j]——O(n*m)（2） s=0;for (i=0;i<n;i++)for (j=0;j<n;j++)s+=B[i][j];sum=s;——O(n2)（3）A=B; B=C; C=A;——O(1)3．设无向图G（所下图所示），要求给出从1出发对该图进行深度优先和广度优先遍历的序列。
深度：125364，广度：123456 （不唯一）4．已知无向图G的邻接表如图所示，分别写出从顶点1出发的深度遍历和广度遍历序列。
【解答】深度优先遍历序列为：1，2，3，4，5，6广度优先遍历序列为：1，2，4，3，5，6二、判断正误(7小题,共14分)1．线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
（√）2．一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。
（ㄨ）3．稀疏矩阵压缩存储后，必会失去随机存取功能。
（√）4．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。
（√）5．用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。
（√）6．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。
（ㄨ）7．逻辑结构与数据元素本身的内容和形式无关。
（√）1．对链表进行插入和删除操作时不必移动链表中结点。
( √ )3．如果两个串含有相同的字符，则说明它们相等。
( ㄨ )4．在线索二叉树中，任一结点均有指向其前趋和后继的线索。
(ㄨ)5．带权无向图的最小生成树是唯一的。
（ㄨ）6．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
（√）7．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的。
( ㄨ ) 8．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
（√）1．由树转化成二叉树，该二叉树的右子树不一定为空。
（ㄨ）2．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
（√）4．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
（√）5．设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。
（ㄨ）6．每种数据结构都具备三个基本操作：插入、删除和查找。
（ㄨ）1．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（×）2．在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
√3．链表的每个结点都恰好包含一个指针域。
（×）4．有向图的邻接表和逆邻接表中表结点的个数不一定相等。
（×）5．对连通图进行深度优先遍历可以访问到该图中的所有顶点。
（√）6．当装填因子小于1时，向散列表中存储元素时不会引起冲突。
（×）2．线性表的逻辑顺序和存储顺序总是一致的。
（×）3．非空的双向循环链表中任何结点的前驱指针均不为空。
（√）4．子串“ABC”在主串“AABCABCD”中的位置为2。
（√）5．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。
（×）7．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。
（×）9．当装填因子小于1时，向散列表中存储元素时不会引起冲突。
（×）10．散列技术的查找效率主要取决于散列函数和处理冲突的方法。
（×）1．线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。
（）2．稀疏矩阵压缩存储后，必会失去随机存取功能。
（√）5．对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。
（ㄨ）6．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。
（√）7．数据的逻辑结构和数据的存储结构是相同的。
（ㄨ）8．数据的存储结构是数据的逻辑结构的存储映像。
（√）三、单项选择题(8小题,共16分)1．下面关于线性表的叙述错误的是（ D ）。
A 线性表采用顺序存储必须占用一片连续的存储空间B 线性表采用链式存储不必占用一片连续的存储空间C 线性表采用链式存储便于插入和删除操作的实现D 线性表采用顺序存储便于插入和删除操作的实现2．单链表的存储密度（ C ）。
A．大于1 B．等于1 C．小于1 D．不能确定3．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ B ）。
A 5，3，4，6，1，2B 3，2，5，6，4，1C 3，1，2，5，4，6D 1，5，4，6，2，34．若串S="SOFTWARE"，其子串的数目最多是：（ C ）。
A．35 B．36 C．37 D．385．二叉排序树中，最小值结点的（A ）。
A 左指针一定为空B 右指针一定为空C 左、右指针均为空D 左、右指针均不为空6．在散列函数H(k)= k mod m中，一般来讲，m应取（C ）。
A 奇数B 偶数C 素数D 充分大的数7．用直接插入排序对下面四个序列进行由小到大排序，元素比较次数最少的是（ B ）。
A 94, 32, 40, 90, 80, 46, 21, 69B 21, 32, 46, 40, 80, 69, 90, 94C 32, 40, 21, 46, 69, 94, 90, 80D 90, 69, 80, 46, 21, 32, 94, 401．使用双链表存储线性表，其优点是可以（B ）。
A 提高查找速度B 更方便数据的插入和删除C 节约存储空间D 很快回收存储空间2．链表不具有的特点是（B ）A.不必事先估计存储空间B.可随机访问任一元素C.插入删除不需要移动元素D.所需空间与线性表长度成正比3．下面关于线性表的叙述错误的是（ D ）。
A 线性表采用顺序存储必须占用一片连续的存储空间B 线性表采用链式存储不必占用一片连续的存储空间C 线性表采用链式存储便于插入和删除操作的实现D 线性表采用顺序存储便于插入和删除操作的实现4．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（ D ）个结点。
A nB n/2C (n-1)/2D (n+1)/25．在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ）。
A．已固定 B．不固定 C．可以改变 D．动态变化6．两个字符串相等的充要条件是（C ）。
A 两个字符串的长度相等B 两个字符串中对应位置上的字符相等C 同时具备(A)和(B)两个条件D 以上答案都不对8．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ C ）。
A N0=N1+1B N0=Nl+N2C N0=N2+1D N0=2N1+l 9．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )A．e B．2e C．n2－e D．n2－2e10．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ A ）。
A N1-1B N2-1C N2+N3D N1+N311．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（D ）。
A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子D 任一结点无右孩子12．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择（快速）排序，如果从节省存储空间的角度来考虑则最好选择（堆）排序。
