下载文档原格式
数据结构与算法练习试卷2(题后含答案及解析) 全部题型 2. 填空题填空题（每空2分，共30分）请将每一个空的正确答案写在答题卡上。
注意：以命令关键字填空的必须拼写完整。
1．数据元素之间______的整体称为逻辑结构。
正确答案：逻辑关系涉及知识点：数据结构与算法2．一个算法的时间复杂性是______的函数。
正确答案：算法输入规模涉及知识点：数据结构与算法3．在单链表中，NULL称为______，它不指向任何结点，只起______作用。
正确答案：空指针、标志涉及知识点：数据结构与算法4．对长度为n的顺序表的删除算法，它的最坏情况时间复杂度及其量级分别是和______，平均时间复杂性及其量级分别为______和______。
正确答案：n-1、O(n)、(n-1)/2、O(n) 涉及知识点：数据结构与算法5．存储结点中数据域占用的存储量与整个结点占用存储量之比称为______。
正确答案：存储密度涉及知识点：数据结构与算法6．一般地，二叉树可以有______种基本形态。
正确答案：5 涉及知识点：数据结构与算法7．按照排序过程涉及的存储设备的不同，排序可分为______和______。
正确答案：内部排序、外部排序涉及知识点：数据结构与算法8．评价排序算法优劣的主要标准是______和______。
正确答案：时间复杂度、算法需要的附加空间涉及知识点：数据结构与算法9．稳定的排序算法有______、______和______。
正确答案：直接插入排序、冒泡排序、归并排序涉及知识点：数据结构与算法10．第一趟排序后序列中关键字最大的记录交换到最后的排序方法是______。
正确答案：冒泡排序涉及知识点：数据结构与算法11．数据结构分为逻辑结构与存储结构，线性链表属于______。
正确答案：存储结构涉及知识点：数据结构与算法12．在树型结构中，树根结点没有______。
正确答案：前件涉及知识点：数据结构与算法13．数据的逻辑结构有线性结构和______两大类。
数据结构与算法模考试题（含参考答案）一、单选题（共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、设栈与队列初始状态为空。
国家二级C语言（数据结构与算法）机试模拟试卷1(题后含答案及解析)题型有：1. 选择题选择题1．算法具有五个特性，以下选项中不属于算法特性的是A．有穷性B．简洁性C．可行性D．确定性正确答案：B解析：算法的五个特性分别是：有穷性、可行性、确定性、输入和输出。
知识模块：数据结构与算法2．算法的有穷性是指A．算法程序的运行时间是有限的B．算法程序所处理的数据量是有限的C．算法程序的长度是有限的D．算法只能被有限的用户使用正确答案：A解析：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
知识模块：数据结构与算法3．算法的时间复杂度是指A．算法的执行时间B．算法所处理的数据最C．算法程序中的语句或指令条数D．算法在执行过程中所需要的基本运算次数正确答案：D解析：算法的时间复杂度，是指执行算法所需要的计算工作量。
算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。
知识模块：数据结构与算法4．对存储器按字节进行编址，若某存储器芯片共有10根地址线，则该仔储器芯片的存储容量为A．1kbB．2kbC．4kbD．8kb正确答案：A解析：10根地址线，每根地址线有0和1两种情况，地址范围就是2的10次方=1024=1K。
知识模块：数据结构与算法5．磁盘处于写保护状态时其中的数据A．不能读出，不能删改B．可以读出，不能删改C．不能读出，可以删改D．可以读出，可以删改正确答案：B解析：磁盘处于写保护状态时其中的数据可以读出来，但是不能修改和删除。
知识模块：数据结构与算法6．在Windows环境下，单击当前窗口中的按钮“”，其功能是A．讲当前应用程序转为后台运行B．退Windows后再关机C．终止当前应用程序的运行D．退出Windows后重新启动计算机正确答案：C解析：在Windows中，单击窗口中的按钮“”表示关闭当前运行的程序。
知识模块：数据结构与算法7．下列描述中正确的是A．数据的逻辑结构与存储结构必定是一一对应的B．由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C．程序设计语言中的数据一般是顺序存储结构，因此，利用数组只能处理线性结构D．以上三种说法都不对正确答案：D解析：数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。
数据结构与算法同步训练模拟试题及答案解析(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题下列叙述中正确的是()。
国家二级C语言（数据结构与算法）机试模拟试卷2(题后含答案及解析)题型有：1. 选择题选择题1．算法中，对需要执行的每一步操作，必须给出清楚、严格的规定。
这属于算法的A．正当性B．可行性C．确定性D．有穷性正确答案：C解析：本题考查算法的基本特征。
算法的可行性表示算法中执行的任何步骤都是可以被分解为基本的可执行的操作步：确定性是指算法的每一步骤必须有确切的含义；有穷性是指算法必须能在执行有限个步骤之后终止。
知识模块：数据结构与算法2．下列叙述中正确的是A．算法就是程序B．设计算法时只需要考虑数据结构的设计C．设计算法时只需要考虑结果的可靠性D．以上三种说法都不对正确答案：D解析：所谓算法是指解题方案的准确而完整的描述。
是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。
算法不等于程序，也不等于计算方法。
设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。
知识模块：数据结构与算法3．下列叙述中正确的是A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关正确答案：B解析：算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。
算法的时间复杂度与空间复杂度并不相关。
数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之问的关系如何在计算机中表示，它们并非一一对应。
算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。
知识模块：数据结构与算法4．在DOS环境F，代表键盘和显示器的设备文件名为A．PRNB．CONC．NULD．LPT正确答案：B解析：本题考查DOS下面的虚拟设备文件，选项A)的PRN表示打印机，选项B)中的CON表示键盘或屏幕，选项C）的NUL表示虚拟空设备，选项D)的LPT表示并口。
数据结构与算法练习试卷1(题后含答案及解析) 题型有：1. 选择题选择题（每小题1分，共60分）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。
下列各题基于下面的叙述：某二叉树节点的对称序序列为A、B、C、D、E、P、G，后序序列为B、D、C、A、F、G、E。
1．该二叉树节点的先序序列为______。
A．E、G、F、A、C、D、BB．E、A、C、B、D、G、FC．E、A、G、C、F、B、DD．E、G、A、C、D、F、B正确答案：B 涉及知识点：数据结构与算法2．该二叉树对应的树林包括多少棵树? ______。
A．1B．2C．3D．4正确答案：B 涉及知识点：数据结构与算法3．该二叉树对应的树林节点的层次次序序列为______。
A．E、G、F、A、C、D、BB．E、A、C、B、D、G、FC．E、A、G、C、F、B、DD．E、G、A、C、D、F、B正确答案：C 涉及知识点：数据结构与算法4．有6个元素6，5，4，3，2，1顺序进栈，问下列哪一个不是合法的出栈序列______。
A．5，4，3，6，1，2B．4，5，3，2，1，6C．3，4，6，5，2，1D．2，3，4，1，5，6正确答案：A 涉及知识点：数据结构与算法5．下面关于串的叙述中，哪一个是不正确的? ______。
A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储正确答案：B 涉及知识点：数据结构与算法6．下列排序方法中，哪一个是稳定的排序方法? ______。
A．直接选择排序B．二分法插入排序C．希尔排序D．快速排序正确答案：B 涉及知识点：数据结构与算法7．下面关于B和B+树的叙述中，不正确的是______。
A．B树和B+树都是平衡的多分树B．B树和B+树都可用于文件的索引结构C．B树和B+树都能有效地支持顺序检索D．B树和B+树都能有效地支持随机检索正确答案：C 涉及知识点：数据结构与算法8．下面关于线性表的叙述中，错误的是______。
数据结构与算法试题及答案数据结构与算法试题及答案在计算机科学领域，数据结构与算法是非常重要的基础知识。
数据结构是一种组织和存储数据的方式，而算法则是解决问题的方法和步骤。
掌握好数据结构与算法，有助于提高程序的运行效率和解决实际问题。
下面是一些关于数据结构与算法的试题及其答案，希望能够帮助大家更好地理解和应用这方面的知识。
试题一：什么是数据结构？请举例说明。
答案一：数据结构是一种组织和存储数据的方式。
它可以使数据的操作更加高效。
常见的数据结构有数组、链表、栈、队列、树和图等。
举个例子，数组是一种线性数据结构，可以存储一组相同类型的元素。
试题二：什么是算法？请举例说明。
答案二：算法是一种解决问题的方法和步骤。
它是一个精确的描述，用于解决特定问题。
常见的算法有排序算法、查找算法、递归算法等。
例如，冒泡排序算法是一种比较简单的排序算法，通过不断交换相邻元素的位置来达到排序的目的。
试题三：什么是时间复杂度和空间复杂度？答案三：时间复杂度和空间复杂度是衡量算法性能的两个指标。
时间复杂度是指算法执行所需要的时间，通常用大O符号表示。
空间复杂度是指算法执行所需要的额外空间，通常也用大O符号表示。
它们都是描述算法随着输入规模增大而变化的趋势。
试题四：介绍一下常见的数据结构和相应的操作。
答案四：常见的数据结构有数组、链表、栈、队列、树和图等。
- 数组是一种线性数据结构，可以随机访问元素，并且在插入和删除元素时需要移动其他元素。
- 链表是一种动态数据结构，不需要固定的内存空间，但只能通过指针进行元素的访问。
- 栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除元素的操作。
- 队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。
- 树是一种非线性数据结构，由节点和指向子节点的边组成。
常见的树有二叉树、二叉搜索树和AVL树等。
- 图是一种复杂的数据结构，由节点和边组成，可以表示各种关系。
国家开放大学《数据结构与算法》形考任务1-2参考答案《数据结构与算法》是“数据科学与大数据技术”专业（本科）的一门统设必修课。
课程编号：04692形考任务1一、单项选择题1.下面说法错误的是（）。
A.数据结构是指互相之间存在着一种或多种关系的数据元素的集合B.数据(Data)是指客观事物的符号表示C.数据元素是表示数据的不可分割的最小标识单位D.数据的基本单位是数据元素2.数据结构中的线性结构是指（）。
A.数据元素之间属于同一个集合B.数据元素之间存在着一对一的线性关系C.数据元素之间存在着一对多的线性关系D.数据元素之间存在着多对多的线性关系3.下列有关递归的说法错误的是（）。
A.递归需要有边界条件、递归方程两部分构成。
B.递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算。
C.递归通常把一个复杂问题层层转化为一个与原问题相似的规模较小的问题来求解。
D.只有在函数中直接调用自身才能叫做递归函数。
4.根据数据元素之间关系的不同，数据结构分为（）。
A.物理结构，逻辑结构B.集合结构，线性结构，树结构，图结构C.顺序结构，链表结构D.递归结构，普通结构5.栈S最多能容纳4个元素。
现有6个元素按A、B、C、D、E、F的顺序进栈，下列（）序列是可能的出栈序列。
A.E、D、C、B、A、FB.B、C、E、F、A、DC.B、D、C、F、E、AD.A、D、F、E、B、C6.顺序循环队列容量为50，队头表示第一个元素的位置，队尾表示最后一个元素的下一个位置，当队头为31，队尾为8的时候，队列中共有（）个元素。
A.25B.26C.27D.287.对线性表，在下列（）情况下应当采用链表表示。
A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变8.若用一个大小为8的数组来实现循环队列，且当tail和head的值分别为6，0。
当从队列中删除两个元素，再加入一个元素后，tail和head的值分别为（）。
数据结构模拟试卷(一)及参考答案一．单项选择题（本大题共15小题，每小题2分，共30分）1．如果只想得到1024个元素组成的序列中的前5个最小元素，那么用( A )方法最快。
A、起泡排序B、快速排序C、堆排序D、直接选择排序2．算法分析的目的是（B）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（C）A．插入B．删除C．定位D．排序4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（D）A．3，2，6，1，4，5 B．5，6，4，2，3，1C．1，2，5，3，4，6 D．3，4，2，1，6，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（A）A．15 B．16C．17 D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（B）。
A. 108B. 112C. 116D. 1207．从一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（C）个结点。
A. nB. n/2C. (n+1)/2D. (n-1)/28．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（D）A．不一定相同 B．互为逆序C．都不相同D．都相同9．高度为5的二叉树至多有结点数为（A）A. 63B. 32C. 24D.6410．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（B）A．图中每个顶点的出度B．图中每个顶点的入度C．图中弧的条数D．图中连通分量的数目11．图的邻接矩阵表示法适用于表示（C）A．无向图B．有向图C．稠密图D．稀疏图12．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则执行（D）。
一、单选题1、若串S= 'software',其前缀真子串的数目是（）。
A.9B.8C.7D.10正确答案：C2、两个串相等的充要条件是（）。
A.两个字符串的长度相等且对应位置上的字符也相等B.两个字符串的长度相等C.两个字符串中对应位置上的字符相等D.两个字符串存储形式相同正确答案：A3、函数strcmp('stcabuc','stbabuc')的返回值是（）。
A.1B.-1C.0D.2正确答案：A4、StrIndex （‘DATASTRUCTURE'，1,‘STR'）= （）。
A.9B.5C.3D.7正确答案：B5、设正文串长度为n，模式串长度为m，则模式匹配的KMP算法的时间复杂度为（）。
A.O(n)B.O(m)C.O(m+n)D.O(m*n)正确答案：C6、设S=""，则LenStr(S)=（）。
A.1B.2C.3D.0正确答案：D7、设目标串T="aabaababaabaa"，模式P="abab"，朴素匹配算法的外层循环进行了( )次。
A.5B.9C.4D.1正确答案：A8、若串S='SOFT'，其子串的数目最多是（）。
A.9B.12C.10D.11正确答案：D9、设串S1='ABCDEFG'，S2='PQRST' ,则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为( )。
A.'BCPQRST'B.'BCDEFEF'C.'BCDEF'D.'BCDEFG'正确答案：B10、某串的长度小于一个常数，则采用（）存储方式最节省空间。
A.堆结构B.顺序C.链式D.无法确定正确答案：B11、二维数组A的每个元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则如果A按行存放元素A[8][5]的起始地址与A按列存放时元素（）的起始地址一致。
四川大学《数据结构与算法分析》课程考试模拟试卷模拟试卷一一、单选题（每题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,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。
以下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.数据的物理结构被分为_________、________、__________和___________四种。
2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。
3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________;删除一个结点时，需要执行的操作是______________________________（假设栈不空而且无需回收被删除结点）。
4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双亲，则双亲结点的编号为________。
5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整到____________位置为止。
6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。
7.表示图的三种常用的存储结构为_____________、____________和_______________。
8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。
9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为____________，空间复杂度为___________。
10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________个，其子树数目最少为________，最多为________。
三、运算题（每题6 分，共24分）1.写出下列中缀表达式的后缀形式：（1）3X/(Y-2)+1（2）2+X*(Y+3)2.试对图2中的二叉树画出其：(1)顺序存储表示的示意图；(2)二叉链表存储表示的示意图。
3.判断以下序列是否是小根堆? 如果不是, 将它调图2 整为小根堆。
（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }4.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4, (4,7)20,(5,6)18,(6,7)25};按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
四、阅读算法（每题7分，共14分）1.void AE(Stack& S){InitStack(S);Push(S,3);Push(S,4);int x=Pop(S)+2*Pop(S);Push(S,x);int i,a[5]={1,5,8,12,15};for(i=0;i<5;i++) Push(S,2*a[i]);while(!StackEmpty(S)) cout<<Pop(S)<<' ';}该算法被调用后得到的输出结果为：2.void ABC (BTNode *BT,int &c1,int &c2) {if (BT !=NULL ) {ABC(BT->left,c1,c2);c1++;if (BT->left==NULL&&BT->right==NULL) c2++;ABC(BT->right,c1,c2);}//if}该函数执行的功能是什么？五、算法填空（共8分）向单链表的末尾添加一个元素的算法。
Void InsertRear(LNode*& HL,const ElemType& item){LNode* newptr;newptr=new LNode;If (______________________){cerr<<"Memory allocation failare!"<<endl;exit(1);}________________________=item;newptr->next=NULL;if (HL==NULL)HL=__________________________;else{LNode* P=HL;While (P->next!=NULL)____________________;p->next=newptr;}}六、编写算法（共8分）编写从类型为List的线性表L中将第i个元素删除的算法，（假定不需要对i的值进行有效性检查,也不用判别L是否为空表。
）void Delete(List& L, int i)模拟试卷一参考答案一、单选题（每题2分，共20分）1.B2.D3.A4.B5.B6.C7.A8.C9.B 10.B二、填空题（每空1分，共26分）1.顺序链表索引散列2.O(n) O(1)3.p->next=HS;HS=p HS=HS->next4.2i 2i+1 ⎣i/2⎦（或i/2）5.向上根6. 2.97.邻接矩阵邻接表边集数组8. 1 49.O(n) O(nlog2n) O(n)10.⎡m/2⎤-1 m-1 ⎡m/2⎤ m三、运算题（每题6分，共24分）1.(1) 3 X * Y 2 - / 1 +图3(2) 2 X Y 3 + * +2.（1）3.(1)不是小根堆。
调整为：{12,65,33,70,24,56,48,92,86,33}(2)是小根堆。
4.普里姆算法从顶点1出发得到最小生成树为：(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20四、阅读算法（每题7分，共14分）1.30 24 16 10 2 102.该函数的功能是：统计出BT所指向的二叉树的结点总数和叶子总数五、算法填空（共8分，每一空2分）newptr==NULL newptr->=data newptr p=p->next六、编写算法（8分）void Delete(List& L, int i){for(int j=i-1;j<L.size-1; j++)L.list[j]=L.list[j+1]; //第i个元素的下标为i-1 L.size--;}模拟试卷二一、单选题（每题2 分，共20分）1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A. HL=p; p->next=HL;B. p->next=HL->next; HL->next=p;C. p->next=HL; p=HL;D. p->next=HL; HL=p;2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（）个元素.A. nB.n-1C. n+1D.不确定3.下述哪一条是顺序存储方式的优点？（）A．存储密度大 B.插入和删除运算方便C. 获取符合某种条件的元素方便D.查找运算速度快4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3)A．658 B．648 C．633 D．6535.下列关于二叉树遍历的叙述中，正确的是( ) 。
A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.k层二叉树的结点总数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.对线性表进行二分法查找，其前提条件是( ).A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.对n个记录进行堆排序，所需要的辅助存储空间为A. O（1og2n）B. O（n）C. O（1）D. O（n2）9.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有（）个，A．1 B．2 C．3 D．410.下列关于数据结构的叙述中，正确的是( ).A.数组是不同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法二、填空题（每空1分，共26分）1.数据的逻辑结构被分为_________、________、__________和___________四种。
