数据结构习题集(含答案)

内容发布更新时间 : 2024/12/26 4:21:14星期一 下面是文章的全部内容请认真阅读。

安徽科技学院

数 据 结 构 习 题 册

(仅供网络工程、计算机和信息专业同学参考)

计 算 机 科 学 技 术 教 研 室

二OO八年十一月

1

1. B 2. D 3. D 4. A 5. C 6. B 7. D 8. C 9. A

一、选择题

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 逻辑 B 存储 C 逻辑和存储 D 物理

5 数据结构在计算机中的表示是指()

A 数据的逻辑结构 B 数据结构 C 数据的存储结构 D 数据元素之间的关系

6 下面(B)的时间复杂性最好,即执行时间最短。 A O(n) B O(logn) C O(nlogn) D O(n2)

7 下面程序段的时间复杂性的量级为( C)。 Int fun(int n){ I=1,s=1; While(s

s+=++I; return I; }

1

A O(n/2) B O(logn) C O(n) D O(n1/2)

8 下面程序段的时间复杂性的量级为( C)。 For(int i=0;i

For(int j=0;j

A[i][j]=i*j;

A O(m) B O(n) C O(m*n) D O(m+n)

9 执行下面程序段时,S 语句的执行次数为(C )。 For(int i=1;i

For(int j=i+1;j<=n;j++)

S;

A n(n-1)/2 B n/2 C n(n-1)/2 D n

2

3

2

二、简答题

1 数据的逻辑结构有哪几种?常用的存储有哪几种?

2 举一个数据结构的例子,叙述其逻辑结构、存储结构和运算三方面的内容。 3 什么叫算法?它有哪些特性

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,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}

三、计算题

设n为整数,求下列各程序段的时间复杂度 (1)i=1;k=2;

While(i

(2)i=1;j=0;

While(i+j<=n) If(i>j)j=j+1;

2

Else i=i+1;

(3)x=91;y=100 While(y>0) If(x>100){ x=x-10; y=y-1; }else x=x+1;

一、选择题

题2

1. A 2. B 3. B 4. D A5. A 6. C 7. B 8. A 9. C

1 线性表是( A)

A 一个有限序列,可以为空 B 一个有限序列,不能为空 C 一个无限序列,可以为空 D 一个无限序列,不能为空

2 在一个长度为n的顺序表中,向第iI个元素(1≤i≤n+1)位置插入一个新元素时,需要从后向前依次后移( B)个元素。

A n-i B n-i+1 C n-i-1 D i

3 在一个顺序表的表尾插入一个元素的时间复度的量级为( A)。

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/2

5 设单链表中指针p指向结点a,若要删除p之后的结点(若存在),则需修改指针的操作为(A )。 A p->next=p->next->next B p=p->next C p=p->next->next D next=p

6 单链表的存储密度为(D )。

A 大于1 B 等于5 C 小于1 D 不能确定

7 在一个单链表中,若要在p所指向的结点之后插入一个新结点,则需要相继修改( B)个指针域的值。

A 1 B 2 C 3 D 4

8 在一个单链表中,若要在p所指向的结点之前插入一个新结点,则此算法的时间复杂度的量级为(C )。

3

A O(n) B O(n/2) C O(1) D O(n1/2)

9 在一个带头结点的双向循环链表中,若要在p所指向的结点之前插入一个新结点,则需要相继修改(C )个指针域的值。

A 2 B 3 C 4 D 6

二、简答题

1 什么叫线性表?它有哪些特点?

2 在链表的设计中,为什么通常采用带头结点的链表结构?

3 对比顺序表与单链表,说明顺序表与单链表的主要优点和主要缺点。

4 试编写算法实现顺序表的逆置,即把顺序表A中的数据元素(a1,a2, ?,an)逆置为(an,an-1, ?,a1)。

5 已知A和B为两个非递减的线性表,现要求实现如下操作:从A中删除在B中出现的元素。试编写在顺序表中实现上述操作的算法。

6 试编写算法实现链表的就地逆置(不增加存储空间),即把链表A中的数据元素(a1,a2, ?,an)逆置为(an,an-1, ?,a1)。 7 假设有两个非递减的线性表A 和B,均采用链式存储结构,试编写算法将A和B 归并成一个按元素非递减的线性表C。 8 试编写算法求单循环链表的表长。

一、选择题

题3

1. C 2. B 3. A 4. D 5. B 6. C7. C 8. A 9. B 10. B

1在栈顶一端可进行的全部操作是(C )。

A 插入 B 删除 C插入和删除 D进栈

2 栈的特点是( B)。

A 先进先出 B 后进先出 C后进后出 D不进不出

//3 顺序栈是空栈的条件是(C )。

A top==0 B top==1 C top==-1 D top==m

4 假定利用数组A[N]顺序存储一个栈,top表示栈顶指针,已知栈未满,则x入栈时所执行的操作是( D)。

A a[--top]=x; B a[top--]=x C a[++top]=x D a[top++]=x

5 一个栈的入栈序列是a,b,c,d,e,则不可能的出栈序列是( B)。 A edcda B dceab C decba D abcde

4

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi