资源描述：
《福建农林大学数据结构考试试卷4(附答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、福建农林大学考试试卷评分标准（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.通常不会
2、出现栈满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
3、.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
4、）不适合于树。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.①,②,⑥
5、,③,④,⑦,⑧,⑤C.①,②,⑥,③,④,⑤,⑦,⑧D.①,②,③,⑤,④,⑥,⑦,⑧13、对上一题的图G，从顶点①开始，深度优先遍历，则可能的顶点访问顺序为（D）。A.①,②,③,④,⑤,⑥,⑦,⑧B.①,②,⑥,③,④,⑦,⑧,⑤C.①,②,⑥,③,④,⑤,⑦,⑧D.①,②,③,⑤,④,⑥,⑦,⑧14、采用顺序检索的方法检索长度为n的顺序表，检索每个元素的平均比较次数（即平均检索长度）为（C）。A.nB.n/2C.(n+1)/2D.(n-1)/215、散列法存储的基本思想是依据关键字值的简单换算来决
6、定（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
7、，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.归并排序得分二、判断
8、题（每小题2分，共20分。正确的在括号内打“√”，错误的打“×”）1、顺序存储方式的优点是存储密度大，且插入和删除运算的效率高。（×）2、栈和队列都是顺序存储的线性结构。（×）3、“后进先出”符合栈的特性。（√）4、二叉树先序遍历序列的最后一个结点，必是其中序遍历序列中的最后一个结点。（×）5、不使用递归也能实现二叉树的遍历。（√）6、邻接矩阵只能用于表示无向图的顶点关系。（×）7、n个带权叶子结点构成的哈夫曼树（最优二叉树）
