1.一个算法应该是(B)。A.程序
B.问题求解步骤的描述
C.要满足五个基本特性
D.A和C
C是特性不是定义
22.某算法的时间复杂度为O(n)，表明该算法(C)。
A.问题规模是nB.执行时间等于nC.执行时间与n成正比3.设n表示问题规模，下面程序片段的时间复杂度是()。
x=2;while(x O（log2（n/2））时间复杂度不要常数4.下面程序段的时间复杂度是(count=0;for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++; T1（n）＝O（log2（n））T2（n）＝O（n） T＝T1×T2＝O（nlog2（n）） ). 222 D.问题规模与n成正比 2 第二章线性表 1.设线性表有n个元素，严格来说，以下操作中，哪些操作在顺序表上实现要比在链表上实现的效率高。ABA.输出第i个数据元素的值 B.交换第两个指定位置的数据元素 C.输出这n个数据元素 n-i个元2.在一个长度为n的顺序表中删除第i(1<=i<=n)个元素时，需要向前移动素。 3.设计算法从顺序表中删除具有最小值的元素（假设最小值唯一）并由函数返回被删除的元素值，空出的位置由最后一个元素填补，若顺序表为空则显示错误信息并退出运行。要求：(1)给出算法的设计思想；(2)根据设计思想，采用C语言描述算法，关键之处给出 注释；(3)说明你设计的算法时间复杂度。 4.给定一个带头结点的单链表L，设head为头指针，结点的结构为（data,next）,data为整型元素，next为指针。设计算法，将L逆置，要求算法的空间复杂度为O(1)。 要求：(1)给出算法的设计思想；(2)根据设计思想，采用C语言描述算法，关键之处给出注释；(3)说明你设计的算法时间复杂度。 第三章栈和队列 1.假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并且已知栈未满，则元素x入栈需要执行的的操作为 a[++top]=x。2.向一个栈顶指针为top的链栈中插入一个结点x，则执行的操作x->next=top;top=x;。3.设元素abcdefg依次进入栈S,得到的出栈序列为bdcfeag，则栈的容量至少是 3。4.有5个元素，依次按照A,B,C,D,E的次序入栈，则第一次出栈为C第二次出栈为D的出栈序列有3种，它们分别是CDBAECDEBACDBEA。 5.循环队列存储在数组A[0…n]中，rear表示队尾，front表示队首，则入队列的操作为rear=(rear+1)mode(n+1)。6.在一个链队列中，头指针为front,尾指针为rear,将结点x插入队列的操作是rear->next=x;rear=x;。 第四章数组和广义表 1.设有n*n的对称矩阵A,将其下三角部分按行优先存放在一维数组B中，A[0][0]存放在B[0]中，那么A[i][j]在B中的存放位置是 B[i*(i-1)/2+j-1]。 2.将一个A[1…100][1…100]的三对角矩阵，按行优先存放在一维数组B中，则数组B的大小至少应该为193。3.将n阶上三角矩阵A按照列优先的方式存放在一维数组B中，则存放在B[k]中的非零元素A[i][j]的下标i,j与k的对应关系是 k=j*(j-1)/2-i-1。 298。假设A[1][1]存放在B[0]中，则A[65][66]在B中的存放位置是 4.广义表是否能够使用顺序存储结构？为什么？不能，广义表的数据元素可以具有不同的结构 第五章树和二叉树 1.已知一棵度为4的树中，度为0,1,2,3的结点个数分别为14,4,3,2，求该树的节点总数n和度为4的节点个数m,并给出推导过程。 14*0+4*1+3*2+2*3+4*m+1=14+4+3+2+m解的m=2n=14*0+4*1+3*2+2*3+4*m+1=252.具有10个叶子结点的二叉树中有9个度为2的结点。3.一个具有1025个结点的二叉树的高度为 [11,1025]。 8。4.设二叉树只有度为0和度为2的结点，结点总数为15个，则该二叉树的高度最大是5.一棵完全二叉树有1001个结点，其叶节点个数为 501。 6.对于一棵满二叉树，共有n个结点和m个叶子结点，高度为h，则你，n,m,h之间的关系是 。7.已知某二叉树的先序序列为ABDEHCFIMGJKL，中序序列为DBHEAIMFCGKLJ，请画出这棵二叉树，然后将其转化成树并画出这棵树的双亲表示、孩子兄弟表示，最后在把这棵二叉树转成森林。 8.假设二叉树采用二叉链表作为存储结构，设计一个算法求二叉树的高度。 9.假设A,B,C,D,E,F,G,H八个字符在一段报文中出现的次数为分别为{15,20,70,31,66,89,97,1000},请给出每个字符的最佳编码方式。 第六章图 1.一个有28条边的非连通无向图至少有个9顶点。2.对于一个有n个顶点的图：如果是连通无向图，其边的个数至少是n-1；如果是强连通图，其边的个数最少是 n。棵生成树。3.如果具有n个顶点的图是一个环，则它有 4.假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点相关的所有边的时间复杂度为 。5.一个图的邻接表表示如下图所示，画出该图，并给出其邻接矩阵表示，最后给出从顶点1开始的广度优先遍历和深度优先遍历序列。 6.分别用Prim算法和Kruskal算法求出下图所示的带权连通无向图的最小生成树，要求写出具体求解过程。 7.使用Dijstra算法求解下图中从顶点1到其他顶点的最短路径，写出具体求解过程。 8.已知有6个顶点(编号0-5)的有向带权图G，其邻接矩阵A的上三角矩阵，按照行优先保存在如下的一维数组中。 (1)写出图G的邻接矩阵A;(2)画出有向带权图G; (3)求图G的关键路径，并计算该关键路径的长度。9.求出下图的所有拓扑排序序列。 第七章查找 1.已知一个长度为16的顺序表L,其元素按关键字有序排列，若用折半查找一个在L中不存在的元素，则关键字的比较次数最多是 5次。2.已知一个有序表{13,18,24,35,47,50,62,83,90,115,134}，当二分查找值为90的元素时，查找成功的比较次数为 2次。 3.设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908。 (1)试画出对其进行折半查找的判定树。 (2)若查找275和684，分别将依次和哪些元素进行比较？(3)计算查找成功和查找不成功两种情况下的平均查找长度。4.写出折半查找的递归算法和非递归算法。 5.按照序列{40,72,38,35,67,51,90,8,55,21}建立一棵二叉排序树，画出该树，并求出在等概率情况下，查找成功的平均查找长度。 6.依次把结点{34,23,15,98,115,28,107}插入到初始状态为空的平衡二叉排序树中，使得每次插入后保持该树仍是平衡二叉树。请以此画出每次插入后所形成的平衡二叉排序树。7.使用散列函数H(key)=key%11,把一个整数值转换成散列下标，现要把数据{1,13,12,34,38,33,27,22}依次插入到散列表中。1）使用线性探测法来构造散列表。2）使用拉链法构造散列表。 试针对两种情况，分别确定查找成功所需的平均查找长度，以及查找不成功所需的平均查找长度。 8.将关键字序列{7,8,30,11,18,9,14}散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(key*3)%7,处理冲突采用线性探测再散列法，要求 装填因子为0.7. 1）请画出所构造的散列表；。， 2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。 第八章内部排序 1.给出关键字序列{4,5,1,2,6,3}的直接插入排序过程。451263451263145263124563124563123456 2.给出关键字序列{50,26,38,80,70,90,8,30,40,20}的希尔排序过程。取增量序列为d={5,3,1},排序结果为从小到大。50830402090263880702683040208050389070826302040503880709082620304038507080908202630384050708090 3.若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一而得到的第二趟排序后的结果，则该排序算法只能是(B).A.冒泡排序 B.插入排序 C.选择排序 D.2路归并排序 A先把最小翻上来排除B C选择最极端数字先排排除DP268 4.一组记录的关键码为{46,79,56,38,40,84}，则利用快速排序的方法，以第一个记录为基准，从小到大得到的一次划分结果为（C）。A.{38,40,46,56,79,84}C.{40,38,46,56,79,84} B.{40,38,46,79,56,84}D.{40,38,46,84,56,79} 5.写出对关键字序列为{23,17,72,60,25,8,68,71,52}进行堆排序的过程。使用大根堆，从小到大排序。 6.构建n个记录的初始堆，其时间复杂度为(O（nlog2（n））)，对n个记录进行堆排序，最坏情况下其时间复杂度为（ O（nlog2（n）））。 7.已知序列{503,87,512,61,908,170,897,275,653,462}，采用二路归并排序法对该序列左升序排序时需要几趟排序？并给出每一趟的结果。8.编程实现冒泡排序。 因篇幅问题不能全部显示，请点此查看更多更全内容