办学单位： 年级专业： 姓名： 学号： 成绩：
广会科学大学 2012学年第 一 学期期末试卷 《数据结构》 专科 试卷（A卷） （本试卷共有 五 大题，满分 100 分，考试时间 100 分钟）
题号 一 二 三 四 五 总分 核分人 得分
评卷人
一、判断题（每题1分，共10分）
题号 1 2 3 4 5 6 7 8 9 10 答案 × √ × √ √ × × √ √ × 二、填空题（每小题2分，共20分） 1、__联系___、 图或图的结构 2、_3_、_3_
3、__有序__、__N-1__ 4、___尾___、 首
5、 有序序列 、 后缀表达式 6、 归并
7、有向无回路 8、__e___、__2e___ 9、 进栈和退栈 10、 12
三、单项选择题（每题2分，共30分）
题号 1 2 3 4 5 6 7 8 9 10 答案 D C A C A A D D B B 题号 11 12 13 14 15 答案 D D D B B 四、解答题（每小题5分，共10分）
1、
（a）
（b）
（c） （d） （e）
评分标准：画出一个得1分。
第 1 页 共 2 页
2、
c1:10 c2:1111 c3:01 c4:1110 c5:110 c6:00 评分标准：画出赫夫曼树得2分，每写出一个赫夫曼编码得0.5分。
五、算法分析题（每小题10分，共30分）
1、前序：ABDECF 中序：DBEACF 后序：DEBFCA 评分标准：写出一个得3分
2、（1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,…,an,a1） 评分标准：写出一点得3分
3、typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) {
lklist *p,*q,*t;
for(p=ha,hc=0;p!=0;p=p->next)
{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } }
评分标准：1、定义三个变量lklist *ha,lklist *hb,lklist *&hc得3分； 2、写出循环体for(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } 得6分
第 2 页 共 2 页
