国家电网招聘考试计算机类专业知识（数据结构与算法）模拟试卷5

国家电网招聘考试计算机类专业知识（数据结构与算法）模拟试卷5一、单项选择题(本题共30题，每题1.0分，共30分。)1、设无向图G中的边的集合E={(a,b)，(a,e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为()。A、aedfcbB、aedfbcC、aebcfdD、acfebd标准答案：A知识点解析：根据题干描述，可画出无向图如下：B项中，aedf之后下一个遍历顶点为c，而不是b；C项中，aeb之后应该回溯到顶点e，下一个遍历顶点为d，而不是c；D项中，acf之后下一个遍历顶点为d，而不是e。2、广义表((a，(b，c))，d,e)的表头是()。A、aB、(a)C、(b，c)D、(a，(b，c))标准答案：D知识点解析：广义表中的第一个元素为表头，其他元素组成的表为表尾，故本题中的广义表的表头为(a，(b，c))。3、设一个顺序有序表A[1．．14]中有14个元素，则采用二分查找法查找元素A[4]的过程中，比较元素的顺序为()。A、A[7],A[5],A[3],A[4]B、A[1],A[1A],A[7],A[4]C、A[7],A[3],A[5],A[4]D、A[1],A[2],A[3],A[4]标准答案：C知识点解析：二分查找法每次都与中间值进行比较。4、下列关于栈和队列的叙述，错误的是()。A、栈可以为空B、栈的使用原则是先进后出C、可以用顺序存储的线性表来表示队列D、根据循环队列的头指针与尾指针是否相等，可判断循环队列是否为空标准答案：D知识点解析：当栈中没有元素时，称为空栈。栈的使用原则是后进先出，也就是先进后出。可以用顺序存储的线性表来表示队列，通常还会添加队头指针和队尾指针。不能仅根据循环队列的队头指针与队尾指针是否相等判断循环队列是否为空，队头指针与队尾指针相等，循环队列可能为空，也可能为满。5、设一棵三叉树中有2个度为1的节点，2个度为2的节点，2个度为3的节点，则该三叉树中有()个度为0的节点。A、8B、6C、7D、5标准答案：C知识点解析：设度为0的节点数为n，根据树中节点总数与总度数的关系可列方程为2+2+2+n=2×1+2×2+2×3+n×0+1，解得n=7。6、下列排序方法中，比较次数与待排序记录的初始状态无关的是()。A、选择排序和归并排序B、插入排序和归并排序C、插入排序和快速排序D、归并排序和快速排序标准答案：A知识点解析：选择排序在最好、最坏、平均情况下的时间复杂度均为O(n2)，归并排序在最好、最坏、平均情况下的时间复杂度均为O(logn)。7、设有5000个元素，希望用最快的速度挑选出前10个最大的元素，采用()方法最好。A、希尔排序B、归并排序C、快速排序D、堆排序标准答案：D知识点解析：堆排序不必将整个序列排序即可确定前若干个最大(或最小)元素。8、已知一个有序表为(12，18，24，35，47，50，62，83，90，115，134)，当折半查找值为90的元素时，经过()次比较后查找成功。A、2B、3C、4D、5标准答案：A知识点解析：根据二分查找法进行查找，第1次将90与表中中间元素50进行比较，由于90大于50，所以在线性表的后半部分查找；第2次与90比较的元素是后半部分的中间元素，即90，这时两者相等，即查找成功。9、已知10个元素(54，28，16，34，73，62，95，60，26，43)，按照依次插入的方法生成一棵二叉排序树，查找值为62的节点所需要的比较次数为()。A、2B、3C、4D、5标准答案：B知识点解析：根据题干描述，可画出二叉排序树如下：在该二叉排序树中查找值为62的节点，从根节点开始，将62与54进行比较，由于62大于54，所以在根节点的右子树中查找；将62与73进行比较，由于62小于73，所以在值为73的节点的左子树中查找；将62与62进行比较，由于62等于62，查找成功。因此，查找值为62的节点所需要比较的次数为3。10、已知数据元素为(34，76，45，18，26，54，92，65)，按照依次插入节点的方法生成一棵二叉排序树，则该树的深度为()。A、6B、7C、4D、5标准答案：D知识点解析：根据题干描述，可画出二叉排序树如下：该二叉排序树的最大层次为5，因此深度为5。11、在平衡二叉树中，节点的平衡因子的绝对值不超过()。A、1B、2C、3D、4标准答案：A知识点解析：在平衡二叉树中，任一节点的平衡因子的可能取值为－1、0和1，故其绝对值不超过1。12、二叉排序树中，最小值节点的()。A、左、右指针均为空B、左、右指针均不为空C、左指针一定为空D、右指针一定为空标准答案：C知识点解析：在二叉排序树中，最小值节点一定是中序遍历序列中第一个被访问的节点，即二叉排序树的最左下方节点，该节点的左指针一定为空。13、散列技术中的冲突是指()。A、两个元素具有相同的序号B、数据元素过多C、两个元素的键值不同，而其他属性相同D、不同键值的元素对应相同的存储地址标准答案：D知识点解析：暂无解析14、设散列表表长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。15、判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用()。A、广度优先遍历算法B、深度优先遍历算法C、求关键路径的方法D、求最短路径的方法标准答案：B知识点解析：当有向图中无回路时，从某顶点出发进行深度优先遍历，出栈的顺序即为逆向的拓扑序列。16、下列关于工程计划的AOE网络的叙述，不正确的是()。A、某些关键活动若提前完成，那么整个工程将会提前完成B、关键活动不按期完成就会影响整个工程的完成时间C、任何一个关键活动提前完成，那么整个工程将会提前完成D、所有的关键活动都提前完成，那么整个工程将会提前完成标准答案：C知识点解析：AOE网络中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前完成整个工程，则必须同时提前完成在几条关键路径上的关键活动。17、某无向图的邻接矩阵A=，可以看出，该图共有()个顶点。A、3B、6C、9D、12标准答案：A知识点解析：邻接矩阵是表示顶点之间邻接关系的矩阵。设G=(V,E)是具有n个顶点的图，顶点序号依次为1，2，…，n，则G的邻接矩阵是n阶方阵，所以该图有3个顶点。18、无向图的邻接矩阵是一个()。A、对称矩阵B、无规律矩阵C、上三角矩阵D、下三角矩阵标准答案：A知识点解析：在无向图的邻接矩阵中，两个顶点邻接是相互的，即l和2邻接，则2和1也邻接，因此无向图的邻接矩阵是一个对称矩阵。19、下列叙述正确的是()。A、一个图的邻接矩阵表示是不唯一的，邻接表表示也是不唯一的B、一个图的邻接矩阵表示是唯一的，邻接表表示也是唯一的C、一个图的邻接矩阵表示是唯一的，邻接表表示不是唯一的D、一个图的邻接矩阵表示是不唯一的，邻接表表示是唯一的标准答案：C知识点解析：暂无解析20、关键路径是AOE网络中()。A、最长的回路B、最短的回路C、从源点到终点的最长路径D、从源点到终点的最短路径标准答案：C知识点解析：在AOE网络中，从源点到终点具有最大路径长度的路径称为关键路径。关键路径的工期是指关键路径上的各个活动所持续的时间之和，它决定了整个项目的最短工期。21、静态查找与动态查找的根本区别在于()。A、所包含的数据元素的类型不一样B、存储实现方式不一样C、逻辑结构不一样D、施加在其上的操作不一样标准答案：D知识点解析：静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。22、假定一棵度为3的树中的节点个数为50，则其最小高度应为()。A、5B、6C、3D、4标准答案：A知识点解析：节点数相同而高度最小的三叉树是满三叉树或完全三叉树(深度为h的三叉树，若前h一1层是满的，只有第h层从右边起，连续缺若干个节点的三叉树称为完全三叉树)。设根节点的层次为1，则第1层有1个节点，第2层最多有3个节点，第3层最多有9个节点，第4层最多有27个节点，第5层最多有81个节点，1+3+9+27=40＜50，1+3+9+27+81=121＞50，因此最小高度为5。23、在线索二叉树中，一个节点是叶节点的充要条件是()。A、左、右线索标志均为0B、左、右线索标志均为1C、左线索标志为0，右线索标志为1D、左线索标志为1，右线索标志为0标准答案：B知识点解析：一个节点是叶节点的充要条件是没有左孩子节点，并且没有右孩子节点。24、含n个顶点的连通图中的任意一条简单路径，其长度不可能超过()。A、n－1B、nC、1D、n／2标准答案：A知识点解析：若简单路径的长度超过n一1，则路径中必存在重复的顶点。25、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是()。A、nB、(n－1)2C、n－1D、n2标准答案：D知识点解析：暂无解析26、设无向图G=(V，E)和G′=(V′，E′)，如果G′是G的生成树，则下列说法错误的是()。A、G′为G的极小连通子图，且V=V′B、G′为G的一个无环子图C、G′为G的子图D、G′为G的连通分量标准答案：D知识点解析：由于G＇为G的生成树，因此G＇为G的极小连通子图，包含G中所有的顶点，即V=V＇；如果G中有n个顶点，则G＇由n一1条边构成，因此不存在回路，G＇为G的无环子图。连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，因此连通分量中可能存在回路。27、G是一个非连通无向图，共有28条边，则该图至少有()个顶点。A、8B、9C、6D、7标准答案：B知识点解析：在含有n个顶点的无向图中，边数e≤n(n－1)／2，将e=28代入，得n≥8，现已知无向图非连通，则该图至少有9个顶点。28、线索二叉树中某节点R没有左孩子节点的充要条件是()。A、R．1tag=1B、R．rchild=NULLC、R．1child=NULLD、R．1tag=0标准答案：A知识点解析：线索二叉树中某节点是否有左孩子节点，不能通过左指针域lchild是否为空来判断，而要判断左标志1tag是否为1。29、讨论树、森林和二叉树的关系，目的是()。A、借助二叉树上的运算方法去实现对树的一些运算B、将树