2013年中国科学院大学程序设计考研试题
- 格式：pdf
- 大小：89.28 KB
- 文档页数：4
文档推荐
-
最新中国海洋大学考研试题页数:12
-
新版中国海洋大学生物学考研经验考研参考书考研真题页数:15
-
中国海洋大学硕士研究生环境工程考研试题页数:13
下载文档原格式
合集下载
2013年中国科学院大学计算机原理考研试题
中国科学院中国科学院大学大学2013年招收攻读硕士学位研究生入学统一考试试题科目名称科目名称：：计算机原理考生须知考生须知：：1．本试卷满分为150分，全部考试时间总计180分钟。
2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
一、单选题（每空3分，共45分）1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除一个元素，则采用最节省运算时间的存储方式是 。
A. 单链表B. 仅有头指针的单循环链表C. 双链表D. 仅有尾指针的单循环链表2. 链表不具有的特点是 。
A. 插入、删除操作不需要移动元素B. 可随机访问任一元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比3. 设广义表L=（（a ，b ，c ）），则L 的长度和深度分别是 。
A ．1和1 B. 1和3 C. 1和2 D. 2和34. 在树的双亲表示法中，对树按层次编号，用数组进行存储，则下面说法不正确的是 。
A. 兄结点的下标值小于弟结点的下标值B. 所有结点的双亲可以找到C. 任意结点的孩子信息可以找到D. 下标值为i 和i+1结点的关系是孩子和双亲5. 对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为 。
A. 求一个顶点的邻接点B. 求一个顶点的度C. 深度优先遍历D. 广度优先遍历6. 含n 个关键字的二叉排序树的平均查找长度主要取决于 。
A. 关键字的个数B. 树的形态C. 关键字的取值范围D. 关键字的数据类型7.下列排序算法中，其时间复杂度和记录的初始排列无关的是。
A. 折半插入排序B. 堆排序C. 快速排序D. 冒泡排序8.在Hash函数H(k)=k MOD m中，一般来讲，m应取。
A. 奇数B. 偶数C. 素数D. 充分大的数9.冯•诺依曼计算机体系结构的基本思想是：。
A. 存取独立B. 存储程序C. 流水处理D. 并行处理10.某浮点数x按IEEE754标准表示其16进制存储格式为(C1360000)16，则其十进制数值为。
中科院864程序设计考研大纲
中国科学院大学硕士研究生入学考试《程序设计》考试大纲本《程序设计》考试大纲适用于中国科学院大学计算机科学与技术类的硕士研究生入学考试。
程序设计是计算机科学与技术及相关学科的重要基础，主要内容包括数据结构和C 程序设计两大部分。
要求考生对计算机科学与技术及相关学科的基本概念有较深入、系统的理解，掌握各种数据结构的定义和实现算法，对C语言的基本知识有较深入的了解，掌握程序设计的基本方法，并具有综合运用所学知识分析问题和解决问题的能力。
一、考试内容数据结构1、绪论（1）数据结构的基本概念，数据的逻辑结构、存储结构。
（2）算法的定义、算法的基本特性以及算法分析的基本概念。
2、线性表（1）线性关系、线性表的定义，线性表的基本操作。
（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。
在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。
3、堆栈与队列（1）堆栈与队列的基本概念、基本操作。
（2）堆栈与队列的顺序存储结构与链式存储结构的构造原理。
（3）在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。
4、串（1）串的基本概念、串的基本操作和存储结构。
（2）串的模式匹配算法和改进的KMP算法5、数组和广义表（1）数组的概念、多维数组的实现（2）对称矩阵和稀疏矩阵的压缩存储（3）广义表的基本概念6、树与二叉树（1）树的定义和性质（2）二叉树的概念、性质和实现（3）遍历二叉树和线索二叉树（4）树和森林（5）赫夫曼树及其应用（6）树的计数7、图（1）图的定义，基本概念，图的分类，常用名词术语。
（2）图的邻接矩阵存储方法、邻接表存储方法的构造原理。
（3）图的遍历操作。
（4）最小生成树，最短路径，AOV网与拓扑排序。
8、文件及查找（1）数据文件的基本概念和基本术语，数据文件的基本操作。
（2）顺序文件、索引文件、散列(Hash)文件。
北京中国科学院大学2013年考研计算机软件基础真题
（北京）中国科学院大学2013年考研计算机软件基础真题中国科学院大学2013 年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机软件基础考生须知：1．本试卷满分为 150 分，全部考试时间总计 180 分钟。
2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
第一部分：数据结构（共 70 分）一、单选题（每题 2 分，共 20 分）1. 下列关于数据的逻辑结构的叙述中，不正确的是【】。
(A) 数据的逻辑结构是数据间关系的描述(B) 线性表是典型的线性结构(C) 数据的逻辑结构分为线性结构和非线性结构(D) 数据的逻辑结构不仅反映数据间的逻辑关系，而且包含其在计算机中的存储方式2. 下列关于数据运算的叙述中，不正确的是【】。
(A) 数据运算是数据结构的一个重要方面(B) 数据运算的具体实现是在数据的逻辑结构上进行(C) 检索是一种常用的运算(D) 插入是一种常用的运算3. 在包含1000个元素的线性表中实现如下各运算，所需执行时间最长的是【】。
(A) 线性表按顺序方式存储，删除线性表的第 900 个结点(B) 线性表按链式方式存储，删除指针 P 所指向的结点(C) 线性表按顺序方式存储，在线性表的第 100 个结点后面插入一个新结点(D) 线性表按链式方式存储，在线性表的第 100 个结点后面插入一个新结点4. 设某散列表的当前状态如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18该散列表的负载因子约为【】。
(A) 0.37 (B) 0.42 (C) 0.58 (D) 0.735. 设有关键码序列（Q,G,M,Z,A,N,B,P,X,H,Y,S,T,L,K,E），采用堆排序法进行排序，经过初试建堆后关键码值 A 在序列中的序号是【】。
(A) 1 (B) 4 (C) 8 (D) 126. 栈和队列的共同特点是【】。
(A) 只允许在端点处插入和删除元素 (B) 都是先进后出(C) 都是先进先出 (D) 没有共同点7. 用链接方式存储的队列，在进行插入运算时【】。
中国科学院研究生院程序设计
..........................................中国科学院研究生院2012 年招收攻读硕士学位研究生入学统一考试试题科目名称：程序设计考生须知：1.本试卷满分为 150 分，全部考试时间总计 180 分钟。
2.所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
一、判断题（共10 分，每小题 2 分）(1)Floyd 算法求两个顶点的最短路径时，path k-1一定是path k的子集。
【】(2)在快速排序、堆排序、归并排序和插入排序中，堆排序所需要的附加存储开销最大。
【】(3)用Prim 算法和Kruskal 算法分别构造的图的最小生成树不一定相同。
【】(4)在结点数多于1 的哈夫曼树中不存在度为1 的结点。
【】(5)在长度都为 n 的有序单链表和顺序表上分别做顺序查找，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度相同。
【】二、选择题（共20 分，每题 2 分）1、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储【】。
A．数据的操作方法B．数据的存取方法C．数据元素之间的关系D．数据元素的类型2、程序段for ( i=n-1; i>1; i-- )for ( j=1; j<i; j++ )if (A[j]>A[j+1])A[j]与A[j+1]对换;其中n 为正整数，则最后一行的语句频度在最坏情况下是【】。
A．O(n) B．O(n2) C．O(n log2n) D．不直接依赖于n3、在顺序表的动态存储定义中需要包含的数据成员是【】I．数组基址base II．表中元素个数nIII．数组指针*data IV．表的大小maxSizeA．II 、III B．I、II、III C．II、III、IV D．全部需要4、对于一个线性表既要能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应选用【】A．链式存储方式B．顺序存储方式C．散列存储方式D．以上均可以5、3 个数顺序（依次）进栈，出栈序列有【】种。
2012年-2013年中国科学院大学计算机技术基础考研真题试题试卷汇编
第 1 页，共 12 页
芝士传媒 × 题源库
...让知识更美味...
中国科学院研究生院 2012 年招收攻读硕士学位研究生入学统一考试试题 科目名称：计算机技术基础
考生须知：
1．本试卷满分为 150 分，全部考试时间总计 180 分钟。 2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
芝士传媒 × 题源库
...让知识更美味...
目 录
2012 年中国科学院大学计算机技术基础考研真题试题试卷········································ 2 2013 年中国科学院大学计算机技术基础考研真题试题试卷········································ 6
u p1 , u p2 , , u pn 当且仅当序列 1,2, , n 可通过一个栈得到序列 p1 , p2 , , pn 。
六、（12 分）假设以三元组 (F, C, L/R) 的形式输入一棵二叉树的各条边（其中 F 表示父结点标识，C 表示子结点标识，L/R 表示 C 为 F 的左子结点或右子 结点） ，且在输入的三元组序列中，C 是按层次顺序出现的。设结点的标识 是字符类型。F=’^’时 C 为根结点标识，若 C 也为’^’，则表示输入结束。试 根据上述信息完成下列各题。 1. （4 分）已知一组有效的三元组输入序列为：^AL ABL ACR BDL BER CFR EGL EHR FIL ^^L，请画出其所对应的二叉树； 2. （8 分）试编写算法，由输入的三元组序列建立二叉树的二叉链表。
...让知识更美味...
2. 3. 4.
处于同一个进程中的多个线程， CPU 寄存器对于每个线程来说是私有的。 从一个小根堆中查找具有给定键值的元素，在最坏情况下需要 lgn 次比 较操作。 Huffman 树的结点个数一定是偶数。
2013年计算机考研专业课真题及答案
考研专业课复习是考研备考中至关重要的一环，真题是必不可少的备考资料。
中公考研为大家整理了2013年计算机考研专业课真题及答案，供大家下载使用，并且提供计算机考研专业课辅导，更多真题敬请关注中公考研网！2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项符合试题要求。
1.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是A.()OnB. ()OmnC. (min(,))OmnD. (max(,))Omn2.一个栈的入栈序列为1,2,3, ,n，其出栈序列是123,,, ,npppp。
若23p，则3p可能取值的个数是A. 3nB. 2nC. 1nD. 无法确定3.若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是A. 0B. 1C. 2D. 34.已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权（外部）路径长度最小是A. 27B. 46C. 54D. 565.若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是A.X的父结点B. 以Y为根的子树的最左下结点C. X的左兄弟结点YD. 以Y为根的子树的最右下结点6.在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。
下列关于T1与T3的叙述中，正确的是I. 若v是T1的叶结点，则T1与T3不同II. 若v是T1的叶结点，则T1与T3相同III. 若v不是T1的叶结点，则T1与T3不同IV. 若v不是T1的叶结点，则T1与T3相同A.仅I、IIIB. 仅I、IVC. 仅II、IIID. 仅II、IV7.设图的邻接矩阵A如下所示。
各顶点的度依次是0101001101001000AA. 1，2，1，2B. 2，2，1，1C. 3，4，2，3D. 4，4，2，28.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是A.h，c，a，b，d，e，g，fB. e，a，f，g，b，h，c，dB.C. d，b，c，a，h，e，f，g D. a，b，c，d，h，e，f，g9.下列AOE网表示一项包含8个活动的工程。
2013计算机考研真题及参考答案完整版
2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m +n 的降序链表，则最坏情况下的时间复杂度是（ ）。
A ．()O n B ．()O m n ⨯ C ．(min(,))O m n D ．(max(,))O m n 2．一个栈的入栈序列为1,2,3,,n ，其出栈序列是123,,,,n p p p p 。
若23p =，则3p 可能取值的个数是（ ）。
A ．3n -B ．2n -C ．1n -D ．无法确定3．若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）。
A ．0B ．1C ．2D ．34．已知三叉树T 中6个叶结点的权分别是2，3，4，5，6，7，T 的带权（外部）路径长度最小是（ ）。
A ．27B ．46C ．54D ．565．若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）。
A ．X 的父结点B ．以Y 为根的子树的最左下结点C ．X 的左兄弟结点YD ．以Y 为根的子树的最右下结点6．在任意一棵非空二叉排序树T 1中，删除某结点v 之后形成二叉排序树T 2，再将v 插入T 2形成二叉排序树T 3。
下列关于T 1与T 3的叙述中，正确的是（ ）。
I ．若v 是T 1的叶结点，则T 1与T 3不同II ． 若v 是T 1的叶结点，则T 1与T 3相同III ．若v 不是T 1的叶结点，则T 1与T 3不同IV ．若v 不是T 1的叶结点，则T 1与T 3相同A ．仅I 、IIIB ．仅I 、IVC ．仅II 、IIID ．仅II 、IV7．设图的邻接矩阵A 如下所示。
各顶点的度依次是（ ）。
2013考研计算机真题及答案解析(详细)
10．在一棵高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（
11．对给定的关键字序列 110，119，007，911，114，120，122 进行基数排序，则第 2 趟分 ） 。 B．007，110，119，114，911，122，120 D．110，120，911，122，114，007，119
18． 某 CPU 主频为 1.03 GHz， 采用 4 级指令流水线， 每个流水段的执行需要 1 个时钟周期。
第 3 页 共 15 页
假定 CPU 执行了 100 条指令，在其执行过程中，没有发生任何流水线阻塞，此时流水线的吞吐率为 （ ） 。 A．0.25×109 条指令/秒 C．1.0×109 条指令/秒 A． PCI I．磁盘镜像 A．仅 I、II 和 IV 21．某磁盘的转速为 10 000 转/分，平均寻道时间是 6 ms，磁盘传输速率是 20 MB/s，磁盘 控制器延迟 为 0.2 ms，读取一个 4 KB 的扇区所需的平均时间约为（ A．9 ms B．9.4 ms ） 。 D．12.4 ms ） 。 C．12 ms B． USB II．条带化 B．仅 I、III B．0.97×109 条指令/秒 D．1.03 ×109 条指令/秒 ） 。 C． AGP ） 。 IV．增加 Cache 机制 D．仅 II、III III．奇偶校验 D． PCI-Express
19．下列选项中，用于设备和设备控制器（I/O 接口）之间互连的接口标准是（ 20．下列选项中，用于提高 RAID 可靠性的措施有（
C．仅 I、III 和 IV
22．下列关于中断 I/O 方式和 DMA 方式比较的叙述中，错误的是（
A．中断 I/O 方式请求的是 CPU 处理时间，DMA 方式请求的是总线使用权 B．中断响应发生在一条指令执行结束后，DMA 响应发生在一个总线事务完成后 C．中断 I/O 方式下数据传送通过软件完成，DMA 方式下数据传送由硬件完成 D．中断 I/O 方式适用于所有外部设备，DMA 方式仅适用于快速外部设备 23．用户在删除某文件的过程中，操作系统不可能执行的操作是（ A．删除此文件所在的目录 C．删除与此文件对应的文件控制块 （ ） 。 A．连续结构 引结钩 25．用户程序发出磁盘 I/O 请求后，系统的处理流程是：用户程序→系统调用处理程序→设 备骆动程 序→中断处理程序。其中， 计算数据所在磁盘的柱面号、 磁头号、 扇区号的程序是（ A．用户程序 C．设备驱动程序 文件长度 无关的因素是（ A．索引结点的总数 C．地址项的个数 ） 。 B．间接地址索引的级数 D．文件块大小 B．系统调用处理程序 D．中断处理程序 ） 。 B．链式结构 C．直接索引结构 D．多级索 ） 。 B．删除与此文件关联的目录项 D．释放与此文件关联的内存级冲区
2013计算机考研真题及答案解析
2013 年全国硕士研究生入学统一考试—计算机专业基础综合试题2013 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题（科目代码 408）12013 年全国硕士研究生入学统一考试—计算机专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．求整数n(n≥0)阶乘的算法如下，其时间复杂度是int fact(int n){if (n<=1)return 1;return n*fact(n-1);}A. O(log2n)B. O(n)C. (nlog2n)D. O(n2)2．已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。
将中缀表达式a+b-a*((c d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+ 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是A. 5B. 7C. 8D. 113.若一棵二叉树的前序遍历序列为a, e, b, d, c，后序遍历序列为b, c, d, e, a，则根结点的孩子结点A.只有eB.有e、bC.有e、cD.无法确定4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为A. 10B. 20C. 32D. 335．对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是A. O(n)B. O(e)C. O(n+e)D. O(n*e)6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是A.存在，且唯一C.存在，可能不唯一B.存在，且不唯一D.无法确定是否存在7．对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是22013 年全国硕士研究生入学统一考试—计算机专业基础综合试题A.d,e,fB.e,d,fC. f,d,eD.f,e,d8．下列关于最小生成树的说法中，正确的是I.最小生成树树的代价唯一II.权值最小的边一定会出现在所有的最小生成树中III.用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV.普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A.仅IB.仅IIC.仅I、IIID.仅II、IV9．设有一棵3阶B树，如下图所示。
2013年中国科学院大学考研真题计算机技术基础硕士研究生专业课考试试题
中国科学院大学2013年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机技术基础考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。
2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
一、单选题（每小题2分，共80分）1.操作系统负责管理和控制计算机系统的__________。
A. 软件资源B. 硬件资源和软件资源C. 对用户有用的资源D. 硬件资源2.UNIX操作系统产生于__________年。
A. 1965B. 1970C. 1973D. 19753.进程和程序的本质区别是_____________。
A. 前者分时使用CPU，后者独占CPUB. 前者存储在内存，后者存储在外存C. 前者在一个文件中，后者在多个文件中D. 前者是动态的，后者是静态的4.__________置换算法会产生Belady现象。
A. 最不常用B. 先进先出C. 最近最久未使用D. 最佳5.下列关于管程的叙述中，错误的是___________。
A. 管程有数据结构，但不包含对数据的操作B. 管程内部定义函数的具体实现对于外部来说是不可见的C. 管程是一个基本程序单位，可以单独编译D. 管程中引入了面向对象的思想6.如果P、V操作的信号量S的初值为3，当前值为-2，则表示有_______个等待进程。
A. 0个B. 1个C. 2个D. 3个7.进程和线程的本质区别是___________。
A. 前者存储在外存，后者存储在内存B. 前者有地址空间，后者没有地址空间C. 前者在一个文件中，后者在多个文件中D. 前者是拥有资源的基本单位，后者是程序执行的基本单位8.关于线程的优点，描述不正确的是___________。
A. 线程是具有最少开销的程序执行实体B. 撤销线程比撤销进程花费的时间短C. 线程间切换比进程间切换花费的时间短D. 由于共享资源，一个进程中的线程不能并发执行9.关于内核线程和用户线程，描述不正确的是___________。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
科目名称：程序设计
第2页 共4页
4、 设关键字序列为 ｛3， 7， 6， 9， 7， 1， 4， 5， 20｝ ， 对其进行排序的最小交换次数是 【
】 。
5、将一个
的对称矩阵 A 的下三角部分按行存放在一个一维数组 B 中，A[0] [0]存放于 】 。
B[0]中，那么第 i 行的对角元素 A[i] [i]在 B 中的存放位 共4页
3、对一个具有 7 个记录的文件进行快速排序，回答下面的问题： （1）在最好的情况下需要进行多少次比较？说明理由，并给出一个最好情况下初始排列的 实例； （2）在最坏的情况下需要进行多少次比较？为什么？并给出此时的一个实例。
4、 设 n 为正整数，分析如下程序段中加下划线的语句的执行次数。 int i, j, k, x=0, y=0; for (i=1; i<=n; i++) for(j=1; j<=i ; j++) for(k=1; k<=j ; k++) x=x+y;
6、在一棵度为 4 的树中，有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点， 10 个度为 1 的结点，则树中度为 0 的结点个数为【 】 。 7、在 n 个结点的线索二叉树中，线索的数目是【 】 。
8、由权值为 8，4，5，7 的 4 个叶结点构造一棵 Huffman 树，该树的带权路径长度为 【 】 。 9、中缀表达式 A-(B+C/D)*E 的后缀形式是【 】 。
(5) 在长度都为 n 的有序单链表和顺序表上分别做顺序查找，若查找每个元素的概率相等， 则顺序查找表中任一元素的查找成功的平均查找长度相同。 【 】
二、选择题（ 选择题（共 20 分，每题 2 分）
1、若想把数组中的 100 个元素调整为小根堆（或大根堆） ，需做【 】次关键字值比较。 A．164 B．195 C．220 D．257 2、执行下面的程序段，语句 3 的执行次数为【 】 。 for (i=0; i<=n-1; i++) (1) for (j=n; j>i; j--) (2) state; (3) B． ( n − 1)(n + 2) / 2 A． n(n + 2) / 2 C． n(n + 1) / 2 D． (n − 1)(n + 2) 3、如果具有 n 个顶点的图是一个环，则它有【 】棵生成树。 A． n B．2n C．n-1 D．n+1 4、下面关于 B 树和 B+树的叙述中，不正确的是【 】 A. B 树和 B+树都是平衡的多分树 B. B 树和 B+树都是可用于文件的索引结构 C. B 树和 B+树都能有效地支持顺序检索
10、当一个有 N 个顶点的图用邻接矩阵 A 表示时，顶点 Vi 的度为【 A．
】 。
∑ A[i, j ]
i =1 n
n
B．
∑ A[i, j ]
j =1 n
n
C．
∑ A[ j, i]
i =1
Ｄ．
∑ A[i, j ] + ∑ A[ j, i]
i =1 j =1
n
三．填空题（ 填空题（共 20 分，每空 2 分）
中国科学院大学 中国科学院大学 201 2013 年招收攻读硕士学位研究生入学统一考试试题 科目名称： 科目名称：程序设计
考生须知： 考生须知：
1．本试卷满分为 150 分，全部考试时间总计 180 分钟。 2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
一、判断题（ 判断题（共 10 分，每小题 2 分）
科目名称：程序设计
第1页 共4页
D. B 树和 B+树都能有效地支持随机检索 5、若一棵二叉树具有 10 个度为 2 的结点，则该二叉树的度为 0 的结点个数是【 A. 9 B. 11 C. 12 D. 不确定 6、含有 12 个结点的平衡二叉树的最大深度为【 A．3 B．4 C．5 】 。 D．6 】
7、若用数组名作为函数调用的实参，则传递给形参的是【 】 。 A． 数组的首地址 B． 数据第一个元素的值 C． 数组中全部元素的值 D． 数组元素的个数 8、设待排序关键码序列为{25，18，9，33，67，82，53，95，12，70}。要按关键码值递增 的顺序进行排序， 采取以第一个关键码为分界元素的快速排序法， 第一趟排序完成后关键码 95 被放置在第几个位置？【 】 。 A．7 B．8 C． 9 D．10 9、能有效缩短关键路径长度的方法是【 】 。 A．缩短任意一个活动的持续时间 B．缩短关键路径上任意一个关键活动的持续时间 C．缩短多条关键路径上共有的任意一个关键活动的持续时间 D．缩短所有关键路径上共有的任意一个关键活动的持续时间
四、问答题（ 问答题（共 50 分，每题 10 分）
1、试利用 Dijkstra 算法求下图中从顶点 a 到其它各顶点间的最短路径，写出执行算法过程 中各步的状态。
2、在地址空间为 0~16 的散列区中，对以下关键字序列构造两个哈希表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） (1) 用线性探测开放定址法处理冲突； (2) 用链地址法处理冲突； 并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。 设哈希函数为 i / 2 H(x)= ,其中 i 为关键字中第一个字母在字母表中的序号。
(1) 在快速排序、 堆排序、 归并排序和插入排序中， 堆排序所需要的附加存储开销最大。 【 (2) 图的深度遍历不适用于有向图。 【 】 】 】 】
(3) 用 Prim 算法和 Kruskal 算法分别构造的图的最小生成树不一定相同。 【
(4) 对一个具有 n 个元素的线性表，建立其有序单链表的时间复杂度为 O(n)。 【
1 、设 m 、 n 、 a 、 b 、 c 均为 int 型变量且 m=2 ， n=1 ， a=1 ， b=2 ， c=3 ，则执行表达式 d=(m=a!=b)&&(n=b>c)后，n 的值为【 】 ；m 的值为【 】 。 2、前序遍历序列和中序遍历序列相同的二叉树为【 】 。
3、有关键码值为 10、20、30 的三个结点。按所有可能的插入顺序去构造二叉排序树，能构 造出【 】棵不同的二叉排序树。