《数据结构》复习 .docx

《《数据结构》复习 .docx》由会员分享，可在线阅读，更多相关《《数据结构》复习 .docx（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结一、填空题：ZH 计 0520九州 0520数据结构复习可编辑资料 - - - 欢迎下载精品名师归纳总结1、空串的长度是 0，空格串的长度是串中包含的容格的个数。2、队列是一种先进先出表，在队列中答应插入的一端称队尾，答应删除的另一端称队头。3、两串相等是指两个字符串的长度相等，且各对应位置上的字符相等。4、组成数据的最小单位是数据项。5、线性结构中元素之间存在一对一的关系，树形结构中元素之间存在一对多的关系，图形结构中元素之间存在多对多的关系。6、向栈中压入元素的操作是：先移动栈顶指针，后存入元素。7、栈的规律结构是线性结构，其特点是后进先出，先进后出，栈中答应插入和删除的一

2、端称栈顶。8、在双向链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。9、数据结构通常包括四种基本结构：集合、线性结构、树形结构、图形结构、线性表10、 线性表（ a1,a2.an）k , a1称表头元素，an 称表尾元素，线性表有两种储备结构：次序储备结构和 链式储备结构。11、 在一个次序储备的线性表中，第 1 个元素的的址是 100，每个元素的长度为 2，就第 5 个元素的的址是 108。12、 在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1 个前驱结点。最终一个结点没有后续结点，其余每个结点有且只有1 个后续结点。二、挑选题1、具有 6 个顶点的无向图至

3、少应有 A 条边才能确保是一个连通图。A、dB.cC.bD.e2、在初始状态为空的堆栈中依次插入元素f,e,d,c,a,b 后，连续进行了三次删除操作，就此时的栈顶元素是 DA、5B、6C、7D、8 3、后序遍历的次序是 DA、根结点，左子树，右子树B、左子树，根结点，右子树C、右子树，根结点，左子树D、左子树，右子树，根结点4、设结点 X 有左孩子结点 Y，右孩子结点 Z，用三种基本遍历方法得到的遍历序列中X（B） 是 Y 的前驱， X（ B）是 Z 的后继， Y（A）是 Z 的前驱。A、肯定，B、不肯定C、肯定不5、串是指 BA、少于一个字母的序列B、有限个字符的序列C、不少于一个字符的序

4、列D、任意个字母的序列6、一个栈的输入序列为 1，2，3，4， 就以下序列中不行能是栈的输出序列的是 C A、2， 3， 4，1，5 B、2，3，1，4，5 C、5，4，1，2， 3 D、1，5，4，3，2 7、假如结点 A 有 3 个兄弟，且 B 是 A 的双亲，就 B 的度是 A可编辑资料 - - - 欢迎下载精品名师归纳总结A、4B、5C、1D、38、通常对数组进行的两种基本操作是CA、插入和删除B、索引和修改C、查找和修改D、删除和修改9、一个队列的入队序列是 1， 2， 3， 4，就队列的输出序列是BA、4， 3， 2，1B、1， 2， 3， 4C、1，4，3，2D、3，2 ，4 ，

5、 1 10、 运算机算法必需具备输入、输出和B 等五个基本特性A、可行性、可移植性、和可扩充性 B、可行性、确定性和可穷性 C、确定性、可穷必和稳固性D、易读性、稳固性和安全性11、树最适合用来表示 CA、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据D、元素之间无联系的数据12、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序的正确位置上的方法，称为： （C）A、希尔排序 B、起泡排序 C、插入排序 D、挑选排序13、N 个顶点的强连通图至少有（ A） 条边A、NB、N+1C、N-1D、N（ N-1）14、栈通常采纳的两种储

6、备结构是（ A）A、次序储备结构和链表储备结构 B、散列方式和索引方式 C、链表储备结构和数组 D、线性储备结构和非线性储备结构15、深度为 4 的二叉树至多有（ D）个结点A、8B、16C、7D、1516、对线性表进行二分查找时，要求线性表必需（C）A、以次序方式储备 B、以链接方式储备 C、以次序方式，且结点按关键字有序排序D、以链接方式储备，且结点按关键字有序排序17、线性表的次序储备结构是一种（ A）的储备结构、A、随机存取 B、次序存取 C、索引存取 D、散列存取18、串是一种特别的线性表，其特别性表达在（ B）A、可以次序储备 B、数据元素是一个字符C、可以链接储备 D、数据元素可

7、以是多个字符19、任何一个无向连通图的最小生成树有BA、只有一棵 B、有一棵或多棵 C、肯定有多棵 D、可能不存在20、在一棵非空二叉树的中序遍历序列中，根结点的右边AA、 只有右子树上的全部结点 B、只有右子树上的部分结点 C、只有左子树上的部分结点 D、只有左子树上的全部结点、三、试分别按先根遍历，中根遍历，后根遍历法写出二叉树的遍历序列可编辑资料 - - - 欢迎下载精品名师归纳总结AB先根序列： ABDHIEJCFG DC中根序列： HDIBEJAFCGE后根序列： HIDJEBFGCAHIGJF四、画出含有三个结点的二叉树的全部形状。五、给出图中每个顶点的入度，出度和顶点的度可编辑资

8、料 - - - 欢迎下载精品名师归纳总结145 213 2246顶点 入度 出度 度可编辑资料 - - - 欢迎下载精品名师归纳总结 1 2343 303 235 123可编辑资料 - - - 欢迎下载精品名师归纳总结六、用 Dijkstra算法求图中 V1 到其余各顶点的最短路径8113最短路径长度V1V21332327V1V385307V1V4 经 V31347V1V5 经 V3,V4 196179V1V6 经 V3,V4,V5 21可编辑资料 - - - 欢迎下载精品名师归纳总结526V1V7 经 V220可编辑资料 - - - 欢迎下载精品名师归纳总结七、已知无向图，试给出：1. 从

9、A 动身的“深度优先”遍历序列2. 从 A 动身的“广度优先”遍历序列3. 该图是连通图吗？答： ABDCEGFABCDEFG是B EADGC F八、对比图未的树回答以下问题ACBD FGHEJKLIMN1. 树中哪些是叶结点？哪个是根结点？答：叶结点 D M N F J K L。根结点： A2. 结点 C 的双亲结点是哪一个？ A3. 结点 C 的孩子有哪些？ F G H可编辑资料 - - - 欢迎下载精品名师归纳总结4. 哪些是 G的兄弟？ F、HC的深度是多少？ 3树的深度是多少？ 5E的子孙哪些？ I M N九、用 kruskal算法求图的最小生成树。11421206923211167

10、54162112121116233555142119214221566431569643十、对于给定的一组权 W= 14 ， 15， 7， 4，20，13，5， 8， 10 ，试画出一棵哈夫曼树，并算出带权路径长度 WPL可编辑资料 - - - 欢迎下载精品名师归纳总结答： WPL=29296可编辑资料 - - - 欢迎下载精品名师归纳总结3919209104557273015151314可编辑资料 - - - 欢迎下载精品名师归纳总结78十一、用 Prim 算法求图的最小生成树可编辑资料 - - - 欢迎下载精品名师归纳总结14141411212可编辑资料 - - - 欢迎下载精品名师归纳总结122120911 312673555211116 541421211492162166334545可编辑资料 - - - 欢迎下载精品名师归纳总结十二、对于给定的一组权值W=14，15，7，4，20， 3 ，试给出哈夫曼树，并算出带权路径长度 WP？L答： WPL=147632835152014147734可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载