2008下数据结构试卷A.doc

武汉大学测绘学院
2008-2009学年度第一学期期末考试
《数据结构与数据库》课程试卷( A卷)
出题者虞晖刘进审核人
班级学号姓名成绩
一、选择题:(以下各题只有一个正确答案,请将代表正确答案的字母填入括号内。)
(本大题共6个小题,每小题3分,共18分。)
( )。
B. 哈希表 D. 单链表
2. 链表不具有的特点是( )
、删除不需要移动元素

3. 某堆栈的输入序列为a, b,c ,d,下面的四个序列中,不可能是它的输出序列的是( )。
A. a,c,b,d B. b, c,d,a C. c, d,b, a D. d, c,a,b
4. 数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( )。
A. 1175 B. 1180 C. 1205 D. 1210
( )个度为2的结点,

=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),
(e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是( )。
,b,e,c,d,f ,c,f,e,b,d ,e,b,c,f,d ,e,d,f,c,b

二、填空题:(每空2分,共28分)
1. 在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时,需向后移动_ ______个元素。
2. 对于给定的n个元素,可以构造出的逻辑结构有, , ,__ _四种。
3. 顺序存储结构是通过_ _______表示元素之间的关系的;链式存储结构是通过__ ______表示元素之间的关系的。
4. 设循环队列用数组A[1..M]表示,队首、队尾指针分别是FRONT和TAIL,判定队满的条件为_ ______。
5. 对于一个具有n个顶点和e条边的连通图,其生成树中顶点数和边数分别为和。
6. 广义表运算式Tail(((a,b),(c,d)))的操作结果是。
7. 从一棵二叉搜索树中查找一个元素时,若元素的值等于根结点的值,则表明,若元素的值小于根结点的值,则继续向查找,若元素的值大于根结点的值,则继续向
查找。

三、分析题:(本大题共2个小题,每小题10分,共20分。)
:
1 2 3 4 5 6 7 8 9 10
Lchild
0
0
2
3
7
5
8
0
10
1
Data
J
H
F
D
B
A
C
E
G
I
Rchild
0
0
0
9
4
0
0
0
0
0
其中BT为树根结点的指针,其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:
(l)画出二叉树BT的逻辑结构;
(2)写出按前序、中序