《数据结构与算法》试卷(1A)参考答案.doc

江苏技术师范学院2007—2008学年第2学期 《数据结构与算法》试卷（1A）参考答案与评分标准 一、选择题（每题1.5分，共15分） 题号 1 2 3 4 5 6 7 8 9 10 答案 B B A D A B A D C C 二、填空（每空1.5分 ，共15分） 1、数据元素的有限集，D上关系的有限集 2、n-i 3、队列 4、20 ,3 5、开放定址法，再哈希法，链地址法，建立一个公共溢出区 6、非零元很少 t m*n 且分布没有规律 7、简单路径 或 简单回路 或简单环 8、31 n1+n2 0+ n2 n0-1 31）， 26-1 32 9、 log2n 三、判断题（10分，每题1分对的打‘√’，错的打‘×’） 题号 1 2 3 4 5 6 7 8 9 10 答案 √ × √ √ × × × √ × √ 四、简答、应用题（共40分） 1设顺序表循环队列中存放元素的数组data[]，容量为MAXSIZE，队列中队头指针为begin，队尾指针为end，指向队列的指针为pring。采用少用一个元素空间的办法判断队列空与满。写出元素x入队列，x出队列的操作 操作中不考虑队列满与空 。 4分 解：入队列:pring- data[pring- end] x pring- end pring- end+1 %MAXSIZE 出队列: x pring- data[pring- begin] pring- front pring- front+1 %MAXSIZE 2 列出先序遍历能得到ABC序列的所有不同的二叉树。（5分） 3 已知某算法如下，试说明该算法实现的功能。（6分） #define Max 100 void unknow int num ,int r int st[Max],top 0; while num! 0 st[top++] num%r; num num/r; while top 0 cout st[--top] “ “; cout endl; 答：将十进制数num转换成r进制的数，并输出结果。 G是一个非连通无向图，共有28条边，则该图至少有多少个顶点？（5分） 解：设有一个顶点为独立的结点，其余结点为全连通图，则具有28条边的全连通图其有结点数为28 n n-1 /2,则n取满足该式的最小值为8，故该图至少有9个顶点。 5 对于下图所示的有向图G，给出从顶点0到其余各顶点的最短路径及路径长度。（6分） 1： 0-1 13 2： 0-2 8 3： 0-2-3 13 4： 0-2-3-4 19 5： 0-2-3-4-5 21 6： 0-1-6 20 6已知某二叉树中序遍历的结果为： DGBAECHF，其后半序遍历的结果为：GDBEHFCA，试画出这棵二叉树。（6分） 7 对关键字序列（7，4，1，14，100，30，5，9，20，134），设哈希函数为H k k mod 13,试给出表长为13的哈希表（用线性探测开放定址法处理冲突），并求出在等概率情况下，查找成功的平均查找长度。（7分） 解： H 7 7 mod 13 7 H 4 4 mod 13 4 H 1 1 mod 13 1 H 14 14 mod 13 1 冲突 H1 （14+1） mod 13 2 H 100 100 mod 13 9 H 30 30 mod 13 4 冲突 H1 （30+1）mod 13 5 H 5 5 mod 13 5 冲突 H1 （5+1）mod 13 6 H 9 9 mod 13 9 冲突 H1 （9+1）mod 13 10 H 20 20 mod 13 7 冲突 H1 （20+1）mod 13 8 H 134 134 mod 13 4 冲突 H1 （134+1）mod 13 5 冲突 H1 （134+2）mod 13 6 冲突 H1 （134+3）mod 13 7 冲突 H1 （134+4）mod 13 8 冲突 H1 （134+5）mod 13 9 冲突 H1 （134+6）mod 13 10 冲突 H1 （134+7）mod 13 11 冲突 在等概率情况下：ASL （1*4+5*2+1*8）/10 2.2 五、算法设计题（20分） 1．[题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。 LinkedList delinsert（LinkedList list） ∥list是非空线性链表，链结点结构是（data，link），data是