考试科目:《数据结构》第一章至第四章（总分100分） 时间：90分钟 ______________学习中心（教学点） 批次： 层次： 专业： 学号： 身份证号： 姓名： 得分： 一、选择题（每题3分，共30分） 1、（　　）是数据的不可分割的最小单位。 Ａ、数据元素　Ｂ、数据对象　Ｃ、数据项　Ｄ、数据结构 2、若采用顺序映象，则数据元素在内存中占用的存储空间（　　）。 Ａ、一定连续　Ｂ、一定不连续　Ｃ、可连续可不连续 3、下列说法中错误的是（　　）。 Ａ、栈是一种非线性结构 Ｂ、一个数据元素由一或多个数据项构成 Ｃ、在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来体现 Ｄ、语句的频度就是语句的执行次数 4、以下属单链表优点的是（　　）。 Ａ、顺序存取　Ｂ、插入操作能在O(1)的时间复杂度上完成 Ｃ、插入时不需移动数据元素　Ｄ、节省存储空间 5、顺序表中数据元素的存取方式为（　　）。 Ａ、随机存取　Ｂ、顺序存取　Ｃ、索引存取　Ｄ、连续存取 6、设输入序列为ABC，输出序列为CBA，则经过的栈操作为（　　）。 Ａ、push,pop,push,pop,push,pop　Ｂ、push,

数据结构 数据结构全文共3页，当前为第1页。数据结构全文共3页，当前为第1页。顺序表的插入操作 伪代码如下 数据结构全文共3页，当前为第1页。 数据结构全文共3页，当前为第1页。 如果表满了,则抛出上溢异常; 如果元素的插入位置不合理,则抛出位置异常; 将最后一个元素直至第i个元素分别向后移动一位置; 将元素x填入位置i处; 5.表长加一; 算法如下 void SeqList::Insert(int i,DataType x) { If(length>=MaxSize)throw"上溢"; If(i<1""i>length+1)throw"位置"; for(j=length;j>=i;j- -) { Data[j]=data[j-1]; } //注意第j个元素存在于数组下标为j-1处 Data[i-1]=x; length++; } 平均O(n) 顺序表的删除操作 伪代码如下 如果表空,则抛出下溢异常; 如果删除位置不合理,则抛出位置异常; 取出被删元素; 5.表长减一,返回被删元素值; 将下标i,i+1,...,n-1处的元素分别移到下标i-1,i,...,n-

数据结构.ppt该文档详细且完整，值得借鉴下载使用，欢迎下载使用，有问题可以第一时间联系作者~

线性数据结构部分： 一、填空题 1. 数据结构包括数据的逻辑结构、 数据的储存结构 和数据的运算三个方面。 2. 数据结构包括 逻辑结构 、数据的存储结构和数据的运算三个方面。 3. 在算法"正确"的前提下，评价算法主要有两个指标是：时间复杂度和 空间复杂度 。 4. 在算法"正确"的前提下，衡量算法效率的主要指标是： 时间复杂度 及空间复杂度。 5. 线性数据结构的逻辑特征是有且仅有一个 开始结点 和一个终端结点，且所有结点都最多只有一个直接前趋和一个 直接后继 。 6. 线性数据结构的逻辑特征是有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个 直接前趋 和一个直接后继。 7. 数据的存储结构包含有 顺序存储结构 、 链式存储结构 、 索引存储结构 和 散列存储结构 等四种基本的映像方法。 8. 数据存储结构的四种基本形式是： 顺序 存储结构、 链式 存储结构、索引存储结构以及散列存储结构。 9. 若频繁地对线性表进行插入与删除操作，该线性表应采用 链式 存储结构。 10. 线性链表中数据元素的组成：一是数据元素的值，二是直接后继元素的 地址的指针 ，这两部分信息组成数据

"题型( 单选:1, 不定项选择:2, 判断:3, 填空:4, 名词解释:5, 问答题:6, 计算题:7, 论述题:9, 证明题:10, 阅读理解:11, 完形填空:12, 作文题:13)",标题,题干 ,分值,"答案,(判断题:正确请输入T,错误则输入F;填空题如有多个空，请换行输入答案，换行请按alt+enter键。其它题型直接输入答案)",选项A,选项B,选项C,选项D,选项E,选项F,"难度（容易:0.75,一般:0.5,困难:0.25,也可在0~1区间自定义难度）" 1,常用查找算法的适用范围,顺序查找法适合于存储结构为（ ）的线性表。,2,B,散列存储,顺序存储或链接存储,压缩存储,索引存储,,,0.5 1,常用查找算法的适用范围,二分查找要求被查找的表是（ ）。,2,C,键值有序的链接表,链接表但键值不一定有序表,键值有序的顺序表,顺序表但键值不一定有序表,,,0.5 1,常用查找算法的适用范围,对于二叉排序树，以下说法错误的是（ ）,2,A,对一个二叉排序树进行先序遍历，可以得到一个递增序列,右子树上所有结点的值均大于根结点的值,左右二叉树也分别是二叉排序树,左子树上所

第五章 线性表和串习题 5.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实 现各基本运算时需要做那些修改？ 5.2试用顺序表表示较多位数的大整数，以便于这类数据的存储。请选择合适的存放 次序，并分别写出这类大数的比较、加、减、乘、除等运算，并分析算法的时间性能。 5.3试用顺序表表示集合，并确定合适的约定，在此基础上编写算法以实现集合的交 、并、差等运算，并分析各算法的时间性能。 5.4假设顺序表L中的元素递增有序，设计算法在顺序表中插入元素x，要求插入后仍 保持其递增有序特性，并要求时间尽可能少。 5.5假设顺序表L中的元素递增有序，设计算法在顺序表中插入元素x，并要求在插入 后也没有相同的元素，即若表中存在相同的元素，则不执行插入操作。 5.6设计算法以删除顺序表中重复的元素，并分析算法的时间性能。 5.7假设顺序表L中的元素按从小到大的次序排列，设计算法以删除表中重复的元素, 并要求时间尽可能少。要求： （1）对顺序表（1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9）模拟执行本算法，并统计 移动元素的次数。 （2）分析

第七章 树和二叉树习题 7.1画出由4个结点所构成的所有形态的树（假设是无序树）。 7.2已知一棵树的度为4，其中度为4的结点的数目为3，度为3的结点的数目为4，度为 2的结点的数目为5，度为1的结点的数目为2，请求出该树中的叶子结点的数目。 7.3如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右 孩子，求出该二叉树的结点数目。 7.4已知某完全二叉树有100个结点，试用三种不同的方法求出该二叉树的叶子结点数 。 7.5如果已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树 ，并指出结点数目最多的那棵完全二叉树的叶子结点数目。 7.6在编号的完全二叉树中，判断编号为i和j的两个结点在同一层的条件是什么？ 7.7设计算法以求解编号为i和j的两个结点的最近的公共祖先结点的编号。 7.8分别求出下图中二叉树的三种遍历序列。 7.9分别描述满足下面条件的二叉树的特征： （1）先序序列和中序序列相同。 （2）先序序列和后序序列相反。 7.10证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的 两个序列构造出相应的二叉树： 先序：A

第九章 查找习题 9.1若简单顺序查找算法所要查找的元素的下标从0开始，因而不能用监视哨，故查找 失败时要返回-1。试设计相应的算法。 9.2对有序数据表（5,7,9,12,15,18,20,22,25,30,100），按二分查找方法模拟查找 元素10和28，并分别画出其搜索过程。 9.3构造有20个元素的二分查找的判定树，并求解下列问题： （1）各元素的查找长度最大是多少？ （2）查找长度为1、2、3、4、5的元素各有多少？具体是哪些元素？（假设下标从0 开始） （3）查找第13个元素依次要比较哪些元素？ 9.4对有n个元素的有序表按二分查找方法查找时，最大的查找长度是多少？ 9.5设计算法以构造有n个元素（下标范围从1到n）的二分查找的判定树。 9.6判断题：若二叉树中每个结点的值均大于其左孩子的值，小于其右孩子的值，则 该二叉树一定是二叉排序树。 9.7分别以下列数据序列为输入构造二叉排序树，并计算出在等概率情况下的平均查 找长度。 （1）100，60，20，80，50，150，110，120，200，70，135 （2）90，80，40，160，155，50，20，30，10，

1.1 请说明算法具有哪些特性，各是什么含义？ 算法的一般性质包括：（1） 通用性 对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的 正确性.（2） 有效性 组成算法的每一条指令都必须是能够被人或机器确切执行的.（3） 确定性 算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于 下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.（4） 有穷性 算法的执行必须在有限步内结束. 2. 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数 据类型。 数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素（data element）：数据集合中的一个实体，是计算机程序中加工处理的基本单位。例如：一条 学生记录（包括学号、姓名、年龄等）就是一个数据元素数据对象（data object）：性质相同的数据元素的集合。是数据的一个子集。数据结构(data structure)：相互之间存在一种或多种关系的数据元素的集合。即包括数据元素的集合 和数据元素之间的关系的集合。存储结构：数据结构在计算

实验2 线性表的顺序储存结构实现 13081319 金晨 (3)设计线性表的接口函数"int MergeList(LIST &L1,LIST L2);"，把线性表L中的数据全部合并到线性表L1的尾部。其中，L1中有数据{1,2,3,4,5},L2中有数据{6,7,8,9,10};合并的结果为L1中包含数据{1,2,3,4,5,6,7,8,9,10}。 代码如下： //listInArray.h(此为顺序表的类型声明和操作接口声明) #include using namespace std; #define LISTSIZE 100 typedef int DataType; //声明DataType类型 typedef struct SqList { DataType items[LISTSIZE]; //存放线性表数据 int length; }LIST; //LIST为用户定义的线性表类型 void InitList(LIST &L); //初始化空线性表 int ListEmpty(LIST &L); //判断线性表是否为空 int ListLength(L