2016《数据结构域算法》复习题
复习题集─参考答案
一判断题
（√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机内部表示和实现无关。
（×）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。
（×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。
（√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）14.二叉树的度为2。
（√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。
（√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。
（√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。
（×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。
（×）24.判断某个算法是否容易阅读是算法分析的任务之一。
（×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的内存单元地址必须是连续的。
（√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。
（×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。
1
2016《数据结构域算法》复习题
（√）34.满二叉树中不存在度为1的结点。
（×）35.完全二叉树中的每个结点或者没有孩子或者有两个孩子。
（√）36.对n个元素执行快速排序，在进行第一次分组时，排序码的比较次数总是n-1次。 （√）37.在有向图中，各顶点的入度之和等于各顶点的出度之和。
一、选择题
（A）1. 在n个结点的顺序表中，算法的时间复杂度是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) 分析算法的易懂性和文档性 （A）3. 算法分析的两个主要方面是：
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.链表 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（1≤i≤n）个元素是。
A) 不确定 B) n－i＋1 C) i D) n－i
（B）10. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A) (rear＋1)% n==front B) rear===front C) rear＋1==front D) (rear－l) % n==front （A）11. 循环队列A[0..m－1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是:
(A) (rear－front＋m)%m (B) rear－front＋1 (C) rear－front－1 (D) rear－front
（B）12. 若用一个大小为6的数值来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为: (A) 1和5 (B) 2和4 (C) 4和2 ( D) 5和1
2
2016《数据结构域算法》复习题
（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(n>0)个结点的完全二叉树的深度为:
(Ａ) ?log2(n)? (Ｂ) ? log2(n)? (Ｃ) ? log2(n) ?+1 (Ｄ) ?log2(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(1≤i （B）18. 深度为5的二叉树至多有（ ）个结点。 A) 32 B) 31 C) 16 D) 10 （A）19. 用邻接表表示图进行深度优先遍历时，通常采用( )结构来时实现算法。 A) 栈 B) 队列 C) 树 D) 图 （D）20. 对N个记录作顺序查找时，当查找成功时，平均查找长度是（ ）。 A) N2 B) N2/2 C) N D)（N﹢1)/2 （B）21. 当一个有n个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。 (A) ?A[i,j] B) ?A[i,j] C)?A[j,i] D)?A[i,j]+?A[j,i] i?1j?1nnnnni?1i?1j?1（C）22．某算法的时间复杂度为O(2n)，表明该算法的（ ） A.问题规模是2n B.执行时间等于2n C.执行时间近似与2n成正比 D.问题的规模近似与2n成正比 （D）23．“二叉树为空”意味着二叉树（ ） A.由一些没有赋值的空结点构成 B.根结点没有子树 C.不存在 D.没有结点 （D）24．数据结构的研究内容不涉及（ ） A.数据如何组织 B.数据如何存储 C.数据的运算如何实现 D.算法用什么语言描述 （C）25．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 （D）26．数据采用顺序存储，要求（ ） A.存储的是属于线性结构的数据 B.根据结点值的大小，有序存放各结点 C.按存储单元地址由低到高的顺序存放各结点 D.各结点存放方法有规律，能隐含表示结点间的逻辑关系 （D）27．一个顺序表所占存储空间大的大小与（ ）无关 A.顺序表长度 B.结点类型 C.结点中各字段的类型 D.结点存放顺序 （A）28．数据采用链接存储，要求（ ） A.每个结点占用一片连续的存储区域 B.所有结点占用一片连续的存储区域 C.结点的最后一个字段是指针型的字段 C.每个结点有多少个后继，就设多少个指针字段 （A）29．算法的时间复杂度与（ ）有关 3