这篇摘要主要包含了2018年上海大学计算机考研832科目的一份真题回忆版,包括选择题部分。这些题目涵盖了计算机科学的基础知识,如排序算法的稳定性、进制转换、数据结构的操作复杂度、查找算法效率、计算机硬件分类、存储器类型及其特性、计算机体系结构中的各种组件作用以及程序执行流程等。
1. 排序算法的稳定性:冒泡排序和直接插入排序是稳定的排序算法,它们不会改变相等元素的相对顺序。基数排序也是稳定的,而希尔排序、堆排序和选择排序不是稳定的排序算法。
2. 进制数的真值比较:要比较不同进制数的真值,需要将它们转换成相同的进制再进行比较。这里可以计算每个选项对应的十进制值,然后比较大小。
3. 计算机存储器:SRAM(静态随机存取存储器)不需要刷新,而DRAM(动态随机存取存储器)需要定期刷新;DRAM的集成度比SRAM高;DRAM是易失性存储器,断电后数据会丢失;而cache通常使用SRAM,因为它速度快但成本高。
4. 操作复杂度:在顺序表中访问一个元素的时间复杂度是O(1),因为可以直接通过索引访问。而在顺序表中插入一个元素、在单链表中访问或插入一个元素的时间复杂度都不是O(1)。
5. 折半查找:在递增有序数组中,最坏情况下折半查找的比较次数不超过log2n次,所以100个元素的数组最多比较9次(因为2^9=512>100)。
6. 完全二叉树的叶子节点数量:对于100个节点的完全二叉树,可以使用公式2^(h-1) - 1来估算,其中h是高度。根据完全二叉树的性质,高度为6时,叶子节点数量为45。
7. 计算机分类:一般家用台式电脑属于微型机。
8. 微程序存储位置:微程序通常存储在控制存储器中。
9. 一地址指令:这种指令可能有一个操作数,也可能有多个操作数,具体取决于指令编码。
10. 决定程序执行顺序的是程序计数器,它存储了下一条指令的地址。
11. 扩展操作码设计:其目的是在不增加指令字长度的情况下,增加操作指令的数量。
12. 运算器功能:运算器可以执行算术和逻辑运算,但发出“读”信号通常由控制器负责。
13. 存储上三角矩阵:上三角矩阵的非零元素个数是n*(n+1)/2,因此需要这么大的数组存储。
14. 栈的出栈序列:深度为4的栈,入栈顺序为ABCDEF,出栈顺序可能是多种,但不能违反先入后出的原则。
15. 排序算法的效率:当待排序数列越有序时,冒泡排序和插入排序的速度会变快,而选择排序和快速排序的平均时间复杂度与数据初始顺序关系不大,故不会明显变慢。
这些题目反映了计算机科学基础理论和实践中的关键概念,对于准备计算机相关考试的学生来说是很好的练习材料。