国家电网（计算机类）专业知识备考题库大全（按章节）-数据结构与算法

PAGEPAGE1国家电网（计算机类）专业知识备考题库大全（按章节）-数据结构与算法一、单选题1.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足()。A、所有的结点均无左孩子B、所有的结点均无右孩子C、只有一个叶子结点D、是任意一棵二叉树答案：C解析：先序遍历的次序为根一左一右，而后序遍历的次序为左一右一根先序遍历与后序遍历相对次序可以相反的部分为根一左(对后序的左一根)，或者是根一右(对后序的右一根)，所以满足条件的二叉树只有一个叶子结点。2.设一条单链表的头指针为head且该链表没有头节点，则其判空条件是()。A、head==NULLB、head-＞next==NULLC、head！=NULLD、head-＞next==head答案：A解析：因为单链表没有头节点，所以当头指针为空时证明链表为空。3.某二叉树中序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则前序序列是()。A.E，G，F，A，C，D，BB.E，A，C.A、B、C、FD、以上都不对答案：B解析：由后序序列知E为根节点，再由中序序列知A，B，C，D为E的左子树1，F，G，E为右子树1；由后序序列知A为左子树l的根节点，B，C，D为A的右子树2。依次类推可得到该数，其前序序列也可自然而然的得到。4.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是()A、EB、FC、GD、H答案：C解析：5.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为()A、3，2，5，8，6B、2，3，5，8，6C、3，2，5，6，8D、2，3，6，5，8答案：C解析：快速排序的每趟排序在待排序列中选取一个数为基准，将序列划分为两段，一段的值比基准值小，另一段大于或等于基准值。6.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是()。A、冒泡排序B、堆排序C、快速排序D、希尔排序答案：D解析：冒泡排序每趟选出一个最值移至序列的一端。快速排序的一趟排序可以使选出的基准值移至最终位置。7.二叉树的第k层的结点数最多为()。A、2K-1B、2K+1C、2KD、2答案：A解析：二叉树第k层最多有2k-1个结点。8.下列关于AOE网的叙述中，不正确的是()。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成。那么整个工程将会提前完成C、所有的关键活动提前完成，那么整个工程将会提前完成D、某些关键活动提前完成，那么整个工程将会提前完成答案：B解析：关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完咸。9.若对序列(tang，deng，an，wang，shi，bai，fang，liu)采用选择排序法按字典顺序进行排序，下面给出的四个序列中，()是第三趟的结果。A、an.bai，deng，wang，tang，fang，shi，huB、an，bai，deng，wang，shi，tang，fang，liuC、an.bai，deng，wang，shi，fang，tang，liuD、an.bai，deng，wang，shi，liu，tang，fang答案：B解析：选择排序是指每一趟从待排序的数据元素中选出最小(或最大)的一个元素，顺序地放在已排好序的数列的最后，直到待排序数据元素全部排完。按字典顺序排序的排序过程如下:第一趟:an,deng,tang,wang，shi,bai,fang,liu;.第二趟，an,bai,tang,wang，shi，deng,fang,liu;第三趟:an,bai，deng,wang，shi,tang,fang,liup第四趟:an,bai,deng,fang，shi,tang,wang,liu;第五趟，an,bai，deng,fang，liu,tang,wang，shi;第六趟:an,bai,deng,fang,liu,slu,wang,tang;第七趟:an.bai,deng,fang,liu,shi,tang,中ang。10.A、AB、BC、CD、D答案：A解析：11.用直接选择排序方法分别对序列S1=(1，2，3，4，5，6，7)和序列S2=(7，5，3，2，4，1，6)进行排序，关键字比较次数()。A、相同B、前者大于后者C、前者小于后者D、无法比较答案：A解析：直接选择排序的比较次数与序列的初始状态无关，因此，对于给定两个序列进行排序的关键字比较次数是相同的。12.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H(key)=keyMOD13，散列地址为1的链中有()个记录。A、1B、2C、3D、4答案：D解析：由散列函数H(key)=keyMOD13计算每个记录的散列地址，散列地址为1的关键字有14，1，27，79，共4个记录。13.以下属于逻辑结构的是()。A、顺序表B、哈希表C、有序表D、单链表答案：C解析：数据结构分别为逻辑结构、存储结构(物理结构)和数据的运算。数据的逻辑结构是对数据之间关系的描述，与数据元素本身的形式、内容、相对位置、所含结点个数都无关。顺序表、哈希表、单链表都涉及到数据的存储结构，有序表是指表中数据有序，与逻辑结构无关。14.A[N，N]是对称矩阵，将下三角(包括对角线)以行序存储到一维数组T[N(N+l)/2]q中，则对任一上三角元素A[i][j]对应T[k]的下标k是()。A、i(1-1)/2+jB、j(j-1)/2+iC、i(j-i)/2+1D、j(1-1)/2+1答案：B解析：将对称矩阵A[N，N]下三角以行序存储到一维数组T[N(N+1)/2]中。对应的A[i][j]啪与T[k]的下标k的关系为k=i(i-1)/2+j；但题目中是求任一上三角元素A[i][j]对应T[k]的下标k，在对称矩阵中A[i][D]=A[i][i]，即上三角中的元素的A[i][j]存储位置对应下三角A[i][j]的存储位置，所以k=j(j-1)/2+i。15.如果节点A有3个兄弟，B是A的双亲，则节点B的度是()。A、3B、4C、1D、2答案：B解析：节点A有3个兄弟，B是A的双亲，则节点B的度是4。16.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A、AB、BC、CD、D答案：B解析：Prim算法的时间复杂度：当图采用邻接矩阵存储时，时间复杂度为0(r12)，采用邻接表存储时，时间复杂度为O(n+e)。17.已知有向图G=(V，A)，其中V={a，b，C，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，对该图进行拓扑排序，下面序列中()不是拓扑排序A、a，d，c，b，eB、d，a，b，c，eC、a，b，d，c，eD、a，b，c，d，e答案：D解析：18.无向图的邻接矩阵是一个()。A、对称矩阵B、无规律C、上三角矩阵D、下三角矩阵答案：A解析：两个顶点邻接是相互的，1和2邻接，2和1也就邻接了。19.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1.n]中，则二叉树中第i个结点(i从1开始用上述方法编号)的右孩子在数组A中的位置是()。A、A[2i](2i＜=n)B、A[2i+1](2i+1＜=n)C、A[i-2]D、条件不充分，无法确定答案：D解析：本题目并未明确所给二叉树的形状，因此不能根据第i个结点在数组A中的存储位置确定其右孩子在数组A中的位置。20.在二叉排序树中插入一个关键字值的平均时间复杂度为()。A、AB、BC、CD、D答案：B解析：在二叉排序树中插入节点的时间复杂度等于查找失败的时间复杂度，即在查找失败的位置插入节点，时间复杂度为0(1og2n)。21.有n个记录的文件，若关键字位数为d，基数为r，则基数排序共需进行()遍分配与收集。A、nB、rC、dD、d+r答案：C解析：22.栈在()中应用。A.递归调用B.子程序调用A、表达式求值B、C、D、C答案：D解析：栈的特点是先入后出。A项，递归调用的特点是最外层的调用最后执行，最内层的调用最先执行，递归调用符合栈的特点，即先将外层的调用依次入栈，然后从最内层调用出栈执行；B项，子程序的调用与递归调用的特点类似；C项，表达式求值将数据入栈，遇到运算符时与栈顶的运算符比较优先级，级别高则数据出栈，进行运算。23.下列排序算法中，在待排序数据已有序时，花费时间反而最多的排序是()。A、冒泡B、希尔C、快速D、堆答案：C解析：在待排序数据已有序时，快速排序会退化为冒泡排序，时间复杂度为O(n)。24.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是()。A、栈B、线性表C、队列D、二叉排序树答案：A解析：栈(stack)又称为堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素称作出栈或退栈，它是把栈顶元素删除，使其相邻的元素成为新的栈顶元素。25.()在其最好情况下的算法时间复杂度为O(n)。A、插入排序B、归并排序C、快速排序D、堆排序答案：A解析：26.下面()不属于特殊矩阵。A、对角矩阵B、三角矩阵C、稀疏矩阵D、对称矩阵答案：C解析：稀疏矩阵不属于特殊矩阵。27.某高度为k的完全二叉树中，所含叶子结点的个数最少为()。A、AB、BC、CD、D答案：C解析：28.设单循环链表中结点的结构为(data，link)，且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作()。A、s=rear；rear=rear-＞link；deletes；B、rear=rear-＞link；deleterear；C、rear=rear-＞link-＞link；deleterear；D、s=rear-＞link-＞link；rear-＞link-＞link=s-＞link；deletes；s为第一个结点硫答案：D解析：若要删除结点需要改变尾指针的指向。29.A、{(1，4)，(2，3)，(2，5)}B、{(3，5)，(3，4)，(4，5)}C、{(1，3)，(3，4)，(3，5)}D、{(2，3)，(3，4)，(2，5)}答案：A解析：30.对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为()。A、h或h+1B、任意C、hD、h+1答案：A解析：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为1或1+1满二叉树：一棵深度为k.且有2的(k)次方－1个节点的二叉树特点：每一层上的结点数都是最大结点数。31.已知一个线性表为(38，25，74，63，52，48)，假定采用H(K)=Kmod7计算散列地址进行散列存储，若利用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为()；若利用链地址法处理冲突，则在该散列上进行查找的平均查找长度为()。A、1.5，1B、1.7，3/2C、2，4/3D、2.3，7/6答案：C解析：若用开放定址法处理冲突，发生0次冲突的关键字有3个，1次冲突的1个，2次冲突的1个，3次冲突的1个，因而在该散列表上进行查找的平均查找长度为ASL-(3*1+1*2+1*3+1*4)/6=2；若用链地址法处理冲突，同一链表上有1个元素的线性链表有2个，有2个元素的线性链表有2个，因此ASL=(4*1+2*2)/6=4/3。32.若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方式最节省时间的是()。A、单链表B、双链表C、单循环链表D、顺序表答案：D解析：在顺序表中查找第i个元素的前驱很方便。双链表虽然能快速查找第i个元素的前驱，但不能实现随机存取。单链表和单循环链表既不能实现随机存取，查找第i个元素的前驱也不方便。33.下列说法不正确的是()。A、图的遍历是从给定的源点出发每一个顶点仅被访问一次B、遍历的基本算法有两种：深度遍历和广度遍历C、图的深度遍历不适用于有向图D、图的深度遍历是一个递归过程答案：C解析：图的遍历是指从给定图中任意指定的顶点出发，按照某种搜索方法沿着图的边访问图中的所有顶点，便每个丁贞点仅被访问一次。遍历的基本算法有两种：深度遍历和厂度遍历。图的深度遍历是一个递归过程，既适用于无向图，也适用于有向图。34.设有向无环图G中的有向边集合E={＜1，2＞，＜2，3＞，＜3，4＞，＜1，4＞}，则下列属于该有向图G的一种拓扑排序序列的是()。A、1，2，3，4B、2，3，4，1C、1，2，4，3D、1，4，2，3答案：A解析：35.以下排序方法中，在初始序列已基本有序的情况下，排序效率最高的是()。A、归并排序B、直接插入排序C、快速排序D、堆排序答案：B解析：直接插入排序对于基本有序的序列进行排序效率最高。36.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为()。A、p-＞next=s；s-＞next=q；B、q-＞next=s；s-＞next=p；C、p-＞next=s-＞next；s-＞next=p；D、s-＞next=p-＞next；p-＞next=-s；答案：B解析：插入s结点，应使s的next指针指向p结点，使q结点的next指针指向s。37.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有()个结点。A、13B、12C、26D、25答案：D解析：哈夫曼树的特点：具有n个叶子结点的哈夫曼树共有2×n-1个结点。38.设一组初始记录关键字的长度为8，则最多经过()趟插入排序可以得到有序序列。A、8B、7C、9D、6答案：B解析：插入排序的每一趟在待排元素中取出第一个元素，移至有序序列的适当的位置，所以共八个关键字的序列，最多经过7趟插入排序就可以得到一个有序序列。39.已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()。A、-A+B*C/DEB、-A+B*CD/EC、-+*ABC/DED、-+A*BC/DE答案：D解析：将算术表达式的前缀形式、中缀形式和后缀形式分别看成二叉树的前序遍历、中序遍历和后序遍历，本题可转化成已知二叉树的中序遍历和后序遍历序列，如何求出其前序遍历序列。前序遍历的顺序是根结点，左子树，右子树；中序遍历的顺序是左子树，根结点，右子树；后序遍历的顺序是左子树，右子树，根结点；因此后序遍历中最后访问的结点是根结点，该结点将中序遍历分成两个子序列，分别为其左右子树的中序序列，之后递归应用这个过程，构造出一个二叉树，前序遍历该序列，即可得到表达式的前缀形式。40.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的()倍：A、1/2B、2C、1D、4答案：C解析：在有向图中每个顶点的入度就是另外一个顶点的出度，因此所有顶点的入度之和等于所有顶点出度之和，等于有向图中所有的边数。41.设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。A、10，15，14，18，20，36，40，21B、15，10，14，18，20，36，40，21C、10，15，14，20，18，40，36，21D、10，15，14，18，20，40，36，21答案：A解析：快速排序的每趟排序在待排序列中选取一个数为基准，将序列划分为两段，一段的值比基准值小，另一段大于或等于基准值。在快速排序中通常有两个指针分别为i和j，j从后向前遍历，找第一个小于基准值的节点，将值交换，i从前向后遍历，找到第一个大于或等于基准值的节点，将值交换，重复此过程，直至i和j指向同一节点，一趟排序结束。42.A、AB、BC、CD、D答案：A解析：由森林转换为二叉树，利用的是树转为二叉树时，二叉树的右子树始终为空的特点，所以，从第二棵树开始，每棵树都成为了B的右子树，即B的左子树的结点个数为N1-1个。43.若对27个元素只进行三趟多路归并排序，则选取的归并路数为()。A、2B、3C、4D、5答案：B解析：44.下列各种排序算法中平均时间复杂度为O(n)是()。A、快速排序B、堆排序C、归并排序D、冒泡排序答案：D解析：45.在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是()。A、希尔排序B、起泡排序C、插入排序D、选择排序答案：D解析：每一趟从待排序的数据元素中选出最小(或最大)的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。46.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为()。A、第i列0元素的个数之和B、第i列非0元素的个数之和C、第i行0元素的个数之和D、第i行非0元素的个数之和答案：B解析：考察图的邻接矩阵的特点，在有向图的邻接矩阵中，第i列非0元素的个数之和即为第i个节点的入度。47.求解Hanoi问题时，若初始有5个圆盘，则移动圆盘的次数是()。A、7B、15C、31D、5答案：C解析：48.在一个双链表中，删除P结点之后的一个结点的操作是()。A、AB、BC、CD、D答案：C解析：考查双链表中插入操作，要注意保存后继节点。49.A、4B、5C、6D、7答案：C解析：右节点均为原来森林的树。将T2还原为森林T1，其中有6棵树：C、D、F、G，I和J是叶子结点。50.一棵m阶非空B-树，每个结点最多有()棵子树。A、m/2B、m-1C、mD、m+1答案：C解析：B-树中每个结点之多有m棵子树，m就是B-树的阶。51.二维数组A的每个元素是由6个字符组成的串，行下标的范围从0～8，列下标的范围是从0～9，则存放A至少需要()个字节。A、240B、540C、90D、180答案：B解析：数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元。52.下列排序方法中，属于不稳定的排序方法的是()。A、直接插入排序法B、冒泡排序法C、基数排序法D、堆排序法答案：D解析：本题选项所述的四种排序方法中，只有堆排序是不稳定的。53.对于栈操作数据的原则是()。A、先进先出B、后进先出C、后进后出D、不分顺序答案：B解析：栈的特点就是后进先出，入栈和出栈的操作只能在栈顸进行.而队列的特点是先进先出，这两点容易混淆，要注意区分。54.下面关于图的遍历说法不正确的是()。A、遍历图的过程实质上是对每个顶点查找其邻接点的过程B、深度优先搜索和广度优先搜索对无向图和有向图都适用C、深度优先搜索和广度优先搜索对顶点访问的顺序不同，它们的时间复杂度也不相同D、深度优先搜索是一个递归的过程，广度优先搜索的过程中需附设队列答案：C解析：深度优先搜索和广度优先搜索的时间算杂度相同，均为O(n+e)。55.若用冒泡排序方法对序列{10、14、26、29、41、52}从大到小排序，需要进行几次比较()。A、3B、10C、15D、25答案：C解析：冒泡排序法比较排序的时候，第一个10要进行5次比较，第二个要进行4次比较，依次类推，3次，2次，1次，总共是15次比较。56.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是()。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孙答案：C解析：中序遍历时，先访问左子树，再访问根结点。n在m前，则n必须在m的左子树中。57.对于一个长度为n的任惫表进行排序，至少需要进行的比较次数是()。A、AB、BC、CD、D答案：D解析：58.设结点x和y是二叉树中任意的两个结点，在该二叉树的前序遍历序列中x在y之前，而在其后序遍历序列中x在y之后，则x和y的关系是()。A、x是y的左兄弟B、x是y的右兄弟C、x是y的祖先D、x是y的后裔答案：C解析：前序遍历序列中x在y之前，有两种情况，即x是y的祖先，或者x、y有某个共同祖先，并且x在其左子树中，y在其右子树中。而第二种情况在后序遍历序列中，x必定在y之前，所以只能是x是y的祖先。59.下列命题正确的是()。A、一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一B、一个图的邻接矩阵表示是唯一的，邻接表表示也唯一C、一个图的邻接矩阵表示是唯一的，邻接表表示不唯一D、一个图的邻接矩阵表示不唯一的，邻接表表示是唯一答案：C解析：一个图的邻接矩阵表示是唯一的，邻接表表示不唯一。60.以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。A、front=front+1B、front=(front+1)%mC、front=(front+1)%(m+1)D、rear=(rear+1)%m答案：C解析：循环队列的出队操作是：front=(front+1)%(m+l)。61.()的邻接矩阵是对称矩阵。A、有向图B、无向图C、AOV网D、AOF网答案：B向图的邻接矩阵一定是一个对称矩阵。62.下面给出的四种排序方法中，辅助空间为O(n)的是()。A、希尔选择B、冒泡排序C、归并排序D、堆排序答案：C解析：希尔选择、冒泡排序、堆排序的辅助空间都为0(1)；而归并排序中，由于每一趟都要一个TR数组来复制，因此需要与待排记录等量的辅助空间O(n)。63.对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为()。A、n/2B、(n+1)/2C、(n-1)/2D、n/4答案：B解析：所有元素的搜索长度之和为1+2+…+n=n(n+1)/2。搜索每个元素的概率都是1/n，所以平均搜索长度为：n(n+1)，2×(1/n)=(n+1)/2。64.算法指的是()。A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列答案：D解析：算法是精确定义的一系列规则，它指出怎样从给定的输入信息经过有限步骤产生所求的输出信息。它既不是计算机程序，也不是某种算术运算。65.下列与数据元素有关的叙述中，哪一项是不正确的()。A、数据元素是数据的基本单位，即数据集合中的个体B、数据元素是由独立含义的数据最小单位C、数据元素又称为节点D、数据元素又称为记录答案：B解析：数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为节点、记录、表目等。一个数据元素可由一个或多个数据项组成，数据项是由独立含义的数据最小单位。66.线索化的二叉树中，某结点*P没有孩子的充要条件是()。A、p-＞lchild=NULLB、p-＞ltag=l&&p-＞rtag=1C、p-＞ltag=0D、p-＞lchild=NULL&&p-＞ltag=1答案：B解析：考查线索二叉树。67.一个队列的入队顺序是a，b，c，d，则出队顺序是()。A.a，b，C，dB.b，C，d，aA、d，B、b，aC、D、d，a，b答案：A解析：队列的特点是先进先出，因此出队的序列于入队的序列完全相同，这点与栈不同。68.设有序表中有1000个元素，则用二分查找元素X最多需要比较()次。A、15B、10C、17D、25答案：B解析：二分查找每趟都使用序列的中间值与关键字比较，直至查找成功或失败。69.若一个栈的输入序列为1，2，3…，n，输出序列的第一个元素是i，则第j个输出元素是()。A、i-j-1B、i-jC、j-i+lD、不确定答案：D解析：栈是一种后进先出的线性表结构，但本题无法确定输入和输出的时间顺序，即不一定是在所有元素输入栈后再进行输出。70.设有关键字序列F={Q，G，M，Z，A，N，P，X，H}，下面()序列是从上述序列出发建堆的结果。A.A，G，H，M，N，P，Q，X，ZB.A，G，M，H，Q，N，P，X，ZC.G，M，Q，A，N，P，X，A、ZB、C、0，M，P，D、N，Q.X.Z答案：B解析：本题考查堆建立算法。71.一个循环队列Q最多可存储m个元素，已知其头尾指针分别是front和rear，则判定该循环队列为满的条件是()。A、Q.rear-Q.front==mB、Q.real！==Q.frontC、Q.front==(Q.real+1)%mD、Q.front==Q.rear%m+1答案：C解析：少用一个元素空间和空队区别开：每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满，这种情况下队满的条件是：(Q.rear+1)%MAXSIZE==Q.front。72.由圈权值为9.2.5.7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为()。A、23B、37C、44D、46答案：C解析：73.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有()条有向边。A、n-1B、nC、m-1D、m答案：B解析：邻接表的表头结点个数即为图中结点的个数。74.下面的说法中，不正确的是()。A、对角矩阵只需存放非零元素即可B、稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储C、稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储D、对称矩阵只需存放包括主对角线元素在内的下(或上)三角的元素即可答案：C解析：稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。75.以下数据结构中，属于非线性数据结构的是()，A、树B、队列C、栈D、字符串答案：A解析：线性结构是一个数据元素的有序(次序)集合。它有四个基本特征：(1)集合中必存在唯一的一个“第一个元素”；(2)集合中必存在唯一的一个“最后的元素”；(3)除最后元素之外，其它数据元素均有唯一的“后继”；(4)除第一元素之外，其它数据元素均有唯一的“前扑”。数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。线性结构包括线性表(如结构体数组，结构体链表)、一维数组、字符串、堆栈、队列。76.在单链表指针为P的结点之后插入指针为s的结点，正确的操作是()。A、AB、BC、CD、D答案：B解析：在单链表结点P后插入结点s，要先改变s结点的指针域，指向p的后继结点。然后将s的地址赋给P的指针域。具体的操作语句为s—＞next=P—＞next；p—＞next=s。77.用链接方式存储的队列，在进行删除运算时()。A、仅修改头指针B、仅修改尾指针C、头、尾指针都要修改D、头、尾指针可能都要修改答案：D解析：链接方式存储队列的删除运算仍要保持链式队列结构。当队列中仅包含一个元素结点时，头尾指针均指向该结点，删除该结点后头尾指针均要修改；当队列中有多个结点时，队列的删除运算仅针对头结点，修改头指针即可。78.()不是算法的基本特性。A、可行性B、长度有限C、在规定的时间内完成D、确定性答案：B解析：算法的5个重要特性：①确定性；②有穷性；③可行性；④输入；⑤输出。C项指的是有穷性，而有穷性并不是指长度有限，而是指执行的时间是有限的。79.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则下面最合适的存储方式是()。A、单链表B、循环双链表C、单循环链表D、带有尾指针的单循环链表答案：B解析：在链表中的最后一个结点之后插入个结点要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点要知道终端结点的前驱结点的地址，所以，带有尾指针的单循环链表不合适，而循环双链表满足条件。80.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为()。A、37/12B、35/12C、39/12D、43/12答案：A解析：用二分法查找有序表，相当于在一个完全二叉树中查找元素，查找成功的比较次数相当于到查找结点的路径长度加1。12个结点的完全二叉树前三层是满二叉树，第四层有5个结点。整棵树的查找次数总和为：1+22+4×3+5×4=37。查找某个元素的概率是37/12。81.以下各种存储结构中，最适合用作链队的链表是()。A、带队首指针和队尾指针的循环单链表B、带队首指针和队尾指针的非循环单链表C、只带队首指针的非循环单链表D、只带队首指针的循环单链表答案：B解析：因为队列的入队和出队操作都在端点进行。即在队首和队尾进行。所以带队首指针和队尾指针的非循环单链表最适合用作链队的链表。82.将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][64]在B数组中的位置等于()。A、198B、197C、196D、195答案：D解析：将三对角矩阵a[i][j]存入b[k]中，矩阵压缩地址计算公式为k=2i十j。所以a[65][64]对应的k=2×65+64=194，194是一维数组b的下标，而数组下标是从0开始计数的.所以元素的位置应该是195。83.采用邻接表存储的图的广度优先遍历算法类似于树的()。A、中根遍历B、先根遍历C、后根遍历D、按层次遍历答案：D解析：图的广度优先遍历算法思想是，对于某个结点，首先遍历该结点，而后遍历其相邻的所有结点，而树的层次遍历中，对于某个结点，首先遍历该结点，然后遍历其所有的子结点。84.采用开放定址法处理散列表的冲突时，其平均查找长度()。A、与链接法处理冲突相同B、高于二分查找C、低于链接法处理冲突D、高于链接法处理冲突答案：D解析：开放定址法处理冲突的平均查找长度高于链接法。85.如果结点A有3个兄弟，B是A的双亲，则结点B的度是()A、3B、4C、1D、2答案：B解析：结点A有3个兄弟，B是A的双亲，则结点B的度是4。86.以下说法正确的是()。A、数据结构的逻辑结构是指数据的各数据项之间的逻辑关系。B、数据元素是数据结构的最小单位。C、数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。D、判断某个算法是否容易阅读是算法分析的任务之一。答案：C解析：A项，数据结构的逻辑结构是指数据的各数据元素之间的逻辑关系，而不是数据项之间的逻辑关系。B项，数据元素是数据结构的基本单位，数据结构的最小单位是数据项。D项，算法分析是一个软件的验证确认任务，用于保证选择的算法是正确的、合适的和稳定的，并且满足所有精确性、规模和时间方面的要求，保证产品高质量高效率的运行。容易阅读是增加算法的可读性，不是算法分析的任务。87.A、AB、BC、CD、D答案：B解析：88.用P代表入栈，O代表出栈。栈的初始状态和最终状态都为空，则下列栈操作正确的是()。A、POOPOOPPB、POPOPOOPC、PPPOOOPPD、PPPOOPOO答案：D解析：AB两项，均会出现下溢，即出栈时栈为空。C项，导致出现最终状态不为空。89.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是()。A、1B、2C、3D、4答案：C解析：出队的顺序也是出栈的顺序，由此顺序可以推出栈的容量最小值。90.在顺序表(3，6，8，10，12，15，16，18，21，25，30)中，用二分法查找关键值11，所需的关键码比较次数为()。A、2B、3C、4D、5答案：C解析：用二分法查找关键值11比较的元素依次是15，12，10，8，共比较4次。91.A、AB、BC、CD、D答案：D解析：92.若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。A、BCAGFEDB、DAEBCFGC、ABCDEFGD、BCAEFGD答案：B解析：由前序序列和中序序列先构造出二叉树，然后按层次序列进行访问。93.执行一趟快速排序能够得到的序列是()。A、[41，12，34，45，27]55[72，63]B、[12，27，45，41]55[34，63，72]C、[63，12，34，45，27]55[41，72]D、[45，34，12，41]55[72，63，27]答案：A解析：一趟快速排序的结果为基准值的左边节点的值全部小于基准值，基准右边的节点的值全部不小于基准值。94.对任意7个关键字进行排序，至少要进行()次关键字之间的两两比较。A、13B、14C、15D、16答案：C解析：95.A、AB、BC、CD、D答案：C解析：96.将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为()。A、O(n)B、0(1)C、O(m)D、O(m+n)答案：C解析：要将长度为n的单链表接在长度为m的单链表之后，必须从单链表的头结点沿链找到长度为m的单链表的最后一个结点，所以时间复杂度为O(m)。97.栈和队列的共同点是()。A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点答案：C解析：栈和队列都是运算受限的线性表，只允许在表端点处进行操作。98.如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用的查找法是()。A、分块查找B、顺序查找C、折半查找D、基于属性答案：A解析：分块查找又称索引顺序查找，是一种性能介于顺序查找和二分查找之间的查找方法。其基本思想是：(1)首先查找索引表：索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。(2)然后在已确定的块中进行顺序查找：由于块内无序，只能用顺序查找。分块查找既能较快的查找，又能适应动态变化的要求。99.设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作()。A、求子串B、判断是否相等C、模式匹配D、连接答案：C解析：A项，求子串操作是从字符串S中截取第i个字符开始后的长度1的子串。BD明显不对。100.A、3B、6C、9D、以上答案均不正确答案：A解析：邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n个顶点的图，顶点序号依次为1，2，……，n，则G的邻接矩阵是n阶方阵，所以该图有3个顶点。101.如果以链表作为栈的存储结构，则退链栈操作时()A、必须判断链栈是否满B、判断链栈元素的类型C、必须判断链栈是否空D、对链栈不做任何判断答案：C解析：在链表的退链栈操作时，如果栈已空.就没有元素可供退栈，返回退栈失败信息，所以必须判断链栈是否空。102.用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为()。A、AB、BC、CD、D答案：D解析：103.建立一个长度为n的有序单链表的时间复杂度为()A、AB、BC、CD、D答案：C解析：建立有序单链表的时间复杂度是O(n)，对单链表插入节点时，先遍历单链表，找到插入位置，将节点插入。104.A、(1)B、(1)、(2)C、(1)、(4)D、(3)答案：C解析：(1)项，原地工作不是不需要额外空间，而是额外空间相对于问题的规模(输入数据量)来说是个常数，那么我们就称之为原地工作。(4)项，这个结论不是绝对的，要看具体情况而定，一般情况下是这样的。105.在由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为()。A、20B、29C、30D、35答案：B解析：当把森林转换成二叉树后，第二、第三和第四棵树均在第一棵树的根结点的右子树上。106.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。A、数据的处理方法B、数据元素的类型C、数据元素之间的关系D、数据的存储方法答案：C解析：在存储数据时，需要存储数据元素的值和数据元素之间的关系。107.已知串S=′aaab′，其next数组值为()。A、0123B、0213C、0231D、1211答案：A解析：108.若用单链表来表示队列，则应该选用()。A、带尾指针的非循环链表B、带尾指针的循环链表C、带头指针的非循环链表D、带头指针的循环链表答案：B解析：假设尾指针为TAIL，则通过TAIL可访问队尾，通过TAIL—＞next可访问队头。109.设链式栈中节点的结构为(data，link)，且top是指向栈顶的指针。若想摘除链式栈的栈顶节点，并将被摘除节点的值保存到x中，则应执行下列()操作。A、x=top-＞data；top=top-＞link；B、top=top-＞link；x=top-＞data；C、x=top；top=top-＞link；D、x=top-＞data；答案：A解析：若想摘除链式栈的栈顶节点，并将被摘除节点的值保存到x中，则应执行x=top-＞data；top=top-＞link.110.下列序列中，满足堆定义的是()。A、(100，86，48，73，35，39，42，57，66，21)B、(12，70，33，65，24，56，48，92，86，33)C、(103，97，56，38，66，23，42，12，30，52，6，26)D、(5，56，20，23，40，38，29，61，36，76，28，100)答案：A解析：n个元素的序列{K1，K2，…，Kn}当且仅当满足下面关系：Ki＜=K2i和Ki＜=K(2i+1)或者Ki＞=K2i和Ki＞K(2i+1)时，称之为堆。B项，其构成的是小顶堆，70和24之间不满足小顶堆性质；C项，其构成的是大顶堆，23和26不满足大顶堆性质；D项，其构成的是小顶堆，56和23，40和28不满足小顶堆性质。A项对应的是大顶堆，满足大顶堆性质。111.将数组称为随机存取结构是因为()。A、数组的存储结构是不定的B、数组元素是随机的C、对数组任一元素的存取时间是相等的D、随时可以对数组进行访问答案：C解析：将数组称为随机存取结构是因为对数组任一元素的存取时间是相等的。112.设顺序表的长度为n，则顺序查找的平均比较次数为()。A、(n-1)/2nB、n/2C、(n+1)/2D、n答案：C解析：顺序查找是顺序遍历查找表，直至找到或查找失败，所以最好的情况是第一个节点即想找的元素，最坏的情况是查找失败，所以平均查找次数为(n+1)/2。113.若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79答案：C解析：由于选择第一个记录为基准，第一次排序即对整个序列进行一趟快速排序。使得位于基准左侧的关键码均小于基准，位于基准右侧的关键码均大于基准。114.二叉排序树中左子树上所有结点的值均()根结点的值。A、＜B、=C、＞D、！=答案：A解析：二叉排序树的左子树的结点的值全部小于根结点的值，并且根结点的值小于右子树左右结点的值。115.在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。A、一定都是同义词B、一定都不是同义词C、不一定都是同义词D、都相同答案：C解析：采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。116.设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择()。A、小于等于m的最大偶数B、小于等于m的最大合数C、小于等于m的最大奇数D、小于等于m的最大素数答案：D解析：p最好选择小于等于m的最大素数。117.如果一棵二叉树结点的先根遍历序列是A、B、C，后根遍历序列是C、B、A，则该二叉树结点的中根遍历序列()。A.必为A、B、CB.必为A、C、BA、必为B、C、AD、不能确定答案：D解析：118.A、6B、4C、3D、2答案：C解析：119.若用一个大小为6的一维数组来实现循环队列，且当前front和rear的值分别为3，0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为()。A、5，1B、4，2C、2，4D、1，5答案：B解析：删除front=(front+1)mod6，加入：rear=(rear+1)mod6。120.使用双链表存储线性表，其优点是()。Ⅰ.提高查找速度Ⅱ.更方便数据的插入和删除Ⅲ，节约存储空间Ⅳ.很快回收存储空间A、Ⅰ、ⅡB、Ⅰ、ⅣC、仅ⅡD、Ⅱ、Ⅲ、Ⅳ答案：C解析：在链表中一般只能进行顺序查找，所以双链表并不能提高查找速度，因为双链表中有两个指针域，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，其插入和删除操作更加方便。121.一棵完全二叉树上有1001个结点.其中叶子结点的个数是()。A、250B、500C、505D、501答案：D解析：122.分别以下列序列构造=叉排序树，与用其他三个序列所构造的结果不同的是()。A、(100，80，90，60，120，110，130)B、(100，120，110，130，80，60，90)C、(100，60，80，90，120，110，130)D、(100，80，60，90，120，130，110)答案：C解析：二叉排序树的特点：左子树的结点小于根结点，右子树的结点大于根结点。由其特点得C得到的结果与其他三个序列构造的结果不同。123.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为()。A、aedfcbB、aedfbcC、aebcfdD、acfebd答案：A解析：124.快速排序最易发挥其长处的情况是()。A、被排序的数据中含有多个相同排序码B、被排序的数据已基本有序C、被排序的数据完全无序D、被排序的数据中的最大值和最小值相差悬殊答案：C解析：125.假设以S和X分别表示进栈和出栈操作，则对输入序列a，B，c，d，E进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为()。A.B，c，E，d，aB.B，E，c，a，dC.E，c，A、d，aB、c，C、D、a，d答案：A解析：a，B进栈(SS)，B出栈(X)，输出“B”，c进栈(S)，c出栈(X)，输出“c”，d，E进栈(SS)，E，d，a出栈(XXX)，输出“E，d，a”，所以结果为B，c，E，d，a。126.在有n个结点的二叉链表中，值为非空的链域的个数为()。A、n-1B、2n-1C、n+1D、2n+1答案：A解析：本题考查的是二叉树的链式存储。由于在有n个结点的二叉链表中，值为空的链域的个数为n+1个，而总的链域为2n(在二叉树中每个结点头2个链域)。所以，非空的链域的个数为2n-(n+1)=n-1。127.循环队列qu的队空条件是()。A、(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB、(qu.rear+1)%MaxSize-=qu.front+1C、(qu.rear+1)%MaxSize==qu.frontD、qu.rear==qu.front答案：D解析：循环队列为空，当且仅当队尾指针等于队尾指针.具体的操作语句为qu.rear==qu.front。128.设有n个元素进栈序列是P1，P2，P3，…，Pn，其输出序列是1，2，3，…，n，若P3=3，则P1的值()。A、可能是2B、一定是2C、不可能是1D、一定是1答案：A解析：进栈序列是P1，P2，P3，…，Pn，当P3=3时，由输出序列可知，只有以下两种情况：P1进栈后出栈，P2进栈后出栈，或P1、P2都进栈然后出栈，因此P1的值可能为1，也可能为2。129.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中，第一棵树的结点个数是()。A、m-nB、m-n-1C、n+1D、条件不足，无法确定答案：A解析：森林转换成二叉树的原则：将第一棵树的根结点作为根结点，所有结点的第一个左孩子作为左孩子，下一个兄弟结点作为右孩子，其它树作为第一棵树的右孩子。所以森林F中第一棵树的结点个数是m-n。130.A、AB、BC、CD、D答案：C解析：131.前序遍历和中序遍历结果相同的二叉树是()。A、所有节点只有左子树的二叉树B、所有节点只有右子树的二叉树C、根节点无左孩子的二叉树D、根节点无右孩子的二叉树答案：B解析：前序遍历是首先访问根节点，然后前序遍历左子树，最后前序遍历右子树。中序遍历是首先中序遍历左子树，然后访问根节点，最后中序遍历右子树。当所有节点都没有左子树时，前序遍历和中序遍历的遍历结果相同。132.算法分析的目的是()。A、找出数据结构的合理性B、研究算法中输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档性答案：C解析：算法分析的目的是分析算法的效率以求改进。133.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为()。A、AB、BC、CD、D答案：B论是顺序存储还是链式存储，使用顺序查找法的时间复杂度相同。134.栈S最多只能容纳4个元素，现在6个元素按A，B，C，D，E，F的顺序进栈，下列哪一个序列是可能的出栈序列()。A、EDCBAFB、BCEFADC、CBEDAFD、ADFEBC答案：C解析：一次进栈最多4个，即ABCD同时在栈中，则EDCBAF不可能，A项中，E和F还没有进栈就已经出栈；B项中，D元素不可能出栈在A的后面；D项中，最后两个元素出栈顺序也有误。135.已知10个数据元素为(54，28，16，34，73，62，95，60，23，43)，按照依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需比较的次数为()。A、2B、3C、4D、5答案：B解析：将这10个元素按照依次插入结点的方法生成一棵二叉排序树后，62位于这棵二叉排序树的第三层，查找值为62的结点所需要的次数恰好是从二叉排序树的根到被查结点的树的深度。136.二叉排序树中，最小值结点的()。A、左、右指针均为空B、左、右指针均不为空C、左指针一定为空D、右指针一定为空答案：C解析：在二叉排序树中，值最小的结点一定是中序遍历序列中第一个被访问的结点，即二叉树的最左下结点。137.在一个顺序表的表尾插入一个元素的时间复杂性的量级为()。A、AB、BC、CD、D答案：C解析：在一个顺序表的表尾插入一个元素移动次数为1次。138.以数组Q[0…m-1]存放循环队列中的元素，若变量front和qulen分别指示循环队列中队头元素的实际位置和当前队列的长度，则队尾元素的实际位置是()。A、front+qulen-1B、(front+qulen)modmC、(front+qulen-1)modmD、front+qulen答案：C解析：循环队列的元素顺序存储在数组Q中，已知循环队列中队头元素的存储位置为front。当前队列的长度为qulen，队尾元素的位置要在front上加上qulen，然后减l(第一个元素存储在front的位置上)，对于循环队列求队尾的位置还要对总长度求余，所以队尾元素的实际位置为(front+qulen-1)modm。139.设一个顺序有序表A[1：14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。A、A[7]，A[5]，A[3]，A[4]B、A[1]，A[14]，A[7]，A[4]C、A[7]，A[3]，A[5]，A[4]D、A[1]，A[2]，A[3]，A[4]答案：C解析：二分查找法的每次比较都与中间值进行比较，第一次与位置7的元素比较，依次类推。140.在二叉排序树中插入一个结点的时间复杂度为()。A、AB、BC、CD、D答案：B解析：在二叉排序树中进行插入时最坏情况下时间复杂度是O(n)。141.非空的循环单链表FIRST的尾结点(由P所指向)满足：()。A、P—＞EXT=NULL；B、P=NULL；C、P—NEXT-FIRST；D、P=FIRST；答案：C解析：循环单链表是单链表的一种特殊形式，其结构特点是链表中最后一个结点的指针域不再是结束标记(NULL)，而是指向链表中的第一个结点，从而使链表形成一个环。在本题中，FIRST指向循环单链表的首结点，P指向尾结点，可知P—＞NEXI=FIRST。142.已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为()。A、DBACEFB、DABECFC、BCDEAFD、ABDCEF答案：D解析：按照遍历左子树要在遍历右子树之前进行的原则，根据访问根节点位置的不同，可得到二叉树的前序，中序和后序3种遍历方法。层序遍历是从根节点(第1层)出发，首先访问第1层的树根节点，然后从左到右依次访问第2层上的节点，其次是第3层上的节点，依此类推，自上而下，自左向右逐层访问各层上的节点。对于二叉树来说，第n层节点最多为2m1。由层序序列可得:F是树根节点，D.E是第2层节点:结合中序序列有DBA构成F的左子树，CE构成F的右子树，进-一步有C是E的左节点、B无右节点:这样A是第4层节点，据DBA序列有B是D的右节点.A是B的右节点。易知后序序列为ABDCEF.143.设指针变量p指向双向链表中节点A，指针变量s指向被插入的节点X，则在节点A的后面插入节点X的操作序列为()A、p-＞right=s；s-＞left=p；p-＞right-＞left=s；s-＞right=p-＞right；B、p-＞right=s；p-＞right-＞left=s；s-＞left=p；s-＞right=p-＞right；C、s-＞left=p；s-＞right=p-＞right；p-＞right=s；p-＞right-＞left=s；D、s-＞left=p；s-＞right=p-＞right；p-＞right-＞left=s；p-＞right=s；答案：D解析：为了防止在插入节点时链表断裂，在修改指针时，需要先使s的后继指针指向p原来的后继节点，然后修改p的后继指针。144.设散列表表长m=14，散列函数H(k)=kmod11。表中已有15，38，61，84四个元素，如果用线性探测法处理冲突，则元素49的存储地址是()。A、8B、3C、5D、9答案：A解析：元素15，38，61，84分别存储在4，5，6，7单元，而元素49的散列地址为5，发生冲突，向后探测3个单元，其存储地址为8。145.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A、53B、73C、48D、24答案：B解析：根据赫夫曼树的构造方法可构造出赫夫曼树，经计算可得带权路径长度为73。146.m阶B+树中除根节点外，其他节点的关键字个数至少为()。A、[m/2]B、[m/2]-1C、[m/2]+1D、任意答案：A解析：这是B+树的定义。147.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为()。A、AB、BC、CD、D答案：D解析：148.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为()。A、9，5，3B、9，5，2，3C、1，2，3D、9，4，2，3答案：D解析：二分查找的基本思想是将n个元素分成大致相等的两部分，取中间位置的节点值与关键字做比较，如果相等，则查找成功；如果关键字的值小于中间节点，则只要在数组的左半部分继续搜索，重复与中间值进行比较，直至查找成功或失败；如果关键字大于中间值，则只要在数组的右半部搜索即可。149.在一裸m阶的B+树中，每个非叶结点的儿子数S应满足()。A、AB、BC、CD、D答案：A解析：m阶B+树包含如下两个特点：(1)每个分支结点至多有m棵子树。(2)除根结点外的所有非终端结点每个结点至少有1(m+1)/21棵子树。150.两个字符串相等的充要条件是()。A.两个字符串中对应位置上的字符相等B.两个字符串的长度相等A、同时具备B、和C、两个条件D、两个字符串的大小相等答案：C解析：两个字符串相等是指两个字符串不仅长度相等，而且在对应位置上的字符也要相等。151.在平衡二叉树中，()。A、任意结点的左右子树结点数目相同B、任意结点的左右子树高度相同C、任意结点的左右子树高度之差的绝对值不大于1D、不存在度为1的结点答案：C解析：该题考查考生对平衡二叉树的理解，形态匀称的二叉树称为平衡二叉树，其严格定义是：一棵空树是平衡二叉树；T是一棵非空二叉树，其左、右子树为TL和TR，令h1和hr分别为左、右子树的深度，当且仅当TL、TR都是平衡=叉树且丨h1-hr丨≤1时，T是平衡二叉树152.下列叙述中，不符合m阶B树定义要求的是()。A、根节点最多有m棵子树B、所有叶结点都在同一层上C、各结点内关键字均升序或降序排列D、叶结点之间通过指针链接答案：D解析：B树的定义。153.数据的存储结构是指()。A、数组类型B、指针类型C、数据之间的逻辑关系D、数据之间的物理关系答案：D解析：数据的存储结构就是物理结构，指数据之间的物理关系。154.假设执行语句S的时间为0(1)，则执行下列程序段的时间为()。for(i=l;k=n;it+)for(j=l;jA、0(n)B、0(n^2)C、O(n×i)D、0(n+1)答案：B解析：观察可知，程序段S的执行频度为T(n)=n^2，得时间复杂度T(n)=O(n^2)。155.链表不具有的特点是()。A、不必事先估计存储空间B、可随机访问任一元素C、插入删除不需要移动元素D、所需空间与线性表长度成正比答案：B解析：链表采用的是链式存储结构，它克服了顺序存储结构的缺点：①它的结点空间可以动态申请和释放；②它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处：①每个结点中的指针域需额外占用存储空间；②链式存储结构是一种非随机存储结构。156.以下叙述不正确的是()。A、后序线索二叉树是不完善的，要对它进行遍历，不需使用栈B、任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈C、任何一棵二叉树都可以不用栈实现先序线索树的先序遍历D、任何一棵二叉树都可以不用栈实现中序线索树的中序遍历答案：B解析：遍历后序线索二叉树不需要使用栈。157.设有n个待排序的记录关键字，则在堆排序中需要()个辅助记录单元。A、AB、BC、CD、D答案：A解析：堆排序的辅助空间为0(1)。158.时间复杂度不受数据初始状态影响而恒为0(nlog2n)的是()。A、堆排序B、快速排序C、希尔排序D、冒泡排序答案：A解析：堆排序无论是最好情况还是最坏情况，时间复杂度都是相等的。159.在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标为k(起始下标为1)，采用顺序存储更节省空间的情况是()。A、d＜12n/(k-n)B、d＞12n/(k-n)C、d＜12n/(k+n)D、d＞12n/(k+n)答案：A解析：160.如下陈述中正确的是()。A、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串答案：A解析：串的长度可以等于0，等于0时叫作空串。空串和空白串是不同的，例如：Strings=“”，是空串；Strings=NULL，是空白串。串中的元素只能是字符，但不仅仅是字母。161.关于哈夫曼树，下列说法正确的是()。A、在哈夫曼树中，权值相同的叶子结点都在同一层上B、在哈夫曼树中，权值较大的叶子结点一般离根结点较远C、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近D、在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理答案：C解析：哈弗曼编码中不允许出现两个字符编码相同的情况。162.中缀表达式A-(B+C/D)*E的后缀形式是()。A、AB-C+D/E*B、ABC+D/-E*C、ABCD/E*+-D、ABCD/+E*-答案：D解析：将中缀表达式表示成二叉树的形状，则这棵二叉树的后序遍历序列即为表达式的后缀形式。163.用邻接矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度m路径相连，则只要检查()的第i行和第j列的元素是否为零即可。A、mAB、AC、AmD、Am-1答案：C解析：要判断相邻矩阵A中任意两个顶点Vi和Vj之间是否有长度为m的路径相连，只要检查Am的第i行第j的元素是否为0即可，若为0则无，否则就存在。164.下面关于工程计划的AOE网的叙述中，不正确的是()。A、某些关键活动若提前完成，那么整个工程将会提前完B、关键活动不按期完成就会影响整个工程的完成时间C、任何一个关键活动提前完成，那么整个工程将会提前完成D、所有的关键活动都提前完成，那么整个工程将会提前完成答案：C解析：AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，则必须同时提高在几条关键路径上的关键活动。165.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则完全二叉树的结点个数最多是()。A、39B、52C、111D、119答案：C解析：根据完全二查处定义，前6层应该是满二叉树，共有2^6-1=63个结点。第6层有8个叶节点。说明有32-8=24个结点不是叶节点，因此最多时共有63+24*2=111个。166.下列叙述正确的个数是()。(1)向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。(2)对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。(3)所谓平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。(4)删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二又排序树。A、4B、3C、2D、1答案：D解析：只有第3项是正确的。167.下列说法正确的是()。A、任何有向网络(AOV-网)拓扑排序的结果是唯一的B、有回路的图不能进行拓扑排序C、在AOE网中一定只有一条关键路径D、一个正常的AOE网中只能有一个源点、一小汇点和一条关键路径答案：B解析：拓扑排序的结果不一定是唯一的；在AOE网中，关键路径不止一条。168.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3]存放在什么位置？脚注(10)表示用10进制表示。()A、678B、688C、692D、696答案：C解析：A[2][2]是A[0][0]后面的第2n+2个元素，即2n+2=676-644，解得n=15。A[3][3]是A[2][2]后面的第n+1个元素，676+n+1=692，则A[3][3]存放位置是692。169.n个结点的线索二叉树上含有的线索数为()。A、nB、2nC、n-1D、n+1答案：D解析：对于有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域，由于只有n-1个结点被有效指针所指向.则共有2n-(n-1)=n+1个空链域。用这些空链域存放指向结点的前驱和后继结点的指针，这些指针称作线索。170.已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是()。A、dacbB、cadbC、dbcaD、以上答案都不对答案：B解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。A项，输入序列为abcd，输出序列为dacb，由输出受限性质可知以da开头的结果只有dabc。B项，输入序列为abcd，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入b，这时队列中的序列为ba，再在输出端输入c，这时队列中的序列为bac；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输出d，再输出b。最后得到输出序列为cadb。C项，输入序列为abcd，输出序列为dbca，由输出受限性质可知以db开头的结果只有dbac。171.有种关系模式R=＜U，F＞，U={C，T，H，X，S}，F={C→T，(H，X)→C，(H，T)→YC，(H，S)→Y}则表示模式R的码是()。A.CB.(H，S)A、B、Y)C、D、T)答案：B解析：由题可得如下推导：(H，S)+R，(H，R)+C，C--4T，(H，T)--4R，故可知(H，S)为关系模式的码。172.在双向循环链表中，在p所指的结点之后插入指针f所指的新结点，其操作步骤是()。A、AB、BC、CD、D答案：D解析：在双向循环链表中。在p所指的结点之后插入指针f所指的新结点的操作步骤为：改变f的前驱指针域，使其指向p；然后改变f的后继指针域，使其指向p的后继；接下来修改p的后继结点得前驱指针域，指向f，最后将f的地址付给p的后继指针。具体操作为：f—＞pnor=p；f—＞next=p—＞next；p—＞next—＞prior=f；P—＞next=f。173.当各边上的权值满足()的条件时，BFS算法可用来解决单源最短路径问题。A、均相等B、均互不相等C、不一定相等D、其他答案：A解析：单源最短路径问题是指：从已知图G=(V，E)中找出某给定的源结点S∈V到V中的每个结点的最短路径。当各边上的权值均相等时，BFS算法可用来解决单源最短路径问题。174.A、LRNB、NRLC、RLND、RNL答案：D解析：由7，5，6的顺序可知遍历顺序为RNL。175.字符串的长度是指()。A、串中不同字母的个数B、串中字符不同的个数C、串中不同数字的个数D、串中所含字符的个数答案：D解析：字符串的长度是指串中所含的字符的个数。176.由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为()。A、27B、38C、51D、75答案：D解析：177.在长度为n(Il＞1)的()上，删除第一个元素.其时间复杂度为O(n)。A、只有首结点指针的不带头结点的循环单链表B、只有尾结点指针的不带头结点的循环单链表C、只有尾结点指针的带头结点的循环单链表D、只有头结点的循环单链表答案：A解析：只有首结点指针的不带头结点的循环单链表删除第一个元素，需要遍历整个链表，因此A项的时间复杂度为O(n)，BCD三项的时间复杂度都为O(1)。178.引入二叉线索树的目的是()。A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便地进行插入与删除C、为了能方便地找到双亲D、使二叉树的遍历结果唯一答案：A解析：当以二叉链表作为存储结构存储非线索化的二叉树时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一遍历序列中的直接前驱和直接后继的结点信息，这种信息只有在遍历的动态过程中才能得到。二叉线索树利用空链域存放结点的前驱和后继结点的信息，这样能保存遍历过程中得到的信息。可见，引入二叉线索树的目的是方便查找结点的前驱或后继结点的速度。179.如果一棵完全二叉树共有26个结点，则必定有()个结点的度为1。A、0B、1C、3D、13答案：B解析：26个结点，可知该二叉树有5层。由于前4层组成一棵满二叉树，共15个结点，则共有11个叶子结点，可知只有1个结点的度为1。180.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作()型调整以使其平衡。A、LLB、LRC、RLD、RR答案：C解析：平衡二叉树是在构造=叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系。进行相应的旋转，使之成为新的平衡子树。具体步骤如下：(1)每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡=叉树没有失去平衡，继续插入、结点；(2)若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；(3)判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；(4)如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树。在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；(5)计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。结合上面的知识点，对于题目中的情况应该选择RL型调整。181.串′ababaaababaa′的next数组值为()。A、01