当前位置: 首页 > >

2012年-2013年中国科学院大学计算机软件基础考研真题试题试卷汇编

芝士传媒 × 题源库 www.zhishi360.com ...让知识更美味... 目 录 2012 年中国科学院大学计算机软件基础考研真题试题试卷········································ 2 2013 年中国科学院大学计算机软件基础考研真题试题试卷········································ 7 第 1 页,共 13 页 芝士传媒 × 题源库 www.zhishi360.com ...让知识更美味... 中国科学院研究生院 2012 年招收攻读硕士学位研究生入学统一考试试题 科目名称:计算机软件基础 考生须知: 1.本试卷满分为 150 分,全部考试时间总计 180 分钟。 2.所有答案必须写在答题纸上,写在试题纸上或草稿纸上一律无效。 第一部分:数据结构(共 70 分) 一、单选题(每题 2 分,共 20 分) 1.下面关于线性表的叙述错误的是【 】 。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2. 栈和队列的共同特点是【 】 。 (B) 都是先进后出 (D) 没有共同点 】是非线性结构。 (B) 栈 (C) 线性表 (D) 二叉树 (A) 只允许在端点处插入和删除元素 (C) 都是先进先出 3. 以下数据结构中【 (A) 队列 4. 树最适合用来表示【 (A) 有序数据元素 】 。 (B) 无序数据元素 (D) 元素之间无联系的数据 (C) 元素之间具有分支层次关系的数据 5. 二叉树的第 k 层的结点数最多为【 (A)2k-1 (B)2k+1 】 。 (C)2k-1 (D) 2k-1 6.若有 18 个元素的有序表存放在一维数组 A[19]中,第一个元素放 A[1]中, 现进行二分查找,则查找 A[3]的比较序列的下标依次为【 】 。 科目名称:计算机软件基础 第 1 页 共 5 页 第 2 页,共 13 页 芝士传媒 × 题源库 www.zhishi360.com ...让知识更美味... ( A) (C) 1,2,3 9,5,3 (B) (D) 9,5,2,3 9,4,2,3 】 。 7. 对 n 个记录的文件进行快速排序,所需要的辅助存储空间大致为【 (A) O(1) (B) O(n) (C) O(1og2n) (D) O(n2) 8.设有 6 个结点的无向图,该图至少应有【 (A)5 (B)6 】条边才能确保是一个连通图。 (D)8 (C)7 9.设哈夫曼树中的叶子结点总数为 m,若用二叉链表作为存储结构,则该哈夫 曼树中总共有【 】个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 10.设某棵二叉树的中序遍历序列为 ABCD,前序遍历序列为 CABD,则后序遍 历该二叉树得到序列为【 】 。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 二、填空题(每空 2 分,共 20 分) 1. 2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为【 】 。 若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子 的两个指针。在这种存储结构中,n 个结点的二叉树共有【 】个指针域, 其中有【 】个指针域是存放了地址,有【 】个指针是空指针。 在一个具有 n 个顶点的无向完全图中,包含有【 个顶点的有向完全图中,包含有【 】条边。 】条边,在一个具有 n 3. 4. 向一棵 B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树 的高度【 】 。 】和【 】 。 5. 为了能有效地应用 HASH 查找技术,必须解决的两个问题是【 6. 设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛 选法建立的初始堆为【 】 。 三、计算题(每题 10 分,共 30 分) 1. 在如下数组 A 中链接存储了一个线性表,表头指针为 A [0].next,试写出该线 性表。 A data next 3 0 1 60 5 2 50 7 3 78 2 4 90 0 5 34 4 6 7 40 1 科目名称:计算机软件基础 第 2 页 共 5 页 第 3 页,共 13 页 芝士传媒 × 题源库 www.zhishi360.com ...让知识更美味... 2. 设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查 找方法用二分查找,要求计算出查找关键字 62 时的比较次数并计算出查找成 功时的平均查找长度。 3. 已知待散列的线性表为 (36, 15, 40, 63, 22) , 散列用的一维地址空间为[0..6], 假定选用的散列函数是 H(K)= K mod 7,若发生冲突采用线性探查法处理,试: (1)计算出每一个元素的散列地址并在下图中填写出散列表: ` 0 1 2 3 4 5 6 (2)求出在查找每一个元素概率相等情况下的平均查找长度。 第二部分:操作系统(共 40 分) 一、单选题(每题 2 分,共 10 分) 1.把逻辑地址转变为内存的物理地址的过程称做【 (A) 编译 (B) 连接 (C) 】 。 运行 】 。 (D) 重定位 2.进程和程序的一个本质区别是【 (A) (B) (C) (D) 前者分时使用 CPU,后者独占 CPU 前者存储在内存,后者存储在外存 前者在一个文件中,后者在多个文件中 前者为动态的,后者为静态的 】 。 (B) (D) 系统调用命令 低级进程通信原语 3. 在操作系统中,P、V 操作是一种【 (A) (C) 机器指令 作业控制命令 4. 分页式虚拟存储管理系


相关推荐


友情链接: 高中资料网 职业教育网 成人教育网 理学 大学工学资料