《数据结构》习题

《《数据结构》习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、单项选择题1.对矩阵进行压缩存储是为了（）A・节省存储空间B.提高运算速度C.便于运算D.方便存储2•链式栈与顺序栈相比，一个比较明显的优点是（）A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便3.设输入序列为1,2,3,4,5,贝IJ借助一个队列可以得到的输出序列是（）A.3,4,1,2,5B・1,2,3,4,5C.2,3,4,1,5D.5,4,3,2,14.一个栈的输入序列是6,5,4,3,2,1,可能的输出序列是()A.4,3,2,1,5,6B.3,6,2,1,5,4C.1,2,3,5,4,6D.5,4,1,3,2,65.设

2、输入序列为A,B,C,Do借助一个栈可以得到的输出序列是()A.A,C,D,BB.C,A,D,B6.将含100个结点的完全二叉树从根开始，71的结点的双亲结点的编号为（）A.34B.35C.D,C,A,BD.每层从左到右依次对结点编号，根结点的编号为1,则编号为C.36(2D,A,B,CD.无法确定）个度为1的结点。D.不确定7.已知完全二叉树有80个结点，则该二叉树有A.0B.1C.8.任何一个无向连通图的最小生成树（）A口右■——梯r右•——櫟口p名梯C9.设窗G川矗接表存储，•对该图应行深度优先搜索遍历，A.0（n）B.0（n+e）C・0（n2）10.用n个键值构造一

3、棵二叉排序树，最低高度为（A.n/2B.nC.[bg2n]11.如果以链表作为栈的存储结构，则执行出栈操作时（A.必须判断栈是否满C.判断栈元素的类型12.设数组DataM作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）A.front二front+1C.rear=（rear+l）%m13.线性表的长度是指（）A.顺序存储方式卜-数组所占用的元索个数C.表中的元素个数D.14.设有一个无向图G=（V,E）和G'=（VE'-定冇多棵D.口J能不存在则算法的时间复杂度为（）D.0（n3）D.[log2n]+1）B.必须判断栈是否空

4、D.对栈不作任何判断B.D.front二(front+1)%mfront=(front+1)%(m+1)A.G，为G的子图B.G'为G的连通分量C.G，为G的极小连通子图且W二VD.G'是G的一个无环子图15.在采川线性探测法处理冲突所构成的闭散列表上进行查找，可能耍探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（）A.—定都是同义词B.—定都不是同义词C.都相同D.不一定都是同义词16.在有序表A[20]屮按二分查找方法查找A[13]依次比较的元素的卜•标是（）A.9,14,12，13B.9,15,12,13C.9,14,11,12,13D.10,15,12,

5、1317.栈和队列都是（）A.顺序存储的线性表B.链式存储的线性表C.限制的线性表D.限制存储点的非线性结构18.向顺序栈中压入新元索时，应当（)A.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D.同时进行19.若树的先序序列和中序序列正好相同,则一定是一棵（）的二叉树。B.链表存储方式卜•的结点个数所能存储的最大的结点个数）,如果V是G的住成树，则下面不正确的说法是（）20.21.22.23.24.A.结点个数可能大于1且该树无左子树B.结点个数可能大于1且根结点无左孩子C.结点个数可能大于1几各结点均无左孩子D.其中任意一个结点的度不为2

6、下列算法中，在第一趟排序之后，-•定能把数据表中最大或最小元素放在其最终位置上的算法是（）A.归并排序B.直接插入排序C.快速排序D.冒泡排序当初始序列己经按键值有序时，用直接插入算法进行排序，需要比较元素的次数为（A.n2下列排序算法屮，A.直接选择排序下列排序方法中，A.直接插入排序B.nbg211C.,og2n在最好情况F，时间复杂度为0（n）的算法是（B.归并排序C.快速排序排序所花费时间不受数据初始排列特性影响的算法是（B.冒泡排序C.直接选择排序对待排序的元素序列进行划分，将其分为左、右两个了序列，直到子序列为空或只剩一个元素为止。这样的排序方法是（）A.直接选

7、择排序B.直接插入排序C.快速排序対5个不同的数据元素进行直接插入排序，最多需要进行（A.8B.10C.1525.D.n-1）D.冒泡排序）D.快速排序再对两个了序列施加同样的排序操作，D.起泡排序）次比较。D.2526.在一个具有n个结点的双链表屮插入一个新结点，则该操作的时间复杂性的量级为（）A.0（1）B.0（n）C・0（nlog2n）D.0（n2）27.二分查找法要求被查找的表是（）A.顺序表B.分块有序表C.顺序表H•是按键值递增或递减次序排列D.不受上述任何限制28.若某线性表屮最常用的操作是在最示一个