中科大软件学院资料

中科大软件学院资料大全
QQ资料群：329852581
[size=16.0000pt]1.《科大软院学长讲真题》先睹为快

中科大软件学院研究生入学考试专业课

（第一部分）数据结构（40分）

考点分布（2017版）

2010

解答题：
[size=14.0000pt]1.设计在链式存储结构上合并排序的算法。

解析：参考2011年和2015考过的链表合并题。科大软院在相同的知识点上总是变换着考，所有看真题需要多留意。

参考代码：
file:///C:\Users\WQS\AppData\Local\Temp\ksohtml\wpsB6D9.tmp.pngVoid mergelklist(lklist *ha,lklist *hb,lklist *&hc)
    {
       lklist *s=hc=0;
       while(ha!=0 && hb!=0){
         if(ha->data<hb->data){
           if(s==0)hc=s=ha;
           else {s->next=ha; s=ha;};
           ha=ha->next;
           }
         else {
           if(s==0) hc=s=hb;
           else{s->next=hb; s=hb;};
           hb=hb->next;
           }   
           }
       if(ha==0) s->next=hb;
       else s->next=ha;
   }

2011

3对于单链表表示法，以下说法错误的是__________。
A.指向链表的第一个结点的指针，称为头指针
B.单链表的每一个结点都被一个指针所指
C.任何结点只能通过指向它的指针才能引用
D.尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表
[size=10.5000pt]
解析：D 链表由头指针唯一确定,单链表可以用头指针的名字来命名
[size=10.5000pt] 4.设rear是指向非空带头结点的循环单链表的尾指针，则删除表首结点的操作可表示为____。
A.p=rear; rear=rear->next; free (p)
B.rear=rear->next; free(rear);
C.rear=rear->next->next; free(rear);
D.p=rear->next->next; rear->next->next=p->next; free(p);

解析：D ,这道题关键是弄明白循环单链表的尾指针指向的下一个元素是谁，
（1）如果是带有头结点的链表，那么指向的就是头结点，
（2）如果不带头结点，就是链表的第一个元素，
（3）本题中带有头节点，所以rear尾指针的下一个元素是头节点，头节点下一个元素是表首节点。

题目补充：
1.带有头结点的单向循环链表L(L为头指针)中,指针p所指结点为尾结点的条件是__________.

答案：p->next=L;

考点1.7【★★★】理解树的概念和基本术语

考点1.7.1理解树的概念和基本术语；掌握二叉树的概念、存储结构和遍历

2010

选择题：
[size=14.0000pt]7.设F是由T1，T2和T3三棵树组成的森林，与F对应的二叉树为B,T1，T2和T3的结点数分别为N1，N2和N3，则二叉树B的根节点的左子树结点数为（）。
[size=14.0000pt]A.N1-1                     B.N2-1
C.N2+N3                    D.N1+N3
[size=10.5000pt]
解析：B的左孩子其实就完全由T1构成的，根据孩子兄弟存储结构，减去T1这个根节点，所以节点个数是N1-1，选A

解答题：
[size=16.0000pt]2.设计计算二叉树中所有结点值之和的算法

解析：运用递归的思想，二叉树的所有节点之和=左孩子节点之和+右孩子节点之和+该节点的值。
参考代码：