的比较次数并计算出查找成功时的平均查找长度。4．设一棵树T中边的集合为A，B，A，C，A，D，B，E，C，F，C，G，要求用孩子兄弟表
示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。5．设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。
6．设有一组初始记录关键字为45，80，48，40，22，78，要求构造一棵二叉排序树并给出构造过程。四、算法设计题16分1．设有一组初始记录关键字序列（K1，K2，…，K
），要求设计一个算法能够在O
的时间复杂度内将线
性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。2．设有两个集合A和集合B，要求设计生成集合CA∩B的算法，其中集合A、B和C用链式存储结构表
示。
4
f数据结构试卷（三）
一、选择题每题1分，共20分
1．设某数据结构的二元组形式表示为AD，R，D01，02，03，04，05，06，07，08，09，Rr，
r01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09，则数
据结构A是（）。
A线性结构
B树型结构
C物理结构
D图型结构
2．下面程序的时间复杂为（）
for（i1，s0；i
；i）t1；forj1；ji；jttj；sst；
AO

BO
2
CO
3
DO
4
3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。
Aqp
ext；pdataqdata；p
extq
ext；freeq；
Bqp
ext；qdatapdata；p
extq
ext；freeq；
Cqp
ext；p
extq
ext；freeq；
Dqp
ext；pdataqdata；freeq；
4．设有
个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。
A1
B

C
log2

D
2
5．设一组初始关键字记录关键字为20，15，14，18，21，36，40，10，则以20为基准记录的一趟快速
排序结束后的结果为。
A10，15，14，18，20，36，40，21
B10，15，14，18，20，40，36，21
C10，15，14，20，18，40，36，2l
D15，10，14，18，20，36，40，21
6．设二叉排序树中有
个结点，则在二叉排序树的平均平均查找长度为（）。
AO1
BOlog2

C
DO
2
7．设无向图G中有
个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。
A
，e
Be，

C2
，e
D
，2e
8设某强连通图中有
个顶点，则该强连通图中至少有（）条边。
A
1
B
1
C

D
1
9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列
（）方法可以达到此目的。
Ar