习题课
填 空
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