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

《福建农林大学数据结构考试试卷3(附答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福建农林大学考试试卷评分标准（A）卷2007——2008学年第一学期课程名称：数据结构考试时间：120分钟专业年级班学号姓名题号一二三四五总得分得分评卷人签字复核人签字得分一、选择题（每小题1分，共20分）1、用链表表示线性表的优点是（C）。A.便于随机存取B.存储的密度较高C.便于元素的插入和删除操作D.元素的物理顺序与逻辑顺序一致2、在长度为n的顺序表中，向第k个元素（1≤k≤n+1）之前插入一个新元素时，需向后移动（B）个元素。A.n-1B.n-k+1C.n-k-1D.k3、设用一维数组S存储一个栈，令S[n-1]为栈底，变量top表示当前栈顶的位置（下标），即S[top]为栈顶元素。则

2、，元素出栈后top应做如下（B）的修改。A.top--;B.top++;C.top=n-1;D.top=-1;4、上一题中，栈满的条件表达式应为（C）。A.top==nB.top==n-1C.top==0D.top==-15、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6先后进入栈S，一个元素出栈后即进入队列Q，若6个元素的出队顺序是e2,e4,e3,e6,e5,e1，则栈S至少可以容纳（A）个元素。A.3B.4C.5D.66、设有一个大小为m的数组queue表示循环队列，若f表示当前队头元素在数组中的位置，r表示队尾元素的后一位置（按顺时针方向），则计算队列中元素个数的

3、表达式为（D）。A.r-fB.(m-f-r)%mC.(m+f-r)%mD.(m+r-f)%m7、深度为5的二叉树至多有（B）个结点。A.30B.31C.32D.638、设二叉树中任一结点的值大于它的左子树中每个结点的值，而小于右子树中每个结点的值，即是一个二叉排序树。若要获取该二叉树中所有结点的值的递增序列，应采用下列（B）的方法遍历二叉树。A.先序遍历B.中序遍历C.后序遍历D.层序遍历9、由3个结点可以构成（C）棵形态不同的二叉树。A.3B.4C.5D.610、某二叉树如图所示，对该二叉树进行先序遍历，结点的访问序列为（B）。A.1,2,3,4,5,6,7B.1,2,4,6,7,3,5C.

4、2,6,4,7,1,5,3D.6,7,4,2,5,3,111、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵中元素的个数为（D）。A.nB.(n-1)2C.(n+1)2D.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,FB.A,C,B,D,E,FC.A,B,C,D,E,FD.A,C,F,E,B,D14、有向图G有n个顶点，其邻接矩阵为A（二维数

5、组），G中第k个顶点的度为（C）。A.B.C.D.+15、设检索表（a1,a2,a3,...,a32）中有32条记录，且已按关键字递增有序排列，采用二分法检索一个与给定的键值K相等的记录，若a1.key

6、。A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.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,53B.37,48,65,16,72,27,50,9,53,93C.9,37,27,16,48,72,93,50,65,53D.16,27,50,9,53,48,37,65,93,7219、以下

7、4种排序算法中，时间复杂度最高的是（A）。A.直接插入排序B.归并排序C.快速排序D.堆排序20、以下4种排序算法中，需要附加的内存空间最大的是（D）。A.插入排序B.选择排序C.快速排序D.归并排序得分二、判断题（每小题2分，共20分。正确的在括号内打“√”，错误的打“×”）1、线性表的链式存储结构优于顺序存储结构。（×）2、一个n维数组可以视为其数据元素是n-1维的线性表。（√）3、空栈就是所