《北京理工大学-889-2020-真题回忆版》由会员分享，可在线阅读，更多相关《北京理工大学-889-2020-真题回忆版（5页珍藏版）》请在金锄头文库上搜索。
1、2020 北京理工大学 889 回忆 选择题选择题 20 个个 1，给你入栈顺序 123，出栈顺序 231，问你操作序列。（push、push、pop、push、pop、pop） 2，下列哪个说法错误： A 对称矩阵的存储只需要存主对角线和上三角或下三角 B 对角矩阵不用存储零 C 稀疏矩阵可以用三元组 D 稀疏矩阵有分布规律，可以用三元组 3，给了一循环队列 A030，rear 指向队尾元素，front 指向队头元素的前一个位置，存储了 11 个元素，当前 front 指向 25，求 rear 指针位置。(5) 4，有一个无向图，每个边值不同，问下列哪一个选项是错的。 A 生成树不一定唯一
2、BC 很简单，不记得了。 D 两节点的最短距离一定是最小生成树上的两节点最短距离 5，一个外层循环 n,内层循环 2n 的程序，问你时间复杂度。（O(n2)）（注意不要选O(2n2)，渐进复杂度省略常数） A O(2n) B O(n) C O(2n2) D O(n2) 6，二维矩阵的压缩方式：（答案应该是十字链表和三元组，不要选散列和邻接表） 7，请选出排序算法的启动时间最少的算法，所谓启动时间就是说选出第一个元素的最终位置所花的时间。A 归并排序 B 堆排序 C 插入排序 D 快速排序 8，下列哪个空间复杂度不是常数： A 归并排序 B 堆排序 C 快速排序 D 置换-选择排序 9，顺序表下
3、列哪个操作平均复杂度与众不同。 A 删除元素 a B 查找元素 a C 求表长 D 在第 i 个元素后插入 10，给你一个图，问你哪个 dfs 序是不可能的（简单题，没啥说的） 11，给你一个 1.5, 1.5 上三角矩阵，问你压缩成一维后（下标从零开始），在行优先的情况下，a33 的下标。（10） 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研12，关于 m 阶 b 树性质，下列哪个错
4、误：（每个节点最少有 2 个子树，注意根节点为叶子结点的情况）A 每个节点最少有 2 个子树 B 每个节点最多 m-1 关键字 C 叶节点都在同一层 D 记录是有序的 13，中序线索二叉树的后继不可能是： A 祖先 B 兄弟 C 右孩子的左子树 D 儿子 14，问你抽象数据类型说法错误的是：（D 用户可以看外面，也能清楚看到内部算法过程）15，给你一个序列，问你折半查找某个不存在的数字的比较次数。（简单题） 16，对于一个森林来说，以孩子兄弟表示法表示，那么对于森林中的叶子节点，在孩子兄弟表示法中应该是（）A 没有左孩子 B 没有右孩子 C 有左孩子，没有右孩子 D 既没有左孩子也没有右孩子
5、17，n 个节点的正则（完全）二叉树，分支节点个数为？ A n/2 B (n-1)/2 C (n+1)/2 D n 18，给了四个序列问哪个不是折半查找的查找序列。（简单题，只要保证搜索范围在不断缩小就行，比如目标是 12，你之前已经比较过 10 和 14 了，这时候序列出来个 8，那明显就不是折半查找的查找序列了）19，给了四个序列问哪个既不是大根堆，也不是小根堆。（简单题，选项里有一个 83 82 84，83 两个孩子一大一小，那肯定错了啊） 填空题填空题 15 个题，个题，20 个空个空 1，给了一个 hash 函数和输入序列，问你某一个值在表中的 key 是什么，问你平均查找长度。（这
6、题第一问简单，第二问。可能要把成功查找的平均值和不成功的平均值再求平均）2，问你 100 个数字归并排序需要几趟（7） 3，给你前序中序求层次遍历。（简单题） 4，基数排序的步骤：（分配）和收集 5，给你一个序列，问步长为 3 的一趟希尔排序后是什么样（简单题） 6，5 层(不含叶子结点层)3 阶 B 树结点最多 121 个，最少 31 个。 7，在二叉搜索树中删除 u，已知 u 的祖先是 p，u 只有左子树 s。操作是：p-lc=s,s-parent=p；然后释放 u 的空间。 8，给你一个 avl 的插入序列（10，9，15，12，11），问你它旋转后的树的层次遍历。（10，9，12，11
7、，15） 9， 一个 n 个节点的完全二叉树只有一个叶子结点的点是第几个点。（n/2） 10，单链表中删除 q 的后继结点的操作（q-next=q-next-next） 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研11，给你一个 hash 函数 x%7，和几个数，问你能和 48 映射在同一位置的数字是（62） 12，广义表(a),(b),c),(d)，求长度：3，深度：4，表头：(a)
8、，表尾(b),c),(d)： 13，森林的后序遍历是树的 中 序遍历 14，给你一个序列（1，2，3，4，5），问你折半查找数字 2 所用的比较次数为 2 次。 简答题简答题 4 个个 1，给你中序和层次遍历，让你画出那个树，并写出前续和中序。 简单题，没啥说的2，已知 L 是单向循环链表，长度大于 4，p1p2 为指向其中两个不同节点的指针，问你 A程序的意思和复杂度。 1 void A(L, p1, p2) 2 3 B(p1,p2); 4 5 B(p2,p1); 6 7 8 9 void B(LNode *s, LNode *e) 10 11 LNode *p=s; 12 13 while
9、(p-next!=e)p=p-next; 14 15 p-next = s; 16 17 A 的功能是把循环链表 L 在 p1 和 p1 的前缀处切开、p2 和 p2 的前缀处切开，分割成两个单向循环链表。复杂度是 O(n) 3，有两个小问： 1，一个 50 个点，100 条边的无向图，点信息 20 字节，边信息 10 字节，邻接信息4 字节，n、m、type 各 8 字节，用邻接矩阵表示，问你存储这个图要花多少字节。 50*20+50*50*(10+4)+3*8 2，问你邻接表存储的无向图求连通分量的复杂度分析。 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t
10、 h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研时间复杂度：O(n+e)。因为要 DFS 每一个节点，且每个边都访问一遍。 空间复杂度：O(n)。因为要开染色标记的辅助数组，如果 DFS 是递归实现，还要用深度为 n 的系统栈。 4，给你 14 个带权重的字母，设计一种三进制编码。 构造三叉哈夫曼树，没啥好说的，唯一要注意的点是要加一个权重为 0 的空节点。因为：(n-1)%(m-1)=(14-1)(3-1)=1。我一开始忘加了，写完才发现不对，浪费了 15 分钟。
11、算法题算法题 3 个：个： 1，现有一字符数组 S,其中存储的是从 a 到 z 的小写字母。设计一个算法，对该字符数组进行重新排列，使得所有的字母a都放在前面，其他字母放在 a 后面，请分析你设计的算法的时间复杂度。void MaxAFront(char S,int n); 提供两种思路：1，用a做轴，做一趟快排，把小于等于的放左，大于的放右 2，两个指针pq，p指向0，q遍历，遇到一个a就交换pq指向的元素然后p+ 2，一个有表头节点的单链表 l。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k(k 为正整数)个节点。若查找成功，输出该节点的 data 值，并retur
12、n 1，否则 return 0. int KtoLast(LinkList L,int k) typedef struct LNode int data; struct LNode *next; LNode, *LinkList 提供三种思路： 1，两个指针pq，先让p走k步，然后pq一起走，如果p指向空，那么q就是倒数第k个元素。 2，计算表长n，然后输出正向第n-k+1个元素 3，递归，返回值是当前层深度，回溯的时候就可以判断是否为倒数第k个。 这题要注意两个坑， 一个是列表长度可能小于k，那就是无解。 一个是不允许改变链表，也就是说不能用“反转、取正向第K个、再转回来”的算法。 各个学校
13、计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研3，二叉树t中，每个节点都拥有一个权值(正整数)，请设计一个递归算法，求T中所有叶子权值的最大值，假设函数定义如下。 int MaxLeafValue(BiTree T) typedef struct BiTNode int w; struct BiTNode *lchild,*rchild; BiTNode.*BiTree int MaxLeafValue(BiTree T) if(!T) return 0; if(!T-lchild&!T-rchild) return T-w; return max(MaxLeafValue(T-lchild), MaxLeafValue(T-rchild); 出处 ：https:/ 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研
