2022年青岛理工大学数据结构A卷考试题答案 .pdf

青岛理工大学试卷标准答案及评分标准专用纸第 1 页 共 3 页2010_201_学年第2 学期数据结构课程试卷标准答案及评分标准A( )/B( ) 卷专业 计算机科学与技术、软件、网络班级 计算 091-3、网络 091-2、软件 091-2 一、单项选择题（ 1*30=0 分）1A 2D 3D 4B 5B 6C 7C 8D 9A 10B 11B 12A 13C 14B 15B 16B 17A 18B 19C 20C 21B 22C 23B 24D 25B 26C 27A 28B 29B 30B 二、判断题（ 1*10=10 分） 1 2 3 4 5 6 7 8 9 10三、综合题（ 45 分）1二叉排序树如下所示：（8 分）查找成功情况下的平均查找长度为：（ * 3*2+4*2+5*3+6*2）/12=23/6 2二叉树为： （5 分）线索二叉树（ 5 分）红色带箭头的为线索名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 青岛理工大学试卷标准答案及评分标准专用纸第 2 页 共 3 页3哈夫曼树如下（5 分）带权路径长度为：WPL= （4+6+8+10）*4+ （15+20）*3+(23+35)*2=333 (2分) 4. 散列表如下：序号0 1 2 3 4 5 6 7 8 9 10 11 12 值63 27 132 68 95 187 123 70 08 87 47 310 25 次数3 1 1 1 1 1 1 3 1 1 3 1 1 成功查找情况下的平均查找长度为：ASL=（10*1+3*3 ）/13=19/13 5 （1）邻接表如下（2 分）（2）深度优先遍历序列：1，2，3，4，5（2 分）广度优先遍历序列：1，2，4，5，3（2 分）（3）最小生成树： （2 分）最小生成树各边上的权值之和为：10 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 青岛理工大学试卷标准答案及评分标准专用纸第 3 页 共 3 页五、算法设计题（ 7+8=15分）1 （共分）void MergeList_L(LinkList &HA,LinkList &HB,LinkList &HC) /按值递增排序的单链表LA,LB，归并为 LC后也按值递增排序pa=HA-next; pb=HB-next; Lc=pc=HA； /初始化（1 分）while(pa&pb) /将 pa 、pb 结点按大小依次插入C中 if(pa-datadata) （1 分） pc-next=pa; pc=pa; pa=pa-next; （2 分） else pc-next=pb; pc=pb; pb=pb-next （2 分） pc-next = pa?pa:pb ; /插入剩余段（1 分）free(HB); /释放 Lb 的头结点 /MergeList_L 2二叉链表存储的二叉树的层次遍历的算法：（共 8 分）void BFSTraverse(BiTree T) InitQueue(Q); / 置空的辅助队列Q if (T) EnQueue(Q, T); / 根结点入队列（1 分） while (!QueueEmpty(Q) （1 分） DeQueue(Q, p); / 队头元素出队并置为p （1 分） Visit(p); （1 分） if (p-Lchild) EnQueue(Q, p-Lchild); / 左子树根入队列（2 分） if (p-Rchild) EnQueue(Q, p-Rchild); / 右子树根入队列（2 分） / while 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -