首页 数据结构期末复习题

数据结构期末复习题

举报
开通vip

数据结构期末复习题.-.优选-练习题:填空题1、元素项是数据的最小单位,数据元素是讨论数据构造时涉及的最小数据单位。2、设一棵完全二叉树具有100个结点,则此完全二叉树有49个度为2的结点。3、在用于表示有向图的邻接矩阵中,对第i列的元素进展累加,可得到第i个顶点的出度。4、一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有12个叶子的结点。n=n0+n1+n2+…+nm(1)又有除根结点外,树中其他结点都有双亲结点,且是唯一的(由树中的分支表示),所以,有双亲的结点数为:n-1=0*n0+1*n1+2...

数据结构期末复习题
.-.优选-练习 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 :填空题1、元素项是数据的最小单位,数据元素是讨论数据构造时涉及的最小数据单位。2、设一棵完全二叉树具有100个结点,则此完全二叉树有49个度为2的结点。3、在用于表示有向图的邻接矩阵中,对第i列的元素进展累加,可得到第i个顶点的出度。4、一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有12个叶子的结点。n=n0+n1+n2+…+nm(1)又有除根结点外,树中其他结点都有双亲结点,且是唯一的(由树中的分支表示),所以,有双亲的结点数为:n-1=0*n0+1*n1+2*n2+…+m*nm(2)联立(1)(2)方程组可得:叶子数为:n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm5、有一个长度为20的有序表采用二分查找方法进展查找,共有4个元素的查找长度为3。6、对于双向链表,在两个结点之间插入一个新结点需要修改的指针共4个。删除一个结点需要修改的指针共2个。7、广义表LS=(a,(b,c,d),e),它的深度是2,长度是3。8、循环队列的引入是为了抑制假溢出。9、表达式a*(b+c)-d/f的后缀表达式是abc+*df/-。10、数据构造中评价算法的两个重要指标是时间复杂度和空间复杂度。11、设r指向单链表的最后一个结点,要在最后一个结点之后插入s所指的结点,需执行的三条语句是r->ne*t=s;r=s;r->ne*t=null;12、设有一个空栈,栈顶指针为1000H(十六进制),现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后,输出序列是23,而栈顶指针值是1012_H。设栈为顺序栈,每个元素占4个字节。13、模式串P=‘abaabcac’的ne*t函数值序列为01122312。14、任意连通图的连通分量只有一个,即是自身。15、栈的特性是先进后出。16、串的长度是包含的元素个数。17、如果一个有向图中没有回路,则该图的全部顶点可能排成一个拓扑序列。18、在具有n个叶子结点的哈夫曼树中,分支结点总数为n-1。17619、在线性表的散列存储中,装填因子a又称为装填系数,假设用m表示散列表的长度,n表示待散列存储的元素的个数,则a等于n/m。20、排序的主要目的是为了以后对已排序的数据元素进展查找。21、对于一个具有n个结点的单链表,在的结点*p后插入一个新结点的时间复杂度为O(1),在给定值为*的结点后插入一个新结点的时间复杂度为O(n)。22、线性表L=〔a1,a2,…,an〕用数组表示,假定删除表中任一元素的概率一样,则删除一个元素平均需要移动元素的个数是n/2。23、两个栈共享空间时栈满的条件top1=top2-1。24、深度为H的完全二叉树至少有H个结点;至多有2^H-1个结点;H和结点总数N之间的关系是H=[log2n]+1。15025、在有序表A[1…20]中,按二分查找方法进展查找,查找长度为4的元素的下标从小到大依次是13681113161926、设查找表中有100个元素,如果用二分法查找方法查找数据元素*,则最多需要比拟7次就可以断定数据元素*是否在查找表中。26、数据构造被形式地定义为〔D,R〕,其中D和R的含义是〔D是数据元素的集合,R是数据关系的集合〕。数据的逻辑构造包括哪四种类型〔集合类型,线性构造,树形构造,图状构造〕。从存储构造的概念上讲,顺序表是线性表的〔顺序存储构造〕,链表是〔链式存储构造〕。27、根据初始关键字序列(17,25,3,39,12)建立的二叉排序树的高度为3。27、算法的五个重要特性有哪些。〔有穷性、确定性、可行性、输入、输出〕。抽象数据类型是指一个〔数学模型〕以及定义在该模型上的〔一组操作〕。28、设有一个n阶的下三角矩阵A,如果按照行的顺序将下三角矩阵中的元素〔包括对角上元素〕存放在n(n+1)个连续的存储单元中,则A[i][j]与A[0][0]之间有((i+1)*i/2+j个数据元素。栈的插入和删除只能在栈的栈顶进展,后进栈的元素必定先出栈,所以又把栈称为FILO;队列的插入和删除运算分别在队列的两端进展,先进队列的元素必定先出队列,所以又把队列称为FIFO表。设一棵完全二叉树的顺序存储构造中存储数据元素为ABCDEF,则该二叉树的前序遍历序列为ABDEF,中序遍历序列为DBEAFC,后序遍历序列为DEBFCA。如果以链栈为存储构造,则出栈操作时(必须判别栈是否空),与顺序栈相比,链栈有一个明显的优势是(通常不会出现栈满的情况)。循环队列采用数组data[1..n]来存储元素的值,并用front和rear分别作为其头尾指针。为区分队列的满和空,约定:队中能够存放的元素个数最大为n-l,也即至少有一个元素空间不用,则在任意时刻,至少可以知道一个空的元素的下标是〔front〕;入队时,可用语句〔rear=rear+1%n〕求出新元素在数组data中的下标。设一棵完全二叉树有128个结点,则该完全二叉树的深度为8,有65个叶子结点。33、栈的输入序列为1,2,3….,n,输出序列为a1,a2,…,an,a2=n的输出序列共有〔n-1〕种输出序列。设有向图G的存储构造用邻接矩阵A来表示,则A中第i行中所有非零元素个数之和等于顶点i的出度,第i列中所有非零元素个数之和等于顶点i的入度。35、将下三角矩阵A[l..8,1..8]的下三角局部逐行地存储到起始地址为1000的内存单元中,每个元素占4个单元,则A[7,5]的地址为〔1100〕。36、数组A[1..10,1..10]为对称矩阵,其中每个元素占5个单元。现将其下三角局部按行优先次序存储在起始地址为1000的连续的内存单元中,则元素A[5,6]对应的地址为〔1095〕。37、两个串相等的充要条件是,两个串的(长度)相等,且其所对应各个位置的〔字符〕也相等。39、在有n个结点的二叉链表中,值为非空的链域的个数为〔n-1〕。在有n个叶子结点的哈夫曼树中, 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 点数是〔2n-1〕。在树形构造中,根结点数只有〔1〕,其余每个结点有且仅有一个〔前驱〕元素结点。40、一棵二叉树L的高度为h,所有结点的度或为0,或为2,则这棵二叉树最少的结点数为(2h-1)。二叉树有50个叶子结点,则该二叉树的总结点数至少是〔99〕。将一棵有100个结点的完全二叉树从根这一层开场,每一层上从左到右依次对结点进展编号,根结点的编号为1,则编号为49的结点的左孩子编号为〔98〕。有64个结点的完全二叉树的深度为(7)。41、拓扑排序只能用于〔有向无环图〕。连通图是指图中任意两个顶点之间〔都连通的无向图〕。一个有n个顶点的无向连通图,它所包含的连通分量个数最多为(1)个。任何一个无向连通图的最小生成树〔有一棵或多棵〕。假设含有n个顶点的图形成一个环,则它有〔n〕棵生成树。42、求图的最小生成树有两种算法,〔普利姆〕算法适合于求稠密图的最小生成树,〔克鲁斯卡尔〕算法适合于求稀疏图的最小生成树。设图G用邻接表存储,则拓扑排序的时间复杂度为(O(n+e))。44、从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进展比拟,将其放入已排序序列的正确位置上的方法,称为(插入排序)。对于关键字序列(12,13,11,18,60,15,7,18,25,100),用筛选法建堆,则开场结点的键值必须为〔60〕。33、typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(t==0)return(0);elsewhile(t!=0)if(t->key==k)t->lchild=t->rchild=0;elseif(t->key>k)t=t->lchild;elset=t->lchild;;}下面程序段的功能是实现冒泡排序算法,请在下划线处填上正确的语句。voidbubble(intr[n])272{for(i=1;i<=n-1;i++){for(e*change=0,j=0;jr[j+1]){temp=r[j+1];__r[j]=r[j+1]_;r[j]=temp;e*change=1;}if(e*change==0)return;}}下面程序段的功能是实现二分查找算法,请在下划线处填上正确的语句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key,<2,4>,<4,5>,<1,3>,<3,2>,<3,5>},则给出该图的一种拓扑排序序列13245。38、设一组初始记录关键字序列为(49,38,65,97,76,13,27,50),则以d=4为增量的一趟希尔排序完毕后的结果为4913275076386597。39、设二叉排序树的高度为h,则在该树中查找关键字key最多需要比拟h次.二、选择题1、从逻辑上可以把数据构造分为〔C〕两大类。A.动态构造、静态构造B.顺序构造、链式构造C.线性构造、非线性构造D.初等构造、构造型构造2、假设长度为n的线性表采用顺序存储构造,在其第i个位置插入一个新元素的算法的时间复杂度为〔C〕(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)3、假设一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pN,假设pN是n,则pi是(A)。A.iB.n-iC.n-i+1D.不确定4、广义表L=〔〔*,y,z〕,a,〔u,t,w〕〕,从L表中取出原子项t的运算是〔D〕。A.head〔tail〔tail〔L〕〕〕B.tail〔head〔head〔tail〔L〕〕〕〕C.head〔tail〔head〔tail〔L〕〕〕〕D.head〔tail(head〔tail〔tail〔L〕〕〕)〕5、以下陈述中正确的选项是〔D〕。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树,并且有左右之分6、设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是〔A〕。173A.m-nB.m-n-1C.n+1D.条件缺乏,无法确定7、.算术表达式a+b*〔c+d/e〕转为后缀表达式后为〔B〕。A.ab+cde/*B.abcde/+*+C.abcde/*++D.abcde*/++8、关键路径是事件结点网络中〔A〕。A.从源点到终点的最长路径B.从源点到终点的最短路径C.最长回路D.最短回路9、具有12个关键字的有序表,二分查找的平均查找长度〔C〕。236A.2.5B.4C.3.1D.510、AVL树是一种平衡的二叉排序树,树中任一结点的〔B〕245A.左、右子树的高度均一样B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度11、线性表采用存储时,其地址〔D〕。A.必须是连续的B.局部地址必须是连续的C.一定是不连续的D.连续与否均可以12、栈和队列是两种特殊的线性表,只能在它们的〔B〕处添加或删除结点。A.中间点B.端点C.随机存取点D.结点13、输入序列为ABC,可以变为BAC时,经过的栈操作为〔C〕。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop14、下面〔C〕不是算法所具有的特性。A.有穷性B.确切性C.高效性D.可行性15、下面关于串的的表达中,〔B〕是不正确的.A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储,也可以采用链式存储16、数组A[6][7]的每个元素占五个字节,将其按行优先次序存储在起始地址为1000的内存单元中,则元素A[3][5]的地址是(A)。117A.1130B.1180C.1205D.121017、对于一个具有n个顶点的无向图,假设采用邻接矩阵存储,则该矩阵的大小是〔D〕。195A.nB.(n-1)2C.n-1D.n218、假设广义表A满足Head(A)=Tail(A),则A为〔B〕。A.〔〕B.〔〔〕〕C.〔〔〕,〔〕〕D.〔〔〕,〔〕,〔〕〕19、堆的形状是一棵(C)。A.二叉排序树B.满二叉树C.完全二叉树D.判定树20、假设要在单链表中的结点*p之后插入一个结点*s,则应执行的语句是(A)A.s->ne*t=p->ne*t;p->ne*t=s;B.p->ne*t=s;s->ne*t=p->ne*t;C.p->ne*t=s->ne*t;s->ne*t=p;D.s->ne*t=p;p->ne*t=s->ne*t;21、链表不具有的特点是〔B〕。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比22、一个栈的输入序列为12345,则以下序列中不可能是栈的输出序列的是〔B〕。A.23415B.54132C.23145D.1543223、递归过程或函数调用时,处理参数及返回地址,要用一种称为〔C〕的数据构造。A.队列B.多维数组C.栈D.线性表24、设给定权值总数有n个,其哈夫曼树的结点总数为(D)。A.不确定B.2nC.2n+1D.2n-125、假设需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是〔C〕。 课件 超市陈列培训课件免费下载搭石ppt课件免费下载公安保密教育课件下载病媒生物防治课件 可下载高中数学必修四课件打包下载 106 107A.快速排序B.堆排序C.归并排序D.直接插入排序26、设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置.脚注(10)表示用10进制表示。(C)A.688B.678C.692D.69627、假设有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进展二分查找,则查找A[3]的比拟序列的下标依次为(D)A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,328、设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进展一趟快速排序的结果为〔C〕。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,829、设指针变量p指向单链表中结点A,假设删除单链表中结点A,则需要修改指针的操作序列为〔A〕。Aq=p->ne*t;p->data=q->data;p->ne*t=q->ne*t;free(q);Bq=p->ne*t;q->data=p->data;p->ne*t=q->ne*t;free(q);Cq=p->ne*t;p->ne*t=q->ne*t;free(q);Dq=p->ne*t;p->data=q->data;free(q);30、设*二叉树中度数为0的结点数为N0,度数为1的结点数为Nl,度数为2的结点数为N2,则以下等式成立的是〔C〕。A.N0=N1+1B.N0=Nl+N2C.N0=N2+1D.N0=2N1+l31、设一棵m叉树中度数为0的结点数为N0,度数为1的结点数为Nl,……,度数为m的结点数为Nm,则N0=〔B〕。A.Nl+N2+……+NmB.l+N2+2N3+3N4+……+(m-1)NmC.N2+2N3+3N4+……+(m-1)NmD.2Nl+3N2+……+(m+1)Nm32、设无向图G中的边的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发进展深度优先遍历可以得到的一种顶点序列为〔A〕。A.aedfcbB.acfebdC.aebcfdD.aedfbc26、*二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是〔BB〕。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子28、下面的说法中正确的选项是〔B〕。(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。(2)按二叉树定义,具有三个节点的二叉树共有6种。A.(1),(2)B.(1)C.(2)D.(1),(2)都错29、树有先根遍历和后根遍历,树可以转化为对应的二叉树。下面的说法正确的选项是〔B〕。A.树的后根遍历与其对应的二叉树的后根遍历一样B.树的后根遍历与其对应的二叉树的中根遍历一样C.树的先根遍历与其对应的二叉树的中根遍历一样D.以上都不对30、.以以下图的邻接表中,从顶点V1出发采用深度优先搜索法遍历该图,则可能的顶点序列是〔D〕。31、以下说法不正确的选项是〔D〕。A.无向图中的极**通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索32、设哈希表长为14,哈希函数H(key)=key%11,表中已有数据的关键字为15,38,61,84,四个,现将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是〔DD〕。A.8B.3C.5D.934、二维数组A的每个元素是由6个字符组成的串,其行下标i=0,l,…,8,列下标为j=1,2.….10。设每个字符占一个字节,假设按行先存储,元素A[8,5]的起始地址与A按列存储时起始地址一样的元素是〔B〕。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]35、.在n个结点且为完全二叉树的二叉排序树中查找一个键值,其平均比拟次数的数量级为〔B〕。A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)37、关键路径是事件结点网络中〔AA〕。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路38、将两个各有n个元素的有序表归并成一个有序表,其最少的比拟次数是〔AA〕。A.nB.2n-1C.2nD.n-141、有向图G用邻接矩阵A存储,则顶点i的入度等于A中〔BB〕。A.第i行1的元素之和B.第i列1的元素之和C.第i行0的元素个数D.第i列0的元素个数42、用*种排序方法对关键字序列〔25,84,21,47,15,27,68,35,20〕进展排序时,序列的变化情况如下:20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84则所采用的排序方法是〔DD〕A.选择排序B.希尔排序C.归并排序D.快速排序43、设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序完毕后的结果为(AA)。(A)10,15,14,18,20,36,40,21(B)10,15,14,18,20,40,36,21(C)10,15,14,20,18,40,36,2l(D)15,10,14,18,20,36,40,2144、设有n个关键字具有一样的Hash函数值,则用线性探测法把这n个关键字映射到HASH表中需要做〔D〕次线性探测。A.n2B.n(n+1)C.n(n+1)/2D.n(n-1)/2三、判断题1.如果两个串含有一样的字符,则这两个串相等。〔 *〕2.数组可以看成线性构造的一种推广,因此可以对它进展插入、删除等运算。〔* 〕3.二叉树是度为2的树。〔*〕4.在顺序表中取出第i个元素所花费的时间与i成正比。〔 *〕5.在栈满情况下不能作进栈运算,否则产生"上溢〞。 (v 〕6.图G的生成树是该图的一个极小连通子图。〔 v〕7.所谓数据的逻辑构造指的是数据之间的逻辑关系。〔*〕数据项8.二叉排序树的查找和折半查找的时间性能一样。〔*〕9.在执行*个排序算法过程中,出现了排序码朝着最终排序序列位置相反方向移动,则该算法是不稳定的。〔 *〕10.一个有向图的邻接表和逆邻接表中表结点的个数一定相等。〔v 〕11、双向链表中至多只有一个结点的后继指针为空。〔v〕12、在循环队列中,front指向队列中第一个元素的前一位置,rear指向实际的队尾元素,队列为满的条件是front=rear。〔*〕13、对链表进展插入和删除操作时,不必移动结点。〔v〕14、栈可以作为实现程序设计语言过程调用时的一种数据构造。〔v〕15、在一个有向图的拓朴序列中,假设顶点a在顶点b之前,则图中必有一条弧(*)。16、对有向图G,如果从任一顶点出发进展一次深度优先或广度优先搜索就能访问每个顶点,则该图一定是完全图。(*)17、"顺序查找法〞是指在顺序表上进展查找的方法。〔*〕18、向二叉排序树插入一个新结点时,新结点一定成为二叉排序树的一个叶子结点。〔v〕19、二分查找要求序列顺序存储且关键字序列有序。〔v〕20、二路归并时,被归并的两个子序列中的关键字个数一定要相等。〔*〕21.调用一次深度优先遍历可以访问到图中的所有顶点。〔*〕21.分块查找的平均查找长度不仅与索引表的长度有关,而且与块的长度有关。〔v〕22.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。〔v〕23.满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。〔v〕24.设一棵二叉树的先序序列和后序序列,则能够唯一确定出该二叉树的形状。〔*〕25.层次遍历初始堆可以得到一个有序的序列。〔*〕26.设一棵树T可以转化成二叉树BT,则二叉树BT中一定没有右子树。〔v〕27.线性表的顺序存储构造比链式存储构造更好。〔*〕28.中序遍历二叉排序树可以得到一个有序的序列。〔v〕29.快速排序是排序算法中平均性能最好的一种排序。〔v〕30.不管是入队列操作还是入栈操作,在顺序存储构造上都需要考虑"溢出〞情况。〔v〕31.当向二叉排序树中插入一个结点,则该结点一定成为叶子结点。〔v〕32.设*堆中有n个结点,则在该堆中插入一个新结点的时间复杂度为O(log2n)。〔v〕33.完全二叉树中的叶子结点只可能在最后两层中出现。〔v〕34.哈夫曼树中没有度数为1的结点。〔v〕35.对连通图进展深度优先遍历可以访问到该图中的所有顶点。〔v〕36.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。〔v〕37.由树转化成二叉树,该二叉树的右子树不一定为空。〔*〕38.线性表中的所有元素都有一个前驱元素和后继元素。〔*〕39.带权无向图的最小生成树是唯一的。〔*〕四、应用题1、一棵二叉树的中根序列和后根序列分别为CBEDAFIGH及CEDBIFHGA,请画出这棵二叉树,并给出其先序序列。ABCDEGFIH1、一棵二叉树的先根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF,请画出这棵二叉树,并给出其后序序列。GHDEBJIFCA2、将以下由三棵树组成的森林转换为二叉树。〔只要求给出转换结果〕3、无向图如下所示:〔1〕.给出从V1开场的广度优先搜索序列;〔2〕.画出它的邻接表;〔3〕.画出从V1开场深度优先搜索生成树。4.假定用于通讯的电文仅有8个字母C1,C2,…,C8组成,各个字母在电文中出现的频率分别为5,15,3,6,22,11,30,8,请先构建一棵哈夫曼树,计算其WPL值,并为这8个字母设计相应的哈夫曼编码4、假定用于通讯的电文仅有8个字母C1,C2,…,C8组成,各个字母在电文中出现的频率分别为5,25,3,6,10,11,36,4,请先构建一棵哈夫曼树,计算其WPL值,并为这8个字母设计相应的哈夫曼编码。5、一表为〔Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec〕,按表中顺序依次插入初始为空的二叉排序树,要求:(1)画出建立的二叉排序树〔值的大小以字母顺序为准〕。(2)对该二叉排序树作中序遍历,试写出遍历序列。(3)求出在等概率情况下查找成功的平均查找长度。6、一个图的顶点集V和边集G分别为:V={0,1,2,3,4,5,6,7};E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20};按照普里姆算法从顶点0出发得到最小生成树,试写出在最小生成树中依次得到的各条边。(0,1),(0,3),(0,2),(1,5),(3,6),(6,4),(5,7)。7、设一哈希表长为13,采用线性探测法解决冲突,哈希函数H(key)=key%13,〔1〕画出在空表中依次插入关键字25,20,34,15,21,32,29,82,57后的哈希表。〔2〕求在等概率情况下,查找成功和查找不成功的平均查找长度。7、散列函数为H(K)=Kmod11,健值序列为{47,7,29,11,16,92,22,8,3}哈希表长为11,采用线性探测法处理冲突,试构造闭散列表,并计算查找成功和不成功的平均查找长度。8、待排序的序列为〔403,187,312,61,818,170,857,272,633,442〕,试完成以下各题。(1)根据以上序列建立一个堆〔画出第一步和最后堆的结果图〕,希望先输出最小值。(2)输出最小值后,如何得到次小值。〔并画出相应结果图〕。8、待排序的序列为〔503,87,512,61,908,170,897,275,653,462〕,试完成以下各题。(1)根据以上序列建立一个堆〔画出第一步和最后堆的结果图〕,希望先输出最小值。(2)输出最小值后,如何得到次小值。〔并画出相应结果图〕。9、以以下图表示一个地区的交通网,顶点表示城市,边表示连结城市间的公路,边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路,画出一个 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。v2v4v1v5v3v61621111433619186510、图G=〔V,E〕,其中V={v1,v2,v3,v4,v5},E={,,,,),};画出这个图的图形并写出所有的拓扑序列。11、设有关键码序列{19,32,40,13,30,24,35},请给出平衡二叉树的构造过程〔只需要给出不平衡时到平衡的过程即可〕。11、设有关键码序列{20,35,40,15,30,25,38},请给出平衡二叉树的构造过程〔只需要给出不平衡时到平衡的过程即可〕。12、散列函数为H(K)=Kmod13,健值序列为12,31,15,54,04,78,22,29,34,54,29,47,采用拉链法处理冲突,试构造开散列表,并计算查找成功的平均查找长度。12、散列函数为H(K)=Kmod13,健值序列为13,41,15,44,06,68,12,25,38,64,19,49,采用拉链法处理冲突,试构造开散列表,并计算查找成功的平均查找长度。13、对于以下一组关键字36,48,25,55,80,17,11,72,试写出快速排序每一趟的排序结果。13、对于以下一组关键字46,58,15,45,90,18,10,62,试写出快速排序每一趟的排序结果。10,15,18,45,46,58,62,9014、对下面的关键字集〔30,14,25,43,35,27,64,49〕,假设查找表的装填因子为0.8,采用线性探测再散列解决冲突:〔1〕设计哈希函数;〔2〕画出哈希表;〔3〕求查找成功的平均查找长度。14、在如下数组A中存储了一个线性表,表头指针为A[0].ne*t,试写出该线性表。A01234567data605078903440ne*t3572041线性表为:〔78,50,40,60,34,90〕15、按顺序输入以下顶点对:(V1,V2)、(V1,V6)、(V2,V6)、(V1,V4)、(V6,V4)、(V1,V3)、(V3,V4)、(V6,V5)、(V4,V5)、(V1,V5)、(V3,V5)。〔顶点序列为:V1,V2,V3,V4,V5,V6〕〔1〕画出相应的邻接表。〔2〕写出在邻接表上,从顶点3开场〔表下标从0开场〕的DFS序列和DFS生成树五、算法与程序设计1、阅读算法完成题目要求:〔1〕说出以下算法的功能。templatestructBinnode{Tdata;Binnode*prior,*ne*t;};boolUnknown(Binnode*first){Binnode*p,*q;p=first->ne*t;q=first->prior;while(p!=q&&p->prior!=q)if(p->data==q->data){p=p->ne*t;q=q->prior;}elsereturn0;return1;}//判断双链表的对称性算法功能:〔2〕根据以下算法和输入的数据画出生成的链表形式。templateLinkList::LinkList(intn){first=newNode;Node*s;T*;first->ne*t=NULL;;for(inti=0;i>*;s=newNode;s->data=*;s->ne*t=first->ne*t;first->ne*t=s;}}输入数据为:123456输出结果为:〔3〕说出以下算法的功能,它是采用什么构造实现的。templatevoidBiTree::Unknown(BiNode*root){constintMa*Size=100;intfront=0;intrear=0;BiNode*Q[Ma*Size];BiNode*q;if(root==NULL)return;else{Q[rear++]=root;while(front!=rear){q=Q[front++];cout<data<<"";if(q->lchild!=NULL)Q[rear++]=q->lchild;if(q->rchild!=NULL)Q[rear++]=q->rchild;}}}算法功能:二叉树的层序遍历对列〔4〕阅读以下算法求出调用该算法后输出结果。voidAE(Stack&S){InitStack(S);Push(S,30);Push(S,40);Push(S,50);int*=Pop(S)+2*Pop(S);Push(S,*);inti,a[4]={5,8,12,15};for(i=0;i<4;i++)Push(S,a[i]);while(!StackEmpty(S))cout<ne*t;while(p&&p->ne*t->data!=*){q=p;p=p->ne*t;}if(p){q->ne*t=p->ne*t;free(p);}}算法的功能:删除单链表L中值为*的结点的直接前驱结点2、程序设计(1)设有一单链表L,结点构造为data|ne*t,编写算法判断该单链表L中的元素是否成等差关系,即:设各元素值次为a1,a2,a3,…,an,判断ai+1-ai=ai-ai-1是否成立。假设是返回1,否则返回0。函数说明为:intdengcha(Node*L);(2)写出二分查找的非递归算法。(要求统计查找过程中元素的比拟次数)函数说明为:intbinsearch(intr[],intn,intk);(3)设单链表以非递减有序排列,设计算法实现在单链表中删除值一样的多余结点。函数说明为:VoidLinklist::purge(Node*first);〔3〕templateVoidpurge(Node*first){Node*p,*q;P=first->ne*t;While(p->ne*t)If(p->data==p->ne*t->data){q=p->ne*t;p->ne*t=q->ne*t;deleteq;}Elsep=p->ne*t;}(4)写出图在邻接表存储构造下广度优先的遍历算法。函数说明为:template函数说明为:voidALGraph::BFSTraverse(intv);〔5〕编写计算二叉树最大宽度的算法〔二叉树的最大宽度是指二叉树所有层中结点个数的最大值〕。〔6〕设计有向图〔AOV网〕在邻接表存储构造下的拓扑排序算法。template函数说明为:voidALGraph::TopSort();〔6〕假设哈希函数为H〔key〕,编写用链地址法解决冲突的哈希表的插入和删除算法。voidF2(HashTable&H,keytypeKey){//哈希表插入,用链地址法解决冲突i=H(Key);;//获取哈希地址if(H[i]==Null){s=(Linklist)malloc(sizeof(Lnode));s→data=key;s→ne*t=H[i];H[i]=s;}//ifelse{p=H[i];//查找while(p&&p→data!=key)p=p→ne*t;if(p→data==key)e*it(1);else{s=(Linklist)malloc(sizeof(Lnode));//产生新结点,插入表头s→ne*t=H[i];H[i]=s;}//else}//else}//F2voidDelete_HS(HashTable&H,KeyTypekey){//哈希表删除,用链地址法解决冲突i=H(key);//获得哈希地址if(H[i]==Null)e*it(1);p=H[i];q=p;//p为工作指针,q为p前趋while(p&&p→data!=key){//查找q=p;p=p→ne*t;}//whileif(!p)e*it(1);if(q==H[i]){//key为第一结点H[i]p→ne*t;free(p);}//ifelse{q→ne*t=p→ne*t;free(p);}//else}//Delete_HS〔7〕设计在链式存储构造上交换二叉树中所有结点左右子树的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}
本文档为【数据结构期末复习题】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
个人认证用户
dykcs64
从事建筑工程对接,工程图纸设计施工管理方面的经验
格式:doc
大小:153KB
软件:Word
页数:24
分类:教育学
上传时间:2022-07-10
浏览量:0