攀枝花学院-数据结构—2016—答案(A).doc

《攀枝花学院-数据结构—2016—答案(A).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、……………………………………………线………………………………………订………………………………………装…………………………………………………线………………………………攀枝花学院考试试卷2015～2016学年度第二学期《数据结构》试卷（A卷）评阅标准及考核说明适用年级专业：适用年级专业：2014级计算机科学与技术、软件工程、网络工程、信息与计算科学考试形式：（）开卷、（Ö）闭卷得分阅卷人一、[教师答题时间：8分钟]单项选择题（每个小题2分，共30分。）1、[三基类]C2、[三基类]D3、[三基类]C4、[三基类]D5、[三基类]B6、[三基类]A7、[三基类]B8、[三基类]

2、C9、[三基类]C10、[三基类]D11、[三基类]D12、[三基类]A13、[三基类]A14、[三基类]B15、[三基类]A得分阅卷人二、[三基类][教师答题时间：5分钟]判断题（每个小题1分，共10分。正确的划√，错误的划×）题号12345678910答案√×√√√×××√×得分阅卷人三、填空题（每空1分，共15分）1、[三基类][教师答题时间：1分钟]链式、索引2、[三基类][教师答题时间：0.5分钟]p->next!=null3、[三基类][教师答题时间：1分钟]_O(1)__、__O(n)__4、[三基类][教师答题时间：0.5分钟]栈顶、栈底5、[三基类][教

3、师答题时间：0.5分钟]堆分配存储6、[三基类][教师答题时间：1分钟]400、3997、[三基类][教师答题时间：1分钟]邻接表、邻接矩阵8、[三基类][教师答题时间：1分钟]86629、[三基类][教师答题时间：0.5分钟]比较、移动得分阅卷人四、简答题（5个小题，每个小题6分，共30分）1、（6分）[一般综合型][教师答题时间：3分钟]答：（1）生成的二叉树如下图所示（4分）：（2）后序遍历序列为：GDBEHFCA（2分）2、（6分）[一般综合型][教师答题时间：3分钟]A000011110.250.250.1220.470.280.220.5310.13DEBC答

4、：(1)一棵哈夫曼树如右图所示（答案不唯一）（4分）：（2）各字符的哈夫曼编码如下（2分）：A：01B：10C：11D：000E：0013、（6分）[一般综合型][教师答题时间：3分钟]答：答：（1）最后得到的哈希表示意图如下表所示（4分）：地址编号012345678910关键字值112247921637298（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、③④⑤⑥⑦⑧③④⑤⑥⑦⑧②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分）得分阅卷人五、算法题（本题含

6、2小题，共15分）1、（6分）[综合型][教师答题时间：5分钟]：（1）high（1.5分）（2）high（1.5分）（3）low（1.5分）（4）low（1.5分）2、（9分）[综合型][教师答题时间：5分钟]参考答案:(本题答案不唯一)voiddelete（Linklist&L）∥L是带头结点的单链表，本算法删除其最小值结点。{p=L->next；∥p为工作指针。指向待处理的结点。假定链表非空。（1分）pre=L；∥pre指向最小值结点的前驱。（1分）q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。（1分）while（p->next!=null）（1分）

7、{If（p->next->datadata）（1分）{pre=p；（1分）q=p->next；（1分）}∥查最小值结点p=p->next；∥指针后移。（1分）}pre->next=q->next；∥从链表上删除最小值结点（1分）free（q）；∥释放最小值结点空间（1分）}∥结束算法delete。