大连理工大学网络教育学院
2020年春《数据结构》
期末考试复习题
☆ 注意事项：本复习题满分共：200分。
一、单项选择题
1、在队列中存取数据的原则是（ ）。
A．先进先出 B．后进先出 C．先进后出
D．随意进出
2、在下列链表中，不能从当前结点出发访问到其余各结点的是（ ）。 A．单链表
B．单循环链表 C．双向链表
D．双向循环链表
3、在一棵二叉树上第5层的结点数最多为（ ）设树根为第1层。 A．16
B．15
C．8
D．32
4、一棵有124叶子结点的完全二叉树，最多有（ ）个结点。 A．247
B．249
C．248
D．125
5、具有10个叶子结点的二叉树中有（ ）个度为2的结点。 A．8
B．9
C．10
D．11
6、若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（ A．gdbehfca
B．bdgaechf
C．gdbecfha D．gcefhabd
7、对线性表进行顺序查找时，要求线性表的存储结构是（ ）。 A．倒排表
B．索引表 C．顺序表或链表
D．散列表
8、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找，则查找元素26的查找长度为（A．2
B．3
C．4
D．5
9、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（ ）。 A．希尔排序 B．起泡排序 C．插入排序
D．选择排序
2020年春季《数据结构》课程期末复习题 第1页 共8页
。 ）。 ） 10、堆的形状是一棵（ ）。 A．二叉排序树 C．完全二叉树
B．满二叉树 D．平衡二叉树
11、线性表采用顺序存储结构时，其地址（ ）。 A．必须是连续的 C．一定是不连续的
B．部分地址必须是连续的 D．连续与否均可以
12、在栈中存取数据的原则是（ ）。 A．先进先出 C．后进后出
B．后进先出 D．随意进出
13、插入和删除只能在一端进行的线性表，称为（ ）。 A．队列 C．栈
B．循环队列 D．数组
14、一个基本线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（ ）。 A．110
B．108
C．100
D．120
15、算法分析的目的（ ）。 A．找出数据结构的合理性 C．分析算法的效率以求改进
B．研究算法中的输入与输出的关系 D．分析算法的易懂性和文档性
16、结点前序为xyz的不同二叉树，那么它有（ ）种不同状态。 A．3
B．4
C．5
D．6
17、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ）。 A．98
B．99 C．50
D．48
18、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ），设根结点的所在高度为1。 A．2h
B．2h-1 D．h+1
C．2h+1
19、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ ）条边。 A．n
B．n+1 D．n/2
C．n-1
20、存储在磁带上的顺序文件的查找只能用（ ）。
2020年春季《数据结构》课程期末复习题 第2页 共8页
A．顺序查找 C．分块查找 单选题答案
B．二分查找 D．树表查找
1． A 2． A 3． A 4． C 5． B 6． A 7． C 8． C 9． D 10． C 11． A 12．B 13．C 14．B 15． C 16． C 17．A 18．B 19．C 20． A
二、填空题
1、一个算法有五个特性：_______、_______、_______、有零个或多个输入、有一个或多个输出。 2、栈S在进行出栈操作时首先要判断_______。
3、在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=_______。 4、设front为队首指针，rear为队尾指针，则循环队列sq是空队列的条件是_______。 5、同一数组中各元素的长度_______。
6、深度为k的二叉树共有2k-1个结点，该二叉树为_______二叉树。 7、若图G中每条边都_______方向，则称G为无向图。 8、二叉树的按层次遍历类似于图的_______遍历。 9、选择排序算法的效率为_______。 10、冒泡排序算法的效率为_______。 答案：
1、有穷性、确定性、可行性 2、栈空否 3、n2+1
4、sq->rear==sq->front 5、相等 6、满 7、没有 8、广度优先 9、O(nlogn) 10、O(n2)
三、判断题
2020年春季《数据结构》课程期末复习题 第3页 共8页
1、数组的缺点是插入、删除运算效率低。（ √ ） 2、链表的优点是插入、删除运算效率高。（ √ ） 3、对图进行深度优先遍历时，应借助于一个队列。（ × ） 4、二叉树的深度优先遍历与先序序列一致。（ √ ） 5、归并排序算法是原地算法。( × )
6、堆数据结构可以看作是一个非完全二叉树。( × ) 7、对图进行广度优先遍历时，应借助于一个队列。（ √ ） 8、二叉树的深度优先遍历与后序序列一致。（ × ） 9、对图进行广度优先遍历时，应借助于一个栈。（ × ） 10、冒泡排序算法是原地算法。( √ )
四、 简答题
1、初始为空的队列中，元素f,e,d,c,b,a依次进队以后，连续进行了三次出队操作，此时的队首元素是什么？
队尾元素是什么？队列操作应遵循的原则是什么？ 答：
（1） 队首元素是c （2） 队尾元素是a
（3） 队列操作应遵循的原则是先进先出
2、当为解决某一问题而选择数据结构时，应从哪些方法考虑？
答：
通常从两方法考虑；第一是算法所需的存储空间量，第二是算法所需的时间。 对算法所需的时又涉及以下几点： 1）程序运行时所需输入的数据总量 2）计算机执行每条指令所需的时间 3）程序中指令重复执行的次数
3、写出用直接插入法排序将数值序列{33,23,8,41,68,64,50}排序过程的每一趟结果。
答：（1）23 33 8 41 68 64 50
（2）8 23 33 41 68 64 50 （3）8 23 33 41 68 64 50 （4）8 23 33 41 68 64 50 （5）8 23 33 41 64 68 50 （6）8 23 33 41 50 64 68
2020年春季《数据结构》课程期末复习题 第4页 共8页
4、简述顺序表特点。
答：优点：
可随机存取表中任意数据元素，算法简单，空间利用率高； 直接可获取线性表的长度。
缺点：
1）需要预先确定数据元素的最大个数；
2）数据元素的插入、删除相对麻烦，插入和删除时需要移动较多的数据元素。 5、简述逻辑结构和存储结构的关系。
答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各种数据元素间的逻辑关系。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储或链式存储结构表示。
6、简述线性表、栈和队列的异同。
答：线性表、栈和队列中元素这之间的逻辑关系都是线性关系。栈和队列是操作位置受限的线性表，即对播入和删除操作的位置加以限制，都只能在端点进行。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。队列是只允许在表的一端进行插入，另一端进行删除操作的线性表，因而是先进先出表。
7、堆排序是否是一种稳定的排序方法？为什么？
答：堆排序是不种不稳定的排序方法。因为在堆的调整过程中，关键字进行比较和交换所走的是该节点到叶子节点的一条路径，因此对相同的关键字而言，就可能出现排在后面的关键字补交换到前面来的情况。
8、若频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构，为什么？
答：宜采用链式存储结构。因为采用链式结构存储线性表，在插入和删除操作时只修改相关节点的指针域，不需要移动节点；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。修改指针域操作比移动元素操作花费的时间少得多。 9、对单链表设置头节点的作用是什么？
答：对于带头节点的单链表，在单链表的任何节点之前插入节点或删除节点，所要做的都是修改前一个节点的指针域，因为任何节点都有前驱节点（若单链表没有头节点，则首节点没有前驱节点，在其前插入节点和删除节点时操作复杂些）。对于带头节点的链表，在表空时也存在一个头节点，因此空表与非空表的处理是一样的。
2020年春季《数据结构》课程期末复习题 第5页 共8页
大工20春9月网考【数据结构】复习资料
