《算法与数据结构》课程模拟考试试卷

《算法与数据结构》课程模拟考试试卷一、单项选择题（共10小题，每小题2分，共20分）1．在下面的程序段中，对x的赋值语句的频度为（）。i=1;k=0;while(in){k=k+10;i++;}A．0(1)B．O(n)C．0(log2n)D．0(nlog2n)2．线性表采用链式存储时，其地址（）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以3．一个栈的输入序列为1,2,……，n，输出序列的第一个元素是n，则第二个输出元素是（）。A．不确定B．n-1C．n-i+1D．24.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表5．深度为5的二叉树其结点个数至多有（）。A．16B．32C．31D．106．有6个结点的无向图要确保是一个连通图至少应有（）。A．5条边B．6条边C．7条边D．8条边7．下列说法中正确的是（）。A．有向图的邻接矩阵一定是非对称矩阵B.无向图的邻接矩阵一定是对称矩阵C．若图G的邻接矩阵是对称的，则G一定是无向图D．有向图的邻接矩阵一定是下三角矩阵8．下列排序算法中，第一趟排序完毕后，其最大或最小元素一定在最终位置上的算法是（）。A．归并排序B．直接插入排序C．快速排序D．冒泡排序9．二分查找法要求被查找的表是（）。A．顺序表B．分块有序表C．顺序表且是按递增或递减次序排序D．不受上述任何限制10．下列有关散列文件的说法中不正确的是（）。A.散列文件具有随机存放的优点B.散列文件只能按关键字存取C.散列文件需要索引区D.散列文件的记录不需要进行排序二、简述题（共4小题，每小题5分，共20分）1．线性表与有限集合有什么区别？2．如何判断顺序循环队列的空与满？3．说明满二叉树与完全二叉树的区别。4．基于“关键字比较”排序算法最好平均时间复杂度是多少？分别是那些排序算法？三、应用题（共6小题，每小题6分，共36分）1．请画出与下面二叉树对应的森林。2．巳知8个权值：5，29，7，8，14，23，3，11，请构造出相应的哈夫曼树。3．已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表。4．有一个数据序列：25，50，70，21，4，18，43。现采用简单选择排序算法进行排序，写出每趟的结果。5．给定表(19,22,18,15,30,20,42,35,16)，按数据元素在表中的次序构造一棵二叉排序树。6．设散列表长度为11，散列函数h(x)=x%11,给定的关键字序列为：1，13，13，34，38，33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。四、算法设计题（共2小题，共24分）1．已知二叉树的结构如下，请填写中序遍历二叉树算法。(8分)typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;INORDER(bitree*t){//二叉树t非空{;//中序遍历*t的左子树;//访问根结点;//中序遍历*t的右子树}}2．设待排序记录的数据类型SqList如下所示。实现的直接插入算法InsertionSort如下，请在空白处填入适当内容。(16分)typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表长度}SqList;//顺序表类型voidInsertionSort(SqList&L){//对顺序表L作直接插入排序for(i=;i=;++i)if(){;//复制为监视哨for(j=;L.r[0].keyL.r[j].key;);//记录后移;//插入到正确位置}}//InsertSort