《数据结构》综合练习一.doc
《《数据结构》综合练习一.doc》由会员分享，可在线阅读，更多相关《《数据结构》综合练习一.doc（6页珍藏版）》请在冰点文库上搜索。
综合练习一
一.单选题
1.数据的逻辑结构可以分为_______C_____。
A）静态结构和动态结构
B）物理结构和存储结构
C）线性结构和非线性结构
D）虚拟结构和抽象结构
2.顺序存储方式的优点是_______A_____。
A）存储密度大
B）插入、删除运算方便
C）可进行动态存储分配
D）可方便地用于各种逻辑结构的存储表示
3.下面关于线性表的叙述中，错误的是____B_____。
A）线性表采用顺序存储，必须占用一片连续的存储单元
B）线性表采用顺序存储，便于进行插入和删除操作
C）线性表采用链接存储，不必占用一片连续的存储单元
D）线性表采用链接存储，可以动态分配存储空间
4.用数组存储线性表的优点是____B_________。
A）便于插入和删除操作
B）便于随机存取
C）可以方便地改变表的长度
D）不需要占用一片连续的存储空间
5.线性表中各元素之间呈____C______关系。
A）层次
B）网状
C）有序
D）集合
6.一维数组和线性表的区别是_____A_____。
A）前者长度固定，后者长度可变
B）后者长度固定，前者长度可变
C）两者长度均固定
D）两者长度均可变
7.单链表L中，P所指结点为尾结点的条件为____B____。
A）P＝L
B）P->next=NULL
C）P↑.next:
＝L
D）P＝nil
8.与数据元素本身的形式、内容、相对位置及个数无关的
是数据的_____C___。
A）存储结构
B）存储实现
C）逻辑结构
D）运算实现
9.单链表中，增加头结点的目的是____C____。
A）使单链表至少有一个结点
B）表示单链表中首结点的位置
C）方便运算的实现
D）说明单链表是线性表的链式存储结构
10.数据结构是一门研究非数值计算的程序设计问题中计
算机的__A__以及它们之间的关系和运算等的学科。
A）操作对象
B）计算方法
C）逻辑存储
D）数据映像
11.算法分析的目的是_B___。
A）找出数据结构的合理性
B）分析算法的效率以求改进
C）研究算法中的输入和输出的关系
D）分析算法的易懂性和文档性
12.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一
个元素，元素的移动次数为__A__。
A）n-i+1
B）n-i
C）i
D）i-1
13.不带头结点的单链表head为空的判断条件为__A__。
A）head==Null
B）head->next==Null
C）head->next==head
D）head!
=Null
14.数据结构被形式地定义为（D，S），其中D是数据元素的有
限集合，S是D上___B______的有限结合。
A）操作
B）关系
C）存储
D）映像
15.线性结构的顺序存储结构是一种A的存储结构。
A）随机存取
B）顺序存取
C）索引存取
D）散列存取
16.组成数据的基本单位是__C__。
A）数据项
B）数据类型
C）数据元素
D）数据变量
17.双循环链表的*p结点之后插入*s结点的操作是-D—
A） p->next=s，s->prior=p，
p->next->prior=s，s->next=p->next；
B） p->next=s，p->next->prior=s，
s->prior=p，s->next=p->next；
C） s->prior=p，s->next=p->next，
p->next=s，p->next->prior=s；
D） s->prior=p，s->next=p->next，
p->next->prior=s，p->next=s；
18.一维数组和线性表的共同点是A。
A）两者都是相同类型数据的集合
B）两者都允许不同类型数据共存
C）两者长度均固定
D）两者长度均可变
19.线性链表中各链接结点之间的地址__A___。
A）连续与否都可以
B）必须连续
C）一定不连续
D）部分地址必须连续
20.对于只在表的首、尾两端进行插入操作的线性表，宜采
用的存储结构为C。
A）单链表
B）用头指针表示的单循环链表
C）用带尾指针表示的单循环链表
D）顺序表
二.多选题
1.下列关于链式存储结构的叙述中，正确的是__ACD__。
A）结点除自身信息外还包括指针域，因此存储密度小于
顺序存储结构
B）可以通过计算直接确定第i个结点的存储地址
C）逻辑上相邻的结点物理上不必相邻
D）插入、删除操作方便，不必移动结点
2.下面的叙述正确的是__AD__。
（06）
A）线性表在链式存储时，查找第i个元素的时间同i的值成正比
B）线性表在链式存储时，查找第i个元素的时间同i的值无关
C）线性表在顺序存储时，查找第i个元素的时间同i的值成正比
D）线性表在顺序存储时，查找第i个元素的时间同i的值无关
3.链表具有的特点是_ABD___。
A）插入、删除不需要移动元素
B）不必事先估计存储空间
C）可随机访问任一元素
D）所需空间与链表长度成正比
4.下列关于链式存储结构的叙述中，正确的是_AD___。
A）结点除自身信息外还包括指针域，因此存储密度小于顺序
存储结构
B）可以通过计算可以直接确定第i个结点的存储地址
C）逻辑上相邻的结点物理上必须相邻
D）插入、删除操作方便，不必移动结点
5.数据元素之间的关系在计算机中的表示方法有_AD_______。
A）顺序映像
B）线性结构
C）非线性结构
D）非顺序映像
三、判断题
1.数据结构中与所使用的计算机无关的是数据的逻辑结构。
2.线性表是一个有序序列，其中可包含相同的元素，也允许各
个元素可以是不同的数据类型。
3.链表的每个结点都含有两个指针。
4.线性结构的基本特征是：
每个结点有且仅有一个直接前
趋和一个后继。
5.线性表中各元素类型必须是相同的。
6.数据结构的操作一定是定义在逻辑结构上，实现在存储
结构上。
7.数据的逻辑结构指的是数据元素之间的逻辑关系的整体。
正确1567
四、填空题
1.数据结构包括的三个方面的内容是、和。
2.通常衡量算法效率的一般标准为和。
3.算法是对特定问题求解步骤的一种描述，它具有有穷性、
确定性、可行性、_________及一个或多个输出等重要特征。
4.数据结构是相互之间存在一种或多种关系的______集合。
5.线性结构中元素的关系是_______的关系。
答案：
1逻辑结构、存储结构、运算
2时间复杂度、空间复杂度
3具有零个或多个输入
4数据元素
5一对一
6.用一维数组表示线性表L=（a1,a2,……,an），假定删除表中
任一元素的概率相同（都为1/n），则删除一个元素平均需移
动的元素个数为________。
（n-1）/2
7.当线性表采用顺序存储结构进行存储时，其主要特点是
________。
逻辑结构相邻的结点存储结构也相邻
8.链式存储结构最显著的优点是______。
方便插入、删除操作
9.单循环链表的最显著的优点是________。
答：
从任意结点出发都可以访问链表中的每个元素
10.一个线性表第一个元素的存储地址是100，每个元素的长度
为2，则第6个元素的地址是________。
答：
110
五、简答题
1．解释数据结构、逻辑结构、存储结构的概念，并讨论他
们之间的关系；
参考答案：
数据结构：
相互之间存在一种或多种特定关系的
数据元素的集合。
逻辑结构：
逻辑结构描述数据之间的逻辑
关系。
包括集合、线性、树形和网状结构。
存储结构：
数据
结构在计算机中的表示称存储结构。
包括顺序、索引、链式
和散列。
三者关系：
在数据结构中，数据的逻辑结构和存储
结构密切相关的；存储结构不仅存储数据元素，还要存储数
据元素的逻辑关系；逻辑结构与计算机无关；逻辑结构相同
但存储结构不同，可以是不同的数据结构。
2．线性表的顺序存储具有如下缺点：
（1）.在进行插入或删除
操作时，需要移动大量元素；
（2）.由于难以估计其大小，必须
预先分配较大的存储空间，往往使存储空间得不到充分利用
；（3）.表的容量难以扩充。
试问线性表的链式存储结构是否一
定能克服上述缺点？
试做简要讨论。
参考答案：
链式存储结构一般克服的顺序结构的三个弱点：
首先，链式存储结构插入、删除不需要移动元素，只需修改
指针，时间复杂度为O
（1）；其二，不需要预先分配存储空间
，可根据需要动态申请；其三，表容量只受内存空间的限制
；
缺点：
因指针增加了内存空间开销，当空间不允许时，就不能
克服顺序存储的优点。
六、编程题
1．已知两个带头结点的单链表La和Lb中的元素按非递减顺
序排列，试用C语言编写一个函数将这两个有序表合并成一
个有序单链表保存在La中，而不改变其排序性。
设带头结点
的单链表的结点结构说明及函数名如下：
ntypedefstructnode/*定义结点结构*/
{datatypedata;
structnodenext;
}lklist;
ntypedefstructnode*pointer;
n函数首部为：
Øpointermergelklist（lklistha,lklisthb）
1题参考答案
pointermergelklist（lklistha,lklisthb）
{pointer*h,*pa,*pb;
pa=ha->next,pb=hb->next；
h=r=ha；
while（pa&&pb）
If（pa->data<=pb->data）/*移动ha,hb头指针,修改r指向
{r->next=pa;r=pa;pa=pa->next}；
else
{r->next=pb;r=pb;pb=pb->next}；
if（pa==NULL）r->next=pb;
if（pb==NULL）r->next=pa;
returnh；
}
2．设计算法求两个递增有序的顺序表L1和L2中的公共元素
，并将其置入顺序表L3中，用C语言实现。
设顺序表存储结
构说明如下：
ntypedefstruct{
ElemType*elem;
Intlength;
}sqlist;
nsqlistL1,L2,L3;
n函数首部为：
statuscomplist（sqlistL1,sqlistL2,sqlistL3）
2题参考答案
statuscomplist（sqlistL1,sqlistL2,sqlistL3）
{i1=0,i2=0,i3=0;
L3.length=0;
while（i1<=L1.length-1）&&（i2<=L2.length-1）
{if（L1.elem[i1]if（L1.elem[i1]>L2.elem[i2]）i2=i2+1;
if（L1.elem[i1]=L2.elem[i2]）
{L3.elem[i3]=L1.elem[i1];
i3=i3+1;
i1=i1+1;
i2=i2+1;}
}
L3.length=i3;
}
升级会员 