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

《2022年北大数据结构与算法期末考试模拟试卷.docx》由会员分享，可在线阅读，更多相关《2022年北大数据结构与算法期末考试模拟试卷.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果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

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. 当图中各条边上的权值 _都相等 _ 时,宽

3、度优先搜寻算法可用来解决单源最短路径问题？【 2 分】6. 一棵有 n 个结点的满二叉树有 _0_个度为 1 的结点、 有_n-1/2 个分支 （非终端） 结点；该满二叉树的深度最大为 _n-1/2 _, 最小为 intlog 2n或 log2n ；（独根树深度为 0）【4 分】7.对于给定的n 个元素 ,可以构造出的规律结构有线性结构,树形结构,图形8.结构,_集合 _四种；【2 分】下面程序段的时间复杂度为_On_；n1 大 O 表示法 【2 分】sum=1；for i=0;sumlchild=null lh=_0_; else lh=_ heightp-lchild_ _; if p-r

4、child=null rh=_0_; else rh=_ heightp-rchild _; if lhrh hi=_lh+1_；else hi=_ rh+1 _; else hi=_ 0_; return hi; / 题目中结构已经给定,就应当依据题目要求来 / 假如依据给定的题目结构填入其他内容也正确的话,那么就是正确的；2对单链表（带头结点） 中元素按插入方法实现非递增序列的排序的C 语言描述算法如下,其中 L 为链表头结点指针；请填充算法中标出的空白处,完成其功能；typedef struct node int data; struct node *next; linknode,*li

5、nk; 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 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 页- - - - - - -