福建农林大学数据结构考试试卷3(附答案)

福建农林大学考试试卷评分标准福建农林大学考试试卷评分标准 （A）卷）卷 2007 2008 学年 第 一 学期 课程名称： 数据结构 考试时间： 120 分钟 专业 年级 班 学号 姓名 题号一二三四五总得分 得分 评卷人签字复核人签字 得分一、选择题（每小题 1 分，共 20 分） 1、用链表表示线性表的优点是（C） 。 A. 便于随机存取 B. 存储的密度较高 C. 便于元素的插入和删除操作 D. 元素的物理顺序与逻辑顺序一致 2、在长度为 n 的顺序表中，向第 k 个元素（1kn+1）之前插入一个新元素时，需向后 移动（B）个元素。 A. n-1 B. n-k+1 C. n-k-1 D. k 3、设用一维数组 S 存储一个栈，令 Sn-1为栈底，变量 top 表示当前栈顶的位置（下标） ， 即 Stop为栈顶元素。则，元素出栈后 top 应做如下（B）的修改。 A. top-; B. top+; C. top = n-1; D. top = -1; 4、上一题中，栈满的条件表达式应为（C） 。 A. top=n B. top=n-1 C. top=0 D. top=-1 5、设栈 S 和队列 Q 的初始状态为空，元素 e1,e2,e3,e4,e5,e6 先后进入栈 S，一个元素出栈 后即进入队列 Q，若 6 个元素的出队顺序是 e2,e4,e3,e6,e5,e1，则栈 S 至少可以容纳（A） 个元素。 A. 3 B. 4 C. 5 D. 6 6、设有一个大小为 m 的数组 queue 表示循环队列，若 f 表示当前队头元素在数组中的位置， r 表示队尾元素的后一位置（按顺时针方向） ，则计算队列中元素个数的表达式为（D） 。 A. r-f B. (m-f-r) % m C. (m+f-r) % m D. (m+r-f) % m 7、深度为 5 的二叉树至多有（B）个结点。 A. 30 B. 31 C. 32 D. 63 8、设二叉树中任一结点的值大于它的左子树中每个结点的值，而小于右子树中每个结点的 值，即是一个二叉排序树。若要获取该二叉树中所有结点的值的递增序列，应采用下列 （B）的方法遍历二叉树。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 9、由 3 个结点可以构成（C）棵形态不同的二叉树。 A. 3 B. 4 C. 5 D. 6 10、某二叉树如图所示，对该二叉树进行先序遍历，结点的访问序列为（B） 。 A. 1, 2, 3, 4, 5, 6, 7 B. 1, 2, 4, 6, 7, 3, 5 C. 2, 6, 4, 7, 1, 5, 3 D. 6, 7, 4, 2, 5, 3, 1 11、对于一个具有 n 个顶点的图，若采用邻接矩阵表示，则矩阵 中元素的个数为（D） 。 A. n B. (n-1)2 C. (n+1)2 D. n2 12、对图所示的无向图 G，从顶点 A 开始，深度优先遍历，可能的顶点访问顺序为（D） 。 A. A, B, E, C, D, F B. A, C, F, E, B, D C. A, B, C, D, E, F D. A, C, F, D, E, B 13、对上一题的图 G，从顶点 A 开始，广度优先遍历，则可能 的顶点访问顺序为（A） 。 A. A, B, E, C, D, F B. A, C, B, D, E, F C. A, B, C, D, E, F D. A, C, F, E, B, D 14、有向图 G 有 n 个顶点，其邻接矩阵为 A（二维数组） ，G 中第 k 个顶点的度为（C） 。 A. 1 0 k i iiA B. 1 0 1 n i ikA C. 1 0 )11( n i kiAikA D. 1 0 1 k i kiA + 1 1 1 k i ikA 15、设检索表（a1,a2,a3,.,a32）中有 32 条记录，且已按关键字递增有序排列，采用二分法 检索一个与给定的键值 K 相等的记录，若 a1.keynext= p-next ; p-next= s ; 2、 栈 作为实现函数递归调用的数据结构。 队列 作为打印缓冲区的数据结构。 3、n 个结点的循环队列中，front 指示当前队头的前一个位置（下标） ，rear 指示当前队尾 的位置。那么，在元素入队前，要执行 rear = (rear+1) % n 语句；在元素出队前，要 执行 front = (front+1) % n 语句。 4、树与二叉树之间的主要区别是：二叉树各结点的子树区分为 左子树 和 右子树 。 5、在具有 n 个顶点的无向完全图中，共有 n(n-1)/2 条边；而它的生成树中，有 n-1 条 边。 6、一棵深度为 6 的满二叉树中，叶子结点的个数为 32 ，分支结点的个数为 31 。 7、有由 1000 个数据元素组成的顺序表，假设一次比较表中关键字所需的时间为 0.5 毫秒。 则在机会均等的情况下顺序检索，成功检索一个元素的平均用时为 250.25 毫秒。 8、快速排序算法在一般情况下的时间复杂度为 O(nlog2n) ；最坏情况下为 O(n2) 。 / 第 2 小题填 栈存储结构 和 队列存储结构 得一半分 / 第 8 小题填 nlog2n 和 n2 得一半分 得分四、应用题（每小题 5 分，共 15 分） 1、试分别画出下面二叉树的二叉链表和静态二叉链表。 dataL-childR-child 0A1-1 1B23 2C-1-1 3D-14 4E-1-1 二叉链表表示正确得 2.5，其中，指针表示错误扣 1 分，空指针未表达扣 0.5 分，缺少 1 个 结点扣 0.5 分； 静态二叉链表表达正确得 2.5 分，其中，每个结点占 0.5 分，未表示元素存储位置扣 1 分。 2、有向图 G 如图所示，顶点的次序依次为 A, B, C, D, E，试写出该图的邻接矩阵。 00010 10000 00000 00001 10100 或： 01001 00000 00001 10000 00010 矩阵 5 行 5 列，每行正确各得 1 分，共 5 分。 3、已知顺序表中存储的序列19, 14, 22, 1, 66, 21, 83, 27, 56, 13，将元 素按其在表中的次序依次插入到一棵初始为空的二叉排序树中，画出插入完成后的二叉排 序树。 根结点正确得 1 分；左子树包含 14, 1, 13，或包含 22, 66, 21, 83, 27, 56 得 1 分；右子树包 含 22, 66, 21, 83, 27, 56，或包含 14, 1, 13 得 1 分；叶子结点包含 13, 21, 56, 83 得 1 分；其 它关系正确得 1 分。 得分五、设计题（每小题 5 分，共 15 分） 1、有一个带头结点的单链表，已知指向头结点的指针 hp，试写出在元素值为 a 的结点 （假设该结点存在）之后插入元素值为 b 的结点（该结点未建立）的算法过程。结点类型 node 已经定义，含有存放元素的 data 域（elemtp 类型）和指向后继结点的指针域 next。 void insert(node *hp, elemtp a, elemtp b) / 1 分 node *p, *q; / 0.5 分 p=hp-next; / 0.5 分 while(p-data!=a) p = p-next; / 1 分 q = new node; / 0.5 分 q-data=b; / 0.5 分 q-next=p-next; / 0.5 分 p-next=q; / 0.5 分 2、以二叉链表为存储结构，写出求二叉树中叶子结点数的算法的递归函数。 int LeafNumber(bitree *bt); / 1 分 if (bt=NULL) return 0; / 1 分 if (bt-lp=NULLL) / 1 分 return LeftNumber(bt-lp)+LeftNumber(bt-rp); / 2 分 3、以链地址法处理冲突建立开散列表，设散列函数为：H(key)=key%13。试编写在此开散 列表上实现动态检索（即，给定记录键值 K，若检索成功则返回结点地址；否则以拉链法 插入新结点，并返回新结点的地址）算法的函数。设同义词单链表结点的数据类型定义如 下： typedef struct node elemtp data; / 记录 keytp key; / 关键字 struct node *next; / 后继指针 listnode; listnode *hashlist_search(listnode *h, keytp K, elemtp D) / 0.5 分 listnode *p; p=hK%1