2022年北大数据结构与算法期末考试模拟试卷.docx

精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果20XX 年春季北大数据结构与算法B期末考试模拟试卷（本试卷只是给同学们看看考题形式和范畴,难度与真实考卷稍有差别）学号 _ 姓名_ 老师 /教室 _ （注：如未标明,本试卷题中的下标、位置都从0 开头计数）”一、填空题（共32 分）, C= “just,请运算以下表达式：1.设有字符串变量String A = “This ”, B= “is ”（1）A+B+D=_ “ Thisisa.test” _；（2）D.IndexOf “ t ” = _2_；（求字符在字符串中的第一个位置）（3）B.Strlength = _ 2_ （4）D.SubStr1,2 = _“ .t”_（注： 1 为起始下标, 2 为子串长度） 【4 分】2. 次序查找 n 个元素的次序表,如查找胜利,就比较关键字的次数最多为 _n_次；如查找失败,就比较关键字的次数最多为_n_,最少为 _n_次；【3 分】3. 在散列函数 H（key）=key%p 中, p 值最好取 _质数（或素数 ）_；【1 分】4. 对于下图邻接表所对应的有向图,试写出：【 2 分】1 从顶点动身进行深度优先遍历结果 _1, 2, 3, 4, 5_；2 从顶点动身进行广度优先遍历结果 _1, 2, 3, 4, 5 _；5. 当图中各条边上的权值 _都相等 _ 时,宽度优先搜寻算法可用来解决单源最短路径问题？【 2 分】6. 一棵有 n 个结点的满二叉树有 _0_个度为 1 的结点、 有_n-1/2 个分支 （非终端） 结点；该满二叉树的深度最大为 _n-1/2 _, 最小为 intlog 2n或 log2n ；（独根树深度为 0）【4 分】7.对于给定的n 个元素 ,可以构造出的规律结构有线性结构,树形结构,图形8.结构,_集合 _四种；【2 分】下面程序段的时间复杂度为_On_；n>1 大 O 表示法 【2 分】sum=1；for i=0;sum<n;i+ sum+=1; 9.对于最大堆 65 43 59 24 37 48 57 12 23 28 5 3,删除掉最大元素后,堆中元素为59,43,57,24,37,48,3,12,23,28,5 【2 分】名师归纳总结 - - - - - - -第 1 页,共 5 页精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果10. 从空二叉树开头,严格依据二叉搜寻树的插入算法（不进行旋转平稳）,逐个插入关键码 18,73,10,5,68,99,27,41,51,32,25 构造出一棵二叉搜寻树,该二叉树转换为森林,就该森林的层次遍历序列为 对于的二叉树为_18 73 99 10 68 5 27 41 51 25 32_【4 分】名师归纳总结 11. 用 S 表示入栈操作,X 表示出栈操作,如元素入栈的次序为12345,为了得到13542 出第 2 页,共 5 页栈次序,相应的S和 X 的操作串为 _SXSSXSSXXX _；【2 分】二、单项题（ 18 分,每题 2 分,最终两题每题4 分）1. 对初始状态为递增的表按递增次序排序,最省时间的是（C ）算法；- - - - - - -精选学习资料 - - - - - - - - - A. 基数排序B. 桶排多练出技巧巧思出硕果C. 直接插入排序D. 归并排序2. 一个 n 个顶点的连通无向图,其边的个数至少为（A）；C）An-1Bn Cn+1 Dnlogn ；3 线性表（a1,a2, ,an）以链接方式储备时,拜访第i 位置元素的时间复杂度为（AO（i）BO（1）CO（n）DO（i-1）4. 使用 Prim 算法从结点0 动身求下图的最小生成树,依次写出每次被加入到最小生成树中边的编号,下面正确的答案是（B）；A. 0, 2 3, 5 1, 4 2, 5 1, 2 C. 0, 2 3, 5 1, 4 1, 2 2, 5 B. 0, 2 2, 5 3, 5 1, 2 1, 4 B. 0, 2 1, 2 1, 4 2, 5 3, 5 5一个有 n 个结点的图,最多有（D）个连通重量；A0 B1 Cn-1 Dn 6. 用二分（对半）查找法检索元素速度比用次序法 D ；【2 分】A必定快 B. 必定慢 C. 相等 D. 不能确定7. 已知一算术表达式的中缀形式为 A+B*C-D/E ,后缀形式为 ABC*+DE/- ,其前缀形式为 D ；【4 分】A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE 8对序列 15 ,9,7,8, 20,-1,4 进行排序,进行一趟处理（对应于排序算法中一层循环或一层递归算法）后,数据的排列变为4 ,9,-1,8,20,7,15 ；就采纳的是 （C ）排序；【4 分】A. 挑选 B. 快速 C. 希尔（ Shell ） D. 冒泡三、简答题（ 30 分,每题 10 分）1. 试问由二叉树的中序序列和后序序列是否能唯独的建立二叉树,请说明理由；如能,对中序序列 DBEAFGC 和后序序列DEBGFCA 构造二叉树；答：（1）给定二叉树结点的后序序列和对称序（中序）序列,可以唯独确定该二叉树；由于后序序列的最终一个元素是根结点,该元素将二叉树中序序列分成两部分,左边（设 有 l 个元素）表示左子树,如左边无元素,就说明左子树为空；右边（设有 r 个元素）是右子树,如为空,就右子树为空；依据后序遍历中“ 左子树右子树根” 的次序,名师归纳总结 就后序序列中由从第1 元素开头的l 个结点序列和中序序列根左边的l 个结点序列构造第 3 页,共 5 页- - - - - - -精选学习资料 - - - - - - - - - 左子树； 由后序序列多练出技巧巧思出硕果r 个元素序列构造l 个元素后面r 个元素序列与中序序列根右边的右子树；（2）中序序列 DBEAFGC 和后序序列 DEBGFCA 构造的二叉树如下图2设一组数据为 1,14,27,29,55,68,10,11,23 ,现采纳的散列函数是 Hkey=key % 13 ,冲突用链地址法解决,设散列表的大小为 答：13下标为 012,试画出插入上述数据后的散列表；3. 设 T 是一棵二叉树,除叶子结点外,其它结点的度数皆为2,如 T 中有 6 个叶结点,试问：（1）T 树的最大深度Kmax=. 最小可能深度Kmin=. （假定独根二叉树深度为0）（2）T 树中共有多少非叶结点？（3）如叶结点的权值分别为 权路径长度 wpl ；1,2,3,4,5,6；请画出一棵哈曼夫树,并运算该哈曼夫树的带答： 1）T 树的最大深度 Kmax=5（除根外,每层均是两个结点）T 树的最小深度 Kmin=3（具有 6 个叶子的完全二叉树是其中的一种形状）（2）非叶子结点数是 5；（n2=n0-1 ）（3）哈夫曼树见下图,其带权路径长度 wpl=51 四、算法填空题（20 分,第一题 10 分,第 2 题 10 分）1. 下面是求二叉树高度（独根树高度是1）的递归算法,试补充完整名师归纳总结 二叉树的两指针域为lchild 与 rchild, 算法中 p 为二叉树的根,lh 和 rh 分别为以 p 为根的二第 4 页,共 5 页叉树的左子树和右子树的高,hi 为以 p 为根的二叉树的高,hi 最终返回；- - - - - - -精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果int heightBinTree *p int hi, lh, rh; / p.=NULL 也对if _ p _ if p->lchild=null lh=_0_; else lh=_ heightp->lchild_ _; if p->rchild=null rh=_0_; else rh=_ heightp->rchild _; if lh>rh hi=_lh+1_；else hi=_ rh+1 _; else hi=_ 0_; return hi; / 题目中结构已经给定,就应当依据题目要求来 / 假如依据给定的题目结构填入其他内容也正确的话,那么就是正确的；2对单链表（带头结点） 中元素按插入方法实现非递增序列的排序的C 语言描述算法如下,其中 L 为链表头结点指针；请填充算法中标出的空白处,完成其功能；typedef struct node int data; struct node *next; linknode,*link; void Insertsortlink L link p,q,r,u; p=L->next; _L->next = NULL _; / L->next = NULL 这一句是需要的, 由于 p 指向待插入结点, L 后来始终指向排好序的链表；/ 其次层 while 循环实际上是在 L所指向的有序表中查找 p 应当插入的位置；while_ p .= NULL _ r=L; q=L->next; whileq .= NULL && q->data <= p->data r=q; q=q->next; u=p->next; _p->next=r->next 或 p->next = q_; _r->next = p_; p=u; 名师归纳总结 【注：后面两空也可以是r->next = p; p->next = q; 此时肯定不能写成p->next = r->next 】第 5 页,共 5 页- - - - - - -