数据结构考试用

1 一个数组元素ai与（*(a+i)）的表示等价。 2.某算法仅含并列的程序段1和程序段2，程序段1的执行次数3n2，程序 段2的执行次数为0.01n3，则该算法的时间复杂度为（O(n3)）。 3设有一个n x n 的对称矩阵A，将其下三角部分按行存放在一个一维 数组B中，A00存放于B0中，那么第i行的对角元素Aii存放于B中 （i+3）*i/2）处。 4给定有n个元素的向量，建立一个有序单链表的时间复杂度是 （O（n2）。 5假定一个顺序存储的循环队列的队头和队尾指针分别为front和 rear，则判断对空的条件为（front= =rear）。 6如果一个第归函数过程中只有一个第归语句，而且它是过程体的最 后语句，则称这种第归为（尾第归），它很容易被改写为非第归过程。 7在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于 等于0而小于等于树的高度），最多具有（2i）个结点。 8利用3，6，8，12这四个值作为叶子结点的权，生成一棵霍夫曼树， 该树的带权路径长度为（55）。 9从具有n个结点的AVL树中搜索一个元素时，在等概率情况下进行成 功搜索的时间复杂度大致为（O（log2n）。 10对于具有e条边的无向图，它的邻接表中有（2e）个边结点。 11图的深度优先搜索类似于树的（先根）次序遍历。 12一个对象序列的排序码为46，79，56，38，40，84，采用快速排 序（以位于最左位置的对象为基础）所得到的第一次划分结果为 （40，38，46，79，56，84）。 1. 向顺序栈中压入新元素时，应当 （先移动栈顶指针，再存入元 素）。 2. 设有向图与n个顶点和e条边，采用邻接表作为其存储表示，在进行 拓扑排序时总的计算时间为 （O ( n+ e )）。 3. 一个对象序列的排序码为 46，79，56，38，40，84 , 采用快速排 序以位于最左位置的对象为基准而得到的第一次划分结果为 （40,38,46,56,79,84）。 4. 线性链表不具有的特点是 （随机访问）。 5. 设有一个10阶的对称矩阵1010，采用压缩存储方式按行将矩 阵中下三角部分的元素存入一维数组 中，00存入0中， 则85在 中 (41) 位置。 6. 设是一个森林，是由转换得到的二叉树，中有n个非叶结 点，则中右指针域为空的结点有（n+1）个。 7. 具有65个结点的完全二叉树的高度为（6）。（根的层次号为0） 8. 若待排序对象序列在排序前已按其排序码递增顺序排列，则采用 （直接插入排序）方法比较次数最少。 9. 在一个无向图中，所有顶点的度数之和等于所有边数的（2）倍。 10. 对有14个数据元素的有序表R14 进行折半搜索，搜索到R3的关键 码等于给定值，此时元素比较顺序依次为（R6, R2 ,R4, R3）。 1基本数据类型是计算机已经实现了的数据结构。 2二维数组是一种非线性结构，其中的每一个数组元素最多有两个个 直接前驱（或直接后继）。 3 链表对于数据元素的插入和删除不需要移动结点，只需要改变相应 结点的指针域的值。 4队列是一种限定在表的一端插入，在另一端删除的线性表，它又被 称为先进先出表。 5如果一个过程直接或间接地调用自己，则称这个过程是一个递归的 过程。 6假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度 为4。假定树根结点的层次为0。 7在一个堆的顺序存储中，若一个元素的下标为i（0i（n 1）/2），则它的左子女元素的下标为2i+1。 8根据n个元素从空树开始建立一棵二叉搜索树的渐进时间复杂度在最 好情况下为O（nlog2n）。 9N（n0）个顶点的无向图中顶点的度的最大值不超过n1。 10每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做二 路归并排序。 11快速排序在最坏情况下的空间复杂度为O（n）。 12若对长度n=10000的线性表进行二级索引存储，每级索引表中的索 引项是下一级20个表项的索引，则二级索引表的长度为25。 （错）1数据元素是数据的最小单位。 （错）2在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 （对）3链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满 的情况。 （错）4递归方法和递推方法本质上是一回事，例如求n！时既可用递 推的方法，也 可用递归的方法。 （错）5在一棵二叉树中，假定每个结点只有左子女，没有右子女， 对它分别进行前 序遍历和后序遍历，则具有相同的结果。 （错）6对具有n个结点的堆进行插入一个元素运算的时间复杂度为 O（n）。 （对）7在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率 越大的结点离树 根越近，则得到的是最优二叉树。 （对）8用边表示活动的网络（AOE网）的关键路径是指从源点到终点 的路径长度最 长的路径。 （错）9对一个有向图进行拓扑排序，一定可以将图中的所有顶点排 列成一个线性有 序的拓扑序列。 （错）10一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索 树是3阶B 树。 11. （）数据的基本单位是数据项。 12. （）带权的无向连通图的最小生成树是唯一的。 13. （）数组元素之间的关系，既不是线性的，也不是树形的。 14. （）对于有n个对象的待排序序列进行归并排序，所需平均时间为 ( nlog2n )。 15. （）用邻接矩阵法存储一个图所需的存储单元数目与图的边数有 关。 16. （）在霍夫曼编码中，当两个字符出现的频率相同时，其编码也 相同，对于这种情 况应当特殊处理。 17. （）线性表采用顺序存储表示时，必须占用一片连续的存储单 元。 18. （）由树转化成二叉树，其根的右子女指针总是空的。 19. （）直接选择排序是一种稳定的排序方法。 20. （）装载因子是散列表的一个重要参数，它反映了散列表的装满 程度。 1 对于一个nn的矩阵A的任意矩阵元素aij，按行存储时和按列 存储时的地址之差是多少。（设两种存储时的开始存储地址均为 LOC（0，0），每个元素所占存储单元数均为d） 地址之差为：（ij）*（n1）*d 2 已知一棵二叉树的中序和后序序列如下，求该二叉树的前序序列。 中序序列：c,b,d,e,a,g,i,h,j,f 后序序列：c,e,d,b,i,j,h,g,f,a 前序序列：a,b,c,d,e,f,g,h,i,j 3 假定一组记录为（40，28，16，56，50，32，30，63，44，38）， 按次序插入每个记录生成一棵AVL树，请回答插入时造成不平衡的 结点个数。 4 4 已知一个带权图的顶点集V和边集G分别为： V=0，1，2，3，4，5； E=（0，1）19，（0，2）21，（0，3）14，（1，2）16，（1，5）5， （2，3）26，（2，4）11，（3，4）18，（4，5）6；试根据克鲁斯卡 尔算法求出最小生成树，在下面填写依次得到的各条边。 1 （1，5）5，（4，5）6，（2，4）11，（0，4）14，（3，4）18 5 已知一个数据表为48，25，56，32，40，请写出进行快速排序的 过程中每次划分后数据表的变化。 6 （0）48 25 56 32 40 （1）40 25 32 48 56 （2）32 25 40 48 56 （3）25 32 40 48 56 1 指出算法的功能和时间复杂度，若n=20，则求出函数的返回值。 int fun(int n) int i=1,s=1; while(sdata=x; (1) ; rearlink=p；rear=p； ； bool DeLQUEUE(ListNode * if(HL= =NULL|itemHLdate) newptrlink=HL; HL=newptr; return; ListNode * cp,* ap; ap=HL; cp=HLlink; while(cp!=NULL) if(itemcpdata)break; ap= cp; cp=cplink; newptrlink=cp aplink=newptr; 算法功能：向表示集合的有序单链表HL中插入一个新元素，使得插入后 的集合单链表仍然保持有序。 1 设有一个线性表（e0，e1，en-2，en-1）已存放在一个一维数组 AarraySize中的前n个数组元素位置上。请编写一个函数将这个 线性表原地逆置，即将数组的前n个元素内容置换为（en-1，en-2， ，e1，e0）。函数的原型为： template void inverse(Type A,int n)； Template Void inverse(Type A,int n) Type tmp;/变量名任意 For (int i=0;I=(n-1)/2;i+)/或把ileft=BTright; BTright=pt; /对左子树进行同样处理 BtreeSwop(BTleft); /对右子树进行同样处理 BtreeSwop（BTright）； 11. 静态 12. 2 * I + J 13. 顺序 14. 对尾 对头 15. 3 16. 栈 17. （d,e,f） 18. 根 19. 2 20. 50 31.按行存储时与按列存储时，计算A i j 地址的公式分别为 LOC( i, j ) = LOC(0,0)+(i *n + j) * d 及 LOC ( i, j ) = LOC(0,0)+( j *n + i) * d 两者相减，得 LOC( i, j ) LOC ( i, j ) = LOC(0,0)+( i *n + j) * d LOC(0,0) ( j *n + i) * d =( i j) * n * d + (j i)*d 或 =(i j)*(n 1) *d 32.汉诺塔的递归处理过程如下表示： move 1 to 3 (2分) move 1 to 2 (2分) move 3 to 2 (2分) move 1 to 3 (2分) 33.后序序列：c, e, d, b, i, j, h, g, f, a 34.插入结果和调整类型为 402816565032 3063 无无右单 旋 无先右 后左 双旋 转 先左 后右 双旋 转 无左单 旋 调整类型： 插入数据： /每一个元素调整类型正确给1分。 35. 已知要存储的表项数为 n = 150，搜索成功的平均搜索长度为 ASLSUCC2，则有ASLSUCC = 1/2（1+1/1-a）2， 解得a 2/3。 又有a = n/m = 150/m 2/3, 则 m 225。 36. (1) 算法执行后得到的顺序表为38，47，94，64，73，83，51，0，表的 长度减为8。（4分） （2）该算法的功能是在顺序表中删除其值在给定值s与t之间（要求s小于 t）的所有元素。（2分） （3）此算法的渐进时间复杂度为O（n）（2分） 37. 1 1 / 3分 1 2 1 / 3分 1 3 3 1 / 2分 38.（1） return c1 + 1 / 3分 (2) NodeLevel (BT rightChild , X) / 3分 （3） return c2 + 1 / 2 分 39. 算法如下： int BTreeHeight (BinTreeNode * BT ) if (BT = = NULL ) return 1; / 对于空树，返回1并结束递归，1分 else int h1 = BTreeHeight(BT leftChild ); /计算左子树的高 度，2分 int h2 = BTreeHeight(BT rightChild ); /计算右子树的 高度，2分 if (h1h2) return h1 + 1 ; else retrun h2 + 1; /返回树的高度，1分 21. void unknoewn(BinTreeNode * T,int i) / 指针T是完全二叉树的根指针。 if (T ! = NULL) count Tdata ” ,” i endl; unknown(T leftChild , i+1 ); unknown(T rightChild , i+1 ); 主程序调试方式unknown (BT.root, 0 ) / 二叉树根结点的层次号为，其他结点的层次号等于其双亲的层 次号加一。 以前序顺序输出用二叉链表表示的二叉树各结点的数据和结点的层次号 22. 对下面的有向图从顶点开始进行遍历，试画出遍历得到的 生成森林和生成森林。（各分，共分） 答：遍历得到的生成森林和生成森林如下：（各分，共 分） C D I A H G F E B 23. 已知某二叉树的前序序列为，中序序列为 ，请给出二叉树的后序序列。（构造出二叉树 分，后序遍历分，共分） 24. E 后序序列为。 25. 将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初 始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树。 （分） 26. 设有个记录要存储到散列表中，并利用线性探查法解决冲 突，要求找到所需记录的平均比较次数不超过次。试问散列表需 要设计多大？（设是散列表的装转因子，则有 （）。（分） 已知要存储的记录数为 n =150，查找成功的平均查找长度为 ，则有a2,解得 a=2/3。又有a=n/m=150/m2/3,则m225。 V1 V3 V4 V6 V7 V2 V5 V8 五、综合算法题（每小题分，共分） 一个一维整数数组m中有n(n=m)个非空整数，它们相继存放于 数组的前端并已按非递减顺序排列，针对下列三种情况，分别编写相 应的函数。 27. 在数组 中插入一个新的整数x，并使得插入后仍保持非递减有 序。要求插入值相等的整数后面。（分） void InsertSort(int ,int m, int for( i =0; i n j- )A j+1= A j ; A i = x; n +; else cerr”数组已满，不能插入！” endl ; exit( 1 ); 27.将数组中所有整数原地逆置，即利用原数组空间中全部元素反转。 （分） void reverse ( int A ,int n) int mid = n/2,i,temp; for (i=0;imid;i+) temp = A i ;A i = An-i-1;An-i-1=temp; 28.删除数组中多余的值相等的整数（只保留第一次出现的那个整 数）。（分） void delDuplicate(int A ,int while (in-1) j = i+1; while (jn) if(Ai=Aj) for (k = j+1;kn;k+)A k-1=Ak; n-; else j+; i+; 29.设有一个带表