全国计算机等级考试考点解析、例题精解与应试模拟——三级数据库.docVIP

第2章 数据结构与算法第2章 数据结构与算法本章大纲要求：（1）基本概念 （2）线性表（3）多维数组、稀疏矩阵和广义表（4）树形结构（5）查找 （6）排序重要考点提示：根据对历年真题的分析可知，本章考核内容约占15%，主要包括以下几个方面：（1）数据结构和算法的基本概念 （2）数据的逻辑结构、存储结构 （3）顺序表和一维数组（4）链表、栈、队列、串的概念与操作 （5）稀疏矩阵的存储、广义表的定义与存储（6）二叉树的定义、存储与表示、线索二叉树（7）树与二叉树的转换、二叉树的周游算法 （8）霍夫曼算法及其应用（9）静态表、动态表的查找 （10）各种排序算法，插入排序、选择排序、交换排序、归并排序2.1 基本概念考点1：数据结构的基本概念（1）数据数据就是采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述，简而言之，数据就是计算机化的信息。数据元素是数据的基本单位。一个数据元素可由一个或多个数据项组成，数据项是有独立含义的数据最小单位。（2）数据结构数据结构一般包括3个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式以及在这些数据上定义的运算的集合。a数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式。数据的逻辑结构分为线性结构和非线性结构。b数据的存储结构是逻辑结构在计算机存储器里的实现。c数据的运算定义在数据的逻辑结构上，而实现是在存储结构上。主要的运算包括插入、删除、排序、查找等。考点2：主要的数据存储方式实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。最主要的存储方式有顺序存储储结构和链式存储方式。（1）顺序存储结构顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元中，结点之间的关系由存储单元的邻接关系来体现，其主要特点是：a结构中只有自身信息域，没有链接信息域，因此，存储密度大，存储空间利用率高；b可以通过计算直接确定数据结构中第i个结构的存储地址；c插入、删除运算会引起大量结构的移动。（2）链式存储结构链式存储结构是在每个结点中至少包括一个指针域，用指针来体现数据元素之间逻辑上的联系。其主要特点是：a存储密度小，存储空间利用率低；b逻辑上相邻的结点物理上不必邻接，可用于线性表、树、图等多种逻辑结构的存储表示；c插入、删除操作灵活方便，不必移动结点。考点3：算法的设计与分析算法的设计采用由粗到细、由抽象到具体的逐步求精的方法。算法分析主要是分析算法所要占用的计算机资源，即时间代价和空间代价两个方面。a时间代价是当问题的规模以某种单位由1增至n时解决该问题的算法运行时所耗费的时间，也以某种单位由f(1)增至f(n)，则称该算法的时间代价为f(n)b空间代价是当问题的规模由1增至n时，解决该问题的算法实现时所占用的空间也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。2.2 线性表考点4：顺序表和一维数组线性表的逻辑结构是n个数据元素的有限序列（a1,a2,an）。按存储方式不同线性表可以分为：顺序存储的顺序表、链式存储的链表、散列存储的散列。顺序表是用一组地址连续的存储单元依次存储数据元素的线性表，其逻辑相邻的数据元素具有相邻的物理（存储）位置。对数据元素进行插入、删除操作时需要移动数据元素，存储空间被分配后难以再被扩充。各种高级语言中的一维数组就是用顺序方式存储的线性表，因此也常用一维数组来称呼顺序表。考点5：链表链表的特点是可以用一组任意的存储单元来存储线性表的各个数据元素，不要求逻辑上相邻的元素物理上也相邻。链表的优点是插入、删除等操作不需要移动元素，只需要修改指针，比较灵活，缺点是不能随机存取。链表可以分为线性链表和双向链表两种，前者也称为单链表，每个结点中只有一个指向后一个结点的指针；后者每个结点有两个指针，一个指向直接前驱结点，一个指向直接后继结点。考点6：栈与队列栈与队列都是对操作位置加以限制的线性表。可以使用顺序存储也可以采用链式存储。栈的插入和删除只能发生在线性表的一端，允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。栈是按“后进先出”的规则进行操作的。栈的常用运算主要包括入栈（push）、出栈（pop）和取栈顶元素（top）。栈是使用最为广泛的数据结构之一，表达式求值、递归过程实现都是栈应用的典型例子。队列的插入只能在线性表的一端进行，而删除在线性表的另一端进行，允许插入的一端叫队尾（rear），允许删除的一端叫队头（front）。队列是按“先进先出”的规则进行操作的。队列常用的运算有入队（enq）、出队（deq）和取队首元素（front）。队列在计算机中应用也十分广泛，硬件设备中的各种排队器、缓冲区的循环使用技术、操作系统中的作业队列等都是队列应用的例子。考点7：串串（或字符串）是由零个或多个字符组成的有限序列，零个字符的串是空串。串的存储方式有：顺序存储和链式存储。顺序存储时可以采用非紧缩方式，也可以采用紧缩方式。串的基本运算有连接、赋值、求长度、全等比较、求子串、求子串位置以及替换等。其中找子串位置（也称模式匹配）是非常重要的一种运算。2.3 多维数组、稀疏矩阵和广义表考点8：多维数组的线性存储多维数组是一维数组的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。多维数组中最常用的是二维数组。多维数组的存储方式一般是多维数组中的元素放在一个线性序列中，排列方式可以是行优先顺序或列优先顺序。二维数组第i行、第j列元素aij存储地址的计算公式为：行优先顺序：LOC（aij）=LOC（a11）+（i1）*n+（j1）*l列优先顺序：LOC（aij）=LOC（a11）+（j1）*m+（i1）*l式中m和n分别为数组中每列和每行的元素个数，l为每个数组元素占用的存储单元个数。考点9：稀疏矩阵的存储具有大量0元素的矩阵称为稀疏矩阵。对稀疏矩阵进行压缩存储，即只存储非0元素。对非0元素的分布有规律的矩阵，如下三角矩阵，按行优先顺序存储，非零元素的存储地址用下式计算： LOC（aij）=LOC（a11）+（i*（i1）/2+（j1）*l对一般的稀疏矩阵，可以采用三元组方法或十字链表方法存储。前者是按行优先顺序存储非零元素所在的行、列以及它的值构成的三元组，后者则采用十字链表。考点10：广义表的定义和存储广义表是线性表的推广，也称为列表，是由零个或多个单元素或子表所组成的有限序列。广义表与线性表的区别在于：线性表的成分都是结构上不可分的单元素，而广义表的成分既可以是单元素，又可以是有结构的表。广义表的特征：广义表的元素可以是子表，而子表的元素还可以是子表。广义表可被其他广义表所共享。广义表可以是递归的表，即广义表也可以是本身的一个子表。2.4 树形结构考点11：树及二叉树的定义及表示树是一个或多个结点组成的有限集合T，有一个特定的结点称为根，其余结点分为m（m0）个不相交的集合T1，T2，Tm。每个集合又是一棵树，被称为这个根的子树。这是树的递归定义。树的性质有以下4条：（1）树中的结点数等于所有结点的度数加1。（2）度为k的树中第i层上至多有ki1个结点(i1)。（3）深度为h的k叉树至多有(kh1)/(k1)个结点。（4）具有n个结点的k叉树的最小深度为logk(n(k1)+1)二叉树是树形结构的一个重要类型。二叉树是结点的有限集合，这个有限集合或者为空集，或者由一个根结点及两棵不相交的分别称做这个根的左子树和右子树的二叉树组成。二叉树不是树的特殊情况，树与二叉树之间最主要的区别是：二叉树的子树有左右之分，其次序不能颠倒，即使是在只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。在一棵二叉树中，如果最多只有最下面两层结点度数可以小于2，并且最下面一层结点都集中在最左边的位置上，这样的一棵二叉树称为完全二叉树。树与二叉树可以互相转化，树（树林）转换为二叉树的算法：在一棵树中，凡是兄弟结点就用线连起来，然后去掉父结点到子结点的连线，只保留父结点到第一个子结点的连线。如果把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟结点，则同样可以导出森林与二叉树的对应关系。把二叉树转换为树的算法：若某结点是其双亲的左孩子，则把该结点的右孩子，右孩子的右孩子，都与该结点双亲用线连起来，最后去掉所有的双亲到右孩子的连线。考点12：二叉树与树的周游遍历一个树形结构就是按一定的次序系统地访问树上的所有结点，使每个结点恰好被访问一次。由二叉树的定义可知，一棵二叉树由3部分组成：根、左子树和右子树。因此对二叉树的遍历也可相应地分为3类先序（根）遍历、中序（对称序）遍历、后序（根）遍历。先序遍历：访问根结点；先序遍历左子树；先序遍历右子树。中序（对称序）遍历：中序遍历左子树；访问根结点；中序遍历右子树。后序遍历：后序遍历左子树；后序遍历右子树；访问根结点。由于树也是一种层次结构，所以对树有时也进行按层遍历，所谓按层遍历，就是从树根结点开始，依次访问每一层，对同一层结点，由左至右进行访问。树和森林的遍历也主要有三种：先根次序、后根次序和层次次序。其中，前两种是按深度优先方式进行的，后一种是按广度优先方式进行的。根据树和二叉树的对应关系，可以看出，按先序遍历树正好等同于按先序遍历对应的二叉树；按后序遍历树正好等同于按对称序法遍历对应的二叉树。考点13：二叉树的存储与线索二叉树（1）二叉树的Llinkrlink法存储二叉树通常的存储方式是链式存储，每个链结点除了数据域外，还可以增加两个指针域llink和rlink，分别指向左右两个子结点。当某个结点的子结点不存在时，相应的指针值为空（nil）。（2）线索二叉树一个具有n个结点的二叉树若采用二叉链表存储结构，在2n个指针域中只有n1个指针域是用来存储结点孩子的地址的，而另外n+1个指针域存放的都是nil。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的这n+1个空指针域来记录这些信息。这些指向直接前驱结点和指向直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。（3）完全二叉树的顺序存储二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。完全二叉树或者满二叉树比较适合于顺序存储。考点14：霍夫曼算法及其应用霍夫曼（Huffman）树，也称为最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为：其中Wk为第k个叶结点的权值，Lk为第k个叶结点的路径长度。最优二叉树算法为：对于n个权为，, 的结点，首选找出两个最小的值，不妨设为和，然后对m1个权，, ,来解这个问题，并且将解中的代替，如此进行下去，直到所有的w构成一棵二叉树。给定一组权值，构造出来的霍夫曼树不是唯一的。在霍夫曼树中，权值大的结点离根最近。另外，在霍夫曼树中，没有度为1的结点。2.5 查找考点15：线性表的查找查找是确定一个元素在表或树中的位置，衡量一个查找算法的标准是对关键码平均比较的次数，或称为平均检索长度ASL。对于线性表的查找主要分下面几种：（1）顺序查找顺序查找是线性表的最简单的查找方法，其具体步骤是：用待查关键码从头开始逐个与表中元素比较，直到找出相等的元素，则查找成功；或者找遍所有元素，则查找失败。顺序查找的优点：对线性表的结点的逻辑次序无要求，对线性表的存储结构无要求。顺序查找的缺点：平均检索长度长，与表中结点个数n成正比，若检索关键码的概率相等，则查找成功时平均比较次数为(n+1)/2。查找不成功时；关键码的比较次数总是n+1次。（2）二分查找二分查找法是一种效率较高的线性表查找方法，要求线性表结点必须是按关键码值排好序的，且线性表以顺序方式存储。其具体步骤是：首选用要查找的关键码值与线性表中间位置结点的关键码值相比较，这个中间结点把线性表分成两个子表，比较相等则查找完成，不等则根据比较结果确定下一步的查找应该在哪一个子表中进行，如此进行下去，直到找到满足要求的点。二分查找的优点：平均查找长度小，为二分查找的缺点：线性表排序需要花费时间，顺序方式存储的插入、删除不便。（3）分块查找分块查找要求把线性表分成若干块，每一块中的结点不必有序，但块与块之间必须有序，还要求将各块中的最大关键码值组成一个有序的索引表。其具体步骤是：首选在索引表中用顺序查找或二分查找法确定所求记录所在的块，然后再从该块中用顺序查找方法找出所求的记录。（4）散列表查找散列法的基本思想是：由结点的关键码决定结点的存储地址，即以关键码k为自变量，通过散列函数计算出对应的函数值h(k)，将这个值解释为结点的存储地址。检索时再根据要检索的关键码值用同样的方法计算出结点位置。散列法需要解决以下两个问题：a构造好的散列函数，能够将一组关键码值尽可能均匀地安排在事先确定的范围里，并且使得发生碰撞的可能性最小。常见的散列函数有直接定址法除余法、数字分析法、折叠法、平方取中法等。b制定解决碰撞的方案。处理碰撞的方法主要有拉链法和开放定址法。影响产生冲突多少有以下三个因素：哈希函数是否均匀；处理冲突的方法；哈希表的负载因子。散列表的负载因子公式：负载因子的大小体现散列表的装满程度，越大，则散列表装得越满，发生碰撞的机会越大，一般取。考点16：树形结构与查找（1）二叉排序树二叉排序树是一类特殊的二叉树，其特点是：若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；所有的子树也遵守相同的规则。对二叉排序树中序遍历（周游）可以得到关键字从小到大的有序序列。对无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造二叉排序树的过程就是对无序序列进行排序的过程。对二叉排序树的操作主要的插入和删除操作。平衡二叉树是对二叉排序树的一种“平衡化”处理。结点的平衡因子定义为其右子树高度减去左子树高度。若任一结点的平衡因子均取1，0或1，则此二叉排序树为平衡的二叉排序树（AVL树）。平衡二叉排序树的查找方法与一般的二叉排序树完全一样，优点是总能保持检索长度为量级。往平衡二叉树插入新结点时，需要对树的结构进行必要调整，以动态地保持平衡二叉树的特点。（2）B树和B树B树和B+树是一种平衡的多路查找树形结构，用于组织外存储器中文件的动态索引结构。这样可以使得每个结点包含多个关键码值，有多个孩子，使得树的层次降低，查找时访问外存的次数减少。由B树定义可以知：am阶B树每一个结点最多有m个子树。bm阶B树根结点或为叶结点，或至少有两棵子树；中间结点至少有m/2棵子树。cm阶B树任一结点的左右子树的高度都相等。B树的主要操作是：查找、插入、删除。在m阶B树上插入关健码的过程为：aB树是从空树开始，逐个插入关键码而生成的。b在B树中，每个非叶结点的关键码个数都在m/21，m1之间。cB树中关键码的插入不是在叶结点上进行的，而是在最底层的某个非终端结点中添加一个关键码。若插入结点上关键码个数不超过m1个，则可直接插入到该结点上；否则，要进行调整，即结点的“分裂”。根据B+树的定义可知：a有n棵子树的结点中含有n个关键码。b所有关键码均出现在叶结点中，上层关键码均是下层相应结点中最大关键码的重复，且叶子结点所有关键码是有序的。c对B+树进行两种查找运算：一种是从最小关键码起顺序查找，另一种是从根结点开始，进行随机查找。2.6 排序考点17：插入排序插入排序的基本思想是每次将一个待排序记录按其关键码值大小插入到前面已排序的文件中的合适位置上，直到记录插入完为止。a直接插入排序：在已排好序的序列中查找插入位置时用顺序法查找，找到插入位置后将该位置原来的记录及其后面所有的记录顺序后移一个位置，空出该位置来插入记录。b二分法插入排序：在已排好的序列中找插入的位置时，用二分法查找，找到插入位置后和直接插入排序法同样处理。cshell排序：又称缩小增量法，是按增量将文件分组。首先取增量d1n，把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，各组内用插入法排序，然后取d2 d1，重复上述分组和排序工作，直至取d=1，即所有记录放在一个组中为止。考点18：选择排序选择排序的基本思想是每次从待排序的记录中选出关键码值最小（或最大）的记录，顺序放在已排记录序列的最后，直到全部排完，这里主要讲堆排序堆排序是对一组待排序的关键码，首先把它们按堆的定义排成一个序列（称为建堆），这就找到了最小的关键码，然后将最小的关键码取出，用剩下的关键码再建堆，便得到次最小的关键码，如此反复进行，直至将全部关键码排好序为止。堆排序的两个主要问题：（1）如何将n个元素的序列按关键码建成堆。（2）输出堆顶元素后，如何调整剩余元素使之成为一个新堆。考点19：交换排序交换排序主要是起泡排序和快速排序。a起泡排序是将排序的记录顺次两两比较，若为逆序则进行交换，将序列照此方法从头到尾处理一遍称做一趟起泡。第二趟起泡再将次最大关键码交换到倒数第二个位置，即它的最终位置，如此进行下去，若某一趟起泡过程中没有发生任何交换，或排序已经进行了n1趟，则排序过程结束。b快速排序是在待排序序列中任取一个记录，以它为基准用交换的方法将所有的记录分成两部分，关键码值比它小的一个部分，关键码值比它大的在另一部分，再分别对两个部分实施上述过程，一直重复到排序完成。考点20：归并排序归并排序的基本思想是对两个或两个以上的表组合成一个新的有序表。排序方法为先将原始序列中的每个关键字都看作一个序列，两两有序归并，逐步扩大于序列尺寸，直到全部排序完成。2.7 经典题解一、选择题1下列哪一个术语与数据的存储结构有关。（2007.09）A）栈B）队列C）链表D）线性表解析：数据的存储结构是逻辑结构在计算机存储器里的实现，如链表。数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式。逻辑结构分为线性结构（如线性表、栈、队列）和非线性结构（如树）。答案：C2下列关于数据的逻辑结构的叙述中，哪一条是不正确的。（2007.09）A）数据的逻辑结构是数据间关系的描述B）数据的逻辑结构不仅反映数据间的逻辑关系，而且包括其在计算机中的存储方式C）数据的逻辑结构分为线性结构和非线性结构D）线性表是典型的线性结构解析：数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式，在计算机中的存储是由存储结构决定的。逻辑结构分为线性结构（如线性表、栈、队列）和非线性结构（如树）。答案：B3下列关于数据运算的叙述中，哪一条是不正确的。（2007.09）A）数据运算是数据结构的一个重要方面B）数据运算的具体实现在数据的逻辑结构上进行C）检索是一种常用的运算D）插入是一种常用的运算解析：数据的运算定义在数据的逻辑结构上，而实现是在存储结构上。主要的运算包括插入、删除、排序、查找等。答案：B4栈结构不适用于下列哪一种运用。（2007.09）A）表达式求值B）快速排序算法的实现C）树的层次次序周游算法的实现D）二叉树对称序周游算法的实现解析：树的层次次序周游算法需要先存储每一层的结点，然后按照先进后出的顺序依次访问结点信息，需要用先进先出的队列来实现，而不是用先进后出的栈来实现；表达式求值，需要设置操作数和操作符两个栈；快速排序需要用栈实现递归；二叉树对称序周游算法即中序周游算法，也需要用栈结构实现。答案：C5双链表的每个结点包括两个指针域。其中rlink指向结点的后继，llink指向结点的前驱。如果要在p所指结点后插入q所指的新结点，下列哪一个操作序列是正确的。（2007.09）A）p.rlink.llink:=q; p.rlink:=q; q.llink:=p; q.rlink:=p.rlink;B）p.llink.rlink:=q; p.llink:=q; q.rlink:=p; q.llink:=p.llink;C）q.llink:=p; q.rlink:= p.rlink ; p.rlink.llink:=q; p.rlink:=q;D）q.rlink:=p; q.llink:=p.llink; p.llink.rlink:=q; p.llink:=q;解析：需要先将待插入结点q的左指针更新为p，然后将q右指针的信息更新为p的右指针所指向结点，再将p的右指针所指结点的左指针信息更新为q，最后将p的右指针信息更新为q。pqnew nodeLlinkRlinkLlinkRlinkLlinkRlink答案：C6在包含1000个元素的线性表中实现如下运算，哪一个所需执行时间最长。（2007.09）A）线性表按顺序方式存储，在线性表的第100个结点后面插入一个新结点B）线性表按链接方式存储，在线性表的第100个结点后面插入一个新结点C）线性表按顺序方式存储，删除线性表的第900个结点D）线性表按链接方式存储，删除指针P所指向的结点解析：线性表按顺序方式存储，执行插入操作时要将插入点后的所有元素平移一个单位，在1000个元素的线性表的第100个结点后插入新结点需要移动900个元素。链接方式存储插入新结点需要查找100次找到结点再插入。线性表按顺序方式存储，删除第900个元素要将第9001000个元素向前移动一个单位。按链接方式存储，删除指针P指向结点，其平均查找长度为500.5。查找开销比移动开销要小。答案：B7设某散列表的当前状态如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1907519476855958208该散列表的负载因子约为。（2007.09）A）0.37B）0.42C）0.58D）0.73解析：散列表的负载因子公式：由题可知负载因子为7/19=0.37答案：A8设有关键码序列(Q、G、M、Z、A、N、B、P、X、H、Y、S、T、L、K、E)，采用堆排序法进行排序，经过初始建堆后关键码值A在序列中的序号是。（2007.09）A）1B）4C）8D）12解析：堆排序是将待排序的关键码先按堆的定义排成一个序列（称为建堆），找到最小的关键码，然后将最小的关键码取出，用剩下的关键码再建堆，便得到次最小的关键码，如此反复进行，直至将全部关键码排好序为止。所以初始建堆关键码A即为堆顶，序号为1。答案：A9对n个记录的文件进行起泡排序，所需要的辅助存储空间为。（2007.09）A）O(1)B）O(n)C）O(n).D）O()解析：起泡排序仅需一个辅助存储空间作为记录在交换位置时的缓存空间。答案：A10下列关于数据结构基本概念的叙述中，哪一条是不正确的。（2007.04）A）数据是采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述B）数据元素（或称结点、记录等）是数据的基本单位C）一个数据元素至少由两个数据项组成D）数据项是有独立含义的数据最小单位解析：一个数据元素可由一个或若干个数据项组成。数据项是有独立含义的不可分割的数据的最小单位。数据是所有能输入到计算机中并被计算机程序识别、存储和处理的符号的总称。答案：C11下列关于链式存储结构的叙述中，哪些是正确的。（2007.04）I逻辑上相邻的结点物理上不必邻接II每个结点都包含恰好一个指针域III用指针来体现数据元素之间逻辑上的联系IV可以通过计算机直接确定第i个结点的存储地址V存储密度小于顺序存储结构A）I、II和IIB）I、II、III和IVC）II、IV和VD）I、III和V解析：链式存储结构中除了包含保存数据元素自身信息的信息域外，还有表示数据元素之间的链接信息的指针域，因此比顺序存储结构的存储密度低；链式存储结构中逻辑上相邻的数据元素在物理上不一定相邻；不是所有节点都包含指针域，如单向链表中最后一个节点的指针为空。答案：D12和13基于以下描述：有一个初始为空的栈和输入序列A、B、C、E、F、G：现发过如下操作：push,push,top,pop,push,push,top,push,pop,pop,pop.12下列哪一个是正确的从栈中删除元素的序列。（2007.04）A）BEB）BDC）BEDCD）BDEC解析：栈的操作遵循后进先出的原则。题中的操作依次为：A进栈、B进栈、B读取、B删除、C进栈、D进栈、E进栈、E删除、D删除、C删除。由此可见删除的序列为BEDC。答案：C13下列哪一个是上述操作序列完成后栈中的元素列表（从底到顶）。（2007.04）A）AB）BDC）ABCED）ABCDE解析：通过上题的分析可知，在操作过程中进栈的有ABCDE，删除的有BEDC，因此最后栈中的元素只有A。答案：A1415基于如下所示的二叉树。14该二叉树对应的树林包括几棵树。（2007.04）A）1B）2C）3D）4解析：二叉树转换为树林时，二叉树的根就是树林第一棵树的根；二叉树的左子树转换为树林的第一棵树，二叉树的右子树对应于树林中其余的树；二叉树右子树的根节点作为余下树中第一棵树的根节点，其余以此类推。本题中的二叉树应该包含2棵树。答案：B15按后根次序周游该二叉树对应的树林，所得到的结点序列为。（2007.04）A）DBAFEGCB）ABCDEFGC）DBFGECAD）ACBEGDF解析：后序遍历二叉树的次序是：后序遍历左子树，后序遍历右子树，访问根节点。因此后序遍历此二叉树对应的树林所得的节点序列为选项C。答案：C16按层次次序周游该二叉对应的树林，所得到的结点序列为。（2007.04）A）DBAFEGCB）ABCDEFGC）DBFGECAD）ACBEGDF解析：按层次次序遍历二叉树的次序是：从树的根节点开始，依次访问每一层，对同一层节点，由左到右进行访问。因此按层次次序遍历此二叉树对应的树林所得的节点序列为选项B。答案：B17设待排序关键码序列为(25，18，9，33，67，82，53，95，12，70)，要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟排序完成后关键码95被放到第几个位置。（2007.04）A）7B）8C）9D）10解析：快速排序法第一趟排序后，关键码序列为(12，18，9，25，67，82，53，95，33，70)，因此关键码95处在第8个位置。答案：B18设散列表的地址空间为0到16，散列函数为h(k)=kmod17,用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值190，89，217，208，75，177，则最后一个关键码177的地址为。（2007.04）A）6B）7C）8D）9解析：本题采用除留余数法构造散列函数，将关键码值190，89，217，208，75，177分别带入h(k)=kmod17，得到散列地址分别为3，4，13，4，7，7，在存储关键码208时，由于其散列地址4与前面的一个关键码发生冲突，因此其存储地址向后移1位到5。而存储关键码177时，由于其散列地址7与前面的一个关键码发生冲突，因此其存储地址再向后移1位到8。答案：C19下列哪些是数据结构研究的内容。（2006.09）I数据的采集II数据的逻辑组织III数据的存储实现IV数据的传输V数据的检索A）II和IVB）I、II和IIIC）II、III和VD）I、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的顺序进栈，下列哪一个序列是可能的出栈序列。（2006.09）A）E、D、C、B、A、FB）B、C、E、F、A、DC）C、B、E、D、A、FD）A、D、F、E、B、C解析：对于选项A，因为该栈最多只能容纳4个元素，而E是第五个元素，在前4个元素还没出栈的情况下是不可能进栈再出栈的。对于选项B，A元素不可能在D元素还没出栈的情况下先出栈；对于选项C，其出栈序列为：C、B、E、D、A、F；对于选项D，B元素不可能在C元素还没出栈情况下出栈，出栈序列为选项C。答案：C23从单链表中删除指针s所指结点的下一个结点t，其关键运算步骤为。（2006.09）A）s .link:=tB）t .link:=s C）t .link:=s .linkD）s .link:=t .link 解析：要从单链表中删除指针s所指节点的下一个节点t，则原节点t指的后继节点成为s所指的后继节点，因此关键运算步骤为：s .link:=t .link。答案：D24按行优先顺序存储下三角矩阵的非零元素，则计算非零元素(1ijn)的地址公式为（2006.09）A）B）C）D）解析：非零元素aij在矩阵中处在第i行第j列，在按行优先顺序存储时，应先存储前i1行的非零元素和同一行的前j1个元素。如果a11的存储地址为LOC(a11)，则aij的存储地址为D。答案：D25下列关于二叉树周游的叙述中，哪一项是正确的。（2006.09）A）若一个结点是某二叉树对称序的最后一个结点，则它必是该二叉树前序的最后一个结点B）若一个结点是某二叉树前序的最后一个结点，则它必是该二叉树对称序的最后一个结点C）若一个树叶是某二叉树对称序的最后一个结点，则它必是该二叉树前序的最后一个结点D）若一个树叶是某二叉树前序的最后一个结点，则它必是该二叉树对称序的最后一个结点解析：若一个树叶是某二叉树对称序的最后一个节点，则它必是该二叉树最右边的树叶，即前序的最后一个节点。而若将“树叶”改为“结点”则不正确，因为有可能出现二叉树最右结点无右孩子的情况。答案：C26如下所示是一棵5阶B树，该B树现在的层数为2。从该B树中删除关键码38后，该B树的第2层的结点数为。（2006.09）A）6B）7C）8D）9解析：删除38后该节点剩下的关键码的个数为1，小于5/21=2，所以删除后要将该结点剩余的41与双亲结点中的45一起移至原结点的右兄弟节点，故结点数减1，变为6个。答案：A27在待排序文件已基本有序的前提下，下列排序方法中效率最高的是。（2006.09）A）直接插入排序B）直接选择排序C）快速排序D）归并排序解析：直接插入排序，若文件基本有序，则比较次数最小为n1次，移动次数为0；直接选择排序，无论待排序文件是否基本有序，其比较次数均为n(n1)/2，若文件基本有序，则移动次数减少，最小为0；快速排序在文件基本有序时蜕化为起泡排序，时间复杂度为n(n1)/2；对于归并排序，无论待排序文件是否基本有序，其比较次数均为，若文件基本有序，则移动次数减少，最小为0，可见直接插入排序效率最高。答案：A28下列关于数据结构基本概念的叙述中，哪一条是正确的。（2006.04）A）数据的逻辑结构分为表结构和树结构B）数据的存储结构分为线性结构和非线性结构C）数据元素是数据的基本单位D）节点是有独立含义的数据最小单位解析：数据的基本单位是数据元素，故C正确。数据的逻辑结构可以划分为集合、线性结构、树型结构和图状结构（网状结构）。数据的存储结构指的是数据结构在计算机中的表示（映像），它包括顺序存储和链式存储两种结构。节点是由若干位组合起来形成的位串，数据的最小单位是节点中的一个二进制数位（bit）。答案：C29下列关于串的叙述中，哪一条是正确的。（2006.04）A）串是由零个或多个字符组成的有限序列B）空串是由空格构成的串C）串只能顺序存储D）“推入”是串的基本运算之一解析：串是由零个或多个字符组成的有限序列；如果串中没有任何字符，则称为空串。由一个或多个空格组成的串称为空格串，空格串不是空串，因为空格串中有字符；串既可以顺序存储也可以链表存储；串的基本操作一般是以“串的整体”作为操作对象，“推入”不是串的基本运算。答案：A30双链表的每个结点包括两个指针域。其中rlink指向结点的后继，llink指向结点的前驱。如果要在p所指结点前面插入q所指的新结点，下列哪一个操作序列是正确的。（2006.04）A）p.rlink.llink:=q；p.rlink:=q；q.llink:=p；q.rlink:=p.rlink；B）p.llink.rlink:=q；p.llink:=q；q.rlink:=p；q.llink:=p.llink；C）q.llink:=p；q.rlink:=p.rlink；p.rlink.llink:=q；p.rlink:=q；D）q.rlink:=p；q.llink:=p.llink；p.llink.rlink:=q；p.llink:=q；解析：首先要修改p所指节点的llink字段和原前驱节点的rlink字段，然后置q所指节点的rlink和llink值，即q.rlink:=p；q.llink:=p.llink； p.llink.rlink:=q；p.llink:=q。答案：D31下列哪一个不是队列的基本运算。（2006.04）A）从队尾插入一个新元素B）从队列中删除第i个元素C）判断一个队列是否为空D）读取队头元素的值解析：队列的基本操作有：构造一个空队列；将队列清为空队列；判断队列是否为空队列；计算队列的长度；读取队列的队头元素；向队列插入一个元素为该队列的队尾元素；删除队列队头元素。队列只允许在队尾插入元素，而在队头删除元素。答案：B32栈结构不适用于下列哪一种应用。（2006.04）A）表达式求值B）树的层次次序周游算法的实现C）二叉树对称序周游算法的实现D）快速排序算法的实现解析：见第4题。答案：B33按层次次序将一棵有n个结点的完全二叉树的所有结点从1到n编号，当in/2时，编号为i的结点的左孩子的编号是。（2006.04）A）2i1B）2iC）2i+1D）不确定解析：若对有n个节点的完全二叉树按层次从上到下，每个层次从左至右的规则为节点编号，若in/2，则编号为i的节点的左孩子节点的编号为2i；若in/2，则编号为i的节点没有左孩子节点。答案：B34对于给出的一组权w=10，12，16，21，30，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为。（2006.04）A）89B）189C）200D）300解析：霍夫曼算法建立的扩充二叉树如下图所示。所以带权外部路径长度为(21+16)2+302+(12+10)3200答案：C35设散列表的地址空间为0到10，散列函数为h(k)=kmod11，用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值95，14，27，68，82，则最后一个关键码82的地址为。（2006.04）A）4B）5C）6D）7解析：本题采用除留余数法构造散列函数，将关键码值95，14，27，68，82分别带入h（k）=kmod11，得到散列地址分别为7，3，5，2，5，当存储关键码82时，由于其散列地址与前面的一个关键码发生冲突，因此其存储地址向后移1位到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个节点，依次与前i1个节点进行比较，最终确认结点的位置。答案：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个数据元素组成的有限序列，其中的数据元素既可以是单元素，也可以是子表；广义表既可以是自身的子表，也可是空表。答案：A4143题基于下图所示的二叉树：41该二叉树对应的树林包括几棵树。（2005.09）A）1B）2C）3D）4解析：二叉树转换为树林，二叉树的根就是树林第一棵树的根；二叉树的左子树转换为树林的第一棵树，二叉树的右子树对应于树林中其余的树；二叉树右子树的根节点作为余下树中第一棵树的根节点，其余以此类推。本题中的二叉树应该包含4棵树。答案：D42如果用lli