《数据结构》期末考试试卷?/p>
B
卷)?/p>
1
?/p>
?/p>
4
?/p>
2009
?/p>
2010
学年第二学期
计算机科学学院《数据结构》期末考试试卷?/p>
B
卷)
答案与评分标?/p>
年级?/p>
08
?/p>
专业?/p>
班级?/p>
学号?/p>
姓名?/p>
题号
一
?/p>
?/p>
?/p>
总分
签名
得分
注:
1
、共
100
分,考试时间
120
分钟?/p>
2
、此试卷适用于计算机科学与技术本科、信息管理与信息系统专业?/p>
一
?/p>
?/p>
阅卷教师
一?/p>
填空题(本题?/p>
10
小题,每个空
2
分,?/p>
20
分)
1
.在一般情况下,一个算法的时间复杂度是(问题规?/p>
)的函数?/p>
2
.当线性表的元素总数稳定,且很少进行插入和删除运算,但要求以最?/p>
的速度存取线性表中的元素时,应采用(
顺序
)存储结构?/p>
3.
一个具?/p>
n
个结点的单链表,在给定值为
x
的结点后插入一个新结点?/p>
时间复杂度为?/p>
O
?/p>
n
?/p>
?/p>
?/p>
4
.循环队列的引入是为了克服(
假溢出或假上?/p>
?/p>
?/p>
5
.数组通常只有?/p>
存取
)和修改这两种运算?/p>
6
.已知一棵完全二叉树共有
748
个结点,则该树中有(
374
)个叶子?/p>
点?/p>
7
.树
T
?/p>
n
个结点且结点的度均为
k
或?/p>
0
,则树中的叶子结点总数为:
?/p>
n
?/p>
(n-1)/k
?/p>
?/p>
8
.在无向图的邻接矩阵中,?/p>
i
行非零元个数就是?/p>
i
个顶点的?/p>
?/p>
?/p>
?/p>
?/p>
9
.如果待排序序列已接近正序,则在快速排序、堆排序和归并排序之中,
选用?/p>
堆排?/p>
)较为适当?/p>
10
.某二叉树的先序遍历序列?/p>
ABCDEFG
,中序遍历序列是
CBDAFGE
,则?/p>
后序遍历序列是(
CDBGFEA
?/p>
?/p>
?/p>
?/p>
?/p>
阅卷教师
二?/p>
选择题(本题?/p>
10
小题,每个空
2
分,?/p>
20
分)
1
.链表不具有的特点是?/p>
A
?/p>
A
.随机访问任一元素
B
.插入不需移动元素
—————————————?/p>
?
———————————————?/p>
?
———————————————?/p>
?
———————————?/p>