庄2008数据结构习题集new

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

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

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

3、O(n1/2)8下面程序段的时间复杂性的量级为（C）。For(inti=0;i

4、么叫算法？它有哪些特性4有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑结构图，并指出它们分别以属于何种结构。（1）A=(K,R),其中K={a,b,c,d,e,f,g,h}R={r}r={,,,,,,}(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,

5、2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}三、计算题设n为整数，求下列各程序段的时间复杂度（1）i=1;k=2;While(ij)j=j+1;Elsei=i+1;(3)x=91;y=100While(y>0)If(x>100){x=x-10;y=y-1;}elsex=x+1;44习题2一、选择题1线性表是（A）A一个有限序列，可以为空B一个有限序列，不能为空C一个无限序列，可

6、以为空D一个无限序列，不能为空2在一个长度为n的顺序表中，向第iI个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（B）个元素。An-iBn-i+1Cn-i-1Di3在一个顺序表的表尾插入一个元素的时间复度的量级为（B）。AO(n)BO(1)CO(n2)DO(logn)4表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（D），删除一个元素需要移动元素的平均个数为（A）A(n-1)/2BnC(n+1)/2Dn/25设单链表中指针p指向结点a，

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

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