军队文职人员（收发员兼通信员）考试题库大全-数据结构与算法（重点题）

PAGEPAGE1军队文职人员（收发员兼通信员）考试题库大全-数据结构与算法一、单选题1.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A、53B、73C、48D、24答案：B解析：根据赫夫曼树的构造方法可构造出赫夫曼树，经计算可得带权路径长度为73。2.顺序查找法适合于()结构的线性表。A、哈希存储B、顺序存储或链式存储C、压缩存储D、索引存储答案：B解析：顺序查找法适合于线性表(不论线性表采用顺序存储还是链式存储)。而哈希存储查找是根据哈希函数值直接查找。压缩存储是通过对应关系进行查找。索引存储是通过索引表进行查找。3.下列排序算法中，()排序在某趟结束后不一定选出一个元素放到其最终的位置上。A、选择B、冒泡C、归并D、堆答案：C解析：根据归并排序的思想，在归并排序工程中，某趟排序结束后，某个元素只在它的子序列中找到了最终的位置。4.在一个具有n个单元的顺序栈中，假定以地址低端(即下标为0的单元)作为栈底，以top作为栈顶指针，当出栈时，top的变化为()。A、top=top-1；B、top=top+1；C、不变D、top=0；答案：A解析：以top作为栈顶指针，当出栈时，top的变化为top=top-1。5.设一个有序的单链表中有n个节点，现要求插入一个新节点后使得单链表仍然保持有序，则该操作的时间复杂度为()。A、AB、BC、CD、D答案：C解析：对单链表进行插入节点的操作，就是对单链表进行查找，找到节点需要插入的位置，然后修改指针，将节点插入单链表。6.双向链表中有两个指针域llink和rlink，分别指向前驱和后继，设β指向表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插人为()。A、AB、BC、CD、D答案：D解析：p→llink→rlink=q；q→rlink=p；q→llink=p→llink；p→llink=q7.一个队列的入队顺序是a，b，c，d，则出队顺序是()。A.a，b，C，dB.b，C，d，aA、d，B、b，aC、D、d，a，b答案：A解析：队列的特点是先进先出，因此出队的序列于入队的序列完全相同，这点与栈不同。8.A、AB、BC、CD、D答案：C解析：9.A、45B、46C、55D、56答案：D解析：本题目甲对角线以下均为-3，个与共他元素里复，可知这45个元素只需用一个但米表示，故该矩阵只需用(100-45)+1=56个元素来表示。10.堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次输出堆顶元素。设给定序列{48，62，35，77，55，14，35，98}，若在堆排序的第一阶段将该序列建成一个堆(大根堆)，那么交换元素的次数为()。A、5B、6C、7D、8答案：B解析：11.用二分(对半)查找表的元素的速度比用顺序法的速度要()。A、必然快B、必然慢C、相等D、不能确定答案：D解析：两者的查找速度要看元素是否有序以及所找元素所在的位置。比如：如果要查找的元素是表的第一个元素，则顺序查找速度要快。如果要查找的元素刚好位于顺序表的中间位置，则二分查找更快。12.设二维数组A[6][0]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址为()。A、1000B、860C、1140D、1200答案：A解析：每个数组元素占用4个存储单元，按行优先顺序存放的数组元素，则a[3][5]的存储地址为860+(3×10+5)×4=1000。13.高度为5(除叶子层之外)的三阶B-树至少有()个结点。A、30B、31C、32D、33答案：B解析：14.深度为k的完全二叉树中最少有()个结点。A、k-1B、2C、k+1D、2-1答案：B解析：最少有两个结点，一个为根结点，另一个为根结点的左子树。15.下面关于线性表的叙述中，错误的是()。A、线性表采用顺序存储，必须占用一片连续的存储单元B、线性表采用顺序存储，便于进行插入和删除操作C、线性表采用链接存储，不必占用一片连续的存储单元D、线性表采用链接存储，便于插入和删除操作答案：B解析：线性表的顺序存储称为顺序表。顺序表就是把线性表中的所有元素按照其逻辑顺序。依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中，不便于插入和删除；线性表的链式存储称为链表。在链式存储中，存储结点之间通过指针链接到下一个结点，不必占用一片连续的存储单元，而且便于插入和删除操作。16.若一组记录的关键码为(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解析：由于选择第一个记录为基准，第一次排序即对整个序列进行一趟快速排序。使得位于基准左侧的关键码均小于基准，位于基准右侧的关键码均大于基准。17.n个结点的线索二叉树上含有的线索数为()。A、nB、2nC、n-1D、n+1答案：D解析：对于有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域，由于只有n-1个结点被有效指针所指向.则共有2n-(n-1)=n+1个空链域。用这些空链域存放指向结点的前驱和后继结点的指针，这些指针称作线索。18.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a1，1为第一元素，其存储地址为1，每个元素占一个地址空间，则a8·5的地址是()。A、13B、33C、18D、40答案：B解析：数组下标从1开始，只存储其下三角形元素，在A，5的前面有7行，第1行有1个元素，第2行有2个元素，…，第7行有7个元素，这7行共有(1+7)×7/2=28个元素，在第8行中，a8·5的前面有4个元素，所以a8·5前有28+4=32个元素，其地址为33。19.字符串的长度是指()。A、串中不同字母的个数B、串中字符不同的个数C、串中不同数字的个数D、串中所含字符的个数答案：D解析：字符串的长度是指串中所含的字符的个数。20.有种关系模式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)为关系模式的码。21.线性表是()。A、一个有限序列，可以为空B、一个有限序列，不可以为空C、一个无限序列，可以为空D、一个无限序列，不可以为空答案：A解析：线性表是具有相同特性的数据元素的一个有限序列，可以为空。22.对下列关键字序列用快速排序法进行排序时，速度最快的是()。A、{21，25，5，17，9，23，30}B、{25，23，30，17，21，5，9}C、{21，9，17，30，25，23，5}D、{5，9，17，21，23，25，30}答案：A解析：对于快速排序，若数据初始特性能够使每趟排序划分的两块大小相当，则排序效率会比较高。在A中，第一个元素21刚好是序列中7个元素的中间元素，将序列分成的两个部分大小相等，第一次划分后的结构为(9，17，5)21(25，23，30)；第二次划分，左右两部分的第一个元素也刚好是所在块序列的中间元素，同样将所在块分成均等的两部分。在这种情况下排序的速度最快。23.设有向无环图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解析：24.表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为()。A、nB、n/2C、(n-1)/2D、(n+1)/2答案：C解析：25.A、AB、BC、CD、D答案：C解析：26.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为()。A、4B、6C、5D、7答案：A解析：27.A、21/7B、28/7C、15/6D、21/6答案：B解析：28.单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是()。A、若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)B、在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理C、加入头结点后，在链表中进行查找运算的时间复杂度为O(1)D、加入头结点后，代表链表的头指针不因为链表为空而改变答案：C解析：在链表中加入头结点后，查找表中某一元素仍然要从头指针出发，顺序找到目标元素或失败时找到表尾为止，时间复杂度与表长成正比。故D项错误。29.如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用的查找法是()。A、分块查找B、顺序查找C、折半查找D、基于属性答案：A解析：分块查找又称索引顺序查找，是一种性能介于顺序查找和二分查找之间的查找方法。其基本思想是：(1)首先查找索引表：索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。(2)然后在已确定的块中进行顺序查找：由于块内无序，只能用顺序查找。分块查找既能较快的查找，又能适应动态变化的要求。30.在向图的邻接矩阵表示中，计算第i个顶点八度的方法是()。A、第i行非零元素个数B、第i列非零元素个数C、第i行零元素个数D、第i列零元素个数答案：B解析：先用一个二维数组Edge存储表示邻接矩阵，输入文件中顶点的序号是从1开始，当输入一条有向边＜u，v＞时，将Edge[u-1][v-1]=1即可；第i+1个顶点的出度等于邻接矩阵中第i行所有元素中元素值为1的个数，把第i行所有元素值累加起来，得到的结果也是该顶点的出度，同理，在计算第i+1个顶点的入度时，也只需要将第i列所有元素值累加起来即可。31.若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有()个顶点。A、11B、10C、9D、8答案：B解析：要使图的顶点数最少，应该尽量构造一个完全图，具有36条边的无向完全图的顶点数是9，又因为图示非连通的，所以再加一个孤立的顶点即可。所以至少有10个顶点。32.从一个具有N个结点的单链表中查找其值等于X结点时，查找成功的情况下，需平均比较()结点。A、NB、N/2C、(N-1)/2D、(N+1)/2答案：D解析：33.快速排序在最坏情况下的时间复杂度为()。A、AB、BC、CD、D答案：D解析：34.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，es，e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是()。A、6B、4C、3D、2答案：C解析：35.在一个无向图中，所有顶点的度数之和等于所有边数()倍。A、1/2B、2C、1D、4答案：B向图中每条边都有两个顶点，所以所有顶点的度数之和等于所有边数的2倍。36.一棵m阶非空B-树，每个结点最多有()棵子树。A、m/2B、m-1C、mD、m+1答案：C解析：B-树中每个结点之多有m棵子树，m就是B-树的阶。37.树形结构的特点是：一个结点可以有()。A、多个直接前驱B、多个直接后继C、多个前驱D、一个后继答案：B解析：树的唯一根节点无前驱，叶子结点可以有多个且无后继，树的其他结点可以有多个后继但只能有一个前驱。38.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。A、数据的处理方法B、数据元素的类型C、数据元素之间的关系D、数据的存储方法答案：C解析：在存储数据时，需要存储数据元素的值和数据元素之间的关系。39.向一个带头结点HS的链栈中插入一个s所指结点时需执行()。A、HS-＞next=s；B、s-＞next=HS-＞next；HS-＞next=s；C、s-＞next=HS：HS=s；D、s-＞next=HS；HS=HS-＞next；答案：B解析：为了将结点s插入到带头结点HS的链栈中，首先需要修改s的指针域，使得s的下一个结点为链栈中的第一个有效结点，即数据域中存放有效数据的结点，该结点可由HS的指针域获得，因此相应的语句为s-＞next=HS-＞next，之后使s结点成为链栈中的第一个有效结点，即HS的指针域指向s，相应的语句为HS-＞next=S。40.A、n-iB、n-i+lC、n-i-lD、i答案：A解析：顺序表中的删除操作是通过将当前结点用后面结点的值覆盖来实现的，因此删除第i个元素主要是前移第i个元素后的所有的元素，即n-i个元素。41.非空的循环单链表head的尾结点P满足的条件是()。A、P.link=headB、p.link=NILC、p=NIL，D、p=head答案：A解析：对于循环单链表来说尾结点的指针指向第一个元素。42.在一裸m阶的B+树中，每个非叶结点的儿子数S应满足()。A、AB、BC、CD、D答案：A解析：m阶B+树包含如下两个特点：(1)每个分支结点至多有m棵子树。(2)除根结点外的所有非终端结点每个结点至少有1(m+1)/21棵子树。43.在有n个结点的二叉链表中，值为非空的链域的个数为()。A、n-1B、2n-1C、n+1D、2n+1答案：A解析：本题考查的是二叉树的链式存储。由于在有n个结点的二叉链表中，值为空的链域的个数为n+1个，而总的链域为2n(在二叉树中每个结点头2个链域)。所以，非空的链域的个数为2n-(n+1)=n-1。44.在一个双链表中，删除P结点之后的一个结点的操作是()。A、AB、BC、CD、D答案：C解析：考查双链表中插入操作，要注意保存后继节点。45.在向下生成的堆栈中，如果入栈指令PUSHX的操作定义为：SP←(SP)+1，M(SP)←M(X)，则出栈指令POPX应定义为()。A、SP←(SP)-1，M(X)←M(SP)B、SP←(SP)+1，M(X)←M(SP)C、M(X)←M(SP)，SP←(SP)-1D、M(X)←M(SP)，SP←(SP)+1答案：C解析：入栈是先定位栈顶指针然后存储数据，出栈是先出数据，然后再定位栈顶指针。46.有n个记录的文件，若关键字位数为d，基数为r，则基数排序共需进行()遍分配与收集。A、nB、rC、dD、d+r答案：C解析：47.以下数据结构中哪一个是非线性结构？()A、线性表B、栈C、队列D、二叉树答案：D解析：线性表、栈、队列都是线性结构，树、图是非线性结构。48.非空的循环单链表FIRST的尾结点(由P所指向)满足：()。A、P—＞EXT=NULL；B、P=NULL；C、P—NEXT-FIRST；D、P=FIRST；答案：C解析：循环单链表是单链表的一种特殊形式，其结构特点是链表中最后一个结点的指针域不再是结束标记(NULL)，而是指向链表中的第一个结点，从而使链表形成一个环。在本题中，FIRST指向循环单链表的首结点，P指向尾结点，可知P—＞NEXI=FIRST。49.设有5000个元素，希望用最快的速度挑选出前10个最大的，采用()方法最好。A、希尔排序B、归并排序C、快速排序D、堆排序答案：D解析：堆排序不必将整个序列排序即可确定前若干个最大(或最小)元素。50.如果一棵完全二叉树共有26个结点，则必定有()个结点的度为1。A、0B、1C、3D、13答案：B解析：26个结点，可知该二叉树有5层。由于前4层组成一棵满二叉树，共15个结点，则共有11个叶子结点，可知只有1个结点的度为1。51.设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为()。A、AB、BC、CD、D答案：B解析：52.设无向图的顶点个数为n，则该图最多有()条边。A、AB、BC、CD、D答案：B解析：53.下列不属于内部排序的算法是()。A、归并排序B、拓扑排序C、树型排序D、折半插入排序答案：B解析：归并排序、树型排序、折半插入排序属于内部排序算法，拓扑排序不属于内部排序算法。54.在由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为()。A、20B、29C、30D、35答案：B解析：当把森林转换成二叉树后，第二、第三和第四棵树均在第一棵树的根结点的右子树上。55.二维数组A的每个元素是由6个字符组成的串，行下标的范围从0～8，列下标的范围是从0～9，则存放A至少需要()个字节。A、240B、540C、90D、180答案：B解析：数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元。56.若对27个元素只进行三趟多路归并排序，则选取的归并路数为()。A、2B、3C、4D、5答案：B解析：57.在一棵高度为h的理想平衡二叉树中，最少含有()个结点，最多含有()个结点。A、AB、BC、CD、D答案：D解析：58.A、abcfdegB、abcgfdeC、abcdefgD、abcfgde答案：A解析：本题考查深度优先算法。59.如果以链表作为栈的存储结构，则退链栈操作时()A、必须判断链栈是否满B、判断链栈元素的类型C、必须判断链栈是否空D、对链栈不做任何判断答案：C解析：在链表的退链栈操作时，如果栈已空.就没有元素可供退栈，返回退栈失败信息，所以必须判断链栈是否空。60.循环队列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。61.中缀表达式A-(B+C/D)*E的后缀形式是()。A、AB-C+D/E*B、ABC+D/-E*C、ABCD/E*+-D、ABCD/+E*-答案：D解析：将中缀表达式表示成二叉树的形状，则这棵二叉树的后序遍历序列即为表达式的后缀形式。62.用s表示入栈操作，*表示出栈操作，栈的初态、终态均为空，人栈和出栈的操作序列可表示成仅为由S和*组成的序列。下面的序列中合法的操作序列有()。A、S*SS*S**B、SSS****SC、S**S*SS*D、SSS*S*S*答案：A解析：要使栈的初态、终态均为空，入栈和出栈的操作次数应该相等，因此排除D项。而BC两项项都出现某一时刻栈已空的情况下执行出栈操作。63.若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有()棵树。A、kB、nC、n-kD、n+k答案：C解析：一个具有n个结点的树有n-l条边，结点数比边数多1，则若一个森林中有m棵树，其结点数比边数多m。反过来，森林中树的个数等于结点数减去边数。64.头指针为head的带头结点的循环链表为空的判定条件是()。A、head=nullB、head—＞next=nullC、head—＞next=headD、head—＞null答案：C解析：循环链表为空，即头结点的后继结点是头结点本身，具体的操作语句为head—＞next=head。65.设有向图G=(V，E)和G′-(V′，E′).如(G′)是G生成树，下面说法中不正确的是()A、G′为G的连通分量B、G′为G的无环子图C、G′为G的子图D、G′为G的极小连通子图且V′=V答案：A解析：B项、D项都是生成树的特点，而A项为概念错误：G′为连通图而非连通分量，图的连通分量是指无向图中的极大连通子图。66.对于具有n个顶点、6条边的图()。A、采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)B、进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C、采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)D、进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关答案：A解析：67.在()存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。A、树形存储结构B、链式存储结构C、索引存储结构D、散列存储结构答案：D解析：散列存储结构中是根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置。而树形存储结构、链式存储结构和索引存储结构中关键字在结构中的相对位置是随机的。68.A、顶点序列B、边序列C、权值总和D、边的条数答案：A解析：69.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是()。A、(1)，(2)B、(1)C、(1)，(2)，(3)D、(2)答案：B解析：静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点，同时使用游标(指示器cur)代替指针以指示结点在数组中的相对位置。这种存储结构仍然需要预先分配一个较大空间，但是在进行线性表的插入和删除操作时不需要移动元素，仅需要修改“指针”，因此仍然具有链式存储结构的主要优点，(2)，(3)是正确的，但它不具备直接存取数据的特性，所以只有(1)是错误的。70.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于()。A、nB、n-1C、n+1D、2×n答案：C解析：71.在最好和最坏情况下的时间复杂度均为0(nlogn)且稳定的排序方法是()。A、基数排序B、归并排序C、快速排序D、堆排序答案：B解析：快速排序和堆排序是不稳定的，基数排序和归并排序是稳定的。基数排序的平均时间为O(d(n+rd))，最坏情况下时间复杂度为O(d(n+rd))；归并排序是一种稳定的排序方法，其最好和最坏情况下的时间复杂度为O(nlogn)。72.假定一棵度为3的树中结点数为50，则其最小高度应为()。A、5B、6C、3D、4答案：A解析：73.快速排序最易发挥其长处的情况是()。A、被排序的数据中含有多个相同排序码B、被排序的数据已基本有序C、被排序的数据完全无序D、被排序的数据中的最大值和最小值相差悬殊答案：C解析：74.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1]～A[n]中，结点A[i]若有左子树，则左子树的根结点是()。A、A[i/2]B、A[2i]C、A[2i-1]D、A[2i+1]答案：B解析：据二叉树的性质5，对完全二叉树从上到下、从左至右给结点编号，若编号为2i的结点存在，则i的左子树一定是A[2i]。75.在单链表指针为P的结点之后插入指针为s的结点，正确的操作是()。A、AB、BC、CD、D答案：B解析：在单链表结点P后插入结点s，要先改变s结点的指针域，指向p的后继结点。然后将s的地址赋给P的指针域。具体的操作语句为s—＞next=P—＞next；p—＞next=s。76.在具有n个结点的顺序表，算法的时间复杂度是O(1)的操作是()。A、AB、BC、CD、D答案：A解析：77.二维数组A的每个元素是由6个字符组成的串，其行下标i=O，1，…，8，列下标j=1，2，…，10。设每个字符占一个字节。若A按行先存储，元素A[8，5]的起始地址与当A按列先存储时起始地址相同的元素是()。A、A[8，5]B、A[3，10]C、A[5，8]D、A[0，9]答案：B解析：元素A[8，5]的起始地址与当A按列先存储时的A[i，j]元素的起始地址相同，即8×10+5-1=(j-1)×9+i，将四个答案代入可得正确答案。78.下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是()。A、顺序结构B、链式结构C、索引结构D、Hash结构答案：A解析：顺序结构又称连续结构。这是一种最简单的物理结构，它把逻辑上连续的文件信息依次存放在连续编号的物理块中，只要知道文件在存储设备上的起始地址(首块号)和文件长度(总块数)，就能很快地进行存取。这种结构的优点是访问速度快，缺点是文件长度增加困难。因此，顺序结构的磁盘空间利用率不高，不利于文件长度动态增长。79.将5个字母“ooops”按此顺序入栈，则有()种不同的出栈顺序可以仍然得到“ooops”。A、1B、3C、5D、6答案：C解析：此题可以首先列出所有可能的出栈顺序，然后列出各个出战顺序的结果，计数即可。80.有m个叶子结点的哈夫曼树所具有的结点数为()。A、mB、m+1C、2mD、2m-1答案：D解析：哈夫曼树中仅有度为0和2的结点，由二叉树的性质可知，具有m个叶子结点的哈夫曼树具有m-1个度为2的结点，因此，具有m个叶子结点的哈夫曼树所具有的节点数为2m-1。81.已知一个有序表为(12，18，24，35，47，50，62，83，90，115，134)，当折半查找值为90的元素时，经过()次比较后查找成功。A、2B、3C、4D、5答案：A解析：根据二分法查找的查找过程，首先将90与表中中间的元素50进行比较，由于90大于50，所以在线性表的后半部分查找。第二次与比较的元素是后半部分的中间元素，即90，这时两者相等，即查找成功。82.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为()。A、219B、129C、189D、229答案：D解析：83.散列函数有一个共同的性质，即函数值应当以()概率取其值域的每个值。A、最大概率B、最小概率C、平均概率D、同等概率答案：D解析：散列函数的构造万痃有很多，每种构造方法的目的都是尽量减少冲突。为了减少冲突计算出的结果应以同等概率分布到值域的各个部分。84.n个顶点的连通图至少有多少条边()。A、n-1B、nC、n+1D、0答案：A解析：至少要有(n-1)条边(也就是树)才能保证图为连通图。85.一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是()。A、43512B、12345C、54321D、45321答案：A解析：此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序(指的是元素的序号)的两个元素。86.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是()。A、head==0B、head-＞next==0C、head！=0D、head-＞next==head答案：A解析：因为单链表没有头结点，所以当头指针为空时证明链表为空。87.A、14B、19C、21D、26答案：C解析：本题考查最小生成树算法。88.A、(1)，(2)，(3)B、(1)C、(1)，(3)D、(2)，(3)答案：C解析：89.线索化的二叉树中，某结点*P没有孩子的充要条件是()。A、p-＞lchild=NULLB、p-＞ltag=l&&p-＞rtag=1C、p-＞ltag=0D、p-＞lchild=NULL&&p-＞ltag=1答案：B解析：考查线索二叉树。90.算法分析的目的是()。A、找出数据结构的合理性B、研究算法中输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档性答案：C解析：算法分析的目的是分析算法的效率以求改进。91.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为()。A、AB、BC、CD、D答案：B论是顺序存储还是链式存储，使用顺序查找法的时间复杂度相同。92.高度为7的AVL树最少有()个结点。A、31B、32C、33D、34答案：C解析：93.下列命题正确的是()。A、一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一B、一个图的邻接矩阵表示是唯一的，邻接表表示也唯一C、一个图的邻接矩阵表示是唯一的，邻接表表示不唯一D、一个图的邻接矩阵表示不唯一的，邻接表表示是唯一答案：C解析：一个图的邻接矩阵表示是唯一的，邻接表表示不唯一。94.在一个长度为n(n＞1)的带头结点单链表h上，另设有尾指针r(指向尾结点)。与链表的长度有关的操作是()。A、删除单链表中的第一个元素B、删除单链表中的最后一个元素C、在单链表第一个元素前插入一个新元素D、在单链表最后一个元素后插入一个新元素答案：B解析：在单链表中要删除最后一个元素必须找到尾结点的前驱结点的指针。由于单链表只能访问结点的下一个结点，所以根据尾指针不能够直接找到它的前驱结点，只有从头开始依次向下找到尾结点的前驱结点。所以删除单链表中的最后一个元素与链表的长度有关。95.设一棵二叉树的深度为k，则该二叉树中最多有()个结点。A、1B、2k-1C、2D、k-1答案：B解析：一棵深度为k的二叉树，结点最多为2k-1个。96.如果S是由有序树T转换的二叉树，则T中的结点的后序遍历顺序是S结点的()。A、先序遍历B、中序遍历C、后序遍历D、层次遍历答案：B解析：树转换成二叉树的过程：将结点的最左边的孩子作为该节点的左孩子，下一个兄弟结点作为右孩子。所以树的后序遍历恰好对应于二叉树的中序遍历。97.指出在顺序表F={2，5，7，10，14，15，18，23，35，41，52}中，用二分查找法查找12需要进行多少次比较()。A、2B、3C、4D、5答案：C解析：折半查找又称二分查找，其基本思想：首先用要查找的关键字k与中间位置的结点的关键字相比较，这个中间结点把线性表分成了两个子表，若比较结果相等则查找完成；若不相等，再根据k与该中问结点关键字的比较大小确定下一步查找哪个子表，这样递归进行下去，直到找到满足条件的结点或者该线性表中没有这样的结点。98.线索二叉树中某结点R没有左孩子的充要条件是()。A、R.ltag=1B、R.rchild=NULLC、R.lchild=NULLD、R.ltag=0答案：D解析：线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为0。99.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做()次线性探测。A、n(n+1)B、nC、n(n+1)/2D、n(n-1)/2答案：D解析：线性探测解决冲突的办法指一旦目标空间被占有，则探测相邻的下一个空间，如果空闲则插入，否则继续向下一个探测，如果到了队列末尾则返回队列头探测，一旦全部空间都被占据则无法插入。100.快速排序最不利于发挥其长处的情况是()。A、待排序的数据中含有多个相同值B、待排序的数据已基本有序C、待排序的数据量太大D、被排序的数据数量为奇数答案：B解析：各种排序方法对待排序的数据中是否含有多个相同值、被排序的数据数量为奇数或偶数都没有影响。快速排序等改进的排序方法均适用于待排序数据量较大的情况。101.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是()A、EB、FC、GD、H答案：C解析：102.串′ababaaababaa′的next数组值为()。A、01234567899B、012121111212C、011234223456D、0123012322345答案：C解析：103.设指针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。104.队列是一种()的线性表。A、先进先出B、只能插入C、先进后出D、只能删除答案：A解析：队列的特点是先进先出、后进后出。105.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为()。A、e，nB、n.eC、2n，eD、n.2e答案：D解析：使用邻接表存储图，图有多少结点，邻接表就有多少个表头，无向图的表结点个数为2e。106.设一组初始关键字记录关键字为(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指向同一节点，一趟排序结束。107.对关键码序列28，16，32，12，60，2，5，72快速排序.从小到大一次划分结果为()。A、(2，5，12，16)26(60，32，72)B、(5，16，2，12)28(60，32，72)C、(2，16，12，5)28(60，32，72)D、(5，16，2，12)28(32，60，72)答案：B解析：根据快速排序的思想，容易得到序列28，16，32，12，60，2，5，72一次排序后的结果(5，16，2，12)28(60，32，72)。108.求解Hanoi问题时，若初始有5个圆盘，则移动圆盘的次数是()。A、7B、15C、31D、5答案：C解析：109.二叉排序树中，最小值结点的()。A、左、右指针均为空B、左、右指针均不为空C、左指针一定为空D、右指针一定为空答案：C解析：在二叉排序树中，值最小的结点一定是中序遍历序列中第一个被访问的结点，即二叉树的最左下结点。110.某二叉树的前序遍历序列为UKLMNO，中序遍历序列为JLKINMO，则后序遍历序列为()。A、JLKMNOIB、LKNJOMIC、LKJNOMID、LKNoMI答案：C解析：111.关于哈夫曼树，下列说法正确的是()。A、在哈夫曼树中，权值相同的叶子结点都在同一层上B、在哈夫曼树中，权值较大的叶子结点一般离根结点较远C、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近D、在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理答案：C解析：哈弗曼编码中不允许出现两个字符编码相同的情况。112.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为()。A、5B、11C、7D、6.5答案：D解析：分块查找是先在索引下进行查找，找到该元素可能存在的块号，然后在块中顺序查找。则本题的平均查找长度为(5+1)/2+(6+1)/2=6.5。113.将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最多需要比较的次数是()。A、N，2N-1B、N-l，2NC、N，2ND、N-l，2N-1答案：A解析：对于此题而言最少的比较次数是，其中一个有序表的最后一个数小于另一表的的第一个数，那么直接合并即可。当一个表递增一个表递减且递减表时，需要比较ZN-1次。114.静态查找与动态查找的根本区别在于()。A、所包含的数据元素的类型不一样B、存储实现不一样C、它们的逻辑结构不一样D、施加在其上的操作不同答案：D解析：静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。115.判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A、求关键路径的方法B、求最短路径的Dijkstra方法C、广度优先遍历算法D、深入度优先遍历算法答案：D解析：判断一个图是否存在回路的方法包括：(1)设图G是n个顶点的无向图，若G的边数e＞=n，则图G中一定有回路存在。(2)设图G是n个顶点的无向连通图，若G的每个顶点的度＞=2，则图G中一定有回路存在。(3)利用拓扑排序算法可以判断图中是否存在回路。即在拓扑排序输出结束后所余下的顶点均有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在有回路。(4)利用深度优先遍历算法可以判定图G中是否存在回路。对于无向图来说，若深度优先遍历过程中遇到了回边则必定存在环；对于有向图来说，这条回边可能是指向深度优先森林中另一棵生成树上顶点的弧；但是，如果从有向图上的某个项点v出发进行深度优先遍历，若在dfs(v)结束之前出现一条认顶点v到顶点v的回边，因u在生成树上是v的孙子，则有向图必定存在半含顶点u和顶点v的环。116.若要求尽可能快地对序列进行稳定的排序，则应选()A、快速排序B、归并排序C、冒泡排序D、堆排序答案：B解析：117.若用单链表来表示队列，则应该选用()。A、带尾指针的非循环链表B、带尾指针的循环链表C、带头指针的非循环链表D、带头指针的循环链表答案：B解析：假设尾指针为TAIL，则通过TAIL可访问队尾，通过TAIL—＞next可访问队头。118.设有一个二维数组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。119.采用开放定址法处理散列表的冲突时，其平均查找长度()。A、与链接法处理冲突相同B、高于二分查找C、低于链接法处理冲突D、高于链接法处理冲突答案：D解析：开放定址法处理冲突的平均查找长度高于链接法。120.按照二叉树的定义，具有3个结点的二叉树有()种。A、3B、4C、5D、6答案：C解析：121.完全二叉树高度为h，则最左边的叶子结点序号为()。A、AB、BC、CD、D答案：B解析：122.在一棵完全二叉树中，其根的序号为1，()可判定序号为p和q的两个结点是否在同一层。A、AB、BC、CD、D答案：A解析：123.以比较为基础的排序算法在最坏情况下的计算时间下界为()。A、AB、BC、CD、D答案：D解析：124.对特殊矩阵采用压缩存储的目的主要是为了()。A、去掉矩阵中的多余元素B、减少不必要的存储空间C、表达变得简单D、对矩阵元素的存取变得简单答案：B解析：在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。125.算法指的是()。A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列答案：D解析：算法是精确定义的一系列规则，它指出怎样从给定的输入信息经过有限步骤产生所求的输出信息。它既不是计算机程序，也不是某种算术运算。126.设某强连通图中有n个顶点，则该强连通图中至少有()条边。A、n+1B、n(n-1)C、nD、n(n+1)答案：C解析：强连通图是指在一个有向图中，若从节点i到节点j有路径，并且节点j到i有路径，那么为强连通图。127.Hash表是用于数据存储的一种有效的数据结构，Hash表的查找复杂度依赖于Hash值算法的有效性，在最好的情况下，Hash表的查找复杂度为()。A、O(nlogn)B、O(logn)C、O(n)D、O(1)答案：D解析：0(1)，哈希表是通过计算hashcode来定位元素位置，所以只需一次即可。128.有关二叉树下列说法正确的是()。A、二叉树的度为2B、一棵二树的度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任何一个结点的度都为2答案：B解析：二叉树的特点是每个结点至多有两棵子树，即不存在度大于2的结点。B项是说可以小于2，符合二叉树的特点。129.A、AB、BC、CD、D答案：D解析：130.A、O(m×n×t)B、O(m+n+t)C、O(m×t+n)D、O(m+n×t)答案：A解析：在程序段中，有两段循环程序，第一段是一个双层嵌套循环，另一个是三层嵌套循环，所以基本操作是c[i][j]=c[i][j]+a[i][k]×b[k][j]，此基本操作共执行m×t×n次。131.下面关于求关键路径的说法不正确的是()。A、求关键路径是以拓扑排序为基础的B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D、关键活动一一定位于关键路径上答案：C解析：最迟开始时间应等于本工作的最迟完成时间与其持续时间之差。132.下列排序算法中，()算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A、堆排序B、冒泡排序C、快速排序D、插入排序答案：D解析：插入排序在最后一个元素被插入时，所有元素都要后移，即在最后一趟开始之前，所有元素都不在其最终的位置上。133.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为()。A、aedfcbB、aedfbcC、aebcfdD、acfebd答案：A解析：134.A、AB、BC、CD、D答案：C解析：135.引入二叉线索树的目的是()。A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便地进行插入与删除C、为了能方便地找到双亲D、使二叉树的遍历结果唯一答案：A解析：当以二叉链表作为存储结构存储非线索化的二叉树时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一遍历序列中的直接前驱和直接后继的结点信息，这种信息只有在遍历的动态过程中才能得到。二叉线索树利用空链域存放结点的前驱和后继结点的信息，这样能保存遍历过程中得到的信息。可见，引入二叉线索树的目的是方便查找结点的前驱或后继结点的速度。136.设用数组A[1，n]作为两个栈S1、S2的共用存储空间，对任一个栈，只有当数组A[1，n]全满时才不作入栈操作，则分配这两个栈空间的最佳方案是()。A、S1的栈底位置设为1，S2的栈底位置设为nB、S1的栈底位置设为n/2，S2的栈底位置设为n/2+1C、S1的栈底位置设为1，S2的栈底位置设为n/2D、S1的栈底位置设为n/2，S2的栈底位置设为1答案：A解析：由于栈中元素个数不固定，因此如果将栈底设在中间位置，固定了栈中元素的个数，不能满足只有当数组全满时才不作入栈操作的要求。137.以下说法正确的是()。A、数据结构的逻辑结构是指数据的各数据项之间的逻辑关系。B、数据元素是数据结构的最小单位。C、数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。D、判断某个算法是否容易阅读是算法分析的任务之一。答案：C解析：A项，数据结构的逻辑结构是指数据的各数据元素之间的逻辑关系，而不是数据项之间的逻辑关系。B项，数据元素是数据结构的基本单位，数据结构的最小单位是数据项。D项，算法分析是一个软件的验证确认任务，用于保证选择的算法是正确的、合适的和稳定的，并且满足所有精确性、规模和时间方面的要求，保证产品高质量高效率的运行。容易阅读是增加算法的可读性，不是算法分析的任务。138.下面几个符号串编码集合中，不是前缀编码的是()。A、{0，10，110，1111}B、{11，10，001，101，0001}C、{00，010，0110，1000}D、{b，c，aa，aba，abb，abc}答案：B解析：前缀编码的定义：任一个字符的编码都不是另一个字符的编码的前缀。B选项中10是101的前缀，因此其不是前缀编码。139.在单链表中，指针p指向结点A，若要删除A之后的结点(存在)，则指针的操作方式为()。A、p—＞next=p—＞next—＞nextB、p=p—＞nextC、p=p—＞next—＞nextD、p-＞next-p答案：A解析：要在单链表中删除p指向的结点的后继结点，需要将后继结点的后继交给p所指结点的指铲域。具体实现语句为p—＞next=p—＞next—＞next。140.设有广义表D(a，b，D)，其长度为3，深度为()A、∞B、3C、2D、5答案：A解析：长度为3，但是因第三个元素是一个广义表，所以深度为无穷。141.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是()。A、M1B、M1+M2C、M3D、M2+M3答案：D解析：森林转换成二叉树的原则：将第一棵树的根结点作为根结点，所有结点的第一个左孩子作为左孩子，下一个兄弟结点作为右孩子，其它树作为第一棵树的右孩子。所以森林F对应的二叉树根结点的右子树上的结点个数是M2+M3。142.设某棵二叉树中有2000个结点，则该二叉树的最小高度为()。A、12B、10C、11D、9答案：C解析：想使二叉树的高度最小，即为完全二叉树的时候，所以高度最小为11。143.有六个元素6，5，4，3，2，1的顺序进栈.下列选项中，()不是合法的出栈序列。A、543612B、453126C、346521D、234156答案：C解析：根据栈的后进先出的特点，对于C选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，有根据入站顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出栈。144.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是()。A、栈B、线性表C、队列D、二叉排序树答案：A解析：栈(stack)又称为堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素称作出栈或退栈，它是把栈顶元素删除，使其相邻的元素成为新的栈顶元素。145.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中，第一棵树的结点个数是()。A、m-nB、m-n-1C、n+1D、条件不足，无法确定答案：A解析：森林转换成二叉树的原则：将第一棵树的根结点作为根结点，所有结点的第一个左孩子作为左孩子，下一个兄弟结点作为右孩子，其它树作为第一棵树的右孩子。所以森林F中第一棵树的结点个数是m-n。146.A、AB、BC、CD、D答案：A解析：147.用P代表入栈，O代表出栈。栈的初始状态和最终状态都为空，则下列栈操作正确的是()。A、POOPOOPPB、POPOPOOPC、PPPOOOPPD、PPPOOPOO答案：D解析：AB两项，均会出现下溢，即出栈时栈为空。C项，导致出现最终状态不为空。148.以下有关算法的说法错误的是()。Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间；Ⅱ，在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法；Ⅲ.所谓最坏时间复杂度是指最坏情况下估算算法执行时间的一个上界；Ⅳ，同一个算法，实现语言的级别越高，执行效率就越低。A、ⅠB、Ⅰ和ⅡC、Ⅰ和ⅣD、Ⅲ答案：C解析：算法原地工作的含义是指算法的空间复杂度为O(1)，同一个算法实现语言的级别越高执行效率并不一定越低。149.A、(1)B、(1)、(2)C、(1)、(4)D、(3)答案：C解析：(1)项，原地工作不是不需要额外空间，而是额外空间相对于问题的规模(输入数据量)来说是个常数，那么我们就称之为原地工作。(4)项，这个结论不是绝对的，要看具体情况而定，一般情况下是这样的。150.一棵有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中的位置。151.循环链表的主要优点是()。A、不再需要头指针B、已知某个结点的位置后，能很容易找到它的直接前驱结点C、在进行删除操作后，能保证链表不断开D、从表中任一结点出发都能遍历整个链表答案：D解析：A项，头指针不能省略，因为没有头指针就没有办法引用该链表了；B项，循环链表还是单链表，要找到直接前驱结点，必须至少循环遍历整个链表一次才行；C项，无论链表是不是循环的，都能保证在删除时链表不断开；D项，因为循环链表首尾相接，形成一个环，从循环链表中任何一个结点开始都能遍历整个链表。152.下列说法不正确的是()。A、图的遍历是从给定的源点出发每一个顶点仅被访问一次B、遍历的基本算法有两种：深度遍历和广度遍历C、图的深度遍历不适用于有向图D、图的深度遍历是一个递归过程答案：C解析：图的遍历是指从给定图中任意指定的顶点出发，按照某种搜索方法沿着图的边访问图中的所有顶点，便每个丁贞点仅被访问一次。遍历的基本算法有两种：深度遍历和厂度遍历。图的深度遍历是一个递归过程，既适用于无向图，也适用于有向图。153.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用()存储方式最节省时间。A、顺序表B、双链表C、带头结点的双循环链表D、单循环链表答案：A解析：在线性表的顺序存储中，可以存取任一指定序号的元素。当插入和删除运算是在最后操作时，顺序表的实现也非常方便。BCD三项都不同时具备这两个特点。154.对于栈操作数据的原则是()。A、先进先出B、后进先出C、后进后出D、不分顺序答案：B解析：栈的特点就是后进先出，入栈和出栈的操作只能在栈顸进行.而队列的特点是先进先出，这两点容易混淆，要注意区分。155.设某棵三叉树中有40个结点，则该三叉树的最小高度为()A、6B、4C、5D、3答案：B解析：树高度最小时即为每一层都是满的，只有最下层不满的情况是树的高度最小的情况。156.由圈权值为9.2.5.7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为()。A、23B、37C、44D、46答案：C解析：157.已知二叉树的前序序列为ABCDEFG，中序序列为DBCAFEG，则后序序列为()。A、DCBAFGEB、DCBFGEAC、DCBFEGAD、DCBGFEA答案：B解析：本题考查的是二叉树的遍历过程。在本题中，由于前序遍历首先访问的是根结点，所以根结点是A，又由于后序遍历最后访问的是根结点，所以排除选项A；根据中序序列知道，DBC是左子树的结点，FEG是右子树的结点。158.设n阶方阵是一个上三角矩阵，则需存储的元素个数为()。A、nB、n×nC、n×n/2D、n(n+1)/2答案：D解析：在上三角矩阵中，第一行有1个元素，第二行有2个元素，…，第n行有n个元素，则共n(n+1)/2个。159.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有()个结点。A、13B、12C、26D、25答案：D解析：哈夫曼树的特点：具有n个叶子结点的哈夫曼树共有2×n-1个结点。160.下面术语中，与数据的存储结构无关的是()。A、循环队列B、栈C、散列表D、单链表答案：B解析：只有栈是逻辑结构，其他选项都是存储结构(或物理结构)。161.以下排序方法中，在初始序列已基本有序的情况下，排序效率最高的是()。A、归并排序B、直接插入排序C、快速排序D、堆排序答案：B解析：直接插入排序对于基本有序的序列进行排序效率最高。162.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为()。A、9，5，3B、9，5，2，3C、1，2，3D、9，4，2，3答案：D解析：二分查找的基本思想是将n个元素分成大致相等的两部分，取中间位置的节点值与关键字做比较，如果相等，则查找成功；如果关键字的值小于中间节点，则只要在数组的左半部分继续搜索，重复与中间值进行比较，直至查找成功或失败；如果关键字大于中间值，则只要在数组的右半部搜索即可。163.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为()。A、AB、BC、CD、D答案：D解析：164.下列排序算法中，在待排序数据已有序时，花费时间反而最多的排序是()。A、冒泡B、希尔C、快速D、堆答案：C解析：在待排序数据已有序时，快速排序会退化为冒泡排序，时间复杂度为O(n)。165.已知有向图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解析：166.线性表的静态链表存储结构与顺序存储结构相比优点是()。A、所有的操作算法实现简单B、便于随机存取C、便于插入与删除D、便于利用零散的存储器空间答案：C解析：基础题。静态链表具有链表的插入和删除方便的优点，也不需要移动较多的元素。167.将10个元素散列到100000个单元的哈希表中，()产生冲突？A、一定会B、一定不会C、仍可能会D、可能不会答案：C解析：168.设某完全无向图中有n个顶点，则该完全无向图中有()条边。A、n(n-1)/2B、n(n-1)C、n+1D、n答案：A解析：因为无向图的边是没有方向的，所以完全无向图有n(n-l)/2条边。169.若一个栈以向量V[1.n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是()。A、top=top+1；V[top]=xB、V[top]=x；top=top+1C、top=top-1；V[top]=xD、V[top]=x；top=top-1答案：C解析：栈是运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行人栈操作时top指针应该进行减1操作。通常元素进栈的操作为：先移动栈顶指针后存入元素。170.A、AB、BC、CD、D答案：C解析：171.下列序列中，满足堆定义的是()。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项对应的是大顶堆，满足大顶堆性质。172.适用于折半查找的表的存储方式及元素排列要求为()。A、链接方式存储，元素无序B、链接方式存储，元素有序C、顺序方式存储，元素无序D、顺序方式存储，元素有序答案：D解析：折半查找的线性表中的结点必须已按关键字值的递增或递减顺序排列，而且为顺序存储。173.二路归并排序的时间复杂度为()。A、AB、BC、CD、D答案：C解析：174.一棵完全二叉树上有1001个结点.其中叶子结点的个数是()。A、250B、500C、505D、501答案：D解析：175.散列技术中的冲突指的是()。A、两个元素具有相同的序号B、数据元素过多C、两个元素的键值不同，而其他属性相同D、不同键值的元素对应于相同的存储地址答案：D解析：散列技术中的冲突指的是不同键值的元素对应于相同的存储地址。176.对任意7个关键字进行排序，至少要进行()次关键字之间的两两比较。A、13B、14C、15D、16答案：C解析：177.下列的叙述不正确的个数是()。(1)9阶B-树，除根以外的任一结点的关键字个数不少于4(2)理想情况下，在散列表中查找一个元素的时间复杂度为0(1)(3)在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻(4)在索引顺序表的查找中，对索引表既可以采用顺序查找方法，也可采用=分查找方法A、1B、2C、3D、4答案：A解析：如果发生多次冲突，则同义词在表中就不会相邻，因此(3)是错误的，其它正确。178.A、AB、BC、CD、D答案：A解析：179.与单链表相比，双链表的优点之一是()。A、插入、删除操作更简单B、可以进行随机访问C、可以省略表头指针或表尾指针D、访问前后相邻结点更灵活答案：D解析：对于插入、删除操作单链表更简单，因为需要改动的指针域少，而随机访问是顺序表的特点。无论是单链表还是双链表都要有表头指针或表尾指针，在双链表中可以访问任一结点的前后相邻结点，而单链表中只能访问任意结点的后继结点。180.数据的存储结构是指()。A、数组类型B、指针类型C、数据之间的逻辑关系D、数据之间的物理关系答案：D解析：数据的存储结构就是物理结构，指数据之间的物理关系。181.下列叙述中，不符合m阶B树定义要求的是()。A、根节点最多有m棵子树B、所有叶结点都在同一层上C、各结点内关键字均升序或降序排列D、叶结点之间通过指针链接答案：D解析：B树的定义。182.设某哈夫曼树中有199个结点，则该哈夫曼树中有()个叶子结点。A、101B、100C、99D、102答案：B解析：在哈夫曼树中的结点只有两种，一种是度为零的结点，另一种是度为1的结点。183.下面关于工程计划的AOE网的叙述中，不正确的是()。A、某些关键活动若提前完成，那么整个工程将会提前完B、关键活动不按期完成就会影响整个工程的完成时间C、任何一个关键活动提前完成，那么整个工程将会提前完成D、所有的关键活动都提前完成，那么整个工程将会提前完成答案：C解析：AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，则必须同时提高在几条关键路径上的关键活动。184.若将数据结构中的数据元素称为结点，则一般没有开始结点和终端结点的数据结构是()。A、树B、图C、多维数组D、线性表答案：B解析：图G由两个集合V和E组成，记为G=(V，E)。其中V是顶点的有限集合，记为V((G)；E是连接V中两个不同顶点(顶点对)的边的有限集合，记为E(G)。图是由有限集合的顶点和边构成，没有开始结点和终端结点。185.在线索二叉树中，一个结点是叶子结点的充要条件为()。A、左、右线索标志均为0B、左、右线索标志均为1C、左线索标志为0，右线索标志为1D、左线索标志为1，右线索标志为O答案：A解析：一个结点是叶子结点的充要条件是没有左孩子，并且没有右孩子。186.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是()。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孙答案：C解析：中序遍历时，先访问左子树，再访问根结点。n在m前，则n必须在m的左子树中。187.二叉排序树中左子树上所有结点的值均()根结点的值。A、＜B、=C、＞D、！=答案：A解析：二叉排序树的左子树的结点的值全部小于根结点的值，并且根结点的值小于右子树左右结点的值。188.下列与数据元素有关的叙述中，哪一项是不正确的()。A、数据元素是数据的基本单位，即数据集合中的个体B、数据元素是由独立含义的数据最小单位C、数据元素又称为节点D、数据元素又称为记录答案：B解析：数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为节点、记录、表目等。一个数据元素可由一个或多个数据项组成，数据项是由独立含义的数据最小单位。189.设有一组记录的关键字为{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个记录。190.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为()。A、q=p-＞next；p-＞data=q-＞data；p-＞next=q-＞next；free(q)；B、q=p-＞next；p-＞data=q-＞data；free(q)；C、q=p-＞next；p-＞next=q-＞next；free(q)；D、q=p-＞next；q-＞data=p-＞data；p-＞next=q-＞next；free(q)；答案：A解析：应先使指针q指向结点A之后的结点，以防链表断裂，然后删除结点q，最后将删除的结点q的存储空间释放。191.下列说法正确的是()。A、任何有向网络(AOV-网)拓扑排序的结果是唯一的B、有回路的图不能进行拓扑排序C、在AOE网中一定只有一条关键路径D、一个正常的AOE网中只能有一个源点、一小汇点和一条关键路径答案：B解析：拓扑排序的结果不一定是唯一的；在AOE网中，关键路径不止一条。192.下列排序方法中，属于不稳定的排序方法的是()。A、直接插入排序法B、冒泡排序法C、基数排序法D、堆排序法答案：D解析：本题选项所述的四种排序方法中，只有堆排序是不稳定的。193.假设执行语句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)。194.设循环队列的存储空间为Q(1：30)，初始状态front=rear=30，先经过一系列入队和退队运算后，front=10，rear=10，则循环队列中的元素个数为()。A、30B、0C、29D、0或30答案：D解析：当frontrear时，循环队列中的元素个数为N-front+rear(N为循环队列容量)。当front=rear时，循环队列中的元素个数可能为空，也可能为满。195.采用分块查找时.若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分()个结点最佳。A、10B、25C、6D、625答案：B解析：196.判定一个栈ST(最多元素为m0)为满的条件是()。A、ST-＞top=m0-1B、ST-＞top=0C、ST-＞top＜＞m0D、ST-＞top＜＞0答案：A解析：如果一个栈的栈顶指针为m0-1，则该栈为满。197.下面关于图的存储的叙述中，正确的是()。A、用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关B、用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关C、用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D、用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关答案：A解析：对于n个节点的图来说，用邻接矩阵法存储图，需要n×n个存储单元，只与图中结点个数有关，与边数无关；用邻接表法存储图，与图的结点个数和边数都有关。198.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有()条有向边。A、n-1B、nC、m-1D、m答案：B解析：邻接表的表头结点个数即为图中结点的个数。199.A、AB、BC、CD、D答案：D解析：考查双链表中插入操作，要注意保存后继节点。200.占用的额外空间的空间复杂度为0(1)的排序算法是()。A、堆排序算法B、归并排序算法C、快速排序算法D、以上答案都不对答案：A解析：归并排序中，由于每一趟都要一个TR数组来复制，因此需要与待排记录等量的辅助空间O(n)；而快速排序中的递归所耗费的栈空间最好情况下也要O(logn)；堆排序仅在交换是需要一个记录的辅助空间。201.()不是算法的基本特性。A、可行性B、长度有限C、在规定的时间内完成D、确定性答案：B解析：算法的5个重要特性：①确定性；②有穷性；③可行性；④输入；⑤输出。C项指的是有穷性，而有穷性并不是指长度有限，而是指执行的时间是有限的。202.G是一个非连通无向图，共有28条边，则该图至少有()个顶点。A、8B、9C、6D、7答案：B解析：n个顶点的无向图中，边数e≤n(n-l)/2，将e=28代入，有n≥8，现已知无向图非连通，则n=9。203.某高度为k的完全二叉树中，所含叶子结点的个数最少为()。A、AB、BC、CD、D答案：C解析：204.简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结