《数据结构与算法复习题及参考答案》由会员分享，可在线阅读，更多相关《数据结构与算法复习题及参考答案（15页珍藏版）》请在金锄头文库上搜索。
1、2016数据结构域算法复习题1复习题集参考答案一判断题（）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。（）2. 抽象数据类型与计算机内部表示和实现无关。（）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（）4. 链表的每个结点中都恰好包含一个指针。（）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （）8. 线性表在物理存储空间中也一定是连续的。（）9. 顺序存储
2、方式只能用于存储线性结构。（）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）14.二叉树的度为 2。（）15.若二叉树用二叉链表作存贮结构，则在 n 个结点的二叉树链表中只有 n1 个非空指针域。（）16.二叉树中每个结点的两棵子树的高度差等于 1。 （）17.用二叉链表
3、法存储包含 n 个结点的二叉树，结点的 2n 个指针区域中有 n+1 个为空指针。（）18.具有 12 个结点的完全二叉树有 5 个度为 2 的结点。（）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。（）21.计算机处理的对象可以分为数据和非数据两大类。计算机处理的对象都是数据（）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。（）23.算法必须用程序语言来书写。（）24.判断某个算法是否容易阅读是算法分析的任务之一。（）25.顺序表是一种有序的线性表。任何数据结构才用顺序存储都叫
4、顺序表（）26.分配给顺序表的内存单元地址必须是连续的。（）27.栈和队列具有相同的逻辑特性。它们的逻辑结构都是线性表（）28.树形结构中每个结点至多有一个前驱。（）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。（）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。（）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。（）32.顺序查找方法只能在顺序存储结构上进行。2016数据结构域算法复习题2（）33.折半查找可以在有序的双向链表上进行。（）34.满二叉树中不存在度为 1 的结点。（）35.完全二叉树中的每个结点或者没有孩子或者有两个孩子。（）36.对 n 个元
5、素执行快速排序，在进行第一次分组时，排序码的比较次数总是 n-1 次。（）37.在有向图中，各顶点的入度之和等于各顶点的出度之和。一、选择题（A）1. 在 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是：A) 访问第 i 个结点（1in）和求第 i 个结点的直接前驱（2i n） C) 删除第 i 个结点（1in）B) 在第 i 个结点后插入一个新结点（ 1i n） D) 将 n 个结点从小到大排序（C）2. 算法分析的目的是：A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（A）3. 算法分析的两个主要方面是
6、：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性（C）4. 计算机算法指的是：A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法（B）5. 计算机算法必须具备输入、输出和 等 5 个特性。A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性（B）6. 一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是:（A）110 （B）108 （C）100 （D）120（D）下列选项中与数据存储结构无关的术语是：A.顺序表 B
7、.链表 C.链队列 D.栈（A）7. 链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C） 只有一部分，存储表示结点间关系的指针（D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数（B）8. 带头结点的单链表 head，链表为空的判定条件是(A)head = NULL (B) head-next =NULL ( C) head-next =head (D) head!=NULL（B）9. 一个栈的输入序列为 1，2，3，n，若输出序列的第一个元素是 n，输出第 i（1in）个元素是。A) 不确定 B) n
8、i1 C) i D) ni（B）10. 最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是 （ ） 。A) (rear1)% n=front B) rear=front C) rear1=front D) (rearl) % n=front（A）11. 循环队列 A0.m 1存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素数是:(A) (rearfrontm)%m (B) rearfront 1 (C) rearfront 1 (D) rearfront（B）12. 若用一个大小为 6 的数值来实现循环队列，且当前 rear
9、和 front 的值分别为 0 和 3，当从队列中2016数据结构域算法复习题3删除一个元素，再加入两个元素后，rear 和 front 的值分别为:(A) 1 和 5 (B) 2 和 4 (C) 4 和 2 ( D) 5 和 1（C）13. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。A) 3 B) 4 C) 5 D) 6 利用排列组合知识来做（B）14. 若一棵二叉树中度为 l 的结点个数是 3，度为 2 的结点个数是 4，则该二叉树叶子结点的个数是:(A) 4 (B) 5 (C) 7 (D) 8（B）15. 具有 n(n0)个结点的完全二叉树的深度为:() log 2(n) (
10、) log 2(n) () log 2(n) +1 () log 2(n)+1（D）16. 对一个满二叉树， m 个叶子，n 个结点，深度为 h，则:(A) n = h+m (B) h+m = 2n (C) m = h-1 (D) n = 2h-1（C）17在高度为 h 的完全二叉树中，表述正确的是（ ）A.度为 0 的结点都在第 h 层上 B.第 i(1inext ; (2) P-next = P; (3) P-next = P-next-next(4) P-next = P-next-next; (5) while(P!=NULL) P = P-next ;(6) while(Q-next
11、 != NULL) P = Q; Q=Q-next;(7) while(P-next != Q) P = P-next;(8) while(P-next-next != Q) P = P-next;(9) while(P-next-next != NULL) P = P-next;(10) Q = P; (11) Q = P-next; (12) P = L ; (13) L = L-next; (14) free(Q);7栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。8设栈 S 的初始状态为空，若元素 a、b、c、d、e、f 依次进栈，得
12、到的出栈序列是 b、d、c、f、e、a，则栈 S 的容量至少是 3 。9用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈顺序，相应的 S和 X 的操作串为 SXSSXSXX 。10数据的逻辑结构可以分为 线性 和 非线性 两大类。11数据的运算用 算法 表示。12逻辑上相邻的结点在存储器中也相邻，这是 顺序 存储结构的特点。13在长度为 n 的顺序表上实现定位操作，其算法的时间复杂度为 O(n) 。14为了实现随机访问，线性结构应该采用 顺序 存储。15在长度为 n 的顺序表中插入一个元素，最多要移动 n 个元素。16栈的存储结构主要有 顺序 和
13、链式 两种。2016数据结构域算法复习题617在编写程序的时候，如果栈的最大长度难以预先估计，则最好使用 链式 栈。18在树形结构中，如果某结点 没有前驱（双亲） ，则称该结点为根结点；如果某结点 没有后继（孩子） ，则称该结点为叶子。19在树形结构中，每个结点最多只有一个前驱（双亲） 。20 由 3 个结点所构成的二叉树有 5 种形态。 21二叉树的前序遍历按如下三个步骤进行： 访问根结点 ； 前序遍历左子树 ； 前序遍历右子树 。 【注意：中一定要加“前序”两字！】22二叉树的中序遍历按如下三个步骤进行：中序遍历左子树 ； 访问根结点 ；中序遍历左子树 。 【注意：中一定要加“中序”两字！
14、】23在 n 个顶点的无向图中，至少有 0 条边，至多有 n(n-1)/2 条边。24在 n 个顶点的有向图中，至少有 0 条边，至多有 n(n-1) 条边。25如果排序不改变关键字相同的记录之间的相对次序，则称该排序方法是稳定的。26如果排序改变了关键字相同的记录之间的相对次序，则称该排序方法是不稳定的。27当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是 直接插入排序 。28在一个图中，所有顶点的度数之和是所有边数的 2 倍。29无向图中边的数目等于邻接矩阵中非零元素个数的 0.5 倍。30折半查找有序表（4，6，12，20，28，38，50，70，88，100） ，若查找表中元素 20，它将依次与表中元素 28，6，12，20 比较大小。31在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素 9，其中第二次被比较的元素是 4 。32在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素 9，其中第三次被比较的元素是 6 。三、简答题1对链表设
