还剩4页未读,继续阅读
文本内容:
计九州ZH05200520《数据结构》复习
一、填空题、空串的长度是,空格串的长度是串中包含的容格的个数
1、队列是一种先进先出表,在队列中允许插入的一端称限屋,允许删除的另一端称队头
2、两串相等是指两个字符串的长度相笠,且各对应位置上的字符相等
3、组成数据的最小单位是教据项
4、线性结构中元素之间存在一对一的关系,树形结构中元素之间存在一对多的关系,图形5结构中元素之间存在多对多的关系、向栈中压入元素的操作是先移动栈顶指针,后存入元素
6、栈的逻辑结构是线性结构,其特点是后进先出,先进后出,栈中允许插入和删除的一端7称栈顶、在双向链表中,每个结点有两个指针域,一个指向前驱结点,另一个指向后继结点
8、数据结构通常包括四种基本结构集合、线性结构、树形结构、图形结构、线性表
9、线性表忠…称表头元素,称表尾元素,线性表有两种存储结构顺序存储结构10ai ak,ai ann和链式存储结构、在一个顺序存储的线性表中,第个元素的地址是每个元素的长度为则第个元素111100,2,5的地址是
108、在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有个前驱结点;最后一个12L结点没有后续结点,其余每个结点有且只有个后续结点L
二、选择题、具有个顶点的无向图至少应有条边才能确保是一个连通图16A、A dB.c C.b D.e、在初始状态为空的堆栈中依次插入元素后,连续进行了三次删除操作,则此时的栈2f,e,d,c,a,b顶元素是D、、、、A5B6C7D
8、后序遍历的顺序是3D、根结点,左子树,右子树、左子树,根结点,右子树A B、右子树,根结点,左子树、左子树,右子树,根结点C D、设结点有左孩子结点右孩子结点用三种基本遍历方法得到的遍历序列中是的前4X Y,Z,X BY驱,是的后继,是的前驱X BZ YA Z、一定,、不一定、一定不A BC、串是指5B、少于一个字母的序列、有限个字符的序列、不少于一个字符的序列、任意A BC D个字母的序列、一个栈的输入序列为则下列序列中不可能是栈的输出序列的是61,2,3,4,C、、、、A2,3,4,1,5B2,3,1,4,5C5,4,1,2,3D1,5,4,3,
2、如果结点有个兄弟,且是的双亲,则的度是7A3B A B A、、、、A4B5C1D
3、通常对数组进行的两种基本操作是8C、插入和删除、索引和修改、查找和修改、删除和修改A BC D、一个队列的入队序列是则队列的输出序列是91,2,3,4,B、、、、A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,
1、计算机算法必须具备输入、输出和等五个基本特性10B、可行性、可移植性、和可扩充性、可行性、确定性和可穷性、确定性、可穷必和稳定性A BC、易读性、稳定性和安全性D、树最适合用来表示11C、有序数据元素、无序数据元素、元素之间具有分支层次关系的数据、元素之间无联系的A BC D数据、排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,12将其放入已排序的正确位置上的方法,称为(©_、希尔排序、起泡排序、插入排序、选择排序A BC D、个顶点的强连通图至少有()条边13N A、、、、()A NB N+l CN-l DN N-
1、栈通常采用的两种存储结构是()14A、顺序存储结构和链表存储结构、散列方式和索引方式、链表存储结构和数组、线性存储A BC D结构和非线性存储结构、深度为的二叉树至多有()个结点154D、、、、A8B16C7D
15、对线性表进行二分查找时,要求线性表必须()16C、以顺序方式存储、以链接方式存储、以顺序方式,且结点按关键字有序排序、以链接方A BC D式存储,且结点按关键字有序排序、线性表的顺序存储结构是一种()的存储结构、17A、随机存取、顺序存取、索引存取、散列存取A BC D、串是一种特殊的线性表,其特殊性体现在()18B、可以顺序存储、数据元素是一个字符、可以链接存储、数据元素可以是多个字符A BC D、任何一个无向连通图的最小生成树有19B、只有一棵、有一棵或多棵、一定有多棵、可能不存在A BC D、在一棵非空二叉树的中序遍历序列中,根结点的右边20A、只有右子树上的所有结点、只有右子树上的部分结点、只有左子树上的部分ABC结点、只有左子树上的所有结点、D
三、试分别按先根遍历,中根遍历,后根遍历法写出二叉树的遍历序列顶点入度出度度ABDHIEJCFG2131HDIBEJAFCG2242HIDJEBFGCA1343@3032355四
123、6
六、用Dijkstra算法求图中VI到其余各顶点的最短路径
五、给出图中每个顶点的入度,出度和顶点的度
七、已知无向图,试给出:
1.从A出发的“深度优先”遍历序列
2.从A出发的“广度优先”遍历序列
3.该图是连通图吗?答
①ABDCEGF
②ABCDEFG
③是
八、对照图未的树回答下列问题
1.树中哪些是叶结点?哪个是根结点?答叶结点D MN FJ KL;根结点A
2.结点C的双亲结点是哪一个?A
3.结点C的孩子有哪些?F GH
4.哪些是G的兄弟?F、H
⑤C的深度是多少?3
⑥树的深度是多少?5
⑦E的子孙哪些?I MN哈夫曼树,并算出带权路径长度WPL
十、对于给定的一组权W={14,15,7,4,20,13,5,8,10,试画出一棵答WPL=292
十二、对于给定的一组权值归{14,15,7,4,20,3},试给出哈夫曼树,并算出带权路径长度WPL答:WPL=1473。