四川师范大学-第一学期数据结构期末试题B.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

四川师范大学计算机科学学院计算机科学与技术专业、 网络工程专业、
软件工程专业
－ 第一学期期末考试
数据结构试卷B卷
答卷说明: 1、 本试卷共 7页, 五个大题, 满分 100分, 120分钟完卷。
2、 本次考试为闭卷考试。
3、 本试卷适用于 级 1, 2, 3班。
题号
分数
一
二
三
四
五
总分
总分人
得分
评卷人
一、 单项选择题( 每小题2分, 共20分)
1.
线性表若采用链式存储结构时, 要求内存中可用存储单元的地址【
】。
A．必须是连续的
B．部分地址必须是连续的
D．连续或不连续都能够
C．一定是不连续的
2.
稀疏矩阵一般的压缩存储方法有【
A．二维数组和三维数组
C．三元组顺序表和十字链表
广义表( ( a,b) ,c,d) 的表尾是【
】。
B．三元组顺序表和散列表
D．散列表和十字链表
3.
4.
5.
】。
A．
设有一个足够大的栈, 入栈元素的顺序为 ABCDE,, 则栈的不可能输出序列是【
A．EDCBA B．DECBA C．DCEAB D．ABCDE
在一个链队列中, 假定 front和 rear分别为队首和队尾指针, 则删除一个结点的操作为
c
B．
d
C．(a,b)
D．(c,d)
】。
【
】。
A．front=front->next
C．rear=front->next
B．rear=rear->next
D．front=rear->next
6.
线性表的顺序存储结构是一种【
】的存储结构。
A．随机存取
B．顺序存取
C．索引存取
D．散列存取
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 B第 1页 (共 7页)

7.
在长度为 n的字符串 S的第 i个位置插入另外一个字符串, i的合法值应该是【
】。
A．i＞0
B． i≤n
D．1≤i≤n+1
C．1≤i≤n
8.下列字符串中【
】是串"ABABCDEABX"的子串。
A．"ABC"
B．"BX
D．"A
"
C．"
AB"
C"
9.
设满二叉树的深度为 m, 现采用顺序表示法存储该满二叉树, 每个结点占 L个存储单元, 则
共需要【
】个存储单元。
A. m
B. 2
m
*L
C.
(2
m
-1)*L
D.(2 +1)*L
m
10.有组记录的排序码为( 46, 79, 56, 38, 40, 84) , 则利用堆排序的方法建立的初始堆为
【
】
A.79, 46, 56, 38, 40, 80
C.84, 79, 56, 46, 40, 38
B.84, 79, 56, 38, 40, 46
D.84, 56, 79, 40, 46, 38
得分
评卷人
二、 填空题( 每空2分, 共10分)
1.
有一个 10阶对称矩阵 A, 采用下三角的压缩存储方式, 以行序为主序存储, 每个元素占用的
地址空间为 2, 且 A[0][0]=1, 则 A[8][5]的地址是_______________________________________。
向一个栈顶指针为 hs的链栈中插入一个 s结点时, 应执行的语句有
2.
3.
4.
设三叉树度为 1, 2, 3的结点数分别是 n1,.n2,n3, 则该三叉树的叶子结点数 n0是
循环队列用数组 A[0 .. m-1]存放其元素值, 已知其头尾指针分别是 front和 rear, 其中 front
指向队列头元素的位置, rear指向队列尾元素的下一位置, 则当前队列中的元素个数
是
。
5.
哈夫曼树的结点数目 n与叶结点数目 m满足如下关系
。
得分
评卷人
三、 判断题, 用”×”或”√”确定以下说法错误或正确( 每小题1分, 共10分)
1．对链表进行插入和删除操作时, 不必移动结点。
(
)
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 B 第 2页 (共 7页)

2．在一个有向图的拓扑序列中, 若顶点 a在顶点 b之前, 则图中必有一条弧<a,b>。(
)
3．向一棵平衡二叉树中插入一个结点后, 一定会改变其平衡性。
4．在单循环链表中设置尾指针比设置头指针好。
(
)
(
)
)
)
)
5．向二叉排序树插入一个新结点时, 新结点一定成为二叉排序树的一个叶子结点。(
6．如果两个串含有相同的字符, 则这两个串相等。
7．一个有向图的邻接表和逆邻接表中表结点的个数一定相等。
8．将一棵树转换为二叉树表示后, 该二叉树的根结点没有右子树。
9．串和一般的线性表在运算上没有任何区别。
(
(
(
)
(
)
10.栈和队列都是限制存取点的线性结构。
(
)
得分
评卷人
四、 简答题( 每小题6分, 共30分)
1．什么是队列的”假上溢”现象? 试给出两种解决方法, 并做简单描述。
2、 设某密码电文由8个字母组成, 每个字母在电文中的出现频率分别是7, 19, 2, 6, 32, 3,
21, 10, 试为这8个字母设计相应的哈夫曼编码。
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 B第 3页 (共 7页)

3.给定下列网G:
( 1) 试着画出网 G的最小生成树;
( 2) 画出网 G的邻接矩阵的存储结构图。
4．对给定的关键字序列19,14,23,1,68,20,84,27,55,11,给定哈希函数为H(k)=k%13, 试用拉链
法解决冲突建立哈希表, 并给出查找成功的平均查找长度。
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 B 第 4页 (共 7页)

5．假设一棵二叉树的后序序列为 DCEGBFHKJIA, 中序序列为 DCBGEAHFIJK, 试建立这棵二
叉树, 并画出该二叉树的先序线索二叉树。
得分
评卷人
五、 用类C语言描述下列算法, 并给出必要说明( 共30分)
1.写出求二叉树的叶子结点数目的算法( 本小题8分) 。
//二叉树的存储表示
typedef struct BiTNode{
ElemType data;
Stuct BiTNode * lchild,*rchild;//左右指针标志
}BiTNode,*BiTree
给出算法 Status LeafBiTree( BiTree T), 并给出必要的注释。
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 B第 5页 (共 7页)

2.给出建立不带头结点的单链表 La的算法, 并给出删除该链表中的第 i个结点的算法( 本小题12
分) 。
已知线性表的单链表存储结构如下:
typedef struct Lnode {
ElemType data;
Lnode * next;
}Lnode,*LinkList;
给出算法 Status creatList( LinkList &La);
和算法 Status DeleteList( LinkList &La, int i), 并给出必要的注释。
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 B 第 6页 (共 7页)

3．给出有向图的邻接表建立的算法( 本小题10分, ) 。
已知有向图的邻接表存储结构如下:
#define MAX_VERTEX_NUM 20
typedef
struct ArcNode{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;
typedef struct Vnode{
VertexType
ArcNode
data;
//顶点信息
//指向第一条依附该顶点的弧的指针
*firstarc;
}VNode, AdjList[MAX_VERTEX_NUM ];
typedef struct {
AdjList
vertices;
int
vexnum,arcnum;
//图的当前顶点数和弧数
}ALGraph;
给出算法 Status createDG(ALGraph &G ), 并给出必要的注释。
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 B第 7页 (共 7页)