学海网

共10页。
2004北京大学软件与微电子学院研究生入学试题
一. 选择题（１５分）
1.在双向循环链表中，在p所指的结点之后插入指针f所指的结点，其操作是（）
A.p-﹥rlink=f; f-﹥rlink=p; (p-﹥rlink)-﹥llink=f; f-﹥rlink=p-﹥rlink
B.p-﹥rlink=f; (p-﹥rlink)-﹥llink=f; f-﹥llink=p; f-﹥rlink=p-﹥rlink
C.f-﹥llink=p; f-﹥rlink=p-﹥rlink; p-﹥rlink=f; (p-﹥rlink)-﹥llink=f
D.f-﹥llink=p; f-﹥rlink=p-﹥rlink; (p-﹥rlink)-﹥llink=f; p-﹥rlink=f
解答: 本题可参见教材P30中关于双链表的插入和删除过程, 答案选(D)
2.有如下递归函数fac(n),其时间复杂度为（）
int fact(int n)
{
if(n==0)
return 1;
else
return(n*fact(n-1));
}
A.O(n) B.O(n^2) C.O(n^3) D.O(n^4)
解答: f(n)=c+f(n-1)
通过递归扩展, 层层递归直至递归出口, 得f(n)=cn，因此时间复杂度为0(n), 答案选(A)
3.设环形队列中数组的下表范围是１～n ，头尾指针分别为f和r，则其元素个数为：（）