数据结构习题集new

《数据结构习题集new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构习题册（仅供计算机和信息专业同学参考）基础篇习题1一、选择题1计算机算法必须具备输入、输出、（）等5个特性。A可行性、可移植性和可扩展性B可行性、确定性和有穷性C确定性、有穷性和稳定性D易读性、安全性和稳定性2在数据结构中，从逻辑上可以把数据结构分为（）A动态结构和静态结构B紧凑结构和非紧凑结构C内容结构和外部结构D线性结构和非线性结构3下面程序段的时间复杂性的量级为（）For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)x=x+1;AO(1)BO(n)CO(n2)DO(n3)4在数据结构中，与所使用的计算机无关的是数据的（）结构A

2、逻辑B存储C逻辑和存储D物理5数据结构在计算机中的表示是指（）A数据的逻辑结构B数据结构C数据的存储结构D数据元素之间的关系446下面（）的时间复杂性最好，即执行时间最短。AO(n)BO(logn)CO(nlogn)DO(n2)7下面程序段的时间复杂性的量级为（）。Intfun(intn){I=1,s=1;While(s

3、(m+n)9执行下面程序段时，S语句的执行次数为（）。For(inti=1;i,,,,,,

4、,h>}(2)B=(K,R),其中K＝{a,b,c,d,e,f,g,h}R={r}r={,,,,,,}(3)B=(K,R),其中K={1,2,3,4,5,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}44三、计算题设n为整数，求下列各程序段的时间复杂度（1）i=1;k=2;While(ij)j=j+1;Elsei=i+1;(3)x=91;y=100Whil

5、e(y>0)If(x>100){x=x-10;y=y-1;}elsex=x+1;习题2一、选择题1线性表是（）A一个有限序列，可以为空B一个有限序列，不能为空C一个无限序列，可以为空D一个无限序列，不能为空2在一个长度为n的顺序表中，向第iI个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（）个元素。An-iBn-i+1Cn-i-1Di3在一个顺序表的表尾插入一个元素的时间复度的量级为（）。AO(n)BO(1)CO(n2)DO(logn)4表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（），删除一个元素需要移

6、动元素的平均个数为（）A(n-1)/2BnC(n+1)/2Dn/25设单链表中指针p指向结点a，若要删除p之后的结点（若存在），则需修改指针的操作为（）。Ap->next=p->next->nextBp=p->nextCp=p->next->nextDnext=p6单链表的存储密度为（）。A大于1B等于5C小于1D不能确定447在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。A1B2C3D48在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂度的量级为（）。AO(n)BO(n/2)CO(1)DO(n1/2)9在一个带头结点的双

7、向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。A2B3C4D6二、简答题1什么叫线性表？它有哪些特点？2在链表的设计中，为什么通常采用带头结点的链表结构？3对比顺序表与单链表，说明顺序表与单链表的主要优点和主要缺点。4试编写算法实现顺序表的逆置，即把顺序表A中的数据元素（a1,a2,…,an）逆置为（an,an-1,…,a1）。5已知A和B为两个非递减的线性表，现要求实现如下操作：