如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
PAGE\*MERGEFORMAT8数据结构复习题一、填空题1、(数据元素)是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。2、在一般情况下,一个算法的时间复杂度是(问题规模)的函数。3、设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为(Ο(1)),若为n*log25n,则表示成数量级的形式为(Ο(nlog2n))。【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。4、顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是(108)。【分析】第5个元素的存储地址=第1个元素的存储地址+(5-1)×2=1085、设单链表中指针p指向结点A,若要删除A的后继结点(假设A存在后继结点),则需修改指针的操作为(p->next=(p->next)->next)。6、非空的单循环链表由头指针head指示,则其尾结点(由指针p所指)满足(p->next=head)。7、一个具有n个结点的单链表,在指针p所指结点后插入一个新结点的时间复杂度为(Ο(1));在给定值为x的结点后插入一个新结点的时间复杂度为(Ο(n))。8、设有一个空栈,栈顶指针为1000H,现有输入序列为1、2、3、4、5,经过push,push,pop,push,pop,push,push后,输出序列是(23),栈顶指针为(1003H)。9、(栈)可作为实现递归函数调用的一种数据结构。【分析】递归函数的调用和返回正好符合后进先出性。10、表达式a*(b+c)-d的后缀表达式是(abc+*d-)。【分析】将中缀表达式变为后缀表达式有一个技巧:将操作数依次写下来,再将算符插在它的两个操作数的后面。11、数组Q[n]用来表示一个循环队列,front为队头元素的前一个位置,rear为队尾元素的位置,计算队列中元素个数的公式为((rear-front+n)%n)。【分析】也可以是(rear-front)%n,但rear-front的结果可能是负整数,而对一个负整数求模,其结果在不同的编译器环境下可能会有所不同。12、稀疏矩阵一般压缩存储方法有两种,分别是(三元组顺序表)和(十字链表)。13、广义表((a),(((b),c)),(d))的长度是(3),深度是(4),表头是((a)),表尾是(((((b),c)),(d)))。14、已知广义表LS=(a,(b,c,d),e),用Head和Tail函数取出LS中原子b的运算是(Head(Head(Tail(LS))))。15、一棵二叉树的第i(i≥1)层最多有(2i-1)个结点;一棵有n(n>0)个结点的满二叉树共有((n+1)/2)个叶子结点和((n-1)/2)个非终端结点。【分析】设满二叉树中叶子结点的个数为n0,度为2的结点个数为n2,由于满二叉树中不存在度为1的结点,所以n=n0+n2;由二叉树的性质n0=n2+1,得n0=(n+1)/2,n2=(n-1)/2。16、深度为k的二叉树中,所含叶子的个数最多为(2k-1)。【分析】在满二叉树中叶子结点的个数达到最多17、已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点。则该树中有(12)个叶子结点。【分析】根据二叉树性质3的证明过程,有n0=n2+2n3+1(n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数)。18、某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,则其后序遍历序列是(CDBGFEA)。【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来19、已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为(O(n+e))。【分析】在无向图的邻接表中,顶点表有n个结点,边表有2e个结点,共有n+2e个结点,其空间复杂度为O(n+2e)=O(n+e)。20、对于含有n个顶点e条边的连通图,利用Prim算法求最小生成树的时间复杂度为(O(n2)),利用Kruskal算法求最小生成树的时间复杂度为(O(elog2e))。【分析】Prim算法采用邻接矩阵做存储结构,适合于求稠密图的最小生成树;Kruskal算法采用边集数组做存储结构,适合于求稀疏图的最小生成树。21、如果一个有向图不存在(回路),则该图的全部顶点可以排列成一个拓扑序列。22、在一个有向图中,若存在弧、、,则在其拓扑序列中,顶点vi,vj,vk的相对次序为(vi,vj,vk)。23、对于数列{25,30,8,5,1,27,24,10,20,21,9,28,7,13,15},假定每个结点的查找概率相同,若用顺序存储结构组织该数列,则查找一个数的