数据结构习题1

数据结构习题册（仅供计算机和信息专业同学参考）计算机科学技术教研室二ＯＯ八年十一月基础篇习题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++)x=x+1;A O(1)B O(n)C O(n2)D O(n3)4 在数据结构中，与所使用的计算机无关的是数据的（A ）结构A 逻辑B 存储C 逻辑和存储D 物理5 数据结构在计算机中的表示是指（C ）A 数据的逻辑结构B 数据结构C 数据的存储结构D 数据元素之间的关系6 下面（B ）的时间复杂性最好，即执行时间最短。

A O(n)B O(logn)C O(nlogn)D O(n2)7 下面程序段的时间复杂性的量级为（D ）。

Int fun(int n){I=1,s=1;While(s<n)s+=++I;return I;}A O(n/2)B O(logn)C O(n)D O(n1/2)8 下面程序段的时间复杂性的量级为（C）。

For(int i=0;i<m;i++)For(int j=0;j<n;j++)A[i][j]=i*j;A O(m3)B O(n2)C O(m*n)D O(m+n)9 执行下面程序段时，S 语句的执行次数为（A）。

For(int i=1;i<n-1;i++)For(int j=i+1;j<=n;j++)S;A n(n-1)/2B n2/2C n(n-1)/2D n二、简答题1 数据的逻辑结构有哪几种？常用的存储有哪几种？集合线性结构树形结构图状结构顺序存储结构链式存储结构2 举一个数据结构的例子，叙述其逻辑结构、存储结构和运算三方面的内容。

3 什么叫算法？它有哪些特性4 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑结构图，并指出它们分别以属于何种结构。

（1）A=(K,R),其中K={a,b,c,d,e,f,g,h}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}(2) B=(K,R),其中K＝{a,b,c,d,e,f,g,h}R={r}r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}(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)}三、计算题设n为整数，求下列各程序段的时间复杂度（1）i=1;k=2;While(i<n){k=k+10*I;i=i+1;}(2)i=1;j=0;While(i+j<=n)If(i>j)j=j+1;Else i=i+1;(3)x=91;y=100While(y>0)If(x>100){x=x-10;y=y-1;}else x=x+1;习题1参考答案一、选择题1. B2. D3. D4. A5. C6. B7. D8. C9. A二、简答题1. 答：数据的逻辑结构通常有四种，即集合、线性结构、树形结构和图状结构。

存储结构主要有顺序存储结构和链式存储结构。

2. 答：比如一分通讯录，记录了相关人员的电话号码，将其按姓名一人占一行构成表，这个表就是一个数据结构。

每一行是一个记录，对于整个表来说，只有一个开始结点和一个终端结点，其它结点也只有一个前驱和一个后继。

这几个关系就确定了表的逻辑结构。

3. 答：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。

算法具有有穷性、确定性、可行性、输入和输出5个特性。

4.答：(1) A 对应的逻辑图形如下图左，它是一种线性结构。

(2) B 对应的逻辑图形如上图右所示，它是一种树型结构。

(3) C 对应的逻辑图形如下图所示，它是一种图型结构。

三、计算题解： (1) O(n) ； (2) O(n) ； (3) O(n 1/2)。

习题2一、选择题 1 线性表是（A ）A 一个有限序列，可以为空B 一个有限序列，不能为空C 一个无限序列，可以为空D 一个无限序列，不能为空1 2 3 4 6 52 在一个长度为n的顺序表中，向第iI个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（B）个元素。

A n-iB n-i+1C n-i-1D i3 在一个顺序表的表尾插入一个元素的时间复度的量级为（B）。

A O(n)B O(1)C O(n2)D O(log n)4 表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（C），删除一个元素需要移动元素的平均个数为（D）A (n-1)/2 B n C (n+1)/2 D n/25 设单链表中指针p指向结点a，若要删除p之后的结点（若存在），则需修改指针的操作为（A）。

A p->next=p->next->nextB p=p->nextC p=p->next->nextD next=p6 单链表的存储密度为（C）。

A 大于1B 等于5C 小于1D 不能确定7 在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（B）个指针域的值。

A 1B 2C 3D 48 在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂度的量级为（A）。

A O(n)B O(n/2)C O(1)D O(n1/2)9 在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（C）个指针域的值。

A 2B 3C 4D 6二、简答题1 什么叫线性表？它有哪些特点？2 在链表的设计中，为什么通常采用带头结点的链表结构？3 对比顺序表与单链表，说明顺序表与单链表的主要优点和主要缺点。

4 试编写算法实现顺序表的逆置，即把顺序表A中的数据元素（a1,a2, …,a n）逆置为（a n,a n-1, …,a1）。

5 已知A和B为两个非递减的线性表，现要求实现如下操作：从A中删除在B中出现的元素。

试编写在顺序表中实现上述操作的算法。

6 试编写算法实现链表的就地逆置(不增加存储空间)，即把链表A中的数据元素（a1,a2, …,a n）逆置为（a n,a n-1, …,a1）。

7 假设有两个非递减的线性表A 和B，均采用链式存储结构，试编写算法将A和B 归并成一个按元素非递减的线性表C。

8 试编写算法求单循环链表的表长。

1. A2. B3. B4. D A5. A6. C7. B8. A9. C二、简答题1. 答：线性表是具有n个数据元素的一个有限序列。

线性表的特点是：数据元素之间是一对一的关系。

除第一个元素外，每个元素有且只有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继。

2. 答：头指针是链表的一个标识，它用来指向带头结点的链表中的头结点。

头结点是在链表的第一个数据元素之前附加的一个结点，它的作用是使对第一个结点的操作和其它结点一致，表空与非空时处理一致，不需要特殊处理，简化了操作。

3. 答：顺序表的特点是逻辑位置相邻的数据元素其物理位置也相邻，因此可以进行随机存储，是一种随机存储结构。

其插入和删除操作的时间复杂度均为O(n)。

链表中的数据元素使用一组任意的存储单元存储，不要求逻辑位置相邻的数据元素物理位置也相邻，而是采用附加的指针表示元素之间的逻辑关系。

链表的插入和删除结点均不需要移动其他结点，但是，其查找运算必须从头指针开始顺序查找，其时间复杂度为O(n)。

4.答：算法如下void Convert(SqList &L){int i,j,temp;j=L.length-1;i=0;while(i<j){temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;i++;j--;}}5.答：算法如下void Delete(SqList &La,SqList Lb){int i,j,k;i=0;j=0;while(i<La.length&&j<Lb.length){if(La.elem[i]<Lb.elem[j]) i++;else if(La.elem[i]>Lb.elem[j]) j++;else ListDelete_Sq(La, i+1, k);}}6.答：算法如下void InvertList(LinkList &L){LinkList p,q,r;p = L->next;q = p->next;p->next=NULL;while(q!=NULL){r=q->next;q->next=p;p=q;q=r;}L->next=p;}7. 答：算法如下void MergeOrder(LinkList La,LinkList Lb){LinkList pa,pb,Lc,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while (pa&&pb){if(pa->data <=pb->data ){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}if (!pa) pc->next=pb;else pc->next=pa;}8. 答：算法如下int Length(LinkList L){int i=0;LinkList p;p=L->next;while(p){p=p->next;i++;}return i;}习题3一、选择题1在栈顶一端可进行的全部操作是（）。

A 插入B 删除C插入和删除D进栈2 栈的特点是（）。

A 先进先出B 后进先出C后进后出D不进不出3 顺序栈是空栈的条件是（）。

A top==0B top==1C top==-1D top==m4 假定利用数组A[N]顺序存储一个栈，top表示栈顶指针，已知栈未满，则x入栈时所执行的操作是（）。