数据结构期中测试

姓名

学号

一、单项选择题:（每小题3分，本大题共60分）

一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是（）

在一个长度为n的顺序表中第i个位置插入一个元素的算法时间复杂度为（ ）。

将一个由指针p所指向的结点插入到单链表L中由指针q所指向的结点后面，则需要执行的语句为（  ）。

一般计算机提交打印作业的速度比打印机打印的速度要快很多，为了解决速度不匹配问题，需要在计算机中设置一个打印缓冲区。打印缓冲区的实现一般采用（）。

用链表表示线性表的优点是（  ）。

使用一维数组压缩存储n阶上三角矩阵时，常数c在一维数组中的索引位置为（  ）。

设有串t=”computer software”，那么Substring(t,6,6)=（  ）。

一个广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（  ）。

利用孩子-兄弟法表示树时，其二叉链表的根结点的右指针是（  ）。

若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（  ）。

设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（  ）。

头指针为head的带头结点的单链表为空的判定条件是（  ）。

在大小为 size 的循环队列中，队列满的判定条件是（  ）

广义表 G=(a,G) 的深度是（  ）。

树的后根遍历结果与其孩子-兄弟法所表示的二叉树的后序遍历结果是一样的,这种说法是（  ）。

深度为k的完全二叉树若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（  ）。

某二叉树的先序遍历结点访问顺序是ABDGCEFH，中序遍历的结点访问顺序是DGBAECHF，则其后序遍历的结点访问顺序是（ ）。

已知某二叉树的后序遍历序列是DABEC，中序遍历序列是DEBAC，它的先序遍历序列是（）。

设一棵完全二叉树中有999个节点，用二叉链表做存储结构，则有多少个空指针域（）。

20、已知一棵完全二叉树共有50个结点，则叶子结点的个数为（）。

二、简答题:（本大题共20分）

已知一个6*5稀疏矩阵如图所示，试采用三元组表作为存储结构，写出它的行优先三元组线性表（5分）。

请画出下列森林对应的二叉树。（5分）

假定用于通信的电文由5个字母A、B、C、D、E组成，若电文为“ADCEBDBCACADEEEEDAED”，试通过构造最优二叉树求出每个字符的Huffman编码。要求：

三、算法设计题:（本大题共20分）

简要说明下列算法的主要功能。（5分）

有一个线性表(a1，a2，…，an)，它存储在带有表头结点的单链表中，写一个算法，求出该线性表中值为x的元素的序号。如果x不存在，则输出序号为0。（15分）