文档介绍：该【国家二级ACCESS机试选择题(公共基础知识)模拟试卷3(题后含答案及解析 】是由【小屁孩】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【国家二级ACCESS机试选择题(公共基础知识)模拟试卷3(题后含答案及解析 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..ESS机试选择题(公共基础知识)模拟试卷3(题后含答案及解析)题型有:()。,,,在操作过程中其栈底指针均是固定不变的正确答案:A解析:由于带链栈利用的是计算机存储空间中的所有空闲存储结点,因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素,则头指针与尾指针相同。知识模块:=bottom=NULL,经过一系列正常的入栈与退栈操作后,top=bottom=20,该栈中的元素个数为()。:B解析:带链的栈就是用一个单链表来表示的栈,栈中的每一个元素对应链表中的一个结点。栈为空时,头指针和尾指针都为NULL;栈中只有一个元素时,头指针和尾指针都指向这个元素。知识模块:=bottom=NULL,经过一系列正常的入栈与退栈操作后,top=10,bottom=20。该栈中的元素个数为()。:D解析:带链的栈使用了链表来表示栈,而链表中的元素存储在不连续的地址中,因此当top=10,bottom=20时,不能确定栈中元素的个数。知识模块:公共基础知识:..=rear=NULL。经过一系列正常的入队与退队操作后,front=rear=10。该队列中的元素个数为()。:B解析:带链队列空时,头指针和尾指针都为NULL;队列中只有一个元素时,头指针和尾指针都指向这个元素。知识模块:=rear=NULL。经过一系列正常的入队与退队操作后,front=10,rear=5。该队列中的元素个数为()。:D解析:带链的队列使用了链表来表示队列,而链表中的元素存储在不连续的地址中,因此当front=10,rear=5时,不能确定队列中元素的个数。知识模块:()。:B解析:循环链表是指在单链表的第一个结点前增加一个表头结点,队头指针指向表头结点,最后一个结点的指针域的值由NULL改为指向表头结点。循环链表是线性表的一种链式存储结构,循环队列是队列的一种顺序存储结构。知识模块:,且只有度为3的结点和叶子结点,其中叶子结点有7个,则该树中度为3的结点数为()。:D解析:根据题意,树中只有度为3的结点和叶子结点(7个),则度为3的结:..点有25—7:18个;又根据树中的结点数=树中所有结点的度之和+1,设度为3的结点数为n,则3n+1=25,得n=8。两种方式得到的度为3的结点数不同,故不存在这样的树。知识模块:—,1的结点个数分别为3,4。则该树中的叶子结点数为()。:B解析:设叶子结点数为n,则度为2的结点数为30—3—4—n=23—n,根据树中的结点数=树中所有结点的度之和+1,得3×3+2×(23—n)+1×4+0×n+1=30,则n=15。知识模块:,则下列说法中错误的是()。:B解析:满二叉树满足深度为m的二叉树最多有2n—1个结点,本题中二叉树深度为7且有127个结点,满足27—1=127,达到最大值,故此二叉树为满二叉树,也是完全二叉树。满二叉树第k层上有2k—1结点,则该二叉树的叶子结点数为27—1=64个。满二叉树不存在度为1的结点。知识模块:()。:A解析:设完全二叉树的结点数为n,根据深度为k的二叉树至多有2k—1个结点,再根据完全二叉树的定义可知,2k—1—1<n≤2k—1。本题中完全二叉树的深度为5,则25—1—1<n≤25—1,15<n≤31。因此,结点数不能为15。知识模块:,则该完全二叉树的深度为()。:..:C解析:根据完全二叉树的性质:具有n个结点的完全二叉树的深度为[log:n]+1。本题中完全二叉树共有256个结点,则深度为[log2256]+1=8+1=9。知识模块:,叶子结点个数为()。+—:A解析:由二叉树的定义可知,树中必定存在度为O的结点和度为2的结点,设度为O结点有a个,根据度为0的结点(即叶子结点)总比度为2的结点多一个,得度为2的结点有a—1个。再根据完全二叉树的定义,度为1的结点有0个或1个,假设度1结点为0个,a+0+a—1=2n,得2a=2n—1,由于结点个数必须为整数,假设不成立;当度为1的结点为1个时,a+1+a—1=2n,得a=n,即叶子结点个数为n。知识模块:()。:C解析:在计算机中,二叉树为非线性结构,通常采用链式存储结构,但对于满二叉树和完全二叉树来说,可以按层进行顺序存储。因此A项错误,C项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构,但仍是一种非线性结构,因此D项错误。双向链表也有两个指针域,因此B项错误。知识模块::则前序序列为()。:A解析:前序遍历首先访问根结点,然后遍历左子树,最后遍历右子树;在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。故本:..题前序序列是ABDFGCFH。中序遍历首先遍历左子树,然后访问跟结点,最后遍历右子树;在遍历左、右子树时,仍然先遍历左子树,然后访问跟结点,最后遍历右子树。故本题的中序序列是DBGEAFHC。后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点;在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点。故本题的后序序列是DGEBHFCA。知识模块:,中序序列为DBGEHACIFJ。则后序序列为()。:B解析:二叉树的前序序列为ABDFJGHCFIJ,由于前序遍历首先访问根结点,可以确定该二叉树的根结点是A。再由中序序列为DBGEHACIFJ,可以得到结点D、B、C、E、H位于根结点的左子树上,结点C、I、F、J位于根结点的右子树上。由于中序遍历和后序遍历都是先遍历左子树,故本题后序遍历首先访问D结点;再由后序遍历是最后访问根结点,故本题后序遍历最后访问的结点是根结点A。采用排除法可知,后续序列为DGHEBIJFCA。知识模块:,后序遍历序列为CBEDA,则前序遍历序列为()。:C解析:二叉树的后序遍历序列为CBEDA,由于后序遍历最后访问根结点,可以确定该二叉树的根结点是A。再由中序遍历序列为CBADE,可以得到子序列(CB)一定在左子树中,子序列(DE)一定在右子树中。结点C、B在中序序列和后序序列中顺序未变,说明结点B是结点C的父结点;结点D、E在中序序列和后序序列中顺序相反,说明结点D是结点E的父结点。因此该二叉树的前序遍历序列为ABCDE。知识模块:,中序序列为DCBAEFG,则该二叉树的深度(根结点在第1层)为()。:..正确答案:C解析:二叉树的前序序列为ABCDEFG,则A为根结点;中序序列为DCBAEFG,可知结点D、C、B位于根结点的左子树上,结点E、F、G位于根结点的右子树上。另外,结点B、C、D在前序序列和中序序列中顺序相反,则说明这三个结点依次位于前一个结点的左子树上;结点E、F、G顺序未变,则说明这三个结点依次位于前一个结点的右子树上。故二叉树深度为4。知识模块:,中序序列为HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为()。:C解析:二叉树的前序序列为ABDFHCEG,可以确定这个二叉树的根结点是A;再由中序序列HFDBACEG,可以得到HFDB为根结点A的左子树,CEG为根结点A的右子树。同理依次对左子树HFDB和右子树CEG进行同样的推理,得到该二叉树的结构如下:该二叉树按层次输出(同一层从左到右)的序列为ABCDFFGH。知识模块:(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为()。:B解析:完全二叉树的特点是除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。根据这一特点,再根据题意输出序列为ABCDEFGH,可以得到该二叉树的结构如下:故此完全二叉树的前序序列为ABDHECFG。知识模块:,其左子树上的结点值均小于根结点值,而右子树上的结点值均不小于根结点值,则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是()。:..正确答案:B解析:中序遍历的次序是先遍历左子树,再遍历根结点,最后遍历右子树。而在排序二叉树中,左子树结点值<根结点值≤右子树结点值,要使对排序二叉树的遍历结果为有序序列,只能采用中序遍历。知识模块:,其中的结点值互不相同。如果该二叉树的前序序列与中序序列相同,则该二叉树的深度为()。:C解析:在具有n个结点的二叉树中,如果各结点值互不相同,若该二叉树的前序序列与中序序列相同,则说明该二叉树只自右子树,左子树为空,二叉树的深度为n;若该二叉树的后序序列与中序序列相同,则说明该二叉树只有左子树,右子树为空,二叉树的深度为n。故本题中二叉树的深度为15。知识模块:,假设需要查找的元素一定在表中,并且元素出现在表中每个位置上的可能性是相同的,则在平均情况下需要比较的次数为()。.3n/4D.(n+1)/2正确答案:D解析:在顺序表中查找,最好情况下第一个元素就是要查找的元素,则比较次数为1;在最坏情况下,最后一个元素才是要找的元素,则比较次数为n。则平均比较次数:(1+2+…+n)/n=(n(n+1)/2)/n=(n+1)/2。知识模块:,假设需要查找的元素有一半的机会在表中,并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为()。/:B解析:在顺序表中查找,最好情况下第一个元素就是要查找的元素,则比较次数为1;在最坏情况下,最后一个元素才是要找的元素,则比较次数为n。这:..是找到元素的情况。如果没有找到元素,则要比较n次。因此,平均需要比较:找到元素的情况×+未找到元素的情况×=(1+2+…+n)/n×知识模块:,则平均情况与最坏情况下的时间复杂度相同的是()。:A解析:寻找最大项,无论如何都要查看所有的数据,与数据原始排列顺序没有多大关系,无所谓最坏情况和最好情况,或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找,都与要找的数据和原始的数据排列情况有关,最好情况是第1次查看的一个数据恰好是要找的数据,只需要比较1次;如果没有找到再查看下一个数据,直到找到为止,最坏情况下是最后一次查看的数据才是要找的,顺序查找和对分查找在最坏情况下比较次数分别是n和log2n,平均情况则是“1~最坏情况”的平均,因而是不同的。知识模块:。在最坏情况下,比较次数为n—1的算法是()。:C解析:顺序查找要逐个查看所有元素,会比较n次。在最坏情况下,寻找最大项无论如何需要查看表中的所有元素,n个元素比较次数为n—1。同时寻找最大项和最小项,需要为判断较大值和较小值分别进行比较,会有更多的比较次数。有序表的插入最坏情况下是插入到表中的最后一个元素的后面位置,则会比较n次。知识模块:()。:A解析:二分查找法(又称对分查找法)只适用于顺序存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列(即从小到大,但允许相邻元素值相等)。知识模块:公共基础知识:..,每经过一次数据交换(或移动)后()。:B解析:在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。快速排序的思想是:从线性表中选取一个元素,设为T,将线性表中后面小于T的元素移到前面,而前面大于T的元素移到后面,结果就将线性表分成两部分(称两个子表),T插入到其分割线的位置处,这个过程称为线性表的分割,然后再用同样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻元素进行比较,可以实线通过一次交换而消除多个逆序,但由于均与T(基准元素)比较,也可能会产生新的逆序。知识模块:()。A.(98,95,93,94,89,90,76,80,55,49)B.(98,95,93,94,89,85,76,64,55,49)C.(98,95,93,94,89,90,76,64,55,49)D.(98,95,93,96,89,85,76,64,55,49)正确答案:D解析:根据堆的定义,n个元素的序列(h1,h2,…h。),当且仅当hi≤h2i且hi≤h2i+1时为小顶堆,当且仅当hi≥h2i且hi≥h2i+1时为大顶堆。D项中,h2=95,h4=96,h2<h4,但h5=89,h2>h5,不满足小顶堆和大顶堆条件。知识模块:,最坏情况下比较次数相同的是()。:C解析:对于长度为n的线性表,最坏情况下查找或排序的次数如下表:知识模块:,对该表进行简单插入排序。在最坏情况下需要的比较次数为()。:..:A解析:简单插入排序在最坏情况下,即初始排序序列是逆序的情况下,比较次数为n(n—1)/2,移动次数为n(n—1)/2。本题中n=16,16×(16—1)÷2=8×15=120。知识模块:(S#,C#,G),其中S#为学号,C#为课程号,G为成绩,关系T=1TS#,C#(SC)/C表示()。:B解析:πS#,C#(SC)表示从关系SC中取出S#、C#两列,得到的结果与关系C进行除运算,表示选修了表C中全部课程的学生学号。知识模块:()。:A解析:关系数据库中的关系是要满足一定要求的,满足不同程度要求的为不同的范式。满足最低要求的叫第一范式,简称1NF。在满足第一范式的基础上,进一步满足更多要求规范则是第二范式。然后在满足第二范式的基础上,还可以再满足第三范式,以此类推。对于关系模式,若其中的每个属性都已不能再分为简单项,则它属于第一范式。若某个关系R为第一范式,并且R中每一个非主属性完全依赖于R的某个候选键,则称其为第二范式。第二范式消除了非主属性对主键的部分依赖。如果关系R是第二范式,并且每个非主属性都不传递依赖于R的候选键,则称R为第三范式。(传递依赖:在关系模式中,如果Y→X,X→A,且X不决定Y和A不属于X,那么Y→A是传递依赖。)比第三范式更高级的BCF范式,它要求所有属性都不传递依赖于关系的任何候选键。知识模块:(书店编号,书籍编号,库存数量,部门编号,部门负责人),其中要求(1)每个书店的每种书籍只在该书店的一个部门销售;(2)每个书店的每个部门只有一个负责人;(3)每个书店的每种书籍只有一个库存数量。则关系模式R最高是()。:..:B解析:由题可知关系模式R有三个函数依赖:(书店编号,书籍编号)→部门编号(书店编号,部门编号)→负责人(书店编号,书籍编号)→库存数量由此可知,(书店编号,书籍编号)可以唯一标识关系模式R中的每个元组,因此属于关系模式的主键。在此关系模式中,每个属性都是不可再分的,R属于1NF,且“书店编号”和“书籍编号”单独之一都不能决定其他非主属性,所以R属于2NF;但(书店编号,书籍编号)可以决定“部门编号”,“部门编号”又可决定“部门负责人”,存在传递依赖,所以不属于3NF,F。知识模块:公共基础知识