07本科-数据结构期末考试B-陈正铭

装

订

线——————————————————————————————————————————————————————————2008－2009学年第二学期 计算机科学学院《数据结构》期末考试试卷（B卷）

注：1、共100分，考试时间120分钟。 2分，共20分） 1．数据是对客观事物的符号的表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的（ 符号总称 ）。 2．抽象数据类型是指一个数学模型以及定义在该模型上的一组( 操作 )。 3. 在顺序表中插入或删除一个元素，需要平均移动（ 表中一半 ）元素，具体移动的元素个数与表长和( 该元素表中位置 ）有关。 4. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的存储地址是（ 110 ）。 5．循环队列的引入是为了克服（ ）。 6．head(tail(head(((a，b)，(c，d)))))= b 。 7．已知一棵完全二叉树共有768个结点，则该树中有（ ）个叶子结点。 8．某二叉树的先序遍历序列是8，

5，1，3，2，4，6，7，10，9，11 ，中序遍历序列是1，2，3，4，5，6，7，8，9，10，11，则其后序遍历序列是（ ）。 9．有向图G用邻接矩阵存储，其第i列的所有元素之和等于顶点i的（ 度数 ）。 10．对n个待排序记录序列进行快速排序，其最好时间复杂度为（ ）。 2分，共10分） 1．算法是指 （ A ） A．对特定问题求解步骤的一种描述，是指令的有限序列 B．计算机程序 C．解决问题的计算方法 D．数据处理 2．若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（ A ）存储方法最节省时间。 A．顺序表 B．单链表 C．双链表 D．单循环链表