软件技术基础总复习题及参考答案.doc
《软件技术基础总复习题及参考答案.doc》由会员分享,可在线阅读,更多相关《软件技术基础总复习题及参考答案.doc(40页珍藏版)》请在咨信网上搜索。
1、一、 选择题 软件技术基础 总复习题及参考答案1、 线性表若是采用链式存储结构时,要求内存中可用存储单元的地址 D 。 A、必须是连续的B、部分地址必须是连续的 C、一定是不连续的D、连续或不连续都可以 2、 栈和队列都是 B。 A、顺序存贮的线性结构B、限制存取点的线性结构 C、链接存贮的线性结构D、限制存取点的非线性结构 3、 与线性表的链接存贮不相符合的特性是 C。 A、便于插、删运算B、存贮空间动态分配 C、需要连续的存贮空间 D、只能顺序查找 4、 设二叉树的根为第一层,则第 i 层上的结点数最多有 B 。 ii A、B、+1 C、i -D、i -1 5、 如将一棵有 n 个结点的完
2、全二叉树按顺序存放方式,存放在下标编号为 0, 1, n-1 的一维数组中,设某结点下标为 k(k0),则其双亲结点的下标是 A 。 A、(k-1)/2 B、(k+1)/2C、k/2 D、k-1 6、 由权值分别为 3,8,6,2,5 的叶子结点生成一棵霍夫曼树,它的带权路径长度为 A 。 A、53B、48C、72D、24 7、 设 I 和 O 分别表示入栈和出栈操作,栈的初态和终态都为空,则下列操作序列 合法的有_ D_ _。 A、IOIOOIOI B、IOOIOIIO C、IIIOIOIOO D、IIOIIOOO 8、 二叉树的前序序列为 EFHIGJK,中序序列为 HFIEJKG,则二叉
3、树的根为 C。 A、KB、G C、ED、H 9、 对有序表 -1, 0, 1, 3, 4, 6, 8, 10, 12 进行折半查找,则查找 12 需要 比较的次数为 B。 A、3B、4 C、5D、6 10、 在一个单链表中,若 q 结点是 p 结点的前驱结点,若在 q 与 p 之间插入结点 s, 则执行 D。 A、slink = plink; plink = s; B、plink = s; slink = q; C、plink = slink; slink = p; D、qlink = s; slink = p; 11、 一个栈的入栈序列为 a,b,c,则出栈序列不可能的是 C 。 A、c,b
4、,a B、b,a,cC、c,a,b D、a,c,b 12、 如果将一棵有 n 个结点的完全二叉树按层次遍历次序,存放在下标编号为 0, 1, , n-1 的一维数组中,设某结点下标为 k( k 0 ),如果其左孩子存在, 则其左孩子结点的下标是 C。 A、2k 1 B、2k C、2k + 1 D、2k + 2 13、 用整数 5, 7, 3, 6, 4 作为五个树叶的权值,可以构造一棵带权路径长度值为 C的霍夫曼树。 A、78 B、62 C、57 D、25 14、 设单链表中结点结构为(data,link),若想删除结点*p 的直接后继,则应执行 下列哪一个操作 A 。 A、p-link=p-
5、link-link; B、p=p-link; p-link=p-link-link; C、p-link=p-link; D、p=p-link-link; 15、 顺序表是线性表的 B 。 A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构 16、 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素,则采用 A 存储方式最节省时间。 A、顺序表 B、单链表 C、双链表 D、单循环链表 17、 当利用大小为 n 的数组顺序存储一个栈时,假定用 top= =n 表示栈空,则向这 个栈插入一个元素时,首先应执行 B 语句修改 top 指针。 A、top+;B、t
6、op-; C、top=0;D、top; 18、 对于任何一棵二叉树 T,如果其终端结点数为 n0,度为 2 的结点为 n2.,则 A A、n0= n2+1 B、n2= n0+1 C、n0= 2n2+1 D、n2=2n0+1 19、 具有 35 个结点的完全二叉树的深度为 A 。 A、5 B、6 C、7 D、8 20、 在有向图中,所有顶点的入度之和是所有顶点出度之和的 B 倍。 A、0.5 B、1 C、2 D、4 21、 若用冒泡排序法对序列(18,14,6,27,8,12,16,52,10,26,47,29,41,24)从小到大进行排序,共要进行 B 次比较。 A、33 B、45 C、70
7、D、91 22、 对含有 B 个结点的非空二叉树,采用任何一种遍历方式,其结点访问序 列均相同。 A、0 B、1 C、2 D、不存在这样的二叉树 23、 数据结构是一门研究非数值计算的程序设计问题中计算机的 A以及它 们之间的 B和运算等的学科。A.数据元素B.计算方法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法 24、 数据结构在计算机内存中的表示是指 A。A.数据的存储结构B.数据结构 C.数据的逻辑结构D.数据元素之间的关系25、 在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C。 A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法26、
8、 在数据结构中,从逻辑上可以把数据结构分成 C 。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 27、 带头结点的单链表 head 为空的判定条件是 B 。 A. head= =NULL B. head-next= =NULL C. head-next= =head D. head ! NULL 28、 在循环双链表的 p 所指结点之前插入 s 所指结点的操作是 D 。 A. p-prior=s;s-next=p;p-priornext=s;s-prior=p-prior; B. p-prior=s;p-prior-next=s;s-ne
9、xt=p;s-prior=p-prior; C .s-next=p;s-prior=p-prior;p-prior=s;p-right-next=s; D. s-next=p;s-prior=p-prior;p-priornext=s;p-prior=s; 29、 需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。 A.单链表 B.静态链表 C.线性链表 D.顺序存储结构 30、 栈和队列的共同点是 C 。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 31、 向一个栈顶指针为 hs 的链栈中插入一个 s 所指结点时,则执行 C 。
10、 A. hs-next=s; B. s-next=hs-next; hs-next=s; C. s-next=hs; hs=s; D. s-next=hs; hs=hs-next; 32、 判定一个环形队列 qu(最多元素为 MaxSize )为空的条件是 C 。 A. qu-rear-qu-front= =MaxSize B. qu-rear-qu-front-l=MaxSize C. qu-front= =qu-rear D. qu-front= =qu-rear+l 33、 若用一个大小为 6 的一维数组来实现环形队列,且当前 rear 和 front 的值分 别为 0 和 3。当从队列
11、中删除一个元素,再加入两个元素后,rear 和 front 的 值分别是 B 。 A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1 34、 在一个链队中,假设 f 和 r 分别为队头和队尾指针,则删除一个结点的运算是 C。 A. r=f-next; B. r=r-next; C. f=f-next; D. f=rnext; 35、 下图所示二叉树的中序遍历序列是 B 。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 36、 深度为 5 的二叉树至多有 C 个结点。 A. 16B. 32C. 31D.1037、 对一个满二叉树,m
12、个树叶,n 个结点,深度为 h,则 D 。 A. n=h+mB. h+m=2nC. m=h-1D. n=2h-138、 下列说法正确的是 A。 A、链栈没有容量限制 B、顺序栈没有容量限制 C、链队有容量限制 D、单向链表有容量限制 39、 在一个无向图中,所有顶点的度数之和等于所有边数的 C倍。 A. 1/2B. 1C. 2D. 440、 对于一个具有 n 个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是D。A. nB. (n-1)2C. n-1D. n241、 已知一个图如下图所示,若从顶点 a 出发按深度搜索法进行遍历,则可能得到 的一种顶点序列为 D;按广度搜索法进行遍历,则可能得
13、到的一 种顶点序列为 B。A.a,b,e,c, d,fB. a,c,f,e,b,dC.a,e,b,c,f,dD. a,e,d,f,c,bA.a,b,c,e,d,fB. a,b,c,e,f,dC.a,e,b,c,f,dD. a,c,f, d,e,b42、 顺序查找法适合于存储结构为 B 的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 43、 采用折半查找法查找长度为 n 的线性表时,每个元素的平均查找长度为 D 。 A.O(n2) B.O(nlog2 n) C.O(n) D. O(log2n) 44、 对有 18 个元素的有序表作折半查找,则查找 A3 的比较序列的
14、下标为 D 。 A. 1、2、3 B.9, 5、2、3 C.9、5、3 D.9, 4、2、3 45、 有一数列 2、3、4、5,按 2、3、4、5 顺序入队,出队的顺序是 A。 A. 2345 B. 3245 C. 5342 D. 2435 46、 在排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空) 中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为 C 。 A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 47、 在下列算法中, C 算法可能出现下列情况:在最后一趟开始之前,所 有的元素都不在其最终的位置上。 A.堆排序 B.冒泡排序 C.插入排序 D.快速排
15、序 48、 在对 n 个元素进行冒泡排序的过程中,最好情况下的时间复杂度为 D 。 A. O(1) B.O (log2n) C. O(n2) D. O(n) 49、 在决定选取何种存储结构时,一般不考虑 A 。 A.各结点的值如何 B.结点个数的多少 C.对数据有哪些运算 D.所用编程语言实现这种结构是否方便 50、 通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 B 。 A.数据元素具有同一特点 B.不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致 C.每个数据元素都一样 D.数据元素所包含的数据项的个数要相等 51、 不带头结点的单链表 head 为空的判
16、定条件是 A 。 A. head= =NULL B. head-next= =NULL C. head-nexthead D. head != NULL 52、 非空的循环单链表 head 的尾结点(由 p 所指向)满足 C 。 A. p-next= =NULL B. p= =NULL C.p -next= =head D. p= =head 53、 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点,故采用 D 存储方式最节省运算时间。 A.单链表 B仅有头结点的单循环链表 C.双链表 D.仅有尾指针的单循环链表 54、 如果最常用的操作是取第 i 个结点及其前驱,则采用
17、D 存储方式最节省 时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 55、 设线性表有 n 个元素,以下算法中, A 在顺序表上实现比在链表上实 现效率更高。 A. 输出第 i (0=inext=s;f=s; B. r-next=s;r=s; C. s-next=r;r=s; D. s-next=f;f=s; 62、按照二叉树的定义,具有 3 个结点的二叉树有 C 种。 A. 3 B. 4 C. 5 D. 6 63、任何一 棵二叉树的叶子结点在先序、 中序和后序遍历序列中的相对次序 A 。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 64、一个有 n 个顶点的无向图
- 配套讲稿:
如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。