数据结构期末考试题及答案.doc
《数据结构期末考试题及答案.doc》由会员分享,可在线阅读,更多相关《数据结构期末考试题及答案.doc(29页珍藏版)》请在咨信网上搜索。
1、 数据结构期末考试题及答案一、 选择题1在数据结构中, 从逻辑上能够把数据结构分为 C 。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构2数据结构在计算机内存中的表示是指A。A数据的存储结构B数据结构C数据的逻辑结构 D数据元素之间的关系3在数据结构中, 与所使用的计算机无关的是数据的 A 结构。A逻辑B存储C逻辑和存储D物理4在存储数据时, 一般不但要存储各数据元素的值, 而且还要存储 C 。A数据的处理方法B数据元素的类型C数据元素之间的关系D数据的存储方法5在决定选取何种存储结构时, 一般不考虑 A 。A各结点的值如何B结点个数的多少C对数据有哪
2、些运算D所用的编程语言实现这种结构是否方便。6以下说法正确的是D 。A数据项是数据的基本单位B数据元素是数据的最小单位C数据结构是带结构的数据项的集合D一些表面上很不相同的数据能够有相同的逻辑结构7算法分析的目的是C , 算法分析的两个主要方面是A 。( 1) A找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进 C分析算法的易读性和文档性( 2) A空间复杂度和时间复杂度 B正确性和简明性C可读性和文档性 D数据复杂性和程序复杂性8下面程序段的时间复杂度是O( n2) 。s 0; for( I 0; in; i) for( j0; jn; j) s Bij; sum
3、 s ; 9下面程序段的时间复杂度是O( n*m) 。for( i 0; in; i) for( j0; jm; j) Aij 0; 10下面程序段的时间复杂度是O( log3n) 。i 0; while( in) i i * 3; 11在以下的叙述中, 正确的是 B 。A线性表的顺序存储结构优于链表存储结构B二维数组是其数据元素为线性表的线性表C栈的操作方式是先进先出D队列的操作方式是先进后出12一般要求同一逻辑结构中的所有数据元素具有相同的特性, 这意味着B 。A数据元素具有同一特点B不但数据元素所包含的数据项的个数要相同, 而且对应的数据项的类型要一致C每个数据元素都一样D数据元素所包含
4、的数据项的个数要相等13链表不具备的特点是A 。A可随机访问任一结点B插入删除不需要移动元素C不必事先估计存储空间D所需空间与其长度成正比14不带头结点的单链表head为空的判定条件是 A。next NULLCheadnext headD head! NULL15带头结点的单链表head为空的判定条件是 B。next NULLCheadnext headD head! NULL16若某表最常见的操作是在最后一个结点之后插入一个结点或删除最后一个结点, 则采用D存储方式最节省运算时间。A单链表 B给出表头指针的单循环链表C双链表 D带头结点的双循环链表17需要分配较大空间, 线插入和删除不需要移
5、动元素的性表, 其存储结构是 B 。A单链表 B静态链表C线性链表 D顺序存储结构18非空的循环单链表head的尾结点( 由p所指向) 满足C 。Apnext NULLBp NULLCpnext head Dp head19在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。AppriorpriorBppriorpriorCspriornext sDspriorprior s20如果最常见的操作是取第i个结点及其前驱, 则采用D存储方式最节省时间。A单链表 B双链表C单循环链表D 顺序表21在一个具有n个结点的有序单链表中插入一个新结点并依然保持有序的时间复杂度是B 。AO( 1) B
6、O( n) CO( n2) DO( nlog2n) 22在一个长度为n( n1) 的单链表上, 设有头和尾两个指针, 执行 B操作与链表的长度有关。A删除单链表中的第一个元素B删除单链表中的最后一个元素C在单链表第一个元素前插入一个新元素D在单链表最后一个元素后插入一个新元素23与单链表相比, 双链表的优点之一是D。A插入、 删除操作更简单B能够进行随机访问C能够省略表头指针或表尾指针D顺序访问相邻结点更灵活24如果对线性表的操作只有两种, 即删除第一个元素, 在最后一个元素的后面插入新元素, 则最好使用 B 。A只有表头指针没有表尾指针的循环单链表B只有表尾指针没有表头指针的循环单链表C非循
7、环双链表D循环双链表25在长度为n的顺序表的第i个位置上插入一个元素( 1 i n1) , 元素的移动次数为: A 。An i 1Bn iCiDi 126对于只在表的首、 尾两端进行插入操作的线性表, 宜采用的存储结构为 C。A顺序表 B 用头指针表示的循环单链表C用尾指针表示的循环单链表 D单链表27下述哪一条是顺序存储结构的优点? C。A插入运算方便 B可方便地用于各种逻辑结构的存储表示C存储密度大 D删除运算方便28下面关于线性表的叙述中, 错误的是哪一个? B。A线性表采用顺序存储, 必须占用一片连续的存储单元B线性表采用顺序存储, 便于进行插入和删除操作。C线性表采用链式存储, 不必
8、占用一片连续的存储单元D线性表采用链式存储, 便于进行插入和删除操作。29线性表是具有n个 B 的有限序列。A字符B数据元素 C数据项D表元素30在n个结点的线性表的数组实现中, 算法的时间复杂度是O( 1) 的操作是 A 。A访问第i( 1in) 个结点和求第i个结点的直接前驱( 1in) B在第i( 1in) 个结点后插入一个新结点C删除第i( 1in) 个结点D以上都不对31若长度为n的线性表采用顺序存储结构, 在其第i个位置插入一个新元素的算法的时间复杂度为C。AO( 0) BO( 1) CO( n) DO( n2) 32对于顺序存储的线性表, 访问结点和增加、 删除结点的时间复杂度为
9、 C。AO( n) O( n) BO( n) O( 1) CO( 1) O( n) DO( 1) O( 1) 33线性表( a1, a2, , an) 以链式方式存储, 访问第i位置元素的时间复杂度为 C。AO( 0) BO( 1) CO( n) DO( n2) 34单链表中, 增加一个头结点的目的是为了C。A使单链表至少有一个结点 B标识表结点中首结点的位置C方面运算的实现 D说明单链表是线性表的链式存储35在单链表指针为p的结点之后插入指针为s的结点, 正确的操作是 B 。Apnextpnextpnexts; Cpnextsnextsnext; pnexts36线性表的顺序存储结构是一种A
10、 。A随机存取的存储结构B顺序存取的存储结构C索引存取的存储结构DHash存取的存储结构37栈的特点是 B , 队列的特点是A。A先进先出 B先进后出38栈和队列的共同点是C 。A都是先进后出 B都是先进先出C只允许在端点处插入和删除元素 D没有共同点39一个栈的进栈序列是a, b, c, d, e, 则栈的不可能的输出序列是 C 。AedcbaBdecbaCdceabDabcde40设有一个栈, 元素依次进栈的顺序为A、 B、 C、 D、 E。下列 C 是不可能的出栈序列。 AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A4
11、1以下 B 不是队列的基本运算?A从队尾插入一个新元素B从队列中删除第i个元素C判断一个队列是否为空D读取队头元素的值42若已知一个栈的进栈序列是1, 2, 3, , n, 其输出序列为p1, p2, p3, , pn, 若p1n, 则pi为 C。Ai Bni Cni1 D不确定43判定一个顺序栈st( 最多元素为MaxSize) 为空的条件是B 。Asttop ! top 1Csttop ! top MaxSize44判定一个顺序栈st( 最多元素为MaxSize) 为满的条件是D 。Asttop ! top 1Csttop ! top MaxSize45一个队列的入队序列是1, 2, 3,
12、 4, 则队列的输出序列是B 。A4, 3, 2, 1 B1, 2, 3, 4C1, 4, 3, 2 D3, 2, 4, 146判定一个循环队列qu( 最多元素为MaxSize) 为空的条件是C 。Aqurear qurear qufront 1MaxSizeCqufront 147在循环队列中, 若front与rear 分别表示对头元素和队尾元素的位置, 则判断循环队列空的条件是 C。Afrontrear1 Brearfront1 Cfrontrear Dfront048向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时, 应执行D操作。Ahnexth ; Csnexthnexts
13、; 49输入序列为ABC, 能够变为CBA时, 经过的栈操作为B。Apush, pop, push, pop, push, popBpush, push, push, pop, pop, popCpush, push, pop, pop, push, popDpush, pop, push, push, pop, pop50若栈采用顺序存储方式存储, 现两栈共享空间V1m, top1、 top2分别代表第1和第2个栈的栈顶, 栈1的底在V1, 栈2的底在Vm, 则栈满的条件是B。A|top2top1|0 B top11top2 Ctop1top2mDtop1top251设计一个判别表示式中左、
14、 右括号是否配对出现的算法, 采用D 数据结构最佳。A线性表的顺序存储结构 B队列 C线性表的链式存储结构D栈52允许对队列进行的操作有D。A对队列中的元素排序B取出最近进队的元素C在队头元素之前插入元素D删除队头元素53对于循环队列D 。A无法判断队列是否为空 B无法判断队列是否为满C队列不可能满 D以上说法都不对54若用一个大小为6的数值来实现循环队列, 且当前rear和front的值分别为0和3, 当从队列中删除一个元素, 再加入两个元素后, rear和front的值分别为 B。A1和5 B2和4 C4和2D5和155队列的”先进先出”特性是指 D 。A最早插入队列中的元素总是最后被删除
15、B当同时进行插入、 删除操作时, 总是插入操作优先C每当有删除操作时, 总是要先做一次插入操作D每次从队列中删除的总是最早插入的元素56和顺序栈相比, 链栈有一个比较明显的优势是A 。A一般不会出现栈满的情况 B 一般不会出现栈空的情况C插入操作更容易实现 D删除操作更容易实现57用不带头结点的单链表存储队列, 其头指针指向队头结点, 尾指针指向队尾结点, 则在进行出队操作时 C。A仅修改队头指针B仅修改队尾指针C队头、 队尾指针都可能要修改D队头、 队尾指针都要修改58若串Ssoftware, 其子串的数目是 B 。N( n+1) /2+1个空串=A8 B37 C36D959串的长度是指B
16、。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数60串是一种特殊的线性表, 其特殊性体现在B 。A能够顺序存储B数据元素是一个字符C能够链式存储D数据元素能够是多个字符61设有两个串p和q, 求q在p中首次出现的位置的运算称为B。A连接 B 模式匹配 C求子串D求串长62数组A中, 每个元素的长度为3个字节, 行下标i从1到8, 列下标j从1到10, 从首地址SA开始连续存放的存储器内, 该数组按行存放, 元素A85的起始地址为 C。 ( 8-1) *10+( 5-1) *3ASA141B SA144 CSA222DSA22563数组A中,
17、每个元素的长度为3个字节, 行下标i从1到8, 列下标j从1到10, 从首地址SA开始连续存放的存储器内, 该数组按行存放, 元素A58的起始地址为 C 。ASA141B SA180 CSA222DSA22564若声明一个浮点数数组如下: froat averagenew float30; 假设该数组的内存起始位置为200, average15的内存地址是C。A214 B215 C260D25665设二维数组A1 m, 1 n按行存储在数组B中, 则二维数组元素Ai, j在一维数组B中的下标为 A 。An*( i1) jB n*( i1) j1Ci*( j1) Dj*mi166有一个10090
18、的稀疏矩阵, 非0元素有10, 设每个整型数占2个字节, 则用三元组表示该矩阵时, 所需的字节数是B。A20 B 66C18 000 D3367数组A0 4, 1 3, 57中含有的元素个数是A 。A55 B 45C36 D1668对矩阵进行压缩存储是为了D。A方便运算B 方便存储C提高运算速度 D减少存储空间69设有一个10阶的对称矩阵A, 采用压缩存储方式, 以行序为主存储, a1, 1为第一个元素, 其存储地址为1, 每个元素占1个地址空间, 则a8, 5的地址为B。A13B 33 C18D4070稀疏矩阵一般的压缩存储方式有两种, 即C 。A二维数组和三维数组 B三元组和散列C三元组和
- 配套讲稿:
如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。