![](https://csdnimg.cn/release/download_crawler_static/88285321/bgc.jpg)
单选题(每小题
2
分,共
8
分)
1
、 在一个长度为
n
的顺序线性表中顺序查找值为
x
的元素时,查找成功时的平 均查
找长度(即
x
与元素的平均比较次数,假定查找每个元素的概率都相等) 为
()
。
An B n/2 C (n+1)/2 D (n-1)/2
2
、 在一个单链表中
,
若
q
所指结点是
p
所指结点的前驱结点
,
若在
q
与
p
之间插入
一个
s
所指的结点
,
则执行
()
。
A s
—
link=p
f
link; p
—
link=s ; B p
—
lin k=s; s
—
lin k=q;
C p
—
lin k=s
—
link; s
—
lin k=p; D q
—
lin k=s; s
—
link =p;
3
、 栈的插入和删除操作在()进行。
A
栈顶
B
栈底
C
任意位置
D
指定位置
4
、 由权值分别为
11
,
8
,
6
,
2
,
5
的叶子结点生成一棵哈夫曼树,它的带权路
径长度为()
A 24 B 71 C 48 D 53
填空题(每空
1
分,共
32
分)
1
、 数据的逻辑结构被分为 ________ 、 ____________ 、 ________ 和 ________
四种。
2
、 一种抽象数据类型包括 ______________ 和 ______________ 个部分。
3
、 在下面的数组
a
中链接存储着一个线性表,表头指针为
a[o].next
,则该线
性表为 _____________________________________________________ 。
4
、在以
HL
为表头指针的带表头附加结点的单链表和循环单链表中, 判断链
表为空的条件分别为 ________________ 和 ______________________ 。
5
、 用具有
n
个元素的一维数组存储一个循环队列,则其队首指针总是指向
队首元素的 ___________ ,该循环队列的最大长度为 __________ 。
6
、 当堆栈采用顺序存储结构时,栈顶元素的值可用 --------------- 表示;
当堆栈采用链接存储结构时,栈顶元素的值可用 _________________ 示。
7
、 一棵高度为
5
的二叉树中最少含有 _________ 结点,最多含有 __________
个结点;
一棵高度为
5
的理想平衡树中,最少含有 _____________ 结点,最多含有
_________ 结点。
&
在图的邻接表中,每个结点被称为 _______________ ,通常它包含三个域:
_
k
日 一日 一日
60 56 42 38
74 25
4 3 7
6 2
0 1
a 0 1 2 3 4 5 6 7 8
data
n
ext