2010数据结构期末试卷A

浙江大学宁波理工学院200_9_–2010_学年_二_学期

《数据结构（乙）》课程期末考试试卷（A）

开课分院： 信息分院 ，考试形式：开卷

考试日期：__ 2010___年__6__月__ 24__日，考试所需时间： 120 分钟

考生姓名 学号 考生所在分院： 专业班级： . 题序 题型 得分 评卷人 一 问答题 二 程序编写题 总 分 一、简答题（本大题共10小题，每小题2分，共60分）

1.设字符a,b,c,d,e,f,g的使用权值分别是15，5，36，2，22，12，8，画出Huffman树，并写出a,b,c,d,e,f,g的Huffman编码。（6分）

0371001015ae1022012f0702d15b2711518g63136c

2．已知二叉树的先序序列和中序序列分别为ABDHIEJKCFLMG和HDIBJEKALFMCG。（1）画出该二叉树；（2）画出（1）中求得的二叉树对应的森林。(10分)

命题（组）老师签名：____________________ 年 月 日

分院主管教学院长或首席主讲教授签名：_______________ 年 月 日

第1页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

AACGBBFDELHIJKMCDGHIJLEKFM

3．已知AOE网如下图所示，要求完成如下任务：（20分）

V64V21V73V13V479V92V3512V83V56

（1）写出该图的邻接矩阵（3分）

0 3 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ 3 ∞ 4 ∞ ∞ ∞ ∞ ∞ 0 5 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 7 1 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ ∞ 0 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ 9 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 （2）写出该图的邻接表（3分）

第2页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

V1V2V3V4V5V6V7V8 V9 ^V2V4V4V7V8^ V3 ^ V6 ^ V5 ^ V8 ^ V7 ^ V9 ^ V9 ^

（3）写出该图的深度优先遍历序列（2分） V1 V2 V6 V7 V9 V4 V8 V3 V5 （4）写出该图的广度优先遍历序列（2分） V1 V2 V3 V6 V4 V5 V7 V8 V9

（5）求每项事件及活动的最早开始时间及最晚开始时间（6分） E L E L （6）求关键路径及关键路径长度（4分） A2 a5 a8 a11 23

4．将下列关键字序列进行堆排序（大根堆），画出堆排序过程。（10分） 5 56 20 23 40 38 29 61 35 76 28 100

A1 0 1 A2 0 0 A3 3 9 A4 3 4 A5 2 2 A6 2 12 A7 4 13 A8 7 7 A9 7 20 A10 5 15 A11 14 14 A12 11 21 V1 0 0 V2 3 4 V3 2 2 V4 7 7 V5 5 15 V6 4 13 V7 14 14 V8 11 21 V9 23 23 第3页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

510056207638234038296156202961357628100762335402856161385638355620293540202923540285610023528407610040383538352820292328202923561763810055661761003535292829232820523520384056617610040566176100292828202320235353852935384056617610040566176100第4页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

2320520523282935382829353840566176100405661761005202328293538405661761005．二维数组A[1..100 , 1.. 50]它的首地址是1000，记录字段长度为8个字节（每个地址存储一个字节）。请问在行优先和列优先存储方式下A[20,30]它的地址分别是多少？（6分）

行优先：1000+8*（19*50+29）=8832 列优先：1000+8*（29*100+19）=24352

6． 请用顺序栈判断一字符串中“（”和“）”是不是成对，并提示两类错误信息，一是“）”出现在“（”之前，二是缺少多少个“）”。（不需要编栈的基本操作运算函数，直接应用）（8分） I=0;

While (i

Esle if str[i]= =”)” If empty(s)

Printf(“error:)befor (“); I++;} N=0;

While (empty(s)! =0) {pop(s); N++;} If (n!=0)

Printf(“you need %d “)”’,n);

二、程序编写题（本大题共2小题，每小题20分，共40分）

1. 编程实现稀疏矩阵（三元组存储方式）的乘法，C=A*B。（提示：先将B矩阵转置，然后再进行乘法运算）

要求：写出程序流程框图及程序注解。 Trans()

第5页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

{dnum=0;

for(i=1;i

While(num

{if (b.data[num].row==i)

{d.data.[numd].col=b.data[num].row d.data.[numd].row=b.data[num].col d.data.[numd++].x=b.data[num].x } num++;}

d.num=b.num; d.col=b.row; d.row=b.col;}

mulad() {numc=0; c.col=a.col; c.row=d.col;

For(i=1;i

While((numa

Else if(a.data[numa].rowd.data[num].row) numd++; Else temp+=a.data[numa].x*d.data[numd].x; }

If (temp!=0)

{C.data[numc].col=I; c.data[numc].row=j;

c.data[numc++].x=temp;} }

2. 假设已有2个顺序链表分别记录同一专业2个班级的学生，按学号顺序排列，并有一字段记录该学生的智育得分。编程实现输出学生的班级排名和专业排名。（提示：先分别对2个链表进行排序，得到班级排名，然后再将2链表按合并成一个链表得到专业排名） 要求：写出程序流程框图及程序注解。 Linear Sort(linear L) {node p,q,x; Int n=0; P=L->next;

While(P!=NULL) {Q=L-NEXT;

While ((p.data<(q->next).data)&&(p!=q)) Q=q->next; If(p!=q) { X=p;

第6页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

x->next=q->next; q->next=x;} p=p->next;} p=L->next; while (p!=null) {n++;

printf(“ %d %d %d “,n,p.no,p.data); } }

Main() {node p; la=sort(la); Lb=sort(lb); P=la;

While(p->next!=null) P=p->next; p->next=lb; la=sort(la);}

第7页（共7页）

本文来源：https://www.bwwdw.com/article/fx93.html