数据结构与算法期末考试复习试题.doc
《数据结构与算法期末考试复习试题.doc》由会员分享,可在线阅读,更多相关《数据结构与算法期末考试复习试题.doc(18页珍藏版)》请在咨信网上搜索。
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各结点的值如何
2、 B结点个数的多少 C对数据有哪些运算 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
3、; i+) for(j=0;jn;j+) s +=Bij; sum = s ; 9下面程序段的时间复杂度是 O(n*m) 。 for( i =0; in; i+) for(j=0;jm;j+) Aij 0; 10下面程序段的时间复杂度是 O(log3n) 。 i 0; while(inext =NULL Chead-next =head D head!=NULL 15带头结点的单链表 head 为空的判定条件是 B 。 Ahead = NULL B head-next =NULL Chead-next =head D head!=NULL 16若某表最常用的操作是在最后一个结点之后插入一个结点
4、或删除最后一个结点,则采用 D 存储方式最节省运算时间。 A单链表 B给出表头指针的单循环链表 C双链表 D带头结点的双循环链表 17需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。 A单链表 B静态链表 C线性链表 D顺序存储结构 18非空的循环单链表 head 的尾结点(由 p 所指向)满足 C 。 Ap-next = NULL Bp = NULL Cp-next =head Dp = head 19在循环双链表的 p 所指的结点之前插入 s 所指结点的操作是 D 。 Ap-prior = s;s-next = p;p-prior-next = s;s-prior
5、= p-prior Bp-prior = s;p-prior-next = s;s-next = p;s-prior = p-prior Cs-next = p;s-prior = p-prior;p-prior = s;p-prior-next = s Ds-next = p;s-prior = p-prior;p-prior-next = s;p-prior = s 20如果最常用的操作是取第 i 个结点及其前驱,则采用 D 存储方式最节省时间。 A单链表 B双链表 C单循环链表 D 顺序表 21在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B 。 AO(
6、1) BO(n) CO(n2) DO(nlog2n) 22在一个长度为 n(n1)的单链表上,设有头和尾两个指针,执行 B 操作与链表的长度有关。 A删除单链表中的第一个元素 B删除单链表中的最后一个元素 C在单链表第一个元素前插入一个新元素 D在单链表最后一个元素后插入一个新元素 23与单链表相比,双链表的优点之一是 D 。 A插入、删除操作更简单 B可以进行随机访问 C可以省略表头指针或表尾指针 D顺序访问相邻结点更灵活 24如果对线性表的操作只有两种,即删除第一个元素,在最后一个元素的后面插入新元素,则最好使用 B 。 A只有表头指针没有表尾指针的循环单链表 B只有表尾指针没有表头指针的
7、循环单链表 C非循环双链表 D循环双链表 25在长度为 n 的顺序表的第 i 个位置上插入一个元素(1 i n+1),元素的移动次数为: A 。 An i + 1 Bn i Ci Di 1 26对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为 C 。 A顺序表 B 用头指针表示的循环单链表 C用尾指针表示的循环单链表 D单链表 27下述哪一条是顺序存储结构的优点? C 。 A 插入运算方便 B 可方便地用于各种逻辑结构的存储表示 C 存储密度大 D 删除运算方便 28下面关于线性表的叙述中,错误的是哪一个? B 。 A 线性表采用顺序存储,必须占用一片连续的存储单元 B 线性表采
8、用顺序存储,便于进行插入和删除操作。 C 线性表采用链式存储,不必占用一片连续的存储单元 D 线性表采用链式存储,便于进行插入和删除操作。 29线性表是具有 n 个 B 的有限序列。 A字符 B数据元素 C数据项 D表元素 30在 n 个结点的线性表的数组实现中,算法的时间复杂度是 O(1)的操作是 A 。 A访问第 i(1=i=n)个结点和求第 i 个结点的直接前驱(1i=n) B在第 i(1=i=n)个结点后插入一个新结点 C删除第 i(1=inext=s;s-next=p-next B s-next=p-next ;p-next=s; Cp-next=s;p-next=s-next Dp
9、-next=s-next;p-next=s 36线性表的顺序存储结构是一种 A 。 A随机存取的存储结构 B顺序存取的存储结构 C索引存取的存储结构 DHash 存取的存储结构 37栈的特点是 B ,队列的特点是 A 。 A先进先出 B先进后出 38栈和队列的共同点是 C 。 A都是先进后出 B都是先进先出 C只允许在端点处插入和删除元素 D没有共同点 39一个栈的进栈序列是 a,b,c,d,e,则栈的不可能的输出序列是 C 。 Aedcba Bdecba Cdceab Dabcde 40设有一个栈,元素依次进栈的顺序为 A、B、C、D、E。下列 C 是不可能的出栈序列。 AA,B,C,D,E
10、 BB,C,D,E,A CE,A,B,C,D DE,D,C,B,A 41以下 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 。 Ast-top != -1 Bst-top = -1 Cst-top != MaxSize D st-top = MaxSize 44判定一个顺序栈 st(最多元素为 M
11、axSize)为满的条件是 D 。 Ast-top != -1 Bst-top = -1 Cst-top != MaxSize Dst-top = MaxSize 45一个队列的入队序列是 1,2,3,4,则队列的输出序列是 B 。 A4,3,2,1 B1,2,3,4 C1,4,3,2 D3,2,4,1 46判定一个循环队列 qu(最多元素为 MaxSize)为空的条件是 C 。 Aqu-rear qu-front =MaxSize Bqu-rear qu-front -1=MaxSize Cqu-rear =qu-front D qu-rear =qu-front -1 47在循环队列中,若
12、 front 与 rear 分别表示对头元素和队尾元素的位置,则判断循环队列空的条件是 C 。 Afront=rear+1 Brear=front+1 Cfront=rear Dfront=0 48向一个栈顶指针为 h 的带头结点的链栈中插入指针 s 所指的结点时,应执行 D 操作。 Ah-next=s ; Bs-next=h ; Cs-next=h ;h =s ; Ds-next=h-next ;h-next=s ; 49输入序列为 ABC,可以变为 CBA 时,经过的栈操作为 B 。 Apush,pop,push,pop,push,pop Bpush,push,push,pop, pop,
13、 pop Cpush,push,pop, pop,push,pop Dpush,pop,push,push,pop, pop 50若栈采用顺序存储方式存储,现两栈共享空间 V1 m,top1、top2分别代表第 1 和第 2 个栈的栈顶,栈 1 的底在 V1,栈 2 的底在 Vm,则栈满的条件是 B 。 A|top2-top1|=0 B top1+1=top2 Ctop1+top2=m Dtop1=top2 51设计一个判别表达式中左、右括号是否配对出现的算法,采用 D 数据结构最佳。 A线性表的顺序存储结构 B队列 C线性表的链式存储结构 D栈 52允许对队列进行的操作有 D 。 A对队列中
14、的元素排序 B取出最近进队的元素 C在队头元素之前插入元素 D删除队头元素 53对于循环队列 D 。 A无法判断队列是否为空 B无法判断队列是否为满 C队列不可能满 D以上说法都不对 54若用一个大小为 6 的数值来实现循环队列,且当前 rear 和 front 的值分别为 0 和 3,当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为 B 。 A1 和 5 B2 和 4 C4 和 2 D5 和 1 55队列的“先进先出”特性是指 D 。 A最早插入队列中的元素总是最后被删除 B当同时进行插入、删除操作时,总是插入操作优先 C每当有删除操作时,总是要先做一次插入操作
15、 D每次从队列中删除的总是最早插入的元素 56和顺序栈相比,链栈有一个比较明显的优势是 A 。 A通常不会出现栈满的情况 B 通常不会出现栈空的情况 C插入操作更容易实现 D删除操作更容易实现 57用不带头结点的单链表存储队列,其头指针指向队头结点,尾指针指向队尾结点,则在进行出队操作时 C 。 A仅修改队头指针 B仅修改队尾指针 C队头、队尾指针都可能要修改 D队头、队尾指针都要修改 58若串 S=software,其子串的数目是 B 。 A8 B37 C36 D9 59串的长度是指 B 。 A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符的个数 D串中所含非空格字符的个数
16、 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 。 ASA141 B SA144 CSA222 DSA225 63数组 A 中,每个元素的长度为 3 个字节,行下标 i 从 1 到 8,列下标 j 从
17、1 到 10,从首地址 SA 开始连续存放的存储器内,该数组按行存放,元素 A58的起始地址为 C 。 ASA141 B SA180 CSA222 DSA225 64若声明一个浮点数数组如下: froat average=new float30; 假设该数组的内存起始位置为 200, average15的内存地址是 C 。 A214 B215 C260 D256 65设二维数组 A1 m,1 n按行存储在数组 B 中,则二维数组元素 Ai,j在一维数组 B 中的下标为 A 。 An*(i-1)+j B n*(i-1)+j-1 Ci*(j-1) Dj*m+i-1 66有一个 10090 的稀疏矩
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击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。