……………………………………………线………………………………………订………………………………………装…………………………………………………攀枝花学院考试试卷 2015～2016学年度第二学期
《数据结构》试卷（A卷） 评阅标准及考核说明
适用年级专业：适用年级专业：2014级计算机科学与技术、软件工程、网络工程、信息与计算科学
考 试 形 式：（ ）开卷、（ ? ）闭卷
得分 阅卷人 一、[教师答题时间：8分钟]单项选择题（每个小题2分，共30分。）
1、[三基类]C 2、[三基类]D 3、[三基类]C 4、[三基类]D 5、[三基类]B 6、[三基类]A 7、[三基类]B 8、[三基类]C 9、[三基类]C 10、[三基类]D 11、[三基类]D 12、[三基类]A 13、[三基类]A 14、[三基类]B 15、[三基类]A
得分 题号 答案 得分 阅卷人 阅卷人 1 √ 二、[三基类] [教师答题时间：5分钟]判断题（每个小题1分，共10分。正确的划√，错误的划×）
2 × 3 √ 4 √ 5 √ 6 × 7 × 8 × 9 √ 10 × 三、填空题（每空1分，共15分）
1、[三基类] [教师答题时间：1 分钟] 链式 、索引
2、[三基类] [教师答题时间：0.5 分钟] p->next!=null 3、[三基类] [教师答题时间： 1 分钟] _ O(1)__、 __O(n)__ 4、[三基类] [教师答题时间：0.5 分钟] 栈顶 、栈底 5、[三基类] [教师答题时间：0.5 分钟]堆分配存储 6、[三基类] [教师答题时间：1 分钟] 400 、 399 7、[三基类] [教师答题时间：1 分钟] 邻接表、邻接矩阵 8、[三基类] [教师答题时间：1 分钟] 8662
9、[三基类] [教师答题时间：0.5 分钟] 比较 、 移动 得分 阅卷人 四、简答题（5个小题，每个小题6分，共30分）
1、（6分）[一般综合型] [教师答题时间：3 分钟] 答：（1）生成的二叉树如下图所示（4分）：
AB CD E FG H（2）后序遍历序列为：GDBEHFCA （2分） 2、（6分）[一般综合型] [教师答题时间：3 分钟]
答 ：(1) 一棵哈夫曼树如右图所示（答案不唯一）（4分）： （2）各字符的哈夫曼编码如下（2分）： A：01 B：10 C：11 D：000 E：001
0 0.13 D 0 0.25 1 0.53 0 1 0.28 A 0.12E 1 0 0.25 B 1 0.47 1 0.22 C 3、（6分）[一般综合型] [教师答题时间：3 分钟]答： 答：（1）最后得到的哈希表示意图如下表所示（4分）： 地址编号 16 3 7 29 8 0 关键字值 11 22 47 92 （2）ASL＝（1+2+1+1+1+4+1+2+2）/9＝5/3=1.67（2分） 4、（6分）[一般综合型] [教师答题时间：3 分钟]
答：根据算法思想，从顶点1出发得到的深度优先生成树和广度优先生成树如下。 （1）深度优先生成树（3分） （2）广度优先生成树（3分） ⑧ ③ ① ④ ② ⑥ ⑤ ⑦ ① ④ ② ⑥ ⑤ ⑦ ⑧ ③ 5、（6分）[一般综合型] [教师答题时间：3 分钟]答：
答：（1）每趟排序的结果序列为：
初态： 14，17，16，30，17*，28，8，25，15，20，2 （1分）
第一趟（Dk=5）: 2，8，5，15，17*，14，17，25，30，20，28 （1分） 第二趟（Dk=3）：2，8，5，15，17*，14，17，25，30，20，28 （1分） 第三趟（Dk=1）：2，5，8，14，16，17*，17， 20，25，28，30 （1分） （2）希尔排序不是稳定的排序，因为值相同的两个关键字17和17*在排序前后位置发生
了改变。（2分）
得分 阅卷人 五、算法题（本题含2小题，共15分）
1、（6分） [综合型] [教师答题时间：5分钟]：
（1） high （1.5分） （2） high （1.5分） （3） low （1.5分） （4） low （1.5分）
2、（9分）[综合型] [教师答题时间：5分钟]参考答案:(本题答案不唯一) void delete（Linklist &L）
∥L是带头结点的单链表，本算法删除其最小值结点。
{ p=L->next； ∥p为工作指针。指向待处理的结点。假定链表非空。 （1分） pre=L； ∥pre指向最小值结点的前驱。 （1分） q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。（1分）
while（p->next!=null） （1分） { If（p->next->data
{ pre=p； （1分） q=p->next； （1分） } ∥查最小值结点
p=p->next； ∥指针后移。 （1分） }
pre->next=q->next；∥从链表上删除最小值结点 （1分） free（q）； ∥释放最小值结点空间 （1分） }∥结束算法delete。
攀枝花学院数据结构—2016—答案A
