2004级《算法与数据结构》期末试卷(a)及答案new

《2004级《算法与数据结构》期末试卷(a)及答案new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、专业学号姓名数学与计算机科学学院计算机系2004级《算法与数据结构》期末试卷（A）时间：120分钟题号：一二三四五总分得分：一、选择题（10*2%=20%）1．代码段for(j=1;j<=n;j++)的时间复杂性是B。for(k=n;k>=1;k/=2)count++;2A、O(n)B、O(nlogn)C、O(logn)D、O(n)2．对某个无向图的邻接矩阵来说，下列叙述正确的是A。A、第i行上的非零元素个数和第i列上的非零元素个数一定相等B、矩阵中的非零元素个数等于图中的边数C、第i行与第i列上的非零元素的总数等于顶点vi的度数D、矩阵中非全零行的行数等于图

2、中的顶点数3．循环双链表中在p所指结点之后插入结点s的操作是D。A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->nextB、p->next=s;p->next->prior=s;s->prior=p;s->next=p->nextC、s->prior=p;s->next=p->next;p->next=s;p->next->prior=sD、s->prior=p;s->next=p->next;p->next->prior=s;p->next=s4．4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前

3、，栈的状态如图，，不可能的出栈顺序是C。A、a4，a3，a2，a1B、a3，a2，a4，a1C、a3，a1，a4，a2D、a3，a4，a2，a15．下列四种排序方法中，不稳定的方法是D。A、插入排序B、冒泡排序C、归并排序D、选择排序6．单个结点二叉树的高度为0，所有含有15个结点的二叉树中，最小高度是D。A、6B、5C、4D、37．在一个具有n个顶点的无向图中，要连通全部顶点至少需要B条边。A、nB、n-1C、n/2D、n+18．快速排序法的运行效率取决于D。A、要排序的数据量B、要排序的数据中含有相同值的比例专业学号姓名C、要排序的数据的局部有序性D、划分

4、过程的对称性9．二叉树若用顺序存储结构（数组）存放，则下列四种运算中的C最容易实现。A、先序遍历二叉树B、判断两个结点是否位于同一层C、层次遍历二叉树D、根据结点的值查找其存储位置10．模式串ABBCABABDBABBC的前缀函数为C。A、00001212000121B、10000120001212C、00001212001234D、10000120012345二、填空题（15*2%=30%）1、已知某棵二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点序列为DCEGBFHKJIA，该二叉树按前序遍历所得到的结点序列为ABCDGE

5、IHFJK。2、一个n×n的下三角矩阵A中的元素aij（i≥j，1≤i，j≤n）按行存于一个一维数组B[1..n（n＋1）/2]中，对其中的任一元素aij，若在B中的位置为k，则k＝j+(i-1)i/2。3、设一棵完全二叉树具有988个结点，则此完全二叉树有494个叶子结点，有493个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。4、向一个有127个元素的有序线性表（数组实现）中插入一个随机的新元素并依然保持有序性，平均要移动63.5个元素。5、设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出

6、栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该能容纳4个元素。6、顺序循环队列中，设队头指针为front，队尾指针为rear，队中最多可有MAX个元素，则元素入队列时队尾指针的变化为(rear+1)%MAX；元素出队列时队头指针的变化为(front+1)%MAX。若采用少用一个存储单元的方法区分队满与队空问题，则可用(rear+1)%MAX==front表示队满的判别条件。7、在输入已经有序的情况下，整个冒泡排序算法需要执行n(n-1)/2次元素比较操作。8、设一个闭散列表的容量为m，用线性探测法解决冲突，要插入一个

7、键值，若插入成功，至多要进行m-1次检测。⎡010⎤⎢⎥9、用邻接矩阵A=101表示一张图，如果该图是有向图，共有4条边；若是无向图，则共有2条边。⎢⎥⎢⎣010⎥⎦三、简答题（28%）1、（5分）设下列二叉树是与某森林对应的二叉树，回答下列问题。（1）森林中有几棵树？（2）每一棵树的根结点标号分别是什么？（3）每一棵树中有几个结点？（4）森林中共有几个叶子结点？解答：（1）3(2分)（2）ACF（1分）（3）623（1分）专业学号姓名（4）6（1分）2、（6分）用Prim算法（初始顶点集S＝{7}）构造出下图的一棵最小生成树，请用图示法画出其构造过程。60①

8、⑦505045图解：（每图1分）654