数据结构复习剖析Word文档下载推荐.docx
- 文档编号:7302039
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:35
- 大小:112.49KB
数据结构复习剖析Word文档下载推荐.docx
《数据结构复习剖析Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构复习剖析Word文档下载推荐.docx(35页珍藏版)》请在冰点文库上搜索。
next=p->
next;
p->
next=s;
B.p->
next=s->
s->
next=p;
C.q->
D.p->
next=q;
8.在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行____。
B.s->
C.s->
p=s;
D.p->
9.在一个单链表中,若删除p所指结点的后续结点,则执行____。
A.p->
next=p->
next->
next;
B.p=p->
C.p->
D.p=p->
10.链表不具备的特点是____。
A可随机访问任何一个元素B插入、删除操作不需要移动元素
C无需事先估计存储空间大小D所需存储空间与线性表长度成正比
11.一个队列的数据入列序列是1,2,3,4,则队列的出队时输出序列是____。
A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,1
12.一个队列的数据入列序列是1,2,3,4,把队列的数据出队后压入一个栈中,当队列为空时再把数据从栈中弹出,数据的出栈序列是____。
A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,1
13.判断一个表达式中左右括号是否匹配,采用____实现较为方便。
A线性表的顺序存储B队列C线性表的链式存储D栈
14.栈与一般线性表区别主要在方面。
A元素个数B元素类型C逻辑结构D插入、删除元素的位置
15.在一个链队中,假设F和R分别是队首和队尾指针,则数据出队的运算是。
AR=F->
BR=R->
CF=F->
DF=R->
填空题(排序结果由小到大排列)
6.数据元素是数据的基本单位,有些情况下它也称为元素、结点、记录。
7.数据项是数据的不可分割的最小单位。
8.数据结构按逻辑结构可分为线性结构和非线性结构。
9.一组记录的关键字为(5,6,2,4,3,1),利用简单选择排序的方法,经过3趟排序后,其关键字序列为1,2,3,4,6,5
10.一组记录的关键字为(5,6,2,4,3,1),利用直接插入排序的方法,经过3趟排序后,其关键字序列为2,4,5,6,3,1
11.一组记录的关键字为(38,5,19,26,49,97,1,66),利用冒泡排序的方法,经过3趟排序后,其关键字序列为5,19,26,38,1,49,66,97
12.一组记录的关键字为(265,301,751,129,937,863,742,694,76,438),利用快速排序的方法,经过3趟排序后,其关键字序列为76,129,265,438,301,694,742,751,863,937
13.一组记录的关键字为(265,301,751,129,937,863,742,694,76,438),利用归并排序的方法,经过3趟排序后,其关键字序列为129,265,301,694,742,751,863,937,76,438
14.在一个长度为n的顺序表中删除第i个元素,要移动N-I个元素。
如果要在第i个元素前插入一个元素,要后移N-I+1个元素。
15.栈操作数据的原则是后进先出,队列操作数据的原则是先进先出。
16.在栈中,可进行插入和删除操作的一端称栈顶。
17.栈和队列都是__线性__结构;
对于栈只能在_栈顶___插入和删除元素;
对于队列只能在__队尾__插入元素和___队头_删除元素。
18.计算机在运行递归程序时,要用到系统提供的栈。
19.表达式a*(b+c)-d的后缀表达式是abc+*d-
20.若a=1,b=2,c=3,d=4,则后缀式db/cc*a-b*+的运算结果为_18
21.设将整数1,2,3,4进栈,若入、出栈次序为Push,Pop,Push,Push,Pop,Pop,Push,Pop,则出栈的数字序列为1324;
若想得到出栈序列1432则具体操作为:
Push,Pop,Push,Push,Push,Pop,Pop,Pop
22.在采用少用一个存储空间的具有n个单元的循环队列中,队满时共有n-1个元素。
对于下图所示的循环队列,队满的条件是front=(rear+1)%MAXSIZE;
队空的条件是rear=front
23.一棵有n个结点的满二叉树有__0_个度为1的结点、有__(n-1)/2_个分支(非终端)结点和__(n+1)/2_个叶子,该满二叉树的深度为_log2(n+1)__。
24.
写出下图二叉树的先序遍历结果ABDCEFJ中序遍历结果DBAECJF、后序遍历结果DBEJFCA
第九周:
排序练习
插入排序:
初始数据:
3020504060
1.30
2.2030
3.203050
4.20304050
5.2030405060
选择排序:
1.2030504060
2.2030504060
3.2030405060
4.2030405060
第十二周:
查找练习
1、已知散列表地址区间为0~10,哈希函数为H(k)=k%ll,给定关键字序列(16,13,20,18,23,15,31,45,56)。
分别采用线性探测法和链接法,将以上关键字依次存储到哈希表中。
请描述出散列地址的计算过程及最后得到的散列表。
1
2
3
4
5
6
7
8
9
10
23
13
45
15
16
56
18
20
31
线性探测法:
H(k)=k%:
ll
第一趟
K=16
H(16)=5
第二趟:
K=13
H(13)=2
第三趟:
K=20
H(20)=9
第四趟:
K=18
H(18)=7
第五趟:
K=23
H(23)=1
K=15
H(15)=4
第六趟:
K=31
H(31)=9
由于与20发生冲突,H(31)=(31+1)/11.即H(31)=10
第七趟:
K=45
H(45)=1
由于与23发生冲突,H(45)=(45+1)/11.即H(45)=2
但又与13发生冲突,H(45)=(45+2)/11.即H(45)=3
第八趟:
K=56
H(56)=1
但又与45发生冲突,H(45)=(45+3)/11.即H(45)=4
但又与15发生冲突,H(45)=(45+4)/11.即H(45)=5
但又与16发生冲突,H(45)=(45+5)/11.即H(45)=6
链接法:
^
30
2、考虑散列表的查找方法,试完成以下两题
⑴已知哈希函数为H(k)=k%ll,线性探测法解决冲突,散列表状态如下:
请描述出关键字45和5的查找过程及结果。
查找45:
H(K)=K%11
由于23不等于45,即H(45)=(45+1)/11=2
由于13不等于45,即H(45)=(45+2)/11=3
由于H(45)=3时,查找成功.比较次数为3
查找5
K=5
K(5)=5
由于16不等于5,即H(5)=(5+1)/11=6
由于56不等于5,即H(5)=(5+1)/11=7
由于18不等于5,即H(5)=(5+1)/11=8
由于H(8)为空,所以关键字5一定不在哈希表中..
⑵已知哈希函数为H(k)=k%ll,线性探测法解决冲突,散列表状态如下:
33
19
请描述出关键字50的查找过程及结果。
K=50
H(50)=6
由于56不等于50,即H(50)=(50+1)/11=7.
由于18不等于50,即H(50)=(50+2)/11=8
由于19不等于50,即H(50)=(50+3)/11=9
由于20不等于50,即H(50)=(50+4)/11=10
由于31不等于50,即H(50)=(50+5)/11=0
由于33不等于50,即H(50)=(50+6)/11=1
由于23不等于50,即H(50)=(50+7)/11=2
由于13不等于50,即H(50)=(50+8)/11=3
由于45不等于50,即H(50)=(50+9)/11=4
由于15不等于50,即H(50)=(50+10)/11=5
由于16不等于50,即H(50)=(50+11)/11=6
由于游历一遍后,亦没有查找关键字50,即查找失败..
第十三周:
数的遍历
1、分别写出下面二叉树的层次、先序、中序、后序遍历的次序。
H
层次:
ABCDEFGH
先序:
ABDFGCEH
中序:
BFDGAEHC
后序:
FGDBHECA
2、画出上面二叉树的二叉链的链式结构
A
ROOT
B
C
E
D
F
G
3、给出一颗二叉树的后序遍历和中序遍历的次序,画出这颗树。
后序遍历为:
BDECA
中序编列为:
BADCE
第十四周:
二叉树
1、画出创建下列数据到二叉排序树的过程,并中序遍历这棵二叉排序树。
3620508030202656
36
50
80
26
中序遍历:
1020263036565080
2、把下列数据生成一棵完全二叉树,并判断这棵树是不是堆。
如果不是就调整为最大堆结构。
9080603020506070
90
60
70
化成大堆
“
3、下面是一棵最小堆结构的树,列出输出排序次序的过程(即每次输出根结点后,删除根)。
过程:
输出10
输出20
输出26
输出30
输出36
输出60
第十五周图的存储结构
三、练习题
1.画出下面无向图的邻接矩阵和邻接表(参考课件)。
E^
A^
B
C
D
A^
A
E
D^
或
4^
这个是后插式,还有前插式。
2.画出下面有向图的邻接矩阵和邻接表。
B^
第3题:
structEdgeNode
{
intadjvex;
EdgeNode*next;
};
structVertexNode
charvexdata;
EdgeNode*firstarc;
VertexNodeG[5];
第十六周:
复习
一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号
(A,B,C,D)写在下表中,答题写在其它地方无效;
每小题1分
题号1234567891011
答案
1.数据的不可分割的基本单位是__D__。
A.元素 B.结点 C.数据类型 D.数据项
数据项是具有独立含义的标识单位,是数据不可分割的最小单位;
数据元素是数据的操作基本单位。
数据元素也又可称为元素、结点、顶点、记录等。
7.与中缀表达式a+b*c-d等价的后缀表达式是_abc*+d-_。
运算符优先级:
0:
(#
1:
+-
2:
*/
利用栈结构存放运算符
转换规则:
①操作数直接存放在后缀表达式中
②运算符按照以下规则入栈/出栈:
先预存“#”至栈底
a)“(”强制入栈
b)遇到“)”开始出栈,直到遇见栈顶元素为“(”为止
c)如果中缀表达式中扫描的当前运算符优先级高于栈顶运算符优先级则当前运算符入栈,否则要栈顶运算符先出栈再进行比较。
8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次 与表中元素__D__进行比较,。
A.65,15,37 B.68,30,37
C.65,15,30 D.65,15,30,37
数组A:
37
65
68
72
89
99
low=0,high=9
⑴(0+9)/2=437<
A[4]low=0,high=4-1=3;
⑵(0+3)/2=137>
A[1]low=1+1=2,high=3
⑶(2+3)/2=237>
A[2]low=2+1=3,high=3
⑷(3+3)/2=337=A[3]。
9.对长度为10的表作选择(简单选择)排序,共需比较__A__次关键字。
A.45 B.90 C.55 D.110
10.对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为__C__。
A.O(log2n) B.O(nlog2n) C.O(n2) D.O(2n)
11.对长度为10的表作2_路归并排序,共需移动__C__次(个)记录。
A.20 B.45 C.40 D.30
一道关于数据结构归并排序移动记录次数的题目
1234567891011121314
1&
2;
3&
4;
5&
6;
7&
8;
9&
10;
两两归并,共移动10次,比较5次
1,2&
3,4;
5,6&
7,8;
9,10两两归并,共移动10次,比较3次
1,2,3,4&
5,6,7,8;
9,10,两两归并,共移动10次,比较4次
1,2,3,4,5,6,7,8&
9,10,两两归并,共移动10次,比较8次
正序共移动10*4=40,比较5+3+4+8=20次
二、填空(每空1分,共11分)
1.一个数据结构在计算机中的表示(映象)称为___存储结构或物理结构__。
2.线性表中____元素的个数___称为表的长度。
3.栈中元素的进出原则为____后进先出或先进后出____。
4.设数组A[1..10,1..8]的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素A[4,5]的存储地址为__2056___;
若以列序为主序顺序存储,则元素A[4,5]的存储地址为__2086____。
1、1
1、2
1、3
1、4
1、5
1、6
1、7
1、8
2、1
2、2
2、3
2、4
2、5
2、6
2、7
2、8
3、1
3、2
3、3
3、4
3、5
3、6
3、7
3、8
4、1
4、2
4、3
4、4
4、5
4、6
4、7
4、8
5、1
5、2
5、3
5、4
5、5
5、6
5、7
5、8
6、1
6、2
6、3
6、4
6、5
6、6
6、7
6、8
7、1
7、2
7、3
7、4
7、5
7、6
7、7
7、8
8、1
8、2
8、3
8、4
8、5
8、6
8、7
8、8
9、1
9、9
9、3
9、4
9、5
9、6
9、7
9、8
10、1
10、2
10、3
10、4
10、5
10、6
10、7
10、8
5.一棵深度为6的满二叉树有___31__个非终端结点(分支结点)。
满二叉树的性质:
性质1:
满二叉树中第i层上有2i-1个结点数(即叶子结点)
性质2:
深度为h的满二叉树有2h-1个结点数
所以:
整棵满二叉树的结点数-叶子结点数=分支结点数
26-1-2(6-1)=31
6.若一棵二叉树中有8个度为2的结点,则它有__9_个叶子。
一般二叉树的性质:
叶子结点数=双分支结点数-1
7.顺序查找n个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为__1__次,最多为__n_次;
若查找失败,比较关键字的次数为__n+1__次。
三、回答下列问题(每小题5分,共10分)
1.线性表的存储结构,在什么情况下采用顺序结构?
为什么?
2.二叉树有哪几种基本形态?
(五种基本形态)画图说明之。
空树仅有根结点的二叉树右子树为空的二叉树左子树为空的二叉树左右子树均非空的二叉树
3画出下面无向图的邻接矩阵和邻接表(参考课件),列出该图有A为起点的广度优先遍历和深度优先遍历结果
11
12
邻接矩阵
广度优先遍历:
ABCDE或AEDCB深度优先遍历:
ABCDE或AEDCB
4列出该图的广度优先遍历和深
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习 剖析