数据结构与算法复习题(含答案).doc
《数据结构与算法复习题(含答案).doc》由会员分享,可在线阅读,更多相关《数据结构与算法复习题(含答案).doc(14页珍藏版)》请在咨信网上搜索。
1、数据结构与算法2015-2016学年第1学期考试复习题一、 选择题(下面各小题有一个正确答案,请将正确答案的编号填写在各小题的括号内)。1、在一棵具有5层的满二叉树中结点总数为( A )。A) 31 B)32C)33 D)162、串的逻辑结构与( D )的逻辑结构不相同。A)线性表 B)栈C)队列 D)集合3、下列序列中,执行第一趟快速排序后得到的序列是( A )。A)d,a,e,d,bfh,g B) c,e,a,dfh,g,bC) g,a,e,c,bfd,h D) a,b,c,d,fe,g,h4、n个顶点的强连通图至少有( A )条边。A)n B)n+1 C)n-1 D)n(n-1)5、数据
2、结构中,在逻辑上可以把数据结构分成( B )。A)动态结构和静态结构B)线性结构和非线性结构C)紧凑结构和非紧凑结构D)内部结构和外部结构6、链式存储的存储结构所占存储空间( A )。A)分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针B)只有一部分,存放结点值C)只有一部分,存储表示结点间关系的指针D)分两部分,一部分存放结点值,另一部分存放结点所占单元数7、有一个有序表1,4,6,10,18,35,42,53,67,71,78,84,92,99。当用二分查找法查找键值为84的结点时,经( B )比较后查找成功。A) 4B)3C)2D)128、设单链表中指针p指向结点m,若要删除
3、m之后的结点(若存在),则需修改指针的操作为( A )。A)p-next=p-next-next; B) p=p-next;C)p=p-next-next; D) p-next=p;9、n个顶点,e条边的有向图的邻接矩阵中非零元素有( C )个。A)nB)2eC)e D) n+e10、对下图V4的度为( C )。A)1 B)2 C)3 D)4 v1 v2 v3 v411、在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为( C )。A)4 B)5C)6 D)712、在数据结构中,从逻辑上可以把数据结构分为( C )。 A)动态结构和静态结构 B)紧凑结构和非紧
4、凑结构 C)线性结构和非线性结构 D)内部结构和外部结构 13、用一维数组A进行顺序存储时,若起始地址为loc(A1),元素长度为c,则A的第i个数组单元在存放地址loc(Ai),等于( B )。A)loc(A1)+i*c B)loc(A1)+(i-1)*cC)loc(A1)+i*c+1 D)loc(A1)+(i+1)*c14、( C )在进行插入操作时,常产生假溢出现象。A)顺序栈 B)循环队列C)顺序队列 D)链队列15、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( D )存储方式最节省运算时间。 A) 单链表 B) 仅有头指针的单循环链表 C) 双链表
5、 D) 仅有尾指针的单循环链表16、向一个栈顶指针为hs的链栈中插入一个s结点时,应执行( D )。 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;17、在一个链队列中,假定front和rear分别为队首和队尾指针,则删除一个结点的操作为( B )。 A) rear=rear-next;B) front=front-next; C) rear=front-next;D) front=rear-next;18、已知栈的最大容量为4。若进栈序列为1,2,3,4,5,6,
6、且进栈和出栈可以穿插进行,则可能出现的出栈序列为( C )。 A) 5,4,3,2,1,6B) 2,3,5,6,1,4 C) 3,2,5,4,1,6D) 1,4,6,5,2,319、已知广义表L=(x,y,z),a,(u,t,w),从L 表中取出原子项t 的操作是( D )。 A) Head(Head(Tail(Tail(L) B) Tail(Head(Head(Tail(L) C) Head(Tail(Head(Tail(L) D)Head(Tail(Head(Tail(Tail(L)20、下列各种数据结构中属于线性结构的有( A )。 A)栈 B) 二叉树 C) 广义表 D) 图21、倘若
7、在对串的插入、删除运算中,期望运算速度最快,则应采用( C )。 A)顺序表示法 B)单字符为结点的单链表表示法 C)等量分块表示法 D)不等量分块表示法22、广义表head(a,b),(c,d)的运算结果为( A )。 A)(a,b) B)(c,d) C)空表 D)(a,b),(c,d))23、 n个顶点的图的最小生成树必定( D ),是不正确的描述。 A)不唯一 B)权的总和唯一 C)不含回路 D)有n条边24、采用链结构存储线性表时,其地址( B )。 A)必须是连续的 B)连续不连续都可以 C)部分地址必须是连续 D)必须是不连续的25、队列的操作的原则是( A )。 A)先进先出 B
8、) 后进先出 C) 只能进行插入 D) 只能进行删除26、以下属于顺序存储结构优点的是( A )。 A) 存储密度大B) 插入运算方便 C)删除运算方便D)可方便地用于各种逻辑结构的存储表示27、数据结构研究的内容是( D )。 A)数据的逻辑结构 B)数据的存储结构 C)建立在相应逻辑结构和存储结构上的算法 D)包括以上三个方面28、在一个单链表中,已知q结点是p结点的前趋结点,若在q和p之间插入s结点,则须执行( A )。 A)q-next=s;s-next=p;B)s-next=p-next;p-next=s; C)p-next=s-next;s-next=pD)p-next=s;s-n
9、ext=q;29、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( D )存储方式最节省时间。 A)顺序表B)双链表C)带头结点的双循环链表D)单循环链表30、下面关于线性表的叙述中,错误的是哪一个?( D ) A)线性表采用顺序存储,必须占用一片连续的存储单元。 B)线性表采用链接存储,便于插入和删除操作。 C)线性表采用链接存储,不必占用一片连续的存储单元。 D)线性表采用顺序存储,便于进行插入和删除操作。31、在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为( C )。 A)top不变
10、B)top=0C)top- D)top+32、在一个链队列中,假定front和rear分别为队首和队尾指针,则插入一个结点的操作为( B )。A)front=front-next;B) rear=rear-next;C) rear=front-next; D) front=rear-next;33、设有一个栈,元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列是( C )。 A) A,B,C,D,E B) B,C,D,E,A C) E,A,B,C,D D) E,D,C,B,A34、广义表A=(A,B,(C,D),(E,(F,G)),则head(tail(head(tail(tail(A
11、)=( D )。 A) (G) B) (D) C) C D) D35、设给定问题的规模为变量n,解决该问题的算法所需时间为Tn=O(f(n),Tn表示式中记号O表示( A )。A)一个数量级别 B)一个平均值C)一个最大值 D)一个均方值36、线性表的链接实现有利于( A )运算。A)插入 B)读元素C)查找 D)定位37、串的逻辑结构与( D )的逻辑结构不同。A)线性表 B)栈C)队列 D)树38、下面程序段的时间复杂度是( A )。 s =0; for( i =0; in; i+) for(j=0;jnext=p-next-next B)p=p-nextC)p=p-nexe-next D
12、)p-next=p41、设一数列的顺序为1,2,3,4,5,6,通过栈结构不可能排成的顺序数列为( B )。A)3,2,5,6,4,1 B)1,5,4,6,2,3C)2,4,3,5,1,6 D)4,5,3,6,2,142、若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点的个数是( B )。 A)9 B)11 C)15 D)不能确定43、对待排序的元素序列进行划分,将其分为左、右两个子序列,再对两个子序列施加同样的排序操作,直到子序列为空或只剩一个元素为止。这样的排序方法是( A )。A)直接选择排序 B)直接插入排序 C)快速排序 D)起泡排序44、设有一个10阶的对称矩阵
13、A,采用压缩存储方式,以行序为主存储,a11为第一个元素,其存储地址为1,每元素占1个地址空间,则a85的地址为( B )。A)13 B)33 C)18 D)4045、如果结点A有3个兄弟,而且B为A的双亲,则B的度为( B )。A)3 B)4 C)5 D)146、线索二叉树中某结点D,没有左孩子的条件是( B )。A)D-Lchild=Null B) D-ltag=1C) D-Rchild=Null D) D-ltag=047、栈进行插入和删除操作的特点是( A )。A)LIFO B)FIFOC)FCFS D)HPF48、与无向图相关的术语有( C )。A)强连通图 B)入度C)路径 D)弧
14、49、 n个顶点的图的最小生成树必定( D ),是不正确的描述。A)不唯一 B)权的总和唯一C)不含回路 D)有n条边50、若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个( D )。A)上三角矩阵 B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵51、采用链结构存储线性表时,其地址( B )。A)必须是连续的 B)连续不连续都可以C)部分地址必须是连续 D)必须是不连续的52、倘若在对串的插入、删除运算中,期望运算速度最快,则应采用( B )。A)顺序表示法 B)单字符为结点的单链表表示法C)等量分块表示法 D)不等量分块表示法53、在循环队列中,若front与rear 分别表示对头
15、元素和队尾元素的位置,则判断循环队列空的条件是( C )。 A)front=rear+1 B)rear=front+1 C)front=rear D)front=0 二、判断题(对的打,错的打 )1、算法和程序都应具有下面一些特征:有输入,有输出,确定性,有穷性,有效性。( 1 )2、顺序表和一维数组一样,都可以按下标随机(或直接)访问。( 1 )3、线性表的链式存储结构优于顺序存储。( 0 )4、对稀疏矩阵进行压缩存储是为了节省存储空间。( 1 )5、数据的逻辑结构反映了数据在计算机中的存储方式。( 1 )6、从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较
16、 (n+1)/2个元素结点。( 1 )7、在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针,则判断队满的条件为:(rear+l)n=front。( 1 )8、选择好的哈希函数就可以完全避免冲突的发生。( 0 )9、栈和队列都是顺序存取的线性表,它们对存取位置的限制是一样的。( 0 )10、在铁路的列车调度中,假设两侧铁道均为单向行驶道,如果进站的列车序列为123456,则一定能得到435612和135426的出站序列。( 0 )11、广义表是由零个或多个原子或子表所组成的有限序列,所以广义表可能为空表。( 0 )12、数组是一种复杂的数据结构,数组元素之间
17、的关系,即不是线性的也不是树形的。( 0 )13、用邻接表存储图所用的空间大小与图的顶点数和边数都有关。( 0 )14、设散列表长度为m,散列函数为H(key)=key% p,为了减少发生冲突的可能性,p应取小于m的最大奇数。( 1 )15、在排序前,关键字值相等的不同记录间的前后相对位置保持不变的排序方法称为稳定的排序方法。( 1 )16、引入线索二叉树的目的是为了能在二叉树中方便的进行插入与删除。( 0 )17、算法分析的主要任务是研究数据之间的逻辑关系。( 0 )18、在一个长度为n的顺序表中删除第i个元素(0in)时,需向前移动n-i个元素。( 0 )19、在具有n个单元的顺序存储的循
18、环队列中,假定front和rear分别为队头指针和队尾指针,则判断队空的条件为:rear=front。( 0 )20、在铁路的列车调度中,假设两侧铁道均为单向行驶道,如果进站的列车序列为123456,则只能得到654321的出站序列。( 0 )21、在一棵二叉树中,假定每个结点只有左孩子,没有右孩子,对它分别进行前序遍历和中根遍历,则具有相同的结果。( 0 )22、广义表(a,b),a,b)的表头和表尾是相等的。( 0 )23、线性表可以看成是广义表的特例,如果广义表中的每个元素是原子,则广义表便成为线性表。( 1 )24、插入和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也会
19、经常使用。( 0 )25、线索二叉树是一种物理结构。( 1 )26、一个带权无向连通图的最小生成树有一棵或多棵。( 1 )27、对线性表进行二分查找时,要求线性表必键值有序的链接表。( 1 )29、树中所有结点的度等于所有结点数加1。( 0 )30、图的深度优先搜索是一种典型的回溯搜索的例子,可以通过递归算法求解。( 1 )三、填空题。1、在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为: p-next-next 。2、有向图的边称为 弧 ,边的始点称为 弧尾 ,边的终点称为 弧头 。有向图顶点的度为 出度 和 入度 之和。3、若一个算法中的语句频度
- 配套讲稿:
如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。