湖南大学研究生入学考试数据结构真题参考答案（2000、2001、2002、2003、2004、2005、2006、2008、2010年）作者：务殊湖南大学2000年招收攻读硕士学位研究生入学考试试题参考答案招生专业 计算机及其应用 考试科目 数据结构一、 填空题（没空0.5分，共15分）1. 数据元素的有限集 数据元素之间关系的有限集2. 可行性 有穷性 确定性 输入 输出3. O（n） 树的高度4. 2 55. 186 746. 不理解什么意思7. 栈和队列8. 双亲表示法 孩子双亲表示法 孩子兄弟表示法 孩子兄弟表示法9. 叶节点的带权路径长度最短的二叉树10. 活动 先后关系11. 此题都是定义，自己查一下书12. 中序13. 有环14． 堆、归并15. 0或-1或1二、选择填空题（没空1分，共20分）1. ② ④2． ⑤ ③3. ③ ⑥4. ① ③ ② ③5. ④ ⑥ ⑤6. ② ⑥7. ② ③8. ③ ⑥9. ⑤三、用类Pascal定义下列数据类型（每小题5分，共15分）Pascal没用过，略。
四、对题图所示的无向带权图（每小题4分，共12分）1.邻接矩阵2.克鲁斯卡尔算法，过程3.最小生成树代价为 31五、完成下列各题（每小题3分，共12分）1.转换成二叉树2.前序：ABEFGCDHITUMV 中序：EFGBCHIDAMUVT 后序：GFEIHDCBMVUTA3.应该指的是第一题中的二叉树，比较容易，略4.不清楚，略六、算法填空题（每小题6分，共12分）1. cqueut cq,elem x (cq.rear+1)%(m+1) cq.rear+12. sqtack S,elem x S.top==arrmax S.top++七、（没用过PASCAL，就用c语言代写的，思想应该一样的本题14分）void SelectSort(LinkList L){//链表为带头结点的单链表LinkList p,s,pre1,pre2,temp;//p为工作指针，s为已排序表的尾节点指针,s=L; //pre1为temp的前驱指针，pre2为p的前驱指针while(s->next!=NULL){pre1=pre2=s;temp=p=s->next;while(p->next!=NULL){pre2=p;p=p->next;if(texmp->data>p->data){//更新temppre1=pre2; temp=p;}//if}//while//可以交换结点，也可以交换值pre1->next=temp->next; //将temp摘下temp->next=s->next;s->next=temp;//将temp并入有序链表中s=s->next;}//while}//end湖南大学2001年招收攻读硕士学位研究生入学考试试题参考答案招生专业 计算机应用技术 考试科目 数据结构一、填空题（每空1.5分，共15分）1. n-i+12. 前一个位置（此空，值得商榷）3. 后继 前驱4. i(i-1)/2+j5. 896. n-17. n+2e8. n-19. 发生冲突的可能性越小（反之越大）二、判断题（每小题1.5分，共15分）1.错 2.错 3.对 4.错 5.错 6.对 7.对 8.错 9.对 10.对三、单选题（每小题1.5分，共15分）1.C 2.C 3.B 4.B 5.D 6.A 7.D 8.D 9.B 10.C四、解析题（1小题8分，2,3小题各10分，4小题9分，共37分）1.此题比较简单，略。
2.同上，略3.画图简单最小生成树从v0开始，依次加入边为（v0，v2），（v2，v3），（v2，v5），（v4，v5），（v1，v2）4.答：最好采用堆排序方法因为建立初始堆的时间不大于4n，每筛选一个元素花费logn的时间，即总的时间为O（4n+Klogn），为线性复杂度且系数为4.而其它的方法有的需要将整表排完，即时间大于等于O（nlogn），有的也是线性阶，但是系数随着k的增大而增大建堆20次，取出6筛选花5次，7花4次，9花5次，一共34次五、算法设计题（1小题8分，2小题10分，共18分）1.DlinkList Locate(LlinkList L,ElemType x){//假设此双向链表带头结点，返回NULL表示没有找到DlinkList p,s;p=L->next;while(p!=NULL) //查找x元素 if(p->data==x) break;else p=p->next;if(p==NULL) return p; //无x元素返回NULLp->freq++; s=p->prior;while(s！=L) //向前查找频度位置 if(p->freq>=s->freq) s=s->prior; else break;p->rior->next=p->next;if(p->next!=NULL) p->next->prior=p->prior; //删除pp->next=s->next; p->prior=s; //将p插入s的后面s->next=p;if(s->next!=NULL) s->next->prior=p;return p;}//end2.略。
湖南大学2002年招收攻读硕士学位研究生入学考试试题参考答案招生专业 计算机科学及应用技术 考试科目 数据结构一、单选题（每小题2分，共20分）1.D 2.D 3.A 4.D 5.D 6.A 7.C 8.B 9.D 10.C二、判断题（每小题1分，共10分）1.错 2.对 3.对 4.对 5.对6.错（储存结构定下，序列也就唯一了）7.错 8.对 9.错 10.对三、填空题（每空2分，共20分）1. n-i2. 先进先出的线性表3. 1324. 75. i(i-1)/2+j6. 507. n(n-1) n8. 09. 冒泡、快速四、解析题（1小题6分，2、4小题8分，3小题10分，共32分）1. 第一问：顺序的，便于访问 第二问：叶子结点 第三问：数据结构 严蔚敏（c语言版）p282 页脚小字部分2.补充完整后 先序：ABCDEFGHIJK 中序：CBEDFAHJKIG 后序：CEFDBKJIHGA3.第一种：p1p2p3p4p5p6 第二种：p1p4p2p3p5p6 第三种：p1p4p2p5p3p6 第四种：p1p2p4p3p5p64. n=16时的判定树平均查找长度：ASL=(1+2x2+3x4+4x4+5x3+6x2)/16=15/4五、算法设计题（1小题8分，2小题10，共18分）1.BitTree getprePointer(BitTree T){BitTree p=T;if(p==NULL) return NULL;while(1){ while(p->lchild!=NULL) p=p->lchild;if(p->rchild!=NULL) p=p->rchild;else break;}//while return p;}//end2.int Search(SqList L,ElemType key){//顺序表下标为零的位置为存放数据，返回0表示未找到int i;for(i=4;i<=L.length;i+=4) if(key==L.elem[i]) return i; else if(keyL.elem[i-2]?(i-1)(i-3); if(key!=L.elem[i]) i=0;}//elsereturn i;}//ifelse{ //在表尾不足四个元素 for(i-=3;i<=L.length;i++) if(key==L.elem[i]) return i;}//elserturn 0; //既不在表中，也不在表尾}//end湖南大学2003年招收攻读硕士学位研究生入学考试试题参考答案招生专业 计算机应用技术、计算机软件与理论、软件工程硕士 考试科目 数据结构一、单项选择题（每小题1分，共15分）1.A 2.D 3.B 4.C 5.B 6.B 7.A 8.B 9.C 10.D 11.A 12.B 13.A 14.B 15.C二、判断题（每小题1分，共10分）1.对 2.对 3. 错 4.对 5.对 6.错 7.错 8.对 9.错 10.对三、填空题（每空2分，共20分）1. 502. 613. n/2向下取整4. 2（n-1）5. 10,15,126. 607. O(n)8. e9. 0,1,1,210. 10100四、解析题（共55分）1.二叉树为2.证明：①设Va为存在两个孩子的结点，Vb为Va的中序后继，即有Va
同时设Vc为Vb的左孩子，则有Vc=0;i--) L.data[i+1]=L.data[i];return 1;}//end2.int JudgeFibo。