数据结构复习题及答案.doc

1、数据结构习题 一、名词解释 1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、 算法、时间复杂度、空间复杂度。 2. 线性表、顺序表、单链表 、双向链表、循环链表 、双向循环链表、三个概念的区别：头 指针、头结点、首元结点（第1个元素结点 ）。 3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。 4. 树、叶子结点、结点的度、树的度、树的高（深）度、二叉树、遍历、满二叉树、完全二叉树、 哈夫曼树、WPL哈夫曼编码。 5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、 （最小）生

2、成树、邻接矩阵、邻接表、DFS BFS 6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。 7. 排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2 路归并。 填空题 1. 数据结构是研究数据的 _逻辑结构_和物理结构_，并在这种结构上定义相关的运算，设计实 现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为时间 复杂度 和空间复杂度。 2. 数据的基本单位是数据元素，数据的最小单位是数据项 。 3. 算法是对特定问题求解 步骤_的一种描述，是指令的有限序列。 4. 一个算法的时间复杂度为

3、 （3n3+2n 7），其数量级表示为_0 （ n3）_。 5. 一个算法具有5个特性：_确定性、可行性_、_有穷性_、输入和输出。 6. 算法性能的分析和度量，可以从算法的时间复杂度一和空间复杂度来评价算法的优劣。 7. 数据的逻辑结构包括集合结构、_线性结构 _、树形结构_和_图型结构四种类型。 8. 数据结构在计算机中的表示称为数据的物理结构，它可以采用_顺序存储_ 或_链式存储_ 两种存储方法。 9. 线性表有两种存储结构，分别为_顺序存储 _ 和 链式存储_。 10. 链式存储的特点是利用指针来表示数据元素之间的逻辑关系。 11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用链

4、式存储存储结构。 12. 线性表中的数据元素之间具有_一对一_的线性关系，除第一个和最后一个元素外，其他数据 元素有且只有一个_直接后继和直接前趋。 13. 在一个单链表中 p所指结点之后插入一个s所指结点时，应执行 s-next=_ p-next和 p-next=_ s的操作。 head-next=NULL 14. 在一个单链表中删除 p的后继结点q时，应执行以下操作 p-next=q-next。 15. 对带头结点head的单链表，则判断其为空的条件为 16. 对带头结点head的循环单链表尾结点(由p所指向)判非空的条件为 _p-next=head 。 17. 在栈结构中，允许插入的一端

5、称为 _栈顶;在队列结构中，允许插入的一端称为_队尾。 18. 队列中元素的入队和出队应遵循一先进先出_ _原则，数据元素1，2, 3, 4，5按照次序入队 后，第一个出队的是 _1。 19. 在循环队列中，存储空间为0n-1。设队头指针front指向队头元素前一个空闲元素，队尾指 针指向队尾元素，那么其队空标志为rear=front ，队满标志为_(rear+1)% n=front_。 20. 设顺序表有19个元素，第一个元素的地址为200,且每个元素占3个字节，则第14个元素的存 储地址为_239。 21. 在一个长度为n的顺序表中删除第i个元素(K i n),需向前移动n-i 个元素。

6、22. 在一个长度为 n的顺序表中第i个元素前(K i lchild=NULL 若初始记录基本无序， 则最好选用快速排序。 99. 在对一组记录(54,38,96,23,15,72, 60,45,83)进行直接插入排序时，当把第7个记录 60插入到有序表时，为寻找插入位置至少需比较_3次。 100. 设一组记录关键字序列为(80, 70, 33, 65, 24, 56, 48)，则用筛选法建成的初始堆为_ ( 80, 70, 56, 65, 24, 33, 48)或 _(24 , 65, 33, 80, 70, 56, 48)。 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 1

7、1. 二、单选题 在数据结构中，数据的基本单位是 （ ） A. 数据项 B. 数据元素 C. 数据对象 D. 数据文件 数据结构是（ ） A. 种数据类型B数据的存储结构 C. 一组性质相同的数据元素的集合 D.相互之间存在一种或多种特定关系的数据元素的集合 A.数据项B. 数据元素 C. 表元素 D. 字符 在数据结构的讨论中把数据结构从逻辑上分为（ ）. A. 内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构。 算法指的是（ ）。 A.计算机程序 B .解决问题的计算方法 C .排序算法 D .解决问题的有限运算序列 算法分析的目的是（

8、A.辨别数据结构的合理性 B .评价算法的效率 C.研究算法中输入与输出的关系 .鉴别算法的可读性 某程序的时间复杂度为（ 3n+nlog 2n+n 2+8） , 其数量级表示为（ ）。 A. O（ n）B . O（ nlog 2n） C . O（ n ）D . O（ log 2n） for （ i=0 ； in ； i+ ） for （ j=0 ； jn ；j+ ） A i j =i*j ； 上述程序段的时间复杂度为 （） 2n） D.O（ 1） A.O（n2）B.O （n）C.O 以下数据结构中哪一个是非线性结构？ A. 队列 B. 栈 C. 线性表 D. 二叉树 设顺序表有 9 个元素，则在第 3 个元素前插入一个元素所