农村信用社招聘-计算机专业-数据结构-综合练习题二

农村信用社招聘-计算机专业-数据结构-综合练习题二[单选题]1.下列叙述正确的个数是（）。（1）m=2的平衡m路查找树是AVL树（2）m=3的平衡m路查找树是2-3树（3）m=2的平衡m路查找树的（江南博哥）叶结点不一定在同一层（4）m阶B-树的叶结点必须在同一层（5）m阶B-树是平衡m路查找树（6）平衡m路查找树不一定是B-树A.3B.4C.5D.6[单选题]2.散列函数有一个共同的性质，即函数值应当以（）概率取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率[单选题]3.快速排序最易发挥其长处的情况是（）。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊[单选题]4.A.iB.n-iC.n-i+lD.不确定[单选题]5.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（）结构。A.栈B.队列C.数组D.线性表[单选题]6.设高度为H的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A.2*HB.1*H-1C.2*H+1D.H+1[单选题]7.下列叙述正确的个数是（）。（1）向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。（2）对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。（3）所谓平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。（4）删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二又排序树。A.4B.3C.2D.1[单选题]8.下列说法正确的是（）。A.任何有向网络（AOV-网）拓扑排序的结果是唯一的B.有回路的图不能进行拓扑排序C.在AOE网中一定只有一条关键路径D.一个正常的AOE网中只能有一个源点、一小汇点和一条关键路径[单选题]9.下面关于m阶B-树说法正确的是（）。①每个结点至少有两棵非空子树；②树中每个结点至多有m-1个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。A.①②③B.②③C.②③④D.③[单选题]10.有六个元素6，5，4，3，2，1的顺序进栈.下列选项中，（）不是合法的出栈序列。A.543612B.453126C.346521D.234156[单选题]11.设有n个元素进栈序列是P1，P2，P3，…，Pn，其输出序列是1，2，3，…，n，若P3=3，则P1的值（）。A.可能是2B.一定是2C.不可能是1D.一定是1[单选题]12.以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是（）。A.front=front+1B.front=（front+1）%mC.front=（front+1）%（m+1）D.rear=（rear+1）%m[单选题]13.采用简单选择排序，比较次数与移动次数分别为（）。A.0（n），0（logn）B.C.D.0（nlogn），0（n）[单选题]14.设二叉排序树中关键字由1～1000的整数构成，现要查找关键字为363的结点，下列关键字序列不可能是在二叉排序树上查找到的序列是（）。A.2，252，401，398，330，344，397，363B.924，220，911，244，898，258，362，363C.925，202，911，240，912，245，363D.2，399，387，219，266，382，381，278，363[单选题]15.循环队列用数组A[o…m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（）。A.（rear-front+m）modmB.rear-front+lC.rear-front-1D.rear-front[单选题]16.将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][64]在B数组中的位置等于（）。A.198B.197C.196D.195[单选题]17.在平衡二叉树中，（）。A.任意结点的左右子树结点数目相同B.任意结点的左右子树高度相同C.任意结点的左右子树高度之差的绝对值不大于1D.不存在度为1的结点[单选题]18.已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE[单选题]19.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a1，1为第一元素，其存储地址为1，每个元素占一个地址空间，则a8·5的地址是（）。A.13B.33C.18D.40[单选题]20.先序遍历序列和中序遍历序列相同的二叉树为（）。A.根结点无左子树的二叉树B.根结点无右子树的二叉树C.只有根结点的二叉树或非子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树[单选题]21.设二维数组A[6][0]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址为（）。A.1000B.860C.1140D.1200[单选题]22.下面关于图的遍历说法不正确的是（）。A.遍历图的过程实质上是对每个顶点查找其邻接点的过程B.深度优先搜索和广度优先搜索对无向图和有向图都适用C.深度优先搜索和广度优先搜索对顶点访问的顺序不同，它们的时间复杂度也不相同D.深度优先搜索是一个递归的过程，广度优先搜索的过程中需附设队列[单选题]23.以数组Q[0…m-1]存放循环队列中的元素，若变量front和qulen分别指示循环队列中队头元素的实际位置和当前队列的长度，则队尾元素的实际位置是（）。A.front+qulen-1B.（front+qulen）modmC.（front+qulen-1）modmD.front+qulen[单选题]24.若一个具有n个结点、k条边的非连通无向图是一个森林（n＞k），则该森林中必有（）棵树。A.kB.nC.n-kD.n+k[单选题]25.m阶B+树中除根节点外，其他节点的关键字个数至少为（）。A.[m/2]B.[m/2]-1C.[m/2]+1D.任意[单选题]26.对下列关键字序列用快速排序法进行排序时，速度最快的是（）。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}[单选题]27.在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储的位置是（）。A.B.C.1D.[单选题]28.无向图G=（V，E），其中：V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c），（b，c），（c，f），（f，d），（e，d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A.a，b，e，c，d，fB.a，C，f，e，b，dC.a，e，b，C，f，dD.a，e，d，f，C，b[单选题]29.在一个长度为n（n＞1）的带头结点的单链表h上，设有尾指针r（指向尾结点），则执行（）操作与链表的长度有关。A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素[单选题]30.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为（）。A.37/12B.35/12C.39/12D.43/12[单选题]31.在一棵完全二叉树中，其根的序号为1，（）可判定序号为p和q的两个结点是否在同一层。A.B.C.D.[单选题]32.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（）。A.4B.5C.6D.7[单选题]33.A.21/7B.28/7C.15/6D.21/6[单选题]34.将5个字母“ooops”按此顺序入栈，则有（）种不同的出栈顺序可以仍然得到“ooops”。A.1B.3C.5D.6[单选题]35.一个具有1025个结点的二叉树的高h为（）。A.11B.10C.11至1025之间D.10至1024之间[单选题]36.中缀表达式A-（B+C/D）*E的后缀形式是（）。A.AB-C+D/E*B.ABC+D/-E*C.ABCD/E*+-D.ABCD/+E*-[单选题]37.下列排序算法中，（）每一趟都能选出一个元素放在最终位置上，并且是不稳定的。A.冒泡排序B.希尔排序C.直接选择排序D.直接插入排序[单选题]38.在单链表指针为P的结点之后插入指针为s的结点，正确的操作是（）。A.B.C.D.[单选题]39.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次进入栈S和进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，es，e1。则栈S的容量至少应该是（）。A.6B.4C.3D.2[单选题]40.二维数组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][单选题]41.以比较为基础的排序算法在最坏情况下的计算时间下界为（）。A.O（n）B.C.O（logn）D.O（nlogn）[单选题]42.某二叉树中序序列为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.B，D，G，FD.以上都不对[单选题]43.在求边稠密的图的最小代价生成树时，（）算法比较合适。A.普里姆（Prim）B.克鲁斯卡尔（Kruskal）C.迪杰斯特拉（Dijkstra）D.其他[单选题]44.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选择（）方法。A.冒泡排序B.快速排序C.堆排序D.基数排序[单选题]45.在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O（n）B.O（n+e）C.On×nD.O（n×n×n）[单选题]46.在有11个元素的有序表A[1..11]中进行折半查找，查找元素A[11]时，被比较的元素的下标依次是（）。A.6，8，10，11B.6，9，10，11C.6，7，9，11D.6，8，9，11[单选题]47.设数组ta[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front的值为（）。A.front=front+1B.front=（front+1）%（m-1）C.front=（front-1）%mD.front=（front+1）%M[单选题]48.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。A.起泡排序B.插入排序C.选择排序D.二路归并排序[单选题]49.以下各种存储结构中，最适合用作链队的链表是（）。A.带队首指针和队尾指针的循环单链表B.带队首指针和队尾指针的非循环单链表C.只带队首指针的非循环单链表D.只带队首指针的循环单链表[单选题]50.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（）。A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙[单选题]51.以下叙述不正确的是（）。A.后序线索二叉树是不完善的，要对它进行遍历，不需使用栈B.任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈C.任何一棵二叉树都可以不用栈实现先序线索树的先序遍历D.任何一棵二叉树都可以不用栈实现中序线索树的中序遍历[单选题]52.一棵有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.条件不充分，无法确定[单选题]53.关于哈夫曼树，下列说法正确的是（）。A.在哈夫曼树中，权值相同的叶子结点都在同一层上B.在哈夫曼树中，权值较大的叶子结点一般离根结点较远C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近D.在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理[单选题]54.设无向图的顶点个数为n，则该图最多有（）条边。A.n-1B.n（n-1）/2C.n（n+1）/2D.[单选题]55.下面关于求关键路径的说法不正确的是（）。A.求关键路径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一一定位于关键路径上[单选题]56.在线索化二叉树中，t所指结点没有左子树的充要条件是（）。A.t-＞left=NUL1B.t-＞ltag=1C.t-＞ltag=1且t-＞left=NUL1D.以上都不对[单选题]57.对任意7个关键字进行排序，至少要进行（）次关键字之间的两两比较。A.13B.14C.15D.16[单选题]58.A.abcfdegB.abcgfdeC.abcdefgD.abcfgde[单选题]59.查找效率最高的二叉排序树是（）。A.所有结点的左子树都为空的二叉排序树B.所有结点的右子树都为空的二叉排序树C.平衡二叉排序树D.没有左子树的二叉排序树[单选题]60.下列排序方法中，（）是稳定的排序方法。A.直接插入排序和快速排序B.折半插入排序和起泡排序C.简单选择排序和四路归并排序D.树形选择排序和shell排序[单选题]61.下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ.所有顶点的度之和为偶数Ⅱ.边数大于顶点个数减1Ⅲ，至少有一个顶点的度为1A.只有B.只有ⅡC.Ⅰ和ⅡD.Ⅰ和Ⅲ[单选题]62.快速排序最不利于发挥其长处的情况是（）。A.待排序的数据中含有多个相同值B.待排序的数据已基本有序C.待排序的数据量太大D.被排序的数据数量为奇数[单选题]63.树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间有分支层次关系[单选题]64.下面关于B和B+树的叙述中，不正确的是（）。A.B树和B+树都是平衡的多叉树B.B树和B+树都可用于文件的索引结构C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索[单选题]65.具有5个叶子结点的二叉树中，度为2的结点的个数为（）。A.4B.6C.5D.不确定[单选题]66.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数是（）。A.5B.6C.7D.8[单选题]67.某二叉树的先序和后序序列正好相反，则该二叉树一定是（）。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子[单选题]68.在一棵高度为h的理想平衡二叉树中，最少含有（）个结点，最多含有（）个结点。A.B.C.D.[单选题]69.用二分（对半）查找表的元素的速度比用顺序法的速度要（）。A.必然快B.必然慢C.相等D.不能确定[单选题]70.若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为（）。A.BCAGFEDB.DAEBCFGC.ABCDEFGD.BCAEFGD[单选题]71.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（）。Ⅰ.父子关系Ⅱ.