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

福建农林大学考试试卷评分标准 （B）卷 2007 —— 2008 学年 第 一 学期 课程名称： 数据结构与算法 考试时间： 120分钟 专业 年级 班 学号 姓名 题号 一 二 三 四 五 总得分 得分 评卷人签字 复核人签字 得分 一、选择题（每小题1.5分，共30分） 1、以下数据结构中，（B）是线性结构。 A. 有向图 B. 栈 C. 二叉树 D. 森林 2、在长度为n的顺序表中，删除第k个元素（1≤k≤n）时，需向前移动（A）个元素。 A. n-k B. n-k+1 C. n-k-1 D. k 3、与顺序栈相比，链栈的主要优点在于（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=0 B. (front+1) mod n=rear C. front=rear D. front=(rear+1) mod n 6、若进栈序列为1、2、3、4，进栈过程允许出栈，则下列出栈序列中，（D）是不可能的。 A. 1、3、4、2 B. 2、4、3、1 C. 3、4、2、1 D. 1、4、2、3 7、以顺序存储方式将完全二叉树中的所有结点逐层存放于数组A[1..n]中，结点A[i]若有左孩子，则左孩子是结点（C）。 A. A[2*i-1] B. A[2*i+1] C. A[2*i] D. A[i div 2] 8、有n个结点的二叉树，其深度为（D）。 A. log2n+1 B. log2n C. n/2 D. 不确定 9、在下列存储形式中，（D）不适合于树。 A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法 10、某二叉树如图所示，对该二叉树进行中序遍历的结点序列为（C）。 A. 1, 2, 3, 4, 5, 6, 7 B. 1, 2, 4, 6, 7, 3, 5 C. 2, 6, 4, 7, 1, 5, 3 D. 6, 7, 4, 2, 5, 3, 1 11、有n个顶点的无向完全图中，具有（A）条边。 A. n(n-1)/2 B. n(n-1) C. n(n+1)/2 D. n2 12、对图所示的无向图G，从顶点①开始，广度优先遍历，可能的顶点访问顺序为（B）。 A. ①, ②, ③, ④, ⑤, ⑥, ⑦, ⑧ B. ①, ②, ⑥, ③, ④, ⑦, ⑧, ⑤ C. ①, ②, ⑥, ③, ④, ⑤, ⑦, ⑧ D. ①, ②, ③, ⑤, ④, ⑥, ⑦, ⑧ 13、对上一题的图G，从顶点①开始，深度优先遍历，则可能的顶点访问顺序为（D）。 A. ①, ②, ③, ④, ⑤, ⑥, ⑦, ⑧ B. ①, ②, ⑥, ③, ④, ⑦, ⑧, ⑤ C. ①, ②, ⑥, ③, ④, ⑤, ⑦, ⑧ D. ①, ②, ③, ⑤, ④, ⑥, ⑦, ⑧ 14、采用顺序检索的方法检索长度为n的顺序表，检索每个元素的平均比较次数（即平均检索长度）为（C）。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 15、散列法存储的基本思想是依据关键字值的简单换算来决定（A）。 A. 存储地址 B. 元素的序号 C. 平均检索长度