数据结构复习题目

*)设一组初始记录关键字序列(8，3，6，5，9)，以第一个记录关键字8为基准进行一趟快速排序的结果为5,3,6,5,9*)用快速排序法对序列（22，5，8，20，18，10）进行升序排序，写出每一趟的排序过程。第一趟：{10582018}22第二趟：{85}10{2018}22第三趟：58101820*)从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为___选择排序_______*)内部排序是指排序过程在内存中进行的排序。按照排序过程涉及的存储设备的不同，排序通常可分为内部排序和外部排序。*)用简单选择排序法对关键字序列(46，90，48，30，22，78)进行升序排序，写出每一趟的排序过程。P247答：第一趟：(22)9048304678第二趟：(2230)48904678 第三趟：(223046)904878第四趟：(22304648)9078第五趟：(2230464878)90堆是完全二叉树，完全二叉树不一定是堆正确直接选择排序是一种稳定的排序方法错误（它是一种不稳定的排序方法）堆的形状是一棵__完全二叉树___________*)假设关键字的输入顺序为(12,2,16,30,28,10,16,20,6,18),画出堆排序每趟排序结束后关键字状态。P2702(1)题图片*)简述快速排序算法思想。设要排序的\t"/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/_blank"数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序*)在快速排序、堆排序、归并排序中，____归并排序_____排序是稳定的。快速排序在___被排序的数据完全无序___情况下最易发挥其长处。P246*)希尔排序实质上是采用_分组插入___的方法来实现的。设待排序的关键字序列为{12，26，40，28，30，20，6，18}，试写出使用直接插入排序，每趟排序结束后关键字序列的状态。答初始化关键字（12）2640283020618i=1 （1226）40283020618i=2 （122640）283020610i=3 （12262840）3020610i=4 （1226283040）20610i=5 （122026283040）610i=6 （6122026283040）10i=7 （610122026283040）*)简述插入排序的基本思想每一趟讲一个待排序的记录，安其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素52，则它将依次与表中（20703050）比较大小，查找结果是失败。P231第7题折半查找只适用于有序表，包括有序的顺序表和链表*）适用于折半查找的表的存储方式及元素排列要求为顺序方式存储，元素有序*）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。P230第5题*)散列表的冲突处理方法，按组织形式的不同，分为___________和_____________.*)散列表的平均查找长度取决于装填因子。

*)创建二叉排序树的时间复杂度为______________*)平衡二叉树的左子树和右子树的深度之差的绝对值不超过1*)已知关键字的输入序列为（352348824135725），画出建立平衡排序二叉树的过程。*）对有序表（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找元素42和80，则需要分别依次与哪些元素比较？*）若有18个元素的有序表存放在一维数组A[18]中，第一个元素放A[1]中，现进行折半查找，则查找A［3］的比较序列的下标依次为在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。*）长度20的有序表进行折半查找，则对应的判定树高度为*）对一个有序表：(13，18，24，35，47，50，62)进行折半查找，画出折半查找过程的判定树，并给出查找元素24时，需要依次与哪些元素比较？*)从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为插入排序*)由3个结点可以构造出（）种不同的二叉树*)一个具有1025个结点的二叉树的高h为*)设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（n+1）个。*）利用二叉链表存储树，则根结点的右指针是（）。A．空 B．非空C．指向最左孩子 D．指向最右孩子*)用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。A．栈 B.队列 C.树 D．图*)在下列存储形式中，（）不是树的存储形式？A．双亲表示法 B．孩子链表表示法C．孩子兄弟表示法 D．顺序存储表示法*)二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是*)深度为h的满m叉树的第k层有（）个结点。(1=<k=<h)mk-1 B．mk-1 C．mh-1 D．mh-1*)n（n≥2）个权值均不相同的字符构成哈夫曼树，以下关于该树的叙述中，错误的是（）。A．该树一定是一棵完全二叉树B．树中一定没有度为1的结点C．树中两个权值最小的结点一定是兄弟结点D．树中任一非叶结点的权值一定不小于下一层任一结点的权值*）拓扑排序算法能判断有向图中存在环*)一棵完全二叉树上有1001个结点，则该二叉树中度为1的结点个数是，叶子结点的个数是，二叉树的高度是。*)某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为*)设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点*)在一个图中，所有顶点的度数之和等于图的边数的（）倍*)具有n个顶点的有向图最多有（）条边。*)若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图*)已知图的邻接表如右图所示，则从顶点v0出发的按照深度优先遍历的结果是（）*）Kruskal算法适合构造一个稀疏图G的最小生成树，Prim算法适合构造一个稠密图G的最小生成树*)有很少条边或弧的图称为稀疏图,反之称为稠密图*)p1882（1）邻接矩阵和邻接表*)简述迪杰斯特拉算法思想。*)简述图的广度优先搜索算法思想。*)简述克鲁斯卡尔算法思想。*)度为2的有序树是二叉树*)存在这样的二叉树，其任何次序的遍历结果都相同*)图的广度优先搜索树是惟一的。*)图的深度优先遍历类似于二叉树的_________*)G是一个非连通无向图，共有28条边，则该图至少有（）个顶点*)存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 *)完全二叉树某结点有右子树，则必然有左子树。 *)图的深度优先序列和广度优先序列不是惟一的。 *)邻接表只能用于存储有向图。 *)从源点到终点的最短路径是唯一的。 *)强连通图的各顶点间均可达。*)完全二叉树某结点有右子树，则必然有左子树。 *)稀疏矩阵压缩存储后，必会失去随机存取功能。 *)图的广度优先搜索树是惟一的。 *)图的生成树是惟一的。 *)无向图的连通分量是其极小连通子图。 *)二叉树中每个结点的两棵子树的高度差等于1。 *)具有12个结点的完全二叉树有5个度为2的结点。 *)哈夫曼树中没有度数为1的结点。 *)中序遍历一棵二叉排序树可以得到一个有序的序列。 *)二叉树的先序、中序、后序遍历*)在用二叉链表存储一棵二叉树时，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有_和_______个指针是空指针。*)图有、等存储结构，遍历图有、等方法。*)在无向图G的邻接矩阵A中，A[i][j]=1，则A[j][i]=*)一棵完全二叉树有128个结点，则该完全二叉树的深度为，叶子结点的个数为________。*)一棵完全二叉树上有500个结点，则该二叉树中度为1的结点个数是，叶子结点的个数是，二叉树的高度是。*)遍历图的基本方法有遍历和遍历两种，其中可以借助栈实现的是遍历，可以借助队列实现的是遍历。*)具有10个顶点的无向图，边的总数最多为________。*)二叉树的后序遍历是CBEDA，中序序列是BCADE，则该二叉树的树根是，根结点的左孩子是，右孩子是，二叉树的先序序列为。*)一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的先序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。*)树结构中根节点________双亲结点，其余每个结点都有个双亲结点；叶子结点孩子结点，其余每个结点都有至少个孩子结点。*)在一个图中，所有顶点的度数之和等于所有边数的______倍。*)度为2的树与二叉树有何区别？*)简述连通图的生成树的定义*)一份电文中有6种字符：A,B,C,D,E,F，它们的出现频率依次为6，5，9，13，30，1，画出对应的哈夫曼树（要求每个结点左孩子的频率不高于右孩子的频率）；计算其带权路径长度WPL*)已知如图所示的无向网，请画出它的最小生成树(两个算法都要掌握)。*)假设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC，画出这棵二叉树，求这棵二叉树的后序序列。*)已知如图所示的有向图，请给出：每个顶点的入度和出度、邻接矩阵和邻接表。*)P17(1)(2),(3)(4)(5)(6)*)逻辑结构的四种基本关系。*)数据结构主要包括哪三方面内容*)逻辑结构与存储结构的关系。*)线性结构与非线性结构的不同点。*)评估算法的优劣，通常从复杂度和复杂度两个方面考察。*)数据的逻辑结构分两大类：_____结构和______结构，数据的存储方法主要有两种：存储方法和存储方法。*)程序段“i=1;while(i<=n)i=i*3;”的时间复杂度为。*)线性结构中元素之间是关系，树结构中元素之间是关系，图结构中元素之间是关系。*)线性表的逻辑结构是，其元素的个数称为线性表的。*)p51(1)(2)(3)(5)(6)(7)(9)(11)(13)*)存储密度*)非空的循环单链表head的尾结点p满足（）。A．p->next==head B.p->next==NULL C.p==NULL D.p==headP83(1)(2)(3)(10)(12)(14)(15)P108(1)(5)(6)(7)(8)(11)(12)(14)(15)判断题：*)数据的逻辑结构是依赖于计算机的。*)顺序存储方式只能用于存储线性结构。*)单链表不是一种随机存储结构*)循环链表不是线性表。*)数组元素的下标值越大，存取时间越长。 *)线性表中的所有元素都有一个前驱元素和后继元素。*)一个递归算法必须包括终止条件和迭代部分。 *)稀疏矩阵压缩存储后，必会失去随机存取功能。 *)空串就是空格串。 *)广义表的元素可以是单原子也可以是子表。*)栈和队列都是受限的线性结构。 *)以链表作为栈的存储结构，出栈必须判别栈空的情况。循环链表不是线性表。1.数据结构包括数据的结构、数据的结构和数据的运算这三个方面的内容。2.在具有n个元素的循环队列中，队满时具有个元素。3.在栈结构中，允许插入、删除的一端称为，另一端称为。*)当有多个函数构成嵌套调用时，按照____________的原则，上述函数之间的信息传递和控制转移必须通过__________来实现。4.广义表(a，(b)，((c，(d))))的长度是，深度是，表头是，表尾是。5.设二维数组A的内存首地址为M，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，则元素A[8,5]的地址为M+；当A按列先存储时，该地址存放的的元素是。设每个字符占一个字节。1.评估算法的优劣，通常从复杂度和复杂度两个方面考察。2.数据的逻辑结构分两大类：_____结构和______结构，数据的存储方法主要有两种：存储方法和存储方法。3.用一个大小为6的数组来实现循环队列时，如果当前front和rear的值分别为3和0，则从队列中删除一个元素，再加入两个元素后，front和rear的值分别为和。2.线性结构中元素之间是关系，树结构中元素之间是关系，图结构中元素之间是关系。3.具有n个元素的循环队列中，队满时有个元素。4.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_______个，树的深度为，树的度为_______。1.数据结构包括数据的结构、数据的结构和数