返回信息流测试二
一． 单项选择题（2分/题）
1． 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（）。
A.23415 B.54132 C.31245 D.14253
2． 设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（）。
A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n
3． 二叉树在线索化后，仍不能有效求解的问题是（）。
A.先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继
4． 求最短路径的FLOYD算法的时间复杂度为（）。
A.O(n) B.O(n+e) C.O(n2) D.O(n3)
5． 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。
A.0 B.1 C.2 D.不确定
6． 数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（）。
A.1140 B.1145 C.1120 D.1125
7． 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（）。
A.快速排序 B.希尔排序 C.冒泡排序 D.堆排序
8． 对有18个元素的有序表做折半查找，则查找A[3]的比较序列的下标依次为（）。
A.1-2-3 B.9-5-2-3 C.9-5-3 D. 9-4-2-3
9． 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）。
A.堆排序 B.冒泡排序 C.快速排序 D.直接插入排序
10． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（）型调整以使其平衡。
A.LL B.LR C.RL D.RR
二． 判断题（1分/题）
1.（）线性表的长度是线性表所占用的存储空间的大小。
2.（）双循环链表中，任意一结点的后继指针均指向其逻辑后继。
3.（）在对链队列做出队操作时，不会改变front指针的值。
4.（）如果两个串含有相同的字符，则说它们相等。
5.（）如果二叉树中某结点的度为1，则说该结点只有一棵子树。
6.（）已知一棵树的先序序列和后序序列，一定能构造出该树。
7.（）图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。
8.（）图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。
9.（）对一个堆按层次遍历，不一定能得到一个有序序列。
10.（）直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。
三． 填空题（2分/空）
1．已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。
2．将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7,5]的地址是（1100）。
3．有n个顶点的强连通有向图G至少有（n）条弧。
4．有n个结点并且其高度为n的二叉树的数目是（2n-1）。
5．高度为8的平衡二叉树的结点数至少是（54）。
6．3个结点可构成（2）棵不同形态的树。
7．对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上适当的内容，以说明该算法的执行过程。
顶点 1 3 4 U V
(U,V) (2,1) (2,3) (2,4) {2} {1,3,4}
代价  4 2
(U,V) (4,1) (2,3) {2,4} {1,3}
代价 5 4
(U,V) (3,1) {2,4,3} {1}
代价 1
(U,V) {2,4,3,1} {}
代价
8．设散列表函数为H(key)，用拉链法解决冲突，H的值域为0,...,n-1，构造的散列表类型如下：
TYPE link=^node;
node=RECORD
key:keytype;
next:link;
...
END;
openhash=array[0..n-1] of link;
请在下列算法划线处填上适当内容，以完成查找键值等于K的结点，若查找成功，返回该结点的指针，否则返回空指针。
FUNC research(K:keytype; HP:openhash):link;
i:=H(K); SUC:=false;
p:=HP[i] ;
while (p<>nil) and not(SUC) do
if p^.key<>K then p:=p^.next
else SUC:=true;
return(p)
ENDC; {researsh}
四． 应用题（5分/题）
1． 对下面两棵二叉树，分别画出它们的顺序存储结构。
A A
B C B C
D E F G D E F
I J K I J
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11
A B C D E F G I J K A B C D E F I J
2． 设图G=(V,E),V={1,2,3,4,5,6}, E={<1,2>,<1,3>,<2,5>,<3,6>,<6,5>,<5,4>,<6,4>}。请写出图G中顶点的所有拓扑序列。
1---2---3---6---5---4
3---2---6---5---4
6---2---5---4
3． 对下面3阶B-树依次执行下列操作，画出每步的操作结果。
（1） 插入300
（2） 插入70
（3） 插入30
（4） 删除150
（1）
（2）
（3）
（4）
4． 求出下面AOE网中的关键路径，要求标明每个顶点的最早和最迟发生时间，并画出关键路径。
1 2 3 4 5 6 7 8 9 10
e 0 4 5 4 10 11 13 14 13 18
l 0 8 5 4 12 11 15 16 13 18
五． 算法设计题（10分/题）
1． 设计算法将一个带头结点的单循环链表A分解为两个具有相同结构的链表B和C，其中B表中结点为A表中值为奇数的结点，而C表中结点为A表中值为偶数的结点（要求利用原表结点）。
算法思想：B表头结点利用A表头结点；为C表产生一个头结点。从A的首元结点检查每个结点应插入B表还是C表，从而从A表取下，做响应的插入操作。
2． 设计算法判断无向图G是否是连通的，若连通则返回true，否则返回false。
可以使用以下几个函数调用：
firstadj(G,v)—返回图G中顶点v的第一个邻接点，若不存在返回0
nextadj(G,v,w)—返回图G中顶点v的邻接点中处于w之后的邻接点，若不存在返回0
nodes(G)—返回图G中的顶点数
算法思想：从某个顶点出发深度/广度遍历。
3． 已知数组A[1..n]的元素递增有序，试设计算法以数组A中的元素构造一棵二叉排序树，并使其满足平衡二叉树的条件。
算法思想：递归算法，以居中的元素作为根结点。
这是一条镜像帖。来源：北邮人论坛 / scs / #924同步于 2026/5/10
该镜像源已超过 30 天没有更新，可能在源站已被删除。
SCS机器人发帖
数据结构考题
reliance
2026/5/10镜像同步40 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
测试三
一． 单项选择题（2分/题）
1． 一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数为（）。
A.0 B.1 C.2 D.不确定
2． 设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（）。
A.O(n) B.O(n+e) C.O(n2) D.O(n*e)
3． 下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（）。
A.堆排序 B.冒泡排序 C.快速排序 D.SHELL排序
4． 已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最节省时间。
A.堆排序 B.插入排序 C.快速排序 D.直接选择排序
5． 串是（）。
A.不少于一个字母的序列 B. 任意个字母的序列
C.不少于一个字符的序列 D.有限个字符的序列
二． 判断题（1分/题）
1.（）若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai =n-i+1。(i=1,2,...,n)
2.（）二叉树中的叶子结点就是二叉树中没有左右子树的结点。
3.（）一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。
4.（）删除二叉排序树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。
5.（）线性表就是顺序表。
6.（）若一棵树中某结点的度为1，则该结点仅有一棵子树。
7.（）所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。
8.（）AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。
9.（）若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。
10.（）在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。
11.（）对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在非叶结点的最下层。
12.（）若一个连通无向图的以顶点1为起点的深度遍历序列唯一，则可唯一确定该图。
13.（）若一个有向图的以顶点1为起点的深度遍历序列唯一，则可唯一确定该图。
14.（）在数据表基本有序时，冒泡排序算法的时间复杂度一定接近O(n)。
15.（）设指针p指向单链表中的一个结点，则语句序列u:=p^.next; u:=u^.next将删除一个结点。
三． 填空题（2分/题）
1．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数是（129）。
2．已知栈的输入序列为1,2,3,...,n，输出序列为a1, a2, a3,..., an，符合a2=n的输出序列共有（n-1）种。
3．已知数组A[1..10,1..10]为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续内存单元中，则元素A[5，6]对应的地址为（1095）。
4．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（log2i=log2j）。
5．在按关键字递增的数组A[1..20]中，按折半查找方法进行查找时，查找长度为5的元素个数是（5）。
四． 应用题（5分/题）
1． 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。
先序序列： B F ICEH G；
中序序列：D KFIA EJC ；
后序序列： K FBHJ G A
先序序列：ABDFKICEHJG；
中序序列：DBKFIAHEJCG；
后序序列：DKIFBHJEGCA
A
B C
D F E G
K I H J
2． 已知哈希表地址空间为0..14，哈希函数为H(k)=k mod 13，采用线性探测法处理冲突。将下面各数依次存入该散列表中，并求出在等概率下的平均查找长度和失败的查找长度。
240,29,345,189,100,20,21,35,3,208,78,99,45,350
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
208 78 350 29 3 240 345 189 100 20 21 35 99 45
0 0 12 3 3 6 7 7 9 7 8 9 8 6
ASLs=43/14 ASLf=105/13
3． 对下面的递归算法，写出调用p(4)的执行结果。
PROC p(w:integer);
if w>0 then
[ write(w);
p(w-1);
p(w-1)
]
ENDP; {p}
4 3 2 1 1 2 1 1 3 2 1 1 2 1 1
4． 一棵排序二叉树结构如下，各结点的值从小到大依次为1~8，请标出各结点的值。
5． 求出下图中顶点1到其余各顶点的最短路径。
五． 算法设计题（10分/题）
1． 已知T为一棵二叉排序树。
（1） 设计算法按递减次序打印各结点的值。
（2） 设计算法以产生一个序列，要求该序列满足：依次将这些元素插入到初值为空的二叉排序树中所得的结果与原二叉排序树相同。
算法思想：（1）按“右根左”遍历
（2）先序遍历
2． 已知一棵二叉树按顺序方式存储在数组A[1..n]中，设计算法求出下标分别为i和j的两个结点的最近公共祖先结点。
算法思想：沿i、j分别上溯查找公共结点。
3． 已知数组A[1..n]的元素类型为整型，设计算法将其调整为左右两部分，使得左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)。
算法思想：利用快速排序的思想。
4． 设计算法判断有向图G是否是一棵以v为根的有向树。
可以使用以下几个函数调用：
firstadj(G,v)—返回图G中顶点v的第一个邻接点，若不存在返回0
nextadj(G,v,w)—返回图G中顶点v的邻接点中处于w之后的邻接点，若不存在返回0
nodes(G)—返回图G中的顶点数
算法思想：从v出发深度优先搜索，若可遍历到图中所有顶点且遍历过的顶点不会再次访问则是；否则不是。
测试一
一． 单项选择题（2分/题）
1． 在线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A.单链表 B.仅有头指针的单循环链表
C.双链表 D.仅有尾指针的单循环链表
2． 链表不具有的特点是（）。
A.可随机访问任一元素 B.插入、删除不需要移动元素
C.不必事先估计存储空间 D.所需空间与线性表长度成正比
3． 对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）次序的遍历实现编号。
A.先序 B.中序 C.后序 D.从根开始的层次遍历
4． 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
A.空或只有一个结点 B.高度等于其结点数
C.任一结点无左孩子 D.任一结点无右孩子
5． 下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlog2n)的是（）。
A.堆排序 B.冒泡排序 C.直接选择排序 D.快速排序
6． 任何一个无向连通图的最小生成树（）。
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在
7． 下列序列中，（）是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。
A.[da,ax,eb,de,bb] ff [ha,gc] B.[cd,eb,ax,da] ff [ha,gc,bb]
C.[gc,ax,eb,cd,bb] ff [da,ha] D.[ax,bb,cd,da] ff [eb,gc,ha]
8． 用n个键值构造一棵二叉排序树，最低高度为（）。
A.n/2 B.n C.log2n D. log2n+1
9． 折半查找法要求查找表中各元素的键值必须是（）排列。
A.递增或递减 B.递增 C.递减 D.无序
10． 对于键值序列{12,13,11,18,60,15,7,18,25,100}，用筛选法建堆，必须从键值为（）的结点开始。
A.100 B.12 C.60 D.15
二． 判断题（1分/题）
1.（）串长度是指串中不同字符的个数。
2.（）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。
3.（）在顺序表中取出第i个元素所花费的时间与i成正比。
4.（）在栈满情况下不能作进栈操作，否则产生“上溢”。
5.（）二路归并排序的核心操作是将两个有序序列归并为一个有序序列。
6.（）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索可访问到该图的每个顶点。
7.（）一个有向图的邻接表和逆邻接表中的结点个数一定相等。
8.（）在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中的块数有关，而且与每一块中的元素个数有关。
9.（）子的值；若它的右子树非空，则根结点的值小于其右孩子二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩的值。
10.（）在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。
三． 填空题（2分/题）
1．在双循环链表L中，指针p所指结点为尾结点的条件是（p^.next=L）。
2．在单链表中，删除指针p所指结点的后继结点的语句是（p^.next:=p^.next^.next）。
3．若某串的长度小于一个常数，则采用（顺序存储）存储方式最节省空间。
4．一棵树T采用二叉链表BT存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定满足（左子树为空）。
5．高度为K的3阶B-树的结点数至少是（2k-1）。
6．有n个球队参加的足球联赛按主客场制进行比赛，共需进行（n(n-1)）场比赛。
7．取出广义表A=(x,(a,b,c,d))中原子b的函数是（Head[Tail[Head[Tail[A]]]]）。
8．对矩阵采用压缩存储是为了（节省空间）。
9．有向图G用邻接矩阵A[1..n,1..n]存储，其第i行的所有元素之和等于顶点i的（出度）。
10． 在顺序文件中，要存取第i个记录，必须先存取（第i-1个记录）。
四． 应用题（5分/题）
1． 已知二叉树的后序和中序序列如下，构造出该二叉树。
后序序列：ABCDEFG 中序序列：ACBGEDF
G
C F
A B E
D
2． 有一组关键码序列{38,19,65,13,97,49,41,95,21,98,73}，采用冒泡排序方法由小到大进行排序，请写出每趟的结果。
19 19 13 13 13 13 13
38 13 19 19 19 19 19
13 38 38 38 38 21 21
65 49 41 41 21 38 38
49 41 49 21 41 41 41
41 65 21 49 49 49 49
95 21 65 65 65 65 65
21 73 73 73 73 73 73
73 95 95 95 95 95 95 97 97
7 97 97 97 97
97
98 98 98 98 98 98 98
3． 对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。{4，5，6，7，10，12，15，18，23}
100
58 42
33 25 23 19
18 15 13 12 10 9
7 6 5 4
带权路径长度WPL=299
4． 图G的邻接表如图，
（1） 画出从顶点5出发进行广度
遍历的生成树。
（2） 判断其中是否存在有向回路，
若不存在，求出其拓扑序列。
（1） 5
9 10 8
11
12
（2） 1 2 4 5 8 9 10 3 7 6 11 12
五．算法设计题（10分/题）
1． 设二叉排序树的根指针为t，每个结点的结构为： Lchild Key Rchild
试写出算法输出二叉排序树中最大的键值。
算法思想：从根结点出发，顺着右孩子方向往下搜索，直到遇到没有右孩子的结点为止——该结点就是值最大的结点。
2． 设一个环上有若干个整数，若采用单循环链表L存储该环，
已知L的结点结构为 data next
试画出链表L的结构图，并编写算法判断环上任意两个相邻元素值之差的绝对值是否不超过2。
算法思想：依次对每两个相邻结点进行判断（共有n组）：若满足条件，则继续余下各组的比较，否则返回false。每组均满足条件，返回ture。
3． 有n个结点的有向图的邻接表定义如下：
type vertex=1..n;
eptr=^enode;
enode=record
num: vertex;
next:eptr
end;
vnode=record
Vinfo:datatype;
firstE:eptr
end;
ajlist=array[vertex] of vnode;
设计算法实现下列要求：
（1） 求出图G中每个顶点的出度
（2） 求出图G中出度最大的一个顶点，输出该顶点号及其信息。
（3） 判断G中是否存在弧<i,j>。
算法思想：顶点v(v=1,2,...,n)的出度即它的邻接表的长度；判断<i,j>是否存在只要检查顶点i的邻接表上是否存在邻接点j。