数据结构基础复习题(CIW) 1

第1页数据结构复习题一、判断题1.线性表的逻辑顺序总是与其物理顺序一致。（）【答案】错2.线性表的顺序存储优于链式存储。（）【答案】错3.在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。（）【答案】对4.若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反。（）【答案】错6.内部排序是指排序过程在内存中进行的排序。（）【答案】对7.当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。（）【答案】错8.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。()【答案】对9.任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。（）【答案】对10.若将一批杂乱无章的数据按堆结构组织起来,则堆中数据必然按从小到大的顺序线性排列。()【答案】错14.当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。()【答案】对15.哈希查找法中解决冲突问题的常用方法是除留余数法。（）【答案】错16.对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。()【答案】错17.堆排序是一种稳定的排序算法。()【答案】错18.如果有向图中各个顶点的度都大于2，则该图中必有回路。()【答案】错19.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置。（）【答案】错21.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。()【答案】错22.拓扑排序是指结点的值是有序排序的。（）【答案】错25.图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。()【答案】对26.对二叉排序树进行中根遍历，可得到结点的有序排列。（）【答案】对第2页27.任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。（）【答案】对28.边数很少的稀疏图，适宜用邻接矩阵表示。（）【答案】错29.二叉树是一棵无序树。()【答案】错31.当待排序序列初始有序时，快速排序的时间复杂性为O(n)。（）【答案】错32.顺序表的空间利用率高于链表。（）【答案】对33.采用不同的遍历方法，所得到的无向图的生成树是不同的。（）【答案】对34.有回路的有向图不能完成拓扑排序。()【答案】对35.存在这样的二叉树，对它采用任何次序的遍历，结果相同。()【答案】对36.装载因子是散列表的一个重要参数，它反映了散列表的装满程度。()【答案】对37.算法分析的目的是找出数据结构的合理性。（）【答案】错38.单链表可以实现随机存取。（）【答案】错39.边数很多的稠密图，适宜用邻接矩阵表示。（）【答案】对40.理想情况下哈希查找的等概率查找成功的平均查找长度是O（1）。()【答案】对41.边数很少的稀疏图，适宜用邻接表表示。（）【答案】对42.对于同一组关键字互不相同的记录，若生成二叉排序树时插入记录的次序不同则得到不同形态的二叉排序树。()【答案】对44.哈希查找法中解决冲突问题的常用方法是除留余数法。（）【答案】错45.顺序查找法适用于存储结构为顺序或链接存储的线性表。（）【答案】对46.若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（）【答案】错47.在线性链表中删除中间的结点时，只需将被删结点释放。（）【答案】错48.线性表若采用链式存储表示,在删除时不需要移动元素。（）【答案】对49.对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。()【答案】错50.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。第3页()【答案】对51.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。()【答案】错53.循环链表的结点与单链表的结点结构完全相同，只是结点间的连接方式不同。（）【答案】对54.能够在链接存储的有序表上进行折半查找，其时间复杂度与在顺序存储的有序表上相同。()【答案】错55.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。()【答案】对56.一个无向连通图的生成树是图的极小的连通子图。（）【答案】对58.快速排序的时间复杂性不受数据初始状态影响，恒为O(nlog2n)。（）【答案】错61.如果无向图中每个顶点的度都大于等于2，则该图中必有回路。()【答案】对62.顺序存储方式只适用于存储线性表。（）【答案】错63.若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相同。（）【答案】对64.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。()【答案】错65.完全二叉树的某结点若无左孩子，则它必是叶结点。()【答案】对66.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。()【答案】错67.折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想平衡二叉树。()【答案】对69.在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。（）【答案】对72.理想情况下哈希查找的等概率查找成功的平均查找长度是O（1）。（）【答案】对73.在任意一棵二叉树的先根序列和后根序列中，各叶子之间的相对次序关系都相同。（）【答案】对75.采用不同的遍历方法，所得到的无向图的生成树总是相同的。（）【答案】错76.对于同一组记录，生成二叉排序树的形态与插入记录的次序无关。()【答案】错77.对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键字大小排列到一个拓扑有序的序列中。()【答案】错78.链式栈与顺序栈相比,一个明显的优点是通常不会出现栈满的情况。（）第4页【答案】对79.对于两棵具有相同记录集合而具有不同形态的二叉排序树，按中根遍历得到的结点序列是相同的。()【答案】对81.边数很少的稀疏图，适宜用邻接矩阵表示。（）【答案】错82.递归的算法简单、易懂、容易编写，而且执行效率也高。（）【答案】错84.链队列的出队操作总是需要修改尾指针。（）【答案】错85.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。（）【答案】对87.直接选择排序是一种稳定的排序方法。()【答案】错89.线性表的逻辑顺序总是与其物理顺序一致。（）【答案】错91.对平衡二叉树进行中根遍历，可得到结点的有序序列。（）【答案】对92.双向循环链表的结点与单链表的结点结构相同，只是结点间的连接方式不同。（）【答案】错93.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（）【答案】错97.当输入序列已经基本有序时，冒泡排序需要比较关键字的次数，比快速排序还要少。()【答案】对98.顺序查找法适用于存储结构为顺序或链接存储的线性表。()【答案】对100.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。()【答案】对101.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（）【答案】对102.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（）【答案】对105.在二叉排序树中插入新结点时，新结点总是作为叶子结点插入。（）【答案】对106.边数很少的稀疏图，适宜用邻接表表示。（）【答案】对107.链队列的出队操作总是需要修改尾指针。（）【答案】错108.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。()【答案】对110.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树。()【答案】错112.图的广度优先搜索算法通常采用非递归算法求解。()【答案】对第5页113.拓扑排序是指结点的值是有序排序的。（）【答案】错114.数据的逻辑结构与数据元素本身的内容和形式无关。【答案】对116.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。()【答案】错117.边数很多的稠密图，适宜用邻接表表示。（）【答案】错119.在索引顺序结构的查找中，对索引表既可以采取顺序查找，也可以采用折半查找。()【答案】对120.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（）【答案】错121.对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。()【答案】对122.对于一棵具有n个结点的任何二叉树，进行先根、中根或后根的任一种次序遍历的空间复杂度为O(log2n)。()【答案】错124.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。（）【答案】对127.进行折半查找的表必须是顺序存储的有序表。()【答案】对128.在索引顺序结构上实施分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的记录个数有关。()【答案】对129.图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。()【答案】对130.数据元素是数据的最小单位。【答案】错131.在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。（）【答案】对二、单项选择题1.向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A.64B.63C.63.5D.7【答案】A2.线性表是具有n个（）的有限序列（n≠0）。A.表元素B.字符C.数据元素D.数据项【答案】C3.下列哪种排序方法在最坏的情况下的时间复杂度是O（n*log2n）（）。A.直接插入排序B.堆排序C.简单选择排序D.快速排序【答案】B5.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。第6页A.x=HS;HS=HS-next;B.x=HS-data;C.HS=HS-next;x=HS-data;D.x=HS-data;HS=HS-next;【答案】D8.在一个长度为n的顺序表中插入一个元素时,等概率情况下的平均移动元素的次数是（）。A．n/2B．（n-1）/2C．n*(n-1)/2D．(n+1)/2【答案】A10.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（）。A．eB．2eC．n2－eD．n2－2e【答案】D13.循环队列用数组A[M]存放元素，已知其头尾指针分别为front和rear，则当前队列中的元素个数是（）。A．rear-front+1B．rear-front-1C．rear-frontD．(rear-front+M)%M【答案】D16.对用邻接矩阵表示的连通图进行深度或广度优先遍历时的时间复杂度为（）。A．O(n2)B．O(n)C．O(e2)D．O(e+n)【答案】A17.对用邻接表表示的连通图进行深度或广度优先遍历时的时间复杂度为（）。A.O(n2)B.O(e2)C.O(n+e)D.O(n2)【答案】C18.一棵有124个叶子结点的完全二叉树，至多有（）个结点。A．251B．250C．248D．247【答案】D21.在一个单链表中已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（）。A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;【答案】C22.对关键字集合K={53,30,37,12,45,24,96},从一棵空二叉树开始逐个插入关键字，建立二叉排序树，若希望得到的二叉排序树的高度最小，应选用下列输入序列（）。A.45，24，53，12，37，96，30B.37，24，12，30，53，45，96C.12，24，30，37，45，53，96D.30，24，12，37，45，96，53【答案】B23.有8个结点的无向图最多有（）条边。A．14B.28C.