科目名称：计算机学科综合(专业)第1页共8页中国科学院大学2015年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机学科综合(专业)考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。一、单项选择题：第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1．下列数据结构中，（）是非线性数据结构。A．栈B.队列C.二叉树D.堆2．在非空双向循环链表中q所指的结点后插入一个由p所指的链结点的过程依次为：rlink(p)<-rlink(q);rlink(q)<-p;llink(p)<-q;()A.rlink(q)<-pB.rlink(llink(p))<-pC.llink(rlink(p))<-pD.rlink(rlink(p))<-p3.若一个栈以向量V[1…n]存储，初始栈顶指针top为n+1，则下面x入栈的正确操作是（）。A．top=top+1;V[top]=xB.V[top]=x;top=top+1C.top=top-1;V[top]=xD.V[top]=x;top=top-14.若6行5列的数组以行序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是（）。A.1040B.1042C.1026D.以上答案都不对5．A[N,N]是对称矩阵，将下三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。A.i(i-1)/2+jB.j(j-1)/2+iC.i(j-i)/2+1D.j(i-1)/2+16.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。A．CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEGB7.有n(n>0)个分支结点的满二叉树的深度是（）。科目名称：计算机学科综合(专业)第2页共8页A．n2-1B.log2(n+1)+1C.log2(n+1)D.log2(n-1)8.无向图G=(V,E)，其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历，得到的顶点序列正确的是（）。A．a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b9.设哈希表长M=14，哈希函数H(KEY)=KEYmod7。表中已有4个结点：ADDR(15)=1,ADDR(38)=3,ADDR(61)=5;ADDR(84)=0,其余地址为空。如用二次探测再哈希法解决冲突，关键字为68的结点的地址是（）。A.8B.3C.5D.610.对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是（）：A．05，46，13，55，94，17，42B.05，13，17，42，46，55，94C．42，13，94，05，55，46，17D.05，13，46，55，17，42，9411.下列序列中，（）是执行第一趟快速排序后所得的序列。A．[68，11，18，69][23，93，73]B.[68，11，69，23][18，93...
