您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 项目/工程管理 > 数据结构(本)期末综合练习(2015年11月)
1数据结构(本)期末综合练习2015年11月综合练习一一、单项选择题1.对稀疏矩阵进行压缩存储,可采用三元组表,一个10行8列的稀疏矩阵A共有73个零元素,其相应的三元组表共有(C)个元素。A.8B.80C.7D.102.对稀疏矩阵进行压缩存储,可采用三元组表,一个10行8列的稀疏矩阵A,其相应的三元组表共有6个元素,矩阵A共有(C)个零元素。A.8B.72C.74D.103.字符串(A)是“abcd321ABCD”的子串。A.“21AB”B.“abcD”C.“aBCD”D.“321a”4.程序段chara[]=“abdcacdef”;char*p=a;intn=0;while(*p!=‘\0’){n++;p++;}结果中,n的值是(D)。A.6B.8C.7D.95.栈和队列的共同特点是(A)。A.都是操作受限的线性结构B.元素都可以随机进出C.都是先进后出D.都是先进先出6.10,6,2,1按顺序依次进栈,该队列的可能输出序列是(A)。(进栈出栈可以交替进行)。A.6,10,1,2B.2,10,6,1C.6,1,10,1D.1,6,10,27.在一个链队中,假设f和r分别为队头和队尾指针,p指向一个新结点,要为结点p所指结点赋值x,并入队的运算为p-data=x;p-next=NULL;(B)。A.f-next=p;f=p;B.r-next=p;r=p;C.r=p;p-next=r;D.p-next=f;f=p;8.对一个栈顶指针为top的链栈进行出栈操作,用变量e保存栈顶元素的值,则执行(B)。A.e=top-next;top-data=e;B.e=top-data;top=top-next;C.top=top-next;e=top-data;D.top=top-next;e=data;9.数据结构中,与所使用的计算机无关的是数据的(A)结构。A.逻辑B.存储C.逻辑与存储D.物理10.算法的时间复杂度与(A)有关。A.算法本身B.所使用的计算机C.算法的程序设计D.数据结构11.顺序表所具备的特点之一是(A)。2A.可以随机访问任一结点B.不需要占用连续的存储空间C.插入元素的操作不需要移动元素D.删除元素的操作不需要移动元素12.在一个单向链表中,在p所指结点之后插入一个s所指的结点时,可执行s-next=p-next;和(D)。A.p=s;B.p-next=s-next;C.p=s-nextD.p-next=s;13.数据元素是数据的基本单位,它(C)。A.只能有一个数据项组成B.至少有二个数据项组成C.可以是一个数据项也可以由若干个数据项组成D.至少有一个数据项为指针类型14.一种逻辑结构在存储时(C)。A.只要存储数据元素间的关系B.只能采用一种存储结构C.可采用不同的存储结构D.只要存储数据元素的值15.设有头指针为head的非空的单向链表,指针p指向其尾结点,要使该单向链表成为单向循环链表,则可利用下述语句(C)。A.p=head;B.p=NULL;C.p-next=head;D.head=p;16.单向链表所具备的特点是(C)。A.可以随机访问任一结点B.占用连续的存储空间C.插入删除不需要移动元素D.可以通过某结点的指针域访问其前驱结点17.在线性表的顺序结构中,以下说法正确的是(C)。A.逻辑上相邻的元素在物理位置上不一定相邻B.数据元素是不能随机访问的C.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高18.数据结构在计算机内存中的表示是指(B)。A.数据元素之间的关系B.数据的存储结构C.数据元素的类型D.数据的逻辑结构19.对链表,以下叙述中正确的是(A)。A.不能随机访问任一结点B.结点占用的存储空间是连续的C.插入删除元素的操作一定要要移动结点D.可以通过下标对链表进行直接访问20.下面关于线性表的叙述中,错误的是(B)。A.线性表采用顺序存储,必须占用一片连续的存储空间。B.线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动。C.线性表采用链式存储,不必占用连续的存储空间。D.线性表采用链式存储,进行插入删除操作,不需要移动元素21.设有一个长度为35的顺序表,要在第5个元素之前插入1个元素(也就是插入元素作为新表的第5个元素),则移动元素个数为(B)。A.30B.31C.5D.622.设有一个长度为18的顺序表,要在第5个元素之前插入1个元素(也就是插入元素作为新表的第5个元素),则移动元素个数为(B)。A.15B.14C.5D.623.设有一个长度为40的顺序表,要删除第10个元素(下标从1开始)需移动元素的个数为(C)。3A.11B.10C.30D.3124.设有一个长度为25的顺序表,要删除第10个元素(下标从1开始)需移动元素的个数为(C)。A.10B.17C.15D.1625.设有一个25阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵中元素a7,5在一维数组B中的下标是(C)。A.25B.24C.26D.2726.设有一个18阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵中元素a10,8在一维数组B中的下标是(D)。A.62,B.63C.51D.5327.线性表在存储后,如果相关操作中有要求:利用已知的指向某结点的指针或序号,访问该结点的前驱结点,则采用(A)的存储方式是不可行的。A.单向链表B.双向链表C.单向循环链表D.顺序表28.在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点,可执行snext=rearnext;和(D)。A.rearnext=snext;B.rear=snext;C.rear=s;D.rearnext=s;29.在一棵二叉树中,若编号为i的结点存在左孩子,i结点的左孩子的顺序编号为(B)。A.i/2.0B.2*iC.2*i+1D.i+230.在一棵二叉树中,若编号为15的结点是其双亲结点的右孩子,则双亲结点的顺序编号为(D)。A.30B.8C.31D.7二、填空题1.广义表((b,a,c),c,d,f,e,((i,j),k))的长度是___6_____。2.结构中的元素之间存在一对多的关系是___树形_____结构。3.数据结构中,数据元素之间的抽象关系称为____逻辑____结构。4.结构中的元素之间存在多对多的关系是___图状_____结构。5.栈的操作特点是后进___先出_____。6.循环队列的最大存储空间为MaxSize,若队头指针front,队尾指针rear,采用少用一个存储空间以有效地判断栈空或栈满,队空的判定条件为___rear==front为真_____。7.广义表((b,a,c),c,d,f,e,((i,j),k))的表头是____(b,a,c)____。8.广义表((b,a,c),c,d,f,e,((i,j),k))的长度是____6____。9.设有一个长度为18的顺序表,第8号元素到第18号元素依次存放的值为8,9,…,18.某人想要删除第8号元素,程序中他的做法是用语句for(i=18;i=9;i--)a[i-1]=a[i];即从第18号元素开始,直到第9号元素,每个元素依次向前(左)移动1个位置.事实上这样做是错误的.其结果新表中第9号元素的值为___18_____。10.要求在n个数据元素中找值最大的元素,其基本操作为元素间的比较。算法的时间复杂度为____O(n)___。11.一棵二叉树,有1个2度结点,,2个1度结点,则该树共有_5______个结点。412.一棵有8个叶结点的二叉树,其1度结点的个数为3,则该树共有___18____个结点。13.设有一棵深度为5的完全二叉树,该树共有21个结点,第5层上有6个结点。(根所在结点为第1层)14.对于一棵具有n个结点的二叉树,其相应的链式存储结构中共有__n+1______个指针域为空。15.中序遍历____二叉排序树____树可得到一个有序序列。16.对一组记录(5,8,9,2,12,7,56,44,39)进行直接插入排序(由小到大排序),当把第6个记录7插入有序表,为寻找插入位置需比较__4______次。17.序列12,10,13,11,16,14,采用冒泡排序算法,经一趟冒泡后,序列的结果是____10,12,11,13,14,16____。(按升序排序)18.设有一棵深度为6的完全二叉树,第6层上有3个结点,该树共有__34_____个结点。(根所在结点为第1层)19.对16个元素的序列用冒泡排序法进行排序,共需要进行___15_____趟冒泡。20.一棵有16个叶结点的哈夫曼树,则该树共有___31____个结点。21.一棵有16个叶结点的哈夫曼树,则该树共有__15_____个非叶结点。22.20个元素进行冒泡法排序,通常第6趟冒泡要进行___14___次元素间的比较。23.在对一组记录(40,24,82,9,1,78,46,31,69)进行直接插入排序(由小到大排序),当把第7个记录46插入到有序表时,为寻找插入位置需比较____3____次。24.对稀疏矩阵进行压缩存储,可采用三元组表,一个6行7列的稀疏矩阵A共有38个零元素,其相应的三元组表共有____4___个元素。三、综合题1.设有序表为(5,8,14,15,33,51,61,73,81,82,93),元素的序号依次为1,2,3,……,11.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点可用序号表示)(2)说明成功查找到元素33需要经过多少次比较?(3)在等概率条件下,给出成功查找的平均查找长度(1)图451148151561828337393(2)4次(3)(1+2*2+3*4+4*4)/11=33/11=352.设数据集合a={1,5,8,3,10,7,13,9}(1)依次取a中各数据,构造一棵二叉排序树。(2)对该二叉树进行查找,成功查找到7要进行多少次元素间的比较?(3)给出对该二叉树中序遍历的序列。(1)图5(2)4次(3)中序遍历1,3,5,7,8,9,10,133.(1)如图1所示,若从顶点a出发,首先经过c按图的深度优先搜索法进行遍历,给出可能得到的一种顶点序列。(1)acdbfeh(2)152364或152634或156234(2)设有向图如图2所示下,写出首先删除顶点1的1种拓扑序列4.设有序表为(30,48,58,70,78,79,90),元素的序号依次为1,2,3,……,7.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用序号表示)(2)给出有序表中经3次比较成功查找到的所有元素(3)说明不成功查找元素59需要经过多少次比较?dceabfhe图11234543465图26(1)图670487930587890(2)30587890(3)3次5.(1)设数据集合a={7,4,9,8,6,5,3},依次取a中各数据,构造一棵二叉排序树。(2)对该二叉树进行查找,成功查找到5要进行多少次元素间的比较?(3)给出对上述二叉排序树进行中序遍历的序列(1)图7(2)4(3)3,4,,5,6,7,8,96.(1)如图3所示,若从顶点a出发,首先经过c按广度优先搜索法进行遍历,给出可能得到的一种顶点序列。(2)同图3所示,若从顶点h出发,按深度优先搜索法进行遍历,给出可能得到的2种顶点序列。a阿decfhedeccdeceec7(3)一组记录的关键字序列为(75,63,95,80,53,45,38,20),利用堆排序的方法建立小根堆(堆顶元素是最小元素),给出按筛选法建立的的初始堆。(1)acefdh(2)hdeacfhdfcae(3)20,53,38,63,75,45,95,80四、程序填空题1.以下函数在a[0]到a[n-1]中,用折半查找算法查找关键字等于k的记录,查找成功返回该记录的下标,
本文标题:数据结构(本)期末综合练习(2015年11月)
链接地址:https://www.777doc.com/doc-2333779 .html