中科院程序设计样题

科目名称：程序设计第1页共4页中国科学院大学2016年招收攻读硕士学位研究生入学考试试题样题（非全日制）科目名称：程序设计考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。一、判断题（共10分，每小题2分）(1)数据元素是数据的基本单位，数据元素可以由数据项组成，数据项是数据的最小单位。【】(2)在快速排序、堆排序、归并排序和插入排序中，堆排序所需要的附加存储开销最大。【】(3)若一个有向图的邻接矩阵为下三角，且主对角线上的元素全为零，则该有向图不含回路。【】(4)在结点数多于1的哈夫曼树中不存在度为1的结点。【】(5)由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。【】二、选择题（共20分，每题2分）1、下列哪种值赋给指针变量时，可能会出错【】。A．地址B．NULLC．数组名D．变量名2、对于一个具有n个顶点e条边的无向图，若采用邻接表表示，则表向量的大小为【】。A．nB．n+1C．n-1D．n+e3、在双向链表中，如果要在指针p所指的结点后插入q所指的新结点，下面哪个操作序列是正确的？【】A．prlinkllink=q；prlink=q；qllink=p；qrlink=prlink；B．pllinkrlink=q；pllink=q；qrlink=p；qllink=pllink；C．qllink=p；qrlink=prlink；prlinkllink=q；prlink=q；D．qrlink=p；qllink=pllink；pllinkrlink=q；pllink=q；科目名称：程序设计第2页共4页4、下列程序的时间复杂性为【】。i=0;s=0;while(sn){i++;s=s+i;}A．()OnB．(1)OC．()OnD．2()On5、已知10个数据元素（50，30，15，35，70，65，95，60，25，40），按照依次插入结点的方法生成一棵二叉排序树后，在检索成功的情况下，检索每个元素的平均比较次数（或称为平均检索长度）为【】。A．2.5B．3.2C．2.9D．2.76、下面这段程序运行的正确结果是【】。intmain(){fun();fun();}voidfun(){staticinta=1;inti=5;a++;i++;printf(i=%d,i);printf(,a=%d,a);}A．i=6,a=2i=7,a=3B．i=6,a=2i=6,a=3C．i=6,a=1i=6,a=2D．i=6,a=1i=7,a=17、若用数组名作为函数调用的实参，则传递给形参的是【】。A．数组的首地址B．数据第一个元素的值C．数组中全部元素的值Ｄ．数组元素的个数8、设有如下定义：structsk{intm;floatx;}data,*ptr;若要使ptr指向data中的m域，则正确的赋值语句是【】。A．ptr=&data.m;B．*ptr=data.m;C．ptr=(structsk*)&data.m;D．ptr=(structsk*)data.m9、对包含n个元素的散列表进行检索，平均检索长度【】。A．为O(log2n)B．为O(n)C．为O(n×log2n)D．不直接依赖于n10、若以{4，5，6，3，8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是【】。科目名称：程序设计第3页共4页A55B68C59D28三．填空题（共40分，每空2分）1、一个算法的时间复杂性通常用它相对于问题的规模的【】形式表示。当一个算法的时间复杂性与问题的规模n大小无关时，则表示为【】；成正比关系时，则表示为【】；成对数关系时，则表示为【】；成平方关系时，则表示为【】。2、在顺序表中插入或删除一个元素，需要平均移动【】元素，具体移动的元素个数与【】有关。3、已知一个待散列存储的线性表为（18，34，58，26，75，67，48，93，81），散列函数为()%11hkk=。若采用线性探测法解决冲突，则检索长度为【】；若采用链地址法解决冲突，则平均检索长度为【】。4、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有【】个结点。5、有一个2000项的表，欲采用等分区间顺序方法进行查找，则每块的理想长度为【】，分成【】块最理想，平均查找长度为【】（块内顺序查找）。6、在程序中，通常可采用3种方法实现输入和输出，分别是【】、【】、【】。7、用数组A[1..N]顺序存储完全二叉树的各结点，则当i0，且i＝【】时，结点A[i]的左子女结点为【】，否则结点A[i]没有左子女。8、对n个元素的序列进行冒泡排序，最少的比较次数为【】，最多的比较次数为【】。四、问答题（共40分，每题10分）1.试利用Dijkstra算法求下图中从顶点a到其它各顶点间的最短路径，写出执行算法过程中各步的状态。科目名称：程序设计第4页共4页2.试推导含12个节点的平衡二叉树的最大深度，并画出一棵这样的树。3.在地址空间为0~16的散列区中，对以下关键字序列构造两个哈希表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）(1)用线性探测开放定址法处理冲突；(2)用链地址法处理。并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。设哈希函数为H(x)=2/i,其中i为关键字中第一个字母在字母表中的序号。4.将下列递推过程改写为递归过程。voidditui(intn){inti;i=n;while(i1)printf(i--);}五、写算法（共40分，每题20分）1.若称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判断读入的一个以‘@’为结束符的字符序列是否为“回文”。要求：（1）写出算法的基本思想；（2）用熟悉的程序设计语言实现上述算法。2.试编写一个算法，给有向无环图G中每个顶点赋以一个整数序号，并满足一下条件：若从顶点i至顶点j有一条弧，则应使ij。要求：（1）写出算法的基本思想；（2）用熟悉的程序设计语言实现上述算法。