中国地质大学(北京)继续教育学院2016年03课程考试第1页(共6页)《数据结构》模拟题(补)一.单项选择题1.在线性表的下列存储结构中,读取元素花费时间最少的是【】。A.单链表B.双链表C.顺序表D.循环链表2.设计一个判定表达式中左、右括号是否配对出现的算法,采用【】数据结构最佳。A.集合B.线性表C.队列D.栈3.n个结点的线索二叉树上含有的线索数为【】。A.2nB.n-1C.nD.n+14.设广义表D=(a,(b,c)),则tail(D)=【】。A.b,cB.(b,c)C.((b,c))D.c5.由4个结点可以构造出【】种不同的二叉树。A.12B.13C.14D.156.在栈中,出栈操作的时间复杂度为【】。A.O(1)B.O(n)C.O(log2n)D.O(n2)7.假设Q[0..len-1]表示循环队列,f为队头指针,r为队尾指针,则进队操作语句是【】。A.f=f+1B.r=r+1C.f=(f+1)%lenD.r=(r+1)%len8.一个n*n的对称矩阵,如果以行或列为主序放入内存,则其容量为【】。A.n*nB.n*n/2C.n*(n+1)/2D.(n+1)*(n+1)/29.队列操作的原则是【】。A.进优于出B.出优于进C.先进先出D.后进先出10.下列数据结构中,【】是非线性数据结构。A.栈B.串C.队列D.树11.两个指针p和q,分别指向单链表的两个元素,p所指元素是q所指元素的前驱,则【】。A.p==qB.q-next=pC.p-next=qD.p-next=q-next12.数组A中,每个元素的长度为4个字节,行下标i从1到5,列下标j从1到4,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[3][2]的起始地址为【】。A.SA+20B.SA+36C.SA+40D.SA+4513.已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为d1,则第i个结点的地址为【】。A.d1+(i-1)*mB.d1+i*mC.d1+(i+1)mD.d1-i*m14.分析下列算法suanfa1(n)的时间复杂度是【】。voidsuanfa1(intn){inti,j,x=1;for(i=0;in;i++)中国地质大学(北京)继续教育学院2016年03课程考试第2页(共6页)for(j=0;jn;j++)x=x*2;}A.O(2n)B.O(2n)C.O(n2)D.O(n2+2)15.将一个A[1..10,1..10]的三对角矩阵,按行优先存入一维数组B[1,30]中,A中元素a[6,5]在B数组中的位置i为【】。A.15B.16C.55D.6516.深度为6的二叉树最多有【】个结点。A.62B.63C.64C.6517.由3个结点可以构造出【】种不同的二叉树。A.2B.3C.4D.518.栈的插入和删除操作在【】进行。A.栈顶B.栈底C.指定位置D.随机位置19.数组A中,每个元素的长度为3个字节,行下标i从1到5,列下标j从1到4,从首地址SA开始连续存放在存储器内,该数组占用的字节数为【】。A.20B.60C.80D.12020.下面语句的时间复杂度为【】。s=0;for(i=1;i=n;i++)s=s+i;A.O(n)B.O(n5)C.O(5n)D.O(n2)21.二叉树中,叶子的数组等于【】。A.度为2的结点数加1B.度为2的结点数减1C.度为2的结点数D.度为2的结点数的两倍22.数制转换的算法,采用【】数据结构最佳。A.集合B.线性表C.队列D.栈23.线性表采用链式存储时,其地址是【】。A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续或不连续都可以24.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为【】。A.物理结构B.逻辑结构C.顺序存储结构D.链式存储结构25.两个指针p和q,分别指向单链表的两个元素,p所指元素是q所指元素的前驱,则【】。A.p==qB.q-next=pC.p-next=q-nextD.p-next=q中国地质大学(北京)继续教育学院2016年03课程考试第3页(共6页)26.线性表在【】时,宜用顺序表作存储结构。A.经常随机存取B.经常作插入、删除C.无足够连续存储空间D.经常作动态增减二、判断题1.【】二叉排序树中每个结点的关键字值大于其左非空孩子(若存在的话)的关键字值,且小于其右非空孩子(若存在的话)结点的关键字值。2.【】算法必须具备的5个特征是:有穷性、确定性、可行性、有0或多个输入量,至少有1个输出量。3.【】完全二叉树的某结点若没有左孩子,则它必是叶子结点。4.【】哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。5.【】空栈就是所有元素都为0的栈。6.【】在单链表中,要访问某个结点,只要知道该结点的指针即可;因此,单链表是一种随机存取结构。7.【】n*n对称矩阵经过压缩存储后占用的存储单元是原来的1/2。8.【】一个栈的输入序列是12345,则栈的输出序列可以是54312。9.【】对于一个非空二叉树,它的根节点作为第一层,则第i层上最多能有2i-1个结点。10.【】稀疏矩阵压缩存储后,必会失去随机存取功能。11.【】完全二叉树中,若一个结点没有左孩子,则它必是树叶。12.【】用带表头结点的单链表表示队列,则判断队列为空的标准是头指针和尾指针均指向同一个结点。13.【】做进栈运算时应先判别,栈是否为空。14.【】广义表中原子个数即为广义表的长度。三、填空题1.数据结构包含四种基本结构,它们是集合、【1】、树形结构、【2】。2.二叉树的深度为k的二叉树最多有【3】个结点,其中第i层最多有【4】个结点。3.n个结点的完全二叉树,使用一维数组t存储结点元素的值,假设t[i]存储第i个结点,那么t[i]的双亲是【5】,左小孩是【6】,右小孩是t[2*i+1]。4.由权值分别为11,8,6,2,5的叶子结点生成一颗哈夫曼树,它的带权路径长度为【7】。5.若串s=hello,其子串个数是【8】。6.将含100个结点的完全二叉树从根这一层开始,每层上从左到右依次对结点编号,根结点的编号为1。编号为24的结点X的左孩子编号为【9】,右孩子编号为【10】。7.长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为【11】。中国地质大学(北京)继续教育学院2016年03课程考试第4页(共6页)8.WPL(T)指的是树的【12】,即每个叶子的权与根到该叶子的路径长度的乘积之和。9.深度为k且有【13】个结点的二叉树称为满二叉树。10.3层完全二叉树至少有【14】个结点。四、简答题1.画出二叉树的5种基本形态。2.线性表的顺序存储结构相比链式存储结构,有什么优缺点?适用于什么情况的存储?3.已知一颗非空二叉树,按前序遍历的结果是ACBGDEHFJI,按中序遍历的结果是CGBAHEDJFI,请画出该二叉树,并写出后序遍历的序列结果。4.若比较频繁的对一个线性表进行插入和删除操作,该线性表适合采用哪种存储结构?为5.简述二叉排序树(二叉查找树)的定义及特点。参考答案:一.单项选择题二.判断题1234567√××√√√×891011121314×√√√√××三.填空题12345678910CADCBDCCCB11121314151617181920AABBCBDABA212223242526ADDCDA12345线性结构图状结构2k-12i-1t[i/2]中国地质大学(北京)继续教育学院2016年03课程考试第5页(共6页)四、简答题1.画出二叉树的5种基本形态。2.线性表的顺序存储结构相比链式存储结构,有什么优缺点?适用于什么情况的存储?优点:1)是一种随机存储结构,存取任何元素的时间是一个常数,速度快;2)结构简单,逻辑上相邻的元素在物理上也是相邻的;3)不使用指针,节省存储空间。缺点:1)插入和删除元素要移动大量元素,消耗大量时间;2)需要一个连续的存储空间;3)插入元素可能发生“溢出”;4)自由区中的存储空间不能被其他数据占用(共享)。适用于经常用于检索、存取元素,但是插入和删除元素操作较少的情况。3.已知一颗非空二叉树,按前序遍历的结果是ACBGDEHFJI,按中序遍历的结果是CGBAHEDJFI,请画出该二叉树,并写出后序遍历的序列结果。二叉树:后序遍历的结果是GBCHEJIFDA4.若比较频繁的对一个线性表进行插入和删除操作,该线性表适合采用哪种存储结构?为什678910t[2*i]3215484911121314O(n)带权路径长度2k-14中国地质大学(北京)继续教育学院2016年03课程考试第6页(共6页)么?时间复杂度是多少?链式存储结构。因为链式存储的线性表,插入和删除操作只需要改变指针,时间复杂度为O(1),而采用顺序存储结构的线性表插入和删除涉及到数据的大量移动,时间复杂度为O(n)。5.简述二叉排序树(二叉查找树)的定义及特点。定义:如果二叉树的任一结点大于其非空左子树的所有节点,而小于等于其非空右子树的所有结点,则这棵二叉树称为二叉排序树。特点:对一颗二叉排序树进行中序排序,所得的结点序列一定是递增有序的。