全国计算机等级考试解析例题精解与应试模拟三级数据.pdf

第2章数据结构与算法※本章大纲要求：( 1 )基本概念( 2 )线性表( 3 )多维数组、稀疏矩阵和广义表( 4 )树形结构( 5 )查找( 6 )排序※重要考点提示：根据对历年真题的分析可知，本章考核内容约占1 5 % ,主要包括以下几个方面：( 1 )数据结构和算法的基本概念( 2 )数据的逻辑结构、存储结构( 3 )顺序表和一维数组( 4 )链表、栈、队列、串的概念与操作( 5 )稀疏矩阵的存储、广义表的定义与存储( 6 )二叉树的定义、存储与表示、线索二叉树( 7 )树与二叉树的转换、二叉树的周游算法( 8 )霍夫曼算法及其应用( 9 )静态表、动态表的查找( 1 0 )各种排序算法，插入排序、选择排序、交换排序、归并排序2.1基 本 概 念考点1 ：数据结构的基本概念*( 1 ) 数据数据就是采用计算机能够识别、 存储和处理的方式， 对现实世界的事物进行的描述， 简而言之,数据就是计算机化的信息数据元素是数据的基本单位一个数据元素可由一个或多个数据项组成，数据项是有独立含义的数据最小单位 2 ) 数据结构数据结构一般包括3 个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式以及在这些数据上定义的运算的集合。

a . 数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式数据的逻辑结构分为线性结构和非线性结构b . 数据的存储结构是逻辑结构在计算机存储器里的实现c . 数据的运算定义在数据的逻辑结构上，而实现是在存储结构上主要的运算包括插入、删除、排序、查找等考点2：主要的数据存储方式*实现数据的逻辑结构到计算机存储器的映像有多种不同的方式最主要的存储方式有顺序存储储结构和链式存储方式 1 ) 顺序存储结构顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元中，结点之间的关系由存储单元的邻接关系来体现，其主要特点是：a . 结构中只有自身信息域，没有链接信息域，因此，存储密度大，存储空间利用率高；b . 可以通过计算直接确定数据结构中第i 个结构的存储地址；c . 插入、删除运算会引起大量结构的移动 2 ) 链式存储结构链式存储结构是在每个结点中至少包括一个指针域，用指针来体现数据元素之间逻辑上的联系其主要特点是：a . 存储密度小，存储空间利用率低；b . 逻辑上相邻的结点物理上不必邻接，可用于线性表、树、图等多种逻辑结构的存储表示；c . 插入、删除操作灵活方便，不必移动结点。

考点3：算法的设计与分析算法的设计采用由粗到细、由抽象到具体的逐步求精的方法算法分析主要是分析算法所要占用的计算机资源，即时间代价和空间代价两个方面a . 时间代价是当问题的规模以某种单位由1增至n 时解决该问题的算法运行时所耗费的时间，也以某种单位由f(l)增至f(n ),则称该算法的时间代价为f(n)b . 空间代价是当问题的规模由1 增 至 n 时，解决该问题的算法实现时所占用的空间也以某种单位由g(l)增至g (n ),则称该算法的空间代价为g(n)o2 . 2线性表考点4：顺序表和一维数组线性表的逻辑结构是〃个数据元素的有限序列( 切, 〃2” ..,东) 按存储方式不同线性表可以分为:顺序存储的顺序表、链式存储的链表、散列存储的散列顺序表是用一组地址连续的存储单元依次存储数据元素的线性表，其逻辑相邻的数据元素具有相邻的物理( 存储) 位置对数据元素进行插入、删除操作时需要移动数据元素，存储空间被分配后难以再被扩充各种高级语言中的一维数组就是用顺序方式存储的线性表，因此也常用一维数组来称呼顺序表考点5：链表*链表的特点是可以用一组任意的存储单元来存储线性表的各个数据元素，不要求逻辑上相邻的元素物理上也相邻。

链表的优点是插入、 删除等操作不需要移动元素，只需要修改指针，比较灵活,缺点是不能随机存取链表可以分为线性链表和双向链表两种，前者也称为单链表，每个结点中只有一个指向后一个结点的指针；后者每个结点有两个指针，一个指向直接前驱结点，一个指向直接后继结点考点6：栈与队列安栈与队列都是对操作位置加以限制的线性表可以使用顺序存储也可以采用链式存储栈的插入和删除只能发生性表的一端，允许插入、删除的这一端称为栈顶，另一个固定端称为栈底当表中没有元素时称为空栈栈是按“ 后进先出”的规则进行操作的栈的常用运算主要包括入栈( p u s h ) 、出 栈 ( p o p ) 和取栈顶元素( t o p ) 栈是使用最为广泛的数据结构之一，表达式求值、递归过程实现都是栈应用的典型例子队列的插入只能性表的一端进行，而删除性表的另一端进行，允许插入的一端叫队尾( r e a r ) , 允许删除的一端叫队头( f r o n t ) 队列是按“ 先进先出”的规则进行操作的队列常用的运算有入队( e n q ) 、出 队 ( d e q ) 和取队首元素( f r o n t ) ,队列在计算机中应用也十分广泛，硬件设备中的各种排队器、缓冲区的循环使用技术、操作系统中的作业队列等都是队列应用的例子。

考点7：串串( 或字符串) 是由零个或多个字符组成的有限序列，零个字符的串是空串串的存储方式有:顺序存储和链式存储顺序存储时可以采用非紧缩方式，也可以采用紧缩方式串的基本运算有连接、赚值、求长度、全等比较、求子串、求子串位置以及替换等其中找子串位置( 也称模式匹配) 是非常重要的一种运算2 . 3多维数组、稀疏矩阵和广义表考点8：多维数组的线性存储*多维数组是一维数组的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型多维数组中最常用的是二维数组多维数组的存储方式一般是多维数组中的元素放在一个线性序列中，排列方式可以是行优先顺序或列优先顺序二维数组第i 行、第 j 列元素a” 存储地址的计算公式为：行优先顺序：L O C ( aij) = L 0 C ( an ) + ( ( i- 1 ) * n + ( j- 1 ) )列优先顺序：L O C ( au ) = L 0 C ( aH) + ( ( j- 1 ) * m+ ( i- D ) * 九式中m 和 n分别为数组中每列和每行的元素个数，入为每个数组元素占用的存储单元个数考点9：稀疏矩阵的存储具有大量0元素的矩阵称为稀疏矩阵。

对稀疏矩阵进行压缩存储，即只存储非0元素对非0元素的分布有规律的矩阵，如下三角矩阵，按行优先顺序存储，非零元素的存储地址用下式计算：L O C ( a“ ) = L 0 C ( an ) + ( i* ( i- 1 ) / 2 + ( j- 1 ) )对一般的稀疏矩阵，可以采用三元组方法或十字链表方法存储前者是按行优先顺序存储非零元素所在的行、列以及它的值构成的三元组，后者则采用十字链表考点10：广义表的定义和存储广义表是线性表的推广，也称为列表，是由零个或多个单元素或子表所组成的有限序列广义表与线性表的区别在于：线性表的成分都是结构上不可分的单元素，而广义表的成分既可以是单元素，又可以是有结构的表广义表的特征：广义表的元素可以是子表，而子表的元素还可以是子表广义表可被其他广义表所共享广义表可以是递归的表，即广义表也可以是本身的一个子表2 . 4树形结构考点11：树及二叉树的定义及表示*树是一个或多个结点组成的有限集合T,有一个特定的结点称为根，其余结点分为m ( m 2 O )个不相交的集合T l， T 2 , …， T m 每个集合又是一棵树，被称为这个根的子树这是树的递归定义。

树的性质有以下4条：( 1 ) 树中的结点数等于所有结点的度数加1 2 ) 度为k 的树中第i层上至多有k -个结点( 泛1 ) 3 ) 深度为h 的 k 叉树至多有( kh- l) / ( k- l) 个结点 4 ) 具有n个结点的k 叉树的最小深度为「 lo gk( n ( k- l) + l) l二叉树是树形结构的一个重要类型二叉树是结点的有限集合，这个有限集合或者为空集，或者由一个根结点及两棵不相交的分别称做这个根的左子树和右子树的二叉树组成二叉树不是树的特殊情况，树与二叉树之间最主要的区别是：二叉树的子树有左右之分，其次序不能颠倒，即使是在只有一棵子树的情况下也要明确指出该子树是左子树还是右子树在一棵二叉树中，如果最多只有最下面两层结点度数可以小于2,并且最下面一层结点都集中在最左边的位置上，这样的一棵二叉树称为完全二叉树树与二叉树可以互相转化，树( 树林) 转换为二叉树的算法：在一棵树中，凡是兄弟结点就用线连起来，然后去掉父结点到子结点的连线，只保留父结点到第一个子结点的连线如果把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟结点，则同样可以导出森林与二叉树的对应关系。

把二叉树转换为树的算法：若某结点是其双亲的左孩子，则把该结点的右孩子，右孩子的右孩子……，都与该结点双亲用线连起来，最后去掉所有的双亲到右孩子的连线考点12：二叉树与树的周游*遍历一个树形结构就是按一定的次序系统地访问树上的所有结点，使每个结点恰好被访问一次由二叉树的定义可知，一棵二叉树由3部分组成：根、左子树和右子树因此对二叉树的遍历也可相应地分为3 类 先 序 ( 根 ) 遍 历 、中序( 对称序) 遍历、后 序 ( 根 ) 遍 历 先序遍历：访问根结点；先序遍历左子树；先序遍历右子树中序( 对称序) 遍历：中序遍历左子树；访问根结点；中序遍历右子树后序遍历：后序遍历左子树；后序遍历右子树；访问根结点由于树也是一种层次结构，所以对树有时也进行按层遍历，所谓按层遍历，就是从树根结点开始，依次访问每一层，对同一层结点，由左至右进行访问树和森林的遍历也主要有三种：先根次序、后根次序和层次次序其中，前两种是按深度优先方式进行的，后一种是按广度优先方式进行的根据树和二叉树的对应关系，可以看出，按先序遍历树正好等同于按先序遍历对应的二叉树；按后序遍历树正好等同于按对称序法遍历对应的二叉树考点13：二叉树的存储与线索二叉树( 1 )二叉树的L l i n k - r l i n k法存储二叉树通常的存储方式是链式存储，每个链结点除了数据域外，还可以增加两个指针域l l i n k和r l i n k ,分别指向左右两个子结点。

当某个结点的子结点不存在时，相应的指针值为空( n i l ) 2 )线索二叉树一个具有n个结点的二叉树若采用二叉链表存储结构，在2 n个指针域中只有n - 1个指针域是用来存储结点孩子的地址的， 而另外n + 1个指针域存放的都是n i l 为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的这n + 1个空指针域来记录这些信息这些指向直接前驱结点和指向直接后继结点的指针被称为线索( t h r e a d ) ,加了线索的二叉树称为线索二叉树 3 )完全二叉树的顺序存储二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点一般是按照二叉树结点从上至下、从左到右的顺序存储完全二叉树或者满二叉树比较适合于顺序存储考点14：霍夫曼算法及其应用*霍 夫 曼( H u f f m a n )树，也称为最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树设二叉树具有n个带权值的叶结点，那么从根结点到各 个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为：W P L = ^WkLkk = l其中Wk为第k个叶结点的权值，L k为第k个叶结点的路径长度。

最优二义树算法为： 对于n个权为w2, w3, w ”的结点， 首选找出两个最小的叱值，不妨设为W］和W2,然后对m - 1个权W 1 + W2，W 3 , 来解这个问题，并且将解中的代替，如此进行下去，直到所有的W构成一棵二叉树给定一组权值，构造出来的霍夫曼树不是唯一的在霍夫曼树中，权值大的结点离根最近另外，在霍夫曼树中，没有度为1的结点2 . 5查找考点15：线性表的查找查找是确定一个元素在表或树中的位置，衡量一个查找算法的标准是对关键码平均比较的次数，或称为平均检索长度A S L对于线性表的查找主耍分下面几种：( 1 )顺序查找顺序查找是线性表的最简单的查找方法，其具体步骤是：用待查关键码从头开始逐个与表中元素比较，直到找出相等的元素，则查找成功；或者找遍所有元素，则查找失败顺序查找的优点：对线性表的结点的逻辑次序无要求，对线性表的存储结构无要求顺序查找的缺点：平均检索长度长，与表中结点个数n成正比，若检索关键码的概率相等，则查找成功时平均比较次数为( n+ l ) / 2 查找不成功时；关键码的比较次数总是n+ 1 次 2 ) 二分查找二分查找法是一种效率较高的线性表查找方法，要求线性表结点必须是按关键码值排好序的，且线性表以顺序方式存储。

其具体步骤是：首选用要查找的关键码值与线性表中间位置结点的关键码值相比较，这个中间结点把线性表分成两个子表，比较相等则查找完成，不等则根据比较结果确定下一步的查找应该在哪一个子表中进行，如此进行下去，直到找到满足要求的点二分查找的优点：平均查找长度小，为［ l og ? ! ! 」二分查找的缺点：线性表排序需要花费时间，顺序方式存储的插入、删除不便 3 ) 分块查找分块查找要求把线性表分成若干块，每一块中的结点不必有序，但块与块之间必须有序，还要求将各块中的最大关键码值组成一个有序的索引表其具体步骤是：首选在索引表中用顺序查找或二分查找法确定所求记录所在的块，然后再从该块中用顺序查找方法找出所求的记录 4) 散列表查找散列法的基本思想是：由结点的关键码决定结点的存储地址，即以关键码k 为自变量，通过散列函数计算出对应的函数值h ( k) , 将这个值解释为结点的存储地址检索时再根据要检索的关键码值用同样的方法计算出结点位置散列法需要解决以下两个问题：a . 构造好的散列函数，能够将一组关键码值尽可能均匀地安排在事先确定的范围里，并且使得发生碰撞的可能性最小• 常见的散列函数有直接定址法除余法、数字分析法、折叠法、平方取中法等。

b.制定解决碰撞的方案处理碰撞的方法主要有拉链法和开放定址法影响产生冲突多少有以下三个因素： 哈希函数是否均匀；处理冲突的方法； 哈希表的负载因子散列表的负载因子公式：散列表中结点的数目C C ------------------------------------------------------基本区域能容纳的结谶负载因子的大小体现散列表的装满程度，e越大，则散列表装得越满，发生碰撞的机会越大，一般取a < 1 o考点16：树形结构与查找*( 1 ) 二叉排序树二叉排序树是一类特殊的二叉树，其特点是：若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；所有的子树也遵守相同的规则对二叉排序树中序遍历( 周游) 可以得到关键字从小到大的有序序列对无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造二叉排序树的过程就是对无序序列进行排序的过程对二叉排序树的操作主要的插入和删除操作平衡二叉树是对二叉排序树的一种“ 平衡化”处理结点的平衡因子定义为其右子树高度减去左子树高度 若任一结点的平衡因子均取一1 , 0或+ 1 , 则此二叉排序树为平衡的二叉排序树( A V L树) 。

平衡二叉排序树的查找方法与一般的二叉排序树完全一样，优点是总能保持检索长度为O Q o g z n ) 量级往平衡二叉树插入新结点时， 需要对树的结构进行必要调整， 以动态地保持平衡二叉树的特点（ 2 ） B树和B +树B树和B +树是一种平衡的多路查找树形结构， 用于组织外存储器中文件的动态索引结构 这样可以使得每个结点包含多个关键码值，有多个孩子，使得树的层次降低，查找时访问外存的次数减少由B树定义可以知：a . m阶B树每一个结点最多有m个子树b . m阶B树根结点或为叶结点，或至少有两棵子树；中间结点至少有「m / 2 ］棵子树c . m阶B树任一结点的左右子树的高度都相等B树的主要操作是：查找、插入、删除在m阶B树上插入关健码的过程为：a . B树是从空树开始，逐个插入关键码而生成的b .在B树中，每个非叶结点的关键码个数都在］ 「m / 2 1 T , m - 1 ］之间c . B树中关键码的插入不是在叶结点上进行的，而是在最底层的某个非终端结点中添加一个关键码若插入结点上关键码个数不超过mT个，则可直接插入到该结点上；否则，要进行调整，即结 点 的 “ 分裂” 。

根据B +树的定义可知：a .有n棵子树的结点中含有n个关键码b .所有关键码均出现在叶结点中，上层关键码均是下层相应结点中最大关键码的重复，且叶子结点所有关键码是有序的c .对B +树进行两种查找运算：一种是从最小关键码起顺序查找，另一种是从根结点开始，进行随机查找2 . 6排序考点17：插入排序插入排序的基本思想是每次将一个待排序记录按其关键码值大小插入到前面已排序的文件中的合适位置上，直到记录插入完为止a .直接插入排序：在已排好序的序列中查找插入位置时用顺序法查找，找到插入位置后将该位置原来的记录及其后面所有的记录顺序后移一个位置，空出该位置来插入记录b .二分法插入排序：在已排好的序列中找插入的位置时，用二分法查找，找到插入位置后和直接插入排序法同样处理c . s he l l排序：又称缩小增量法，是按增量将文件分组首先取增量d i< n ,把全部记录分成出个组，所有距离为出倍数的记录放在一组中，各组内用插入法排序，然后取d 2 < d i，重复上述分组和排序工作，直至取d = l ,即所有记录放在一个组中为止考点18：选择排序*选择排序的基本思想是每次从待排序的记录中选出关键码值最小（ 或最大）的记录，顺序放在已排记录序列的最后，直到全部排完，这里主要讲堆排序堆排序是对一组待排序的关键码，首先把它们按堆的定义排成一个序列（ 称为建堆） ，这就找到了最小的关键码，然后将最小的关键码取出，用剩下的关键码再建堆，便得到次最小的关键码，如此反复进行，直至将全部关键码排好序为止。

堆排序的两个主要问题：（ 1 ）如何将n个元素的序列按关键码建成堆 2 ）输出堆顶元素后，如何调整剩余元素使之成为一个新堆考点19：交换排序*交换排序主要是起泡排序和快速排序a .起泡排序是将排序的记录顺次两两比较，若为逆序则进行交换，将序列照此方法从头到尾处理一遍称做一趟起泡第二趟起泡再将次最大关键码交换到倒数第二个位置，即它的最终位置，如此进行下去，若某一趟起泡过程中没有发生任何交换，或排序已经进行了 n - 1趟，则排序过程结束b .快速排序是在待排序序列中任取一个记录，以它为基准用交换的方法将所有的记录分成两部分，关键码值比它小的一个部分，关键码值比它大的在另一部分，再分别对两个部分实施上述过程，一直重复到排序完成考点20：归并排序归并排序的基本思想是对两个或两个以上的表组合成一个新的有序表排序方法为先将原始序列中的每个关键字都看作一个序列，两两有序归并，逐步扩大于序列尺寸，直到全部排序完成2 . 7经典题解一、选择题1 .下 列 哪 一 个 术 语 与 数 据 的 存 储 结 构 有 关 2 0 0 7 . 0 9 ）A）栈B ）队列C）链表 D）线性表解析：数据的存储结构是逻辑结构在计算机存储器里的实现，如链表。

数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式逻辑结构分为线性结构（ 如线性表、栈、队列）和非线性结构（ 如树） 答案：C2 .下列关于数据的逻辑结构的叙述中，哪 一 条 是 不 正 确 的 2 0 0 7 . 0 9 ）A）数据的逻辑结构是数据间关系的描述B）数据的逻辑结构不仅反映数据间的逻辑关系，而且包括其在计算机中的存储方式C）数据的逻辑结构分为线性结构和非线性结构D）线性表是典型的线性结构解析：数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式，在计算机中的存储是由存储结构决定的逻辑结构分为线性结构（ 如线性表、栈、队列）和非线性结构（ 如树） 答案：B3 .下列关于数据运算的叙述中，哪 一 条 是 不 正 确 的. （ 2 0 0 7 . 0 9 ）A）数据运算是数据结构的一个重要方面B ）数据运算的具体实现在数据的逻辑结构上进行C）检索是一种常用的运算D）插入是一种常用的运算解析：数据的运算定义在数据的逻辑结构上，而实现是在存储结构上主要的运算包括插入、删除、排序、查找等。

答案：B4 . 栈 结 构 不 适 用 于 下 列 哪 一 种 运 用 2007.09）A）表达式求值B）快速排序算法的实现C）树的层次次序周游算法的实现D）二叉树对称序周游算法的实现解析：树的层次次序周游算法需要先存储每一层的结点，然后按照先进后出的顺序依次访问结点信息，需要用先进先出的队列来实现，而不是用先进后出的栈来实现；表达式求值，需要设置操作数和操作符两个栈；快速排序需要用栈实现递归；二叉树对称序周游算法即中序周游算法，也需要用栈结构实现答案：C5 . 双链表的每个结点包括两个指针域其中rlink指向结点的后继，llink指向结点的前驱如果要在p 所指结点后插入q 所指的新结点，下 列 哪 一 个 操 作 序 列 是 正 确 的 2007.09）A） p f .rlink f .llink:=q; p f .rlink:=q; q t .llink-p; q t .rlink:=p f .rlink;B） p f .llink f .rlink:=q; p f .llink:=q; q f .rlink:=p; q t .llink:=p t .llink;C） q f .llink:=p; q f .rlink:= p t .rlink ; p f .rlink t .llink:=q; p t .rlink:=q;D） q f .rlink t :=p: q t .llink:=p t .llink; p t .llink f .rlink:=q; pt .llink:=q;解析：需要先将待插入结点q 的左指针更新为p，然后将q 右指针的信息更新为p 的右指针所指向结点，再将p 的右指针所指结点的左指针信息更新为q , 最后将p 的右指针信息更新为q.p q new nodeLlinkRlinkLlinkRlinkLlinkRlink答案：C6 . 在包含1000个元素的线性表中实现如下运算，哪一个 所 需 执 行 时 间 最 长 . （ 2007.09）A）线性表按顺序方式存储，性表的第100个结点后面插入一个新结点B）线性表按链接方式存储、 性表的第100个结点后面插入一个新结点C）线性表按顺序方式存储，删除线性表的第900个结点D）线性表按链接方式存储，删除指针P 所指向的结点解析：线性表按顺序方式存储，执行插入操作时要将插入点后的所有元素平移一个单位，在 1000个元素的线性表的第100个结点后插入新结点需要移动900个元素。

链接方式存储插入新结点需要查找100次找到结点再插入线性表按顺序方式存储， 删除第900个元素要将第900-1000个元素向前移动一个单位 按链接方式存储， 删除指针P 指向结点，其平均查找长度为500.5查找开销比移动开销要小答案：B7 . 设某散列表的当前状态如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 181907519476855958208该 散 列 表 的 负 载 因 子 约 为 » (2007.09)A) 0.37 B) 0.42 C) 0.58 D) 0.73解析：散列表的负载因子公式:散列表中结点的数目基本区域能容纳的结，敏由题可知负载因子为7 / 1 9 =0 . 3 7答案：A8 .设有关键码序列( Q、G、M、Z 、A、N、B、P 、X、H 、Y 、S 、T 、L 、K 、E ) . 采用堆排序法进行排序，经过初始建堆后关键码值A在 序 列 中 的 序 号 是 < , ( 2 0 0 7 . 0 9 )A ) 1B ) 4C ) 8D ) 1 2解析：堆排序是将待排序的关键码先按堆的定义排成一个序列( 称为建堆) ，找到最小的关键码，然后将最小的关键码取出，用剩下的关犍码再建堆，便得到次最小的关键码，如此反复进行，直至将全部关键码排好序为止。

所以初始建堆关键码A 即为堆顶，序号为1 «答案：A9 . 对 n个记录的文件进行起泡排序，所 需 要 的 辅 助 存 储 空 间 为 . ( 2 0 0 7 .0 9 )A) 0 ( 1 ) B) O ( l o g2n )2C) O ( n ) D) 0 ( n )解析：起泡排序仅需一个辅助存储空间作为记录在交换位置时的缓存空间答 案 : A1 0 . 下列关于数据结构基本概念的叙述中，哪 一 条 是 不 正 确 的 2 0 0 7 .0 4 )A )数据是采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述B )数据元素( 或称结点、记录等) 是数据的基本单位C) 一个数据元素至少由两个数据项组成D )数据项是有独立含义的数据最小单位解析：一个数据元素可由一个或若干个数据项组成数据项是有独立含义的不可分割的数据的最小单位数据是所有能输入到计算机中并被计算机程序识别、存储和处理的符号的总称答案：CII . 下列关于链式存储结构的叙述中，哪 些 是 正 确 的 2 0 0 7 .0 4 )I . 逻辑上相邻的结点物理上不必邻接II . 每个结点都包含恰好一个指针域III . 用指针来体现数据元素之间逻辑上的联系IV . 可以通过计算机直接确定第i 个结点的存储地址V . 存储密度小于顺序存储结构A) I、I I 和 I I B) I、IL III 和 IVC) IL IV 和 V D) I、IH 和 V解析：链式存储结构中除了包含保存数据元素自身信息的信息域外，还有表示数据元素之间的链接信息的指针域，因此比顺序存储结构的存储密度低；链式存储结构中逻辑上相邻的数据元素在物理上不一定相邻；不是所有节点都包含指针域，如单向链表中坡后一个节点的指针为空。

答案：D1 2 和 1 3 基于以下描述：有一个初始为 空 的 栈 和 输 入 序 列 A 、B 、C 、E 、F 、G ：现发过如下操作：p u s h ,p u s h ,t o p ,p o p ,p u s h .p u s h ,t o p ,p u s h ,p o p ,p o p ,p o p .1 2 . 下 列 哪 一 个 是 正 确 的 从 栈 中 删 除 元 素 的 序 列 2 0 0 7 .0 4 )A) BE B) BDC) BEDC D) BDEC解析：栈的操作遵循后进先出的原则题中的操作依次为：A 进栈、B 进栈、B 读取、B 删除、C 进栈、D 进栈、E 进栈、E 删除、D 删除、C 删除由此可见删除的序列为BEDC答案：C13 . 下列哪一个是上述操作序列完成后栈中的元素列表( 从底到顶)2007.04)A) A B) BDC) ABCE D) ABCDE解析：通过上题的分析可知，在操作过程中进栈的有ABCDE,删除的有BEDC,因此最后栈中的元素只有A答案：A14-15基于如下所示的二叉树4B CD EF G14 . 该 二 叉 树 对 应 的 树 林 包 括 几 棵 树 . (2007.04)A) 1 B) 2 C) 3 D) 4解析：二叉树转换为树林时，二叉树的根就是树林第一棵树的根；二叉树的左子树转换为树林的第一棵树，二叉树的右子树对应于树林中其余的树；二叉树右子树的根节点作为余下树中第一棵树的根节点，其余以此类推。

本题中的二叉树应该包含2 棵树答案：B15 . 按后根次序周游该二叉树时应的树林，所 得 到 的 结 点 序 列 为 . (2007.04)A) DBAFEGC B) ABCDEFGC) DBFGECA D) ACBEGDF解析• ：后序遍历二叉树的次序是：后序遍历左子树I 后序遍历右子树，访问根节点因此后序遍历此二叉树对应的树林所得的节点序列为选项C.答案：C16 . 按层次次序周游该二叉对应的树林，所 得 到 的 结 点 序 列 为 . (2007.04)A) DBAFEGC B) ABCDEFGC) DBFGECA D) ACBEGDF解析：按层次次序遍历二义树的次序是：从树的根节点开始，依次访问每一层，对同一层节点，由左到右进行访问因此按层次次序遍历此二叉树对应的树林所得的节点序列为选项B答案：B17 . 设待排序关键码序列为(25, 18, 9, 33, 67, 82, 53, 95, 12, 7 0 ),要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟排序完成后关键码95被 放 到 第 几 个 位 置 2007.04)A) 7B) 8C) 9D) 10解析：快速排序法第一趟排序后，关键码序列为(12, 18, 9, 25, 67, 82, 53, 95, 33, 7 0 ),因此关键码95处在第8 个位置。

答案：B1 8 .设散列表的地址空间为0到1 6 ,散列函数为h(k)=kmodl7,用线性探查法解决碰撞现从空的散列表开始，依次插入关键码值190, 89, 217, 208, 75, 1 7 7 ,则最后■ •个 关键码177的 地 址 为 2007.04)A ) 6B) 7C) 8D) 9解析：本题采用除留余数法构造散列函数，将关键码值190, 89, 217, 208, 75, 177分别带入h(k)=kmodl7,得到散列地址分别为3, 4, 13, 4, 7, 7 ,在存储关键码208时，由于其散列地址4与前面的一个关键码发生冲突，因此其存储地址向后移1位到5而存储关键码177时，由于其散列地址7与前面的一个关键码发生冲突，因此其存储地址再向后移1位 至IJ 8.答案：C1 9 .下 列 哪 些 是 数 据 结 构 研 究 的 内 容 2006.09)I .数据的采集 I I .数据的逻辑组织III .数据的存储实现 I V .数据的传输V .数据的检索A ) II 和 IV B) I、II IIIC) II、III fn V D) 1、III 和 V解析• ： 数据的采集和数据的检索不属于数据结构研究的内容。

数据结构一般包括三方面内容： 数据的逻辑结构,它是从逻楫关系上描述数据，与数据的存储无关数据的存储器内表示，它是指用计算机语言实现的逻辑结构，它依赖于计算机语言数据的运算，即对数据施加的操作答案：c20 .下列关于数据元素的叙述中，哪 一 项 是 不 正 确 的2006.09)A )数据元素是数据的基本单位，即数据集合中的个体B )数据元素是有独立含义的数据最小单位C )数据元素又称作结点D )数据元素乂称作记录解析：数据项是具有独立含义的最小标识单位，而非数据元素数据元素是数据的基本单位，一个数据元素可以由若干个数据项组成，有时也称作结点、记录、表目等答案：B21 .下列关于数据的存储结构的叙述中，哪 一 项 是 正 确 的. (2006.09)A )数据的存储结构是数据间关系的抽象描述B )数据的存储结构是逻辑结构在计算机存储器中的实现C )数据的存储结构分为线性结构和非线性结构D )数据的存储结构对数据运算的具体实现没有影响解析：数据的存储结构是指数据的逻辑结构在计算机存储器中的表示，又称数据的物理结构分为顺序存储结构和链式存储结构数据采用不同的存储结构，将对数据运算的具体实现有着巨大的影响.答案：B22 .栈S最多能容纳4个元素。

现有6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列是可能的出栈序列 o (2006.09)A ) E、D、C、B、A、F B) B、C、E、F、A、DC) C、B、E、D、A、F D) A、D、F、E、B、C解析：对于选项A ,因为该栈最多只能容纳4个元素，而E是第五个元素，在前4个元素还没出栈的情况下是不可能进栈再出栈的 对于选项B, A元素不可能在D元素还没出栈的情况下先出栈；对于选项C ,其出栈序列为：C、B、E、D、A、F ：对于选项D , B元素不可能在C元素还没出栈情况下出栈，出栈序列为选项C答案：C2 3 .从单链表中删除指针s所指结点的下一个结点t ,其 关 键 运 算 步 骤 为 2 0 0 6 . 0 9 )A ) s f . l i nk : = t B) t T』i nk : = sC ) t f . l i nk : = s f . l i nk D ) s f . l i nk : = t T』i nk解析：要从单链表中删除指针s所指节点的下一个节点l ,则原节点t指的后继节点成为s所指的后继节点，因此关键运算步骤为：s T ， l i nk : = t j . l i nk o答案：D2 4 .按行优先顺序存储下三角矩阵aH 0 ... 0A =a2 [ a 22 ♦ • • 0nn• • • • • • • • • • • •anI an9 ... annL nl n2 nn的非零元素，则 计 算 非 零 元 素 的 地 址 公 式 为 (2 0 0 6 . 0 9 )A) IJ3C(aij) = LOC(a11) + ix(i + l)/2+ jB)UDC(aij) = IJDC(a11) 4-ix(i + l)/24-(j-l)C ) L O C (a j j ) = L O C (a | | ) + i x (i -l ) / 2 + jD) LOC(aij) = LOC(all)+ ix(i-l)/2 + (j-l)解析：非零元素a ”在矩阵中处在第i行第j列，在按行优先顺序存储时，应先存储前i - 1行的非零元素和同一行的前jT个元素。

如果a ”的存储地址为L O C (a u ) ,则a ,的存储地址为D答案：D2 5 .下列关于二叉树周游的叙述中，哪一项是正确的. (2 0 0 6 . 0 9 )A)若一个结点是某二叉树对称序的最后一个结点，则它必是该二叉树前序的最后一个结点B )若一个结点是某二叉树前序的最后一个结点，则它必是该二叉树对称序的最后一个结点C)若一个树叶是某二叉树对称序的最后一个结点，则它必是该二叉树前序的最后一个结点D)若一个树叶是某二叉树前序的最后一个结点，则它必是该二叉树对称序的最后一个结点解析• ：若一个树叶是某二又树对称序的最后一个节点，则它必是该二叉树最右边的树叶，即前序的最后一个节点而若将“ 树叶”改 为 “ 结点”则不正确，因为有可能出现二叉树最右结点无右孩子的情况答案：C2 6 .如下所示是一棵5阶B树，该B树现在的层数为2从该B树中删除关键码3 8后，该B树的第2层的结点数为 (2 0 0 6 . 0 9 )A ) 6B) 7C ) 8D ) 9解析：删除38后该节点剩下的关键码的个数为1,小于「5 / 2 1 -1=2,所以删除后要将该结点剩余的41与双亲结点中的45一起移至原结点的右兄弟节点，故结点数减1,变为6个。

答案：A2 7 .在待排序文件已基本有序的前提下，下列 排 序 方 法 中 效 率 最 高 的 是. （ 2 0 0 6 . 0 9 ）A）直接插入排序 B ）直接选择排序C）快速排序 D）归并排序解析：直接插入排序，若文件基本有序，则比较次数最小为n T次，移动次数为0 ：直接选择排序，无论待排序文件是否基本有序，其比较次数均为n（ n T） / 2 ,若文件基本有序，则移动次数减少，最小为0 ；快速排序在文件基本有序时蜕化为起泡排序，时间复杂度为n（ n- l ） / 2 ；对于归并排序，无论待排序文件是否基本有序，其比较次数均为| ■ l o g , n，若文件基本有序，则移动次数减少，最小为0 ，可见直接插入排序效率最高答案：A2 8 .下列关于数据结构基本概念的叙述中，哪 一 条 是 正 确 的 2 0 0 6 . 0 4 ）A）数据的逻辑结构分为表结构和树结构B ）数据的存储结构分为线性结构和非线性结构C）数据元素是数据的基本单位D）节点是有独立含义的数据最小单位解析：数据的基本单位是数据元素，故C正确数据的逻辑结构可以划分为集合、线性结构、树型结构和图状结 构 （ 网状结构） 。

数据的存储结构指的是数据结构在计算机中的表示（ 映像） ，它包括顺序存储和链式存储两种结构节点是由若干位组合起来形成的位串，数据的最小单位是节点中的•个二进制数位（ b i t）答案：C2 9 .下列关于串的叙述中，哪 一 条 是 正 确 的 2 006 .04 ）A）串是由零个或多个字符组成的有限序列B）空串是由空格构成的串C）串只能顺序存储D ） “ 推入” 是串的基本运算之一解析：串是由零个或多个字符组成的有限序列：如果串中没有任何字符，则称为空串由一个或多个空格组成的串称为空格串，空格串不是空串，因为空格串中有字符；串既可以顺序存储也可以链表存储• ：串的基本操作一般是 以 “ 串的整体”作为操作对象， “ 推入”不是串的基本运算答案：A3 0 .双链表的每个结点包括两个指针域其中r l i n k指向结点的后继，l l i n k指向结点的前驱如果要在p所指结点前面插入q所指的新结点，下列哪一个 操 作 序 列 是 正 确 的 2 006 .04 ）A） p | .r l i n k f .l l i n k : = q ： p f .r l i n k : = q ； q 1 .l l i n k : = p ； q 1 .r l i n k : = p f .r l i n k ；B） p 1 ' .l l i n k f .r l i n k : = q ； p f .l l i n k : = q ； q T .Hi n k : = p ； q f .l l i n k : = p T .l l i n k ；C） q | .l l i n k : = p ； q 1 .r l i n k : = p f .r l i n k ； p | .r l i n k f .l l i n k : = q ： p f .r l i n k : = q ；D ） q | .r l i n k : = p ； q T ， l l i n k : = p f .l l i n k ； p | .l l i n k f .r l i n k : = q ； p f .l l i n k : = q ；解析：首先要修改p所指节点的l l i n k字段和原前驱节点的r l i n k字段，然后置q所指节点的r l i n k和l l i n k值，即 q T ， r l i n k : = p ； q f .l l i n k : = p f .l l i n k ； p f .l l i n k ） .r l i n k : = q ； p T .Hi n k : = q。

答案：D3 1 .下列咖一个不是队列的基本运算 2 006 .04 ）A)从队尾插入一个新元素B)从队列中删除第i个元素C)判断一个队列是否为空D )读取队头元素的值解析• ：队列的基本操作有：构造一个空队列；将队列清为空队列；判断队列是否为空队列；计算队列的长度；读取队列的队头元素；向队列插入一个元素为该队列的队尾元素；删除队列队头元素队列只允许在队尾插入元素，而在队头删除元素答案：B3 2 .栈 结 构 不 适 用 于 下 列 哪 一 种 应 用 2 006 .04 )A)表达式求值B)树的层次次序周游算法的实现C)二叉树对称序周游算法的实现D )快速排序算法的实现解析：见第4题答案：B3 3 .按层次次序将一棵有n个结点的完全二叉树的所有结点从1到n编号，当i < n /2时，编号为i的结点的左孩 子 的 编 号 是« ( 2 006 .04 )A ) 2 i -l B ) 2 iC ) 2 i + l D )不确定解析：若对有n个节点的完全二叉树按层次从上到下，每个层次从左至右的规则为节点编号，若i 4 n /2 ,则编号为i的节点的左孩子节点的编号为2 i ；若i > n /2 ,则编号为i的节点没有左孩子节点。

答案：B3 4 .对于给出的一组权w = { 1 0, 1 2 , 1 6 , 2 1 , 3 0) ,通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为 ( 2 006 .04 )A ) 8 9B ) 1 8 9C ) 2 00 D) 3 00解析： 霍夫曼算法建立的扩充二又树如下图所示 所以带权外部路径长度为( 2 1 + 1 6 ) X 2 + 3 0X 2 + ( 1 2 + 1 0) X 3 = 2 002 1 1 6 3 01 2 1 0答案：C3 5 .设散列表的地址空间为 到1 0,散列函数为h (k户k m o d l l ,用线性探查法解决碰撞 现从空的散列表开始,依次插入关键码值95 , 1 4 , 2 7, 6 8, 8 2 ,则最后一个关键码82的 地 址 为. (2 0 0 6 .0 4 )A ) 4 B ) 5C ) 6 D ) 7解析：本题采用除留余数法构造散列函数，将关键码值95 , 1 4 , 2 7, 6 8, 8 2分别带入h (k ) =k m o d l l ,得到散列地址分别为7, 3 , 5 , 2 , 5,当存储关键码82时，由于其散列地址与前面的一个关键码发生冲突，因此其存储地址向后移I 位到6。

答案：C36 . 设有字符序列（ Q, H, C, Y, P, A, M, S, R, D, F, X） , 则新序列（ F, H, C, D, P, A, M, Q, R,S, Y, X） 是下列哪一个排序算法一趟扫描的结果 2006.04）A）起泡排序B）初始步长为4 的希尔（ shell）排序C）二路归并排序D）以第一个元素为分界元素的快速排序解析：若进行升序起泡排序，则因为Q 大于H , 因此Q 和 H 要交换，新序列第一 个字符应该为H；若进行降序起泡排序，Q 和 H 位置不变；若进行希尔排序，始步长为4 , 则Q 应该与P 分为一组，新序列的第一个字符应该为 P （ 升序）或 Q （ 降序） 若进行二路归并排序，则Q 和 H 归并，排序后的结果应该为H, Q （ 升序）或者Q, H（ 降序） 快速排序以第一个元素Q 为分界元素处理原序列可得到新序列答案:D37 . 以下关于数据的逻辑结构的叙述中，哪 一 条 是 不 正 确 的 2005.09）A）数据的逻辑结构是数据间关系的描述B）数据的逻辑结构不仅反映数据间的逻辑关系，而且反映其在计算机中的存储方式C）数据的逻辑结构分为线性结构和非线性结构D）树形结构是典型的非线性结构解析：如第2 题。

答案：B38 . 在包含1000个元素的线性表中实现如下各运算，哪 •个所 需 的 执 行 时 间 最 短 « （ 2005.09）A）线性表按顺序方式存储，查找关键码值为666的结点B）线性表按链接方式存储，查找关键码值为666的结点C）线性表按顺序方式存储，查找线性表中第900个结点D）线性表按链接方式存储，查找线性表中第900个结点解析：线性表顺序方式存储，可直接计算确定第i 个节点的存储地址，其执行时间与i 的值没有关系查找链接存储方式的线性表中的第i 个节点，依次与前i T 个节点进行比较，最终确认结点的位置答案：C39 . 在包含1000个元素的线性表中实现如下各运算，哪 一 个 所 需 的 执 行 时 间 最 长 2005.09）A）线性表按顺序方式存储，性表的第100个结点后面插入一个新结点B）线性表按链接方式存储，性表的第100个结点后面插入一个新结点C）线性表按顺序方式存储，删除线性表的第900个结点D）线性表按链接方式存储，删除指针P 所指向的结点解析：A 中需要把第1000个元素到第101个元素依次后移一位，共需移动900个元素；B 中只需从第一个节点开始，顺序查找到第100个节点，再进行两次交换指针即可；C 中在顺序表中删除一个元素，需把删除元素的后面元素前移，共前移100个元素；D 中在链接表中删除节点，只需进行一次指针的修改即可。

答案：A40 . 以下关于广义表的叙述中，哪 一 条 是 正 确 的 . （ 2005.09）A）广义表是0 个或多个单元素或子表组成的有限序列B）广义表至少有一个元素是子表C）广义表不可以是自身的子表D）广义表不能为空表解析： 广义表是线性表的扩展， 它的定义是由n个数据元素组成的有限序列， 其中的数据元素既可以是单元素，也可以是子表；广义表既可以是自身的子表，也可是空表答案：A4 1 -4 3题基于下图所示的二叉树：AB CDEFG H I41 .该 二 叉 树 对 应 的 树 林 包 括 几 棵 树. (2005.09)A ) 1 B) 2C) 3 D) 4解析：二叉树转换为树林，二叉树的根就是树林第一棵树的根；二叉树的左子树转换为树林的第一棵树，二叉树的右子树对应于树林中其余的树；二叉树右子树的根节点作为余下树中第一棵树的根节点，其余以此类推本题中的二叉树应该包含4棵树答案：D42 .如果用llink-rlink法存储该二叉树，则各结点的指针域中共包含多少个空指针. (2005.09)A ) 6B) 8C) 10D) 12解析：二叉树采用llink-rlink法存储时，其指针域llin k和rlin k分别指向节点的左孩子和右孩子。

题中二叉树D、G、H、I四个节点的左右孩子和E节点的右孩子以及C节点的左孩子均为空，因此空指针共有4X2+2X1 = 10个答案：C43 . 如果将该二叉树存储为对称序线索二叉树，则结点H的 左 线 索 指 向 哪 一 个 结 点. (2005.09)A )结点A B )结点CC )结点E D )结点G解析：采用对称序线索二叉树存储二叉树时，其访问次序是先中序遍历左子树，然后访问根节点，最后遍历右子树题中二叉树存储为对称序线索二叉树的结果是：DBGEACHFI,所以节点H的左线索指向节点C答案：B44 .以下关于B树运算的叙述中，哪 一 条 是 正 确 的 2005.09)A )若插入过程中根结点发生分裂，则B树的高度加1B )每当进行插入运算，就在B树的最下面一层增加一个新结点C )若要删除的关键码出现在根结点中，则不能真正删除，只能做标记D )删除可能引起B树结点个数减少，但不会造成B树高度减小解析：对于根节点，由于没有双亲节点，所以如果根节点发生了分裂，就要建立一个新的根节点，则B树的高度加lo答案：A45 .对n个记录的文件进行归并排序，所 需 要 的 辅 助 存 储 空 间 为 。

2005.09)A ) 0(1) B) O(n)C) O(log2n) D) O(n2)解析：归并排序需把每次归并的结果放入另一个空间中，n个记录的文件就需再分配n个大小的空间，所以空间复杂度为0(n)答案：B二、填空题1 .按行优先顺序存储下三角矩阵A “n的非零元素，则计算非零元素,(IW jW iW n )的地址的公式为Loc( a ,尸_ _ _ _ _ _+i*(i-l)/2+(j-l)(> (2007.09)解析: 非零元素a.在矩阵中处在第i行第j列， 在按行优先顺序存储时， 应先存储前i-1行的非零元素( 共ix(iT)/2个 ) 和 同 一 行 的 前j -l个 元 素 如 果a n的 存 储 地 址 为LOC(au),则a .j的 存 储 地 址 为L O C ^ a = ) L 0 ,(^ ( ax ) - i ( it- 1答案：Loc(4 ] )2 .按对称序周游二叉树等同于按 周游对应的树( 林) 2007.09)解析：按对称序周游二叉树相当于中序遍历二叉树答案：中序3 . m阶B+树的根节点至多有 个孩子2007.09)解析：按 照B+树的定义，m阶B+树每个结点至多有m个孩子。

答 案 :m4 .三元组法和十字链表法都可以用于 矩阵的存储表示20()7.04)解析：三元组法和十字链表法均用于存储稀疏矩阵用三元组存储稀疏矩阵仅存储矩阵中的非零元素，十字链表法则为了避免进行删除和插入操作时而导致的大量节点的移动答案：稀疏5 .有关键码值为10, 20, 30的三个结点，按所有可能的插入顺序去构造二叉排序树，能构造出 棵不同的二叉排序树2007.04)解析：二叉排序树具有以下性质：若其左子树非空，则所有左子树上数据元素关键字的值均小于根节点关键字的值；若其右子树非空，则所有右子树上数据元素关键字的值均大于根节点关键字的值；其左子树和右子树也是二叉排序树，因此能够构造出5棵二叉排序树答案：56 .散列法存储的基本思想是：由结点的 决定结点的存储地址2006.09)解析：散列法存储的基本思想是：由节点的关键码值决定节点的存储地址，具体地址由散列函数决定答案：关键码值7 .若一课二叉树的度为2的结点数为9 ,则 该 二 叉 树 的 叶 结 点 数 为 2006.09)解析：二叉树的叶节点数为n<>=in+l,因此叶节点数9+1 = 10答案：108 .在顺序表(3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 3 0 )中，用二分法查找关键码值1]，所需的关键码比较次数为。

2006.09)解析：二分查找法的基本思路是不断把区间的中间元素与待查找的元素比较，根据比较结果确定是结束查找还是在左边或右边子表并按相同的方法继续查找与11比较的关键码分别为15、8、10、1 2 ,所以比较的次数为4答 案 :49 .广义表是线性表的推广，是由零个或多个单元素或 所组成的有限序列 2006 . 04)解析： 广义表是线性表的扩展， 它的定义是由n个数据元素组成的有限序列， 其中的数据元素既可以是单元素,也可是是子表答案：子表10 .一棵二叉树结点的前序序列为A、B、D、E、G、C、F、H、I ,对称序序列为D、B、G、E、A、C、H、F、I ,则 该 二 叉 树 结 点 的 后 序 序 列 为 2006 . 04)解析：先序遍历和中序遍历可以唯一确定一棵树前序序列中，第一个节点为树根节点，因此根节点为A；对称序序列中，树根节点左边的节点D、B、G、E为左子树节点，右边的节点C、H、F、I为右子树节点根据这个原则可以得出本题对应的二叉树如下图所示由图以及后序遍历规则可以得出其后序序列为：D G EBH I F C A .AB CD E FG H I答案：D G EBH 1F C A11 . m阶B树的每个结点至多有 棵子树。

2006 . 04)解析：一棵m阶B树或者为空，或者满足每个节点至多有m棵子树；根节点或为叶节点或至少有两棵子树答案：m12 .散列法存储中处理碰撞得方法主要有两类：和开地址法 2006 . 04)解析：散列法存储中处理碰撞的方法主要有链地址法和开地址法两类答案：链地址法13 .数据结构包括三方面的内容：数据的逻辑结构、数据的存储结构、数据的. ( 2005 . 09 )解析：数据结构的概念包括三方面的内容：数据的逻辑结构、数据的存储结构和数据的运算答案：运算14 . m阶B树的每个结点至少有 棵子树 2005 . 09 )解析：一棵m阶B树或者为空，或者满足每个节点至多有m棵子树；根节点或为叶节点或至少有两棵子树答案：215 .对于关键码序列18 , 30, 35 , 10, 46 , 38 . 5 , 40,进行堆排序( 假定堆的根结点是最小关键码) ，在初始 建 堆 过 程 中 需 进 行 的 关 键 码 交 换 次 数 为. ( 2005 . 09 )解析：在初始堆建成之前，由题中关键码序列构成的完全二叉树如下图所示由图可知，要使该完全二叉树成为小根堆，需要交换的关键码对为( 5 , 35 )、( 30, 10)和( 18 , 5 ) ,共交换三次。

1830 3510 46 38 54 0答案：32 . 8同步自测一、选择题i .以 下 哪 一 个 ( 些 ) 不 是 数 据 结 构 研 究 的 内 容 i . 数据的采集 n.数据的逻辑组织i n . 数据的存储结构 I V. 数据的传输V .数据的检索A)仅 I B) I 和I Vc ) n和N D)I、i n 和i v2 和 3 基于以下描述： 有一个初始为空的栈和下面的输入序列A , B, C , D , E, F , G；现经过如下操作： p u s h ,p u s h , p o p , p u s h , p u s h , t o p , p u s h , p o p , p o p .2 .以下哪一个是从栈中删除元素的序列.A ) BED B) BD EC ) BED C D ) BD EC3 .以下哪一个是上述所有操作结束后栈中的元素列表( 从底到顶) »A ) A C B) AC ) A BC E D ) A BC D E4 .如下是一个稀疏矩阵的三元组法存储表示和基于此表示所得出的相关叙述行下标 列下标 值113145232326345533I .该稀疏矩阵有5 行 H.该稀疏矩阵有4 列I I I .该稀疏矩阵有6个非0 元素这些叙述中那一个( 些) 是正确的 OA)仅 I B )1 和nC)仅H I D)全部5 .对包含n 个元素的散列表进行检索，平 均 检 索 长 度 。

A)为 O( l o g 2n ) B )为 0( n )C)为O( n * k ) g 2n ) D)不直接依赖于n6和7 基于以下的5 阶 B树结构，该 B树现在的层数为2I 3 5 I45 60 821() 1821 3064 70 73 7886 956 .往该B树中插入关键码72后，该B树的第二层的结点数为.A) 6B) 7C） 8D） 97 .从该B树中删除关键码15后，该B树的第二层的结点数为A ） 6B） 7C) 8D) 98 .下列哪一个关键码序列不符合堆的定义A ） A、C、D, G、H、M、P、Q、R、XB ） A、C、M、D、H、P、X、G、Q. RC） A、D、P、R, C、Q、X、M、H、GD） A、D、C、G、P、H、M、Q、R, X9 .以下关于顺序存储结构的叙述中，哪 一 条 是 不 正 确 的 <,A ）存储密度大B）逻辑上相邻的结点物理上不必邻接C）可以通过计算直接确定第i个结点的存储地址D）插入、删除运算操作不方便10 .以下关于数据的逻辑结构的叙述中，哪 一 条 是 不 正 确 的A ）数据的逻辑结构是数据间关系的描述B）数据的逻辑结构抽象地反映数据元素间的逻辑关系C）数据的逻辑结构具体地反映数据在计算机中的存储方式。

D）数据的逻辑结构分为线性结构和非线性结构11 .以下关于链式存储结构的叙述中，哪 一 条 是 不 正 确 的 A ）结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B）逻辑上相邻的结点物理上不必邻接C）可以通过计算直接确定第i个结点的存储地址D）插入、删除运算操作方便，不必移动结点12 .栈S最多能容纳4个元素现有6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列不是可能的 出 栈 序 列 .A ） A、D、E、C、B、FC） C、 B、 E、 D, A、 F1 3 .队列适用于下列哪一种应用A ）表达式求值C）树的层次次序周游算法的实现B） A, F、E、D、C、BD） C、 D、 B, F、 E、 AB）堆排序算法实现D）二叉树对称序周游算法的实现14 .为了减少栈溢出的可能性，可让两个栈共享一片连续内存空间，两个栈的栈底分别设在这片空间的两端,这样，只有 时才可能产生上溢A)两个栈的栈顶在栈空间的某一位置相遇B)其中一个栈的栈顶到达栈空间的中心点C)两个栈的栈顶同时到达栈空间的中心点D)两个栈均不空，且一个栈的栈顶到达另一个栈的栈底1 5 .设线性表的顺序存储结构中，每个元素占用1 个存储单元，表的第一个元素的存储地址为d ,则第i 个元素 ( I W i V n , n 为 表 长 ) 的 存 储 地 址 为 .A ) d + ( i - l ) l B ) d + i lC ) d + ( i + l ) l D ) d + i l - l1 6 .所 谓 稀 疏 矩 阵 指 的 是。

A)零元素个数较多的矩阵B)零元素个数占矩阵元素总个数一半的矩阵C)零元素个数远远多于非零元素个数且分布没有规律的矩阵D)包含有零元素的矩阵1 7 .二维数组M [ i , j ] 的元素是4个字符( 每个字符占一个存储单元) 组成的串，行下标i 范围从0到4,列下标j 的范围从0到 5 M按行存储时元素M [ 3 , 5 ] 的起始地址与M按列存储时元素 的起始地址相同A ) M [ 2 , 4 ] B ) M [ 3 , 4 ]C ) M [ 3 , 5 ] D ) M [ 4 , 4 ]1 8 和 1 9 基于下面的叙述：某二叉树结点的先序序列为E 、A 、C、B 、D、G、F , 对称序序列为A、B 、C、D、E 、 F 、 G o1 8 . 该二叉树结点的后序序列为 0A ) B 、D 、C 、A 、F 、G、EB ) B 、D、C 、F 、A 、G、EC ) E 、G、F 、A、C 、D 、BD ) E 、G、A 、C 、D 、F 、B1 9 .该二叉树对应的树林包括 棵树A ) 1 B ) 2C ) 3 D ) 42 0 .设电文中出现的字母为A 、B 、C 、D和 E, 每个字母在电文中出现的次数分别为7 , 2 7 , 3 , 5和 1 1 。

按哈夫曼编码，则字母C的编码应是 OA) 1 0 B ) 1 1 0C ) 1 1 1 0 D ) 1 1 1 12 1 .由分别带权为9 、2 、5 、7的四个叶子结点构成一棵哈夫曼树，该 树 的 带 权 路 径 长 度 为 A) 2 3 B ) 3 7C ) 4 4 D ) 4 62 2 . 一棵二叉树如下图所示，其中序遍历的序列为 oA) AB D G C E F H B ) D G B AE C H FC ) G D B E H F C A D ) AB D E F G H CBDACFH2 3 .对关键码集合K二｛ 53, 30, 37, 12, 45, 24, 96） ,从空二叉树开始逐个插入每个关键码，建立与集合K相对应的二叉排序树（ 又称二叉查找树）B S T ,若希望得到的BST高度最小，应选择下列哪种输入序列.A) 45, 24, 53,12, 37, 96, 30B) 37, 24,12, 30, 53, 45, 96C)24, 30, 37, 45, 53, 96D) 30, 24,12, 37, 45, 96, 532 4 .长 度 为12的按关键字排序的查找表采用顺序组织方式。

若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是 oA) 37/12B) 62/1325.26.27.快速排序28.29.C) 39/12D) 49/13用二分查找法对具有n个结点的线性表查找一个结点所需的平均比较次数为一A) O(n2)C) O(n)B) O(nlog2n)D) O(log2n)对n个记录的文件进行堆排序，最坏情况下的执行时间为.A) O(log2n)C) O(nlog2n)B) O(n)D) O(n2)对给定的整数序列（ 541, 132, 984, 746, 518, 181, 946, 314, 205, 827）进行从小到大的排序时，采用（ 以中间元素518为基准）的 第 一 趟 扫 描 结 果 是 A)B)C)D)(181,(541,(205,(541,132,132,132,132,314,827,314,984,205, 541, 518, 946, 827, 746,746, 518,181, 946, 314, 205,984)984)⑻ ，518, 746, 946, 984, 541,746, 827,181, 946, 314, 205,827)518)设有关键码序列（ q, g,A)B)C)D)m,n, p, x, h） ,下面哪一个序列是从上述序列出发建堆的结果.a, g, h, m,a, g, m, h,g, m, q, a,h, g, m, p,n, p, q, x, zq, n, p, x, zn, p, x, h, za, n, q, x, z对于存储同样一组数据元素而言,A)B)C)D)顺序结构比链接结构多占存储空间顺序结构与链接结构相比，更有利于对元素的插入、删除运算顺序结构比链接结构易于扩充空间顺序结构占用整块空间而链接结构不要求整块空间⑵3().为了减少栈溢出的可能性，可让两个栈共享一片连续内存空间，两个栈的栈底分别设在这片空间的两端,这样，只有当时才可能产生上溢。

A )两个栈的栈顶在栈空间的某一位置相遇B )其中一个栈的栈顶到达栈空间的中心点C )两个栈的栈顶同时到达栈空间的中心点D )两个栈均不空，且一个栈的栈顶到达另一个栈的栈底31 .已知某二叉树的后序遍历序列是dacbe,中序遍历序列是debac,它 的 前 序 遍 历 序 列 是 ，A) acbed B) deabcC) decab D) edbac32 .二维数组A[0…8, 0 ...9 ],其每个元素占2个字节，从首地址400开始，按行优先顺序存放，则元素A[8,5]的存储地址为 oA) 570 B) 506C) 410 D) 48233 .若对一个已经排好了序的序列进行排序，在下列4种方法中，比 较 好 的 方 法 是 A )冒泡法 B )直接选择法C )直接插入法 D )归并法34 .用冒泡排序法对下列数据12、37、42、19、27、35、56、44、10进行从小到大排序在将最大的数“ 沉”到最后时，数 的 顺 序 是A ) 12、37、42、19、27、35、44、10、56B) 12、 37、 42、 19、 27、 35、 10、 44、 56C) 12、 37、 19、 27、 35、 42、 44、 10, 56D) 10, 12、19、27、35、37、42、44、56二、填空题1 .设根结点的层次为0 ,则高度为k的 二 叉 树 的 最 大 结 点 数 为 .2 .用 数 组 顺 序 存 储 完 全 二 叉 树 的 各 结 点 ， 则当i> 0 ,且iW 时， 结点A川的右孩子是结点A[2i+1],否则结点A [i]没有右孩子。

3 .设有二维数组A[0.. 9, 0.. 1 9 ],其每个元素占两个字节， 数组按列优先顺序存储，第一个元素的存储地址为1 0 0 ,那么元素A[6, 6]的 存 储 地 址 为 4 .设树的T的度为4 ,其中度为1、2、3和4的结点的个数分别4、2、1、1 ,则T中 叶 子 结 点 的 个 数 是 »5 .在对■二叉树进行顺序存储时，若它的下标为5的结点既有双亲结点，又有左孩子结点和右孩子结点，它的双 亲 结 点 的 下 标 为 .6 .设根结点的层次为0 ,则具有n个 结 点 的 完 全 二 叉 树 的 深 度 为 .7 .设散列表为Tablc[0..m -l],初始状态为空，用线性探测法解决冲突，将n(n

10 .若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为1 ,则左、右子树皆非空的结点个数为 11 .数据结构包括三个方面的内容，分别是：数据的、数据的存储结构和数据的运算12 .散列法存储中处理碰撞的方法主要有两类：拉 链 法 和 13 . m阶B树的根结点至少有 棵子树2 . 9同步自测答案一、选择题1. B2.A3.A4.C5. D6. C7.B8.C9.B10. C11. C12. B13. C14. A15. A16. C17. B18. A19. B20. C21. C22B23B24D25 D26. C27. C28.B29. D30. A31. A32.D33. C34. C二、填空题(1) 2k+,- l(2) (n-1 )/2(3) 232(4) 8(5) 2(6) LlogmJ(7) n(n+l)/2(8) 0(9) n-1(10) 0(1 1 )逻辑结构(1 2 )开地址法(13) 2。