算法与数据结构-B卷

第3页共3页石家庄铁道大学2013-2014学年第1学期2012级本科期末考试试卷（B）课程名称：算法与数据结构任课教师：考试时间：分钟学号：姓名：班级：考试性质（学生填写）：题号一二三四五六七总分满分206020100得分阅卷人答案一律写在答题纸上，写在试卷上无效。一、单项选择题（每小题2分，共20分）1、若某线性表最常用的操作是取第i个元素和找第i个元素的前驱元素，则采取（）存储方式最节省时间。A．单链表B．双链表C．单向循环链表D．顺序表2、在单链表中增加一个头结点的目的是（）。A．使单链表至少有一个结点B．标示表结点中首结点的位置C．方便运算的实现D．说明单链表是线性表的链式存储3、一个栈的输入序列为12345，则下列序列中（）不可能是栈的输出队列。A．23415B．54132C．23145D．154324、一个子串在包含它的主串中的位置是指（）。A．子串的最后一个字符在主串中的位置B．子串的最后一个字符在主串中首次出现的位置C．子串的第一个字符在主串中的位置D．子串的第一个字符在主串中首次出现的位置5、已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（）。A．head(tail(LS))B．tail(head(LS))C．head(tail(head(tail(LS))))D．head(tail(tail(head(LS))))6、若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（）。A．X的双亲B．X的左子树中最右结点C．X的右子树中最左结点D．X的左子树中最左结点7、（）的邻接矩阵是对称矩阵。A．有向图B．无向图C．AOV网D．AOE网8、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。A．完全图B．连通图C．有回路D．一棵树9、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）是散列文件的关键。A．散列函数B．除余法中的质数C．冲突处理方法D.散列函数和冲突处理方法10、堆排序中，堆的形状是一棵（）。A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树二、简答题（共60分）1、（13分）在某报文系统中只出现以下字符，字符的权值分别为：A B C D E F G 7 21 20 23 3 2 24为这7个字母设计Huffman编码。（1）画出Huffman树。（7分）（2）Huffman树HT存储结构的终态如下表所示，请填写完整。（6分）结点iweightparentlchildrchild1700221003200042300530062007240089101112132.（12分）图的邻接矩阵如下：（1）根据邻接矩阵画出这个图。（4分）（2）画出该图的广度优先生成树（从顶点1出发）。（4分）（3）画出该图的深度优先生成树（从顶点3出发）。（4分）3.（11分）散列表的地址范围为0—15，散列函数H(key)=key%13，关键字序列为（26，51，3，23，11，33，38，42，69，13，9），用链地址法处理冲突。（1）对该关键字序列构造散列表。（8分）（2）求等概率下查找成功时的平均查找长度ASLsucc。（3分）4.（12分）待排序的关键字序列为{39，1，28，12，6，24，51，70，19，45}，从小到大排序。（1）写出采用冒泡快速排序算法每趟排序结束后关键字序列的状态。（6分）（2）写出采用希尔排序算法每趟排序结束后关键字序列的状态。（6分）5.（12分）已知二叉树的层次访问序列为ABCDEFGHIJ；二叉树的中序访问次序为DBGEHJACIF。（1）画出和上述已知序列对应的树T。（5分）（2）写出树T的前序遍历序列。（3分）（3）将二叉树T转换成相应的森林。（4分）三、算法设计题（每小题10分，共20分）用类C语言编写算法。1、有一个带头结点的单链表，其结点的元素以非递减有序排列，请(