数据结构基础复习题CIW（ X页）.doc

《数据结构基础复习题CIW（ X页）.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构复习题一、判断题1.线性表的逻辑顺序总是与其物理顺序-•致。（）【答案】错2.线性表的顺序存储优于链式存储。（）【答案】错3.在长度为n的顺序表屮，求第i个元索的育接前驱算法的时间复杂度为0（1）。（）【答案】对4.若一棵二叉树屮的结点均无右孩了，则该二叉树的屮根遍历和后根遍历序列正好相反。（）【答案】错6.内部排序是指排序过程在内存屮进行的排序。（）【答案】对7.当待排序序列初始有序时，简单选择排序的时间复杂性为O（n）。（）【答案】错&用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图屮的顶点个数有关,而与图的边数无关。（）【答案】对9.任何一棵二

2、叉树的叶结点在三种遍历屮的相对次序是不变的。（）【答案】对10.若将一批杂乱无章的数据按堆结构组织起来，则堆屮数据必然按从小到大的顺序线性排列。（）【答案】错14.当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调桀，直到被调報到堆顶位置为II,（）【答案】对15.哈希杏找法屮解决冲突问题的常用方法是除留余数法。（）【答案】错16.对具冇n个结点的堆进行插入一个元索运算的时间复杂度为O（n）0（）【答案】错17.堆排序是一种稳定的排序算法。（）【答案】错18.如果有向图屮各个顶点的度都大于2,则该图中必有冋路。（）【答案】错19.在一个顺序存储的循环队列屮，队头指针指向队头

3、元索的后一个位置。（）【答案】错2L在一棵二叉树屮，假定每个结点只有左了女，没有右了女，对它分别进行前序遍历和屮根遍历，则具有相同的结果。（）【答案】错22.拓扑排序是指结点的值是有序排序的。（）【答案】错25.图的深度优先搜索绘一种典型的冋溯搜索的例了，可以通过递归算法求解。（）【答案】对25.对二叉排序树进行屮根遍历，可得到结点的有序排列。（）【答案】对26.任何一棵二叉树的叶结点在三种遍历屮的相对次序是不变的。（）【答案】对27.边数很少的稀疏图，适宜用邻接矩阵表示。（）【答案】错28.二叉树是一棵无序树。（）【答案】错31.当待排序序列初始有序时，快速排序的时间复杂性为0（n）

4、o（）【答案】错32.顺序表的空间利用率高于链表。（）【答案】对33.采用不同的遍历方法，所得到的无向图的生成树是不同的。（）【答案】对34.有冋路的有向图不能完成拓扑排序。（）【答案】对35.存在这样的二叉树，对它采用任何次序的遍历，结果相同。（）【答案】对36.装载因子是散列表的一个重要参数，它反映了散列表的装满稈度。（）【答案】对37.算法分析的目的是找岀数据结构的合理性。（）【答案】错38•单链表可以实现随机存取。（）【答案】错39.边数很多的稠密图，适宜用邻接矩阵表示。（）【答案】对40.理想情况下哈希查找的等概率杳找成功的平均杏找长度是0（1）。（）【答案】对41.边数很少

5、的稀疏图，适宜用邻接表表示。（）【答案】对42.对于同一纟H•关键字互不相同的记录，若生成二叉排序树时插入记录的次序不同则得到不同形态的二叉排序树。（）【答案】对44.哈希查找法屮解决冲突问题的常用方法是除留余数法。（）【答案】错45•顺序杏找法适用于存储结构为顺序或链接存储的线性表。（）【答案】对46.若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（）【答案】错47.在线性链表屮删除屮间的结点时，貝需将被删结点释放。（）【答案】错48.线性表若采用链式存储表示，在删除时不需要移动元素。（）【答案】对46.对任何用顶点表示活动的网络（A0V网）进行拓扑排序的结果祁

6、是唯一的。（）【答案】错47.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。【答案】对46.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。（）【答案】错53.循环链表的结点与单链表的结点结构完全相同，只是结点间的连接方式不同。（）【答案】对54.能够在链接存储的有序表上进行折半查找，其时间复杂度与在顺序存储的有序表上相同。（）【答案】错55.在一棵二叉树屮，假定每个结点只有左了女，没有右了女，对它分别进行屮序遍历和后序遍历，则具有相同的结果。（）【答案】对56.一个无向连通图的生成树是图的极小的连通子图。（）【答案】对58.快速

7、排序的时间复杂性不受数据初始状态影响，恒为O（nlog2n）0（）【答案】错61.如果无向图屮每个顶点的度都大于等于2,则该图屮必有冋路。（）【答案】对62.顺序存储方式只适用于存储线性表。（）【答案】错63.若一棵二叉树屮的结点均无右孩了，则该二叉树的屮根遍历和后根遍历序列正好相同。（）【答案】对64.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（）【答案】错65.完全二叉树的某结点若无左孩了，则它必是叶结点。（）【答