数据结构与算法期中练习题答案_第1页
数据结构与算法期中练习题答案_第2页
数据结构与算法期中练习题答案_第3页
数据结构与算法期中练习题答案_第4页
数据结构与算法期中练习题答案_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、 数据结构与算法期中练习题一、 写出以下各词语的对应中文queue 队列 singly linked lists 单链表 storge structure 存储结构 time complexity 时间复杂度 abstract data type (adt) 抽象数据类型 二、 选择题1、在数据结构中,线性结构中元素之间存在_a_关系。 a: 一对一b: 一对多c: 多对一d: 多对多2、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的b_和运算等的学科。a: 结构b: 关系c: 操作d: 算法3、算法分析的两个主要方面是_a_。a: 空间复杂度和时间复杂度b: 正确

2、性和简明性c: 可读性和文档性d: 数据复杂性和程序复杂性4、顺序表中逻辑上相邻的节点其物理位置也_a_。a: 一定相邻b: 不必相邻c: 按某种规律排列d: 无要求5、下面两个图各表现一批数据的结构,其中 c 。a: 左边表现的是逻辑结构,右边表现的是物理结构b: 右边表现的是逻辑结构,左边表现的是物理结构c: 两者表现的都是逻辑结构d: 两者表现的都是物理结构6、 向一个长度为n的顺序表的第i个元素(1<=i<=n)之前插入一个元素时,需向后移动_d_个元素。a: ib: n-ic: n-i-1d: n-i+17、在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p

3、之间插入s结点,则执行_c_。a: s->next=p->next; p->next=s;b: p->next=s->next; s->next=p;c: q->next=s; s->next=p;d: p->next=s; s->next=q;8、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是_c_。a: edcbab: decbac: dceabd: abcde9、循环队列用数组a0,m-1存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是_a_。a: (rear-front+m)%m

4、b: rear-front+1c: rear-front-1d: rear-front10、关于空格串,下列说法中正确的有_d_。a: 空格串就是空串b: 空格串是零个字符的串c: 空格串的长度为零d: 空格串的长度就是其包含的空格个数11、数组a中,每个元素a的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址sa开始连续存放在存储器内,该数组按行存放时,元素a85的起始地址为_c_。a: sa+140b: sa+144c: sa+222d: sa+22512、 深度为4的二叉树至多有_b_个结点。a:14b:15c:16d:1713、对于一棵满二叉树,m个树叶,n个节点,深度为

5、h,则_d_。a: n=h+mb: h+m=2nc: m=h-1d: n=2h-114、具有65个结点的完全二叉树其深度为_b_。(根的层次号为1)a: 8b: 7c: 6d: 515、满二叉树_a_二叉树。a: 一定是完全b: 不一定是完全c: 不是d: 不是完全16、将一棵有100个节点的完全二叉树从上到下,从左到右依次对节点进行编号,根节点的编号为1,则编号为49的节点的左孩子编号为_b_。a: 99b: 98c: 50d: 4817、将递归算法转换成对应的非递归算法时,通常需要使用_a_。a: 栈b: 队列c: 链表d: 树18、按照二叉树的定义,具有3个结点的二叉树有_c_种。a:

6、3b: 4c: 5d: 619、如图所示的4棵二叉树中,_c_不是完全二叉树。a: b: c: d: 20、所谓稀疏矩阵指的是_c_。a: 零元素个数较多的矩阵b: 零元素个数占矩阵元素总个数一半的矩阵c: 零元素个数远远多于非零元素个数且分布没有规律的矩阵d: 包含有零元素的矩阵三、已知线性链表如下图,头指针为la,写出语句序列使左图中的指针指向改成右图中的指针指向。答:p=la->next;la->next=p->next; p->next=la;la=p;四、在一个c语言程序中,有结构类型student的定义和结构数组allstudents的声明如下:struct

7、 student char name8; int number;student allstudents1050; allstudents是一个二维数组,它的每个元素都是包含name和number的结构类型。已知在c语言中,二维数组使用以行序为主序的存储结构,char类型占用1字节,int类型占用4字节。假定allstudents在内存中的起始存储位置是2000,请写出计算allstudentsij的存储位置的算式,并计算allstudents35的存储位置。答: (1) allstudentsij的存储位置=2000+(i*50+j)*12 (2) allstudents35的存储位置=200

8、0(3*50+5)*12=3860五、用下标从0到4的一维数组存储一个循环队列,目前其中有两个元素a、b,状态如图(a)。如果此后有17个数据元素c、d、p、q、r、s依次进队列,其间又有16个元素先后出队列,请在图(b)中填写队列最后的状态,包括其中的元素和指针的位置。答:rearrbfrontqfrontarears(a)(b)六、序列(a,b,c,d,e)已存在静态链表如下图a,头指针指向1号结点。请完成:1在静态链表中标出此序列的逻辑关系。2画出依次执行了b前插入f,删除e,c后插入g操作后的新的静态链表图b。答:14 删除e,c后插入g操作后142c52c33e3g54a64a75d

9、35d6b26b277f6图a图b插入”f”后142c53e4a75d36b27f6图b七、已知一个稀疏矩阵a如下,填写下表1给出它的三元组顺序表表示2给出它的转置矩阵b的三元组顺序表表示020000100000030000000040050006答:ijv转置后(排序)ijv122121211212323233454255525544566656a.data b.dataa.mu5b.mu6a.nu6b.nu5a.tu6b.tu6转置后(未排序)ijv212121233544255656八、任意一棵有n个结点的二叉树,已知它有m个叶子结点。试证明非叶子结点中度数为2的有m-1个,其余的度数为

10、1。证: 设二叉树中度为0的结点数为n0, 度为1的结点数为n1,度为2的结点数为n2,二叉树中分支数为b n=n0+n1+n2n=m+n1+n2又 b=0+n1+2*n2 (其中: 0-度为0的结点的分支数(叶子结点) ,n1-度为1的结点的分支数,2*n2-度为2的结点的分支数.又 n=b+1m+n1+n2=0+n1+2*n2+1m=n2+1 n2=m-1证明:设度为1和2 的结点数是n1和n2,则二叉树结点数n为n=m+n1+n2 (1)由于二叉树根结点没有分枝所指,度为1和2的结点各有1个和2个分枝,度为0 的结点没有分枝,故二叉树的结点数n与分枝数b有如下关系n=b+1=n1+2*n

11、2+1.(2)由(1)和(2),得n2=m-1。即n个结点的二叉树,若叶子结点数是m,则非叶子结点中有(m-1)个度为2,其余度为1。九、写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,an)逆置为(an,an-1,a1)。答:#define listsize 100 / 假定表空间大小为100typedef int datatype;/假定datatype的类型为int型typedef structdatatype datalistsize;/ 向量data用于存放表结点int length; / 当前的表长度 seqlist;/ 顺序表结构定义同上题void re

12、verselist( seqlist *l)datatype temp ; /设置临时空间用于存放dataint i;for (i=0;i<=l->length/2;i+)/l->length/2为整除运算 temp = l->datai; /交换数据l -> data i = l -> data l -> length-1-i;l -> data l -> length - 1 - i = temp;十、写一算法,实现统计带表头的单链表中元素值为奇数的结点个数。答:单链表结点的类型定义如下: typedef int elemtype; /定义数据域的类型typedef struct lnode /定义结点

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论