数据结构习题及答案Word文档下载推荐.docx
《数据结构习题及答案Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构习题及答案Word文档下载推荐.docx（52页珍藏版）》请在冰点文库上搜索。
若一组结点在索引表中只对应一个索引项，则索引存储方式称为稀疏索引。
在稠密索引中，索引项的地址指示结点所在的位置，而稀疏索引中，索引项的地址指示一组结点的起始位置。
16、散列存储方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。
17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列，其中每个指令表示一个或多个操作。
18、算法的有穷_性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。
19、算法的确定性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。
并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到相同的输出结果。
20、算法的可行性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行有限_次来实现，即算法的具体实现应该能够被计算机执行。
21、判断一个算法的好坏主要以下几个标准：
正确性，可读性_、健壮性、效率。
22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和所占据空间的大小。
23、空间复杂度（SPaceComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用存储空间的大小。
三、判断题
1、顺序存储方式只能用于存储线性结构。
（×
）树型结构也可以用顺序方式进行存储。
2、数据元素是数据的最小单位。
）数据元素是数据的基本单位，数据项是数据的最小单位。
3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言描述，则算法实际上就是程序了。
）算法用各种计算机语言描述表现为一个程序，但是不等于程序，程序逻辑不一定能满足有穷性。
4、数据结构是带有结构的数据元素的集合。
（对）
5、数据的逻辑结构是指各元素之间的逻辑关系，是用户根据需要而建立的。
（对）6、数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。
7、数据的物理结构是指数据在计算机中实际的存储形式。
8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。
四、综合题
1、用大O形式表示下面算法的时间复杂度：
for（i=0；
i＜m；
i十十）
for（j=0；
j＜n；
j＋＋）
A[i][j]=i*j；
O（m×
n）。
2、写出下面算法的时间复杂度：
i＝0；
s=0；
while（s＜n）
｛i++;
s+=i;
｝O（
）
3、写出以下算法的时间复杂度：
for（i＝0;
i＜m;
i＋＋）
for（j＝0;
j＜t;
j＋＋）
c[i][j]=0；
for（i=0；
i＋＋）
for（j=o;
j<
t;
j++）
for（k=0；
k＜n；
k＋＋）
c［i］［j］＋＝a［i］［k］*b[k][j];
n×
t）。
4、写出下面算法的时间复杂度：
i=1;
while（i＜＝n）
i=i*3;
log3（n）。
5、求下面函数中各条语句的频度和算法的时间复杂度：
prime（intn）
｛
inti＝2；
while（（n％i）！
=0＆＆i＜sqrt（n））
i++;
if（i＞sqrt（n））
printf（”％disaprimenumber.＼n”，n）；
else
printf（”％disnotaprimenumber.＼n”，n）；
｝
O（
）
习题二
1．在一个长度为n的顺序表中删除第i个元素（0＜i<
n）时，需要向前移动（A）个元素。
A．n-iB．n-i+1C．n-i+1D．i+1
2．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（C）个元素结点。
A．n/2B．nC．（n-1）/2D．（n+1）/2
3．对一个具有n个元素的线性表，建立其单链表的时间复杂度为（A）。
A．O（n）B．O
（1）C．O（n2）D．O（long2n）
4．线性表采用链式存储时，其地址（D）。
A．必须是连续的B．一定是不连续的
C．部分地址必须连续D．连续与否均可以
5．在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是（D）。
A．O（long2n）B．O（l）C．O（n2）D．O（n）
6．线性表是（A）。
A．一个有限序列，可以为空B．一个有限序列，不可以为空
C．一个无限序列，可以为空D．一个无限序列，不可以为空
7．在一个长度为n的顺序表中，向第i个元素（0一1＜n＋1）之前捕人一个新元素时，需要向后移动（B）个元素。
A．n-iB．n-i＋1C．n－i－1D．i＋1
8．如果某链表中最常用的操作是取第i个结点及其前驱，则采用（D）存储方式最节省时间。
A．单链表B．双向链表C．单循环链表D．顺序表
9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。
A．98B．100C．102D．106
10．下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（C）。
A．堆排序B．冒泡排序C．直接插人排序D．快速排序
11．对线性表进行二分查找时，要求线性表必须（C）。
A．以顺序方法存储
B．以链接方法存储
C．以顺序方法存储，且结点接关键字有序排列
D．以链接方法存储，且结点接关键字有序排列
12．在顺序存储的线性表（a1……an）中，删除任意一个结点所需移动结点的平均移动次数为（C）
A．nB．n／2C．（n-1）/2D．（n＋l）/2
13．在线性表的下列存储结构中，读取元素花费的时间最少的是（D）。
A．单链表B．双链表C．循环链表D．顺序表
14．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（D）存储方式最节省时间。
A．双链表B．单链表C．单循环链表D．带头结点的双循环链表
1．线性表（LinearList）是最简单、最常用的一种数据结构。
线性表中的元素存在着___一对一的相互关系。
2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有巨仅有一个直接前驱，除终端结点外，其他每个元素有且仅有一个直接后继
3．线性表是n（n>
=0）个数据元素的_有限序列。
其中n为数据元素的个数，定义为线性表的长度。
当n为零时的表称为空表。
4．所谓顺序表（SequentialLISt）是线性表的顺序存储结构，它是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在地址相邻的存储单元中。
5．单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。
它是分配一些任意的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的任意的位置上，它们在物理上可以是一片连续的存储单元，也可以是不连续的。
因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的逻辑关系。
6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：
一部分用来存放元素的数据信息，称为结点的数据域；
另一部分用来存放元素的指向直接后继元素的指针（即直接后继元素的地址信息），称为指针域或链域。
7．线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。
其逻辑顺序和物理存储顺序不再一致，而是一种非顺序存储结构，又称为非顺序映像。
8．如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了循环链表
。
9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了双向链表。
10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p所指向的结点本身。
11．在单链表中，删除指针P所指结点的后继结点的语句是P->
next=p->
next->
next
_。
12．在双循环链表中，删除指针P所指结点的语句序列是P->
prior->
next＝p->
next及P->
prior=P->
prior_。
13．单链表是线性表的链接存储表示。
14．可以使用双链表表示树形结构。
15．向一个长度为n的向量的第i个元素（l≤i≤n+1）之前插人一个元素时，需向后移动n-i+1个元素。
16．删除一个长度为n的向量的第i个元素（l≤i≤n）时，需向前移动n-i
个元素。
17．在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是S->
next=P->
next;
P->
next=S
18．在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句p->
next=S;
s->
prior=p->
prior;
next=p;
p->
prior=s;
19．取出广义表A＝（（x，（a，b，c，d））中原子c的函数是head（tail（tail（（head（tail（head（A））））））。
20．在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为O（n）。
21．写出带头结点的双向循环链表L为空表的条件（L==L->
Next）&
&
（L==L->
Prior）
22．线性表、栈和队列都是线性_结构。
23．向栈中插人元素的操作是先移动栈顶针，再存人元素。
1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
（错）
2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。
3．顺序存储的线性表不可以随机存取。
（错）
4．单链表不是一种随机存储结构。
5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。
6．顺序存储结构是动态存储结构，链式存储结构是静态存储结构。
7．线性表的长度是线性表所占用的存储空间的大小。
8．双循环链表中，任意一结点的后继指针均指向其逻辑后继。
9．线性表的惟一存储形式是链表。
1．编写一个将带头结点单链表逆置的算法。
voidreverse_list（linklist*head）
{
/*逆置带头结点的单链表*/
linklist*s,*p;
p=head->
/*p指向线性表的第一个元素*/
head->
next=NULL;
/*初始空表*/
while（p!
=NULL）
{
s=p;
p=p->
s->
next=head->
head->
next=s;
/*将s结点插入逆表*/
}
}/*reverse_list*/
2．ha和hb分别是两个按升序排列的、带头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表，并用hC指向它的头结点。
linklist*combine_list（linklist*ha,linklist*hb）
/*ha,hb分别是两个按升序排列的,带有头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表,并用hc指向它的头结点*/
linklist*hc,*pa,*pb,*pc,*p,*q,*r;
hc=（linklist*）malloc（sizeof（linklist））;
/*建立hc头结点*/
p=hc;
pa=ha->
free（ha）;
/*释放ha头结点*/
pb=hb->
free（hb）;
/*释放hb头结点*/
while（pa!
=NULL&
pb!
=NULL）
q=（linklist*）malloc（sizeof（linklist））;
/*产生新结点*/
if（pb->
data<
pa->
data）
{
q->
data=pb->
data;
pb=pb->
}
else
data=pa->
pa=pa->
if（pa->
data==pb->
data）/*将相同的元素删除*/
{
r=pb;
pb=pb->
free（r）;
}
p->
next=q;
/*将结点链入c链表*/
p=q;
while（pa!
=NULL）/*a链表非空*/
q->
pa=pa->
while（pb!
=NULL）/*b链表非空*/
pb=pb->
p->
return（hc）;
/*返回*/
}
3．有一个带头结点的单链表，头指针为head，编写一个算法count．list（）计算所有数据域为X的结点的个数（不包括头结点）。
intcount_list（linklist*head）
/*在带头结点的单链表中计算所有数据域为x的结点的个数*/
linklist*p;
intn;
/*p指向链表的第一个结点*/
n=0;
while（p!
=NULL）
if（p->
data==x）
n++;
return（n）;
/*返回结点个数*/
}/*count_list*/
4．在一个带头结点的单链表中，头指针为head，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertx＿list（），在该链表中插人值为x的元素，并使该链表仍然有序linklist*insertx_list（linklist*head,intx）
/*在带头结点的单链表中插入值为x的元素，使该链表仍然有序*/
linklist*s,*p,*q;
s=（linklist*）malloc（sizeof（linklist））;
/*建立数据域为x的结点*/
s->
data=x;
if（head->
next==NULL||x<
head->
data）/*若单链表为空或x小于链表第一个结点的数据域*/
q=head->
p=q->
while（p!
=NULL&
x>
data）
q=p;
p=p->
}/*if*/
}/**insertx_list*/
5．在一个带头结点的单链表中，head为其头指针，p指向链表中的某一个结点，编写算法swapin．list（），实现p所指向的结点和p的后继结点相互交换。
linklist*swapin_list（linklist*head,linklist*p）
/*在带头结点的单链表中，实现p所指向的结点和p的后继结点相互交换*/
linklist*q,*r,*s;
q=p->
/*q为p的后继*/
if（q!
=NULL）/*若p有后继结点*/
if（p==head）/*若p指向头结点*/
head=head->
s=head->
head->
p->
else/*p不指向头结点*/
r=head;
/*定位p所指向结点的前驱*/
while（r->
next!
=p）
r=r->
r->
/*交换p和q所指向的结点*/
next=q->
return（head）;
else/*p不存在后继*/
return（NULL）;
}/*swapin_list*/
6．有一个带头结点的单链表，所有元素值以非递减有序排列，head为其头指针，编写算法deldy．list（）将linklist*deldy_list（linklist*head）
/*在带头结点的非递减有序单链表，将该链表中多余的元素值相同的结点删除*/
linklist*q;
next!
=NULL）/*判断链表是否为空*/
p=head->
while（p->
=NULL）
if（p->
data!
=p->
p=p->
else
q=p->
/*q指向p的后继*/
p->
/*删除q所指向的结点*/
free（q）;
/*释放结点空间*/
}/*while*/
return（head）;
}/*deldy_list*/
该链表中多余元素值相同的结点删除。
7．在带头结点的单链表中，设计算法dellistmaxmin，删除所有数据域大于min，而小于max的元素。
linklist*dellist_maxmin（linklist*head,intmin,intmax）
linklist*p,*q;
q=head;
while（p!
=NULL）/*结点不空*/
if（（p->
=min）||（p->
data>
=max））/*不满足删除条件*/
else/*满足删除条件*/
q->
free（p）;
q=q->
}/*dellist_maxmin*/
8．设计一个将双链表逆置的算法invert．dblinklist（），其中头指针为head，结点数据域为data，两个指针域分别为prior和next。
将双链表逆置的算法invert_dblinklist的算法如下所示：
voidinvert_dblinklist（linklist*head）
/*将head指向的双链表逆置*/
dblinklist*p,*q;
p=head;
do
q=p->
prior=q;
}while（p!
=head）
}/*invert_dblinklist*/
习题三
l．一个栈的序列是：
a，b，c，d，e，则栈的不可能输出的序列是（C）。
A．a，b，c，d，eB．d，e，c，b，aC．d，c，e，a，bD．e，d，c，b，a
2．若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C）。
A．kB．n-k-1C．n-k+1D．不确定
3．判定一个栈S（最多有n个元素）为空的条件是（B）。
A．S->
top！
＝
升级会员 