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

福建农林大学考试试卷评分标准（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]为栈顶元素。则，元素出栈后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表示队尾元素的后一位置（按顺时针方向），则计算队列中元素个数的表达式为（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.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（二维数组），G中第k个顶点的度为（C）。A.10]][[kiiiAB.10]][1[niikAC.10])1][[]][1[(nikiAikAD.10]1][[kikiA+11]][1[kiikA15、设检索表（a1,a2,a3,...,a32）中有32条记录，且已按关键字递增有序排列，采用二分法检索一个与给定的键值K相等的记录，若a1.keyKa2.key，则检索过程中K与记录关键字的比较次数为（C）。A.3B.4C.5D.616、设有一个用线性探测法解决冲突得到的散列表（散列函数：H(key)=key%11）：0123456789101325801617614若要检索关键字值为14的记录，探测（比较）的次数是（B）。A.1B.6C.7D.817、用直接插入排序法对下面4个序列进行递增（由小到大）排序，元素比较次数最少的是（C）。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、以下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，试写出该图的邻接矩阵。0001010000000000000110100或：0100100000000011000000010矩阵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。voidinsert(node*hp,elemtpa,elemtpb)//1分{node*p,*q;//0.5分p=hp-next;//0.5分while(p-data!=a)p=p-next;//1分q=newnode;//0.5分q-data=b;//0.5分q-next=p-next;//0.5分p-next=q;//0.5分}2、以二叉链表为存储结构，写出求二叉树中叶子结点数的算法的递归函数。intLeafNumber(bitree*bt);//1分{if(bt==NULL)return0;//1分if((bt-lp==NULLL)&&(bt-rp==NULL))return1;//1分returnLeftNumber(bt-lp)+LeftNumber(bt-rp);//2分}3、以链地址法处理冲突建立开散列表，设散列函数为：H(key)=key%13。试编写在此开散列表上实现动态检索（即，给定记录键值K，若检索成功则返回结点地址；否则以拉链法插入新结点，并返回新结点的地址）算法的函数。设同义词单链表结点的数据类型定义如下：typedefstructnode{elemtpdata;//记录keytpkey;//关键字structnode*next;//后继指针}listnode;listnode*hashlist_search(listnode**h,keytpK,elemtpD)//0.5分{listnode*p;p=h[K%13];//0.5分while(p!=NULL)//0.5分{if(p-key==K)returnp;//0.5分p=p-next;//0.5分}p=newlistnode;//0.5分p-key=K;p-data=D;//0.5分p-next=h[K%13];//0.5分h[K%13]=p;//0.5分returnp;//0.5分}