数据结构期末考试题(1)
关于书的格言-最新会计法
命题人：葛建梅 教研室主任（签字）： 系主任签字：
日期：2008年12月5日
课程教研室
班级学号
软件
使用专业
考生姓名
计算机科学与技术（工、师）、软件工程
年级
07级
考试地点
————————¤—————¤———————————装订线——
——————¤———————¤——————
大题得分
大题得分
北华大学计算机科学技术学院2008-2009学年第一学期
《 数据结构
》课程期末考试试卷（ 1 ）
题号 一 二 三 四 五 六 七 八 总分
得分
评卷人 核分：
一、填空题（每题2分，共 14分）
1.
下面程序段的时间复杂度是________。
for (i=1; i
2.
顺序队列在实现时，通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生
____
_________现象。判断一个循环队列队满的条件是__________________（设
代表队头静态指针，代表队尾静态指针，Maxsize代表该循环队列的空间大小）。
3. 在一
个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动
________
_个元素。
4．
如果某二叉树的先序遍历序列为abcde，中序为badec，那么该二叉树的后序为________。
5. 一棵二叉树的第i (i≥1)层最多有_________________个结点；一棵深
度为k的满二叉树
共有_______________个非终端结点。
6. 已知一个有
向图的邻接矩阵表示，计算第i个结点出度的方法是__________________。
删除所有
以第i个结点为弧头的弧的方法是__________________________。
7.
在各种查找方法中，平均查找长度与结点个数n无关的查法方法是______________。
二、选择题 （ 每小题2分，共16分）
1. 数据结构是一门研究非数值计
算的程序设计问题中计算机的___①_____以及它们之间的
___②_____和操作等的学科。
① A．操作对象 B．计算方法 C. 逻辑存储 D．数据映像
② A. 结构 B．关系 C. 运算 D．算法
2. 一个栈的入栈序列是 a，b，c，d，e，则栈的不可能的输出序列是________。
A． abcde B． edcba C
．
edabc D． cbade
第 1 页 共 5 页
命题人：葛建梅
教研室主任（签字）： 系主任签字： 日期：2008年12月5日
课程教研室
班级学号
使用专业
考生姓名
年级
考试地点
————————¤——
———¤—————————装订线————————¤———————¤—————————
大题得分
1题得分
3.
带头结点的单链表L为不空的判定条件是
________。
A.
L－>next =null B. L = null
C. L! = null D. L－>next !=
null
4. 判断下列叙述中哪个不正确
A.
将一棵树转换成二叉树后，根结点没有左子树；
B.
用二叉树的先序遍历和中序遍历可以导出后序遍历；
C.
一棵深度为K且有2
K
-1 个结点的二叉树称为满二叉树
D.
哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近
.
5．按二叉树的定义，具有3个结点的二叉树有
_____种形态
A. 3 B. 4 C. 5
D. 6
6．在一个具有n个顶点的无向图中，要连通全部顶点至少需要
________条边。
A．n B．n+l
C．n-1
D．n／2
7．已知图G如下，求出该图的拓扑排序序列
_________________。
B
A D
E G
C
F H
A．
CABDEFGH B． ABCDEFGH
C． ACBDEFGH D． ACBDFEHG
8．在待排序的元素序列基本有序的前提下，效率最高的排序方法是
________。
A． 插入排序 B． 选择排序
C． 快速排序 D． 归并排序
三、分析解答（1至4小题每题6分，5至6小题每题
8 分，共 40 分）
1．二维数组A的每个元素是由4个字符组成的串，行下标的范围从
0~9，列下标的范围是
从0~9，则存放A至少需要多少个字节，A
的第
3列和第7行共占多少个字节，若A按
行优先方式存储，元素A[6][3]的起始地址与当
A按列优先方式存储时的哪个元素的起始
地址一致。
第 2 页 共 5 页
命题人：葛建梅 教研室主任（签字）： 系主任签字：
日期：2008年12月5日
课程教研室
班级学号
使用专业
考生姓名
年级
考试地点
————
————¤—————¤—————————装订线————————¤———————¤————————
已知一棵树如下图，请将此树转化为对应的二叉树，画出转化后的二叉树及二叉链表。
2.
2题得分
3题得分
4题得分
5题得分
6题得分
A
B CDE
F G
3.
已知某系统在通信联络中出现的abcdef
六种字符，其频率为（13，12，35，15，9，16），
试构造一棵Huffman树，并写出每种字符的Huffman编码。
4
．已知关键字序列{503，17，512，908，897，275，170，653，426
}，请给出采用希尔排
序法（d1=4,d2=2,d3=1）对该序列作升序排列时的每一趟的结果。
5.
已知AOE网如下，按关键路径算法:
（1） 找出其关键路径。 （2） 计算：Ve (v5)、 Vl (v3)
（3） 设
V2
18
6
V3
11
8
V1
1
V4
12
24
25
5
V5
V8
V6
20
12
V7
5
6
．依据下列关键字序列{25，15，21，23，40，48，32，22}构成一棵二叉排序树。
（1）请画出此二叉排序树。
（2）若在二叉排序树中查找，则查找成功与查找不成功的平均查找长度分别是多少？
第 3 页 共 5 页
命题人：葛建梅
教研室主任（签字）： 系主任签字： 日期：2008年12月5日
课程教研室
班级学号
使用专业
考生姓名
年级
考试地点
————————¤—————¤——
———————装订线————————¤———————¤————————
大题得分
1题得分
2题得分
四、算法设计（每小题
10 分，共 30 分）
1.
某大学图书馆中有一批图书，按其价格从低到高的次序构成了一个单链表存于计算机中，
链表的每个结点指出同样价格书的数量，现在要清理书库，
将价格为C元的图书清出
库，
即从单链表中删除价格为C元的结点。单链表存储结构与按此存储结构的算法如下，请
在空格上填写适当的语句，完成该算法。
typedef
struct LNode
{ float cost;
int num;
Struct LNode *next;
} LNode,
*LinkList；
void Delbooks ( LinkList &L,
float c)
{ q=L; p=q->next;
while ( ① && p !=null
)
{ q=p; p=p->next; }
if (
p!=null )
{ ②
③ } }
2.
设二叉树采用二叉链表存储结构，PrintElement
是对数据元素打印输出的应用函
数。下面
算法是用类C语言描述的，实现了按中序遍历二叉树
T的递归算法，对每个
数据元素调
用函数PrintElement输出该结点的值。请在空格上填写适当的语句，完成该算法
。
typedef struct BiTNode
{ char data;
struct BitNode
*Lchild, * Rchild;
} BitNode,
*BiTree;
第 4 页 共 5 页
命题人：葛建梅 教研室主任（签字）：
系主任签字： 日期：2008年12月5日
课程教研室
班级学号
使用专业
考生姓名
年级
考试地点
————————¤—————¤—————————装订线————————¤—————
——¤—————————
3题得分
Status
InOrderTraverse ( BiTree T)
{ if (
① )
{ if ( InOrderTraverse (
T->Lchild ))
if (
②
)
if (
③
) return OK;
return ERROR
}
else return Ok;
}
Status PrintElement ( char e )
{
④
return Ok
}
3．假设图采用邻接表存储表示，设计一个广度优先遍历算法。图与队列的存储结构如下，
请依据此存储结构用类C语言编写算法。
#define
MAX_VERTEX_NUM 20
void
BFSTraverse(ALGraph G，Status(*Visit)(int v)) {
typedef struct ArcNode
{ int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{ Vertextype
data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef
struct
{ AdjList vertices;
int
vexnum, arcnum;
}ALGraph;
#define
MAXQSIZE 100
typedef struct
{ int
*base;
int front;
int
rear;
}SqQueue;
第 5 页 共 5 页
命题人：葛建梅 教研室主任（签字）： 系主任签字：
日期：2008年12月5日
课程教研室
班级学号
软件
使用专业
考生姓名
计算机科学与技术（工、师）、软件工程
年级
07级
考试地点
————————¤—————¤———————————装订线——
——————¤———————¤——————
大题得分
大题得分
北华大学计算机科学技术学院2008-2009学年第一学期
《 数据结构
》课程期末考试试卷（ 1 ）
题号 一 二 三 四 五 六 七 八 总分
得分
评卷人 核分：
一、填空题（每题2分，共 14分）
1.
下面程序段的时间复杂度是________。
for (i=1; i
2.
顺序队列在实现时，通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生
____
_________现象。判断一个循环队列队满的条件是__________________（设
代表队头静态指针，代表队尾静态指针，Maxsize代表该循环队列的空间大小）。
3. 在一
个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动
________
_个元素。
4．
如果某二叉树的先序遍历序列为abcde，中序为badec，那么该二叉树的后序为________。
5. 一棵二叉树的第i (i≥1)层最多有_________________个结点；一棵深
度为k的满二叉树
共有_______________个非终端结点。
6. 已知一个有
向图的邻接矩阵表示，计算第i个结点出度的方法是__________________。
删除所有
以第i个结点为弧头的弧的方法是__________________________。
7.
在各种查找方法中，平均查找长度与结点个数n无关的查法方法是______________。
二、选择题 （ 每小题2分，共16分）
1. 数据结构是一门研究非数值计
算的程序设计问题中计算机的___①_____以及它们之间的
___②_____和操作等的学科。
① A．操作对象 B．计算方法 C. 逻辑存储 D．数据映像
② A. 结构 B．关系 C. 运算 D．算法
2. 一个栈的入栈序列是 a，b，c，d，e，则栈的不可能的输出序列是________。
A． abcde B． edcba C
．
edabc D． cbade
第 1 页 共 5 页
命题人：葛建梅
教研室主任（签字）： 系主任签字： 日期：2008年12月5日
课程教研室
班级学号
使用专业
考生姓名
年级
考试地点
————————¤——
———¤—————————装订线————————¤———————¤—————————
大题得分
1题得分
3.
带头结点的单链表L为不空的判定条件是
________。
A.
L－>next =null B. L = null
C. L! = null D. L－>next !=
null
4. 判断下列叙述中哪个不正确
A.
将一棵树转换成二叉树后，根结点没有左子树；
B.
用二叉树的先序遍历和中序遍历可以导出后序遍历；
C.
一棵深度为K且有2
K
-1 个结点的二叉树称为满二叉树
D.
哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近
.
5．按二叉树的定义，具有3个结点的二叉树有
_____种形态
A. 3 B. 4 C. 5
D. 6
6．在一个具有n个顶点的无向图中，要连通全部顶点至少需要
________条边。
A．n B．n+l
C．n-1
D．n／2
7．已知图G如下，求出该图的拓扑排序序列
_________________。
B
A D
E G
C
F H
A．
CABDEFGH B． ABCDEFGH
C． ACBDEFGH D． ACBDFEHG
8．在待排序的元素序列基本有序的前提下，效率最高的排序方法是
________。
A． 插入排序 B． 选择排序
C． 快速排序 D． 归并排序
三、分析解答（1至4小题每题6分，5至6小题每题
8 分，共 40 分）
1．二维数组A的每个元素是由4个字符组成的串，行下标的范围从
0~9，列下标的范围是
从0~9，则存放A至少需要多少个字节，A
的第
3列和第7行共占多少个字节，若A按
行优先方式存储，元素A[6][3]的起始地址与当
A按列优先方式存储时的哪个元素的起始
地址一致。
第 2 页 共 5 页
命题人：葛建梅 教研室主任（签字）： 系主任签字：
日期：2008年12月5日
课程教研室
班级学号
使用专业
考生姓名
年级
考试地点
————
————¤—————¤—————————装订线————————¤———————¤————————
已知一棵树如下图，请将此树转化为对应的二叉树，画出转化后的二叉树及二叉链表。
2.
2题得分
3题得分
4题得分
5题得分
6题得分
A
B CDE
F G
3.
已知某系统在通信联络中出现的abcdef
六种字符，其频率为（13，12，35，15，9，16），
试构造一棵Huffman树，并写出每种字符的Huffman编码。
4
．已知关键字序列{503，17，512，908，897，275，170，653，426
}，请给出采用希尔排
序法（d1=4,d2=2,d3=1）对该序列作升序排列时的每一趟的结果。
5.
已知AOE网如下，按关键路径算法:
（1） 找出其关键路径。 （2） 计算：Ve (v5)、 Vl (v3)
（3） 设
V2
18
6
V3
11
8
V1
1
V4
12
24
25
5
V5
V8
V6
20
12
V7
5
6
．依据下列关键字序列{25，15，21，23，40，48，32，22}构成一棵二叉排序树。
（1）请画出此二叉排序树。
（2）若在二叉排序树中查找，则查找成功与查找不成功的平均查找长度分别是多少？
第 3 页 共 5 页
命题人：葛建梅
教研室主任（签字）： 系主任签字： 日期：2008年12月5日
课程教研室
班级学号
使用专业
考生姓名
年级
考试地点
————————¤—————¤——
———————装订线————————¤———————¤————————
大题得分
1题得分
2题得分
四、算法设计（每小题
10 分，共 30 分）
1.
某大学图书馆中有一批图书，按其价格从低到高的次序构成了一个单链表存于计算机中，
链表的每个结点指出同样价格书的数量，现在要清理书库，
将价格为C元的图书清出
库，
即从单链表中删除价格为C元的结点。单链表存储结构与按此存储结构的算法如下，请
在空格上填写适当的语句，完成该算法。
typedef
struct LNode
{ float cost;
int num;
Struct LNode *next;
} LNode,
*LinkList；
void Delbooks ( LinkList &L,
float c)
{ q=L; p=q->next;
while ( ① && p !=null
)
{ q=p; p=p->next; }
if (
p!=null )
{ ②
③ } }
2.
设二叉树采用二叉链表存储结构，PrintElement
是对数据元素打印输出的应用函
数。下面
算法是用类C语言描述的，实现了按中序遍历二叉树
T的递归算法，对每个
数据元素调
用函数PrintElement输出该结点的值。请在空格上填写适当的语句，完成该算法
。
typedef struct BiTNode
{ char data;
struct BitNode
*Lchild, * Rchild;
} BitNode,
*BiTree;
第 4 页 共 5 页
命题人：葛建梅 教研室主任（签字）：
系主任签字： 日期：2008年12月5日
课程教研室
班级学号
使用专业
考生姓名
年级
考试地点
————————¤—————¤—————————装订线————————¤—————
——¤—————————
3题得分
Status
InOrderTraverse ( BiTree T)
{ if (
① )
{ if ( InOrderTraverse (
T->Lchild ))
if (
②
)
if (
③
) return OK;
return ERROR
}
else return Ok;
}
Status PrintElement ( char e )
{
④
return Ok
}
3．假设图采用邻接表存储表示，设计一个广度优先遍历算法。图与队列的存储结构如下，
请依据此存储结构用类C语言编写算法。
#define
MAX_VERTEX_NUM 20
void
BFSTraverse(ALGraph G，Status(*Visit)(int v)) {
typedef struct ArcNode
{ int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{ Vertextype
data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef
struct
{ AdjList vertices;
int
vexnum, arcnum;
}ALGraph;
#define
MAXQSIZE 100
typedef struct
{ int
*base;
int front;
int
rear;
}SqQueue;
第 5 页 共 5 页