whut数据结构复习题 参考答案.doc

1 复****题集一判断题(×)1. 线性表在物理存储空间中也一定是连续的。(×)2. 顺序存储方式只能用于存储线性结构。(√)3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。(√)4. 两个栈共享一片连续内存空间时, 为提高内存利用率, 减少溢出机会, 应把两个栈的栈底分别设在这片内存空间的两端。(×)5. 二叉树的度为 2。(√)6. 若二叉树用二叉链表作存贮结构,则在 n 个结点的二叉树链表中只有 n—1 个非空指针域。(×)7. 二叉树中每个结点的两棵子树的高度差等于 1。(√)8. 用二叉链表法存储包含 n 个结点的二叉树,结点的 2n 个指针区域中有 n+1 个为空指针。(×)9. 在冒泡法排序中,关键值较小的元素总是向前移动,关键值较大的元素总是向后移动。(×) 10 .计算机处理的对象可以分为数据和非数据两大类。[ 计算机处理的对象都是数据] (×) 11 .数据的逻辑结构与各数据元素在计算机中如何存储有关。(×) 12 .算法必须用程序语言来书写。(×) 13 .判断某个算法是否容易阅读是算法分析的任务之一。(×) 14 .顺序表是一种有序的线性表。[ 任何数据结构才用顺序存储都叫顺序表] (√) 15 .分配给顺序表的内存单元地址必须是连续的。(√) 16 .栈和队列具有相同的逻辑特性。[ 它们的逻辑结构都是线性表] (√) 18 .树形结构中每个结点至多有一个前驱。(×) 19 .在树形结构中,处于同一层上的各结点之间都存在兄弟关系。(×) 20 .如果表示图的邻接矩阵是对称矩阵,则该图一定是无向图。(×) 21 .如果表示图的邻接矩阵是对称矩阵,则该图一定是有向图。(×) 22 .顺序查找方法只能在顺序存储结构上进行。(×) 23 .折半查找可以在有序的双向链表上进行。(√) 24 .满二叉树中不存在度为 1 的结点。(×) 25 .完全二叉树中的每个结点或者没有孩子或者有两个孩子。(√) 26 .对 n 个元素执行快速排序,在进行第一次分组时,排序码的比较次数总是 n-1 次。(√) 27 .在有向图中,各顶点的入度之和等于各顶点的出度之和。一、选择题(A) 个结点的顺序表中,算法的时间复杂度是 O(1) 的操作是: A) 访问第 i 个结点( 1≤i≤n )和求第 i 个结点的直接前驱( 2≤i≤n)C) 删除第 i 个结点( 1≤i≤n) B) 在第 i 个结点后插入一个新结点( 1≤i≤n)D)将n 个结点从小到大排序(C) 2. 算法分析的目的是: A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 2 (A) 3. 算法分析的两个主要方面是: A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性(B) 4. 计算机算法必须具备输入、输出和等5 个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性(B) 5. 一个向量第一个元素的存储地址是 100 ,每个元素的长度为 2 ,则第 5 个元素的地址是: (A) 110 (B) 108 (C) 100 (D) 120 (A) 5. 链接存储的存储结构所占存储空间: (A )分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针(B )只有一部分,存放结点值(C) 只有一部分,存储表示结点间关系的指针(D) 分两部分,一部分存放结点值,另一部分存放结点所占单元数(B) 6. 一个栈的输入序列为 1,2,3,…,n ,若输出序列的第一个元素是 n ,输出第 i(1≤i≤n )个元素是。 A) 不确定 B)n-i+1C)iD)n-i (B) 7. 最大容量为 n 的循环队列,队尾指针是 rear ,队头是 front ,则队空的条件是()。 A) (rear + 1)% n= = front B) rear== = front C) rear + 1= = front D) (rear - l)% n= = front (A) 8. 循环队列 A[0..m - 1] 存放其元素值,用 front 和 rear 分别表示队头和队尾, 则当前队列中的元素数是:A) (rear - front + m)%m B) rear - front +1C) rear - front -1D) rear - front (C) 9. 按照二叉树的定义,具有 3 个结点的二叉树有( )种。 A)3B)4C)5D)6[ 利用排列组合知识来做] (B) 10. 具有 n(n>0) 个结点的完全二叉树的深度为: (A)? log