数据结构-复习题-习题-全六章-含答案.doc
《数据结构-复习题-习题-全六章-含答案.doc》由会员分享,可在线阅读,更多相关《数据结构-复习题-习题-全六章-含答案.doc(30页珍藏版)》请在咨信网上搜索。
1、数据结构期末复习练习题( 适用围:电大开放专科计算机类专业 )电工教学部计算中心第一章 绪 论 一、单项选择题 1. 一个数组元素ai与_的表示等价。A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2. 对于两个函数,假设函数名一样,但只是_不同那么不是重载函数。A、参数类型 B、参数个数 C、函数类型3. 假设需要利用形参直接访问实参,那么应把形参变量说明为_参数A、指针 B、引用 C、 值4. 下面程序段的时间复杂度为_。 for(int i=0; im; i+) for(int j=0; jn; j+) aij=i*j;A、 O(m2) B、 O(n2) C、 O(m*
2、n) D、 O(m+n) 5. 执行下面程序段时,执行S语句的次数为_。 for(int i=1; i=n; i+) for(int j=1; j=i; j+) S;A、 n2 B、 n2/2 C、 n(n+1) D、 n(n+1)/2 6. 下面算法的时间复杂度为_。int f(unsigned int n) if(n=0 | n=1) return 1; else return n*f(n-1); A、 O(1) B、 O(n) C、 O(n2) D、 O(n!) 二、填空题1. 数据的逻辑结构被分为_、_、_和_四种。 2. 数据的存储结构被分为_、_、_和_四种。3. 在线性结构、树形
3、结构和图形结构中,前驱和后继结点之间分别存在着_、_和_的联系。4. 一种抽象数据类型包括_和_两个局部。5. 当一个形参类型的长度较大时,应最好说明为_,以节省参数值的传输时间和存储参数的空间。6. 当需要用一个形参访问对应的实参时,那么该形参应说明为_。7. 在函数中对引用形参的修改就是对相应_的修改,对_形参的修改只局限在该函数的部,不会反映到对应的实参上。8. 当需要进展标准I/O操作时,那么应在程序文件中包含_头文件,当需要进展文件I/O操作时,那么应在程序文件中包含_头文件。9. 在包含有_头文件的程序文件中,使用_能够产生出020之间的一个随机整数。10. 一个数组a所占有的存储
4、空间的大小即数组长度为_,下标为i的元素ai的存储地址为_,或者为_。11. 函数重载要求_、_或_有所不同。12. 对于双目操作符,其重载函数带有_个参数,其中至少有一个为_的类型。13. 假设对象ra和rb中至少有一个是属于用户定义的类型,那么执行ra=rb时,需要调用_重载函数,该函数的第一个参数应与_的类型一样,第二个参数应与_的类型一样。14. 从一维数组an中顺序查找出一个最大值元素的时间复杂度为_,输出一个二维数组bmn中所有元素值的时间复杂度为_。15. 在下面程序段中,s=s+p语句的执行次数为_,p*=j语句的执行次数为_,该程序段的时间复杂度为_。int i=0,s=0;
5、 while(+i=n) int p=1; for(int j=1;jnext = HL; B、p-next = HL; HL = p; C、p-next = HL; p = HL; D、p-next = HL-next; HL-next = p; 5在一个单链表HL中,假设要在指针q所指的结点的后面插入一个由指针p所指的结点,那么执行。 A、q-next = p-next ; p-next = q; B、p-next = q-next; q = p; C、q-next = p-next; p-next = q; D、p-next = q-next ; q-next = p; 6在一个单链表H
6、L中,假设要删除由指针q所指向结点的后继结点,那么执行。 A、p = q-next ; p-next = q-next; B、p = q-next ; q-next = p; C、p = q-next ; q-next = p-next; D、q-next = q-next-next; q-next = q;二、填空题1在线性表的单存储结构中,每个结点包含有两个域,一个叫域,另一个叫域。 2在下面数组a中存储着一个线性表,表头指针为a0.next,那么该线性表为。 3对于一个长度为n的顺序存储的线性表,在表头插入元素的时间复杂度为,在表尾插入元素的时间复杂度为。 4对于一个长度为n的单存储的线
7、性表,在表头插入元素的时间复杂度为,在表尾插入元素的时间复杂度为。5在线性表的顺序存储中,假设一个元素的下标为i,那么它的前驱元素的下标为,后继元素的下标为。 6在线性表的单存储中,假设一个元素所在结点的地址为p,那么其后继结点的地址为,假设假定p为一个数组a中的下标,那么其后继结点的下标为。 7在循环单链表中,最后一个结点的指针指向结点。 8在双向链表中每个结点包含有两个指针域,一个指向其结点,另一个指向其结点。 9在循环双向链表中表头结点的左指针域指向结点,最后一个结点的右指针域指向结点。 10在以HL为表头指针的带表头附加结点的单链表和循环单链表中,链表为空的条件分别为和。 三、应用题1
8、在下面的每个程序段中,假定线性表La的类型为List,元素类型ElemType为int,并假定每个程序段是连续执行的,试写出每个程序段执行后所得到的线性表La。(1) InitList(La);int a=48,26,57,34,62,79;for(i=0; i6; i+)InsertFront(La,ai);TraverseList(La); (2) InitList(La);for(i=0; i6; i+)Insert(La,ai);TraverseList(La);(3) ClearList(La);for(i=0; i6; i+)InsertRear(La,ai);Delete(La,
9、 a5);Sort(La);Insert(La,a5/2);TraverseList(La);2写出下面函数被调用执行后,得到的以HL为表头指针的单链表中的数据元素序列。void AA(LNode * & HL) InitList(HL); InsertRear(HL,30); InsertRear(HL,50);int a5 = 15,8,9,26,12;for ( int i=0; i5; i+ ) InsertFront(HL,ai); 3对于List类型的线性表,编写出以下每个算法。(1) 从线性表中删除具有最小值的元素并由函数返回,空出的位置由最后一个元素填补,假设线性表为空那么显示
10、出错信息并退出运行。(2) 从线性表中删除第i个元素并由函数返回。(3) 向线性表中第i个元素位置插入一个元素。(4) 从线性表中删除具有给定值x的所有元素。 4对于结点类型为LNode的单链表,编写出以下每个算法。(1) 删除单链表中的第i个结点。 (2) 在有序单链表中插入一个元素x的结点。 (3) 从单链表中查找出所有元素的最大值,该值由函数返回,假设单链表为空,那么显示出错信息并停止运行。(4) 统计出单链表中结点的值等于给定值x的结点数。第三章 稀疏矩阵和广义表 一、单项选择题1. 在稀疏矩阵的带行指针向量的存储中,每个行单链表中的结点都具有一样的_。A、行号 B、列号 C、 元素值
11、 D、地址2. 设一个广义表中结点的个数为n,那么求广义表深度算法的时间复杂度为_。A、O(1) B、O(n) C、O(n2) D、O(log2n) 二、填空题1. 在一个稀疏矩阵中,每个非零元素所对应的三元组包括该元素的_、_和_三项。 2. 在稀疏矩阵所对应的三元组线性表中,每个三元组元素按_为主序、_为辅序的次序排列。 3. 在初始化一个稀疏矩阵的函数定义中,矩阵形参应说明为_参数。 4. 在稀疏矩阵的顺序存储中,利用一个数组来存储非零元素,该数组的长度应_对应三元组线性表的长度。 5在稀疏矩阵的带行指针向量的存储中,每个结点包含有_个域,在相应的十字存储中,每个结点包含有_个域。 6在
12、稀疏矩阵的十字存储中,每个结点的down指针域指向_一样的下一个结点,right指针域指向_一样的下一个结点。 7一个广义表中的元素分为_元素和_元素两类。 8一个广义表的深度等于_嵌套的最大层数。 9在广义表的存储结构中,每个结点均包含有_个域。 10在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同,各自分别为_域和_域。 11假设把整个广义表也看为一个表结点,那么该结点的tag域的值为_,next域的值为_。 三、应用题1. 一个稀疏矩阵如以下图所示: 0 4 0 0 0 0 0 0 0 0 -3 0 0 1 8 0 0 0 0 0 0 0 0 0 5 0 0 0 0 -7 0
13、 0 0 2 0 0 0 0 6 0 0 0 具有6行7列的一个稀疏矩阵(1) 写出它的三元组线性表;(2) 给出它的顺序存储表示; (3) 给出它的转置矩阵的三元组线性表和顺序存储表示;2. 画出以下每个广义表的带表头附加结点的存储结构图并分别计算出它们的长度和深度。 (1) A=()(2) B=(a,b,c)(3) C=(a,(b,(c)(4) D=(a,b),(c,d)(5) E=(a,(b,(c,d),(e)(6) F=(a,(b,(),c),(d),e)第四章 栈和队列一、单项选择题 1栈的插入与删除操作在进展。 A、栈顶 B、栈底 C、任意位置 D、指定位置 2当利用大小为N的一维
14、数组顺序存储一个栈时,假定用top=N表示栈空,那么向这个栈插入一个元素时,首先应执行语句修改top指针。 A、top+ B、top- C、top=0 D、top 3假设让元素1,2,3依次进栈,那么出栈次序不可能出现种情况。 A、3,2,1 B、2,1,3 C、3,1,2 D、1,3,2 4在一个循环顺序队列中,队首指针指向队首元素的位置。 A、前一个 B、后一个 C、当前 D、后面 5当利用大小为N的一维数组顺序存储一个循环队列时,该队列的最大长度为。 A、N-2 B、N-1 C、N D、N+1 6从一个循环顺序队列删除元素时,首先需要。 A、前移一位队首指针 B、后移一位队首指针 C、取
15、出队首指针所指位置上的元素 D、取出队尾指针所指位置上的元素7假定一个循环顺序队列的队首和队尾指针分别为f和r,那么判断队空的条件是。 A、f+1=r B、r+1=f C、f=0 D、f=r 8假定一个链队的队首和队尾指针分别为front和rear,那么判断队空的条件是。 A、front=rear B、front!=NULL C、rear!=NULL D、front=NULL二、填空题 1队列的插入操作在进展,删除操作在进展。 2栈又称为表,队列又称为表。 3向一个顺序栈插入一个元素时,首先使后移一个位置,然后把待插入元素到这个位置上。 4从一个栈中删除元素时,首先取出,然后再前移一位。 5在
16、一个循环顺序队列Q中,判断队空的条件为,判断队满的条件为。 6在一个顺序栈中,假设栈顶指针等于,那么为空栈;假设栈顶指针等于,那么为满栈。 7在一个链栈中,假设栈顶指针等于NULL,那么为;在一个链队中,假设队首指针与队尾指针的值一样,那么表示该队列为或该队列为。 8向一个链栈插入一个新结点时,首先把栈顶指针的值赋给,然后把新结点的存储位置赋给。 9从一个链栈中删除一个结点时,需要把栈顶结点的值赋给。 10向一个顺序队列插入元素时,需要首先移动,然后再向所指位置新插入的元素。 11、当用长度为N的一维数组顺序存储一个栈时,假定用top=N表示栈空,那么表示栈满的条件为。 12向一个栈顶指针为H
17、S的链栈中插入一个新结点*P果,应执行和操作。 13从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时,应执行操作。 14假定front和rear分别为一个链队的队首和队尾指针,那么该链队中只有一个结点的条件为。15. 中缀算术表达式3+4/(25-(6+15)*8 所对应的后缀算术表达式为。 16. 后缀算术表达式24 8 + 3 * 4 10 7 - * / 所对应的中缀算术表达式为,其值为。三、应用题执行下面函数调用后得到的输出结果是什么?void AF(Queue & Q) InitQueue(Q); int a4 = 5,8,12,15 ;for ( int
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习题 习题 全六章 答案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【二***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【二***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。