数据结构本期末综合练习12月.doc
《数据结构本期末综合练习12月.doc》由会员分享,可在线阅读,更多相关《数据结构本期末综合练习12月.doc(24页珍藏版)》请在咨信网上搜索。
1、数据结构期末综合练习2014年12月期末综合练习一一、单项选择题1 .单向链表所具备的特点是( )。A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点 2.头指针为head的带头结点的单向链表为空的判定条件是( )为真。A. head= =NULL B. head-next= =NULLC. head-next=NULL; D. head-next!= NULL 3.设有一个长度为18的顺序表,要在第6个元素之前插入一个元素(也就是插入元素作为新表的第6个元素),则移动元素个数为( )。 A12 B5 C. 13 D6 4设有
2、一个长度为32的顺序表,要删除第8个元素需移动元素的个数为( )。 A9 B8 C25 D24 5栈和队列的共同特点是( )。 A都是线性结构 B元素都可以随机进出C都是先进后出 D都是先进先出 6一个栈的进栈序列是2,4,6,8,10,则栈的不可能输出序列是( )(进栈出栈可以交替进行)。A2,4,6,8,10 B8,6,10,2,4C8,10,6,4,2 D10,8,6,4,2 7元素1,3,5,7按顺序依次入队列,按该队列的出队序列进栈,该栈的可能输出序列是( )(进栈出栈可以交替进行)。 A7,5,1,3 B7,3,1,5 C5,1,3,7 D7,5,3,1 8一个队列的入队序列是a,
3、b,c,d,按该队列的可能输出序列使各元素依次入栈,该栈的可能输出序列是 ( )。(进栈出栈可以交替进行)。 Ad,c,b,a Bc,a,b,d Cd,b,a,c Dd,a,b,c 9在一个不带头结点的链队中,假设f和r分别为队头和队尾指针,则对该队列进行出 队操作中并把结点的值保存在变量e中,其运算为e=fdata;和( )。 Ar=rnext; Brnext=r; Cf=fnext; Dfnext=f; 10在一个链队中,假设f和r分别为队头和队尾指针,p指向一个已生成的结点,现要为 该结点的数据域赋值e,并使结点入队的运算为p-data=e; p-next=NULL ; 和( )。A .
4、 f-next=p; f=p; B r-next=p;r=p; C p-next=r;r=p; D p-next=f;f=p; 11设有一个对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),B数组共有45个元素,则该矩阵是( )阶的对称矩阵。A15 B11 C10 D9 12设有一个24阶的对称矩阵A,采用压缩存储的方式(矩阵的第一个元素为a1,1),将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则数组中第30号元素对应于矩阵中的元素是( )。Aa10,8 Ba9,2 C a8,2 Da8 ,5 13. 下列是C语言中abcd
5、321ABCD的子串的选项是( )。 A. 21ABC B.abcABCD C. abcD D. 321a 14. 字符串a1=BEIJING, a2 =BEI , a3= BEFANG a4=“BEFI中最大的是( )。A. a1 B. a2 C. a3 D. a4 15. 字符串a1=BEIJING, a2 =BEF , a3= BEFANG, a4=“BEFI最小的是( ).A. a1 B. a2 C. a3 D. a4 16. 程序段char a =“English”; char *p=a; int n=0; while( *p!=0) n+; p+; 结果中,n的值是( )。 A.
6、6 B.8 C. 5 D.7 17一棵有20个结点采用链式存储的二叉树中,共有( )个指针域为空。 A21 B20 C19 D18 18在一棵二叉树中,若编号为5的结点存在左孩子,则左孩子的顺序编号为( )。 A9 B10 C11 D12 19设一棵哈夫曼树共有18个叶结点,则该树有( )个非叶结点。 A18 B19 C17 D16 20设一棵采用链式存储的二叉树,除叶结点外每个结点度数都为2,该树结点中共有20个指针域为空。则该树有( )个叶结点。A21 B22 C9 D10 21如图1所示的一个图,若从顶点g出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为( )。 Agabecd
7、f Bgacfebd Cgaebcfd Dgaedfcb bdfeCag 图122已知如图2所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则可能得到的一种顶点序列为( )。 Aabcedfg Babcefdg Caebcfdg Dacfdebg bdfecabdfecag 图223线性表以( )方式存储,能进行折半查找。 A关键字有序的 B关键字有序的顺序 C链接 D顺序 24在有序表10,23,32,36,53,66,68,76,87,90,101,120中,用折半查找值53时,经( )次比较后查找成功。A6 B3 C8 D4 25有一个长度为8的有序表,按折半查找对该表进行查找,
8、在等概率情况下查找成功的平均比较次数为( )。A22/8 B20/8 C23/8 D21/8 26有一个长度为11的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为( )。A29/11 B33/11 C26/11 D30/11 27. 排序算法中,从尚未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比较次数尽量少),然后将其放入已排序序列的正确位置的方法是( )。 A折半插入排序 B直接插入排序 C归并排序 D选择排序 28设已有m个元素有序,在未排好序的序列中挑选第m+1个元素,并且只经过一次元素的交换就使第m+1个元素排序到位,该方法是( )。
9、 A堆排序 B简单选择排序 C快速排序 D归并排序 29排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始为空)的一端的方法,称为( )排序。 A堆 B冒泡 C选择 D快速 30一组记录的关键字序列为(32,65,42,24,26,80),利用快速排序,以第一个关键字为分割元素,经过一次划分后结果为( )。 A26,24,32,42,65,80 B24,26,32,42,65,80 C26,24,32,65,42,80 D26,24,32,80,42,65二、填空题1.广义表( a , (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_ 。 2.结构中的
10、数据元素存在一对多的关系称为_结构。3.广义表的( c, a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 。 4.栈的操作特点是_。5. 设顺序队列的类型为typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq为指向顺序队列的指针变量,要进行新元素x的入队操作,按教课书约定,可用语句sq-datasq-rear=x;和_ 。 6.广义表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_。 7. 序列4,2,5,3,8,6,采用冒泡排序
11、算法,经一趟冒泡后,序列的结果是_。(按由小到大顺序) 8. 广义表( (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_ _。9.在对一组记录(50,34,92,19,11,68,56,41,79)进行直接插入排序(由小到大排 序) ,当把第7个记录56插入到有序表时,为寻找插入位置需比较_次。10. 设顺序队列的类型为typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq为指向顺序队列的指针变量,要进行元素的出队操作,并把元素赋给边量x, 按教科书约定,可用语句x=sq-da
12、tasq-front;和_ 。11.数据结构中, _可以由一个或多个数据项组成。 12. 设顺序队列的类型为typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq为指向顺序队列的指针变量,要进行新元素x的入队操作,按教课书约定,可用语句sq-datasq-rear=x;和_。 13循环队列中,设front和rear分别为队头和队尾指针,(最多元素为MaxSize,采用少用一个元素的模式),判断循环队列为满的条件为_为真 。 14. 序列14,12,15,13,18,16,采用冒泡排序算法,经一趟冒泡后,
13、序列的结果是_。(由小到大排序)15排序算法中,从尚未排序序列中依次取出元素与已排序序列(初始为空)中的元素依次进行比较,然后将其放入已排序序列的正确位置的方法是 。16. 数据结构中, _ 之间的抽象关系称为逻辑结构。17对稀疏矩阵进行压缩存储,可采用三元组表,一个6行7列的稀疏矩阵A共有34个零元 素,其相应的三元组表共有_个元素。 18. 循环队列中,设front和rear分别为队头和队尾指针,(最多元素为MaxSize,),判断循环队列为空的条件为_为真。19在双向链表中,要删除p所指的结点,可以先用语句(p-prior)-next=p-next;然后再用语句(p-next)-prio
14、r= _。 20. 排序算法中,从尚未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比较次数尽量少),然后将其放入已排序序列的正确位置的方法是 。21.在双向链表中,每个结点有两个指针域,一个指向结点的直接后继 ,另一个指向_。22. 对稀疏矩阵进行压缩存储,可采用三元组表,矩阵元素a3,4 对应的三元组为_ 。23.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_结构。24在双向链表中,要删除p所指的结点,其中所用的一条语句(p-next)-prior=p-prior; 的功能是:使P所指结点的直接后继的左指针指向_ _。 三、 综合题1.设数据集合a=1,12
15、,5,8,3,10,7,13,9(1)依次取a中各数据,构造一棵二叉排序树。(2)说明如何依据此二叉树得到a的有序序列。(3)对该二叉树进行查找,成功查找到7要进行多少次元素间的比较?(4)给出对该二叉树后序遍历的序列。2.设数据集合a=62,74,30,15,56,48(1)依次取a中各数据,构造一棵二叉排序树。(2)为了成功查找到48需要进行多少次元素间的比较?(3)给出对该二叉树后序遍历的序列。3设有序表为(2, 5, 11, 12, 30, 48, 58, 70, 78, 79, 90) ,元素的序号依次为 1,2,3,,11. (1)画出对上述查找表进行折半查找所对应的判定树(树中结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 本期 综合 练习 12
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。