安徽科技学院
数 据 结 构 习 题 册
（仅供网络工程、计算机和信息专业同学参考）
计 算 机 科 学 技 术 教 研 室
二ＯＯ八年十一月
基
习
础
题
篇
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={ K＝{a,b,c,d,e,f,g,h} R={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