数据结构与算法复习提纲.docx
- 文档编号:9835025
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:14
- 大小:165.26KB
数据结构与算法复习提纲.docx
《数据结构与算法复习提纲.docx》由会员分享,可在线阅读,更多相关《数据结构与算法复习提纲.docx(14页珍藏版)》请在冰点文库上搜索。
数据结构与算法复习提纲
数据结构与算法复习提纲
线性表部分:
1、顺序表的基本操作:
创建、插入、删除、查找、修改、遍历、输出
2、带头结点单链表的基本操作:
创建、插入(头插、尾插、任意位置插入)、删除(头删、尾删、任意位置删除)、查找、修改、定位、输出、求表长、遍历的基本应用
3、带头结点的循环单链表的基本操作:
创建、插入(头插、尾插、任意位置插入)、删除(头删、尾删、任意位置删除)、查找、修改、定位、输出、求表长、遍历的基本应用
4、线性表的应用:
有序顺序表的插入;有序单链表的插入;顺序表的逆置、单链表的逆置;顺序表归并、单链表归并
栈和队列部分:
1、顺序栈的基本操作:
初始化、入栈、出栈、取得栈顶元素(注意top变量的取值)、判栈空、判栈满、遍历
2、链栈的基本操作:
初始化、入栈、出栈、判栈空、遍历
3、循环队列的基本操作:
初始化、入队、出队、队空队满的判定条件、求队列长度、遍历;
4、链队列的基本操作:
初始化、入队、出队、队空、遍历
5、表达式求值:
栈中数据的变化过程
树和二叉树
1、二叉树的5个基本性质
2、二叉树的顺序存储结构
3、二叉链表存储,相关的基本操作:
前中后三种遍历、层次遍历、创建、求结点个数、求叶子个数、求深度、基于遍历的应用
4、树的孩子兄弟链表存储结构,相关的基本操作:
创建、查找某个结点的孩子、插入一个结点、求深度、先根、后根遍历输出
5、二叉树、树与森林的应用:
由两种遍历序列确定一棵二叉树;二叉树的三种遍历序列;由两种遍历序列确定一棵树;树(森林)与二叉树之间的相互转换;
6、哈夫曼树及其应用:
构造哈夫曼树、哈夫曼编码、求wpl;注意:
构造哈夫曼树过程相关存储结构的变化
图的部分
1、图的基本概念
2、图的邻接矩阵存储结构:
创建、深度遍历、广度遍历
3、图的邻接表存储结构:
创建、深度遍历、广度遍历
4、最小生成树:
prim算法
查找与排序部分
1、折半查找:
算法、查找判定树、成功与不成功的ASL
2、二叉排序树的构造、平衡二叉树的构造、成功与不成功的ASL
3、哈希表:
构造、线性探测、二次探测、拉链法;成功与不成功的ASL
4、直接插入排序、希尔排序、冒泡排序、快速排序,一趟排序的结果。
试卷样题
1、假设通信电文使用的字符集为{a,b,c,d,e,f},字符在电文中出现的频率分别为34,5,12,23,8,18。
请构造哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值),并设计哈夫曼编码(10分)。
2、设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树(10分)。
3、已知无向图G,V(G)={1,2,3,4},E(G)={(1,2),(1,3),(2,3),(2,4),(3,4)},试画出G的邻接表。
并简述,已知点i时,如何在邻接表上找到与i点相邻的所有点(10分)。
4、给定关键字序列{55,31,11,37,46,73,63,02,07}
(1)构造平衡二叉树,画出每加入一个新结点时二叉树的形态。
若发生不平衡,指明需做的平衡调整类型及调整的结果(8分)。
(2)计算该平衡二叉树在等概率下查找成功的平均查找长度(2分)。
5、设散列表的长度为13,散列函数为H(h)=k%13,给定的关键字序列为19,14,23,01,68,20,84,27。
试画出用线性探测法解决冲突时所构成的散列表(10分)。
6、设待排序序列为{10,18,4,3,6,12,1,9,15,8},请给出希尔排序一趟的结果。
增加量序列为5。
(5分)
8、试简述一种判定有向图G中是否有环(回路、圈)的方法(5分)。
9、给定如下有向图,完成问题(15分)。
1)从顶点V1出发的深度优先遍历序列;
2)从顶点V1出发的广度优先遍历序列;
10、以顺序表为存储结构,写一算法,删除线性表中从第i个元素开始的k个元素(10分)。
11、用带头结点的循环链表作为队列的存储表示,不设头指针而只设一个尾指针rear指向队尾结点。
试写出该链式队列的入队和出队算法(10分)。
复习题目:
练习题1
一、应用题
1、画出满足以下条件的二叉树形态
1)前序和中序遍历序列相同
2)中序和后序遍历序列相同
3)前序和后序遍历序列相同
2、设权W=(0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10)
(1)构造哈夫曼树,求WPL(8分)。
(2)写出这8个字母的哈夫曼编码(2分)。
3、对森林做以下操作:
(1)转换成二叉树
(2)给出二叉树的三种遍历序列
4、假设用于通讯的电文由8个字母组成,字母在电文中出现的频率分别为7,19,2,6,32,3,21,10,
5、已知一棵树的先根遍历序列为GFKDAIEBCHJ,后根遍历序列为DIAEKFCJHBG,画出该树。
6、假设一棵二叉树的中序序列为cbedahgijf和后序序列为cedbhjigfa。
(1)请画出该二叉树
(2)给出其先序遍历序列
7、已知无向图如下所示,回答问题:
1)写出邻接矩阵;(4分)
2)在邻接矩阵存储上,写出以顶点1作为源点的深度优先遍历序列;(3分)
3)在邻接矩阵存储上,写出以顶点1作为源点的广度优先遍历序列。
(3分)
二、算法设计
1、有向连通图采用邻接表存储结构,写一个根据给定值进行查找的算法(基于遍历做)。
(10分)
2、写一个在单链表上查找最大值的算法。
(10分)
3、写一个求单链表长度的算法(10分)。
4、写出建立无向图的邻接矩阵存储的算法(10分)。
练习题2
一、应用题
1、请对下图的无向带权图:
(1)写出它的邻接矩阵,并按普里姆算法求其最小生成树;
2.给定二叉树的两种遍历序列,分别是:
前序遍历序列:
D,A,C,E,B,H,F,G,I;中序遍历序列:
D,C,B,E,H,A,G,I,F,
试画出二叉树B,并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
3、把如图所示的树转化成二叉树。
4.画出和下列二叉树相应的森林。
5.假定对有序表:
(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:
(1)画出描述折半查找过程的判定树;
(2)若查找元素54,需依次与哪些元素比较?
(3)若查找元素90,需依次与哪些元素比较?
(4)假定每个元素的查找概率相等,求查找成功时的平均查找长度。
二、算法设计
1、写出循环队列初始化、入队和出队操作,并用存储示意图描述每一种操作的变化。
2、写出带头结点单链表的逆置算法。
3、写一个求二叉树叶子结点个数的算法。
注:
二叉树采用二叉链表存储。
习题3
一应用分析题.
1、给定一组关键字序列{36,75,83,54,12,67,60,40,92,72},按照关键字顺序构造一个平衡二叉树AVL,并求等概率情况下查找成功的平均查找长度ASL。
(10分)
3、设有一组关键字(32,75,29,63,48,94,25,46,18,70),采用哈希函数:
H(key)=key%13。
采用链地址法处理冲突,设计出链表结构,并计算查找成功时的平均查找长度。
(10分)
4、已知一组关键字为{46,74,16,53,14,26,40,38,86,65,27,34},利用希尔排序的方法写出增量d每取一个值后所得到的排列结果,假定d依次取5,3,1(5分)
二算法设计
1、写一个建立有向图邻接表存储结构的算法。
(10分)
习题4
一、算法应用题。
1.设哈希(Hash)表的地址范围为0~17,哈希函数为:
H(K)=KMOD17。
K为关键字,用线性探测再散列法处理冲突,输入关键字序列:
(10,24,32,17,31,30,46,47,40,63,49)
造出Hash表,试回答下列问题:
(1)画出哈希表的示意图;
(2)若查找关键字63,需要依次与哪些关键字进行比较?
(3)若查找关键字60,需要依次与哪些关键字比较?
(4)假定每个关键字的查找概率相等,求查找成功时的平均查找长度。
2.画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。
3.在一棵空的二叉查找树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉平衡树,并求ASL.
4、选取散列函数H(key)=(3*key)%11,用线性探测法和链地址法两种方法处理冲突,分别对下列关键码序列构造一个散列地址空间为0~10,表长为11的散列表,{22,41,53,08,46,30,01,31,66}。
并求各自的ASL
5、关键字序列为(7,4,5,9,1,2,8,10,6,5),写出一趟快速排序,画出排序中比较交换的过程。
6、关键字序列4938659776132749550410,画出一趟希尔排序的过程。
d1=5
二、算法设计
1、写一个单链表求长度的算法。
2、写一个根据给定值在二叉树中进行查找的算法。
二叉树采用二叉链表存储结构。
3、编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
习题5
(1)
(2)判定树如下:
(3)
课本上9.19
012345678910
22
67
41
30
53
46
13
01
13121126
H(22)=(3*22)MOD11=0
H(41)=(3*41)MOD11=2
H(53)=(3*53)MOD11=5
H(46)=(3*46)MOD11=6
H(30)=(3*30)MOD11=2
d1=1*((7*30)MOD10+1)=1,H(30)=(2+d1)MOD11=3
H(13)=(3*13)MOD11=6
d1=1*((7*13)MOD10+1)=2,H(13)=(6+d1)MOD11=8
H(01)=(3*01)MOD11=3
d1=1*((7*01)MOD10+1)=8,H(01)=(3+8)MOD11=0
d2=2*((7*01)MOD10+1)=16,H(01)=(3+16)MOD11=8
d3=3*((7*01)MOD10+1)=24,H(01)=(3+24)MOD11=5
d4=4*((7*01)MOD10+1)=32,H(01)=(3+32)MOD11=2
d5=5*((7*01)MOD10+1)=40,H(01)=(3+40)MOD11=10
H(67)=(3*67)MOD11=3
d1=1*((7*67)MOD10+1)=10,H(01)=(3+10)MOD11=2
d2=2*((7*67)MOD10+1)=10,H(01)=(3+20)MOD11=2
ASL=(1*4+2*2+3*1+6)/8=17/8
补充1:
假设一棵二叉树的中序序列为cbedahgijf和后序序列为cedbhjigfa。
(1)请画出该二叉树
(2)给出其先序遍历序列
补充2、如下无向带权图:
(1)以顶点a为源点,写出该图的深度遍历序列(3分)。
(2)以顶点a为源点,写出该图的广度遍历序列(3分)。
课本7.11
补充3、假设用于通讯的电文由8个字母组成,字母在电文中出现的频率分别为7,19,2,6,32,3,21,10,
(1)构造哈夫曼树,求WPL(8分)。
(2)写出这8个字母的哈夫曼编码(2分)。
补充4:
输入关键字序列{16,3,7,11,9,26,18,14,15},完成以下操作:
(1)按关键字顺序构造一棵AVL树(8分);
(2)求在等概率的情况下查找成功的平均查找长度ASL(2分)。
补充5:
关键字集合{19,01,23,14,55,68,11,82,36},设定哈希函数
H(key)=keyMOD11(表长=11),若采用线性探测再散列处理冲突,
(1)试画出哈希表(8分);
(2)求出等概率查找时查找成功的平均查找长度ASL(2分)。
补充6:
设有一组关键字(87,25,08,27,68,95,70,63,47),采用哈希函数:
H(key)=key%7。
采用链地址法处理冲突:
(3)画出哈希表(8分);
(4)求出等概率查找时查找成功的平均查找长度ASL(2分)。
补充7:
已知一组关键字为{46,74,16,53,14,26,40,38,86,65,27,34},利用希尔排序的方法写出增量d每取一个值后所得到的排列结果,假定d依次取5,3,1(10分)。
(1)写一个带头结点单链表的逆置算法(10分)。
提示:
先定义单链表的数据结构。
(2)写一个带岗哨的顺序查找算法(10分)。
提示:
先定义查找表的数据结构。
(3)利用栈结构,写一个10进制转换为8进制的算法。
(4)写出循环队列的入队、出队算法,并画出相应的示意图。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 复习 提纲