2011-2012学年第一学期期末考查
《数据结构》试卷
（答案一律写在答题纸上，在本试卷上做答无效）
一、选择（每题1分，共10分）
1. 长度为n 的线性表采用顺序存储结构，一个在其第i 个位置插入新元素的算法时间复杂度为（D ）
A.O(0) B.O(1) C.O(n) D.O(n2)
2. 六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（ D ）
A.543612 B.453126 C.346512 D.234156
3. 设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ）
A.8 B.9 C.10 D.11
4. 设森林F 对应的二叉树B 有m 个结点，B 的右子树结点个数为n ，森林F 中第一棵树的结点个数是（ B ）
A. m-n B.m-n-1 C.n+1 D.m+n
5. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）
A.9 B.11 C.15 D. 不确定
6. 下列哪一个方法可以判断出一个有向图是否有环。（ A ）
A. 深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
7. 第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236
8. 分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（ B ）
A. （100,80,90,60,120,110,130） B. （100, 120, 110,130,80, 60,90）
C. （100,60,80,90,120,110,130） D. （100,80, 60,90, 120, 130,110）
9. 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ）
A. 选择排序 B. 起泡排序 C. 快速排序 D. 插入排序
10. 对线性表进行折半查找时，要求线性表必须（ D ）
A. 以顺序方式存储 B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储 D. 以链接方式存储，且数据元素有序
二、填空（每空1分，共15分）
1. 数据结构中评价算法的两个重要指标是、空间复杂度。
2. 在单链表中，指针P 所指结点有后继的条件是。（结点构成：data 和next ）
3. 栈的特点是。
4. 判断循环队列是否队满的条件表达式是。
5. 完全二叉树中的结点个数为n ，则编号最大的分支结点的编号为
6. 如果A 有7个兄弟，而B 是A 的双亲，则B 的度是。
7. 如果二叉树中有20个叶子节点，30个度为1的结点，则该二叉树的总结点数为
8. 设二叉树中每个结点均用一个字母表示，若一个结点的左子树或者右子树为空，用. 表示。现前序遍历二叉树的结点序列为ABD.G …CE.H..F.. ，则中序遍历二叉树的结点序列为 。
9. 若用n 表示图中的顶点数目，则有条边的无向图被称为完全图。
10. 如果具有n 个顶点的图是一个环，则它有
11. 克鲁斯卡尔算法的时间复杂度是
12. 顺序查找n 个元素的线性表，若查找成功时的平均查找长度为
13. 高度为5的完全二叉树，其结点最少有
14. 直接插入排序中使用的监视哨的作用是
三、判断题（每题1分，共10分）
1. 算法独立于具体的程序设计语言，与具体的计算机无关。（ ）
2. 线性表采用链式存储时，结点内部的存储空间可以是不连续的。（ ）
3. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ）
4. 哈夫曼树的结点总个数一定是偶数。（ ）
5. 已知二叉树的先序遍历序列和中序遍历序列，可以画出这棵二叉树（ ）。
6. 有e 条边的无向图，在其对应的邻接表中有e 个结点。（ ）
7. 连通分量指的是无向图的极大连通子图。（ ）
8. 在哈希表的查找过程中的“比较”操作是无法避免的。（ ）
9. 完全二叉树肯定是平衡二叉树。（ ）
10. 堆排序是稳定的排序算法。（ ）
四、简答题（共30分）
1. 线性结构的特点是？（4分）
2. 已知图的邻接矩阵存储如下所示，请根据该邻接矩阵画出对应的图，并给出从A 出发的广度优先搜索序列，以及相应的广度优先生成树。（6分）
A B C D E F
A
B
C
D
E
F 3. 已知一棵二叉树的后序遍历序列为EICBGAHDF ，中序遍历序列为CEIFGBADH ，请画出这棵二叉树，并把这棵二叉树转换成相应的树（或森林）。（6分）
4. 已知电文内容为：ACACBACDAACDBAACADAA ，字符集为A ，B ，C ，D ，设计一套二进制编码，使得上述电文的编码最短。（6分）
5. 已知有序序列{3，7，11，20，45，77，90}，请分别写出折半查找10和查找99的过程，并求出ASL （4分）
6. 已知序列{34，17，6，29，33，11，80，37}请用快速排序的方法进行排序，并给出详细过程。（4分）
五、算法填空（每空5分，共20分）
（1）按先序次序输入二叉树中的结点值(字符) 构造二叉树
Status CreateBiTree(BiTree &T)
{
char ch;
read(ch);
if( ch==' ' )
T = NULL;
else {
T = (BiTree)malloc(sizeof(BiTNode));
CreateBiTree(T->lchild);
}
return OK;
}
（2）在顺序表L 的第 i 个元素之前插入新的元素e
Status ListInsert(SqList &L, int i, ElemType e)
{
if (i L.length+1) return ERROR; // 插入位置不合法
for ( j= L.length ; j>i ; j - - )
L.elem[i-1] = e ; // 插入e
return OK;
} // ListInsert_Sq
六、写算法（共15分）
1. 请写出链式存储的线性表中，删除第i 个位置数据元素的实现算法。（给出相应的结构体定义，关键部分给出注释。）
2011－2012学年第一学期期末考查
《数据结构》标准答案
一、 选择（每题1分，共10分）
1-5 DBBBB 6-10 ACCDB
二、填空（每空1分，共15分）
1. 时间复杂度，空间复杂度
2.FIFO ，LIFO
3.Q.rear==Q.front
4.7
5.8
6.O(n2) ，稠密图
7. 极大连通子图
8.n(n-1)
9.n-1
10. 集合结构，树形结构，图状结构
三、判断题（每题1分，共10分）
1. × 2. √ 3. √ 4. × 5. √ 6. × 7. × 8. × 9. × 10. ×
四、简答题（共30分）
1.
(1)在二叉树的第 i 层上至多有2i-1 个结点； (i≥1)
(2)深度为 k 的二叉树上至多含 2k-1 个结点（k ≥1）；
(3)对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1；
(4)具有 n 个结点的完全二叉树的深度为 ⎣ log2n ⎦ +1 。
(5)若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 ⎣i/2⎦ 的结点为其双亲结点；若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。
评分标准：答对5条中的4条得4分。
2.
深度优先遍历序列：abefdc
深度优先生成树：a-.>b->c->e->f->d->c
评分标准：深度优先遍历序列3
3.(1)T->next->next=P->next;
(2)Q=T;
While(Q->!=P)
{Q=Q->next;}
Q->next=P->next;
free(P);
评分标准：回答（1）或者（2）都正确。4.5.{11，3，7，77，20，45，90}
查找过程：11，3，7，77或者90，45，20，77
6.{34，17，6，29，33，11，80，37}
d=5 11，17，6，29，33，34，80，37
d=3 11，17，6，29，33，34，80，37
d=1 6，11，17，29，33，34，37，80
五、算法填空（每空5分，共20分）
1. (1)visit(T->data); 或者printf(T->data);
(2)PreOrderTraverse(T->rchild);
2.(1)return mid;
(2)high=mid-1;
六、写算法（共15分）
//删除表L 中第i 个元素，结果用e 返回，操作成功返回OK ，失败时返回ERROR Status ListDelete(SqList &L, int i, ElemType &e)
{
if(iL.length)return ERROR;
e=L.elem[i-1];
for(int j=i+1;j
L.elem[j-2]=L.elem[j-1];
L.length--;
return OK;
}
2011-2012学年第一学期期末考查
《数据结构》试卷
（答案一律写在答题纸上，在本试卷上做答无效）
一、选择（每题1分，共10分）
1. 长度为n 的线性表采用顺序存储结构，一个在其第i 个位置插入新元素的算法时间复杂度为（D ）
A.O(0) B.O(1) C.O(n) D.O(n2)
2. 六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（ D ）
A.543612 B.453126 C.346512 D.234156
3. 设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ）
A.8 B.9 C.10 D.11
4. 设森林F 对应的二叉树B 有m 个结点，B 的右子树结点个数为n ，森林F 中第一棵树的结点个数是（ B ）
A. m-n B.m-n-1 C.n+1 D.m+n
5. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）
A.9 B.11 C.15 D. 不确定
6. 下列哪一个方法可以判断出一个有向图是否有环。（ A ）
A. 深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
7. 第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236
8. 分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（ B ）
A. （100,80,90,60,120,110,130） B. （100, 120, 110,130,80, 60,90）
C. （100,60,80,90,120,110,130） D. （100,80, 60,90, 120, 130,110）
9. 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ）
A. 选择排序 B. 起泡排序 C. 快速排序 D. 插入排序
10. 对线性表进行折半查找时，要求线性表必须（ D ）
A. 以顺序方式存储 B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储 D. 以链接方式存储，且数据元素有序
二、填空（每空1分，共15分）
1. 数据结构中评价算法的两个重要指标是、空间复杂度。
2. 在单链表中，指针P 所指结点有后继的条件是。（结点构成：data 和next ）
3. 栈的特点是。
4. 判断循环队列是否队满的条件表达式是。
5. 完全二叉树中的结点个数为n ，则编号最大的分支结点的编号为
6. 如果A 有7个兄弟，而B 是A 的双亲，则B 的度是。
7. 如果二叉树中有20个叶子节点，30个度为1的结点，则该二叉树的总结点数为
8. 设二叉树中每个结点均用一个字母表示，若一个结点的左子树或者右子树为空，用. 表示。现前序遍历二叉树的结点序列为ABD.G …CE.H..F.. ，则中序遍历二叉树的结点序列为 。
9. 若用n 表示图中的顶点数目，则有条边的无向图被称为完全图。
10. 如果具有n 个顶点的图是一个环，则它有
11. 克鲁斯卡尔算法的时间复杂度是
12. 顺序查找n 个元素的线性表，若查找成功时的平均查找长度为
13. 高度为5的完全二叉树，其结点最少有
14. 直接插入排序中使用的监视哨的作用是
三、判断题（每题1分，共10分）
1. 算法独立于具体的程序设计语言，与具体的计算机无关。（ ）
2. 线性表采用链式存储时，结点内部的存储空间可以是不连续的。（ ）
3. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ）
4. 哈夫曼树的结点总个数一定是偶数。（ ）
5. 已知二叉树的先序遍历序列和中序遍历序列，可以画出这棵二叉树（ ）。
6. 有e 条边的无向图，在其对应的邻接表中有e 个结点。（ ）
7. 连通分量指的是无向图的极大连通子图。（ ）
8. 在哈希表的查找过程中的“比较”操作是无法避免的。（ ）
9. 完全二叉树肯定是平衡二叉树。（ ）
10. 堆排序是稳定的排序算法。（ ）
四、简答题（共30分）
1. 线性结构的特点是？（4分）
2. 已知图的邻接矩阵存储如下所示，请根据该邻接矩阵画出对应的图，并给出从A 出发的广度优先搜索序列，以及相应的广度优先生成树。（6分）
A B C D E F
A
B
C
D
E
F 3. 已知一棵二叉树的后序遍历序列为EICBGAHDF ，中序遍历序列为CEIFGBADH ，请画出这棵二叉树，并把这棵二叉树转换成相应的树（或森林）。（6分）
4. 已知电文内容为：ACACBACDAACDBAACADAA ，字符集为A ，B ，C ，D ，设计一套二进制编码，使得上述电文的编码最短。（6分）
5. 已知有序序列{3，7，11，20，45，77，90}，请分别写出折半查找10和查找99的过程，并求出ASL （4分）
6. 已知序列{34，17，6，29，33，11，80，37}请用快速排序的方法进行排序，并给出详细过程。（4分）
五、算法填空（每空5分，共20分）
（1）按先序次序输入二叉树中的结点值(字符) 构造二叉树
Status CreateBiTree(BiTree &T)
{
char ch;
read(ch);
if( ch==' ' )
T = NULL;
else {
T = (BiTree)malloc(sizeof(BiTNode));
CreateBiTree(T->lchild);
}
return OK;
}
（2）在顺序表L 的第 i 个元素之前插入新的元素e
Status ListInsert(SqList &L, int i, ElemType e)
{
if (i L.length+1) return ERROR; // 插入位置不合法
for ( j= L.length ; j>i ; j - - )
L.elem[i-1] = e ; // 插入e
return OK;
} // ListInsert_Sq
六、写算法（共15分）
1. 请写出链式存储的线性表中，删除第i 个位置数据元素的实现算法。（给出相应的结构体定义，关键部分给出注释。）
2011－2012学年第一学期期末考查
《数据结构》标准答案
一、 选择（每题1分，共10分）
1-5 DBBBB 6-10 ACCDB
二、填空（每空1分，共15分）
1. 时间复杂度，空间复杂度
2.FIFO ，LIFO
3.Q.rear==Q.front
4.7
5.8
6.O(n2) ，稠密图
7. 极大连通子图
8.n(n-1)
9.n-1
10. 集合结构，树形结构，图状结构
三、判断题（每题1分，共10分）
1. × 2. √ 3. √ 4. × 5. √ 6. × 7. × 8. × 9. × 10. ×
四、简答题（共30分）
1.
(1)在二叉树的第 i 层上至多有2i-1 个结点； (i≥1)
(2)深度为 k 的二叉树上至多含 2k-1 个结点（k ≥1）；
(3)对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1；
(4)具有 n 个结点的完全二叉树的深度为 ⎣ log2n ⎦ +1 。
(5)若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 ⎣i/2⎦ 的结点为其双亲结点；若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。
评分标准：答对5条中的4条得4分。
2.
深度优先遍历序列：abefdc
深度优先生成树：a-.>b->c->e->f->d->c
评分标准：深度优先遍历序列3
3.(1)T->next->next=P->next;
(2)Q=T;
While(Q->!=P)
{Q=Q->next;}
Q->next=P->next;
free(P);
评分标准：回答（1）或者（2）都正确。4.5.{11，3，7，77，20，45，90}
查找过程：11，3，7，77或者90，45，20，77
6.{34，17，6，29，33，11，80，37}
d=5 11，17，6，29，33，34，80，37
d=3 11，17，6，29，33，34，80，37
d=1 6，11，17，29，33，34，37，80
五、算法填空（每空5分，共20分）
1. (1)visit(T->data); 或者printf(T->data);
(2)PreOrderTraverse(T->rchild);
2.(1)return mid;
(2)high=mid-1;
六、写算法（共15分）
//删除表L 中第i 个元素，结果用e 返回，操作成功返回OK ，失败时返回ERROR Status ListDelete(SqList &L, int i, ElemType &e)
{
if(iL.length)return ERROR;
e=L.elem[i-1];
for(int j=i+1;j
L.elem[j-2]=L.elem[j-1];
L.length--;
return OK;
}