练习三。
一、填空：1、设二维数组a[0..m-1][0..n-1]按行优先顺序存储在内存中，每个元素占d个字节，则aij的地址为___loc(a00)+(i*n+j)*d __
2、已知二维数组a8*10中，每个元素占两个字节，元素a12的地址为1000，则元素a00的地址为___976___
3、若数组a定义为a[2..m][2..n]，则元素aij的地址为：__loc(a00)+j*m=i __
4、对于任何一棵二叉树t，如果其终端结点数为n0，度为2的结点数为n2，则有什么样的关系式。
n0=n2+1
5、设x是一棵树，x'''是对应于x的二叉树，则x的先根遍历和x'''的__先序___遍历相同。
6、深度为k的二叉树至多有___6.2^k-1___个结点。
7、对于二叉树来说，第i层上至多有__2^(k-1)__个结点。
8、某二叉树的前序遍历序列为ijklmno,中序遍历序列为jlkinmo,则后序遍历序列为：__lkjnomi __
9、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的孩子编号为：__98___
10、某二叉树的前序和后序正好相反，则该二叉树一定是__高度等于其结点数___二叉树。
11、设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为：_2h-1_
12、设森林t中有4棵树，第一，二，三，四棵树的结点个数分别是n1,n2,n3,n4，那么当把森林t转换成一棵二叉树后，其根结点的右子树上有__ n2+ n3+ n3___个结点。
13、树中结点的最大层次称为树的___深度或高度___
14、由一棵二叉树的前序序列和_中序遍历、由中序和后序遍历序列_，能唯一确定这棵二叉树。
15、高度为5的完全二叉树至少有__ 2^(h-1)__个结点。
16、将一棵树转换成一棵二叉树后，二叉树根结点没有___左___子树。
17、森林的后根遍历序列正是相应二叉树__中根__的遍历序列。森林的先根遍历正是相应二叉树的__先根___遍历序列。
18、哈夫曼树是带权路径长度_最短_最小的二叉树。
19、具有m个叶结点的哈夫曼树共有___2m-1___结点。
20、前序为a,b,c且后序为c,b,a的二叉树共___4___棵。
21、已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为___129___
二、简答：1、在具有n个结点的k（k>=2)叉树的k叉链表表示中，有多少个空指针。
答：n个结点的k叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1
2、已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,给出这棵二叉树的后序遍历序列。
答： ghdbeifca
一、选择。1、在一个图中，所有顶点的度数之和等于图的边数的 (c )倍。
a. 1/2 b.1 c.2 d.4
2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(b )倍。
a. 1/2 b.1 c.2 d.4
3、有8个结点的无向图最多有(b )条边。
a.14 b.28 c.56 d.112
4、有8个结点的无向连通图最少有( c )条边。
a.5 b.6 c.7 d.8
5、有8个结点的有向完全图有(c )条边。
a.14 b.28 c.56 d.112
6、用邻接表表示图进行广度优先遍历时，通常采用(b )来实现算法。
a. 栈 b. 队列 c.树 d.图。
7、用邻接表表示图进行深度优先遍历时，通常采用(a )来实现算法。
a. 栈 b. 队列 c.树 d.图。
8、深度优先遍历类似于二叉树的(a )
a.先序遍历 b.中序遍历 c.后序遍历 d.层次遍历。
9、广度优先遍历类似于二叉树的(d )
a.先序遍历 b.中序遍历 c.后序遍历 d.层次遍历。
10、任何一个无向连通图的最小生成树(a )
a.只有一棵 b.一棵或多棵 c.一定有多棵 d.可能不存在。
二、简答。无向图g有6个结点和9条边，并依次输入这9条边为(0,1),(0,2),(0,4),(0,5),(1,2),(2,3),(2,4),(3,4),(4,5),试从顶点0出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。
答：深度优先搜索法：0-->2-->3-->4-->5-->1
广度优先搜索法：0-->1-->2-->4-->5-->3
一、填空。1、下列关键字序列中(a )是堆。
a.16,72,31,23,94,53
b.94,23,31,72,16,53
c.16,53,23,94,31,72
d.16,23,53,31,94,72
2、堆是一种(b )排序。
a.插入 b.选择 c.交换 d.归并。
3、堆的形状是一棵(c ).
a.二叉排序树 b.满二叉树 c.完全二叉树 d.平衡二叉树。
4、若一组记录的排序码为(46,79,56,38,40,84),则利用堆的方法建立的初始堆为(b )
a. 79,46,56,38,60,86
b.84,79,56,38,40,46
c.84,79,56,46,40,38
d.84,56,79,40,46,38
5、若一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为(c )
a.38,40,46,56,79,84
b.40,38,46,79,56,84
c.40,38,46,56,79,84
d.40,38,46,84,56,79
6、设有100个元素，用折半查找法进行查找的时候，最大比较的次数是(d )
a.15 b.50 c.10 d.7
7、对线性表进行二分查找的时候，要求线性表必须(c )
a.以顺序方式。
b.以链接方式存储。
c.以顺序方式存储，且结点按斗争字有序排列。
d.以链接方式存储，且结点按关键字有序排列。
8、稠密索引是指(c )
a.索引密度大的文件。
b.索引量大的文件。
c.为每个主记录建立一个索引项的文件。
d.为每个页块建立一个索引项的文件。
9、稀疏索引是指(d )
a.索引密度小的文件。
b.索引量小的文件。
c.为每个主记录建立一个索引项的文件。
d.为每个页块建立一个索引项的文件。
数据结构练习
一 选择题 1 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动 个数据元素。a 2.在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行b a.q next p s next p b.s next p q nex...
数据结构练习
第1章。1.从逻辑上可以把数据结构分为。a 动态结构 静态结构 b 顺序结构 链式结构。c.线性结构 非线性结构 d 初等结构 构造型结构。2.关于算法的描述，不正确的是。a.算法最终必须由计算机程序实现。b 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。c.健壮的算法不会因非法的输人数...
数据结构练习
一 选择题。1 广度优先遍历的含义是 从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问，直至图中所有已被访问的顶点的邻接点都被访问到是下图的广度优先遍历序列。a.1 ...