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

福建农林大学考试试卷评分标准（B）卷2007——2008学年第一学期课程名称：数据结构与算法考试时间：120分钟专业年级班学号姓名题号一二三四五总得分得分评卷人签字复核人签字得分一、选择题（每小题1.5分，共30分）1、以下数据结构中，（B）是线性结构。A.有向图B.栈C.二叉树D.森林2、在长度为n的顺序表中，删除第k个元素（1≤k≤n）时，需向前移动（A）个元素。A.n-kB.n-k+1C.n-k-1D.k3、与顺序栈相比，链栈的主要优点在于（C）。A.入栈操作更加方便B.出栈操作更加方便C.通常不会出现栈满D.通常不会出现栈空4、在一个单链表中，若要删除指针p所指向结点的后继结点，则需执行（A）中的语句。A.p^.next:=p^.next^.next;B.p:=p^.next;p^.next:=p^.next^.next;C.p:=p^.next^.next;D.p^.next:=p;5、在由n个结点单元组成的顺序存储的循环队列中，假定front指示队头的位置，rear指示队尾的后一位置，则判定队满的条件是（D）。A.front=0B.(front+1)modn=rearC.front=rearD.front=(rear+1)modn6、若进栈序列为1、2、3、4，进栈过程允许出栈，则下列出栈序列中，（D）是不可能的。A.1、3、4、2B.2、4、3、1C.3、4、2、1D.1、4、2、37、以顺序存储方式将完全二叉树中的所有结点逐层存放于数组A[1..n]中，结点A[i]若有左孩子，则左孩子是结点（C）。A.A[2*i-1]B.A[2*i+1]C.A[2*i]D.A[idiv2]8、有n个结点的二叉树，其深度为（D）。A.log2n+1B.log2nC.n/2D.不确定9、在下列存储形式中，（D）不适合于树。A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法10、某二叉树如图所示，对该二叉树进行中序遍历的结点序列为（C）。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个顶点的无向完全图中，具有（A）条边。A.n(n-1)/2B.n(n-1)C.n(n+1)/2D.n212、对图所示的无向图G，从顶点①开始，广度优先遍历，可能的顶点访问顺序为（B）。A.①,②,③,④,⑤,⑥,⑦,⑧B.①,②,⑥,③,④,⑦,⑧,⑤C.①,②,⑥,③,④,⑤,⑦,⑧D.①,②,③,⑤,④,⑥,⑦,⑧13、对上一题的图G，从顶点①开始，深度优先遍历，则可能的顶点访问顺序为（D）。A.①,②,③,④,⑤,⑥,⑦,⑧B.①,②,⑥,③,④,⑦,⑧,⑤C.①,②,⑥,③,④,⑤,⑦,⑧D.①,②,③,⑤,④,⑥,⑦,⑧14、采用顺序检索的方法检索长度为n的顺序表，检索每个元素的平均比较次数（即平均检索长度）为（C）。A.nB.n/2C.(n+1)/2D.(n-1)/215、散列法存储的基本思想是依据关键字值的简单换算来决定（A）。A.存储地址B.元素的序号C.平均检索长度D.散列表空间16、设计一个用线性探测法解决冲突的散列表（散列函数：H(key)=keymod17），其地址区间为0..16，现将关键字值分别为26、25、72、38、8、18、59的记录依次存储到散列表中。关键字值为59的记录在散列表中的地址是（D）。A.8B.9C.10D.1117、对一组字母序列（Q，D，F，X，A，P，N，B，Y，M，C，W）用归并排序方法进行一趟归并后的结果为（D）。A.（D，F，Q，X，A，B，N，P，C，M，W，Y）B.（D，F，Q，A，P，X，B，N，Y，C，M，W）C.（D，Q，F，X，A，P，N，B，Y，M，C，W）D.（D，Q，F，X，A，P，B，N，M，Y，C，W）18、对n个元素进行堆排序，最坏情况下的执行时间为（C）。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)19、对n个元素进行选择排序，所需要的辅助存储空间为（A）。A.O(1)B.O(n)C.O(log2n)D.O(n2)20、以下4种排序算法中，时间复杂度最小的是（D）。A.插入排序B.选择排序C.快速排序D.归并排序得分二、判断题（每小题2分，共20分。正确的在括号内打“√”，错误的打“×”）1、顺序存储方式的优点是存储密度大，且插入和删除运算的效率高。（×）2、栈和队列都是顺序存储的线性结构。（×）3、“后进先出”符合栈的特性。（√）4、二叉树先序遍历序列的最后一个结点，必是其中序遍历序列中的最后一个结点。（×）5、不使用递归也能实现二叉树的遍历。（√）6、邻接矩阵只能用于表示无向图的顶点关系。（×）7、n个带权叶子结点构成的哈夫曼树（最优二叉树）是唯一的。（×）8、当检索表中的元素以关键字递减（由大到小）有序时，不宜运用折半检索。（×）9、通常，选择排序比插入排序的元素交换次数要少。（√）10、对n个元素的集合进行归并排序时，需要的辅助存储空间为O(log2n)。（×）得分三、填空题（每个填空2分，共30分）1、在一个链栈中，top为指向栈顶的指针，p所指向的结点（已建立）入栈时，应顺序执行如下操作语句：p^.next:=top;top:=p;2、栈中的第一个元素称为栈底。队列的最后一个元素称为队尾。3、n个结点的循环队列中，front指示当前队头的位置（下标），rear指示当前队尾的后一位置。那么，在元素出队前，要执行front:=(front+1)modn语句；在元素入队前，要执行rear:=(rear+1)modn语句。4、一棵深度为h的二叉树中，结点最少有h个，最多有2h-1个。5、n个结点的二叉链表中，共有2n个指针，其中有n-1个指针用于指向左、右孩子，剩余的n+1个指针为空。6、在具有n个顶点的有向完全图中，共有n(n-1)条弧。7、含有n个顶点的有向图的邻接矩阵为A，计算第i个顶点的出度公式为；计算其入度的公式为。8、散列表（哈希表）检索法的平均检索长度与元素个数n无关。得分四、应用题（每小题5分，共10分）1、试画出下面二叉树的二叉链表和顺序存储结构。ABCDE…123456789101112131415…二叉链表表示正确得2.5，其中，指针表示错误扣1分，空指针未表达扣0.5分，缺少1个结点扣0.5分；顺序存储结构表达正确得2.5分，其中，每个结点占0.5分，未表示元素存储位置扣1分。2、无向图G的顶点依次为a、b、c、d和e，其邻接矩阵如下，试画出该图。0101010101010111010101110每个顶点与其它顶点的边（关系）正确得1分，共计5分。njjiA1,njijA1,得分五、设计题（每小题5分，共10分）1、设计算法并分析其最坏时间复杂度：找出数组A[1..n]中最大的数（数组元素类型为integer）。functionGetMax(A:arrayofinteger;n:integer):integer;//函数首部正确得0.5分，半对得0.25分varj,max:integer;//变量声明正确得0.5分，半对得0.25分beginmax:=A[1];//或max:=low(integer);//初试化最大值正确得0.5分，半对得0.25分forj:=2tondo//或forj:=1tondo//循环控制正确得0.5分，半对得0.25分ifA[j]maxthenmax:=A[j];//比较和替换正确得0.5分，半对得0.25分result:=max;//或GetMax:=max;//函数返回值正确得0.5分，半对得0.25分end;该算法的最坏时间复杂度为O(n)。//时间复杂度正确得2分2、有一个不带头结点的单链表，指向第一元素结点的指针为hp，试编写计算单链表长度（结点个数）算法函数。假设，已定义单链表的结点类型node，它含有存放元素的data域和指向后继结点的指针域next。functionLength(hp:^node):integer;//函数首部正确得0.5分，半对得0.25分varp:^node;//指针变量声明正确得0.5分，半对得0.25分n:integer;//计数变量声明正确得0.5分，半对得0.25分beginn:=0;//计数变量初始化正确得0.5分，半对得0.25分p:=hp;//指针变量初始化正确得0.5分，半对得0.25分whilepnildo//循环控制正确得1分，半对得0.25分begininc(n);//计数变量加1正确得0.5分，半对得0.25分p:=p^.next;//指针变量赋值正确得0.5分，半对得0.25分end;result:=n;//或Length:=n;//函数返回值正确得0.5分，半对得0.25分end;