第3部分 模拟试题及参考答案

第3部分 模拟试题及参考答案

模拟试题1

一、选择题(20分)

1．双向链表中有两个指针域，llink和rlink分别指向前趋和后继，设p指向链表中的一个结点(链表结点数大于2，p不是第一个结点)，现在要求删去p所指结点，则正确的删除是( )。

A) p->rlink->llink=p->llink;p->llink->rlink=p->rlink;free(p); B) free(p);p->rlink->llink=p->llink;p->llink->rlink=p->rlink; C) p->rlink->llink=p->llink;free(p);p->llink->rlink=p->rlink; D) 以上A，B，C都不对。

2．对一组数据(84,47,25,15,21)排序，数据的排列次序在排序过程中的变化为：

1) 84, 47,25,15,21 2) 15, 47,25,84,21 3) 15, 21,25,84,47 4) 15, 21,25,47,84 则采用的排序是( )。 A) 冒泡 B) 选择 C) 快速 D) 插入 3．栈和队列都是( )。 A) 顺序存储的线性结构 B) 链式存储的非线性结构 C) 限制存取点的线性结构 D) 限制存取点的非线性结构

4．设有数组A[i, j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为( )。

A) BA+141 B) BA+180 C) BA+222 D) BA+225

5．设元素X，Y，Z顺序进栈(进栈的过程中允许出栈)，得不到的出栈序列是( )。 A) XYZ B) YZX C) ZXY D)ZYX 6．适用于折半查找的表的存储方式及元素排列要求为( )。 A) 链式方式存储，元素无序 B) 链式方式存储，元素有序 C) 顺序方式存储，元素无序 D) 顺序方式存储，元素有序

7．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。 A) 1/2 B) 2 C) 4 8．归并排序的时间复杂度是( )。

D) 1

A) O(n2) B) O(n) C) O(nlog2n) D) O(log2n) 9．( )遍历一棵二叉排序树所得的结点访问序列是按结点值的递增序列。 A) 先序 B) 中序 C) 后序 D) 以上均不是 10．链表不具有的特点是( )。 A) 插入删除不需要移动元素 B) 可随机访问任意元素 C) 不必要先估计存储空间 D) 所需空间与线性长度成正比

·2· 数据结构简明教程（C语言描述）

二、填空题(20分)

l．计算机执行下面的循环语句时，语句“k++;”的执行次数为___________。

for(i=l;i

for(j=n;j>=i;j--)k++;

2．对任意二叉树T，叶子数为n0，度为2的结点的个数是n2，则n0与n2的关系是 ___________。

3．已知有序表为(12,18,24,35,47,50,62,83,90,134)当用二分法查找90时，需___________次比较成功，查找47时需___________次比较成功，查找100时需___________次才能确定不成功。

4．设F是由T1，T2，T3三棵树组成的森林，与F对应的二叉树为B，已知T1，T2，T3的结点数分别为n1，n2和n3，则二叉树B的左子树中有___________个结点，右子树中有___________个结点。

5．有向图G=(V,E)，其中 V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权d。E(G)为{<0,5,100>,<0,2,10>,<1,2,5>,<0,4,30>,<4,5,60>,<3,5,10>,<2,3,50>,<4,3,20>}，则从源点0到顶点3的最短路径长度是_____________，经过的中间顶点是_____________。

6．在直接插入排序、冒泡排序、简单选择排序中，稳定的排序方法为___________。

三、判断题(10分)

1．在某工程的AOE网中，加速其关键路径上的关键活动均可缩短整个工程的完成时间。( ) 2．Hash表的平均查找长度与处理冲突的方法无关。( )

3．完全二叉树中，若一个结点没有左子女，则必是树叶。( )

4．带头结点的链队列执行出队操作不会改变头指针的值，但可能会改变尾指针的值。( ) 5．当待排序记录从小到大排序或者从大到小排序时，快速排序的执行时间最省。( ) 6．有e条边的无向图，其邻接表中有2e个表结点。( )

7．线性表采用链表存储时，结点的存储空间可以是不连续的。( ) 8．所谓取广义表的表尾就是返回广义表中最后一个元素。( ) 9．一棵树中的叶子数一定等于与其对应的二叉树的叶子数。( )

10．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。( )

四、应用题(20分)

1．设哈希函数H(key)=key，用链地址法处理冲突法，在地址空间为0～10的散列区间中，对关键字序列(22,41,53,46,30,13,01,67)构造一个哈希表。

2．已知长度为9的表(19,14,23,01,66,21,83,27,56)，画出以该序列进行堆排序时所建立的第一个小根堆。

3．已知二叉树的中序序列为DGBAECF，后序序列为GDBEFCA，试画出该二叉树的先序线索树。 4．以数据集{3,4,5,8,12,18,20,30}为叶结点，构造一棵哈夫曼树并求其带权路径长度。 5．写出下图所示有向图的所有拓扑排序序列。

B G C D G 6．给定下图，按普里姆算法，画出其最小生成树(从顶点V1开始)。

第3部分 模拟试题及参考答案 ·3·

五、算法设计题(30分)

1．设计一个算法，判别给定二叉树是否为二叉排序树(10分)。

2．设计一个算法，判断以邻接表方式存储的有向图中是否存在从顶点vi到顶点vj的简单路径(10分)。

3．已知一棵以线索链表为存储结构的中序线索二叉树T，设计一个算法，试在该二叉树上求任意结点x的中序后继(10分)。

模拟试题2

一、选择题(20分)

1．广义表L=(A,(B,C))，进行TAIL(L)操作后的结果为( )。

A) C B) B,C C) (B,C) D) ((B,C))

2．一棵3阶树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为( )个。

A) 4 B) 5 C) 6 D) 7

3．在一个图中，所有顶点的度数之和等于所有边数的( )倍 。

A) 1/2 B) 2 C) 1 D) 4

4．下列排序算法中，( )排序在某趟结束后不一定能选出一个元素放到其最终的位置上。 A) 选择 B) 冒泡 C) 归并 D) 堆 5．下列四棵二叉树中( )是一个堆。

6．递归函数调用时，处理参数及返回地址，要用一种称为( )的数据结构。 A) 队列 B) 多维数组 C) 栈 D) 线性表 7．在等概率情况下，顺序查找成功时的平均查找长度为( )。

A) n B) 2n C) n+1 D) (n+1)/2 8．下列排序算法中，其中( )是稳定的。 A) 堆排序，冒泡排序 B) 归并排序，冒泡排序 C) 直接选择排序，归并排序 D) 快速排序，堆排序

9．设输入序列为(A,B,C,D)，借助栈，规定A 最先输出，不可能的输出序列为( )。 A) A,B,D,C C) A,D,B,C

B) A,D,C,B D) A,C,D,B

·4· 数据结构简明教程（C语言描述）

10．设给定权值总数有n 个，其哈夫曼树的结点总数为( )。 A) 2n﹣1 B) 2n C) 2n+1 D) 不确定 二、填空题(20分)

1．数据元素在计算机中有两种基本的存储结构：_____________和_____________。

2．设G为具有n个顶点的无向图，则最多有_____________条边；若G为具有n个顶点的有向图，则最多有_____________条边。

3．单链表中除首元结点外，其余结点的存储位置由_____________________指示。

4．设有m个结点的完全二叉树顺序存放在向量A[1..m]中，对任一结点A[i]，若A[i]有父母，则其父母是_____________，若A[i]有左孩子，则左孩子是_____________。

5．静态查找和动态查找的区别在于____________________。

6．k(k>1)层的完全二叉树上至少有_________个结点，至多又有_____________个结点。

三、判断题(10分)

1．栈是限定仅在表尾进行插入或删除操作的线性表。( )

2．平衡二叉树上所有结点的平衡因子只能是1，0，﹣1。 ( ) 3．有n个顶点、n﹣1边的图是一棵生成树。( )

4．在有序的顺序表和有序的链表上，均可使用折半查找来提高查找效率。( ) 5．关键路径指的是AOE网中从开始点到完成点路径长度最短的路径。( ) 6．已知二叉树的先序遍历序列和中序遍历序列能唯一确定一棵二叉树。( )

7．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。( ) 8．顺序存储结构的主要缺点是不利于插入或删除操作。( )

9．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。( ) 10．对一棵二叉树进行层次遍历时，应借助于一个队列。( ) 四、应用题(20分)

1．设哈希函数H(key)=key，用线性探测法处理冲突,在地址空间为0～10的散列区间中，对关键字序列(22,41,53,46,30,13,01,67)构造一个哈希表。

2．写出下图所示森林的先序遍历序列和中序遍历序列，然后将森林转换成相应的二叉树。

1 5 7 2 3 4 6 8 9 10 3．以数据集{5,29,7,8,23,14,3,11}为叶结点，构造一棵哈夫曼树。

4．对关键字序列(66,27,70,12,100,30,92,35,85,50)进行希尔排序，设步长分别为5、3、1，写出每一趟排序结束时关键字序列。

5．已知长度为10的表为(19,14,23,01,66,21,83,27,56)，试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树。

6．请看下边的带权无向图。 (1) 写出它的邻接矩阵。

第3部分 模拟试题及参考答案 ·5·

(2) 按克鲁斯卡尔算法求其最小生成树。 五、算法设计题(30分)

1．设计一个算法，实现有序表的折半查找。(10分)

2．设计一个算法，实现中序线索二叉树的中序遍历。(10分) 3．设计一个算法，求一个无向图中连通分量的个数。(10分)

模拟试题3

一、选择题(20分)

1．数据序列(2,1,4,9,8,10,6,20)只能是下列排序算法中的( )的两趟排序后的结果。 A) 快速排序 B) 冒泡排序 C) 选择排序 D) 插入排序

2．分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。 A) (100,80,90,60,120,110,130) B) (100,120,110,130,80,60,90) C) (100,60,80,90,120,110,130) D) (100,80,60,90,120,130,110)

3．一棵左右子树均不空的二叉树先序线索化后，其中空链域的个数是( )。 A) 0 B) 1 C) 2 D) 不确定

4．设一个栈的输入序列是(1,2,3,4,5 )，则下列序列中，是合法输出序列的是( )。 A) 5,1,2,3,4 B) 4,5,1,3,2 C) 4,3,1,2,5 D) 3,2,1,5,4

5．在图采用邻接表存储时，求最小生成树的 prim 算法的时间复杂度为( )。 A) O(n) B) O(n+e) 6．下列排序中，( )是堆。

C) O(n2)

D) O(n3)

A) (100,80,55,60,50,40,58,35,20) B) (100,80,55,60,50,40,35,58,20) C) (100,80,55,58,50,40,60,35,20) D) (100,70,55,60,50,40,58,35,20)

7．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F中第一棵树的结点个数是( )。

A) m﹣n B) m﹣n﹣1 C) n+1 D) 条件不足，无法确定 8．采用简单选择排序，比较次数与移动次数分别为( )。 A) O(n)，O(log2n) B) O(log2n)，O(n2) C) O(n2)，O(n) D) O(nlog2n)，O(n)

9．广义表L=((((a))),((b)),(c),d)，利用head和 tail运算把原子项c从L中分离出来的表达式为( )。

A) head(tail (head (tail(L)))) B) head(head(tail(tail(L))))

·6· 数据结构简明教程（C语言描述）

C) tail (head(head (tail(L)))) D) tail (tail (head (head (L))))

10．设有一个按元素值排好序的线性表且长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较次数分别是s和b，在查找不成功的情况下，正确的s和b的数量关系是( )。

A) 总有 s=b B) 总有s>b C) 总有 s

二、填空题(20分)

l．已知完全二叉树有30个结点，则整个二叉树有___________个度为0的结点。

2．有数据WG={7,19,2,6,32,3,21,10}，则所建Huffman树的树高是___________，带权路径长度WPL为___________。

3．设有三对角矩阵如下图

将带状区中的元素ai,j(︱i﹣j︱≤1)放在一维数组B中，则B的大小为___________ ，元素ai,j在B中的位置是___________(下标从0开始)。

4．设关键字输入序列为(13,24,37,90,53)，则生成的平衡二叉树的根为___________，左子树中的数据是___________，右子树中的数据是___________。

5．下面程序段中带下划线的语句的执行次数的数量级是___________。

i=1;

while(i

6．无向图G=(V,E)，其中V(G)={1,2,3,4,5,6,7}，E(G)={(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(6,7),(5,1)}，对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G'=(V,E')，V(G')=V(G)，E(G')={(1,3),(3,6),(7,3),(1,2),(1,5),(2,4)}，则采用的遍历方法是___________。

三、判断题(10分)

1．存在这样的二叉树，对它采用任何次序的遍历，结果相同。( ) 2．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。( ) 3．非空的广义表的表尾只能是一个子表而不可能是一个原子。( ) 4．有向图的邻接表和逆邻接表中的结点的个数可能不等。( ) 5．堆是一个完全二叉树，反之亦然。( )

6．链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( )

7． 在图G的最小生成树中，可能会有某条边的权值超过未选边的权值。( )

8．二叉树中除叶结点外，任一结点x，其左子树根结点的值小于该结点x的值，其右子树根结点的值大于该结点x的值，则此二叉树一定是二叉排序树。( )

9．用二叉链表存储n个结点的二叉树，结点的2n个指针域中有n﹣1个空指针。( )

第3部分 模拟试题及参考答案 ·7·

10．给定一棵树，可以找到唯一的一棵二叉树与之对应。( ) 四、应用题(20分)

1．对下图所示二叉树分别按先序、中序、后序遍历，给出相应的结点序列，同时给二叉树加上后序后继线索。

2．给出下图所示AOE网的中的关键路径。

a3=3

a1=5

a4=6 a2=7

a5=3

a6=4 a9=2 a10=5 a7=4 a8=4

a11=5 a13=2

a12=4

3．对下图所示有向图，列出4种可能的拓扑有序序列。

A C B D F E 4．设一组数据为(1,14,27,29,55,68,10,11,23)，现采用的哈希函数是H(key)=key ，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。

5．已知2-3树如图所示，当插入一个数85后，画出调整后的2-3树。

45 24 30 53 90 3 12 26 37 50 61 70 100 6．对给定文件(28,07,39,10,65,14,61,17,50,21)，选择第一个元素28进行划分，写出其快速排序第一趟的排序过程。

五、算法设计题(30分)

1．请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针(10分)。

·8· 数据结构简明教程（C语言描述）

2．一个无向连通图的存储结构以邻接表的形式给定，删除该图中的一条边(i,j)。叙述思路并编写算法(10分)。

3．线性表(a1，a2，a3，…，an)中元素递增有序，且按顺序存于计算机内(10分)。要求设计一算法完成：

(1) 用最少的时间在表中查找数值为x的元素。

(2) 若找不到将其插入表中并使表中元素仍递增有序。

模拟试题4

一、选择题(20分)

1．在平衡二叉树中插入一个结点后造成了不平衡，最低的不平衡结点为A，并已知A的左孩子的平衡因子为1，则应作( )型调整以使其平衡。

A) LL B) LR C) RL D) RR 2．线性表( a1，a2，···，an)以链式方式存储时，访问第k个元素的时间复杂度为( )。 A) O(k) B) O(1) C) O(n) D) O(k﹣1) 3．以下数据结构中，是非线性数据结构( )。 A) 树 B) 字符串 C) 队 D) 栈 4．算术表达式A+B*(C+D/E)转为后缀表达式为( )。

A) AB+CDE/* B) ABCDE/+*+ C) ABCDE/*++ D) ABCDE*/++

5．循环队列存储在数组A[0..m]中，则入队时的队尾指针的操作为( )。 A) rear=rear+1 B) rear=(rear+1)%(m﹣1)

C) rear=(rear+1)% m D) rear=(rear+1)%(m+1)

6．下列排序方法中，( )不能保证每趟排序至少能将一个元素放到其最终位置上。 A) 快速排序 B) SHELL排序 C) 堆排序 D) 冒泡排序

7．一个栈的输入序列为1234..N，若输出序列的第一个元素是N，则输出序列的第i(1≤i≤N)个元素是( )。

A) 不确定 B) N﹣i+1 C) i D) N﹣i

8．将二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为( )。

A) 4 B) 5 C) 6 D) 7 9．下面关于求关键路径的说法不正确的是( )。

A) 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 B) 一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同 C) 求关键路径是以拓扑排序为基础的 D) 关键活动一定位于关键路径上

10．在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是( )。 A) G中有弧

B) G中有一条从vi到vj的路径 C) G中没有弧

D) G中有一条从vj到vi的路径

第3部分 模拟试题及参考答案 ·9·

二、填空题(20分)

1．如果含n个顶点的图形成一个环，则它有___________棵生成树。 2．空格串是指______________________，其长度等于_____________。 3．广义表(a,(a,b),d,e,((i,j),k))的长度是___________，深度是___________。

4．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入表中，至少要进行___________次探测。

5．设栈Ｓ和队列Ｑ初始均为空，若6个元素入栈的顺序为(a1,a2,a3,a4,a5,a6)。一个元素出栈之后立即入队列Ｑ，若6个元素出队的顺序为(a2,a4,a3,a6,a5,a1)，则栈的容量至少为___________。

6．设无向连通图G的顶点数与边数和一立方体相同，即有8个顶点和12条边。任意一棵G的生成树共有___________条边。

7．对于具有144个记录的文件，若采用全顺序分块查找，每块长度为___________，则平均查找长度最小。

8．二叉树的先序序列和中序序列相同的条件是______________________。

三、应用题(30分)

1．试从空树开始，依次将(20,30,50,52,60,68,70)插入到3阶B-树中，画出最后的B-树。 2．已知关键字序列为(9,4,3,8,10,7,6,5)。 (1) 画出构造的初始小根堆。

(2) 画出步长为3的一趟希尔排序结果。

3．已知字符序列(A,B,C,D,E,F,G)的权值分别为(3,12,7,4,2,8,11)，试写出其对应哈夫曼树HT的存储结构的初态和终态。

4．试对下列给出的有向图回答问题。

(1) 判断该有向图是否含有强连通分量，若有，请将它们画出来。 (2) 试给出顶点C到其他各顶点的最短路径。

5．设哈希表a和b分别用向量a[0..9]和b[0..9]表示 ，哈希函数均为H(key)=key%7，处理冲突使用开放定址法，Hi=[H(key)+Di]% 10，在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法，试将关键字(19,24,10,17,15,38,18,40)分别填入哈希表a和b中，并分别计算出它们的平均查找长度ASL。

6．试画出以下森林对应的二叉树及其中序线索。

A C B E D G H I

F 四、算法设计题(30分)

1．在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计一个算法，去掉数值相同的元素，使表中不再有重复的元素。

·10· 数据结构简明教程（C语言描述）

例如：(7,10,10,21,30,42,42,42,51,70)将变作(7,10,21,30,42,51,70)。

2． 设计一个算法，输出给定哈夫曼编码。例如，输入的哈夫曼树如下： 6 7 2 3 4 5

算法的输出结果如下：

6：00 2：010 3：011 7：10 4：110 5：111

3．设有向图用邻接表表示，图有n个顶点，表示为1至n。设计一个算法，求顶点k的入度(1＜k＜n)。

模拟试题5

一、选择题(20分)

1．设栈S和队列Q的初始状态为空，元素(e1,e2,e3,e4,e5,e6)依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是(e2,e4,e3,e6,e5,e1)，则栈s的容量至少应该是( )。

A) 6 B) 4 C) 3 D) 2

2．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。 A) 直接插入 B) 二分法插入 C) 快速排序 D) 归并排序

3．设树T的度为4，其中度为1、2、3和4的结点个数分别为4、2、1和1，则T中的叶子数为( )。

A) 5 B) 6 C) 7 D) 8

4．有数据(53,30,37,12,45,24,96)，从空二叉树开始逐个插入数据形成二叉排序树，若希望高度最小，则应选择下面( )序列输入。

A) 37,24,12,30,53,45,96 B) 45,24,53,12,37,96,30 C) l2,24,30,37,45,53,96 D) 30,24,12,37,45,96,53

5．有关二叉树下列说法正确的是( )。 A) 一棵二叉树的度可以小于2 B) 二叉树的度为2

C) 二叉树中至少有一个结点的度为2 D) 二叉树中任何一个结点的度都为2

6．设有一个按元素值排好序的线性表且长度大于2，对给定的值k，分别用顺序查找法和二分查找

第3部分 模拟试题及参考答案 ·11·

法查找一个与k相等的元素，比较次数分别是s和b，在查找不成功的情况下，正确的s和b的数量关系是( )。

A) 总有 s＝b B) 总有s＞b C) 总有 s＜b D) 与k值大小有关 7．链表不具有的特点是( )。 A) 插入删除不需要移动元素 B) 可随机访问任意元素 C) 不必要先估计存储空间 D) 所需空间与线性长度成正比

8．一组记录的关键码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

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)

9．下面关于哈希(HASH)查找的说法正确的是( ) 。

A) 哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B) 不存在特别好与坏的哈希函数，要视情况而定 C) 除留余数法是所有哈希函数中最好的

D) 若在哈希表中删除一个元素，不管用何种方法解决冲突都只要简单地将元素删去即可 10．下列关于AOE网的叙述中，不正确的是( )。 A) 关键活动不按期完成就会影响整个工程的完成时间

B) 任何一个关键活动提前完成，那么整个工程将会提前完成 C) 所有的关键活动提前完成，那么整个工程将会提前完成 D) 某些关键活动提前完成，那么整个工程将会提前完成 二、填空题(20分)

1．在二叉树中，指针p所指结点为叶子结点的条件是_____________。

2．已知一无向图G =(V,E)，其中V={a,b,c,d,e} E={(a,b),(a,d),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abedc，则采用的是_____________遍历方法

3． 设G为具有N个顶点的无向连通图，则G中至少有____________条边。

4．设有N个结点的完全二叉树顺序存放在向量A[1..N]中，其下标值最大的分支结点为____________。

5． 设循环队列存放在向量sq.data[0..M-1]中，则队头指针sq.front在循环意义下的出队列操作可表示为____________，若用牺牲一个单元的办法来区分队满和队空(设队尾指针为sq.rear)， 则队满的条件为____________。

6．在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素的下标从小到大依次是____________。

7．当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 (1) 查邻接表中入度为____________的顶点，并进栈。 (2) 若栈不空，则

① 输出栈顶元素vj，并退栈；

② 查vj的直接后继vk，对vk入度处理，处理方法是____________

(3) 若栈空时，输出顶点数小于图的顶点数，说明有__________，否则拓扑排序完成。

三、应用题(30分)

1．已知一棵二叉树的中序(或中根)遍历结点排列为DGBAECHIF，后序(或后根)遍历结点排列为

·12· 数据结构简明教程（C语言描述）

GDBEIHFCA。

(1) 试画出该二叉树。

(2) 试画出与(1)中二叉树对应的森林。

2．下图所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。请画出调整后的AVL树。

100 60 40 80 120 70

3．已知有向图如下所示。

(1) 给出其邻接表表示和逆邻接表表示。

(2) 判断该有向图是否含有强连通分量，若有，请将它们画出来。

4．假设用于通讯的电文仅有6个字母(A,B,C,D,E,F)组成，字母在电文中出现的频率分别为(7,19,5,16,42,11)。试为这6个字母设计哈夫曼编码。

5．计算下列AOE网中各顶点所表示的事件的发生时间ve(j)、vl(j)和各边所表示活动的开始时间e(i)和l(i)，并找出其关键路径。

其中：

a1=2 a6=4 a2=3 a7=6 a3=3 a8=2 a4=5 a9=3 a5=9

6．判断以下序列是否为堆，如果不是，则把它调整为堆。 (1) (12,24,33,65,33,56,48,92,86,70)

(2) (25,56,20,23,40,38,29,61,35,76,28,100) 四、算法设计题(30分)

1．假设二叉树采用二叉链表存储结构，设计一个算法，求二叉树中指定结点x的层数。

2．设有两个栈S1和S2均采用顺序栈方式，并且共享一个存储区[0..M﹣1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。试设计算法，实现S1和S2的入栈和出栈运算。

3．设图用邻接矩阵表示，写出求从指定顶点到其与各顶点的最短路径的迪杰斯特拉算法。

第3部分 模拟试题及参考答案 ·13·

模拟试题1参考答案

一、选择题(20分) 1~5 6~10

A D

B D

C C

A B

C B

二、填空题(20分)

l．(n﹣2)(n+3)/2 2．n0=n2+1 3．3 4．n1﹣1 5．50 6．直接插入排序和冒泡排序 三、判断题(10分) 1．× 6．√

2．× 7．√

3．√ 4．√ 5．× 8． × 9．× 10．√

1

n2+n3 4

4

四、应用题(20分) 1．参考答案：

0 1 2 3 4

5 6 7

8 9 10

30 53 ^ 41 ^ 13 46 ^ 22 ^ 01 67 ^

2．参考答案：

·14· 数据结构简明教程（C语言描述）

3．参考答案：

4．参考答案： (1)

(2) 带权路径长度269

5．参考答案： (1) ABCDEG (2) ABCEDG

6．参考答案：

01 14 21 19 66 23 83 27 56

A B C D E F G

100 40 60 20 20 30 30 8 12 12 18 5 7 3 4

第3部分 模拟试题及参考答案 ·15·

五、算法设计题(30分) 1．算法代码：

int flag=1; int max;

void sortBiTree(BiTree T){ if(T) {

sortBiTree(T->lchild); k++; if(k==1)

max=T->data; else{

if(T->data>max) max=T->data; else flag=0; }

sortBiTree(T->rchild); } }

2．算法代码：

int pathed[MAX_VERTEX_NUM]; int top=0;

int path[MAX_VERTEX_NUM];

int ispath(ALGraph graph,int vi,int vj){ ArcPtr p; int j;

pathed[vi]=1; path[++top]=vi;/*将顶点vi加入当前路径path */ if(path[top]==vj) /*存在顶点vi到顶点vj的路径*/ return 1;

else /*将顶点vi的邻接点加入当前路径*/ for(p=graph.vertices[vi].firstarc;p;p=p->nextarc) if(!pathed[p->adjvex]) return ispath(graph,p->adjvex,vj); pathed[vi]=0; top--; /*将顶点vi从当前路径path中删除 */ if(top==0) return 0; /*不存在vi到vj的简单路径*/ }

3．算法代码：

BiThrTree insucc(BiThrTree p){/*找p结点的后继*/ if(p->rtag==1) /*后继线索*/ return p->rchild;

else {/*右子树的最左下结点*/ p=p->rchild; while(p->ltag==0) p=p->lchild; return p; } }

·16· 数据结构简明教程（C语言描述）

模拟试题2参考答案

一、选择题(20分) 1~5 6~10

D C

C D

B B

C C

A A

二、填空题(20分)

1． 顺序存储结构 链式存储结构 2． n(n﹣1)/2 n(n﹣1) 3． 前驱结点的指针值 4． A[i/2] A[2i]

5． 在查找不成功时，静态查找只宣布查找失败，而动态查找还需要将所查找的元素插入到查找表中 6．2k﹣1 2k﹣1 三、判断题(10分) 1．√ 6．√

2．√ 7．×

3．×

8．√

4．× 9．×

5．×

10．√

四、应用题(20分) 1．参考答案：

0 1 2 3 4 5 6 7 8 9 10

22 01 46 13 67 41 53 30

2．参考答案：

森林的先序序列：1,2,3,4,5,6,7,8,9,10 森林的中序序列：2,3,4,1,6,5,8,10,9,7

1 2 6 5 3 7 4 8 9 10

3．参考答案：

第3部分 模拟试题及参考答案 ·17·

4．参考答案：

66 27 30 27 30 27 12 27 12 27 12 27

5．参考答案：

6．参考答案： (1) 邻接矩阵：

70 12 100 30 92 35 85 66 92 35 70 12 85 50 35 12 50 66 92 70 85 30 92 50 70 35 66 85 35 30 50 66 92 70 85 30 35 50 66 70 85 92

19 14 23 01 21 66 27 83 56 0 2 3 0 0 0 0 0 3 0 0 1 0 0 0 0 0 2 1 0 2 4 0 0 0 0 0 2 0 1 2 0 0 0 0 4 1 0 0 4 0 0 0 0 2 0 0 3 0 0 0 0 0 4 3 0

50

100 100 100

100 100

·18· 数据结构简明教程（C语言描述）

(2) 最小生成树：

五、算法设计题(30分) 1．算法代码：

int search_bin(SSTable ST,int low,int high,int key){ /*对有序表ST折半查找的递归算法*/ int mid;

if (low<=high){

mid=(low+high)/2;

if(key==ST.elem[mid].key) return(mid);

else if(key

return (search_bin(ST,low,mid-1,key)); else

return (search_bin(ST,mid+1,high,key));} else return -1; /*查找失败*/ }

2．算法代码：

void inorder_thr(BiThrTree T){ BiThrTree p; while(p){

while(p->ltag==0) p=p->lchild;

printf(\访问其左子树为空的结点*/ while(p->rtag==1&&p->rchild!=NULL){ p=p->rchild;

printf(\ }

p= p->rchild; } }

3．算法代码：

int count=0;

void is_connected(ALGraph G){ int i;

for (i=1;i<=G.vexnum;i++) /*标识数组置0*/ visited[i]=0;

for (i=1;i<=G.vexnum;i++) if(!visited[i]){

DFS(G,i); /*从顶点vi出发深度优先遍历vi所在的连通分量*/ count++; } }

第3部分 模拟试题及参考答案 ·19·

模拟试题3参考答案

一、选择题(20分) 1~5 6~10

A B

C A

B C

D B

C D

二、填空题(20分) l．15 2．6 261 3．3n﹣2 2i+j﹣3 4．24 13 5．对数阶(O(log2N)) 6．广度优先遍历 三、判断题(10分) 1．√ 6．√

2．× 7．√

3．√ 8． ×

4．×

9．×

5．×

10．√

53

四、应用题(20分)

1．参考答案：

先序遍历序列：HDACBGFE 中序遍历序列：ADCBFEGH 后序遍历序列：ABCDEFGH

2．参考答案：

a4=6

a2=7

a6=4 a9=2 a10=5

a11=5 a13=2

3．参考答案： (1) ABCDEF (2) ABCEDF (3) ABEFCD

·20· 数据结构简明教程（C语言描述）

(4) ACDBEF

4．参考答案：

0 1 2 3 4 5 6 7 8 9 10 11 12

11 ^ 10 23 ^ 29 55 68 ^ 01 14 27 ^ 5．参考答案：

45 70 24 30 53 90 3 12 26 37 50 61 85 100

6．参考答案：

初始序列：28,07,39,10,65,14,61,17,50,21 21前移 ： 21,07,39,10,65,14,61,17,50,[ ] 39后移 ： 21,07,[ ],10,65,14,61,17,50,39 17前移 ： 21,07,17,10,65,14,61,[ ],50,39 65后移 ： 21,07,17,10,[ ],14,61,65,50,39 14前移 ： 21,07,17,10,14,[ ],61,65,50,39

排序结果：{21,07,17,10,14} 28 {61,65,50,39} 五．算法设计题(30分) 1．算法代码：

BiTree head,tail;

void leaf_link(BiTree T ){/*编写函数将二叉树的所有叶子结点从左到右链成一个单链表head*/

第3部分 模拟试题及参考答案 ·21·

if(T){

leaf_link(T->lchild);

if(!T->lchild && !T->rchild){

if(head==NULL){head=T;tail=T;} else {tail->rchild=T;tail=T;} }

leaf_link(T->rchild); } }

2．算法代码：

int delete(ALGraph graph,int i,int j){ ArcPtr q, p;

/*删除顶点vi的邻接点链表中的表结点j*/ p=graph.vertices[i].firstarc;

while(p!=NULL&&p->adjvex!=j) {q=p; p=p->nextarc;} if(p->adjvex==j)

q->netarc=p->nextarc;

/*删除顶点vj的邻接点链表中的表结点i*/ p=graph.vertices[j].firstarc;

while(p!=NULL&&p->adjvex!=i) {q=p; p=p->nextarc;} if(p->adjvex==i)

q->netarc=p->nextarc; }

3．算法代码：

void binsert_sort(SSTable st , int x){/*对有序表st进行折半查找*/ int i,j,low,high,mid;

if(x== st.elem[1].key||x== st.elem[st.length].key) return; else{

st.elem[0].key=x; low=1;

high= st.length;

while(low<=high) {/*折半查找插入位置low*/

mid=(low+high)/2; if(st.elem[0].key==st.elem[mid].key) return; else if(st.elem[0].key

for(j= st.length;j>=low;j--) st.elem[j+1] =st.elem[j];/*后移元素*/ st.elem[low]=st.elem[0]; st.length++; } }

模拟试题4参考答案

一、选择题(20分) 1~5 6~10

A B

C B

A C

B A

D D

·22· 数据结构简明教程（C语言描述）

二、填空题(20分)

1．n

2．只由空格字符组成的字符串 空格字符的个数 3．5 4．k(k+1)/2 5．3 6．7 7．12

8．二叉树无左子树 三、应用题(30分) 1．参考答案：

2．参考答案： (1)

(2) 参考答案： 9 4 3 6 4 3 6 4 3 3．参考答案：

HT的初态 HT3 0 0 0 12 0 0 0

7 0 0 0 4 0 0 0 2 0 0 0 8 0 0 0

3

52 30 68 20 50 60 70 3 4 6 5 10 7 9 8 8 10 7 6 5 8 9 5 10 7 8 5 7

9

10

的终态 3 8 0 0 12 12 0 0 7 10 0 0 4 9 0 0 2 8 0 0 8 10 0 0 第3部分 模拟试题及参考答案 ·23·

11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

11 5 9 15 20 27 47 11 0 9 5 11 4 12 3 13 9 13 2 0 0 1 8 6 7 10 11 12

4．参考答案： (1)

(2)

始点 C C C C C 终点 A B D E F

最短路径 无 无 C,D C,D,F,E C,D,F 长度 ∞ ∞ 3 11 8

5．参考答案：

(1) 哈希表a及其生成过程：

19：5 24：3 10：3，4

17：3，4，5，6 15：1

38：3，4，5，6，7 18：4，5，6，7，8 40：5，6，7，8，9

ASL=(1+1+2+4+1+5+5+5)/8=24/8=3

0 1 2 3 4 5 6 7 8 9 15 24 10 19 17 38 18 40

(2) 哈希表b及其生成过程：

19：5 24：3 10：3，4 17：3，4，2

·24· 数据结构简明教程（C语言描述）

15：1

38：3，4，2，7 18：4，5，3，8 40：5，6，4，9

ASL=(1+1+2+3+1+4+4+4)/8=20/8=2.5

0 1 2 3 4 5 6 7 8 9 15 17 24 10 19 38 18 40

6．参考答案：

A B D G

E C F

四．算法设计题(30分) 1．算法代码：

void delete(LinkList h){ LinkList q, p; p=h->next;

while(p!=NULL){ q=p;

p=p->next;

while(p->data==q->data) { q->next=p->next; free(p); p=q->next; } } }

2．算法代码：

void huffmancode(HTNode *ht, int m, char *hc[], int n){ int i,start,c,p; char cd[m]; cd[m-1]='\\0';

for(i=0;i

if(ht[p].lchild==c) cd[--start]='0'; else cd[--start]='1'; c=p;

p=ht[p].parent; }

strcpy(hc[i],&cd[start]);

第3部分 模拟试题及参考答案 ·25·

} }

3．算法代码：

int idk(ALGraph graph, int k){ ArcPtr p;

int count=0, i;

/*求邻接表中顶点k的入度*/ for (i=1;i<=graph.vexnum;++i){ p=graph.vertices[i].firstarc; while(p!=NULL) {

if(p->adjvex==k) count++; p=p->nextarc; } } }

模拟试题5参考答案

一、选择题(20分) 1~5 6~10

C D

C B

D C

A B

A B

二、填空题(20分) 1．结点*p的左右链域为空 2．深度优先 3．N﹣1 4．A[N/2]

5．sq.front=(sq.fron+1)%M 6．4，9，14，17，20 7．0 入度减1 三、应用题(30分) 1．参考答案： (1) 二叉树

A (sq.rear+1)%M = = sq.front

环

B C D E F G H I (2) 对应的森林

·26· 数据结构简明教程（C语言描述）

A C B E H I

F

2．参考答案：

80 60 100 40 70 120

3．参考答案：

(1) G1的邻接表和G1的逆邻接表

V1 V2 ^ V3 V4 4 ^ 1 ^ 2 3 ^

V1 V2 V3 V4 4 ^ 1 ^ 1 ^ 3 ^

(2) G1的强连通分量

4．参考答案：

(1) 以所有字符的权值作为叶结点构成的哈夫曼树如下：

第3部分 模拟试题及参考答案 ·27·

42 16 19 11

(2) 所有字符的哈夫曼编码如下： A(7)： 0011 B(19)： 011 C(5)： 0010 D(16)： 010 E(42)： 01 F(11)： 000 5．参考答案：

vi v1 v2 v3 v4 v5 v6 5 7 事件的发生时间 活动的发生时间 ve 0 6 3 12 18 21 vl 0 7 3 12 18 21 ai a1 a2 a3 a4 a5 a6 a7 a8 a9 e 0 0 3 6 3 3 12 12 18 l 5 0 4 7 3 14 12 19 18 l-e 5 0 1 1 0 11 0 7 0 6．参考答案：

(1) 该序列是一个小根堆。

(2) 该序列不是一个小根堆，调整如下：

20 25 23 35 28 38 29 61 56 76 40 100 ·28· 数据结构简明教程（C语言描述）

四．算法设计题(30分) 1．算法代码：

void fun(BiTree T, char x, int m){ if(T){ m++;

if(T->data==x) {printf(\ fun (T->lchild,x,m); fun (T->rchild,x,m); } }

main(){

BiTree bt; int m=0; fun(bt,m); }

2．算法代码：

#define MAXSIZE 100 typedef int ElemType; typedef struct{

ElemType elem[MAXSIZE]; int top[2]; }DuStack; DuStack s;

int push(int i,int x) /*入栈操作*/ {

if(i<0||i>1) { printf(\输入数据有误\ if(s.top[1]-s.top[0]==1) {printf(\栈满\ switch(i) {

case 0: s.elem[++s.top[0]]=x; break;

case 1: s.elem[--s.top[1]]=x; }

return 1; }

int pop(int i, int *x) /*出栈操作*/ {

if(i<0||i>1) { printf(\输入数据有误\ switch(i) {

case 0:

if(s.top[0]==-1) {printf(\栈空\ else *x=s.elem[s.top[0]--]; break; case 1:

if(s.top[0]==MAXSIZE) {printf(\栈空\ else *x=s.elem[s.top[1]++]; }

return 1;

第3部分 模拟试题及参考答案 ·29·

}

3．算法代码：

void dijkshort(MGraph G,int v){ int s[30]; int d[30]; int pre[30]; int i,j,k,p,min;

for(i=1;i<=G.vexnum;i++){ d[i]=G.arcs[v][i]; s[i]=0;

if(d[i]<32767) pre[i]=v; else pre[i]=0; }

s[v]=1;

for(i=1;i<=G.vexnum;i++){ min=32767; k=0;

for(j=1;j<=G.vexnum;j++)

if(!s[j]&&d[j]

s[k]=1; /*将找到的顶点加入到第一组中*/

for(j=1;j<=G.vexnum;j++) /*修改第二组中顶点的距离值*/ if(!s[j]&&d[j]>d[k]+G.arcs[k][j]) { d[j]=d[k]+G.arcs[k][j]; pre[j]=k; } }

for(j=1;j<=G.vexnum;j++) /*输出结果*/ if(pre[j]){

printf(\ while(p){

printf(\ p=pre[p]; }

printf(\ } else

if(j!=v) printf(\}