北京交通大学2004年计算机硕士研究生入学考试试卷答案

北京交通大学2004年硕士研究生入学考试试卷答案
一．        单选题       
1.        C  2. B  3. D  4. B  5. C  6. B  7. A  8. A  9. D  10. C  11. D  12. C  13. C  14. A  15. D
二．        填空题
1. O(n**2)   2. ∑pi*(n-i+1) (求和下限i=1,上限n+1)  3. 358  4. 401  5. 稳定  
6. GetHead(GetTail(GetTail(GetTail(GetTail(A)))))  7. +1,   8.  14,  4
三．        判断题
1. 错误     所含数的个数是h或h-1
2. 正确
3. 错误     空间复杂度为O(logn)
4. 错误     242个关键字  （3**5 - 1）
5. 错误     n条
6. 正确
7. 正确
8. 错误     在有向图中
9. 错误     2n-1
10.错误     长度为1
四．        简答题
1.        证明： 设n0,n1,n2,则总结点为
          m=n0+n1+n2=2*n2+n1+1
推出  m=2*n0-1+n1
在完全二叉树中，度为1的结点可能是没有或者仅有一个两种情况
即 n1=0 或 n1=1
当 n1=0时，m=2*n0 -1，m为奇数   所以 n0=(m+1)/2
当 n1=1时，m=2*n0  ， m为奇数   所以 n0=m/2
命题得证
2.
  
五．画图题
1.
   
2.

3.
   
4. bacfde   bafcde   bcafde  bcfade  bfacde  bfcade
六．        阅读程序
1.        通过二叉树的中序和后序序列建立二叉树，每个结点的link1和link2分别指向其左右子树的根结点。

2.        4皇后求解问题，其中任意两个皇后不位于棋盘的同行，同列，同对角线
结果： m=1  2, 4,1,3
m=2  3, 1,4,2
3.        求模式串中的nextval值，并存入数组n[8]中
执行结果： 0 1 1 0 1 3 2
七．        程序填空
1.        (1)cq.elem=0  (2) f=0  (3) (cq.rear+1)%(k+1)  (4) 2*cq.elem[cq.rear]-cq.elem[j]
(5)cq.rear=j    (6) n++
运行结果：0,0,0,1,1,2,4,8,15,29,56,108
2.  (1)q->data=i  (2) p->next=q   (3)p=q   (4)p=p->next  (5)++j  (6)m=code[m-1]
   (7)p->next=q->next  (8) free(q)  (9) return(m)    (10) seq[k]=s->data
八．        写程序
孩子兄弟结构书上有
int  Countleaf(CsNode *T)
   {int leaf; CsNode *T1;
if (!T)   return 0;
else {if (!T->fch) return 1;
    else  { leaf=0; T1=T->fch;
           while (T1)
             {leaf=leaf+Countleaf(T1);
              T1=T1->nsib;
             }
           return leaf;
          }
    }
        }
   本题的详细讲解和另一种算法在05年辅导班有老师详细的讲解！