下载文档原格式
四川大学计算机学院《数据结构与算法分析》课程模拟试卷及参考答案模拟试卷一一、单选题（每题2 分，共20分）1.以下数据结构中哪一个是线性结构？( )A. 有向图B. 队列C. 线索二叉树D. B树2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。
A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3.以下哪一个不是队列的基本运算？（）A. 在队列第i个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？A.14B.5C.6D.85.由权值分别为3,8,6,2A． 11 B.35 C. 19 D. 53以下6-8题基于图1。
6.该二叉树结点的前序遍历的序列为( )。
A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B7.该二叉树结点的中序遍历的序列为( )。
A. A、B、C、D、E、G、FB. E、A、G、C、F、B、DC. E、A、C、B、D、G、FE.B、D、C、A、F、G、E8.该二叉树的按层遍历的序列为( )。
A．E、G、F、A、C、D、B B. E、A、C、B、D、G、FC. E、A、G、C、F、B、DD. E、G、A、C、D、F、B9.下面关于图的存储的叙述中正确的是( )。
A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )A. a，g，h，m，n，p，q，x，zB. a，g，m，h，q，n，p，x，zC. g，m，q，a，n，p，x，h，zD. h，g，m，p，a，n，q，x，z二、填空题（每空1分，共26分）1.数据的物理结构被分为_________、________、__________和___________四种。
数据结构与算法模考试题（含参考答案）一、单选题（共100题，每题1分，共100分）1、某公司秘书小莉经常需要用Word编辑中文公文，她希望所录入的正文都能够段首空两个字符，最简捷的操作方法是：A、在每次编辑公文前，先将“正文”样式修改为“首行缩进 2 字符”。
B、每次编辑公文时，先输入内容然后选中所有正文文本将其设为“首行缩进 2 字符”。
C、在一个空白文档中将“正文”样式修改为“首行缩进 2 字符”，然后将当前样式集设为默认值。
D、将一个“正文”样式为“首行缩进 2 字符”正确答案：C2、现代微型计算机中所采用的电子元器件是：A、大规模和超大规模集成电路B、电子管C、晶体管D、小规模集成电路正确答案：A3、图书馆管理系统中实体图书和实体借阅人之间的联系是A、1：1B、1：NC、M：ND、N：1正确答案：C4、计算机网络最突出的优点是：A、资源共享和快速传输信息B、高精度计算和收发邮件C、运算速度快和快速传输信息D、存储容量大和高精度正确答案：A5、在 Excel 工作表单元格中输入公式时，F$2 的单元格引用方式称为：A、绝对地址引用B、交叉地址引用C、混合地址引用D、相对地址引用正确答案：C6、域名代码 MIL 表示：A、政府机关B、国际组织C、商业组织D、军事部门正确答案：D7、以下对 Excel 高级筛选功能，说法正确的是：A、高级筛选之前必须对数据进行排序B、利用“数据”选项卡中的“排序和筛选”组内的“筛选”命令可进行高级筛选C、高级筛选通常需要在工作表中设置条件区域D、高级筛选就是自定义筛选第 6 组正确答案：C8、软件工程的三要素是A、方法、工具和过程B、方法、工具和文档第 47 组C、方法、工具和环境D、方法、平台和管理正确答案：A9、字长是计算机的一个重要指标，在工作频率不变和 CPU 体系结构相似的前提下，字长与计算机性能的关系是：A、字长越长，计算机的数据处理速度越快B、字长越短，计算机的数据处理速度越快C、字长表示计算机的存储容量大小，字长越长计算机的读取速度越快D、字长越短，表示计算机的并行能力越强正确答案：A10、下面描述错误的是A、类中包含数据（属性）和方法（或操作）B、类中包含对数据的操作（方法）C、类是对象的实例D、类具有抽象性第 49 组正确答案：C11、在数据库的三级模式中,可以有任意多个A、模式B、内模式（物理模式）C、外模式（用户模式）正确答案：C12、以下关于计算机病毒的说法，不正确的是：A、计算机病毒一般会寄生在其他程序中B、计算机病毒一般会传染其他文件C、计算机病毒一般会具有自愈性D、计算机病毒一般会具有潜伏性正确答案：C13、CPU 的参数如 2800MHz，指的是：A、CPU 的速度B、CPU 的大小C、CPU 的时钟主频D、CPU 的字长正确答案：C14、设栈与队列初始状态为空。
数据结构模拟试卷及参考答案一、简答题（共10题，每题10分，共计100分）1. 什么是数据结构？请简要解释。
数据结构是计算机中用于组织和存储数据的方式，它包含了一系列的数据元素，以及这些数据元素之间的关系和操作。
通过使用不同的数据结构，可以更高效地存储、查找和操作数据。
2. 请解释什么是栈，并给出一个栈的应用场景。
栈是一种具有特定操作限制的数据结构，它遵循"先进后出"（LIFO）的原则。
栈的应用场景包括函数调用、表达式求值、撤销操作以及浏览器中的历史记录。
3. 什么是队列？请给出一个队列的实际应用例子。
队列是一种具有特定操作限制的数据结构，它遵循"先进先出"（FIFO）的原则。
一个实际应用例子是操作系统的进程调度，进程按照到达时间加入队列，并按照一定规则出队执行。
4. 请解释什么是链表，并给出一个链表的优点和缺点。
链表是一种动态数据结构，它由一系列节点构成，每个节点包含数据和指向下一个节点的指针。
链表的优点是可以动态地分配内存空间，且插入和删除节点的时间复杂度为O(1)。
缺点是访问链表某个具体节点的时间复杂度为O(n)，且需要额外的内存空间存储指针。
5. 请解释什么是树，并给出一个树的实际应用例子。
树是一种分层次的数据结构，它由一系列节点和节点之间的关系构成。
一个实际应用例子是文件系统的目录结构，文件和文件夹通过树的结构进行组织和存储。
6. 请解释什么是图，并给出一个图的实际应用例子。
图是一种由节点和节点之间的连接关系组成的数据结构。
一个实际应用例子是社交网络，人与人之间的关系可以用图来表示，每个人是一个节点，节点之间的连接表示关系。
7. 请解释什么是散列（哈希）表，以及它的优势和劣势。
散列表是一种根据关键字直接访问的数据结构，它通过将关键字映射到表中的位置来实现快速的查找操作。
散列表的优势是查找操作的平均时间复杂度为O(1)。
劣势是如果存在多个关键字映射到同一个位置，就会发生冲突，需要解决冲突问题。
数据结构与算法同步训练模拟试题及答案解析(1/43)选择题第1题下列叙述中正确的是()。
A.循环队列是队列的一种链式存储结构B.循环队列是队列的一种顺序的存储结构C.循环队列是非线性结构D.循环队列是一种逻辑结构下一题(2/43)选择题第2题算法的有穷性是指()。
A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用上一题下一题(3/43)选择题第3题算法的空间复杂度是指()。
A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数上一题下一题(4/43)选择题第4题定义无符号整数类为UInt，下面可以作为类UInt实例化值的是()。
A.-369B.369C.0.369D.整数集合{1,2,3,4,5}上一题下一题(5/43)选择题第5题下列叙述正确的是()。
A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.以上三种说法都不对上一题下一题(6/43)选择题第6题下列叙述中正确的是()。
A.有一个以上根结点的数据结构不一定是非线性结构B.只有一个根结点的数据结构不一定是线性结构C.循环链表是非线性结构D.双向链表是非线性结构上一题下一题(7/43)选择题第7题下列关于线性链表的叙述中，正确的是()。
A.各数据结点的存储空间可以不连续，但他们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间不需连续C.进行插入数据与删除数据时，不需要异动表中的元素D.以上说法均不对上一题下一题(8/43)选择题第8题下列叙述中正确的是()。
A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间上一题下一题(9/43)选择题第9题下列叙述中正确的是()。
数据结构与算法试题及答案数据结构与算法试题及答案在计算机科学领域，数据结构与算法是非常重要的基础知识。
数据结构是一种组织和存储数据的方式，而算法则是解决问题的方法和步骤。
掌握好数据结构与算法，有助于提高程序的运行效率和解决实际问题。
下面是一些关于数据结构与算法的试题及其答案，希望能够帮助大家更好地理解和应用这方面的知识。
试题一：什么是数据结构？请举例说明。
答案一：数据结构是一种组织和存储数据的方式。
它可以使数据的操作更加高效。
常见的数据结构有数组、链表、栈、队列、树和图等。
举个例子，数组是一种线性数据结构，可以存储一组相同类型的元素。
试题二：什么是算法？请举例说明。
答案二：算法是一种解决问题的方法和步骤。
它是一个精确的描述，用于解决特定问题。
常见的算法有排序算法、查找算法、递归算法等。
例如，冒泡排序算法是一种比较简单的排序算法，通过不断交换相邻元素的位置来达到排序的目的。
试题三：什么是时间复杂度和空间复杂度？答案三：时间复杂度和空间复杂度是衡量算法性能的两个指标。
时间复杂度是指算法执行所需要的时间，通常用大O符号表示。
空间复杂度是指算法执行所需要的额外空间，通常也用大O符号表示。
它们都是描述算法随着输入规模增大而变化的趋势。
试题四：介绍一下常见的数据结构和相应的操作。
答案四：常见的数据结构有数组、链表、栈、队列、树和图等。
- 数组是一种线性数据结构，可以随机访问元素，并且在插入和删除元素时需要移动其他元素。
- 链表是一种动态数据结构，不需要固定的内存空间，但只能通过指针进行元素的访问。
- 栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除元素的操作。
- 队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。
- 树是一种非线性数据结构，由节点和指向子节点的边组成。
常见的树有二叉树、二叉搜索树和AVL树等。
- 图是一种复杂的数据结构，由节点和边组成，可以表示各种关系。
数据结构与算法测试题+参考答案一、单选题（共80题，每题1分，共80分）1、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？A、仅有头指针的单循环链表B、双链表C、仅有尾指针的单循环链表D、单链表正确答案：C2、数据结构研究的内容是（）。
A、数据的逻辑结构B、数据的存储结构C、建立在相应逻辑结构和存储结构上的算法D、包括以上三个方面正确答案：D3、下列关于无向连通图特征的叙述中，正确的是：所有顶点的度之和为偶数边数大于顶点个数减1至少有一个顶点的度为1A、只有1B、1和2C、1和3D、只有2正确答案：A4、下面的程序段违反了算法的（）原则。
void sam(){ int n=2;while (n%2==0) n+=2;printf(“%d”,n);}A、确定性B、可行性C、有穷性D、健壮性正确答案：C5、对任意给定的含 n (n>2) 个字符的有限集 S，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。
下列叙述中，正确的是：A、出现频次不同的字符在 T2 中处于相同的层B、出现频次不同的字符在 T1 中处于不同的层C、T1 的高度大于 T2 的高度D、T1 与 T2 的结点数相同正确答案：A6、数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？A、快速排序B、选择排序C、插入排序D、冒泡排序正确答案：A7、设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。
采用线性探测法处理冲突，并将关键字序列{ 26，25，72，38，8，18，59 }依次存储到散列表中。
元素59存放在散列表中的地址是：A、11B、9C、10D、8正确答案：A8、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：A、每次划分后，先处理较短的分区可以减少递归次数B、递归次数与每次划分后得到的分区处理顺序无关C、递归次数与初始数据的排列次序无关D、每次划分后，先处理较长的分区可以减少递归次数正确答案：B9、以下数据结构中，（）是非线性数据结构。
数据结构与算法题库（含参考答案）一、单选题（共100题，每题1分，共100分）1、在一次校园活动中拍摄了很多数码照片，现需将这些照片整理到一个PowerPoint 演示文稿中，快速制作的最优操作方法是：A、创建一个 PowerPoint 相册文件。
B、创建一个 PowerPoint 演示文稿，然后批量插入图片。
C、创建一个 PowerPoint 演示文稿，然后在每页幻灯片中插入图片。
D、在文件夹中选中所有照片，然后单击鼠标右键直接发送到PowerPoint 演示文稿中。
正确答案：A2、下面对“对象”概念描述错误的是A、对象不具有封装性B、对象是属性和方法的封装体C、对象间的通信是靠消息传递D、一个对象是其对应类的实例正确答案：A3、设栈与队列初始状态为空。
首先A,B,C,D,E依次入栈，再F,G,H,I,J 依次入队；然后依次出队至队空，再依次出栈至栈空。
则输出序列为A、F,G,H,I,J,E,D,C,B,AB、E,D,C,B,A,J,I,H,G,FC、F,G,H,I,J,A,B,C,D,E,D、E,D,C,B,A,F,G,H,I,J正确答案：A4、设表的长度为 20。
则在最坏情况下，冒泡排序的比较次数为A、20B、19C、90D、190正确答案：D5、设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。
则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ正确答案：A6、Excel工作表B列保存了11位手机号码信息，为了保护个人隐私，需将手机号码的后 4 位均用“*”表示，以 B2 单元格为例，最优的操作方法是：A、=REPLACE(B2,7,4,"****")B、=REPLACE(B2,8,4,"****")C、=MID(B2,7,4,"****")D、=MID(B2,8,4,"****")第 10 组正确答案：B7、小金从网站上查到了最近一次全国人口普查的数据表格，他准备将这份表格中的数据引用到 Excel 中以便进一步分析，最优的操作方法是：A、通过 Excel 中的“自网站获取外部数据”功能，直接将网页上的表格导入到 Excel 工作表中。
数据结构与算法设计试卷（答案见尾页）一、选择题1. 数据结构中，下列哪种数据结构的插入和删除操作时间复杂度最低？A. 栈B. 队列C. 数组D. 链表2. 在二叉树的遍历方法中，哪种方法可以访问所有节点且时间复杂度为O(n)？A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历3. 常用的排序算法中，哪种算法是基于比较的排序算法，并且时间复杂度为O(n log n)？A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序4. 在图的存储结构中，邻接矩阵适合表示哪种类型的图？A. 稀疏图B. 密集图C. 有向无环图D. 无向无环图5. 动态规划算法用于解决哪种类型的问题？A. 数值计算问题B. 字符串匹配问题C. 图论问题D. 机器学习问题6. 在最短路径问题中，Dijkstra算法和Floyd算法分别适用于哪种类型的图？A. 有权图和无权图B. 无权图和有权图C. 有向图和无向图D. 无向图和有权图7. 快速排序算法中，基准元素的选择对算法性能有何影响？A. 基准元素的选择不影响算法性能B. 基准元素选择不当会导致算法性能下降C. 基准元素选择得当可以提高算法性能D. 基准元素的选择与算法性能无关8. 在链表中，单向链表的每个节点包含哪些部分？A. 数据域和指针域B. 数据域和指针头C. 数据域和指针尾D. 数据域和指针尾9. 在栈的实现中，后进先出（LIFO）原则是如何体现的？A. 先进入栈的元素总是最先被移除B. 先进入栈的元素总是最后被移除C. 后进入栈的元素总是最先被移除D. 后进入栈的元素总是最后被移除10. 哈希表（Hash Table）的主要优点是什么？A. 查找速度快，插入和删除操作较慢B. 查找速度较慢，插入和删除操作较快C. 查找速度较快，插入和删除操作也较快D. 查找速度较慢，插入和删除操作也较慢11. 在最坏情况下，下列哪种排序算法的时间复杂度为O(n^)？A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序12. 在二叉树的遍历方法中，先序遍历的特点是？A. 先访问根节点，然后遍历左子树，最后遍历右子树B. 先访问左子树，然后访问根节点，最后遍历右子树C. 先访问左子树，然后访问右子树，最后访问根节点D. 先访问右子树，然后访问左子树，最后访问根节点13. 常用的查找算法中，哈希表的查找效率最高，其平均查找时间复杂度为？A. O(1)B. O(log n)C. O(n)D. O(n log n)14. 下列哪种数据结构适用于表示稀疏线性表？A. 数组B. 链表C. 栈D. 队列15. 最短路径问题在图论中的研究内容是？A. 路径长度B. 路径上的节点序列C. 最短路径的长度及路径上的节点序列D. 最短路径的权重16. 快速排序算法是基于什么思想进行递归划分的？A. 分治法B. 动态规划C. 贪心算法D. 回溯算法17. 在图的遍历算法中，普里姆算法用于寻找？A. 所有顶点的最短路径B. 两个顶点之间的最短路径C. 一棵树的中序遍历D. 一棵树的前序遍历18. 下列哪种数据结构可以实现队列的先进先出（FIFO）特性？A. 栈B. 队列C. 数组D. 链表19. 在深度优先搜索算法中，哪种策略用于访问所有可能的路径？A. 沿着边遍历B. 沿着对角线遍历C. 沿着某一特定方向遍历D. 沿着任意方向遍历20. 在图的遍历算法中，普里姆算法用于求解什么问题？A. 最小生成树B. 最短路径C. 连通性D. 网络流21. 哈希表的冲突解决策略中，链地址法适用于哪种情况？A. 哈希函数值分布均匀B. 哈希函数值分布不均匀C. 存储的元素数量较大D. 存储的元素数量较小22. 在快速排序算法中，基准元素的选择对算法性能有何影响？A. 基准元素选择不合适会导致排序效率降低B. 基准元素选择不合适会导致排序效率提高C. 基准元素选择对算法性能没有影响D. 基准元素选择与算法性能无关23. 在二叉树的遍历算法中，先序遍历、中序遍历和后序遍历分别适用于哪些类型的树？A. 充分不平衡的二叉树B. 充分平衡的二叉树C. 不充分平衡的二叉树D. 完全不平衡的二叉树24. 在贪心算法中，贪心选择性质如何帮助求解问题？A. 贪心选择性质使得每次选择都能立即带来全局最优解B. 贪心选择性质使得每次选择都能减少后续问题的规模C. 贪心选择性质使得每次选择都能增加后续问题的规模D. 贪心选择性质使得每次选择都能保持问题的原有规模25. 在动态规划算法中，状态转移方程如何描述问题的解决过程？A. 状态转移方程描述了问题状态之间的转移过程B. 状态转移方程描述了问题状态之间的变换过程C. 状态转移方程描述了问题状态之间的依赖关系D. 状态转移方程描述了问题状态之间的组合关系26. 在下列哪种数据结构中，元素之间的逻辑关系可以通过指针直接访问？A. 数组B. 链表C. 栈D. 队列27. 下列哪种排序算法的平均时间复杂度为O(n^)？A. 快速排序B. 归并排序C. 堆排序D. 插入排序28. 在图论中，表示图中节点间有向边的图形是？A. 无向图B. 有向图C. 网络图D. 树29. 在树的遍历算法中，先序遍历、中序遍历和后序遍历分别指的是什么？A. 先访问根节点，再遍历左子树，最后遍历右子树B. 先访问左子树，再访问根节点，最后遍历右子树C. 先访问左子树，再遍历右子树，最后访问根节点D. 先访问根节点，再遍历右子树，最后遍历左子树30. 在图的存储结构中，邻接矩阵和邻接表分别适用于哪种情况？A. 小型图和大中型图B. 大中型图和小型图C. 都适用于大型图D. 都适用于小型图31. 在动态规划算法中，解决最短路径问题常用的算法是？A. 贝尔曼-福特算法B. 弗洛伊德-沃沙尔算法C. 克鲁斯卡尔算法D. 普里姆算法32. 在贪心算法中，贪心选择性质是指什么？A. 每一步都选择局部最优解，整个问题就最优B. 每一步都选择全局最优解，整个问题就最优C. 每一步都选择当前最优解，整个问题就最优D. 每一步都选择历史最优解，整个问题就最优33. 在搜索算法中，广度优先搜索（BFS）和深度优先搜索（DFS）有何不同？A. BFS从根节点开始，逐层扩展；DFS从任意节点开始，深入探索B. BFS从任意节点开始，逐层扩展；DFS从根节点开始，深入探索C. BFS只搜索浅层节点，DFS可能搜索深层的叶子节点D. BFS只搜索浅层节点，DFS可能搜索深层的叶子节点34. 在图论中，强连通分量是指什么？A. 图中任意两个顶点之间都有路径相连B. 图中任意三个顶点之间都有路径相连C. 图中存在一个顶点集合，使得每个顶点都与另一个顶点直接相连D. 图中存在一个顶点集合，使得每个顶点都与另一个顶点循环相连35. 在下列哪种数据结构中，元素之间的关系可以通过指针直接访问？A. 数组B. 链表C. 栈D. 队列36. 在排序算法中，稳定性意味着什么？A. 相同值的元素在排序后相对顺序不变B. 不相邻的元素在排序后相对顺序不变C. 相邻的元素在排序后相对顺序不变D. 所有元素的相对顺序都不变37. 下列哪种排序算法是递归的？A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序38. 在图的存储结构中，邻接矩阵更适合表示哪种类型的图？A. 小型图B. 大型图C. 稀疏图D. 密集图二、问答题1. 什么是递归？请举例说明递归在计算机科学中的应用。
《数据结构》模拟试题03一、单项选择题（每题 2 分，共30分）1．算法指的是（ ）A ．计算机程序B ．解决问题的计算方法C ．排序算法D ．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ ） A ．必须是不连续的 B ．连续与否均可 C ．必须是连续的D ．和头结点的存储地址相连续3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（ ） A ．O （1） B ．O （n ） C ．O （m ） D ．O （m+n ） 4．由两个栈共享一个向量空间的好处是：（ ） A ．减少存取时间，降低下溢发生的机率 B ．节省存储空间，降低上溢发生的机率 C ．减少存取时间，降低上溢发生的机率 D ．节省存储空间，降低下溢发生的机率5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为（ ）A ．front=front+1B ．front=(front+1)%(m-1)C ．front=(front-1)%mD ．front=(front+1)%m 6．如下陈述中正确的是（ ）A ．串是一种特殊的线性表B ．串的长度必须大于零C ．串中元素只能是字母D ．空串就是空白串7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）A ．O （n3） B ．O （n ） C ．O （n2） D ．O （n3）8．一个非空广义表的表头（ ）A ．不可能是子表B ．只能是子表C ．只能是原子D ．可以是子表或原子 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表对应的稀疏矩阵是（ ）5A.08067000000050400000--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥B.08067000504000000300--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥C.08060000020050400000--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥D.08060000700050400300--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A．4 B．5 C．6 D．711．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )A．e B．2e C．n2－e D．n2－2e12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）A．选择排序B．希尔排序C．归并排序D．快速排序14．适于对动态查找表进行高效率查找的组织结构是（）A．有序表B．分块有序表C．三叉排序树D．线性链表15．不定长文件是指（）A．文件的长度不固定B．记录的长度不固定C．字段的长度不固定D．关键字项的长度不固定二、填空题（每题2分，共20分）1．数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关，是独立于计算机的。
《算法与数据结构》模拟试题3(参考答案)一、填空题（每小题2分，共18分）1、 线性结构 树形结构 图（或网）状结构2、 时间复杂度 空间复杂度3、 (直接)前驱结点 (直接)后继结点4、 零个字符组成的串 05、 3006、 只有右子树上的所有结点7、 先序遍历8、 索引 块9、 操作系统 数据库二、单项选择题（请将答案写在题目后的括号中。
每题2分，共18分）三、分析题（每题6分，共30分）1、 解：所画出的二叉树如图(a)所示。
树的后序遍历序列是gdhiebfca ，其后序线索化树图(a) 二叉树图(b) 后序线索化树2、 解：该网的邻接链表如下图所示： 从顶点V 1出发的广度优先搜索的顶点序列是1→2→3→5→4，相应的生成树如下：3、 解：将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到初态为空的二叉排序树中所得到的二叉排序树T 如图(a)所示；删除18之后的二叉排序树T1如图(b)所示；最后再插入18之后的二叉排序树T2。
从顶点V 1出发广度优先搜索生成树4、解：根据所给定的散列函数和处理冲突方法，得到的散列表结构如下：成功查找的平均查找长度：ASL=(1×8+2×2+3×1)/11=17/115、解：做非递减排序时的每一趟结果如下：初始关键字：35，29，52，60，17，9，38，27，13，45第一趟：[29，35] [52，60] [9，17] [27，38] [13，45]第二趟：[29，35，52，60] [9，17，27，38] [13，45]第三趟：[29，35，52，60] [9，13，17，27，38，45]第四趟：[9，13，17，27，29，35，38，45，52，60]第四趟归并完毕，排序结束。
四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。
每个空白处只能填一个语句。
