2015秋北语数据结构模拟试卷和答案

北京语言大学网络教育学院

《数据结构》模拟试卷一

一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用（ [C] ）存储方式最节省时间。 [A] 顺序表 [B] 双链表 [C] 带头结点的双循环链表 [D] 单循环链表 2、队列操作的原则是（ d ）。 [A] 只能进行删除 [B] 后进先出 [C] 只能进行插入 [D] 先进先出

3、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ b ）的二叉树。 [A] 空或只有一个结点 [B] 高度等于其结点数 [C] 任一结点无左孩子 [D] 任一结点无右孩子 4、在下列排序方法中，（ c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)。 [A] 插入排序 [B] 希尔排序 [C] 快速排序 [D] 堆排序

5、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一个结点的左、右孩子中，其左孩子编号小于右孩子编号。则可采用（ c ）次序的遍历实现编号。 [A] 先序 [B] 中序 [C] 后序 [D] 从根开始的层次遍历

6、若用数组S[n]作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S[n]全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（ c ）。 [A] S1的栈底位置为0，S2的栈底位置为n [B] S1的栈底位置为－1，S2的栈底位置为n/2 [C] S1的栈底位置为0，S2的栈底位置为n－1 [D] S1的栈底位置为0，S2的栈底位置为n/2

7、对一棵二叉排序树进行（ C ）遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。 [A] 前序 [B] 后序 [C] 中序 [D] 按层次 8、在下列排序算法中，（ D ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 [A] 堆排序 [B] 冒泡排序 [C] 快速排序 [D] 插入排序 9、采用邻接表存储的图的广度优先算法类似于二叉树的（ D ）。 [A] 先序遍历 [B] 中序遍历 [C] 后序遍历 [D] 层次遍历 10、具有6个顶点的无向图至少应有（ B ）条边才能保证图的连通性。

[A] 4 [B] 5 [C] 6 [D] 7 二、【判断题】(本大题共10小题，每小题2分，共20分)正确的填T，错误的填F，填在答题卷相应题号处。

11、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（ T ）

12、任何二叉树都唯一对应一个森林，反之亦然。 （ T ） 13、有向图的邻接矩阵一定是对称的。 （ F ） 14、线性表的链式存储结构优于顺序存储结构。 （ F ） 15、关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。 （ F ）

16、直接选择排序是一种不稳定的排序方法。 （ T ） 17、顺序表用一维数组作为存储结构，因此顺序表是一维数组。 （ F ） 18、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。 （ T ） 19、闭散列法通常比开散列法时间效率更高。 （ F ） 20、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。 （ F ） 三、【填空题】（本大题共10小空，每小空2分，共20分）请将答案填写在答题卷相应题号处。 21、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和（运算 ）。 22、若要在单链表结点*P后插入一结点*S，执行的语句（ S->next=p->next;p->next=s ）。 23、折半搜索只适合用于（ 有序表 ）。

24、栈结构允许进行删除操作的一端为（ 栈顶 ）。

25、设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为（ 1130 ）。

26、若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为（ 69 ）。

27、一棵具有5层满二叉树中节点总数为（ 31 ）。

28、从树中一个结点到另一个结点之间的分支构成这两个结点之间的（路径）。 29、在无向图中，若从顶点A到顶点B存在（路径），则称A与B之间是连通的。 30、若图的邻接矩阵是对称矩阵，则该图一定是（无向图）。 四、【应用题】（本大题共5小题，每小题8分，共40分）请将答案填写在答题卷相应题号处。

31、已知序列（12，4，17，10，7，30），用直接选择排序法对其进行递增排序，写出每一趟的排序结果。

答：第1趟：4 12 17 10 7 30 第2趟：4 7 17 10 12 30

第3趟：4 7 10 17 12 30 第4趟：4 7 10 12 17 30 第5趟：4 7 10 12 17 30

32、单链表结点的类型定义如下： typedef struct LNode { int data;

struct LNode *next; } LNode, *Linklist; 写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。（注：不破坏A和B的原有结构）

Merge(Linklist A, Linklist B, Linklist &C ) void Merge(Linklist A, Linklist B, Linklist &C) { C=(Linklist)malloc(sizeof(LNode)); pa=A->next; pb=B->next; pc=C; while(pa&&pb)

{ pc->next=(Linklist)malloc(sizeof(LNode)); pc=pc->next;

if(pa->data<=pb->data)

{ pc->data=pa->data; pa=pa->next;} else

{ pc->data=pb->data; pb=pb->next;} }

if(!pa) pa=pb; while(pa)

{ pc->next=(Linklist)malloc(sizeof(LNode)); pc=pc->next;

pc->data=pa->data; pa=pa->next; }

pc->next=NULL; }

33、已知一棵非空二叉树，其按中序和后序遍历的结果分别为： 中序：CGBAHEDJFI 后序：GBCHEJIFDA 请画出这棵二叉树，并写出其前序遍历的结果。 答：

前序遍历结果:ACBGDEHFJI

34、已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。 标准答案：

c1:10 c2:1111 c3:01 c4:1110 c5:110 c6:00

35、已知如下图所示二叉树，分别写出其前序、中序和后序序列。 A B C

D E F 前序：ABDECF 中序：DBEACF 后序：DEBFCA