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

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

四川师范大学 － 第二学期数据结构
期末考试试题 B1
四川师范大学计算机科学学院电子商务、 教育技术学专业
－ 第二学期期末考试
数据结构试卷B卷
答卷说明: 1.本试卷共9页, 五个大题, 满分100分, 120分钟完卷。
2.本试卷为闭卷考试, 请将所有题目直接做在试卷上。
3.本试卷适用于 级4、 5班。
总分
题号
一
二
三
四
五
总分
人
分数
得分评卷人
一、 单项选择题(每题2分, 共20分, 请将答案填在答题卡中)
答题卡
题
1
6
2
7
3
8
4
9
5
号
答
案
题
号
答
案
10

1．单循环链表的尾结点的指针域的值为(
)。
A)NULL
地址
B)0
C)首结点地址
D)尾结点
2．设有一个足够大的栈, 入栈元素的顺序为wxyz,, 则栈的可能输出序列是(
) 。
A) zwyx
B) ywxz
C) wxyz
D) zxyw
3．设串s1=’ABCDEFG’, s2=’PQRST’, 函数con(x,y)返回x和y串的连接串,
subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串, len(s)返
回串s的长度, 则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的
结果串是:
Ａ)BCDEF
Ｂ)BCDEFG
Ｃ)BCPQRST
Ｄ)BCDEFEF
4．若广义表A=( (a,b,c),(d,e,f)) ,则式子GetHead(GetTail(GetHead(GetT
ail(A))))的值为(
) 。
A) ( a,b,c)
B) (d,e)
C) e
D) f

5．下列程序段的时间复杂度是(
i=1;
) 。
while(i<=n)i*=2;
A) O(1)
B) O(㏒2n)
C) O(n)
D) O(n)
2
6．已知一算术表示式的中缀形式为A＋B*C-D/E, 后缀形式为ABC*+DE/-, 其前
缀形式为(
) 。
A) –A+B*C/DE
C) –+*ABC/DE
B) –A+B*CD/E
D) –+A*BC/DE
7．假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储, 其
基地址为10000, 每个元素占2个存储单元, 那么第32行第58列的元素a[32,
58]的存储地址为(
) 。( 无第0行第0列元素)
Ａ) 16902
C均不对
Ｂ) 16904
Ｃ) 14454
Ｄ) 答案A,B,
8．设满二叉树的深度为m, 现采用顺序表示法存储该满二叉树, 每个结点占L
个存储单元, 则共需要(
)个存储单元。
A)m
B)2
m
*L
C)(2
m
-1)*L
D)(2
m
+1)*L
9．在一个图中, 所有顶点的度数之和等于图的边数的(
) 倍。
D) 4
A) 1/2
B) 1
C) 2
10．若在线性表中采用折半查找法查找元素, 该线性表应该(
) 。
A) 元素按值有序
B) 元素按值有序, 且采用链式
D) 采用顺序存储结构
存储结构
C) 元素按值有序, 且采用顺序存储结构
得分评卷人

二、 填空题(每题2分, 共20分, 请将答案填在答题卡中。)
答题卡
题号
答案
1
6
2
7
3
8
4
9
5
①
②
①
②
①
②
题号
答案
10
①
②
①
②
1．在一个单链表中, 若 p所指结点不是最后结点, 在 p之后插入 s所指结点,
则执行的语句为①
、 ②
。
2．一个算法的效率可分为①
效率和②
效率。
3．在顺序表中访问任意一结点的时间复杂度均为①
, 因此, 顺序
表也称为②
的数据结构。
4．设一棵完全二叉树有700个结点, 则共有
5．具有n个顶点的有向简单图最多有
个叶子结点。
条边。
6．若已知一个栈的入栈序列是1, 2, 3, …, n, 其输出序列为p1, p2, p3, …,
pn, 若p1=n, 则pi为 。
7．三元组表中的每个结点对应于稀疏矩阵的一个非零元素, 它包含有三个数据
项, 分别表示该元素的①
、 ②
和元素值。
8．在一棵平衡二叉排序树中, 每个结点的左子树高度与右子树高度之差的绝对
值不超过______
__。
9．在冒泡、 希尔、 快速和堆排序算法中, 在待排序数据已有序时, 花费时间反
而最多的是
排序。
10、 大多数排序算法都有两个基本的操作①
和②
。
得分
评卷

人
三、 简答题(共5道小题, 其中1-4题每题5分, 第5题10分, 共30分)
1.
已知n阶下三角矩阵A(即当1≤i＜j≤n时, 有aij＝0;当1≤j≤i≤n时,
aij≠0), 按照压缩存储的思想, 能够将其主对角线以下所有元素(包括主对角线)
从第一列开始采用列序为主序依次存放于一维数组B[1..
]中。请写出
下三角任意元素aij(j≤i)在B中的下标k的值的计算公式。( 5分)

2.假设字符 a、 b、 c、 d、 e、 f的使用次数分别是 5, 8, 11, 23, 25, 28, 画出 Huf
fman树, 并根据这棵树写出 a、 b、 c、 d、 e、 f的 Huffman( 哈夫曼) 编码。( 5
分)
3．用序列( 46, 88, 45, 39, 70, 58, 101, 10, 66, 34) 建立一个二叉排序树,
画出该树, 并求在等概率情况下查找成功的平均查找长度。( 5分)

4．已知一个无向图的邻接表如下图所示, 要求: (5分)
( 1) 画出该无向图;
( 2) 根据邻接表, 分别写出用DFS(深度优先搜索)和BFS( 广度优先搜索)
算法从顶点V0开始遍历该图后所得到的遍历序列。
5．若关键字序列为( 47, 7,
29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21) , 取哈希函数为: Hash(ke
y)=keymod11, 给出用链地址法解决冲突所构造的哈希表, 然后求出在等概率
的情况下, 这种方法在查找成功时的平均查找长度。(10分)

得分评卷人
四、 阅读算法并填空( 10分)
如下是一个折半查找算法, 请在画线处填上适当内容, 将算法补充完整。
//查找表存储结构表示
typedefstruct{
ElemType*elem;
intlength;
}Table;
//数据元素存储空间基址
//表长度
intSearch(TableST,KeyTypekey){
//设有序表ST中元素按关键字降序排列, 要求在其中查找其关键字等于k
ey的数据元
//素, 找到则返回该元素在表中的位置, 否则返回0。
low=1;①
while
②
{
mid=(low+high)/2;
ifEQ(key,ST.elem[mid].key) returnmid;
elseifLT(key,ST.elem[mid].key)
③
;

else④
;
}
⑤
;
}//Search

得分评卷人
五、 用类C语言描述下列算法, 并给出必要说明。( 每题10分, 共20分)
1、 已知带表头结点的单链表L, 在该单链表中第i个结点处插入新元素X。
已知线性表的单链表存储结构如下:
typedef struct Lnode {
elemtype data;
Lnode * next;
}Lnode,*LinkList;

2、 设二叉树采用二叉链表存储结构, 试设计一个算法计算一棵给定二叉树的所
有叶子结点的数目。
//二叉树的存储表示
typedef struct BiTNode{
ElemType data;
Stuct BiTNode * lchild,*rchild;//左右指针标志
}BiTNode,*BiTree