北京航空航天大学2023年硕士研讨生招生考试初试试题类别代码991…(北京航空航天大学杭州创新研究院)

一.单项选择题（本题共10分，每小题2分）
1.给定n个整数，进行堆排序的时刻凌乱度为（ ?）
a.o(n2)?????????????b.o(log2n)?????????????c.o(nlog2n）????????????d.o(n1.5)
?
2.有7个元素g，f，e，d，c，b，a顺次进栈（注：相邻两个元素进栈操作之间可以存在若干出栈操作），则下列选项中不可以能呈现的出栈序列是（ ?）。
a.e，c，d，b，a，f，g ??????????????b.f，d，b，c，e，g，a ??????????????
c.g，d，e，b，c，a，f ??????????????d.d，b，f，a，c，e，g
?
3.kmp算法分析了方法中隐含的用于方法匹配的信息，这种信息就是方法中的“有些匹配”信息。当有了next数组之后，然后显着前进了匹配功率。kmp算法的时刻凌乱度为（ ?）。
a.o(m+n) ????????????????????????b.o(m×n) ???????????????
c.o(log2m+log2n) ?????????????????d.o(log2m×log2n)
?
4.给定一个二叉树（根结点为第一层），则第五层最多有（ ?）个结点。
a.16 ???????????????????b.15 ???????????????????c.32 ??????????????

d.31
?
5.给定一棵二叉树，该二叉树的前序遍历得到的序列是abcdef，中序序列得到的序列是cbaedf，后序遍历得到的序列为（ ?）。
a.cbefda ???????????b.fedcba ??????????c.cbedfa ???????????d.不断定
?
二.简答题（本题共20分，每小题5分）
1.关于栈和行列两种数据规划，请指出哪一种数据规划契合“ 先出”原则，哪一种数据规划契合“ 后出”原则？
2.请简述邻接矩阵办法存储无向无权图的根来历理。
3.给定一个长度为100的字符串s，该字符串s对应的集结是{a，b，c，d，e，f，g}，即字符串中没有呈现7个以外的字符，一起在字符串s的这100个字符中，a呈现23次，b呈现2次，c呈现30次，d呈现3次，e呈现10次，f呈现7次，g呈现25次，请写出a，b，c，d，e，f，g的哈夫曼编码。（阐明：规划哈夫曼树时，值较小的结点放左分支，值较大放右分支，左分支为0，右分支为1）
4.运用动态方案办法求解疑问需要具有哪些性质？
?
三.归纳题（本题共10分）
元素个数为n的int型数组a，用二路归并算法完成排序，简述算法完成思路，阐明算法的时刻凌乱度。
?
四.算法方案题（本题共10分）
请写一算法，将两个按值逆序联接的非空线性链表兼并为一个按值逆序联接的线性链表。