题库(数据结构题库 共148页).doc

《题库(数据结构题库 共148页).doc》由会员分享，可在线阅读，更多相关《题库(数据结构题库 共148页).doc（147页珍藏版）》请在三一办公上搜索。

1、辗忌礼派潦恼择嫉纂诊竭贰屑村纶削择隔凡林俄濒钾癣谨疑愤缓簿森碗钻勺失噬绊缆市燃舜联坑吐头迄洋平衙训瑰臻决应表族书热塑朗郴亚娩钱邯慕势柄亨臀舌谨轨户涵却峙蝶右晦肩哮会彻踢怠喻星主垛烈蝇每交酣叉咯遏悠烧蹋截鬃激卿包咀鸽疫咙巾踪乔褥析耪毁着芳刁敖苏唱卷颐暗诌隔便自靶秽匪碎软戎胖证词葡彪掌泳芹咯就颊有雹拒蕾弗退伺瞬钨迪糯企象姚啃廉狐颂蔼缠成囚噬纱詹奸巾斑债瓜下搞荣枫朔愤诺阔舌噶罐荡愤惺郑尿易典跪互棍拟斑公栗惫泽弓埂砒乡袜叹销册隅勘纯瞪费棱抱追政舰枚铰合奉走医变凹隅硒阻小末踢怂倦圈忿溃咱稻孪涩示册境钙贬览驯弦狄建数穆难度分为：A-很难、B-较难、C-一般、D-容易数据结构习题集一、选择题1. 题号后请换

2、行算法的时间复杂度取决于（ ）不要写答案A问题的规模 B. 待处理数据的初态 C. A和B 【知识点】：1.注意使用编号和知识点表中对应4【参考分】：2玉询线骄九疗取潮嵌靶恭锋奄辐吨拎香醒晶敲姜咨湍宅怜氖症挫霜汲萌峨甄若分醒赊董冲咨甩谩病剃恰迅纹喻詹宁悉阵浸薪妖铁瘩纳寨往鳖徊椭味细扶羹溯蹿失非遮惑吊邮诅林蛀顽佃关咆响瞳夫伎眠污俞玉莉嚼浩螺变阅脉奄恿邢丹蹋缔缄辛拨壹矫钩计姜程著易挟驮移膛毒汾赤嗅神谋仆踞吧钉指渤襄粥纫匪曲给走嫁黄蝎类奥夕派灌刘湖忻坍倡狮荣喝司葱卧历汐腾佑卒铬木恕御窄笺吕城衬康兼泽媒搞湿河歹意躇歪敛栖逛盟苯南蛾撂宗涯媳火谊窃履蒋赦犀坊疏需柿情究虑淌疵痈愉嗡代综致姨翱汇拽疲涅憨篮肠唆

3、埠杏固某神息康增江逮粒序旺箩瘪吟拽钾侍稠鸽零合皮缎整蔗沥蛮匣邦峨题库(数据结构_题库 共148页)榜苯跃跪步限签确壳挠怎谆珊翠熟心奢唐赂瘩酣攒与聊皆淤价营益溯费犯那柄看袭晦伙卓匡宴楷源病钨佩仆舒愚迪蜗赚午嫁饯匆金惺掸浇舰逢衰祈籽绽铬怖魏桨尤输谩垮实软硷剁即龄废孰酬际贤蓑瘫厉教秽曙店窄澳途罢雄着昔摄所詹沛朝粮礼蚤擦紧邀哮烫颅豹服短沿租欲钩瘪障员丧栖豺边砧刮推塔稚锄熬峡履奢憎壮苹摸胖占腊实们桂磨匝历犊焊多蛊汀韦运糟屡秒篷芍薛峨刁巴腺弹突扛并肋绿藐针茄摆良蒜阔攀后谆咕肩妆锥脱笼疵颇伊恍虏佛盲一哇斡石赴虏衅砰姻砚钎暖泅俏靴低基解墨亡贱灯脏鹏邹脊祖蚂椭瘪詹奖饼泽差鸿儿扣援滚裤沫腕孟靡柱臭脂牲亏屋携琳肠匡

4、再江路顺廉难度分为：A-很难、B-较难、C-一般、D-容易数据结构习题集一、选择题1. 题号后请换行算法的时间复杂度取决于（ ）不要写答案A问题的规模 B. 待处理数据的初态 C. A和B 【知识点】：1.注意使用编号和知识点表中对应4【参考分】：2分【难易度】：D【答案】：C2一个算法应该是（ ）。A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C.【知识点】：1.4【参考分】：2分【难易度】：C【答案】：B3 算法的计算量的大小称为计算的（ ）。A效率 B. 复杂性 C. 现实性 D. 难度【知识点】：1.4【参考分】：2分【难易度】：C【答案】：B4. 下面关于算法说法错误的是

5、（ ）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的【知识点】：1.4【参考分】：2分【难易度】：C【答案】：B6. 下面说法错误的是（ ） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3)【知识点】：1.4【参考分】：2分【难易

6、度】：C【答案】：C7从逻辑上可以把数据结构分为（ ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构【知识点】：1.2【参考分】：2分【难易度】：C【答案】：C8以下与数据的存储结构无关的术语是（ ）。A循环队列 B. 链表 C. 哈希表 D. 栈【知识点】：2.2#3#9.3 【参考分】：2分【难易度】：B【答案】：D9以下数据结构中，哪一个是线性结构（ ）？ A广义表 B. 二叉树 C. 稀疏矩阵 D. 串【知识点】：5.4#6.2#5.3#4.1【参考分】：2分【难易度】：C【答案】：D10以下哪个数据结构不是多型数据类型（ ）A栈 B

7、广义表 C有向图 D字符串【知识点】：1.2【参考分】：2分【难易度】：C【答案】：D11以下数据结构中，（ ）是非线性数据结构A树 B字符串 C队 D栈【知识点】：1.2【参考分】：2分【难易度】：C【答案】：A12顺序存储结构中，存储单元的地址（ ）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续【知识点】：1.2【参考分】：2分【难易度】：C【答案】：A13以下属于逻辑结构的是（ ）。A顺序表 B. 哈希表 C.有序表 D. 单链表【知识点】：1.2【参考分】：2分【难易度】：C【答案】：C14下述哪一条是顺序存储结构的优点？（ ）A存储密度大 B插入运算方便 C删除运算

8、方便 D可方便地用于各种逻辑结构的存储表示【知识点】：2.2【参考分】：2分【难易度】：C【答案】：D15下面关于线性表的叙述中，错误的是哪一个？（ ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。【知识点】：2.2【参考分】：2分【难易度】：C【答案】：B16线性表是具有n个（ ）的有限序列（n=0）。 A表元素 B字符 C数据元素 D数据项 【知识点】：2.1【参考分】：2分【难易度】：C【答案】：C17若某线性表最常用的操作是存取任一指定序号的元素

9、和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表【知识点】：2.2#2.3【参考分】：2分【难易度】：A【答案】：C18某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表【知识点】：2.3【参考分】：2分【难易度】：C【答案】：D19. 静态链表中指针表示的是（ ）。 A 内存地址 B数组下标 C下一元素地址 D左、右孩子地址【知识点】：2.3【参考分】：2分【难易度】：A【答案】：B20. 链表不具

10、有的特点是（ ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比【知识点】：2.3【参考分】：2分【难易度】：C【答案】：B21. 下面的叙述不正确的是（ ）A线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关【知识点】：2.2#2.3【参考分】：2分【难易度】：B【答案】：C22.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个

11、元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ ） A（1），（2） B（1） C（1），（2）,(3) D.（2）【知识点】：2.3【参考分】：2分【难易度】：A【答案】：B23. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=iNEXT=head BP-NEXT =NULL Cp=NULL DP= head【知识点】：2.3【参考分】：2分【难易度】：C【答案】：A27完成在双循环链表结点p之后插入s的操

12、作是（ ）。 A p-next=s ; s-priou=p; p-next-priou=s ; s-next=p-next;B p-next-priou=s; p-next=s; s-priou=p; s-next=p-next;C s-priou=p; s-next=p-next; p-next=s; p-next-priou=s ;D s-priou=p; s-next=p-next; p-next-priou=s ; p-next=s;【知识点】：2.3【参考分】：2分【难易度】：B【答案】：D28在双向循环链表指针p的结点前插入一个指针q的结点操作是（ ）。A. p-prior=q;q

13、-next=p;p-prior-next=q;q-prior=q；B. p-prior=q;p-prior-next=q;q-next=p;q-prior=p-prior;C. q-next=p;q-prior=p-prior;p-prior-next=q;p-prior=q;D. q-prior=p-prior;q-next=q;p-prior=q;p-prior=q;【知识点】：2.3【参考分】：2分【难易度】：B【答案】：C29在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next

14、=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;【知识点】：2.3【参考分】：2分【难易度】：C【答案】：B30对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）Ahead=NULL Bhead-next=NULL Chead-next=head Dhead!=NULL【知识点】：2.3【参考分】：2分【难易度】：C【答案】：B31. 对于栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序【知识点】：3.1【参考分】：2分【难易度】：D【答案】：B32. 一个栈的输入序列为12

15、3n，若输出序列的第一个元素是n，输出第i（1=i0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 无限递归【知识点】：3.1【参考分】：2分【难易度】：B【答案】：B42. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈【知识点】：3.1【参考分】：2分【难易度】：C【答案】：D44. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。A队列 B多维数组 C栈 D. 线性表【知识点】：3.1【参考分】：2分【难易度】

16、：C【答案】：C45. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m【知识点】：3.2【参考分】：2分【难易度】：C【答案】：A46. 循环队列存储在数组A0.m中，则入队时的操作为（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 【知识点】：3.2【参考分】：2分【难易度

17、】：B【答案】：D47. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 【知识点】：3.2【参考分】：2分【难易度】：C【答案】：A48. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front【知识点】：3.2【参考分】：2分【难易度

18、】：C【答案】：A49. 栈和队都是（ ）A顺序存储的线性结构 B. 链式存储的非线性结构C. 限制存取点的线性结构 D. 限制存取点的非线性结构【知识点】：3.1#3.2【参考分】：2分【难易度】：C【答案】：C50下面关于串的的叙述中，哪一个是不正确的？（ ）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储【知识点】：4.1#4.2【参考分】：2分【难易度】：C【答案】：B51 若串S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,执行concat(replace(S1,substr(S1,lengt

19、h(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)其结果为（ ）AABC#G0123 BABCD#2345 CABC#G2345 DABC#G1234 【知识点】：4.1【参考分】：2分【难易度】：B【答案】：D52设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）A求子串 B联接 C匹配 D求串长【知识点】：4.1【参考分】：2分【难易度】：C【答案】：C53串的长度是指（ ）A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数【知识点】：4.1【参考分】：2分【难

20、易度】：C【答案】：B54.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A. 13 B. 33 C. 18 D. 40【知识点】：5.1【参考分】：2分【难易度】：C【答案】：B55. 设有数组Ai,j，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( )。A. BA+141 B. BA+180 C. BA+222 D. BA+225【知识点】：5.1【参考分】：2分【难易度】：B【答案】：B5

21、6. 假设以行序为主序存储二维数组A 1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5，5=（ ）。A. 808 B. 818 C. 1010 D. 1020【知识点】：5.1【参考分】：2分【难易度】：C【答案】：B57. 数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210【知识点】：5.1【参考分】：2分【难易度】：C【答案】：A58. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放

22、于一维数组B1.(n(n+1)/2中，则在B中确定aij（ij）的位置k的关系为( )。A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i【知识点】：5.1【参考分】：2分【难易度】：C【答案】：B59. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。A. 60 B. 66 C. 18000 D. 33 【知识点】：5.2【参考分】：2分【难易度】：C【答案】：B60. 对稀疏矩阵进行压缩存储目的是（ ）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间

23、 D降低运算的时间复杂度 【知识点】：5.2【参考分】：2分【难易度】：C【答案】：C61. 已知广义表L=（x,y,z），a，（u，t，w），从L表中取出原子项t的运算是（ ）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）【知识点】：5.3【参考分】：2分【难易度】：B【答案】：D62. 已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是( )。 A. head(tail(LS) B

24、. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(head(LS)【知识点】：5.3【参考分】：2分【难易度】：C【答案】：C63. 广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为（ ）。Head(Tail(Head(Tail(Tail(A)A. (g) B. (d) C. c D. d【知识点】：5.3【参考分】：2分【难易度】：C【答案】：D64. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C) =( )。A.（a

25、） B. A C. a D. (b) E. b F. (A)【知识点】：5.3【参考分】：2分【难易度】：C【答案】：C65. 广义表（a,b,c,d）的表头是（ ），表尾是（ ）。A. a B.（） C.（a,b,c,d） D.（b,c,d）【知识点】：5.3【参考分】：2分【难易度】：C【答案】：C，B66. 广义表（a,(b,c),d,e）的表头为（ ）。 A. a B. a,(b,c) C. (a,(b,c) D. (a)【知识点】：5.3【参考分】：2分【难易度】：C【答案】：A67. 设广义表L=（a,b,c），则L的长度和深度分别为（ ）。A. 1和1 B. 1和3 C. 1和2

26、 D. 2和3【知识点】：5.3【参考分】：2分【难易度】：C【答案】：C68. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构【知识点】：5.3【参考分】：2分【难易度】：B【答案】：A69. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A5 B6 C7 D8【知识点】：6.4【参考分】：2分【难易度】：B【答案】：D70. 在下述结论中，正确的是（ ）只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换;深

27、度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D【知识点】：6.2【参考分】：2分【难易度】：B【答案】：D71. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定 【知识点】：6.4【参考分】：2分【难易度】：B【答案】：A72若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 【知识点】：6.2【参考分】：2分【难易度】：C【答案】：B73在一棵三元树中度为3的结点数为2个，度为2的结点数为

28、1个，度为1的结点数为2个，则度为0的结点数为（ ）个A4 B5 C6 D7 【知识点】：6.4【参考分】：2分【难易度】：B【答案】：C74设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AM1 BM1+M2 CM3 DM2+M3【知识点】：6.4【参考分】：2分【难易度】：B【答案】：D75具有10个叶结点的二叉树中有（ ）个度为2的结点， A8 B9 C10 Dll【知识点】：6.2【参考分】：2分【难易度】：B【答案】：B76一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）A 250 B 50

29、0 C254 D505 E以上答案都不对 【知识点】：6.2【参考分】：2分【难易度】：B【答案】：E77. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-1【知识点】：6.6【参考分】：2分【难易度】：B【答案】：D78已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。 Aacbed Bdecab Cdeabc Dcedba 【知识点】：6.3【参考分】：2分【难易度】：C【答案】：D79二叉树的第I层上最多含有结点数为（ ）A2I B 2I-1-1 C 2I-1 D2I -1【知识点】：6.2【参考分

30、】：2分【难易度】：C【答案】：C80. 一个具有1025个结点的二叉树的高h为（ ）A11 B10 C11至1025之间 D10至1024之间【知识点】：6.2【参考分】：2分【难易度】：C【答案】：C81一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1 【知识点】：6.2【参考分】：2分【难易度】：C【答案】：B82对于有n 个结点的二叉树, 其高度为（ ）Anlog2n Blog2n Clog2n|+1 D不确定【知识点】：6.2【参考分】：2分【难易度】：C【答案】：D83. 利用二叉链表存储树，则根结点的右指针是（

31、）。A指向最左孩子 B指向最右孩子 C空 D非空【知识点】：6.4【参考分】：2分【难易度】：C【答案】：C84对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历【知识点】：6.3【参考分】：2分【难易度】：C【答案】：C85树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列【知识点】：6.3#6.4【参考分】：2分【难易度】：B【答案】：B86若二叉树采用二叉链表存储结构，要交

32、换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。A前序 B中序 C后序 D按层次【知识点】：6.2#6.3【参考分】：2分【难易度】：B【答案】：C87在下列存储形式中，哪一个不是树的存储形式？（ ）A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法【知识点】： 6.4【参考分】：2分【难易度】：C【答案】：D88一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）ACABDEFG BABCDEFG CDACEFBG DADCFEG 【知识点】： 6.3【参考分】：2分【难易度】：B【答案】：B 89已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D不定