2017北大软微考研831试题解析：计算机基础综合

"2017北大软微考研831试卷1" 这是一份2017年北京大学软件与微电子学院831试卷，主要涵盖计算机基础综合的知识点，包括数据结构、操作系统和计算机网络三大部分。试卷包含了选择题和问答题。 选择题部分涉及了链表操作的时间复杂度、不同链表结构的选择、栈的性质、循环队列的管理、完全二叉树的节点计算、二叉树线索化的特性、有向图的边数、关键路径分析、AVL树的平衡调整以及排序算法的时间复杂度等知识点。 1. 合并升序链表为降序链表的时间复杂度问题，最坏情况下为O(m+n)，选项D正确。 2. 对于常用末尾插入和删除操作的链表，带尾指针的单循环链表是最佳选择，选项B正确。 3. 由栈的性质可知，不可能的出栈序列是DCEAB，因为A不可能在D之后出栈，选项D错误。 4. 循环队列的删除和插入操作后，rear和front的值应变为2和4，选项B正确。 5. 完全二叉树的叶子节点数计算公式为n=2^(h+1)-1，其中n是节点总数，h是高度，对于626个结点的完全二叉树，答案是B，312。 6. 左子树为空的二叉树在先序线索化后，只有一个空的链域，选项B正确。 7. 强连通图的最少边数为顶点数，因此至少有10条边，选项C正确。 8. 关键路径的描述中，D选项不正确，某些关键活动提前完成并不意味着整个工程会提前完成。 9. AVL树的平衡调整，A的左孩子平衡因子为0，右孩子为1，应作RL型调整，选项C正确。 10. 在O(nlog2n)时间内的稳定排序算法是归并排序，选项C正确。 11. 操作系统提供给程序员的接口通常是系统调用和库函数，选项D正确。 12. 特权指令只能在操作系统内核中使用，选项A正确。 13. 进程描述中的不准确项，进程不是完整的程序，而是程序的一次执行实例，选项A错误。 问答题部分涉及到有向图无环检测和数组排序的问题，要求编写算法来判断有向图是否存在有向回路，并在存在时输出回路；还要求对数组进行排序，可能涉及各种排序算法的讨论和实现。 这份试卷覆盖了计算机科学的基础知识，对考生的数据结构理解、算法设计能力以及操作系统和网络原理的掌握有较高要求。