数据结构与算法复习题及参考答案

本文格式为Word版，下载可任意编辑——数据结构与算法复习题及参考答案2023《数据结构域算法》复习题

复习题集─参考答案

一判断题

（√）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

2023《数据结构域算法》复习题

（√）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＋1C)iD)n－i

（B）10.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A)(rear＋1)%n==frontB)rear===frontC)rear＋1==frontD)(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

2023《数据结构域算法》复习题

（C）13.依照二叉树的定义，具有3个结点的二叉树有（）种。

A)3B)4C)5D)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≤inext;(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!=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依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是3。

9．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为SXSSXSXX。10．数据的规律结构可以分为线性和非线性两大类。11．数据的运算用算法表示。

12．规律上相邻的结点在存储器中也相邻，这是顺序存储结构的特点。13．在长度为n的顺序表上实现定位操作，其算法的时间繁杂度为O(n)