数据结构基础南理工泰州科技学院.docx
- 文档编号:12382109
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:12
- 大小:164.29KB
数据结构基础南理工泰州科技学院.docx
《数据结构基础南理工泰州科技学院.docx》由会员分享,可在线阅读,更多相关《数据结构基础南理工泰州科技学院.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构基础南理工泰州科技学院
习题一绪论
1简要回答术语:
数据,数据元素,数据结构,数据类型。
2数据的逻辑结构?
数据的物理结构?
逻辑结构与物理结构的区别和联系是什么?
3数据结构的主要运算包括哪些?
4算法分析的目的是什么?
算法分析的主要方面是什么?
5分析以下程序段的时间复杂度,请说明分析的理由或原因。
⑴
Sum1(intn)
{intp=1,sum=0,m;
for(m=1;m<=n;m++)
{
p*=m;
sum+=p;
}
return(sum);
}
⑵
Sum2(intn)
{intsum=0,m,t;
for(m=1;m<=n;m++)
{p=1;
for(t=1;t<=m;t++)
p*=t;
sum+=p;
}
return(sum);
}
⑶递归函数
fact(intn)
{if(n<=1)
return
(1);
else
return(n*fact(n-1));
}
习题二线性表
1简述下列术语:
线性表,顺序表,链表。
2何时选用顺序表,何时选用链表作为线性表的存储结构合适?
各自的主要优缺点是什么?
3在顺序表中插入和删除一个结点平均需要移动多少个结点?
具体的移动次数取决于哪两个因素?
4链表所表示的元素是否有序?
如有序,则有序性体现于何处?
链表所表示的元素是否一定要在物理上是相邻的?
有序表的有序性又如何理解?
5设顺序表L是递增有序表,试写一算法,将x插入到L中并使L仍是递增有序表。
5写一求单链表的结点数目ListLength(L)的算法。
6写一算法将单链表中值重复的结点删除,使所得的结果链表中所有结点的值均不相同。
7设线性表中的元素按值递增有序,以带头结点head的单链表作存储结构,写一算法删除表中大于等于min且小于等于max的元素(若表中存在这样的元素),同时释放被删结点的空间。
8写一算法将带有头结点head的单链表逆置。
9写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意:
x和y是给定的参数,可以和表中的元素相同,也可以不同)。
10设A和B是两个按元素值递增有序的单链表,写一算法将A和B归并为按按元素值递减有序的单链表C,试分析算法的时间复杂度。
习题三栈和队列
1设有一个栈,元素进栈的次序为a,b,c。
问经过栈操作后可以得到哪些输出序列?
2循环队列的优点是什么?
如何判断它的空和满?
3设有一个静态顺序队列,向量大小为MAX,判断队列为空的条件是什么?
队列满的条件是什么?
4设有一个静态循环队列,向量大小为MAX,判断队列为空的条件是什么?
队列满的条件是什么?
5利用栈的基本操作,写一个返回栈S中结点个数的算法intStackSize(SeqStackS),并说明S为何不作为指针参数的算法?
6一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。
试为此双向栈设计初始化InitStack(S),入栈Push(S,i,x),出栈Pop(S,i,x)算法,其中i为0或1,用以表示栈号。
7设Q[0,6]是一个静态顺序队列,初始状态为front=rear=0,请画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。
a,b,c,d入队
a,b,c出队
i,j,k,l,m入队
d,i出队
n,o,p,q,r入队
8假设Q[0,5]是一个循环队列,初始状态为front=rear=0,请画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。
d,e,b,g,h入队
d,e出队
i,j,k,l,m入队
b出队
n,o,p,q,r入队
习题六树和二叉树
⑴假设在树中,结点x是结点y的双亲时,用(x,y)来表示树边。
已知一棵树的树边集合为{(e,i),(b,e),(b,d),(a,b),(g,j),(c,g),(c,f),(h,l),(c,h),(a,c)},用树型表示法表示该树,并回答下列问题:
①哪个是根结点?
哪些是叶子结点?
哪个是g的双亲?
哪些是g的祖先?
哪些是g的孩子?
那些是e的子孙?
哪些是e的兄弟?
哪些是f的兄弟?
②b和n的层次各是多少?
树的深度是多少?
以结点c为根的子树的深度是多少?
⑵一棵深度为h的满k叉树有如下性质:
第h层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。
如果按层次顺序(同层自左至右)从1开始对全部结点编号,问:
①各层的结点数是多少?
②编号为i的结点的双亲结点(若存在)的编号是多少?
③编号为i的结点的第j个孩子结点(若存在)的编号是多少?
④编号为i的结点的有右兄弟的条件是什么?
其右兄弟的编号是多少?
⑶设有如图6-27所示的二叉树。
①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。
②写出该二叉树的先序、中序、后序遍历序列。
⑷已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF,请画出这棵二叉树,然后给出该树的后序遍历序列。
⑸设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA,请画出这棵二叉树,然后给出该树的先序序列。
⑹已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca,请画出这棵二叉树对应的中序线索树和后序线索树。
⑺以二叉链表为存储结构,请分别写出求二叉树的结点总数及叶子结点总数的算法。
⑻设图6-27所示的二叉树是森林F所对应的二叉树,请画出森林F。
⑼设有一棵树,如图6-28所示。
①请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。
②请给出该树的先序遍历序列和后序遍历序列。
③请将这棵树转换成二叉树。
⑽设给定权值集合w={3,5,7,8,11,12},请构造关于w的一棵huffman树,并求其加权路径长度WPL。
⑾假设用于通信的电文是由字符集{a,b,c,d,e,f,g,h}中的字符构成,这8个字符在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。
①请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。
②求出每个字符的huffman编码。
习题七图
⑴分析并回答下列问题:
①图中顶点的度之和与边数之和的关系?
②有向图中顶点的入度之和与出度之和的关系?
③具有n个顶点的无向图,至少应有多少条边才能确保是一个连通图?
若采用邻接矩阵表示,则该矩阵的大小是多少?
④具有n个顶点的有向图,至少应有多少条弧才能确保是强连通图的?
为什么?
⑵设一有向图G=(V,E),其中V={a,b,c,d,e},E={,,,
①请画出该有向图,并求各顶点的入度和出度。
②分别画出有向图的正邻接链表和逆邻接链表。
⑶对图7-27所示的带权无向图。
①写出相应的邻接矩阵表示。
②写出相应的边表表示。
③求出各顶点的度。
⑷已知有向图的逆邻接链表如图7-28所示。
①画出该有向图。
②写出相应的邻接矩阵表示。
③写出从顶点a开始的深度优先和广度优先遍历序列。
④画出从顶点a开始的深度优先和广度优先生成树。
⑸一个带权连通图的最小生成树是否唯一?
在什么情况下可能不唯一?
⑹对于图7-27所示的带权无向图。
①按照Prime算法给出从顶点2开始构造最小生成树的过程。
②按照Kruskal算法给出最小生成树的过程。
⑺已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,给出相应的求解步骤。
⑻已知带权有向图如图7-30所示,请利用Floyd算法求出每对顶点之间的最短路径及路径长度。
⑼一个AOV网用邻接矩阵表示,如图7-31。
用拓扑排序求该AOV网的一个拓扑序列,给出相应的步骤。
⑽拓扑排序的结果不是唯一的,请给出如图7-32所示的有向图的所有可能的拓扑序列。
⑾请在深度优先搜索算法的基础上设计一个对有向无环图进行拓扑排序的算法。
⑿设计一个算法利用图的遍历方法输出一个无向图G中从顶点Vi到Vj的长度为S的简单路径,设图采用邻接链表作为存储结构。
⒀假设一个工程的进度计划用AOE网表示,如图7-33所示。
①求出每个事件的最早发生时间和最晚发生时间。
②该工程完工至少需要多少时间?
③求出所有关键路径和关键活动。
习题九查找
⑴对于一个有n个元素的线性表,若采用顺序查找方法时的平均查找长度是什么?
若结点是有序的,则采用折半查找法是的平均查找长度是什么?
⑵设查找表采用单链表存储,请分别写出对该表进行顺序查找的静态查找和动态查找的算法。
⑶设二叉排序树中的关键字互不相同:
则
①最小元素无左孩子,最大元素无右孩子,此命题是否正确?
②最大和最小元素一定是叶子结点吗?
③一个新结点总是插入在叶子结点上吗?
⑷试比较哈希表构造时几种冲突处理方法的优点和缺点。
⑸将关键字序列(10,2,26,4,18,24,21,15,8,23,5,12,14)依次插入到初态为空的二叉排序树中,请画出所得到的树T;然后画出删除10之后的二叉排序树T1;若再将10插入到T1中得到的二叉排序树T2是否与T1相同?
请给出T2的先序、中序和后序序列。
⑹设有关键字序列为:
(Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar),请手工构造一棵二叉排序树。
该树是平衡二叉排序树?
若不是,请为其构造一棵平衡二叉排序树。
⑺设关键字序列是(19,14,23,01,68,84,27,55,11,34,79),散列表长度是11,散列函数是H(key)=keyMOD11,
①采用开放地址法的线性探测方法解决冲突,请构造该关键字序列的哈希表。
②采用开放地址法的二次探测方法解决冲突,请构造该关键字序列的哈希表。
⑻试比较线性索引和树形索引的优点和缺点。
⑼设关键字序列是(19,24,23,17,38,04,27,51,31,34,69),散列表长度是11,散列函数是H(key)=keyMOD11,
①采用开放地址法的线性探测方法解决冲突,请构造该关键字序列的哈希表。
②求出在等概率情况下,该方法的查找成功和不成功的平均查找长度ASL。
⑽下图是一棵3阶B_树,请画出插入关键字B,L,P,Q后的树形。
习题十内部排序
⑴回答下列各题:
①从未排序序列中挑选元素,并将其依次放入到已排序序列中(初始时为空)的一端的方法是什么?
②在待排序的元素基本有序的前提下,效率最高的排序方法是什么?
③从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置方法是什么?
④设有1000个元素,希望采用最快的速度挑选出其中前10个最大的元素,最好的方法是什么?
⑵若对关键字序列为(54,37,93,25,17,68,58,41,76)的一组记录进行快速排序时,递归调用使用的栈所能到达的最大深度是多少?
共需递归调用多少次?
其中第二次递归调用是对哪组记录进行排序?
⑶在堆排序,快速排序和归并排序中,若只从存储空间考虑,应选择哪种方法;若只从排序结果的稳定性考虑,应选择哪种方法;若只从平均情况下排序最快考虑,应选择哪种方法;
⑷设有关键字序列为(14,17,53,35,9,32,68,41,76,23)的一组记录,请给出用希尔排序法(增量序列是5,3,1)排序时的每一躺结果。
⑸设有关键字序列为(14,17,53,35,9,37,68,21,46)的一组记录,请给出冒泡排序法排序时的每一躺结果。
⑹设有关键字序列为(14,17,53,35,9,37,68,21,46)的一组记录,利用快速排序法进行排序时,请给出以第一个记录为基准得到的一次划分结果。
⑺设关键字序列为(14,17,53,35,9,37,68,21)的一组记录,请给出按非递增采用堆排序时的每一躺结果。
⑻设关键字序列为(314,617,253,335,19,237,464,121,46,231,176,344)的一组记录,请给出采用基数排序时的每一躺结果。
⑼将哨兵放在R[n]中,被排序的记录存放在R[1…n-1]中,重写直接插入排序算法。
⑽实际中常采用单链表存储数据记录,请写出排序记录的结构的定义并修改。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 基础 理工 泰州 科技学院