-
《数据结构》复习提纲
第一章
数据结构的概念及基本结构,数据结构在计算机中的表示方法及其存储结构
算法的特性,会计算时间复杂度
第二章
线性表的顺序存储表示,掌握插入和删除操作,
线性表的链式存储表示,掌握单链表的插入和删除操作
第三章
栈的定义及特点,栈的顺序存储表示
队列的定义及特点,链队列的插入和删除,循环队列的判空判满条件
第四章
串的概念及
常用操作,掌握模式串
next
函数的求法
第五章
特殊矩阵的存储表示,稀疏矩阵的三元组表示,
会求广义表的头部和尾部
第六章
树的定义和基本概念,二叉树的性质,
二叉树的链式存储结构――二叉链表
二叉树的先序,中序,后序
,
层次遍历操作
会对二叉树进行先序,中序,后序线索化操作
树的存储结构――-孩子兄弟表示法
树,森林,二叉树三者之间的转换方法,以及它们遍历的对应关系
掌握哈夫曼树的构造,会求树的带权路径长度
WPL
第七章
图的定义和术语,图的邻接矩阵表示法,邻接表,逆邻接表
掌握图的深度优先搜索算法,广度优先搜索算法
最小生成树――普里姆算法和克鲁斯卡尔算法,
会对
AOV
网进行拓扑排序
会求
AOE
网的关键路径,关键活动
第九章
顺序查找表,有序表的折半查找,索引查找表及其平均查找长度
ASL
二叉排序树的建立和删除操作,会计算其平均查找长度
ASL
掌握将二叉排序树转换成平衡二叉树的旋转处理方法,
哈希表的概念,掌握哈希函数的构造方法――除留余数法
掌握处理冲突的方法――线性探测再散列及平均查找长度
ASL
――二次探测再散列及平均查找长度
ASL
第十章
直接插入排序,希尔排序,快速排序,简单选择排序,堆排序,归并排序
会写上述排序算法每趟排序的结果,并对其进行排序性能分析(稳定性,时间复杂度等)
期末考试题型:选择题,填空题,综合题
练习题
一、单选题
1.
一个栈的输入 序列为
1
,
2
,
3
,
4
,下面哪一个序列不可能是这个栈的输出序列?(
c
)
A.
1
,
3
,
2
,
4 B. 2
,
3
,
4
,
1
C.
4
,
3
,
1
,
2 D. 3
,
4
,
2
,
1
2.
下列排序方法中,关键字的比较次数与记 录的初始排列状态无关?(
c
)
A.
直接插入排序
B.
起泡排序
C.
快速排序
D.
直接选择排序
3.
对
n
个记 录的文件进行二路归并排序,总的时间代价为(
d
)
2
A.
O
(
nlogn
)
B. O
(
n
)
C. O
(
logn
)
D. O
(
n
)
4.
若一棵二叉树具有
10
个度为
2
的结点,则该二叉树的度为
0
的结点个数是(
b
)
A. 9 B. 11 C. 12
D.
不确定
5
.在一个单链表
HL
中,若要在指针
q
所指结点的后面插入一个由指针< /p>
p
所指向的结点,则执行(
d
)
A
.
q
一
>ne xt
=
p
一
>next
;
p
一
>next
=
q
; p>
B
.
p
一
>next
=
q
一
>next
;
q
=
p
;
C
.
q
一
>ne xt
=
p
一
>next
;
p
一
>next
=
q
; p>
D
.
p
一
>next
=
q
一
>next
;
q
一
>next
=
p p>
;
6.
广义表
A=
(
a,b,(c,d),(e,(f,g))
)
,
则式子
Head(Tail(Head(Tail(Tail(A)))))
< p>的值为d
;
A
.
(
g
)
B.(d) C.c D.d
7.
直接插入排序在最好情况下的时间复杂度为
(
d
)
。
2
A. O(logn) B. O(n) C.
O(n*logn) D(n
)
8
.数据结构是(
b
)
A
.一种数据类型
B
.数据的存储结构
C
.一组性质相同的数据元素的集合
D
.相互之间存在一种或多种特定关系的数据元素的集合
9
.算法分析的目的是(
)
A
.辨别数据结构的合理性
B
.评价算法的效率
C
.研究算法中输入与输出的关系
D
.鉴别算法的可读性
10
.在线性 表的下列运算中,不改变数据元素之间结构关系的运算是(
)
A
.插入
B
.删除
C
.排序
D
.定位
11
.二维数组
< p>A[8][9]按行优先顺序存储,若数组元素
A[2][3]
的存储地址为
1087
,
A[4][7]
的存储 地址
为
1153
,则数组元素
A[6][ 7]
的存储地址为(
)
A
.
1207 B
.
1209 C
.
1211 D
.
1213
12
.在按层次遍历二 叉树的算法中,需要借助的辅助数据结构是(
)
A
.队列
B
.栈
C
.线性表
D
.有序表
13
.在任意一棵二叉树 的前序序列和后序序列中,各叶子之间的相对次序关系(
)
A
.不一定相同
B
.都相同
C
.都不相同
D
.互为逆序
14
.若采用孩子兄弟 链表作为树的存储结构,则树的后序遍历应采用二叉树的(
c
)
A
.层次遍历
B
.前序遍历
C
.中序遍历
D
.后序遍历
15
.若用邻接矩阵表 示一个有向图,则其中每一列包含的″1″的个数为(
)
A
.图中每个顶点的入度
B
.图中每个顶点的出度
C
.图中弧的条数
D
.图中连通分量的数目
16
.图的邻接矩阵表示法适用于表示(
)
A
.无向图
B
.有向图
C
.稠密图
D
.稀疏图
17
.
在 对
n
个关键字进行简单选择排序的过程中,
每一趟都要从无序区选 出最小关键字元素,
则在进行
第
i
趟排序 之前,无序区中关键字元素的个数为(
)
A
.
i B
.
i+1 C
.
n-i D
.
n-i+1
18
.下列排序算法 中,其时间复杂度和记录的初始排列无关的是(
c
)
A
.插入排序
B
.堆排序
C
.快速排序
D
.冒泡排序
19
、冒泡排序是(
a
)的排序方法
A
、稳定
B
、不稳定
C
、外部
D
、选择
20
.若有序表的关键字序列 为(
b,c,d,e,f,g,q,r,s,t
),则在二分查找关键字
b
的过程中,先后进行
比较的关键字依次为(
b
)
A
.
f,c,b B
.
f,d,b C
.
g,c,b D
.
g,d,b
21.
主串
S=
,若对子串
T=
执行定位操作
Inde x(S,T,9)
,则操作的结果是
__d_
。
A)2 B)3 C)4 D)10
22.<
/p>
设有一个
10
阶的对称矩阵
A
,采有 压缩存储方式,以行序为存储主序,若
a(1,1)
为第一个元素,其
< p>存储地址为
1
,且每个元素占用
1
个 地址空间,则
a(8,5)
元素的地址为
___
。
A)13 B)33 C)18 D)40
二、填空题
1.
从逻辑结构看,线性表是典型的
线性结构
,树是典型的
树形结构
。
2
.
一棵含
999
个结点的完全二叉树的深度为
__ __10_ __
。
3
.含
n
个顶点的无向连通图中至少含有
______
条边。 p>
4.
若对关键字序列(
43
,
02
,
80
,
48
,
26
,
57
,
15
< p>,73
,
21
,
24
,
66
)进行一趟增量为
3
的希尔排
序,则得到的结果为
____ __
。
5
.
数据的逻辑结构被分为
______
集合
_____
、
___
线性结构
___
、
_
树形结构和
____ p>
图形结构
__
四种。
6
p>
.在一个稀疏矩阵中,每个非零元素所对应的三元组包括该元素的
____
< p>行号_
、
_
列号
_
< p>和_
元素值
__
三项。
-
-
-
-
-
-
-
-
-
上一篇:南昌航空大学-大学物理D资料(含答案)
下一篇:学术沙龙执行方案