(算法与数据结构课程模拟考试试卷.docVIP

《 算法与数据结构 》课程模拟考试试卷 一、单项选择题（共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-1 C．n-i+1 D．2 4.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 5．深度为5的二叉树其结点个数至多有（ ）。 A．16 B．32 C．31 D．10 6．有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分) typedef char datatype; typedef struct node {datatype data; struct node *lchild, *rchild; }bitree; INORDER(bitree *t) { //二叉树t非空 { ; //中序遍历*t的左子树 ; //访问根结点 ; //中序遍历*t的右