数据结构模拟题(开卷)

1、1.2.A,单链表B.双链表C.顺序表D.循环链表设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。A.集合B.线性表C.队列D.栈数据结构模拟题(补)单项选择题在线性表的下列存储结构中，读取元素花费时间最少的是【3 .n个结点的线索二叉树上含有的线索数为1】。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 .在栈中，出栈操作的时间复杂度为【】。一一一一一_2A.O(1)B.O(n)C.O(log2n)

2、D.O(n)7 .假设Q0.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=p

3、C.p->next=qD.p->next=q->next12 .数组A中，每个元素的长度为4个字节，行下标i从1到5,列下标j从1到4,从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A32的起始地址为【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;fo

4、r(i=0i<n；i+)for(j=0j+)x=x*2A.O(2n)B.O(2n)_2C.O(n)D._2_O(n+2)15.将一个A1.10,1.10的三对角矩阵，按行优先存入一维数组B1,30中，A中元素16.17.18.19.20.21.22.23.24.25.a6,5在B数组中白位置iA.15B.16C.55D.65深度为6的二叉树最多有【A.62B.63C.64C.65由3个结点可以构造出【种不同的二叉树。A.2B.3C.4D.栈的插入和删除操作在【A.栈顶B.栈底C.指定位置D.随机位置数组A中，每个元素的长度为3个字节，行下标i从1到5,列下标j从1到4,从首地址SA开始连

5、续存放在存储器内,该数组占用的字节数为【A.20B.60C.80D.120卜面语句的时间复杂度为【s=0;for(i=1;i<=n;i+)s=s+i;A.O(n)_5B.O(n)二叉树中，叶子的数组等于【A.度为2的结点数加C.度为2的结点数设广义表D=(a,(b,c)A.b,cB.(b,c)数制转换的算法，采用【A.集合tail(DC.O(5n)D.O(n2)B.度为2的结点数减D.度为2的结点数的两倍.(b,c)D.c】数据结构最佳。B.线性表C.队列D.栈一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【A.n*nB.n*n/2C.n*(n+1)/2D.(n+1)*(n

6、+1)/2线性表采用链式存储时，其地址是【A,必须是连续的B.一定是不连续的26 .数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为【】。A.物理结构B.逻辑结构C.顺序存储结构D.链式存储结构27 .两个指针p和q,分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。A.p=qB.q->next=pC.p->next=q->nextD.p->next=q28.线性表在【】时，宜用顺序表作存储结构。A.经常随机存取B.经常作插入、删除C.无足够连续存储空间D.经常作动态增减二、判断题1 .【】二叉排序树中每个结点的关键字值大于其左非空孩

7、子（若存在的话）的关键字值，且小于其右非空孩子（若存在的话）结点的关键字值。2.1】算法必须具备的5个特征是：有穷性、确定性、可行性、有0或多个输入量，至少有1个输出量。3.1】完全二叉树的某结点若没有左孩子，则它必是叶子结点。4.1哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。5.1】空栈就是所有元素都为0的栈。6.1】在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。7.1n*n对称矩阵经过压缩存储后占用的存储单元是原来的1/2。8.1一个栈的输入序列是12345,则栈的输出序列可以是54312。i-1入9.1】对于一个非空二叉树，它的根节点

8、作为第一层，则第i层上最多能有2个结点。10.1】稀疏矩阵压缩存储后，必会失去随机存取功能。11.【】完全二叉树中，若一个结点没有左孩子，则它必是树叶。12.1】用带表头结点的单链表表示队列，则判断队列为空的标准是头指针和尾指针均指向同一个结点。13.1】做进栈运算时应先判别，栈是否为空。14.1】广义表中原子个数即为广义表的长度。三、填空题2 .二叉树的深度为k的二叉树最多有13】个结点，其中第i层最多有14】个结点。3 .n个结点的完全二叉树，使用一维数组t存储结点元素的值，假设ti存储第i个结点，那么ti的双亲是【5】，左小孩是【6】，右小孩是t2*i+1。4 .由权值分别为11,8,6

9、,2,5的叶子结点生成一颗哈夫曼树，它的带权路径长度为【75 .若串s="hello",其子串个数是18】。6 .将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为24的结点X的左孩子编号为【9】，右孩子编号为【10】。7 .长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为【11】。8 .WPL(T)指的是树的【12】，即每个叶子的权与根到该叶子的路径长度的乘积之和。9 .深度为k且有13个结点的二叉树称为满二叉树。10 .3层完全二叉树至少有14个结点。四、简答题1 .画出二叉树的5种基本形态。2 .线性表的顺序

10、存储结构相比链式存储结构，有什么优缺点？适用于什么情况的存储？3 .已知一颗非空二叉树，按前序遍历的结果是ACBGDEHFJ按中序遍历的结果是CGBAHEDJFI请画出该二叉树，并写出后序遍历的序列结果。4 .若比较频繁的对一个线性表进行插入和删除操作，该线性表适合采用哪种存储结构？为5 .简述二叉排序树(二叉查找树)的定义及特点。参考答案：一.单项选择题12345678910CADDBDCACB11121314151617181920AABBCBDABA2122232425262728ACDCDCDA.判断题1234567VXXVVVX891011121314XVVVVXX三.填空题1234

11、5线性结构图状结构2k-12i-1ti/2678910t2*i3215484911121314O(n)带权路径长度2k-14四、简答题1 .画出二叉树的5种基本形态。2 .线性表的顺序存储结构相比链式存储结构，有什么优缺点？适用于什么情况的存储？优点：1）是一种随机存储结构，存取任何元素的时间是一个常数，速度快；2）结构简单，逻辑上相邻的元素在物理上也是相邻的；3）不使用指针，节省存储空间。缺点：1）插入和删除元素要移动大量元素，消耗大量时间；2）需要一个连续的存储空间；3）插入元素可能发生“溢出”；4）自由区中的存储空间不能被其他数据占用（共享）.适用于经常用于检索、存取元素，但是插入和删除

12、元素操作较少的情况。3.已知一颗非空二叉树，按前序遍历的结果是ACBGDEHFJ按中序遍历的结果是CGBAHEDJFI请画出该二叉树，并写出后序遍历的序列结果。二叉树:后序遍历的结果是GBCHEJIFDA4 .若比较频繁的对一个线性表进行插入和删除操作，该线性表适合采用哪种存储结构？为什么？时间复杂度是多少？链式存储结构。因为链式存储的线性表，插入和删除操作只需要改变指针，时间复杂度为O(1),而采用顺序存储结构的线性表插入和删除涉及到数据的大量移动，时间复杂度为O(n)。5 .简述二叉排序树(二叉查找树)的定义及特点。定义：如果二叉树的任一结点大于其非空左子树的所有节点，而小于等于其非空右子

13、树的所有结点，则这棵二叉树称为二叉排序树。特点：对一颗二叉排序树进行中序排序，所得的结点序列一定是递增有序的。Whenyouareoldandgreyandfullofsleep,Andnoddingbythefire,takedownthisbook,Andslowlyread,anddreamofthesoftlookYoureyeshadonce,andoftheirshadowsdeep;Howmanylovedyourmomentsofgladgrace,Andlovedyourbeautywithlovefalseortrue,Butonemanlovedthepilgrimsou

14、linyou,Andlovedthesorrowsofyourchangingface;Andbendingdownbesidetheglowingbars,Murmur,alittlesadly,howlovefledAndpaceduponthemountainsoverheadAndhidhisfaceamidacrowdofstars.ThefurthestdistanceintheworldIsnotbetweenlifeanddeathButwhenIstandinfrontofyouYetyoudon'tknowthatIloveyou.ThefurthestdistanceintheworldIsnotwhenIstandinfrontofyouYetyoucan'tseemyloveButwhenundoubtedlyknowingthelovefrombothYetcannotbetogether.ThefurthestdistanceintheworldIsnotbeingapart