2008下数据结构试卷a.doc

武汉大学测绘学院 2008-2009学年度第一学期期末考试 《数据结构与数据库》课程试卷( A卷) 出题者虞晖 刘进 审核人 班级 学号 姓名 成绩 一、选择题：(以下各题只有一个正确答案，请将代表正确答案的字母填入括号内。) （本大题共6个小题，每小题3分，共18分。） 1．以下属于逻辑结构的是（ ）。 A．顺序表 B. 哈希表 C.有序表 D. 单链表 2. 链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 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 5．具有10个叶结点的二叉树中有（ ）个度为2的结点， A．8 B．9 C．10 D．ll 6．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d), (e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,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．设二叉树BT的存储结构如下: 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）写出按前序、中序、后序遍历该二叉树所得到的结点序列; 2.以数据集{3,4,5,8,12,18,20,30}为叶结点，构造一棵哈夫曼树，并求其带权路径长度。 四、问答题（每题8分，共16分） 1．数据库的主要数据模型有哪三种？试比较它们的优缺点。 2．说明在线性表的链式存储结构中，头指针与头结点之间的根本区别。 五．编程题：根据题目要求编写程序。 （本大题共2个小题，每题9分，共18分。） 1. 编写一个递归算法，计算以BT为树根指针的二叉树的叶子数。并写出调用过程。 int leaf(BTree BT, int count) 其中二叉树的数据类型定义如下： typedef struct BiTNode { TElemType data