精选优质文档-----倾情为你奉上 福建农林大学考试试卷评分标准 （A）卷2007 —— 2008 学年 第 一 学期课程名称： 数据结构 考试时间： 120分钟 专业 年级 班 学号 姓名 题号一二三四五总得分得分评卷人签字复核人签字得分一、选择题（每小题1分，共20分）1、用链表表示线性表的优点是（C）A. 便于随机存取 B. 存储的密度较高C. 便于元素的插入和删除操作 D. 元素的物理顺序与逻辑顺序一致2、在长度为n的顺序表中，向第k个元素（1≤k≤n+1）之前插入一个新元素时，需向后移动（B）个元素A. n-1 B. n-k+1 C. n-k-1 D. k3、设用一维数组S存储一个栈，令S[n-1]为栈底，变量top表示当前栈顶的位置（下标），即S[top]为栈顶元素则，元素出栈后top应做如下（B）的修改A. top--; B. top++;C. top = n-1; D. top = -1;4、上一题中，栈满的条件表达式应为（C）。
A. top==n B. top==n-1C. top==0 D. top==-15、设栈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. 66、设有一个大小为m的数组queue表示循环队列，若f表示当前队头元素在数组中的位置，r表示队尾元素的后一位置（按顺时针方向），则计算队列中元素个数的表达式为（D）A. r-f B. (m-f-r) % mC. (m+f-r) % m D. (m+r-f) % m7、深度为5的二叉树至多有（B）个结点A. 30 B. 31 C. 32 D. 638、设二叉树中任一结点的值大于它的左子树中每个结点的值，而小于右子树中每个结点的值，即是一个二叉排序树。
若要获取该二叉树中所有结点的值的递增序列，应采用下列（B）的方法遍历二叉树A. 先序遍历 B. 中序遍历C. 后序遍历 D. 层序遍历9、由3个结点可以构成（C）棵形态不同的二叉树A. 3 B. 4 C. 5 D. 610、某二叉树如图所示，对该二叉树进行先序遍历，结点的访问序列为（B）A. 1, 2, 3, 4, 5, 6, 7B. 1, 2, 4, 6, 7, 3, 5C. 2, 6, 4, 7, 1, 5, 3D. 6, 7, 4, 2, 5, 3, 111、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵中元素的个数为（D）A. n B. (n-1)2C. (n+1)2 D. n212、对图所示的无向图G，从顶点A开始，深度优先遍历，可能的顶点访问顺序为（D）A. A, B, E, C, D, FB. A, C, F, E, B, DC. A, B, C, D, E, FD. A, C, F, D, E, B13、对上一题的图G，从顶点A开始，广度优先遍历，则可能的顶点访问顺序为（A）。
A. A, B, E, C, D, F B. A, C, B, D, E, FC. A, B, C, D, E, F D. A, C, F, E, B, D14、有向图G有n个顶点，其邻接矩阵为A（二维数组），G中第k个顶点的度为（C）A. B. C. D. +15、设检索表（a1,a2,a3,...,a32）中有32条记录，且已按关键字递增有序排列，采用二分法检索一个与给定的键值K相等的记录，若a1.key
A. 1 B. 6 C. 7 D. 817、用直接插入排序法对下面4个序列进行递增（由小到大）排序，元素比较次数最少的是（C）A. 94, 32, 40, 90, 80, 46, 21, 69 B. 32, 40, 21, 46, 69, 94, 90, 80C. 21, 32, 46, 40, 80, 69, 90, 94 D. 90, 69, 80, 46, 21, 32, 94, 4018、对10个记录的序列：48, 37, 65, 93, 72, 16, 27, 50, 9, 53进行排序，采用初始间隔为5的希尔排序，一趟之后序列的次序是（D）A. 37, 48, 65, 93, 16, 72, 27, 50, 9, 53 B. 37, 48, 65, 16, 72, 27, 50, 9, 53, 93C. 9, 37, 27, 16, 48, 72, 93, 50, 65, 53 D. 16, 27, 50, 9, 53, 48, 37, 65, 93, 7219、以下4种排序算法中，时间复杂度最高的是（A）。
A. 直接插入排序 B. 归并排序C. 快速排序 D. 堆排序20、以下4种排序算法中，需要附加的内存空间最大的是（D）A. 插入排序 B. 选择排序C. 快速排序 D. 归并排序得分二、判断题（每小题2分，共20分正确的在括号内打“√”，错误的打“×”）1、线性表的链式存储结构优于顺序存储结构 （×）2、一个n维数组可以视为其数据元素是n-1维的线性表 （√）3、空栈就是所有元素都为0的栈 （×）4、二叉树中，有两个孩子的结点，在中序遍历序列中，其后继结点最多只有一个 （×）5、顺序存储结构不仅能用于表示完全二叉树，也能表示一般的二叉树 （√）6、邻接表只能用于有向图的存储 （×）7、有向图不能进行深度优先搜索。
无向图不能进行广度优先搜索 （×）8、运用折半检索时，检索表中的元素必需以关键字递增（由小到大）有序排列 （×）9、散列表中若不存在地址冲突或同义词，则其成功检索的平均检索长度等于1 （√）10、对n个元素的集合进行堆排序时，需要的辅助存储空间为O(n) （×）得分三、填空题（每个填空2分，共30分）1、在一个单链表中，在指针p所指向的结点之后插入指针s所指向的结点时，应执行如下操作：s->next= 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-child0A1-11B232C-1-13D-144E-1-1二叉链表表示正确得2.5，其中，指针表示错误扣1分，空指针未表达扣0.5分，缺少1个结点扣0.5分；静态二叉链表表达正确得2.5分，其中，每个结点占0.5分，未表示元素存储位置扣1分2、有向图G如图所示，顶点的次序依次为A, B, C, D, E，试写出该图的邻接矩阵 或： 矩阵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分）。