《数据结构与算法》期末考试试题及答案
一、 选择题 1.在逻辑上可以把数据结构分成（ A ） A.线性结构和非线性结构 B.动态结构和静态结构 C.紧凑结构和非紧凑结构 D.内部结构和外部结构 2. 单链表中各结点之间的地址（C ） A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对 3.在一个长度为n 的顺序表中向第i 个元素（0
A.P->NEXT=Q->NEXT;FREE(Q);
B.Q->NEXT=P; FREE(Q);
C.Q->NEXT=P->NEXT;FREE(Q);
D.P->NEXT=S;S->NEXT=P; 13.循环队列SQ 队满的条件是（B ）。 A.SQ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ->fro nt C.SQ->rear==0 D. SQ->front==0 14.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为(B )。 A 、79，46，56，38，40，80 B 、84，79，56，38，40，46 C 、84，79，56，46，40，38 D 、84，56，79，40，46，38 15.排序趟数与序列原始状态(原始排列)有关的排序方法是（ACD ）方法。 A 、插入排序 B 、选择排序 C 、冒泡排序 D 、快速排序 16.下列排序方法中，（B ）是稳定的排序方法。 A 、直接选择排序 B 、二分法插入排序 C 、希尔排序 D 、快速排序 17.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(C )的两趟排序后的结果。 A 、选择排序 B 、冒泡排序 C 、插入排序 D 、堆排序 18.对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C ）排序。 A 、选择 B 、快速 C 、希尔 D 、冒泡 19.一组待排序记录的关键字为（46，79，56，38，40，84），则利用快速排序，以第一个记录为基准元素得到的一次划分结果为（ C ）。 A(38,40,46,56,79,84) B 、(40,38,46,79,56,84) C 、(40,38,46,56,79,84) D 、(40,38,46,84,56,79) 20.用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。 A 、94,32,40,90,80,46,21,69 B 、32,40,21,46,69,94,90,80 C 21,32,46,40,80,69,90,94 D 、90,69,80,46,21,32,94,40 21.若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（B ）。 A 、10 B 、15 C 、21
D 、34 22.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（A ）。 A 、堆排序<快速排序<归并排序 B 、堆排序<归并排序<快速排序 C 、堆排序>归并排序>快速排序 D 、堆排序>快速排序>归并排序 23.最小生成树的构造可使用（B ）算法。 A.Dijkstra 算法
B.Prim 算法
C.Haffman 算法
D.Floyd 算法 24. 具有32个结点的完全二叉树的深度为（B ）。 A. 5 B.6 C.7
D.8 25. 在有n 个叶子结点的哈夫曼树中，其结点总数为（D ）。 A ．不确定 B ．2n C ．2n+1 D ．2n-1 26.下列陈述正确的是（B ）。 A.二叉树是度为2的有序树 B. 二叉树中最多只有二棵树,且有左右子树之分 C.二叉树必有度为2的结点 D. 二叉树中结点只有一个孩子时无左右之分 27.先序为A ，B ，C 的二叉树共有（A ）种。 A.3 B.4 C.5 D.6 28.在树结构中,若结点B 有3个兄弟,A 是B 的父亲结点,则A
的度为(B )。
A.3
B.4
C.5
D.6 29.在一个图中，所有顶点的度数之和等于所有边数的（B ）倍。 A 、1 B 、2 C 、3 D 、4 30.n 个顶点的强连通图至少有（A ）边。 A 、n B 、n-1 C 、n+1 D 、n (n-1) 31.在一个无向图中，所有顶点的度数之和等于所有边数的（C ）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C ）倍。 A 、1/2 B 、2 C 、1
D 、4 32.任何一个无向连通图的最小生成树（B ）。 A 、只有一棵 B 、一棵或多棵 C 、一定有多棵 D 、可能不存在 33.在图的表示法中，表示形式唯一的是（A ） A 、邻接矩阵表示法 B 、邻接表表示法 C 、逆邻接矩阵表示法 D 、逆邻接表表示法 34.在一个具有n 个顶点的无向图中，要连通全部顶点至少需要（C ）条边。 A.n B.n+1 C.n-1 D.n+2 35. 在一个图中，所有顶点的度数之和等于图的边数的（B ）。 A ．1/2 B ．2 C ．1 D ．4 36．有7个结点的有向完全图有（C ）边。 A.30 B.40 C.42 D.56 37.假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，则叶子结点数为（B ）。 A 、15 B 、16 C 、17 D 、47 38.设n ，m 为一棵树上的两个结点，在中根遍历时，n 在m 前的条件是（C ）。 A 、n 在m 右方 B 、n 是m 祖先 C 、n 在m 左方 D 、n 是m 子孙 39.某二叉树的后序遍历序列为：DABEC ，中序遍历序列为：DEBAC ，则前序遍历序列为（D ）。 A 、ACBED B 、DECAB C 、DEABC D 、CEDBA 40.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子的编号为（90），右孩子的编号为（91）。 A 、46 B 、47 C 、91 D 、91 41.某树中，若结点B 有4个兄弟，A 是B 的父亲结点，则A 的度为（C ）。 A 、3 B 、4 C 、5 D 、6 42.下列叙述正确的是（D ） A 、二叉树是度为2的有序树 B 、二叉树结点只有一个孩子时无左右之分 C 、二叉树中必有度为2的结点 D 、二叉树中最多只有两棵子树，且有左右之分 43.由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（D ）。 A 、23 B 、37 C 、46 D 、44 44．在图的表示方法中，表示形式是唯一的是（C ）。 A.邻接表 B.逆邻接表 C.邻接矩阵 D.其他 44.下列关键字序列中，构成大根堆的是(D ) A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33 C.9，8，6，3，5，l ，2，7 D.9，8，6，7，5，1，2，3 45.对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C ）排序。 A.选择 B.快速 C.希尔 D.冒泡 46.设n ，m 为一棵树上的两个结点，在中根遍历时，n 在m 前的条件是（C ）。 A.n 在m 右方 B.n 是m 祖先 C.n 在m 左方 D.n 是m 子孙 二、填空题 1.树和 图 都属于非线性结构。 2.顺序表中逻辑上相邻的元素在物理位置上 也 相邻。 3.双向链表有两个指针域，一个指向前趋，另一个指向__后继__。 4.若进栈的次序是A,B,C,D,E,写出两种出栈顺序_ABCD
E 、EDCBA 。 5.队列存取数据应遵循的原则是先进先出。 6.有20个结点的完全二叉树，编号为7的结点的父结点编号为 3 。 7.两个序列分别为：L1={3，50，41，42，55，65，70，75}，L2={3，50，41，42，65，55，. 10，5}，用冒泡排序法对L1和L2进行排序，交换次数较少的是序列： L1 。 8.在排序方法中，从无序序列中选择关键字最小的记录，与无序区（初始为空）的第一个记录交换的排序方法，称为 选择 排序。 9.有向图的边也称为 弧，用邻接矩阵存储有向图，其第i 行的所有元素之和等于顶点i 的 出度 。 10．树转换成的二叉树，其根结点的 右 子树一定为空。 11.二叉排序树是一种 动态 查找表。 12.对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7条记录60插入到有序表中时，为寻找插入位置需比较 15 次。 13.在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后继 结点，其余结点的后继结点可以任意多个。 14.在具有n 个结点的二叉树中，有n+1个空指针。 15.深度为k 的完全二叉树至
少有2k-1个结点，至多有2k
-1个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是n/2+1。 16.由a ，b ，c 三个结点构成的二叉树，共有 30种不同形态，若是构成树，共有9 种形态。 17.树所对应的二叉树其根结点的 右 子树一定为空。 18.已知完全二叉树的第8层有8个结点，则其叶结点数是 68 三、综合应用题。 2.已知完全二叉树的第8层有4个结点，请计算它的叶子结点数和总结点数。（写出计算过程）。（6分） 解：由题意可知， 该完全二叉树有八层，其中 第一层结点数为：1 第二层结点数为：2 第三层结点数为：4 第四层结点数为：8 第五层结点数为：16 第六层结点数为：32 第七层结点数为：64 第八层结点数为：4 因为第八层结点数为4，且为完全二叉树，则第八层四个结点为叶子结点，第七层前两个结点有子结点，其余62个结点无子结点，则第七层的后62个结点为叶子结点，故叶子结点数有4+62=66 总结点数为1+2+4+8+16+32+64+4=131