习题课

填 空

1、对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为 ，双亲结点的编号为 。

2、向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 个元素。 3、在一棵二叉树中，若双分支结点数为5个，单分支结点数为6个，则叶子结点数 为 个。

4、为了实现折半查找，线性表必须采用 方法存储。顺序 5、一种抽象数据类型包括数据对象 和 。

6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__________和_______。

7、数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。

8、队列的插入操作在 进行，删除操作在 进行。 9、二叉搜索树的中序遍历得到的结点序列为____ ____。

10、在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。 11、栈的特点是 。

12、在单链表中，除了首元结点外，任一结点的存储位置由 。

13、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要 条边。 14、深度为k（设根的层数为1）的完全二叉树至少有 个结点，至多 有 个结点。

15、一棵深度为6的满二叉树有 个分支结点和 个叶子结点。 16、一个算法的效率可分为 效率和 效率。 17、队列的特点是 。

18、一棵深度为5的满二叉树中的结点数为 个。

19、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

1

简 答 题

1、已知一组元素为（38，26，62，94，35，50，28，55），画出按元素排列顺序输入生成的一棵二叉搜索树。 答:

2、假设有二维数组A[0..5,0..7]，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算： （1）末尾元素A57的第一个字节地址为；

（2）若按列存储时，元素A47的第一个字节地址为。 (3) 数组A的体积（存储量）；

(4) 若按行存储时，元素A14的第一个字节地址为。

2

3、已知二叉树结点的先序序列是ABCDEFGHIJ，中序序列是CBAEFDIHJG，请画出这棵二叉树。

4、试给出下图所示的有向图的邻接表和邻接矩阵。

5、试给出下图所示的有向图的邻接表和邻接矩阵。 1 答:

3

31 2 5 41 6