中国科学院大学-862计算机软件基础【2012】考研真题
2023-06-21
999+
220.39KB
5 页
侵权投诉
中国科学院研究生院
2012 年招收攻读硕士学位研究生入学统一考试试题
科目名称：计算机软件基础
考生须知：
1．本试卷满分为 150 分，全部考试时间总计 180 分钟。
2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
第一部分：数据结构（共 70 分）
一、单选题（每题 2 分，共 20 分）
1．下面关于线性表的叙述错误的是【 】。
(A) 线性表采用顺序存储必须占用一片连续的存储空间
(B) 线性表采用链式存储不必占用一片连续的存储空间
(C) 线性表采用链式存储便于插入和删除操作的实现
(D) 线性表采用顺序存储便于插入和删除操作的实现
2. 栈和队列的共同特点是【 】。
(A) 只允许在端点处插入和删除元素 (B) 都是先进后出
(C) 都是先进先出 (D) 没有共同点
3. 以下数据结构中【 】是非线性结构。
(A) 队列 (B) 栈 (C) 线性表 (D) 二叉树
4. 树最适合用来表示【 】。
(A) 有序数据元素 (B) 无序数据元素
(C) 元素之间具有分支层次关系的数据 (D) 元素之间无联系的数据
5. 二叉树的第 k 层的结点数最多为【 】。
(A)2k-1 (B)2k+1 (C)2k-1 (D) 2k-1
6．若有 18 个元素的有序表存放在一维数组 A[19]中，第一个元素放 A[1]中，
现进行二分查找，则查找 A[3]的比较序列的下标依次为【 】。
科目名称：计算机软件基础 第 1 页 共 5 页
( A) 1，2，3 (B) 9，5，2，3
(C) 9，5，3 (D) 9，4，2，3
7. 对 n 个记录的文件进行快速排序，所需要的辅助存储空间大致为【 】。
(A) O（1） (B) O（n） (C) O（1og2n） (D) O（n2）
8．设有 6个结点的无向图，该图至少应有【 】条边才能确保是一个连通图。
（A）5 （B）6 （C）7 （D）8
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. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为【 】。
2. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子
的两个指针。在这种存储结构中，n个结点的二叉树共有【 】个指针域，
其中有【 】个指针域是存放了地址，有【 】个指针是空指针。
3. 在一个具有 n个顶点的无向完全图中，包含有【 】条边，在一个具有 n
个顶点的有向完全图中，包含有【 】条边。
4. 向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树
的高度【 】。
5. 为了能有效地应用 HASH 查找技术，必须解决的两个问题是【 】和【 】。
6. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛
选法建立的初始堆为【 】。
三、计算题（每题 10 分，共 30 分）
1. 在如下数组 A中链接存储了一个线性表，表头指针为 A [0].next，试写出该线
性表。
A 0 1 2 3 4 5 6 7
data
60
50
78
90
34
40
next
3 5 7 2 0 4 1
科目名称：计算机软件基础 第 2 页 共 5 页
标签： #中国科学院大学
摘要：
展开>>
收起<<
中国科学院研究生院2012年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机软件基础考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。第一部分：数据结构（共70分）一、单选题（每题2分，共20分）1．下面关于线性表的叙述错误的是【】。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现2.栈和队列的共同特点是【】。(A)只允许在端点处插入和删除元素(B)都是先进后出(C)...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
