数据结构复习题.docx

一判断题（下列各题，正确的请在前面的括号内打；错误的打）第1章（）（1）数据的逻辑结构与数据元素本身的内容和形式无关。（）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（）（3）数据元素是数据的最小单位。（）（4）数据项是数据的基本单位。（）（5）数据的逻辑结构和数据的存储结构是相同的。（）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。（）（7）数据的物理结构是指数据在计算机内实际的存储形式。（）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（）（9）数据的存储结构是数据的逻辑结构的存储映像。（）（10）算法是对解题方法和步骤的描述。第2章（）（1）链表的物理存储结构具有同链表一样的顺序。（）（2）链表的每个结点都恰好包含一个指针域。（）（3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（）（4）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （）（6）数组元素的存储位置是下标的线性函数。（）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个元素。（）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。（）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。（）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。第3章（）（1）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。（）（2）快速排序在任何情况下都比其它排序方法速度快。（）（3）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。（）（4）如果某种排序算法不稳定，则该排序方法就没有实际应用价值。（）（5）对n个记录的进行快速排序，所需要的平均时间是O（nlog2n）。（）（6）冒泡排序是不稳定的排序。（）（7）冒泡排序的时间复杂度是O（n2）。（）（8）堆排序所需的时间与待排序的记录个数无关。（）（9）对快速排序来说，初始序列为正序或反序都是最坏情况。（）（10）对于n个记录的集合进行归并排序，所需的平均时间为O (nlog2n)。第4章（）（1）栈是运算受限制的线性表。（）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。（）（3）栈一定是顺序存储的线性结构。（）（4）空栈就是所有元素都为0的栈。（）（5）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。（）（6）一个栈的输入序列为：A，B，C，D，通过入出栈操作可以输出序列：A，B，C，D。（）（7）在C或C+语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。（）（8）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。（）（9）在栈中插入或删除一个元素应遵守的“后进先出”的原则。（）（10）进位制的换算算法是栈的应用。（）（11）队列是限制在两端进行操作的线性表。（）（12）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。（）（13）在链队列做出队操作时，会改变front指针的值。（）（14）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。（）（15）队列是一种“先进先出”的线性表。（）（16）在循环链队列中无上溢出现象。（）（17）栈和队列都是顺序存储的线性结构。（）（18）栈和队列都是属于线性结构。（）（19）顺序队和循环队的队满和队空的判断条件是一样的。（）（20）在队列中插入或删除一个元素应遵守的”先进先出”的原则。第5章（）（1）串的长度是指串中不同字符的个数。（）（2）串是n个字母的有限序列。（）（3）空串不等于空格串。（）（4）如果两个串含有相同的字符，则说明它们相等。（）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。（）（6）串的堆分配存储是一种动态存储结构。（）（7）“DT”是“DATA”的子串。（）（8）空串与空格串是相同的。（）（9）串中任意个字符组成的子序列称为该串的子串。（）（10）子串的定位运算称为模式匹配。（）（11）n维的多维数组可以视为n-1维数组元素组成的线性结构。（）（12）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。（）（13）若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（）（14）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中数据元素的行号、列号和值。（）（15）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数C。（）（16）对称矩阵、三角矩阵、稀疏矩阵都可以进行压缩存储。（）（17）任何矩阵都可以进行压缩存储。（）（18）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中非零元素的行号、列号和值。（）（19）数组元素可以由若干个数据项组成。（）(20）稀疏矩阵压缩存储就是为矩阵中非零元素分配一个存储空间。第6章（）（1）树结构中每个结点最多只有一个直接前驱。（）（2）完全二叉树一定是满二查树。（）（3）由树转换成二叉树，其根结点的右子树一定为空。（）（4）在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。（）（5）用一维数组来存储二叉树时，总是以前序遍历存储结点。（）（6）已知二叉树的前序遍历和后序遍历并不能唯一确定这棵二叉树，因为不知道根结点是哪一个。（）（7）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（）（8）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（）（9）不使用递归，也可以实现二叉树的前序、中序和后序遍历。（）（10）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。第7章（）（1）图可以没有边，但不能没有顶点。（）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。（）（3）邻接表只能用于有向图的存储。（）（4）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。（）（5）一个图的邻接矩阵表示是唯一的。（）（6）有向图不能进行广度优先遍历。（）（7）一个图的最小生成树是该图所有生成树中权最小的生成树。（）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。（）（9）有向图的邻接矩阵一定是对称的。（）（10）一个图的深度优先遍历的序列是唯一的。第8章（）（1）二分查找法要求待查表的关键字值必须有序。（）（2）哈希法是一种将关键字转换为存储地址的存储方法。（）（3）在二叉排序树中，根结点的值都小于孩子结点的值。（）（4）对有序表而言采用二分查找总比采用顺序查找法速度快。（）（5）二叉排序树是一种特殊的线性表。（）（6）散列存储法的基本思想是由关键字的值决定数据的存储地址。（）（7）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。（）（8）一般说来用哈希函数得到的地址，冲突不可能避免，只能尽可能减少。（）（9）选择好的哈希函数就可以避免冲突的发生。（）（10）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。二填空题第1章1数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的 关系 和运算的学科。2数据的存储结构形式包括：顺序存储、链式存储、 散列存储 、索引存储 。3数据结构按逻辑结构可分为两大类，它们分别是：线性结构和 非线性 结构。4一个算法的空间复杂度是指该算法所耗费的 存储空间 ，它是该算法求解问题规模n的函数。5数据结构有逻辑结构和 存储结构 两种结构。6数据的存储结构形式包括：顺序存储、链式存储、散列存储、 索引存储 。7一个算法的效率可分为 时间 效率和空间效率。8数据元素是数据的 基本单位 。9数据结构主要研究数据的 逻辑结构 、存储结构和算法。11数据的 逻辑结构 是独立于计算机的。12数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的 关系 的有限集合。13树形结构结构中的元素之间存在 一对多 的关系。14若一个算法中的语句频度之和为T（n）=125n+3nlog2n，则算法的时间复杂度为 O（nlog2n） 。15数据结构主要研究数据的逻辑结构、 存储结构 和算法。第2章1顺序表中逻辑上相邻的元素在物理位置上 必须 相连。2在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O (n) 。3线性表是n个结点的 有限 集合。4链表相对于顺序表的优点有 插入、删除 方便；缺点是存储密度小。5链表相对于顺序表的优点有插入、删除方便；缺点是存储密度 小 。6顺序表相对于链表的优点是： 节省存储 和随机存取。7对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是 O（1） 。8在链表中逻辑上相邻的元素的物理位置 不必 相连。9线性表中第一个结点没有直接前趋，称为 开始 结点。10在顺序表中访问任意一个结点的时间复杂度均为 O (1) 。11在n个结点的单链表中要删除已知结点*P，其时间复杂度为 O (1) 。12在单链表中需知道 头指针 才能遍历整个链表。13在一个单链表中，在指针p所指向的结点之后插入指针s所指向的结点时，应执行s-next=p-next和p-next=s 操作。14在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移 n- i +1 个元素。 15在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其 后继 结点。第3章1 根据被处理的数据在计算机中使用不同的存储设备，排序可分为： 内排序 和外排序。2 评价排序算法优劣的主要标准是 时间复杂性 和算法所需的附加空间。3插入排序、堆排序、归并排序中，排序是不稳定的有： 堆排序 。4在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。5对n个关键字进行冒泡排序，其可能的最小比较次数为： n-1 次。6内排序是指整个排序过程，全部在计算机的 内存 中进行。7大多数排序算法都有两个基本的操作： 比较 和移动。8在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序 较好。9在排序前，关键字值相等的不同记录，排序后相对位置变化的排序方法，称为 不稳定 的排序方法。10若原始数据接近无序，则选用 快速排序 最好。11对于n个记录的集合进行归并排序，所需要的平均时间为： O（log2n） 。12在插入排序、归并排序、快速排序中，排序是不稳定的有： 快速排序 。13对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是 54，72，60，96，80 。14对于n个记录的集合进行，若对其进行快速排序，在最坏的情况下所需要的时间是 O(n2) 。15在最坏情况下，在第i趟直接插入排序中，要进行 i-1 次关键字的比较。第4章1在栈中存取数据遵从的原则是： 后进先出 。2在有n个元素的栈中，进栈操作的时间复杂度为 O（1）。3后进先出的线性表称为 栈 。4在顺序栈中，当top=MAXLEN-1时，表示 栈满 。5. 栈是输入、输出受限制的 线性表 。6在有n个元素的栈中，出栈操作的时间复杂度为 O（1）。7在栈结构中，允许插入、删除的一端称为 栈顶 。8顺序栈S存在数组S-data0.MAXLEN-1中，出栈操作时要执行的语句有：S-top - 。9在顺序栈中，当栈顶指针top=-1时，表示 栈空 。10向一个栈顶指针为top的链栈插入一个新结点*p时，应执行 p-next=top； 和top=p； 操作。11同一栈的各元素的类型 相同 。12栈只能在 栈顶 插入和删除元素。13已知顺序栈S，在对S进行出栈操作之前首先要判断 栈是否空 。14若进栈的次序是A、B、C、D、E，执行三次出栈操作以后，栈顶元素为 B 。15从一个栈删除元素时，首先取出栈顶元素，然后再移动 栈顶指针 。16在队列中存取数据应遵从的原则是 先进先出 。17设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O（n）。18在队列中，允许插入的一端称为 队尾 。19设长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为 0（1） 。20设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队空的标志为 front=rear 。21队列在进行出队操作时，首先要判断队列是否为 空 。22设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为 front=(rear+1)% MAXLEN 。23在一个链队列中，若队头指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为： front=rear & front NULL 。24队列结构的元素个数是 可变的 。25设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 0（1） 。26设长度为n的链队列用单循环链表表示，若只设尾指针，则入队操作的时间复杂度为 0（1） 。27链队列为空时，LQ-front-next= NULL 。28设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，当rearfront时，队列长度是 MAXLEN-front 。29向一个循环队列中插入元素时，首先要移动队尾指针，然后再向指针所指位置 写入 新的元素。30队列Q经过InitQueue (Q)；InQueue (Q，a)； InQueue (Q，b)；GetHead (Q，x)后，x的值是 a 。第5章1长度为零的字符串称为 空串 。2在串的运算中，EqualStr(aaa，aabb)的值为 0 。3串的顺序存储结构简称为 顺序串 。4串的链式存储结构简称为 链式串 。5求子串函数SubStr(Today is 30 July,2005,13,4)的结果是： July 。6设S=A:/document/mary.doc，则len(s)= _ 20 。7由零个或多个字符组成的有限序列称为 字符串 （或串）。8字符串按存储方式可以分为：顺序存储、链接存储和 堆分配存储 。9设S=“A:/mydocument/text1.doc”，则strlen(S)= 23 。10在空串和空格串中，长度不为0的是 空格串 。11串顺序存储紧凑格式的优点是： 空间利用率高 ,对串的字符处理效率低。12两个串相等是指两个串相长度等，且对应位置的 字符都相同 。13串顺序存储紧凑格式的缺点是对串的字符处理 效率低 。14模式匹配成功的起始位置称为： 有效位移 。15所有模式匹配不成功的起始位置称为： 无效位移 。16.多维数组的顺序存储方式有行优先顺序存储和 列优先顺序存储 两种。17.同一数组中各元素的长度 相等 。18.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种 随机 存取结构。19. 在n维数组中的每一个元素最多可以有 n 个直接前驱。20.输出二维数组Amn中所有元素值的时间复杂度为 O(m*n) 。数组元素a0.20.3的实际地址上2000，元素长度是4，则Loc1,2=2024 。21.数组的三元组存储是对 稀疏矩阵 的压缩存储22.稀疏矩阵的三元组有 3 列。23.稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的 行数 。24.n阶对称矩阵，如果只存储下三角元素，只需要 n（n-1）/2 个存储单元。25.稀疏矩阵A如下图所示，其非零元素存于三元组表中，三元组（4，1，5）按行优先顺序存储在三元组表的第 6 项。8 0 0 0 0 00 11 0 0 0 00 0 0 6 0 00 3 0 07 0 0 5 0 00 00 0 0 09 0稀疏矩阵AA=26.稀疏疏矩阵的压缩存储方法通常有三元组表和 十字链表 两种。27 n阶下三角矩阵，因为对角线的上方是同一个常数，需要 n（n-1）/2+1 个存储单元。28稀疏矩阵中有n个非零元素，则三元组有 n 行。29.稀疏矩阵的三元组中第2列存储的是数组中非零元素所在的 列数 。30.稀疏矩阵的三元组中，第3列存储的是稀疏数组中的 非零元素 。第6章1在树中，一个结点所拥有的子树数称为该结点的 度 。2一棵含有n个结点的完全二叉树，它的高度是 | log2n |+1 。 （下取整）3度为零的结点为 叶子结点（或叶结点） 。4一棵深度为h的完全二叉树上的结点总数最少为 2 h-1 个。5树内各结点度的最大值称为 树的度 。6一棵深度为h的完全二叉树上的结点总数最多为 2 h-1 个。7树中结点的最大层次称为树的 深度（或高度） 。8三个结点可以组成 2 种不同形态的树。9由树转换成二叉树时，其根结点没有 右子树 。10有20个结点的完全二叉树，编号为10的结点的左儿子结点的编号是 20 。11在树中，一个结点的直接子结点的个数称为该结点的 度 。12由二叉树的后序和 中序 遍历序列，可以唯一确定一棵二叉树。13给定如下图所示的二叉树，其前序遍历序列为： ABEFHCG 。ABFGHDCE14给定如下图所示的二叉树，其层次遍历序列为： ABCEFGH 。ABFGHDCE15将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，该结点右孩子的编号为： 2*i+1 。第7章1图有： _邻接矩阵_ 和邻接表等存储结构。2n个顶点e条边的图若采用邻接矩阵存储，深度优先遍历算法的时间复杂度为： O（n2） 。3图的遍历有：深度优先搜和 _广度优先搜 _等方法。4n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为： _ O（n2）_。5图有：邻接矩阵和 邻接表 等存储结构。6若图G中每条边都 _无 方向，则G为无向图。7在具有n个顶点的图的生成树中，含有 n-1 条边。8有向图的边也称为 _弧_ 。9图的邻接矩阵表示法是表示 _顶点_之间相邻关系的矩阵。10有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 _出度_。11图的深度优先遍历序列 _不是_唯一的。12设有一稀疏图G，则G采用 _邻接表_存储比较节省空间。13从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历（或遍历） 。14遍历图的两种基本方法是： 深度优先遍历 和广度优先遍历。15有向图的邻接表表示适于求顶点的 出度 。第8章1顺序查找法，表中元素可以 任意 存放。2 散列表 查找法的平均查找长度与元素个数n无关。3快速排序是对 冒泡 排序的一种改进。4在哈希函数H(key)=key % P中，P一般应取 质数 。5二分查找的存储结构仅适用于 顺序存储 结构，而且关键字有序的。6在分块查找方法中，首先查找 索引 ，然后再查找相应的块。7二分查找法，表中元素必须按关键字 有序 存放。8在分块查找方法中，表中元素每块内的元素可以 任意存放 ，块与块之间必须有序存放。9顺序查找、二分查找、分块查找都属于 静态 查找。10顺序查找法，其平均查找长度为： (n+1)/2 。11理想情况下，在散列表中查找一个元素的时间复杂度为： O（1） 。12散列表的查找效率主要取决于散列表造表时选取的散列函数和 处理冲突 的方法。13二叉排序树是一种 动态 查找表。14处理冲突的两类主要方法是开放定址法和 拉链法 （或链地址法） 。15设有100个元素，用二分查找时，最少的比较次数是 1 次。三选择题第1章1数据结构通常是研究数据的（ A ）及它们之间的相互联系。 A. 存储结构和逻辑结构 B. 存储和抽象 C. 联系和抽象 D. 联系与逻辑2执行下列语句的时间复杂度为：（ B ）。s=0;for (i=1;i=n; i+) s=s+i; A. O（1） B. O（n） C. O（n2） D. O（n3）3数据结构中，在逻辑上可以把数据结构分成：（ C ）。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构4某程序的时间复杂度为（3n+log2n+n2+15）其数量级表示为（ B ） A. O（n） B. O（n2） C. O（log2n） D. O（nlog2n）5非线性结构的数据元素之间存在（ B ）。 A. 一对多关系 B. 多对多关系 C. 多对一关系 D. 一对一关系6下列时间复杂度中最坏的是（ D ） A. O（1） B. O（ n） C. O（log2n） D. O（n2）7以下任何两个结点之间都没有逻辑关系的是（ D ） A. 图型结构 B. 线性结构 C. 树型结构 D. 集合8链接存储的存储结构所占存储空间（ A ）。 A 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针 B 只有一部分，存放结点值 C 只有一部分，存储表示结点间关系的指针 D 分两部分，一部分存放结点值，另一部分存放结点所占单元素9一个存储结点存放一个（ B ） A. 数据项 B. 数据元素 C. 数据结构 D. 数据类型10下列时间复杂度中最好的是（ A ） A. O（1） B. O（ n） C. O（log2n） D. O（n2）11每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（ B ）存储方式 A. 顺序 B. 链式C. 索引 D. 散列12下列算法的实际复杂度是（ D ） for (i=0;in;i+) for (j=0;in;j+) cij=i+j; A. O（1） B. O（ n） C. O（log2n） D. O（n2）13数据元素是数据的基本单位，其内（ B ）数据项。 A. 只能包括一个 B. 可以包括多个 C. 不包括 D. 可以包括也可以不包括14. 数据结构中，与所使用的计算机无关的是数据的（ C ）结构；A. 存储 B. 物理 C. 逻辑 D. 物理和存储15数据的逻辑结构是（ A ）关系的整体A. 数据元素之间逻辑 B. 数据项之间逻辑C. 数据类型之间 D. 存储结构之间第2章1用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是（ B ）。A 当前结点所在地址域 B 指针域 C 空指针域D 空闲域2在具有n个结点的单链表中，实现（ A ）的操作，其算法的时间复杂度都是O（n）。A遍历链表和求链表的第i个结点B在地址为P的结点之后插入一个结点C删除开始结点D删除地址为P的结点的后继结点3设a，b，c为三个结点，p，10，20，代表地址，则如下存储结构称为（ B ）。a 10 c b 20 PA 循环链表 B 单链表 C双向循环链表 D 双向链表4已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址B，则第i个结点的地址为（ A ）。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m5单链表的存储密度（ C ）。 A 大于1 B 等于1 C小于1 D 不能确定6在n个结点的顺序表中，算法的时间复杂度是O (1)的操作是（ A ）。A 访问第i个结点(1=i-n)和求第i个结点的直接前驱(2=i=n)B 在第i个结点之后插入一个新结点(1=i=n)C 删除第i个结点(1=inext= = P CP-next= = NULL DP-next= = L9一维数组和线性表的区别是（ A ）。A 前者长度固定，后者长度可变 B 后者长度固定，前者长度可变C 两者长度都固定 D 两者长度都可变10指针P所指的元素是双循环链表L的尾元素的条件是（ D ）。AP= = L BP-prori= = L CP= = NULL DP-next= =L11一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）A110 B108 C100 D12012两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（ ）。AP-next= =Q-next BP-next= = QCQ-next= = P DP= = Q13向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B ）个元素。A8 B63.5 C63 D714用链表存储的线性表，其优点是（ C ）。A 便于随机存取 B 花费的存储空间比顺序表少C 便于插入和删除 D 数据元素的物理顺序与逻辑顺序相同15单链表的示意图如下： LABCD P Q R 指向链表Q结点的后继的指针是（ D ）AL BP CQ DR第3章1每次从无序表中取出一个元素，把它插入到有序表中的适当位置，这种排序方法叫（ C ）。 A选择 B交换 C插入 D归并2快速排序方法在（ C ）情况下最不利于发挥其长处。 A要排序的数据量太大 B要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数3排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为: ( D )。A希尔排序 B归并排序 C插入排序 D. 选择排序4在待排序的元素序列基本有序的前提下，效率最高的排序方法是：（ A ）。A直接插入 B冒泡排序 C希尔排序 D选择排序5每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（ C ）。A冒泡排序 B堆排序 C快速排序 D. 归并排序6排序是根据（ A ）的大小重新安排各元素的顺序。 A关键字 B数组 C元素件 D结点7堆的形状是一棵（ D ）。A二叉排序树 B满二叉树 C不是二叉树 D. 完全二叉树8稳定的排序方法是指在排序前后，关键字值相等的不同记录间的前后相对位置（ B ）。 A保持相反 B保持不变 C不定 D无关9下述几种排序方法中，要求内存量最大的是：（ D ）。 A插入排序 B选择排序 C快速排序 D. 归并排序10直接插入排序的方法是（ B ）的排序方法。 A不稳定 B稳定 C外部 D选择11直接插入排序的方法要求被排序的数据（ B ）存储。 A必须链表 B必须顺序 C顺序或链表 D可以任意12设有1000个无序元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（ B ）排序法。A冒泡排序 B堆排序 C快速排序 D. 归并排序13用快速排序法对n个元素进行排序时，最坏情况下的执行时间为（ A ）AO（n2） BO（log2n） CO（nlog2n） D. O（n）14一个数据序列的关键字为：（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：（ C ）A （38，40，46，56，79，84） B（40，38，46，79，56，84） C（40，38，46，56，79，84） D（40，38，46，56，79，84）15用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ D ）。 A选择排序 B希尔排序 C归并排序 D.快速排序第4章1顺序栈判空的条件是（ C ） Atop=0 Btop=1 Ctop=-1 Dtop=m2设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，下列不可能的出站顺序为 ( D ) A1234 B1243 C1324 D14233插入和删除只能在一端进行的线性表，称为( C )。 A队列 B循环队列 C栈 D循环栈4链栈与顺序栈相比，有一个比较明显的优点是（ B ）。A插入操作根加方便 B通常不会出现栈满的情况。C不会出现栈空的情况 D删除操作根加方便5在栈中，出栈操作的时间复杂度为( A )。 AO(1) BO(log2n) C0(n) DO(n2)6带头结点的链栈LS的示意图如下，栈顶元素是（ A ） LSHABCD AA BB CC DD7元素A,B,C,D依次进栈以后，栈顶元素是（ D ） AABB CC DD8顺序栈存储空间的实现使用（ B ）存储栈元素。 A链表B数组 C循环链表 D变量9在C或C+语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ）。 A已固定 B不固定 C可以改变 D动态变化10当栈中的元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为（ C ）。 An-1 Bn+1 Cn Dn/211栈与一般线性表的区别在于 ( B )。 A数据元素的类型不同 B运算是否受限制 C数据元素的个数不同 D逻辑结构不同12设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B，D，C，F，E，A，则栈的容量至少应是 ( A )。 A3 B4 C5 D 613在栈顶一端可进行（ D ）操作。 A插入 B删除 C进栈 D插入和删除14从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 ( D )命令。 Ax=top;top=top-next; Btop=top-next;x=top-data; Cx=top-data; Dx=top-data;top=top-next;15在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列 ( B )命令。 AHS-next=S; BS-next=HS-next;HS-next=S; CS-next=HS-next;HS=S; DS-next=HS;HS=HS-next;16在队列中存取数据应遵循的原则是( A )。 A先进先出 B后进先出 C先进后出 D随意进出17设长度为n的链队列用单循环链表表示，若只设头指针，则人队操作的时间复杂度为( C )。 AO(1) BO(log2n) CO(n) DO(n2)18一个循环队列一旦说明，其占用空间的大小（ A ）。 A已固定 B可以变动 C不能固定 D动态变化19当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（ B ）。 An-2 Bn-1 Cn Dn+120设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为( A )。 AO(1) BO (log2n) CO(n) DO(n2)21队列是限定在（ D ）进行操作的线性表。 A中间 B队头 C队尾 D端点22若进队的序列为：A，B，C，D，则出队的序列是（ C ）。 AB，C，D，ABA，C，B，D CA，B，C，DDC，B，D，A23从一个顺序循环队列删除一个元素时，首先需要做的操作是（ B ）。 A队头指针减1 B取出队头指针所指的元素 C队头指针加1 D取出队尾指针所指的元素24. 在一个顺序存储的循环队列中，队头指针指向队头元素的（ A ）位置。 A前一个 B后一个 C后面 D当前25四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队头元素是（ B ）。 A AB B C C D D26队列中的元素个数是( B )。 A不变的B可变的C任意的D027设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（ A ）操作。 As-next=top-next；top-next=sBtop-next=s Cs-next=top；top=top-nextDs-next=top；top=s28若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( B )。 A5和1 B4和2 C2和4 D1和529以下属于队列的操作有( D )。 A在队首插入元素 B删除值最小的元素 C按元素的大小排序 D判断是否还有元素30.带头结点的链队列LQ示意图如下，LQ为空时（ A ） LQ-frontHABCD LQ-rearALQ-front= LQ-rear BLQ-rear=NULLCLQ-front!= LQ-rear DLQ-front=null第5章1串是一种特殊的线性表，其特殊性体现在（ B ）。A.可以顺序存储 B数据元素是一个字符C.可以链接存储 D数据元素可以是多个字符2设目标串T=AABBCCDDEEFF，P=CCD，则该模式匹配的有效位移为 ( C )。A2 B3 C4 D. 53设有两个串p和q，求q在p中首次出现的位置的运算称作( B )。 A.连接 B模式匹配 C.求子串 D求串长4. S1=sdudent，S2=SDUDENT，执行串比较函数EqualStr(S1,S2) 后的结果为( C )。 A0 B小于0 C大于0 D不确定5串的模式匹配是指（ D ）。A判断两个串是否相等B对两个串比较大小C找某字符在主串中第一次出现的位置D找某子串在主串中第一次出现的第一个字符位置6朴素模式匹配算法在最坏情况下的时间复杂度是( D )。 AO（m） BO（n） C0（m+n） D0（m*n）7以下论断正确的是( A )。 A是空串， 空格串 BBEIJING是BEI JING的子串 CsomethingSomethig DBIT=BITE8. S1=Today is，S2=30 July 2005，执行串连接函数ConcatStr(S1,S2)后的结果为( A )。 AToday is 30 July 2005 B30 July 2005 CToday is D30 July 2005 Today is9某串的长度小于一个常数，则采用（ B ）存储方式最节省空间。 A链式 B顺序 C堆结构 D无法确定10. S=Today is 30 July 2005，LenStr(S)=( D )。 A18 B19 C20 D2111设有两个串S1和S2，则EqualStr(S1,S2)运算称作( D )。 A. 串连接 B模式匹配 C. 求子串 D串比较12. S1=good，S2=morning，执行串连接函数ConcatStr(S1,S2)后的结果为( A )。 Agoodmorning Bgood morning CGOODMORNING DGOOD MORNING13在实际应用中，要输入多个字符串，且长度无法预定，则应该采用（ C ）存储方式比较合适。 A链式 B顺序 C堆结构 D无法确定14. 设串S1=I AM，S2=A SDUDENT,则ConcatStr(S1,S2)=( B )。 AI AM BI AM A SDUDENT CIAMASDUDENTD. A SDUDENT15. 以下论述正确的是（ C ）。 A空串与空格串是相同的Btel是Teleptone的子串 C空串是零个字符的串