福建农林大学数据结构考试试卷

1、精选优质文档-倾情为你奉上 福建农林大学考试试卷评分标准 （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. k3、设用一维数组S存储一个栈，令Sn-1为

2、栈底，变量top表示当前栈顶的位置（下标），即Stop为栈顶元素。则，元素出栈后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表示循环队列

3、，若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

4、 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

5、, 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<K<a2.key，则检索过程中K与记录关键字的

6、比较次数为（C）。A. 3 B. 4 C. 5 D. 616、设有一个用线性探测法解决冲突得到的散列表（散列函数：H(key) = key % 11）： 0 1 2 3 4 5 6 7 8 9 101325801617614若要检索关键字值为14的记录，探测（比较）的次数是（B）。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, 9

7、0, 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种排序算法中，时间复

8、杂度最高的是（A）。A. 直接插入排序 B. 归并排序C. 快速排序 D. 堆排序20、以下4种排序算法中，需要附加的内存空间最大的是（D）。A. 插入排序 B. 选择排序C. 快速排序 D. 归并排序得分二、判断题（每小题2分，共20分。正确的在括号内打“”，错误的打“×”）1、线性表的链式存储结构优于顺序存储结构。 （×）2、一个n维数组可以视为其数据元素是n-1维的线性表。 （）3、空栈就是所有元素都为0的栈。 （×）4、二叉树中，有两个孩子的结点，在中序遍历序列中，其后继结点最多只有一个。 （×）5、顺序存储结构不仅能用于表示完全二叉树，也能表示

9、一般的二叉树。 （）6、邻接表只能用于有向图的存储。 （×）7、有向图不能进行深度优先搜索。无向图不能进行广度优先搜索。 （×）8、运用折半检索时，检索表中的元素必需以关键字递增（由小到大）有序排列。 （×）9、散列表中若不存在地址冲突或同义词，则其成功检索的平均检索长度等于1。 （）10、对n个元素的集合进行堆排序时，需要的辅助存储空间为O(n)。 （×）得分三、填空题（每个填空2分，共30分）1、在一个单链表中，在指针p所指向的结点之后插入指针s所指向的结点时，应执行如下操作：s->next= p->next ; p->next=

10、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、有由100

11、0个数据元素组成的顺序表，假设一次比较表中关键字所需的时间为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

12、分，缺少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，

13、或包含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!

14、=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)&&(bt->rp=NULL) return 1; / 1分 return LeftNumber(bt->l

15、p)+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)