《全国计算机等级考试解析例题精解与应试模拟三级数据.pdf》由会员分享，可在线阅读，更多相关《全国计算机等级考试解析例题精解与应试模拟三级数据.pdf（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章数据结构与算法本章大纲要求：(1)基本概念(2)线性表(3)多维数组、稀疏矩阵和广义表(4)树形结构(5)查找(6)排序重要考点提示：根据对历年真题的分析可知，本章考核内容约占1 5%,主要包括以下几个方面：(1)数据结构和算法的基本概念(2)数据的逻辑结构、存储结构(3)顺序表和一维数组(4)链表、栈、队列、串的概念与操作(5)稀疏矩阵的存储、广义表的定义与存储(6)二叉树的定义、存储与表示、线索二叉树(7)树与二叉树的转换、二叉树的周游算法(8)霍夫曼算法及其应用(9)静态表、动态表的查找(1 0)各种排序算法，插入排序、选择排序、交换排序、归并排序2.1基 本 概 念考点1：数据结
2、构的基本概念*(1)数据数据就是采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述，简而言之,数据就是计算机化的信息。数据元素是数据的基本单位。一个数据元素可由一个或多个数据项组成，数据项是有独立含义的数据最小单位。(2)数据结构数据结构一般包括3 个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式以及在这些数据上定义的运算的集合。a.数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式。数据的逻辑结构分为线性结构和非线性结构。b.数据的存储结构是逻辑结构在计算机存储器里的实现。c.数据的运算定义在数据的逻辑结构上，而实现是在
3、存储结构上。主要的运算包括插入、删除、排序、查找等。考点2：主要的数据存储方式*实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。最主要的存储方式有顺序存储储结构和链式存储方式。(1)顺序存储结构顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元中，结点之间的关系由存储单元的邻接关系来体现，其主要特点是：a.结构中只有自身信息域，没有链接信息域，因此，存储密度大，存储空间利用率高；b.可以通过计算直接确定数据结构中第i 个结构的存储地址；c.插入、删除运算会引起大量结构的移动。(2)链式存储结构链式存储结构是在每个结点中至少包括一个指针域，用指针来体现数据元素之间逻辑上的联系
4、。其主要特点是：a.存储密度小，存储空间利用率低；b.逻辑上相邻的结点物理上不必邻接，可用于线性表、树、图等多种逻辑结构的存储表示；c.插入、删除操作灵活方便，不必移动结点。考点3：算法的设计与分析算法的设计采用由粗到细、由抽象到具体的逐步求精的方法。算法分析主要是分析算法所要占用的计算机资源，即时间代价和空间代价两个方面。a.时间代价是当问题的规模以某种单位由1增至n 时解决该问题的算法运行时所耗费的时间，也以某种单位由f(l)增至f(n),则称该算法的时间代价为f(n)b.空间代价是当问题的规模由1 增 至 n 时，解决该问题的算法实现时所占用的空间也以某种单位由g(l)增至g(n),则称
5、该算法的空间代价为g(n)o2.2线性表考点4：顺序表和一维数组线性表的逻辑结构是个数据元素的有限序列(切,2”.,东)。按存储方式不同线性表可以分为:顺序存储的顺序表、链式存储的链表、散列存储的散列。顺序表是用一组地址连续的存储单元依次存储数据元素的线性表，其逻辑相邻的数据元素具有相邻的物理(存储)位置。对数据元素进行插入、删除操作时需要移动数据元素，存储空间被分配后难以再被扩充。各种高级语言中的一维数组就是用顺序方式存储的线性表，因此也常用一维数组来称呼顺序表。考点5：链表*链表的特点是可以用一组任意的存储单元来存储线性表的各个数据元素，不要求逻辑上相邻的元素物理上也相邻。链表的优点是插入
6、、删除等操作不需要移动元素，只需要修改指针，比较灵活,缺点是不能随机存取。链表可以分为线性链表和双向链表两种，前者也称为单链表，每个结点中只有一个指向后一个结点的指针；后者每个结点有两个指针，一个指向直接前驱结点，一个指向直接后继结点。考点6：栈与队列安栈与队列都是对操作位置加以限制的线性表。可以使用顺序存储也可以采用链式存储。栈的插入和删除只能发生在线性表的一端，允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。栈是按“后进先出”的规则进行操作的。栈的常用运算主要包括入栈(p u s h)、出 栈(p o p)和取栈顶元素(t o p)。栈是使用最为广泛的数据结
7、构之一，表达式求值、递归过程实现都是栈应用的典型例子。队列的插入只能在线性表的一端进行，而删除在线性表的另一端进行，允许插入的一端叫队尾(r e a r),允许删除的一端叫队头(f r o n t)。队列是按“先进先出”的规则进行操作的。队列常用的运算有入队(e n q)、出 队(d e q)和取队首元素(f r o n t),队列在计算机中应用也十分广泛，硬件设备中的各种排队器、缓冲区的循环使用技术、操作系统中的作业队列等都是队列应用的例子。考点7：串串(或字符串)是由零个或多个字符组成的有限序列，零个字符的串是空串。串的存储方式有:顺序存储和链式存储。顺序存储时可以采用非紧缩方式，也可以采
8、用紧缩方式。串的基本运算有连接、赚值、求长度、全等比较、求子串、求子串位置以及替换等。其中找子串位置(也称模式匹配)是非常重要的一种运算。2.3多维数组、稀疏矩阵和广义表考点8：多维数组的线性存储*多维数组是一维数组的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。多维数组中最常用的是二维数组。多维数组的存储方式一般是多维数组中的元素放在一个线性序列中，排列方式可以是行优先顺序或列优先顺序。二维数组第i 行、第 j 列元素a”存储地址的计算公式为：行优先顺序：L O C (aij)=L 0 C (an)+(i-1)*n+(j-1)列优先顺序：L O C (au)=L
9、 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：广义表的定义和存储广义表是线性表的推广，也称为列
10、表，是由零个或多个单元素或子表所组成的有限序列。广义表与线性表的区别在于：线性表的成分都是结构上不可分的单元素，而广义表的成分既可以是单元素，又可以是有结构的表。广义表的特征：广义表的元素可以是子表，而子表的元素还可以是子表。广义表可被其他广义表所共享。广义表可以是递归的表，即广义表也可以是本身的一个子表。2.4树形结构考点11：树及二叉树的定义及表示*树是一个或多个结点组成的有限集合T,有一个特定的结点称为根，其余结点分为m(m 2 O)个不相交的集合T l，T 2,，T m。每个集合又是一棵树，被称为这个根的子树。这是树的递归定义。树的性质有以下4条：(1)树中的结点数等于所有结点的度数加
11、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、边的位置上，这样的一棵二叉树称为完全二叉树。树与二叉树可以互相转化，树(树林)转换为二叉树的算法：在一棵树中，凡是兄弟结点就用线连起来，然后去掉父结点到子结点的连线，只保留父结点到第一个子结点的连线。如果把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟结点，则同样可以导出森林与二叉树的对应关系。把二叉树转换为树的算法：若某结点是其双亲的左孩子，则把该结点的右孩子，右孩子的右孩子，都与该结点双亲用线连起来，最后去掉所有的双亲到右孩子的连线。考点12：二叉树与树的周游*遍历一个树形结构就是按一定的次序系统地访问树上的所有结点，使每个结点恰好被访问一次。由二叉树的定义可知，一棵二叉树由3部分组成
13、：根、左子树和右子树。因此对二叉树的遍历也可相应地分为3 类 先 序(根)遍 历、中序(对称序)遍历、后 序(根)遍 历。先序遍历：访问根结点；先序遍历左子树；先序遍历右子树。中序(对称序)遍历：中序遍历左子树；访问根结点；中序遍历右子树。后序遍历：后序遍历左子树；后序遍历右子树；访问根结点。由于树也是一种层次结构，所以对树有时也进行按层遍历，所谓按层遍历，就是从树根结点开始，依次访问每一层，对同一层结点，由左至右进行访问。树和森林的遍历也主要有三种：先根次序、后根次序和层次次序。其中，前两种是按深度优先方式进行的，后一种是按广度优先方式进行的。根据树和二叉树的对应关系，可以看出，按先序遍历树
14、正好等同于按先序遍历对应的二叉树；按后序遍历树正好等同于按对称序法遍历对应的二叉树。考点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。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信
15、息，可以利用二叉树的二叉链表存储结构中的这n+1个空指针域来记录这些信息。这些指向直接前驱结点和指向直接后继结点的指针被称为线索(t h r e a d),加了线索的二叉树称为线索二叉树。(3)完全二叉树的顺序存储二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。完全二叉树或者满二叉树比较适合于顺序存储。考点14：霍夫曼算法及其应用*霍 夫 曼(H u f f m a n)树，也称为最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。设二叉树具有n个带权值的叶结点，那么从根结点到各 个叶结点的路径长度与
16、相应结点权值的乘积之和叫做二叉树的带权路径长度，记为：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：线性表的查找查找是确定一个元素在表或树中的位置，衡量一个查找算法的标准是对关键码平均比较的次数，或称为平均检
17、索长度A S L。对于线性表的查找主耍分下面几种：(1)顺序查找顺序查找是线性表的最简单的查找方法，其具体步骤是：用待查关键码从头开始逐个与表中元素比较，直到找出相等的元素，则查找成功；或者找遍所有元素，则查找失败。顺序查找的优点：对线性表的结点的逻辑次序无要求，对线性表的存储结构无要求。顺序查找的缺点：平均检索长度长，与表中结点个数n成正比，若检索关键码的概率相等，则查找成功时平均比较次数为(n+l)/2。查找不成功时；关键码的比较次数总是n+1 次。(2)二分查找二分查找法是一种效率较高的线性表查找方法，要求线性表结点必须是按关键码值排好序的，且线性表以顺序方式存储。其具体步骤是：首选用要
18、查找的关键码值与线性表中间位置结点的关键码值相比较，这个中间结点把线性表分成两个子表，比较相等则查找完成，不等则根据比较结果确定下一步的查找应该在哪一个子表中进行，如此进行下去，直到找到满足要求的点。二分查找的优点：平均查找长度小，为 l og?!二分查找的缺点：线性表排序需要花费时间，顺序方式存储的插入、删除不便。(3)分块查找分块查找要求把线性表分成若干块，每一块中的结点不必有序，但块与块之间必须有序，还要求将各块中的最大关键码值组成一个有序的索引表。其具体步骤是：首选在索引表中用顺序查找或二分查找法确定所求记录所在的块，然后再从该块中用顺序查找方法找出所求的记录。(4)散列表查找散列法的
19、基本思想是：由结点的关键码决定结点的存储地址，即以关键码k 为自变量，通过散列函数计算出对应的函数值h(k),将这个值解释为结点的存储地址。检索时再根据要检索的关键码值用同样的方法计算出结点位置。散列法需要解决以下两个问题：a.构造好的散列函数，能够将一组关键码值尽可能均匀地安排在事先确定的范围里，并且使得发生碰撞的可能性最小 常见的散列函数有直接定址法除余法、数字分析法、折叠法、平方取中法等。b.制定解决碰撞的方案。处理碰撞的方法主要有拉链法和开放定址法。影响产生冲突多少有以下三个因素：哈希函数是否均匀；处理冲突的方法；哈希表的负载因子。散列表的负载因子公式：散列表中结点的数目C C -基本
20、区域能容纳的结谶负载因子的大小体现散列表的装满程度，e越大，则散列表装得越满，发生碰撞的机会越大，一般取a 1 o考点16：树形结构与查找*(1)二叉排序树二叉排序树是一类特殊的二叉树，其特点是：若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；所有的子树也遵守相同的规则。对二叉排序树中序遍历(周游)可以得到关键字从小到大的有序序列。对无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造二叉排序树的过程就是对无序序列进行排序的过程。对二叉排序树的操作主要的插入和删除操作。平衡二叉树是对二叉排序树的一种“平衡化”处理。结点的平衡因子
21、定义为其右子树高度减去左子树高度。若任一结点的平衡因子均取一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树根结点或为叶结点，或至少有
22、两棵子树；中间结点至少有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.所有关键码均出现在叶结点中，上层关键码均是下层相应结点中最大关键码的重复，
23、且叶子结点所有关键码是有序的。c.对B+树进行两种查找运算：一种是从最小关键码起顺序查找，另一种是从根结点开始，进行随机查找。2.6排序考点17：插入排序插入排序的基本思想是每次将一个待排序记录按其关键码值大小插入到前面已排序的文件中的合适位置上，直到记录插入完为止。a.直接插入排序：在已排好序的序列中查找插入位置时用顺序法查找，找到插入位置后将该位置原来的记录及其后面所有的记录顺序后移一个位置，空出该位置来插入记录。b.二分法插入排序：在已排好的序列中找插入的位置时，用二分法查找，找到插入位置后和直接插入排序法同样处理。c.s he l l排序：又称缩小增量法，是按增量将文件分组。首先取增量
24、d i n,把全部记录分成出个组，所有距离为出倍数的记录放在一组中，各组内用插入法排序，然后取d 2 d i，重复上述分组和排序工作，直至取d=l,即所有记录放在一个组中为止。考点18：选择排序*选择排序的基本思想是每次从待排序的记录中选出关键码值最小（或最大）的记录，顺序放在已排记录序列的最后，直到全部排完，这里主要讲堆排序堆排序是对一组待排序的关键码，首先把它们按堆的定义排成一个序列（称为建堆），这就找到了最小的关键码，然后将最小的关键码取出，用剩下的关键码再建堆，便得到次最小的关键码，如此反复进行，直至将全部关键码排好序为止。堆排序的两个主要问题：（1）如何将n个元素的序列按关键码建成堆
25、。（2）输出堆顶元素后，如何调整剩余元素使之成为一个新堆。考点19：交换排序*交换排序主要是起泡排序和快速排序。a.起泡排序是将排序的记录顺次两两比较，若为逆序则进行交换，将序列照此方法从头到尾处理一遍称做一趟起泡。第二趟起泡再将次最大关键码交换到倒数第二个位置，即它的最终位置，如此进行下去，若某一趟起泡过程中没有发生任何交换，或排序已经进行了 n-1趟，则排序过程结束。b.快速排序是在待排序序列中任取一个记录，以它为基准用交换的方法将所有的记录分成两部分，关键码值比它小的一个部分，关键码值比它大的在另一部分，再分别对两个部分实施上述过程，一直重复到排序完成。考点20：归并排序归并排序的基本思
26、想是对两个或两个以上的表组合成一个新的有序表。排序方法为先将原始序列中的每个关键字都看作一个序列，两两有序归并，逐步扩大于序列尺寸，直到全部排序完成。2.7经典题解一、选择题1 .下 列 哪 一 个 术 语 与 数 据 的 存 储 结 构 有 关。（2 0 0 7.0 9）A）栈B）队列C）链表 D）线性表解析：数据的存储结构是逻辑结构在计算机存储器里的实现，如链表。数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式。逻辑结构分为线性结构（如线性表、栈、队列）和非线性结构（如树）。答案：C2 .下列关于数据的逻辑结构的叙述中，哪 一 条 是 不
27、正 确 的。（2 0 0 7.0 9）A）数据的逻辑结构是数据间关系的描述B）数据的逻辑结构不仅反映数据间的逻辑关系，而且包括其在计算机中的存储方式C）数据的逻辑结构分为线性结构和非线性结构D）线性表是典型的线性结构解析：数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式，在计算机中的存储是由存储结构决定的。逻辑结构分为线性结构（如线性表、栈、队列）和非线性结构（如树）。答案：B3 .下列关于数据运算的叙述中，哪 一 条 是 不 正 确 的.（2 0 0 7.0 9）A）数据运算是数据结构的一个重要方面B）数据运算的具体实现在数据的逻辑结构上进行
28、C）检索是一种常用的运算D）插入是一种常用的运算解析：数据的运算定义在数据的逻辑结构上，而实现是在存储结构上。主要的运算包括插入、删除、排序、查找等。答案：B4.栈 结 构 不 适 用 于 下 列 哪 一 种 运 用。（2007.09）A）表达式求值B）快速排序算法的实现C）树的层次次序周游算法的实现D）二叉树对称序周游算法的实现解析：树的层次次序周游算法需要先存储每一层的结点，然后按照先进后出的顺序依次访问结点信息，需要用先进先出的队列来实现，而不是用先进后出的栈来实现；表达式求值，需要设置操作数和操作符两个栈；快速排序需要用栈实现递归；二叉树对称序周游算法即中序周游算法，也需要用栈结构实现
29、。答案：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
30、:=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个结点
31、后面插入一个新结点B）线性表按链接方式存储、在线性表的第100个结点后面插入一个新结点C）线性表按顺序方式存储，删除线性表的第900个结点D）线性表按链接方式存储，删除指针P 所指向的结点解析：线性表按顺序方式存储，执行插入操作时要将插入点后的所有元素平移一个单位，在 1000个元素的线性表的第100个结点后插入新结点需要移动900个元素。链接方式存储插入新结点需要查找100次找到结点再插入。线性表按顺序方式存储，删除第900个元素要将第900-1000个元素向前移动一个单位。按链接方式存储，删除指针P 指向结点，其平均查找长度为500.5。查找开销比移动开销要小。答案：B7.设某散列表的当前
32、状态如下：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解析：
33、堆排序是将待排序的关键码先按堆的定义排成一个序列(称为建堆)，找到最小的关键码，然后将最小的关键码取出，用剩下的关犍码再建堆，便得到次最小的关键码，如此反复进行，直至将全部关键码排好序为止。所以初始建堆关键码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)数据是
34、采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述B)数据元素(或称结点、记录等)是数据的基本单位C)一个数据元素至少由两个数据项组成D)数据项是有独立含义的数据最小单位解析：一个数据元素可由一个或若干个数据项组成。数据项是有独立含义的不可分割的数据的最小单位。数据是所有能输入到计算机中并被计算机程序识别、存储和处理的符号的总称。答案：CII.下列关于链式存储结构的叙述中，哪 些 是 正 确 的。(2 0 0 7.0 4)I.逻辑上相邻的结点物理上不必邻接II.每个结点都包含恰好一个指针域III.用指针来体现数据元素之间逻辑上的联系IV.可以通过计算机直接确定第i 个结点的存储地
35、址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
36、 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)BDC)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,删除的有
37、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)AC
38、BEGDF解析：后序遍历二叉树的次序是：后序遍历左子树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),要按关键码值递增的顺序进
39、行排序，采取以第一个关键码为分界元素的快速排序法，第一趟排序完成后关键码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解析：本题采用除留余数法构造散列函数，将
40、关键码值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 和
41、 V解析：数据的采集和数据的检索不属于数据结构研究的内容。数据结构一般包括三方面内容：数据的逻辑结构,它是从逻楫关系上描述数据，与数据的存储无关。数据的存储器内表示，它是指用计算机语言实现的逻辑结构，它依赖于计算机语言。数据的运算，即对数据施加的操作。答案：c20.下列关于数据元素的叙述中，哪 一 项 是 不 正 确 的。(2006.09)A)数据元素是数据的基本单位，即数据集合中的个体B)数据元素是有独立含义的数据最小单位C)数据元素又称作结点D)数据元素乂称作记录解析：数据项是具有独立含义的最小标识单位，而非数据元素。数据元素是数据的基本单位，一个数据元素可以由若干个数据项组成，有时也称作
42、结点、记录、表目等。答案：B21.下列关于数据的存储结构的叙述中，哪 一 项 是 正 确 的.(2006.09)A)数据的存储结构是数据间关系的抽象描述B)数据的存储结构是逻辑结构在计算机存储器中的实现C)数据的存储结构分为线性结构和非线性结构D)数据的存储结构对数据运算的具体实现没有影响解析：数据的存储结构是指数据的逻辑结构在计算机存储器中的表示，又称数据的物理结构。分为顺序存储结构和链式存储结构。数据采用不同的存储结构，将对数据运算的具体实现有着巨大的影响.答案：B22.栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列是可能的出栈序列 o(2006.0
43、9)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 Ti nk:=sC)t f.l i n
44、k:=s f.l i nk D)s f.l i nk:=t Ti 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
45、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)若一个树叶是某二叉树对称序的最后一
46、个结点，则它必是该二叉树前序的最后一个结点D)若一个树叶是某二叉树前序的最后一个结点，则它必是该二叉树对称序的最后一个结点解析：若一个树叶是某二又树对称序的最后一个节点，则它必是该二叉树最右边的树叶，即前序的最后一个节点。而若将“树叶”改 为“结点”则不正确，因为有可能出现二叉树最右结点无右孩子的情况。答案：C2 6 .如下所示是一棵5阶B树，该B树现在的层数为2。从该B树中删除关键码3 8后，该B树的第2层的结点数为。(2 0 0 6.0 9)A)6B)7C)8D)9解析：删除38后该节点剩下的关键码的个数为1,小于5/2 1-1=2,所以删除后要将该结点剩余的41与双亲结点中的45一起移至
47、原结点的右兄弟节点，故结点数减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，若文件基本有序，则移动次数减少，最
48、小为0，可见直接插入排序效率最高。答案：A2 8 .下列关于数据结构基本概念的叙述中，哪 一 条 是 正 确 的。（2 0 0 6.0 4）A）数据的逻辑结构分为表结构和树结构B）数据的存储结构分为线性结构和非线性结构C）数据元素是数据的基本单位D）节点是有独立含义的数据最小单位解析：数据的基本单位是数据元素，故C正确。数据的逻辑结构可以划分为集合、线性结构、树型结构和图状结 构（网状结构）。数据的存储结构指的是数据结构在计算机中的表示（映像），它包括顺序存储和链式存储两种结构。节点是由若干位组合起来形成的位串，数据的最小单位是节点中的个二进制数位（b i t）。答案：C2 9 .下列关于串的
49、叙述中，哪 一 条 是 正 确 的。（2 006.04）A）串是由零个或多个字符组成的有限序列B）空串是由空格构成的串C）串只能顺序存储D）“推入”是串的基本运算之一解析：串是由零个或多个字符组成的有限序列：如果串中没有任何字符，则称为空串。由一个或多个空格组成的串称为空格串，空格串不是空串，因为空格串中有字符；串既可以顺序存储也可以链表存储：串的基本操作一般是 以“串的整体”作为操作对象，“推入”不是串的基本运算。答案：A3 0 .双链表的每个结点包括两个指针域。其中r l i n k指向结点的后继，l l i n k指向结点的前驱。如果要在p所指结点前面插入q所指的新结点，下列哪一个 操
50、作 序 列 是 正 确 的。（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