-
数据结构
1
一、单项选择题(每小题
2
分,共
20
分)
在下 列每小题的四个备选答案中选出一个正确的答案,并将其字母
标号填入题目的括号内。
1.
栈和队列都是(
C
)
。
A.
顺序存储的线性结构
B.
链式存储的线性结构
C.
限制存储点的线性结构
D.
限制存储点的非线性结构
2.
在一个单链表中,已知
q
所指结点是
p
所指结点的前驱结点,若在
q
和
p
之间插入
s
结点,则执行(
C
)
。
A.s->next=p->next; p->next=s; B.p->next=s->next; s->next=p;
C.q->next=s;s->next=p; D.p->next=s; s->next=q;
3.
稀疏矩阵一般的压缩存储方法有两种,即(
C
)
。
A
.二维数组和三维数组
B
三元组和散列
C
.三元组和十字链表
D
散列和十字链表
4.
对于下面的二叉树,按后序遍历所得的结点序列为(
D
)
。
A
.
1234567
B
.
1245367
C
.
4251637
D
.
452673l
5.
深度为
5
的二叉树至多有(
C
)个结点。
A. 16 B .32 C. 31 D.10
n
树的
WPL
是指(
C
)
。
A
.除根以外所有结点的权值之和
B
.所有结点权值之和
C
.各叶子结点的带权路径长度之和
D
.根结点的值
7.
下列排序方法中,
(
D
)的比较次数与记录的初始排列状态无关?
A
.直接插入排序
B
.起泡排序
C
.快速排序
D
.直接选择排序
< br>8.
若一棵二叉树具有
10
个度为
2
的结点,
则该二 叉树的度为
0
的结点个数是
(
C
)
A.
9 B
.
11 C
.
12 D
.不确定
9.
设输入序列为
1,2,3,4,5
,借助 一个栈不可能得到的输出序列是
( C )
。
A.1,2,3,4,5 B.1,4,3,2,5 C.4
,
1,3,2,5 D.1,3,2,5,4
10.
对下图,不能得到的拓扑序列是
( )
A.l,2,3,4,5,6,7,8
B.1,5,2,6,3,7,4,8
C.1,2,5,6,3,4,7,8
1
D.1,2,3,4,8,7,6,5
二、填空题(每空
1
分,共
20
分)
11.
数据元素之间的
关系
称为结构,通常有如下四种基本结构:集合
结构、
线性
结构、
树形
结构和
图形
结构。
12.
具有
n
个结点的无向图中,有
n(n-1)/2
条边的无向图称为完全图;对于具有
n
个结点有向图,有
n(n-1)
条弧的有向图称为有向完全图。
13.
循环队列用数组
A[0.. m-1]
存放其元素值。已知其头尾指针分别是
front
和
rear
,则当前队列中的元素个数是
(rear-front+m)%m
,判断队空的条件是
front==rear
。
14.
在二叉树的第
i
层上至多有
2
i-1
结点。
15.
设有一个二维数组
A[0..6 ,0..8]
,
A[0][0]
存放位置为
500
,每个元素占2
个
字节,以行序为主序列,则
A[4][5]
在位置
568
。
16.
图的遍历的两种搜索方法分别是深度优先搜索
和
广度优先搜索
。
17.
广
义
表
(a,(a,b),d,e,((i,j),k))
的
长
度< br>是
5
,
表
头
是
a
,
表
尾
是
((a,b),d,e,((i,j),k))
。
18.
查找算法中的两种最基本的操作是比较和
移动
。
19.
具有
n
条记录的顺序表中,
在查找概率 相等的情况下顺序查找平均查找长度为
(n+1)/2
。
20
.算法质量的度量标准有两个:
时间
复杂度和
空间
复杂度。
三、设计题(共
40
分)
21.
假设一棵二叉树的中序序 列为
DCBGEAHFIJK
和后序序列为
DCEGBFHKJIA
请
画出该二叉树,并给出先序序列。
(
6
分)
二叉树为
(4
’
)
先序序列为:
ABCDGEIHFJK (2
’
)
22.
已知某系统在通 讯联络中只可能出现
5
种字符
{a,b,c,d,e}
,其概率分别为
0.10
,
0.22
,
0.27
,
0.15
,< br>0.26
,试画出赫夫曼树并设计赫夫曼编码。
(
8
分)
w={10,22,27,15,26}
赫夫曼树为(
4
’)
-
-
-
-
-
-
-
-
本文更新与2021-01-25 09:48,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/565167.html