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

农村信用社招聘-计算机专业-数据结构与算法-综合练习题二[单选题]1.AOV网是一种（）。A.有向图B.无向无环图C.无向图D.有向无环图[单选题]2.二叉树的第k层的节点数最多为（）。（江南博哥）A.B.C.D.2[单选题]3.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。A.B.C.D.[单选题]4.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。A.O（n-1）B.O（n）C.O（n+1）D.[单选题]5.将长度为n的单链表链接在长度为m的单链表之后的算法，其时间复杂度为（）。A.O（m）B.O（m+n）C.O（1）D.O（n）[单选题]6.设一组初始记录关键字序列（5，2，6，3，8），以第一个记录关键字5为基准进行一趟快速排序的结果为（）。A.3，2，5，8，6B.2，3，5，8，6C.3，2，5，6，8D.2，3，6，5，8[单选题]7.设某哈夫曼树中有199个节点，则该哈夫曼树中有（）个叶子节点。A.101B.100C.99D.102[单选题]8.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，问A[3][3]存放在什么位置？脚注（10）表示用10进制表示。（）A.678B.688C.692D.696[单选题]9.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（）。A.栈B.线性表C.队列D.二叉排序树[单选题]10.设有广义表D（a，b，D），其长度为3，深度为（）A.∞B.3C.2D.5[单选题]11.设指针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；[单选题]12.在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（）。A.4B.5C.6D.7[单选题]13.设散列表中有m个存储单元，散列函数H（key）=key%p，则p最好选择（）。A.小于等于m的最大偶数B.小于等于m的最大合数C.小于等于m的最大奇数D.小于等于m的最大素数[单选题]14.设一条单链表的头指针为head且该链表没有头节点，则其判空条件是（）。A.head==NULLB.head-＞next==NULLC.head！=NULLD.head-＞next==head[单选题]15.栈和队列的共同特点是（）。A.都是先进后出B.只允许在端点处插入和删除元素C.都是先进先出D.没有共同点[单选题]16.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（）。A.O（n）B.O（1）C.D.[单选题]17.队列是一种（）的线性表。A.先进先出B.只能插入C.先进后出D.只能删除[单选题]18.由权值分别为11，8，6，2，5的叶子节点生成一棵哈夫曼树，它的带权路径长度为（）。A.53B.71C.48D.24[单选题]19.设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。A.1B.n-1C.D.n+1[单选题]20.由同一关键字集合构造的各棵二叉排序树（）。A.其形态不一定相同，但平均查找长度相同B.其形态不一定相同，平均查找长度也不一定相同C.其形态均相同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都相同[单选题]21.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。A.冒泡排序B.堆排序C.快速排序D.希尔排序[单选题]22.数据的最小单位是（）。A.数据项B.数据类型C.数据元素D.数据变量[单选题]23.设一个有序的单链表中有n个节点，现要求插入一个新节点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。A.B.0（1）C.0（n）D.O（n+1）[单选题]24.执行一趟快速排序能够得到的序列是（）。A.[41，12，34，45，27]55[72，63]B.[12，27，45，41]55[34，63，72]C.[63，12，34，45，27]55[41，72]D.[45，34，12，41]55[72，63，27][单选题]25.设链式栈中节点的结构为（data，link），且top是指向栈顶的指针。若想摘除链式栈的栈顶节点，并将被摘除节点的值保存到x中，则应执行下列（）操作。A.x=top-＞data；top=top-＞link；B.top=top-＞link；x=top-＞data；C.x=top；top=top-＞link；D.x=top-＞data；[单选题]26.设一棵二叉树的深度为k，则该二叉树中最多有（）个节点。A.1B.C.2D.[单选题]27.快速排序在最坏情况下的时间复杂度为（）。A.O（n）B.C.D.[单选题]28.设某强连通图中有n个顶点，则该强连通图中至少有（）条边。A.n+1B.n（n-1）C.nD.n（n+1）[单选题]29.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头节点和表节点的个数分别为（）。A.e，nB.n.eC.2n，eD.n，2e[单选题]30.A.B.C.D.[单选题]31.以下不是栈的基本运算的是（）。A.删除栈顶元素B.删除栈底元素C.判断栈是否为空D.将栈置为空栈[单选题]32.设某数据结构的二元组形式表示为A=（D，R），D={01，02，03，04，05，06，07，08，09}，R={r}，r={＜01，02＞，＜01，03＞，＜01，04＞，＜02，05＞，＜02，06＞，＜03，07＞，＜03，08＞，＜03，09＞}，则数据结构A是（）。A.图形结构B.树形结构C.物理结构D.线性结构[单选题]33.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。A.（n-1）/2B.（n+1）/2C.nD.n/2[单选题]34.A.O（m*n*t）B.O（m+n+t）C.O（m*t+n）D.O（m+n*t）[单选题]35.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（）。A.9，5，3B.9，5，2，3C.1，2，3D.9，4，2，3[单选题]36.在二叉排序树中插入一个节点的时间复杂度为（）。A.O（1）B.O（n）C.D.O（n-1）[单选题]37.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的节点X，则入队列的操作序列为（）。A.s-＞next=rear；rear=s；B.front-＞next=s；front=s；C.rear-＞next=s；rear=s；D.s-＞next=front；front=s；[单选题]38.设有序表中的元素为（13，18，24，35，47，50，62），则在其中利用二分法查找值为24的元素需要经过（）次比较。A.4B.2C.3D.1[单选题]39.以下数据结构中哪一个是非线性结构？（）A.线性表B.栈C.队列D.二叉树[单选题]40.将数组称为随机存取结构是因为（）。A.数组的存储结构是不定的B.数组元素是随机的C.对数组任一元素的存取时间是相等的D.随时可以对数组进行访问[单选题]41.在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。A.（front-rear+1）%mB.（rear-front+1）%mC.（front-rear+m）%mD.（rear-front+m）%m[单选题]42.用顺序存储的方法将完全二叉树中的所有节点逐层存放在数组A[1]～A[n]中，节点A[i]若有左子树，则左子树的根节点是（）。A.A[i/2]B.A[2i]C.A[2i-l]D.A[2i+l][单选题]43.设指针变量p指向单链表中节点A，若删除单链表中节点A，则需要修改指针的操作序列为（）。A.q=p-＞next；p-＞data=q-＞data；p-＞next=q-＞next；free（q）；B.q=p-＞next；p-＞data=q-＞data；free（q）；C.q=p-＞next；p-＞next=q-＞next；free（q）；D.q=p-＞next；q-＞data=p-＞data；p-＞next=q-＞next；free（q）；[单选题]44.下列各种排序算法中平均时间复杂度为O（r12）是（）。A.快速排序B.堆排序C.归并排序D.冒泡排序[单选题]45.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做（）次线性探测。A.n（n+1）B.nC.n（n+1）/2D.n（n-1）/2[单选题]46.设某完全无向图中有n个顶点，则该完全无向图中有（）条边。A.n（n-1）/2B.n（n-1）C.n+1D.n[单选题]47.设一组初始记录关键字序列为（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，XD.H，C，Q，P，A，M，S，R，D，F，X，Y[单选题]48.已知10个元素（54，28，16，34，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉排序树，查找值为62的节点所需比较次数为（）。A.2B.3C.4D.5[单选题]49.静态查找与动态查找的根本区别在于（）。A.所包含的数据元素的类型不一样B.存储实现不一样C.它们的逻辑结构不一样D.施加在其上的操作不同[单选题]50.二叉排序树中，最小值节点的（）。A.左、右指针均为空B.左、右指针均不为空C.左指针一定为空D.右指针一定为空[单选题]51.判定一个栈ST（最多元素为m0）为满的条件是（）。A.ST-＞top=m0-1B.ST-＞top=0C.ST-＞top＜＞m0D.ST-＞top＜＞0[单选题]52.设一组初始关键字记录关键字为（20，15，14，18，21，36，40，10），则以20为基准记录的一趟快速排序结束后的结果为（）。A.10，15，14，18，20，36，40，21B.15，10，14，18，20，36，40，21C.10，15，14，20，18，40，36，21D.10，15，14，18，20，40，36，21[单选题]53.对一个算法的评价，不包括如下（）方面的内容。A.健壮性和可读性B.并行性C.正确性D.时空复杂度[单选题]54.设某有向图的邻接表中有n个表头节点和m个表节点，则该图中有（）条有向边。A.n-1B.nC.m-1D.m[单选题]55.两个字符串相等的充要条件是（）。A.两个字符串中对应位置上的字符相等B.两个字符串的长度相等C.同时具备（A）和（B）两个条件D.两个字符串的大小相等[单选题]56.已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为（）。A.DBACEFB.DABECFC.BCDEAFD.ABDCEF[单选题]57.设二叉排序树中有n个节点，则在二叉排序树的平均查找长度为（）。A.O（n）B.C.O（1）D.O（n-1）[单选题]58.设有序表中有1000个元素，则用二分查找元素X最多需要比较（）次。A.15B.10C.17D.25[单选题]59.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。A.nB.C.n-1D.[单选题]60.广义表（a，b，（c，（d）））的表尾是（）。A.（b，（c，（d））B.（b，（c，（d）））C.（d）D.（c，（d））[单选题]61.下面关于线性表的叙述错误的是（）。A.线性表采用链式存储便于插入和删除操作的实现B.线性表采用顺序存储便于插入和删除操作的实现C.线性表采用顺序存储必须占用一片连续的存储空间D.线性表采用链式存储不必占用一片连续的存储空间[单选题]62.设某棵二叉树中有2000个节点，则该二叉树的最小高度为（）。A.12B.10C.11D.9[单选题]63.设指针变量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；[单选题]64.算法指的是（）A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列[单选题]65.在平衡二叉树中（）。A.不存在度为1的节点B.任意节点的左、右子树节点数目相同C.任意节点的左、右子树高度相同D.任意节点的左右子树高度之差的绝对值不大于1[单选题]66.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。A.O（n+1）B.C.O（1）D.0（n）[多选题]1.计算机算法必须具备（）等特性。A.可行性、可移植性B.易读性C.可行性、确定性D.有穷性E.输入、输出F.稳定性提交答案[多选题]2.串是一种特殊的线性表，下列不能体现其特殊性的是（）。A.可以顺序存储B.数据元素可以是多个字符C.数据元素是一个字符D.可以链式存储提交答案[多选题]3.有向图的连通包括（）。A.弱连通B.多侧连通C.强连通D.单侧连通提交答案[多选题]4.下列不属于数组的主要操作的是（）。A.检索（查找）B.修改C.插入D.删除E.存取提交答案[多选题]5.依据所有数据成员之间的逻辑关系的不同，数据结构分为（）。A.非线性结构B.逻辑结构C.线性结构D.物理结构提交答案[多选题]6.图的四种存储结构（）。A.邻接矩阵B.邻接表C.十字链表D.邻接多重表提交答案[多选题]7.如下陈述中错误的是（）。A.串的长度必须大于零B.串是一种特殊的线性表C.串中元素只能是字母D.空串就是空白串提交答案[多选题]8.下面关于线性表的叙述正确的是（）。A.线性表采用链式存储便于插入和删除操作的实现B.线性表采用顺序存储便于插入和删除操作的实现C.线性表采用顺序存储必须占用一片连续的存储空间D.线性表采用链式存储不必占用一片连续的存储空间提交答案[多选题]9.树的表示方法有以下哪几种（）。A.直观表示法B.广义表表示法C.凹入表示法D.嵌套集合表示法提交答案[多选题]10.下列哪一条不是顺序存储结构的优点（）。A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示提交答案[多选题]11.抽象数据类型按其值的不同特性可分为（）。A.分子类型B.固定聚合类型C.离子类型D.可变聚合类型E.原子类型提交答案[多选题]12.便于插入和删除操作的是（）。A.顺序表B.单链表C.静态链表D.双链表E.循环链表提交答案[多选题]13.算法设计的要求包括（）。A.健壮性B.确定性C.正确性D.可读性提交答案[多选题]14.以下哪些是线性表（）。A.二叉树B.栈C.队列D.集合提交答案[多选题]15.完全二叉树（）。A.某些节点有右子树则必有左子树B.不一定适合顺序结构存储C.叶子节点可在任一层出现D.适合于顺序结构存储提交答案[多选题]16.下列属于算法的重要特征的是（）。A.输入和输出B.确定性C.可行性D.有穷性提交答案[多选题]17.操作系统中动态存储管理方法包括（）。A.伙伴系统B.边界标识法C.朋友系统D.中央标识法提交答案[多选题]18.线性结构的特点是（）。A.除最后元素在外，均有唯一的后继B.除第一元素之外，均有唯一的前驱C.集合中必存在唯一的一个“第一元素”D.集合中必存在唯一的一个“最后元素”提交答案[多选题]19.下列数据结构中，属于线