南京工程学院《数据结构》复习资料
《数据结构》复习
一、填空题:
1、 空串的长度是0,空格串的长度是串中包含的容格的个数。
2、 队列是一种先进先出
,在队列中允许插入的一端称队尾,允许删除的另一端称队头。 3、 两串相等是指两个字符串的长度相等,且各对应位置上的字符相等。 4、 组成数据的最小单位是数据项。
5、 线性结构中元素之间存在一对一的关系,树形结构中元素之间存在一对多的关系,图形
结构中元素之间存在多对多的关系。
6、 向栈中压入元素的操作是:先移动栈顶指针,后存入元素。
7、 栈的逻辑结构是线性结构,其特点是后进先出,先进后出,栈中允许插入和删除的一端
称栈顶。
8、 在双向链表中,每个结点有两个指针域,一个指向前驱结点,另一个指向后继结点。 9、 数据结构通常包括四种基本结构:集合、线性结构、树形结构、图形结构、线性表 10、 线性表(aa.a)k , a称表头元素, a称表尾元素,线性表有两种存储结构:顺1 ,2….n1 n
序存储结构 和 链式存储结构。
11、 在一个顺序存储的线性表中,第1个元素的地址是100,每个元素的长度为2,则第5个
元素的地址是108。
12、 在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点;最后
一个结点没有后续结点,其余每个结点有且只有1个后续结点。
二、选择题
1、 具有6个顶点的无向图至少应有A条边才能确保是一个连通图。
A、d B.c C.b D.e
2、在初始状态为空的堆栈中依次插入元素f,e,d,c,a,b后,连续进行了三次删除操作,则此时的栈顶元素是D
A、5 B、6 C、7 D、8
3、后序遍历的顺序是D
A、根结点,左子树,右子树 B、左子树,根结点,右子树
C、右子树,根结点,左子树 D、左子树,右子树,根结点
4、设结点X有左孩子结点Y,右孩子结点Z,用三种基本遍历方法得到的遍历序列中X (B) 是Y的前驱,X(B)是Z的后继,Y(A)是Z的前驱。
A、一定, B、不一定 C、一定不
5、串是指B
A、少于一个字母的序列 B、有限个字符的序列 C、不少于一个字符的序列 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、4 B、5 C、1 D、3
8、通常对数组进行的两种基本操作是C
A、插入和删除 B、索引和修改 C、查找和修改 D、删除和修改
9、一个队列的入队序列是1,2,3,4,则队列的输出序列是B
A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2 ,4 ,1 10、 计算机算法必须具备输入、输出和B等五个基本特性
A、可行性、可移植性、和可扩充性B、可行性、确定性和可穷性C、确定性、可穷必和稳定性D、易读性、稳定性和安全性
11、树最适合用来表示C
A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据
12、排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序的正确位置上的方法,称为:(C)
A、希尔排序B、起泡排序C、插入排序D、选择排序
13、N个顶点的强连通图至少有 (A) 条边
A、N B、N+1 C、N-1 D、N(N-1)
14、栈通常采用的两种存储结构是(A) H A、顺序存储结构和链表存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存储结构和非线性存储结构
15、深度为4的二叉树至多有(D)个结点
A、8 B、16 C、7 D、15
16、对线性表进行二分查找时,要求线性表必须(C)
A、以顺序方式存储B、以链接方式存储C、以顺序方式,且结点按关键字有序排序D、以链接方式存储,且结点按关键字有序排序
17、线性表的顺序存储结构是一种(A)的存储结构、
A、随机存取B、顺序存取C、索引存取D、散列存取
18、串是一种特殊的线性表,其特殊性体现在(B)
A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符 19、任何一个无向连通图的最小生成树有B
A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在
20、在一棵非空二叉树的中序遍历序列中,根结点的右边A
A、 只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分
结点D、只有左子树上的所有结点、
三、试分别按先根遍历,中根遍历,后根遍历法写出二叉树的遍历序列
A
先根序列:ABDHIEJCFG B
C 中根序列:HDIBEJAFCG D
E 后根序列:HIDJEBFGCA
H I G
J F
四、画出含有三个结点的二叉树的所有形态。
五、给出图中每个顶点的入度,出度和顶点的度
1 4
顶点 入度 出度 度
5
? 2 1 3
6 ? 2 2 4
2 3 ? 1 3 4
? 3 0 3
? 2 3 5
? 1 2 3
六、用Dijkstra算法求图中V1到其余各顶点的最短路径
8 13 最短路径 长度 1
V1 V2 13
3 2
32 7 V1 V3 8
5 30 7 V1 V4(经V3) 13
4 7 V1 V5(经V3,V4) 19
6 17 9 V1 V6(经V3,V4,V5) 21
5 6 2 V1 V7(经V2) 20
七、已知无向图,试给出:
1.从A出发的“深度优先”遍历序列
2.从A出发的“广度优先”遍历序列
3.该图是连通图吗,
答:?ABDCEGF?ABCDEFG?是
B E
A D G
C F
八、对照图未的树回答下列问题
A
C B
D F G H E
L J K I
M N
1.树中哪些是叶结点,哪个是根结点,
答:叶结点D M N F J K L;根结点:A
2.结点C的双亲结点是哪一个,A
3.结点C的孩子有哪些,F G H
4.哪些是G的兄弟,F、H
?C的深度是多少,3
?树的深度是多少,5
?E的子孙哪些,I M N
九、用kruskal算法求图的最小生成树。
14 1 2
1 20 9 2 6 3
21 11 6 7
5 4
16
2 1 2 2 1 1
1 1 1 6 2 3 3
5 5 1 5 4
2 1 2 1 9 2 14 2
1 6 1 9 6 6 3 6 3 4 5 5 4
十、对于给定的一组权W={14,15,7,4,20,13,5,8,10},试画出一棵
哈夫曼树,并算出带权路径长度WPL
答:WPL=292
96
39 57
20 19 30 27
9 15 10 15 13 14
4 5
7 8
十一、用Prim算法求图的最小生成树
14 14 14 1 1 2 1 2
1 2 2
1 20 9 1 1 1 2 3
7 6 3 5 5 5
21 11
5 4 16
14 2 1 2 1
14 9 2
6 3 1 6 2 1 6
3
4 5 4 5
十二、对于给定的一组权值W={14,15,7,4,20,3},试给出哈夫
曼树,并算出带权路径长度WPL,
答:WPL=147
63
28
35
15 20 14 14
7 7
3
4