《数据结构》期末模拟试题一.doc

《数据结构》期末模拟试题一 　　一、单选题（每小题2分，共8分） 　　1. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行________。 　　　　A HL=p; p-next=HL; B p-next=HL; HL=p; 　　　　C p-next=HL; p=HL; D p-next=HL-next; HL-next=p; 　　2. 在一个顺序队列中，队首指针指向队首元素的________位置。 　　　　A 前一个 B 后一个 C 当前 　　3. 从二叉有哪些信誉好的足球投注网站树中查找一个元素时，其时间复杂度大致为________。 　　　　A O(n) B O(1) C O(log2n) D O(n2) 　　4. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。 　　A 24 B 48 C 72 D 53 　　二、填空题（每空1分，共32分） 　　1. 一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为________。 　　2. 在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为________和________。 　　3．一个广义表中的元素分为________元素和________元素两类。 　　4．从一个链栈中删除一个结点时，需要把栈顶结点的_________域的值赋给________。 　　5．在进行函数调用时，需要把每个实参的值和调用后的________传送给被调用的函数中。 　　6．对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。 　　7．在一棵高度为5的理想平衡树中，最少含有________个结点，最多含有________个结点。 　　8．在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左孩子元素的下标为______，右孩子元素的下标为________。 　　9．在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。 　　10．对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为________和________条。 11．以二分查找方法从长度为20的有序表中查找一个元素时，平均查找长度为________。 　　12．假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为_____________、_____________和_____________。 　　13．在线性表的散列存储中，装填因子a又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则a等于________。 　　14．在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________个，其子树数目最少为________，最多为________。 　　15．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。 　　16. 快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为________。 　　三、运算题（每小题6分，共24分） 　　1. 假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。 　　　　先序： 　　　　中序： 　　　　后序： 　　　　按层： 　　2．已知一个图的顶点集V和边集G分别为： 　　　　V={0,1,2,3,4,5,6,7}; 　　　　E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, 　　　　　(4,6)4,(5,7)20,(6,7)30}; 　　按照普里姆算法从顶点0出发得到最小生成树，试写出在生成最小生成树的过程中依次得到的各条边。 　　　　________, ________, ________, ________, ________, ________, ________。 3. 已知一个图的顶点集V和边集G分别为： 　　　　V={0,1,2,3,4,5,6,7,8}; 　　　　E={0,2,1,3,1,4,2,4,2,5,3,6,3,7,4,7,4,8, 　　　　　5,7,6,7,7,8}; 　　若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则