没有合适的资源?快使用搜索试试~ 我知道了~
数据结构与算法复习提纲.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 110 浏览量
2023-04-01
19:22:52
上传
评论
收藏 690KB PDF 举报
温馨提示
试读
17页
。
资源推荐
资源详情
资源评论
数据结构与算法复习提纲
第一部分 概念题
见练习一、二、三及习题等
注意二叉树的 5 条性质的运用等
例: 选择题
(1)表长为n 的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,
插入一个元素所需移动元素的平均个数为( E ),删除一个元素所需移动元素的平均个数
为( A )。
A.(n − 1)/2 B.n C.n + 1 D.n − 1
E.n/2 F.(n + 1)/2 G.(n − 2)/2
(2)设栈S 和队列Q 的初始状态为空,元素e1、e2、e3、e4、e5 和e6 依次通过栈S,
一个元素出栈后即进入队列Q,若6 个元素出队的序列为e2、e4、e3、e6、e5 和e1,则栈S
的容量至少应该为( C )。
A.6 B.4 C.3 D.2
(3)设栈的输入序列为1、2、3 … n,若输出序列的第一个元素为n,则第i 个输出的元素
为( B )。
A.不确定 B.n − i + 1 C.i D.n − i
(4)在一个长度为n 的顺序表中删除第i 个元素(1< = i< = n)时,需向前移动( A )个
元素。
A.n−i B.n − i +1 C.n − i − 1 D.i
(5)若长度为n 的线性表采用顺序存储结构存储,在第i 个位置上插入一个新元素的时
间复杂度为( A )。
A.O(n) B.O(1) C.O(n
2
) D.O(n
3
)
(6)队列是一种特殊的线性表,其特殊性在于( C )。
A.插入和删除在表的不同位置执行 B.插入和删除在表的两端位置执行
C.插入和删除分别在表的两端执行 D.插入和删除都在表的某一端执行
(7)栈是一种特殊的线性表,具有( B )性质。
A.先进先出 B.先进后出 C.后进后出 D.顺序进出
(8)顺序循环队列中(数组的大小为n),队头指示front 指向队列的第1 个元素,队尾
指示rear 指向队列最后元素的后1 个位置,则循环队列中存放了n
−
1 个元素,即循环队
列满的条件为( B )。
A.(rear + 1)%n = front − 1 B.(rear + 1)%n = front
C.(rear)%n = front D.rear + 1 = front
(9)顺序循环队列中(数组的大小为6),队头指示front 和队尾指示rear 的值分别为3
和0,当从队列中删除1 个元素,再插入2 个元素后,front 和rear 的值分别为( D )。
A
.
A.5 和 1 B.2 和 4 C.1 和 5 D.4 和 2
1
(10)前序遍历和中序遍历结果相同的二叉树为( F );前序遍历和后序遍历结果相同的
二叉树为( B )。
A.一般二叉树
B.只有根结点的二叉树
C.根结点无左孩子的二叉树
D.根结点无右孩子的二叉树
E.所有结点只有左子树的二叉树
F.所有结点只有右子树的二叉树。
(11)以下有关二叉树的说法正确的是( B )。
A.二叉树的度为2 B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2 D.二叉树中任一个结点的度均为2
(12) 用一维数组存放完全二叉树:ABCDEFGHI,则后序遍历该二叉树的结点序列为
( HIDEBFGCA )。(首先画出完全二叉树,然后再后序遍历该二叉树)
(1)在关键字序列(12,23,34,45,56,67,78,89,91)中二分查找关键字为45、
89 和12 的结点时,所需进行的比较次数分别为( B )
A.4,4,3 B.4,3,3 C.3,4,4 D.3,3,4
(2)适用于折半查找的表的存储方式及元素排列要求为( D )。
A.链式方式存储,元素无序 B.链式方式存储,元素有序
C.顺序方式存储,元素无序 D.顺序方式存储,元素有序
在一个带权连通图G 中,权值最小的边一定包含在G 的( A )。
A.最小生成树中 B.深度优先生成树中
C.广度优先生成树中 D.深度优先生成森林中
已知一个有向图下图 所示,则从顶点a 出发进行深度优先偏历,不可能得到的DFS
序列为( A )。
A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b
(2)下列说法错误的是( D )
A.冒泡排序在数据有序的情况下具有最少的比较次数。
B.直接插入排序在数据有序的情况下具有最少的比较次数。
C.二路归并排序需要借助O(n)的存储空间。
D.基数排序适合于实型数据的排序。
(3)下面的序列中初始序列构成最小堆(小根堆)的是( D )。
A.10、60、20、50、30、26、35、40
B.70、40、36、30、20、16、28、10
2
C.20、60、50、40、30、10、8、72
D.10、30、20、50、40、26、35、60
(4)在下列算法中,( C )算法可能出现下列情况:在最后一趟开始之前,所有的
元素都不在其最终的位置上。
A. 堆排序 B.插入排序 C.冒泡排序 D.快速排序
(6)以下排序方法中,不稳定的排序方法是( AC )。
A.直接选择排序 B.二分法插入排序
C.堆排序 D.基数排序
(7)一个序列中有10000 个元素,若只想得到其中前10 个最小元素,最好采用( B )
方法。
A.快速排序 B.堆排序 C.插入排序 D.二路归并排序
(8)若要求尽可能快地对实数数组进行稳定的排序,则应选( C )
A.快速排序 B.堆排序 C.归并排序 D.基数排序
(9)排序的趟数与待排序元素的原始状态有关的排序方法是( A )。
A.冒泡排序 B.快速排序 C.插入排序 D.选择排序
(10)直接插入排序在最好情况下的时间复杂度为( A )。
A.O(n) B.O(log n) C.O(nlog n) D.O(n
2
)
第二部分 计算题和证明题
1、 数组元素地址的计算
例:在一个 C 语言程序中,有结构类型 STUDENT 的定义和结构数组 allstudents 的声明如下:
struct STUDENT
{
char name[8];
int number;
}
STUDENT allstudents[10][50];
allstudents 是一个二维数组,它的每个元素都是包含name 和 number 的结构类型。已知
在 C 语言中,二维数组使用以行序为主序的存储结构,char 类型占用 1 字节,int 类型占用
4 字节。
假定 allstudents 在内存中的起始存储位置是 2000,请写出计算 allstudents[i][j]的存储位
置的算式,并计算 allstudents[3][5]的存储位置。
答: (1) allstudents[i][j]的存储位置=2000+(i*50+j)*12
(2) allstudents[3][5]的存储位置=2000(3*50+5)*12=3860
见练习一、二、三
2、 计算树的结点数等
例:
(1)一棵完全二叉树上有1001 个结点,其中叶子结点的个数为( D )。
A.250 B.500 C.254 D.501
深度为k的二叉树至多有
2
k
-1
个结点(k>=1)。(2
10
=1024)
可先求2度结点数,再由此得到叶子总数。
前9层总结点数为2
9
-1=511
3
首先,前k-2层的2
8
-1(255)个结点肯定都是2度的(完全二叉)
另外,末层叶子为489(末层叶子数为1001-511=490个
所对应的双亲也是度=2, (共有490/2=245个)。
所以,全部2度结点数为255(前k-2层)+245(第k-1层)=500个;
总叶子数=2度结点数+1=501个。
(2)一棵完全二叉树有999 个结点,它的深度为( B )。
A.9 B.10 C.11 D.12
深度为k的二叉树至多有
(3)一棵具有5 层的满二叉树所包含的结点个数为( B )。
A.15 B.31 C.63 D.32
深度为k的二叉树至多有
2
k
-1
个结点(k>=1)。(2
10
=1024)
2
k
-1
个结点
(4) 有n 个结点的二叉树,已知叶结点个数为n
0
,则该树中度为1 的结点的个数为
( n-2n
0
+1 )(因为 n0=n2+1);若此树是深度为k 的完全二叉树,则n 的最小值为(
2
k
-1
)
2 -1≤n<2
。
(5)设F 是由T1、T2 和T3 三棵树组成的森林,与F 对应的二叉树为B。已知T1、T2
和T3 的结点数分别是n1、n2 和n3,则二叉树B 的左子树中有( n1-1 )个结点,二叉树
B 的右子树中有( n2+n3 )结点。(首先将森林转为二叉数(兄弟相连 长兄为父,孩子靠左
头根为根 ),然后可得 左子树由T1构成,右由T2和3构成)
(6) 高度为k 的二叉树的最大结点数为( 2
k
-1 ),最小结点数为( k )。
(7) 对于一棵具有 n 个结点的二叉树,该二叉树中所有结点的度数之和为( n-1 )。
(8)已知含10 个结点的二叉排序树是一棵完全二叉树,则该二叉排序树在等概率情况下查
找成功的平均查找长度等于( B )。见习题
A.1.0 B.2.9 C.3.4 D.5.5
(9) 画出对长度为 10 的有序表进行折半查找的判定树,并求其概率时查找成功的平均查找
长度。见习题 9.3 (平均查找长度=2.9)
(10)将一棵有 100 个节点的完全二叉树从上到下,从左到右依次对节点进行编号,根
结点的编号为 1,则编号为 49 的结点的右孩子编号为__A__。
A: 99
B: 98
C: 50
D: 48
性质
5: 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必
为
2i,
其右孩子编号必为
2i+1;
其双亲的编号必为
i/2
(i
=
1 时为根,除外)。
3、 证明题
例:任意一棵有 N 个结点的二叉树,已知它有 M 个叶子结点。试证明非叶子结点中度数为
k k
4
剩余16页未读,继续阅读
资源评论
若♡
- 粉丝: 6196
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功