07本科-数据结构期末考试b答案-陈正铭.doc

2008－2009学年第二学期 计算机科学学院《数据结构》期末考试试卷（B卷） 答案与评分标准 年级：07级 专业： 班级： 学号： 姓名： 题号 一 二 三 四 五 六 总分 签名 得分 注：1、共100分，考试时间120分钟。 2、此试卷适用于计算机科学与技术本科、信息管理与信息系统专业。 一 得 分 阅卷教师 一、填空题（本题共10小题，每个空2分，共20分） 1．数据是对客观事物的符号的表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的（ 符号的总称 ）。 2．抽象数据类型是指一个数学模型以及定义在该模型上的一组( 操作 )。 3. 在顺序表中插入或删除一个元素，需要平均移动（ 表中一半 ）元素，具体移动的元素个数与表长和( 该元素在表中的位置 ）有关。 4. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的存储地址是（ 110 ）。 5．循环队列的引入是为了克服（ 假溢出 ）。 6．head(tail(head(((a，b)，(c，d)))))= b 。 7．已知一棵完全二叉树共有768个结点，则该树中有（ 384 ）个叶子结点。 8．某二叉树的先序遍历序列是8，5，1，3，2，4，6，7，10，9，11 ，中序遍历序列是1，2，3，4，5，6，7，8，9，10，11，则其后序遍历序列是（2，4，3，1，7，6，5，9，11，10，8）。 9．有向图G用邻接矩阵存储，其第i列的所有元素之和等于顶点i的（ 入度 ）。 10．对n个待排序记录序列进行快速排序，其最好时间复杂度为（ O（log2n） ）。 二 得 分 阅卷教师 二、选择题（本题共5小题，每个空2分，共10分） 1．算法是指 （ A ） A．对特定问题求解步骤的一种描述，是指令的有限序列 B．计算机程序 C．解决问题的计算方法 D．数据处理 座位号 2．若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（ A ）存储方法最节省时间。 A．顺序表 　　 B．单链表 C．双链表　　D．单循环链表 3．二叉树的先序序列和后序序列正好相反，则该棵二叉树一定是（ C ）的二叉树。 A．空或只有一个结点 B．任一结点无左孩子 C．高度等于其结点数 D．任一结点无右孩子 4．任何一个无向连通图的最小生成树有 （ A ） A．一棵或多棵 　B．只有一棵 　C．一定有很多棵 　D．可能不存在 5．二叉排序树中，最小值的结点的 （ B ） A．右指针一定为空 　 B．左指针一定为空 C．左、右指针均一定为空 　 D．左、右指针均不为为空 三 得 分 阅卷教师 三、名词解释(本题共小题，每小题分，共分 四、简答题与应用题(本题共小题，每小题分，共分– 1 （3分） 由此， n0 = 1 + 0*n1 + 1*n2 + …… + (k-1)*nk = （2分） 6、有一图的邻接矩阵如下，用Floyd算法求各点间最短距离的矩阵序列A4。 0 2 ∞ ∞ A0＝ ∞ 0 1 6 5 ∞ 0 4 3 ∞ ∞ 0 解： 0 2 3 7 A4＝ 6 0 1 5 5 7 0 4 3 5 6 0 7、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 解：ASL＝（1+2*2+3*4+4*3）/10＝2.9 （3分） （4分） 五 得 分 阅卷教师 五、程序填空：（共2小题 六 得 分 阅卷教师 六、(共分 解： int last=-32767,flag=1; （1分） int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 { if(T-lchildflag) Is_BSTree(T-lchild); （1分） if(T-d