北邮算法与数据结构复习资料

（2分）为解决计算机和打印机速度不匹配问题，通常设置一个打印数据缓冲区，主机将 要输出的数据依次写入缓冲区, 而打印机依次从该缓冲区中取出数据. 该缓冲区的逻辑 结构应该是?A. 栈 B. 队列 C. 树 D. 图 （2分）设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S.若每个元素出 栈后立即进入队列Q且7个元素出对的顺序是bdcfeag,则栈S的容量至少是？A . 1 B: 2 C. 3 D, 45C氛给宦二义弱紬陶所示.设N代谀二乳树的抿，匚代畫提齬点的左子树才R代衷朋结点的右咱脚.腐划巾底同給点序1,3. I. 7. 5. 6.4. ILI臥期山山冗址IX RNLA. LkNId, NRL4. F列.X耳庁陇比備扯T：断乂树定賃們址 （2 分）已知完全二叉树的第六层（根节点视为第一次）有8 个节点. 则此完全二叉树节点个 数最多为A. 39 B. 52 C. 111 D. 119 将森林转换为对应的二叉树. 若在二叉树中节点 u 是节点 v 的父节点的父节点. 则在 原来的森林中, u 与 v 的可能关系为甲） 父子关系.乙）兄弟关系丙） u 的父节点与 v 的父节点是兄弟关系A. 只有 甲B. 甲 和 乙C. 甲 和 丙 D 甲乙丙 下面关于无向连通图特性的叙述中, 正确的是:甲） 所有定点度数之和为偶数.乙） 边数大于顶点个数减 1丙） 至少有一个顶点的度为 1.A.只有甲B.只有乙C.甲和乙D.甲和丙参考答案:1) B2)C 3)D 4)B 5)C 6)B 7) A 下面叙述中，不符合m阶B树定义要求的是：A.根节点最多有m棵子树B.所有叶节点都在同一层上.C.各节点内关键字均升序或降序排列D.叶节点之间通过指针链接. 已知关键字序列 5, 8, 12, 19, 28, 20, 15, 22 为极小堆（小根堆, 最小堆）. 添加关键字 3 调整后得到的极小堆是：A. 3,5,12,8,28,20,15,22,19B. 3,5,12,19,20,15,22,8,28C. 3,8,12,5,20,15,22,28,19D. 3,12,5,8,28,20,15,22,19 若数据元素序列 11,12,13,7,8,9,23,4,5 是采用下列排序算法之一得到的第二趟排序后的 结果, 则该排序算法只能是：A.冒泡排序 B.插入排序C.选择排序D.二路归并排序 如元素 abcdef 依次进栈, 允许进栈出栈操作交替进行 , 但不允许连续三次退栈. 则不 可能得到的出栈序列为：A. dcebfaB. cbdaefC.bcaefdD. afedcb 某队列允许在其两端进行入队操作 , 但仅允许在一端进行出队操作. 若元素 abcde 依 次入队后再进行出队操作, 则不可能的出队序列为A. bacdeB. dbaceC.dbcaeD. ecbad参考答案：1)D 2)A 3)B 4) D 5)CLh 24； 90A. 13. 4$匚.24. 534.在右图席示前平衡二與柯中.插人芟證字 朝府希到一棵新平術二更树.在新乎衡二叉树中, -X ?科所在堆点的古、右子結点L| 保存的关楓 字井别是.5.在一棵度为4的树T中.若有囲个度为4術结点，H)个度为3的結点 1个度为Z曲 结点.R6度为L的结点，财厠丁的叶节点勺敬 A, 4B-號C 113br 122乩 对测*1)6权值均不柑同的字符构造喑夫塑拥。下列关丁邁哈先躍剧的載迷中错误 的皑，A.该嗣一龙是一棵盘全二更轉i树中一定没着度苗j的蜻点c.欄中两个权值嚴小的葫点一运足兄闌结点m 尿申佟一菲叶诙点时敬值隹不腋下一层任貉萸的罠值CBA7-若无向團G屮同中含7个顶点要擁证图G在任何清况下都是连城的.则希耍的边 数般少，比白B. 15C 16D, 21BLC. 1C 68.对F闍进挤朴排序.可议再到不同的拓1卜序列的个敬是弘 己帅一平长度为I石的腼堺茨L,基元诵按关龍字有序萍列.若辆折半査鮭査找- 牛匚中不存在的元畫，则关键字的比较机数嶷零是CBB 采用递归方式对顺序表进行快速排序.下列关于递归次数的叙述中，正确的是：A. 递归的次数与初始数据的排列次序无关.B. 每次划分后先处理较长的区间可以减少递归次数;C. 每次划分后先处理较短的区间可以减少递归次数;D. 递归次数与处理划分后得到的区间的次序无关. 对一组数据（2,12,16,88,5,10）进行排序. 如果前三趟排序结果如下 第一趟（2,12,16,5,10,88）第二趟（2,12,5,10,16,88）第三趟（2,5,10,12,16,88）则采用的排序算法可能是:A.冒泡排序 B.希尔排序C.归并排序D.基数排序DA1. （ ）数据的逻辑结构是指数据的各数据项之间的逻辑关系。2. （）KMP 算法的特点是在模式匹配时指示主串的指针不会变小。3. （ ）强连通分量是无向图的极大强连通子图。4. （ ）查找相同结点的效率折半查找总比顺序查找高。5. （）求n个数中最大的k（kn）个数，起泡排序比直接选择排序要好。6. （）平衡二叉树（AVL树）的中序遍历值是递增的。7. （）外排中使用置换选择排序的目的，是为了增加初始归并段的长度。8. （）链表的每个结点都恰好有一个指针。9. （）用六叉链表表示30个结点的六叉树，则树中共有151 个空指针。10. （ ）若完全二叉树的某个结点没有左子，则此结点必是叶子结点。FTFFFTFFTT11. （）栈和队列都是线性表，只是在插入和删除时受到了一些限制。12. （）数据的逻辑结构与数据元素本身的形式和内容无关。13. （）若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。14. （）若装填因子a为1,则向散列表中散列元素时一定会产生冲突。15. （）霍夫曼树的所有子树也均是霍夫曼树。16. （）平衡二叉树（AVL树）的中序遍历值是递增的。17. （）若有向图不存在回路，即使不用访问标志位同一结点也不会被访问两次18. （）归并排序在任何情况下都比所有简单排序速度快。19. （）外排中使用置换选择排序的目的，是为了增加初始归并段的长度。20. （ ）任何一个关键活动提前完成，则整个工程也会提前完成。TTFFTTFFTF1( )在对线性表的插入、删除操作较多，随机访问较少的情况下，采用链式存储结构 优于顺序存储结构。2( )线性表的逻辑顺序与存储顺序总是一致的。3( )顺序存储方式只能用于存储线性结构。4( )顺序存储的线性表可以按序号随机存取。5. ( )非空循环链表中每一个元素都有后继。6. ()在对队列做出队操作时，不会改变front指针的值。7. ( )数据结构包含数据的逻辑结构、数据的存储结构以及数据集合上定义的运算。8. ()若一个树叶是某二叉树的先序遍历序列最后一个结点，则它必是该二叉树的中序遍历序列最后一个结点。9. ( )已知一棵树的先序序列和后序序列，一定能构造出该树。10. ()字符串是数据对象特定的线性表。TFFTTFFFFT选择题:1. 在数据结构中，从逻辑上可以把数据结构分成()A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址()。A.必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.连续或不连续都可以3. 下列数据中，( )不是线性数据结构。A.队列B.栈C.完全二叉树D.循环队列4. 除了考虑存储数据结构本身所占用的空间外，实现算法所用辅助空间的多少称为()A.时间效率B.空间效率 C.硬件效率D.软件效率5. 带头结点的单链表h为空的判断条件是()A.h=NULLB. h-next=hC. h-next=NULLD. h!=NULL6. 以下算法的时间复杂度为。for(i=1;i=100;i+) for(j=i;j=0) 个结点的值. (假设该链 表至少有 k 个结点, 函数不能修改原链表)甲)描述算法思想 乙)描述实现步骤 将 n(0) 个整数存放在数值 R 中. 试设计一个算法在时间和空间两个方面尽可能高的 算法，将R中元素循环左移p (0pchild=NULL) /左子空，结点必为叶子 return(1+Count(t-nextsibling)； /1(当前结点为叶子)+兄弟子树上的叶子结点个数 elsereturn(Count(t-firstchild)+Count(t-nextsibling); /左子树的叶子个数+兄弟子树的叶子个数算法思想：统计以孩子兄弟链表表示的树的叶子数目，及求对应二叉树中没有左孩子 结点的数目，可采用递归来解决，递归模型如下：若结点空，叶子数目=0；若左子空，则叶 子数目=1+兄弟子树上的叶子结点个数；若左子不空，则叶子数目=左子树的叶子个数+兄弟 子树的叶子个数。 已知由整数组成的、单调递增的有序表以带头结点的单链表存储，试编写算法将链表中 元素值大于n且小于m的部分就地置逆(nm),其它部分保持不变。 假设一棵平衡二叉树的每个结点都标明了平衡因子bf,试设计一个算法，利用bf的值求平衡二叉树的高度。typedef struct nodeint bf, data；struct node *left，*right; BiTNode，*BSTree；int height(BSTree t) /函数返回值为平衡二叉树 t 的高度 若待排序列用带头结点的单链表存储，试给出简单选择排序算法。(15 分)typedef struct nodeint key;node *next; node, *pointer;void selectsort(pointer &h)/h 为头指针 已知一棵二叉树的中序遍历序列和按层次遍历的序列，试编写算法生成此二叉树的二叉 链表。 设整型数组a0 . a J中的数据呈随机分布，利用快速排序的思想设计算法求其中第k小0 n-1元素，要求平均时间复杂度为 O(n)。int k_th(int a, int n, int k)/返回第k小元素模拟试题.选择题：选择正确的答案填入下面的中。（10分）1长度为 n 的顺序存储线性表，当在任何位置上插入或删除一个元素的概率都相等时，插入一个元素所需移动元素的平均个数为A：，删除一个元素所需移动元素的平均个数为B。A、B：(n-l)/2n n+1nTn/2(n+l)/22.data, hext 其中 prior 与在双向循环链表p指针指向的结点之前插入一个q指针指向的结点，其修改指针的操 作为。（注：双向链表结点的结松 priornext 分别为指向前驱结点和后继结点的指针） p-prior二q; q-next=p; p-prior-next=q; q-prior二p-prior; p-prior二q; p-prior-next=q; q-next=p; q-prior二p-prior; q-next=p; q-prior二p-prior; p-prior-next=q; p-prior二q;3. 下列排序方法中时间复杂度为O（nlog2n），且使用辅助空间最少的是A；时间复杂度不受待排序序列的初始状态影响，恒为O（n2）的是B：。A、B：堆排序冒泡排序快速排序希尔排序直接插入排序 简单选择排序4. 顺序文件在数据量很大的情况下适合于。 按关键字存取直接存取成批处理随机存取5. 二维数组a0.81.10中，每个数组元素占用6个存储单元，a的第8列和第5行共占用A个存储单元。若a按行优先存放，元素a85的起始地址与a按列优先存放时元素B的起始地址相同。A：1081145460160B： a85 a310 a58 a096. 假设某文件经过内部排序得到27 个初始归并段，若要使多路归并3趟完成，则应取归并的路数为.23 457. 倒排文件含有若干个倒排表，倒排表的每一个元素 一个主关键字值及其记录地址 一个次关键字值及具有此次关键字值的记录个数 一个次关键字值及所有具有此次关键字值的记录地址.回答下列问题（10分）1. 设T是一棵二叉树，共有11个结点，除叶子结点外其它结点的度数皆为2,试问T的 最大可能高度h和最小可能高度h i是多少？ T中共有多少非叶结点？maxmin2. 设目标串s=abaabcdabfgp,模式串t=abcd。试说明简单的模式匹配过程。设目标串长为n，模式串长为m，这种匹配方法在什么情况下时间复杂度最大？应是多少？ KMP 匹配方法的特点是什么？时间复杂度是多少？-23. 如果有向图含有路径长度为负的回路（如图题II-1所示），厂;试问用Floyd方法求每对顶点之间的最短路径能否正常123工作？为什么？图题II-14. 高度为4的3阶B-树至少有多少个结点？为什么？5外排序的归并排序中使用的选择树和堆排序中的堆有什么区别？三. 已知一棵二叉树按层次遍历序列为ABCDEFGHIJ,中序遍历序列为BGDHAECIFJ（13分）1画出此二叉树的后序后继线索树；2. 画出此二叉树对应于完全二叉树的顺序存储结构；3. 将此二叉树还原成森林。？四. 某工程的AOE网络如图题II-2所示。图中 边上的权值为活动aiai0的期限（即完成 活动所需的天数）。（12分）1. 求该工程各事件的最早发生时间v和允许e 的最晚发生时间V|及各活动的最早开始时 间 e 和允许的最晚开始时间 l。2. 完成此项工程至少需要多少时间？哪些活 动是关键图题II -2五. 有一组记录的关键字为78,12,45,98,23,109,85,68,89,256,34。（15 分）1. 写出对这组记录进行一趟快速排序的结果,并说明这趟排序中关键字比较的次数为多 少？2. 将这组记录关键字建成一个小根堆；3. 将这组记录排序后作为有序查找表,画出此查找表的二叉判定树,求在等概率情况下 查找成功的平均比较长度是多少？若查找给定关键为 45 和 90 的记录各需比较多少 次？六. 有一组数据元素存于数组L1.n中，阅读下面的算法，写出该算法的功能，并分析其 时间复杂度是多少？（10 分）void maxmin（int i,int j,ElemType *max,ElemType *min） /此为递归算法，调用初值 i=1， j=n ElemType max1,max2,min1,min2;int mid;if （i=j） *max=*min=Li;else mid=（i+j）/2; maxmin（i,mid,&max1,&min1）; maxmin（mid+1,j,&max2,&min2）; if （max1max2） *max=max1; else *max=max2;if （min1min2） *min=min1;else *min=min2; /maxmin七. 试写一个算法，判断某二叉树（以二叉链表方式存储）是否为完全二叉树。（15 分）八. 已知有向图的邻接表，试写出求此有向图逆邻接表的算法。（15分）模拟试题参考答案选择题：1. A：B：2.3. A：B：4. 5. A：B：6.7. .问答题：1.非叶结点的个数为 5；h=6 ；h =4max min2简单的模式匹配过程如下：i 123456789 10 11 12s abaabcdab f p gIIIabcdIabcdI1-abcdIIIIabcd(匹配成功， index(s,t)=4)简单的模式匹配方法，最坏的情况出现在每趟比较都到模式串的最后一个字符时才失配，此时的时间复杂度是 O(m*n)。KMP法的特点是每趟比较目标串的下标i不回溯，时间复杂度为O(m+n)。3如果有向图含有路径长度为负的回路时，Floyd方法不能正常工作。虽然Floyd方法 允许路径为负数的情况，但不得包含路径长度为负的回路，如图题II-1的有向图，在 求顶点一的最短路径过程中，当加入中间点测试时，因为回路一一的长 度为T，而一之间可无数次经过这个回路，每经过一次，其路径长度就减去1,因 此使得 A1,3=-x。4高度为4的3阶B-树至少有15个结点。因为m阶B-树除根之外的每个结点至少有 m/2=2棵子树，而根至少有两棵子树，所以对3阶B-树而言最少的结点数应与高度 相同的满二叉树结点数相同。5. 选择树是由参加比较的n个元素作为叶子结点而构造的完全二叉树，而堆是n个元素的序列表示的完全二叉树，它满足R R且R R 且 R R 。i 2i i 2i+1Q F Q图题II -5123 456 7 8910 11 1213 14 15ABCDF图题II -4四. 1 .某工程AOE网络的各事件最早发生时间和允许的最晚发生时间如表题IIT所示; 各个活动的最早开始时间和允许的最晚开始时间如表题II-2所示。10五721.9116完成此项工程至少需14天。关键活动为气、岂， 对这组记录关键字进行一趟快速排序后的结果是：34,12,45,68,23 78 85,109,89,256,98 此趟排序中关键字比较10次。2. 由此组记录关键字建成的小根堆如图题II-6所示。3. 此组记录排序后组成的有序查找表为表题II 3序号 12345key612 23 34 45 68 78 85 89 98 109 256二叉判定树如图题II-7所示。等概率情况下查找成功的平均查找长度为ASL=(1+2x2+4x3+4x4)/11=33/11=3事件 1-3-4-6 为关键路径。12其、68 八/9889 256图题II -67891078查找K=45的记录需要比较3次，查找成功;5图题II-7查找K=90的记录需要比较4次，查找失败。3411-1表题I -1|1表题I -2事件1 23456活动a a a a a a123456a7a8aiove0349514e000344953vl0649 11 14l30794a94六.本算法的功能是求数组L中元素的最大值和最小值。算法的时间复杂度分析如下:算法的语句频度 T(n)=1T(n/2)+T(n/2)+3n=1n2为分析方便假设 n=2k(k 为正整数)，且每次将序列分为两个长度相等的子序列，则:T(n)= T(n/2)+T(n/2)+3=2T(n/2)+3=2(2T(n/4)+3)+3 =4T(n/4)+2*3+3 =4(2T(n/8)+3)+2*3+1*3=8T(n/8)+22*3+21*3+20*3 =8T(n/8)+(22+21+20)*3 =2kT(n/2k)+(2k-1+2k-2+ +21+20)*3=2kT(1)+(2k-1)*3=2k+(2k-1)*3=4*2k-3=4n-3=O(n)因此算法的时间复杂度为0(n)。图题II -8完全二叉树示例七算法思想：如图题II-8所示，对于完全二叉树而言，按层次 排列二叉树的结点时，结点是连续存在的；而对于非 完全二叉树，如以结点5 为根的子树(包括结点10 和 11)不存在时，即结点5 为空结点，其后还会有结点存 在。也就是说，非完全二叉树按完全二叉树序列层次排列结点时，会有空结点间隔实际存在结点的情况。设一个辅助队列q存放二叉树结点的指针，另设标志变量tag,表示按层次逐层从左至右扫描结点过程中是否出现过空结点，其初值为0，意为尚未有空结点出现。1) 若根结点存在，指针入队；2) 队列不空时，反复以下操作：若出队指针P为空，置tag=l；否则p不为空，若此时tag=l,则判定为非完全二叉树，结束；若此时tag=0，将它的左孩子和右孩子指针入队;3) 队列为空时，判定为完全二叉树，结束。算法描述：#define maxsize 100 /预定义队列容量#define FALSE 0 #define TRUE 1 typedef struct Bitnode ElemType data;struct Bitnode *lchild,*rchild;Bitnode,*Bitree; /定义二叉树结点类型和二叉树类型 typedef struct Bitree Elemmaxsize;int front,rear;Sequeue; /定义队列类型 int complete_Bintree(Bitree t)/判断二叉树是否为完全二叉树， t 为二叉树根结点的指针。/该二叉树是完全二叉树，返回“真”(即 1)；否则返回“假”(即 0)。 Sequeue q; /定义辅助队列 qq.front=-1; q.rear=0; /队列初始化tag=0; /标志变量初始化q.Elemq.rear=t; /根结点指针入队while (q.front!=q.rear) /队列不空则循环 q.front+; p=q.Elemq.front; /队头指针出队if (p=NULL) tag=1; /若为空指针，置标志表示出现过空指针else if (tag=1)/队头指针不空且之前出现过空指针return(FALSE); /返回“假”并且退出else /队头指针不空且之前未出现过空指针 q.rear+; q.Elemq.rear二p-lchild; /*p 的左孩子指针入队 q.rear+; q.Elemq.rear=p-rchild; /*p 的右孩子指针入队 /endwhilereturn(TRUE); /返回“真”并且退出/complete_Bintree八算法思想：首先将有向图的邻接表的顶点表拷贝给逆邻接表的顶点表，依次扫描邻接表的边表 若顶点i存在邻接点w,则i应为逆邻接表中顶点w的边表中的一个结点，将其插入到 该边表的表头。当扫描完邻接表中的所有边表后，逆邻接表就建成了。算法描述：#define max_vertex_num 100 /预定义图的最多顶点数typedef struct enode int adjvex;/邻接顶点序号struct enode *next; /下一结点指针EdgeNode; /定义边表结点类型typedef struct vnode VertexType vertex; /顶点信息EdgeNode *firstedge; /边表头指针VertexNode; /定义顶点表结点类型typedef struct VertexNode adjlistmax_vertex_num; /顶点表int n; /图中的顶点数ALGraph; /定义邻接表类型void inverse_adjlist(ALGraph A, ALGraph *B)/利用有向图的邻接表A,建立它的逆邻接表*B B-n=A.n;for (i=0;iadjlisti.vertex=A.adjlisti.vertex;B-adjlisti.firstedge=NULL;for (i=0;iadjvex; /取它的一个邻接点 ws=(EdgeNode *)malloc(sizeof(EdgeNode); /建立一个边表结点 *s s-adjvex=i;s-next=B-adjlistw.firstedge; /插入到逆邻接表顶点 w B-adjlistw.firstedge=s;/的边表之表头p=p-next;/endwhile/endfor/inverse_adjlist