《数据结构与算法》期末试卷

《《数据结构与算法》期末试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、三峡大学试卷纸教学班号序号学号姓名命题教师审题教师…………………….………….……试题不要超过密封线………….………………………………2010—2011学年第一学期《数据结构与算法》期末试卷注意：1、本试卷共4页；2、考试时间120分钟3、姓名、学号必须写在指定地方阅卷负责人签名：题号一二三四五六七八总分得分阅卷人得分一、填空题(15×2＝30分)1．某完全二叉树共有700个节点，那么该二叉树的高度为____，叶子节点数目为__。2.已知一有向图的邻接矩阵如下图所示（各顶点依次编号为1，2，3，4，5，6）：010100001010100100000001001000001010A=

2、那么该图_____（是否）为连通图。编号为3的顶点的出度为______；入度为_____。如果从编号为1的顶点出发对该图进行深度优先遍历，其得到的遍历序列为______；如果从编号为3的顶点出发对该图进行广度优先遍历，其得到的遍历序列_______。3．设三个元素的入栈序列为b，c，a，那么不可能的出栈序列为_____。4.一个顺序存储的循环队列最大能存储的元素数目是100，那么设队头指针(约定为指向队头元素前一位置)和队尾指针的值分别是13和89，那么队列中实际存储元素的个数是____；若队头指针和队尾指针的值分别是89和13，那么队列中实际存储元素的个数是____。5.顺序查找一

3、个具有n个元素的线性表，其时间复杂度为；二分查找一个具有n个元素的顺序存储的线性表，其时间复杂度为。6.已知一二叉树的先序遍历和中序遍历得到的序列为ABECFGHD和EBAFHGCD，那么该二叉树的后序遍历得到的序列是________。7.快速排序的平均时间复杂度为；而当初始数据的关键字有序时，那么快速排序的时间复杂度为。阅卷人得分二、选择题（8×3＝24分）1．顺序存储队列Q的入队操作可描述为：[]A．Q.V[rear++]=xB．Q.V[++rear]=xC．Q.V[Q.rear++]=xD．Q.V[++Q.rear]=x2．已知某二叉树度为1的结点数是100，总结点数是199，

4、那么该二叉树的叶子结点数是：[]A．49B．50C．51D．523．设T为Huffman树，它有6个树叶，且各树叶的权分别为2，3，4，5，6，7。那么该树的非叶子结点的权之和为：[]A．63B．70C．68D．694．一棵二叉树的顺序存储结构如下图所示，若中序遍历该二叉树，则遍历次序为：[]ABCDEFGHA．ABDEGCFHB．DBEGACHFC．ABCDEFGHD．DGEBHFCA5．从未排序序列中挑选元素，并将其放入已排序序列中，此排序方法称为：[]A．插入排序B．选择排序C．冒泡排序D．快速排序6．若一个有向完全图有n个顶点，那么该有向图的弧的数目是：[]A．n!B．n!/

5、2C．n*(n-1)D．n*(n-1)/27．某有序表的关键字分别为：13，33，36，58，70，75，88，90，96，102。那么利用折半查找算法进行查找时的平均查找长度为：[]A．2.0B．2.9C．2.5D．3.08．利用一组关键字（20，15，10，50，60，30，17，53，13）构成二叉排序树，那么该二叉树的平均查找长度是：[]A．20/9B．2C．25/9D．16/93阅卷人得分三、简答题(6+10＝16分)1．已知一组数据元素为（54，46，75，18，27，15，39，67，88）。写出分别利用选择排序、插入排序、冒泡排序、快速排序以及2路归并排序的第一趟排序

6、结果（只需要写出结果）。1．假定一个表为(6,17,22,1,14,8,11,9,28)，散列空间为[0…10]，采用除留余数法构造表，哈希函数为H(K)=KMOD11，分别用线性探测法以及链地址法解决地址冲突，试画出在这两种方法下得到的哈希表以及等概率情况下的平均查找长度（只需要写出结果）。阅卷人得分四、(10分)二叉树定义如下：typedefstructbtnode{intdata;/*存储数据信息*/structbtnode*lchild,*rchild;/*左、右孩子节点指针*/}BTNODE;设二叉树T是一棵二叉排序树，试设计一个算法，实现在T中查找数据信息为x的结点，如果

7、找不到，则给出查找失败信息；否则返回该结点指针。部分代码已经给出，请把程序补充完整。BTNODE*SearchNode(BTNODE*T){BTNODE*p;p=T;/*变量初始化*//*查找过程*/while(____){if(_________)/*找到*/returnp;;elseif(____)_____;else______;}printf(“查找失败”);exit(1);}3阅卷人得分五、（共10分）线性表定义如下：typedefstruc