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

国家电网招聘考试计算机类专业知识（数据结构与算法）模拟试卷4一、单项选择题(本题共32题，每题1.0分，共32分。)1、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为()。A、第i列0元素的个数B、第i列非0元素的个数C、第i行0元素的个数D、第i行非0元素的个数标准答案：B知识点解析：在有向图的邻接矩阵中，第i行非0元素的个数即为顶点i的出度，第i列非0元素的个数即为顶点i的入度。2、执行一趟排序结束后不一定能够选出一个元素放在其最终位置上的是()。A、冒泡排序B、堆排序C、快速排序D、希尔排序标准答案：D知识点解析：冒泡排序每趟选出一个最值移至序列的一端；堆排序和快速排序的一趟排序可以使选出的基准值移至最终位置。3、一个栈的初始状态为空，现有一个入栈序列ABCDEF，则不可能的出栈序列是()。A、ABCDEFB、FEDCBAC、ABCEDFD、ABCFDE标准答案：D知识点解析：栈的特点是元素后进先出。A、B、C三项的出栈序列均可能发生。D项中的F出栈时，表明D和E已经入栈，而二者中后入栈的是E，因此不可能出现D比E先出栈的情况。4、顺序查找不论在顺序线性表中，还是在链式线性表中，时间复杂度都为()。A、O(n－1)B、O(n)C、O(n+1)D、O(log2n)标准答案：B知识点解析：无论是顺序存储还是链式存储，使用顺序查找法的时间复杂度相同，都为O(n)。5、二路归并排序的时间复杂度为()。A、O(n－1)B、O(n)C、O(nlog2n)D、O(log2n)标准答案：C知识点解析：暂无解析6、深度为k的完全二叉树中最少有()个节点。A、2k－1－1B、2k－1－1C、2k－1D、2k标准答案：C知识点解析：当第k层只有最左边一个节点时，完全二叉树具有最少的节点，因此最少的节点个数为2k－1－1+1=2k－1。7、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队的节点X，则入队的操作序列为()。A、s－＞next=rear；rear=s；B、front－＞next=s；front=s；C、real－＞next=s；rear=s；D、s－＞next=front；front=s；标准答案：C知识点解析：向队列插入元素，即入队操作，应该在队尾进行，所以需要修改队尾指针，实现新节点的入队操作。8、下列关于数组的叙述，正确的是()。A、数组大小是固定的，可以有不同类型的数组元素B、数组大小是可变的，所有数组元素的类型必须相同C、数组大小是固定的，所有数组元素的类型必须相同D、数组大小是可变的，可以有不同类型的数组元素标准答案：C知识点解析：数组的定义强调，在声明数组时需要确定数组大小，因此数组大小是固定的，并且数组中的元素必须是相同的数据类型。9、设某哈夫曼树中有199个节点，则该哈夫曼树中有()个叶节点。A、101B、100C、99D、102标准答案：B知识点解析：哈夫曼树中的节点只有两种，一种是度为0的节点，另一种是度为2的节点。由于哈夫曼树是二叉树，因此可列方程组n2=n0－1，n0+n2=199，解得n0=100。10、下列程序段的时间复杂度为()。for(i=0；i＜m；i++)for(j=0；j＜t；j++)c[i][j]=0；for(i=0；i＜m；i++)for(j=0；j＜t；j++)for(k=0；k＜n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；A、O(m×n×t)B、O(m+n+t)C、O(m×t+n)D、O(m+nxt)标准答案：A知识点解析：在本题的程序段中，有两段循环程序，一段是一个双层嵌套循环，另一段是一个三层嵌套循环，所以基本操作是c[i][j]=c[i][j]+a[i][k]*b[k][j]，此基本操作共执行m×t×n次。11、设有序表中的元素为13，18，24，35，47，50，62，则在其中利用二分查找法查找值为24的元素需要经过()次比较。A、4B、2C、3D、1标准答案：C知识点解析：二分查找法的每一次查找都要与中间值进行比较。24第1次与35进行比较，24小于35，接下来在35的左半部分中进行查找，左半部分的中间值为18；24第2次与18进行比较，24大于18，接下来在18的右半部分中进行查找；24第3次与24进行比较，此时查找成功，共比较了3次。12、设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的节点数分别为N1、N2和N3，则二叉树B的根节点的左子树的节点个数为()。A、N1－1B、N2+N3C、N2－1D、N1+N3标准答案：A知识点解析：由森林转换为二叉树，利用的是树转换为二叉树时，二叉树根节点的右子树始终为空的特点。将森林转换为二叉树的过程：先将森林中的每一棵树转换为二叉树，再将第一棵树的根节点作为转换后二叉树的根节点，第一棵树的左子树作为转换后二叉树根节点的左子树，第二棵树作为转换后二叉树根节点的右子树，第三棵树作为转换后二叉树根节点的右子树的右子树，以此类推，通过根节点的兄弟链将各棵树转换成的二叉树链接起来，森林便可以转换为一棵二叉树。因此，二叉树B的根节点的左子树的节点个数为N2－1。13、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为()。A、O(nlog2n)B、O(n+1)C、O(log2n)D、O(n2)标准答案：D知识点解析：暂无解析14、设指针变量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的后继指针。15、将32个元素进行堆排序，则最坏的情况需要比较()次。A、60B、84C、144D、160标准答案：D知识点解析：堆排序的最坏情况需要比较nlog2n次，带人数值计算得，32个元素进行堆排序，最坏的情况需要比较160次。16、设顺序表的长度为n，则顺序查找的平均比较次数为()。A、(n－1)／2B、n／2C、(n+1)／2D、n标准答案：C知识点解析：顺序查找是顺序遍历查找表，直至找到或查找失败，所以最好的情况是第一个节点即想要查找的元素，最坏的情况是查找失败，所以平均比较次数为(n+1)／2。17、设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为()。A、5B、11C、7D、6.5标准答案：D知识点解析：分块查找是先在索引表中进行查找，找到该元素可能存在的块号，然后在块中顺序查找，则本题的平均查找长度为(5+1)／2+(6+1)／2=6．5。18、设有向无环图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知识点解析：根据题干描述，可画出有向图如下：对有向图进行拓扑排序，入度为0的顶点成为可输出的候选顶点，每次选择入度为0的顶点输出，并删除该顶点和其相关联的边，直到所有顶点都已输出，或者剩下的图中不存在入度为0的顶点。因此，该有向图G的拓扑序列是1，2，3，4。19、设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为()。A、4B、6C、5D、7标准答案：A知识点解析：根据题干描述，可画出二叉排序树如下：该二叉排序树的深度为4。20、设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是()。A、A，D，C，R，F，Q，M，S，Y，P，H，XB、P，A，C，S，q，D，F，X，R，H，M，YC、F，H，C，D，P，A，M，Q，R，S，Y，SD、H，C，Q，P，A，M，S，R，D，F，X，Y标准答案：D知识点解析：每一趟冒泡排序都是从第一个记录开始，将相邻的两个记录的关键字进行比较，若是降序则进行交换，一趟排序完成后，关键字最大的记录被移至序列的末尾。21、由同一关键字集合构造的各棵二叉排序树，()。A、其形态不一定相同，但平均查找长度相同B、其形态不一定相同，平均查找长度也不一定相同C、其形态都相同，但平均查找长度不一定相同D、其形态都相同，平均查找长度也相同标准答案：B知识点解析：由同一关键字集合构造的各棵二叉排序树，由于关键字插入的顺序不一定相同，所以其形态不一定相同，平均查找长度也不一定相同。22、设指针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知识点解析：插入节点X，应使节点A的next域指向节点X，使节点X的next域指向节点B。23、下列关于线性表的叙述，错误的是()。A、线性表中的每个节点有且仅有一个后继节点B、非空线性表只有一个根节点C、线性表通常采用顺序存储和链式存储两种结构D、线性表是有限序列标准答案：A知识点解析：在线性表中，除了最后一个节点外，其他节点有且仅有一个后继节点；除了第一个节点外，其他节点有且仅有一个前趋节点。24、设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]与A[0][0]的地址之差为()。A、55B、19C、28D、10标准答案：B知识点解析：行优先压缩存储下三角矩阵，元素A[i][j]阴在数组中的存放位置为(i+1)×i／2+j，因此A[5][4]的存放位置是19，A[0][0]的存放位置是0，地址相差为19。25、设一组初始记录关键字的长度为8，则最多经过()趟插入排序可以得到有序序列。A、8B、7C、9D、6标准答案：B知识点解析：插入排序的每一趟将待排序的记录按其关键字大小插入到前面已经排好序的有序序列的适当位置，直到记录全部插入为止。所以共8个关键字的序列，最多经过7趟插入排序就可以得到一个有序序列。26、二叉排序树中左子树上所有节点的值均()根节点的值。A、小于B、等于C、大于D、大于或等于标准答案：A知识点解析：二叉排序树的左子树所有节点的值都小于根节点的值，并且根节点的值都小于右子树所有节点的值。27、设一组权值集合W={15，3，14，2，6，9，16，17}，要求根据这一权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为()。A、219B、129C、189D、229标准答案：D知识点解析：根据题干描述，可画出哈夫曼树如下：则其带权路径长度=17×2+16×2+15×3+14×3+9×3+6×4+3×5+2×5=229。28、设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中，需要做()次线性探测。A、n(n+1)B、nC、n(n+1)／2D、n(n－1]／2标准答案：D知识点解析：线性探测法解决冲突的办法是一旦目标空间被占有，则探测相邻的下一个空间，如果空闲则插入，否则继续向下一个探测，如果到了Hash表末尾则返回Hash表开头进行探测，一旦全部空间都被占据，则无法插入。第一个关键字映射到Hash表时插入成功，从第二个关键字开始出现冲突，第二个关键字映射时做1次线性探测，第三个关键字映射时做2次线性探测，以此类推，第n个关键字映射时做n－1次线性探测，因此共需要做n(n－1)／2次线性探测。29、设某棵二叉树中只有度为0和度为2的节点，且度为O的节点数为n，则这棵二叉树中共有()个节点。A、2n+1B、n+1C、2n－1D、2n标准答案：C知识点解析：在二叉树中，度为2的节点数等于度为0的节点数减1，所以二叉树共有2n－1个节点。30、下列叙述正确的是()。A、线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B、线性表的链式存储结构所需要的存储空间一般多于顺序存储结构C、线性表的链式存储结构所需要的存储空间一般少于顺序存储结构D、线性表的链式存储结构与顺序存储结构在存储空间的需求上没有可比性标准答案：B知识点解析：线性表的链式存储结构中的每个节点都是由数据域和指针域两个部分组成的