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

农村信用社招聘-计算机专业-数据结构-综合练习题三[单选题]1.下面的说法中正确的是（）。（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变：（2）按二叉树定义，具有三个结点的二叉树共有6种（江南博哥）。A.（1）（2）B.（1）C.（2）D.（1）、（2）都错[单选题]2.已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（）。A.4B.5C.6D.7[单选题]3.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是（）。A.二叉排序树B.哈夫曼树C.堆D.AVL树[单选题]4.设结点x和y是二叉树中的任意两结点，若在该树的先根、中根和后根序列里，x和y中的一个结点皆在另一个结点之前，则它们的关系是（）。A.x和y必互为兄弟B.x和y必是树叶C.一个是另一个的祖先D.彼此无祖先和后代的关系[单选题]5.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。A.nB.n+lC.n-lD.n/2[单选题]6.一棵m阶非空B-树，每个结点最多有（）棵子树。A.m/2B.m-1C.mD.m+1[单选题]7.已知有向图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[单选题]8.A.LRNB.NRLC.RLND.RNL[单选题]9.设n阶方阵是一个上三角矩阵，则需存储的元素个数为（）。A.nB.n×nC.n×n/2D.n（n+1）/2[单选题]10.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）次序的遍历实现编号。A.先序B.中序C.后序D.从根开始按层次遍历[单选题]11.采用邻接表存储的图的广度优先遍历算法类似于树的（）。A.中根遍历B.先根遍历C.后根遍历D.按层次遍历[单选题]12.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中，第一棵树的结点个数是（）。A.m-nB.m-n-1C.n+1D.条件不足，无法确定[单选题]13.一个有n个结点的图，最多有（）个连通分量。A.0B.1C.n-1D.n[单选题]14.若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。A.79，46，56，38，40，84B.84，79，56，38，40，46C.40，38.46，56，79，84D.40，38，46，84，56，79[单选题]15.下列二叉排序树中，满足平衡二叉树定义的是（）。OA.B.C.D.[单选题]16.A[N，N]是对称矩阵，将下三角（包括对角线）以行序存储到一维数组T[N（N+l）/2]q中，则对任一上三角元素A[i][j]对应T[k]的下标k是（）。A.i（1-1）/2+jB.j（j-1）/2+iC.i（j-i）/2+1D.j（1-1）/2+1[单选题]17.下列关于AOE网的叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成。那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成[单选题]18.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A.M1B.M1+M2C.M3D.M2+M3[单选题]19.由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为（）。A.27B.38C.51D.75[单选题]20.假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，至少要进行的探查次数是（）。A.k-1B.kC.k+1D.k（k+1）/2[单选题]21.对于一个满二叉树，共有n个结点和m个叶子结点，深度为h，则（）。A.n=h+mB.h+m=2nC.m=h-1D.[单选题]22.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（）。A.O（n）B.O（n+e）C.D.[单选题]23.A.14B.19C.21D.26[单选题]24.下面给出的四种排序方法中，辅助空间为O（n）的是（）。A.希尔选择B.冒泡排序C.归并排序D.堆排序[单选题]25.下列说法不正确的是（）。A.图的遍历是从给定的源点出发每一个顶点仅被访问一次B.遍历的基本算法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程[单选题]26.A.（1），（2），（3）B.（1）C.（1），（3）D.（2），（3）[单选题]27.下列不属于内部排序的算法是（）。A.归并排序B.拓扑排序C.树型排序D.折半插入排序[单选题]28.每棵树都能唯一地转换成相对应的二叉树，由树转换成的二叉树中，一个结点N的左孩子是它在原树对应结点的（）。A.最左孩子B.最右孩子C.右邻兄弟D.左邻兄弟[单选题]29.判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用（）。A.求关键路径的方法B.求最短路径的Dijkstra方法C.广度优先遍历算法D.深入度优先遍历算法[单选题]30.当采用分块查找时，数据的组织方式为（）。A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同[单选题]31.在含有12个结点的平衡二叉树上，查找关键字为35（存在该结点）的结点，则依次比较的关键字有可能是（）。A.46，36，18，20，28，35B.47，37，18，27，36C.27，48，39，43，37D.15，45，55，35[单选题]32.数据序列{8，9，10，4，5，6，20，1，2}只能是（）算法的两趟排序后的结果。A.直接选择排序B.冒泡排序C.直接插入排序D.堆排序[单选题]33.在含有15个结点的平衡二叉树上，查找关键字为28（存在该结点）的结点，则依次比较的关键字有可能是（）。A.30，36B.38，48，28C.48，18，38，28D.60，30，50，40，38，36[单选题]34.有m个叶子结点的哈夫曼树所具有的结点数为（）。A.mB.m+1C.2mD.2m-1[单选题]35.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13，散列地址为1的链中有（）个记录。A.1B.2C.3D.4[单选题]36.若对序列（tang，deng，an，wang，shi，bai，fang，liu）采用选择排序法按字典顺序进行排序，下面给出的四个序列中，（）是第三趟的结果。A.an.bai，deng，wang，tang，fang，shi，huB.an，bai，deng，wang，shi，tang，fang，liuC.an.bai，deng，wang，shi，fang，tang，liuD.an.bai，deng，wang，shi，liu，tang，fang[单选题]37.已知串S=′aaab′，其next数组值为（）。A.0123B.0213C.0231D.1211[单选题]38.以下排序方法中，在初始序列已基本有序的情况下，排序效率最高的是（）。A.归并排序B.直接插入排序C.快速排序D.堆排序[单选题]39.A.4B.5C.6D.7[单选题]40.堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次输出堆顶元素。设给定序列{48，62，35，77，55，14，35，98}，若在堆排序的第一阶段将该序列建成一个堆（大根堆），那么交换元素的次数为（）。A.5B.6C.7D.8[单选题]41.采用分块查找时.若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。A.10B.25C.6D.625[单选题]42.无向图中一个顶点的度是指图中（）。A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻接的顶点数D.与该顶点连通的顶点数[单选题]43.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍：A.1/2B.2C.1D.4[单选题]44.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键值11，所需的关键码比较次数为（）。A.2B.3C.4D.5[单选题]45.下面几个符号串编码集合中，不是前缀编码的是（）。A.{0，10，110，1111}B.{11，10，001，101，0001}C.{00，010，0110，1000}D.{b，c，aa，aba，abb，abc}[单选题]46.下列四个序列中，（）是堆。A.75，65，30，15，25，45，20，10B.75，65，45，10，30，25，20，15C.75，45，65，30，15，25，20，10D.75，45，65，10，25，30，20，15[单选题]47.要连通具有n个顶点的有向图，至少需要（）条边。A.n-1B.nC.n+1D.2n[单选题]48.KMP算法的特点是在模式匹配时指示主串的指针（）。A.不会变大B.不会变小C.都有可能D.无法判断[单选题]49.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点v相关的所有弧的时间复杂度是（）。A.O（n）B.O（e）C.O（n+e）D.O（n*e）[单选题]50.A.顶点序列B.边序列C.权值总和D.边的条数[单选题]51.线索化的二叉树中，某结点*P没有孩子的充要条件是（）。A.p-＞lchild=NULLB.p-＞ltag=l&&p-＞rtag=1C.p-＞ltag=0D.p-＞lchild=NULL&&p-＞ltag=1[单选题]52.最好情况下的算法时间复杂度为O（n）的是（）。A.插入排序B.归并排序C.快速排序D.堆排序[单选题]53.文件有m个初始归并段，采用k路归并时，所需的归并遍数是（）。A.B.C.D.[单选题]54.下列有关散列查找的叙述正确的是（）。A.散列存储法只能存储数据元素的值，不能存储数据元素之间的关系B.散列冲突是指同一个关键字对应多个不同的散列地址C.用线性探测法解决冲突的散列表中，散列函数值相同的关键字总是存放在一片连续的存储单元中D.若散列表的装填因于a＜＜l，则可免冲突的严生[单选题]55.下列的叙述不正确的个数是（）。（1）9阶B-树，除根以外的任一结点的关键字个数不少于4（2）理想情况下，在散列表中查找一个元素的时间复杂度为0（1）（3）在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻（4）在索引顺序表的查找中，对索引表既可以采用顺序查找方法，也可采用=分查找方法A.1B.2C.3D.4[单选题]56.以下关于查找方法的说法正确的是（）。Ⅰ.顺序查找法只能在顺序存储结构上进行Ⅱ.二分查找法可以在有序的双向链表上进行Ⅲ.分块查找的效率与线性表被分为多少块有关A.Ⅰ、ⅡB.Ⅱ、ⅢC.Ⅰ、ⅢD.只有Ⅲ[单选题]57.下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A.堆排序B.冒泡排序C.快速排序D.插入排序[单选题]58.（）在其最好情况下的算法时间复杂度为O（n）。A.插入排序B.归并排序C.快速排序D.堆排序[单选题]59.在一裸m阶的B+树中，每个非叶结点的儿子数S应满足（）。A.B.C.D.[单选题]60.有n个记录的文件，若关键字位数为d，基数为r，则基数排序共需进行（）遍分配与收集。A.nB.rC.dD.d+r[单选题]61.指出在顺序表F={2，5，7，10，14，15，18，23，35，41，52}中，用二分查找法查找12需要进行多少次比较（）。A.2B.3C.4D.5[单选题]62.若对27个元素只进行三趟多路归并排序，则选取的归并路数为（）。A.2B.3C.4D.5[单选题]63.对关键码序列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）[单选题]64.求最短路径常用的算法有（）。A.Prim算法和Kruskal算法B.深度优先遍历算法和广度优先遍历算法C.Dijkstra算法和Floyd算法D.拓扑排序算法[单选题]65.对于含有n个顶点的带权连通图，它的最小生成树是指（）。A.图中任意一个由n-l条权值最小的边构成的子图B.图中任意一个由n-1条权值之和最小的边构成的子图C.图中任意一个由n-1条权值之和最小的边构成的连通子图D.图中任意一个由n个顶点构成的边的权值之和最小的连通子图[单选题]66.对包含n个关键码的散列表进行检索，平均检索长度为（）。A.O（logn）B.O（n）C.O（nlogn）D.不直接依赖于n[单选题]67.下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的是（）。A.快速排序B.shell排序C.堆排序D.冒泡排序[单选题]68.A.B.C.D.[单选题]69.对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（）。A.n/2B.（n+1）/2C.（n-1）/2D.n/4[单选题]70.下面关于哈希查找的说法正确的是（）。A.哈希函数构造的越复杂越好，因为这样随机性好、冲突小B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数，要视情况而定D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可[单选题]71.外排序是指（）。A.在外存上进行的排序方法。B.不需要使用内存的排序方法。C.数据量大，需要人工干预的排序方法。D.排序前后数据在外存，排序时数据调入内存的排序方法。[单选题]72.用直接选择排序方法分别对序列S1=（1，2，3，4，5，6，7）和序列S2=（7，5，3，2，4，