数据结构复习题目.docx
《数据结构复习题目.docx》由会员分享，可在线阅读，更多相关《数据结构复习题目.docx（79页珍藏版）》请在冰点文库上搜索。
数据结构复习题目
第1章概论
练习题
一、单项选择题
1•在数据结构中，从逻辑上可以把数据结构分为
A.紧凑结构和非紧凑结构
C.内部结构和外部结构
B.线性结构和非线性结构
D.动态结构和静态结构
2.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为
A.顺序存储结构B.链式存储结构
C.索引存储结构D.散列存储结构
3.算法分析的两个主要方面是
A.正确性和简明性B.时间复杂性和空间复杂性
C.可读性和可维护性D.数据复杂性和程序复杂性
4.线性表采用链式存储结构时，要求内存中可用存储单元地址
A.不一定连续的B.部分地址必须是连续的
C.必须是连续的D.—定是不连续的
5.算法指的是
A.计算机程序
C.解决问题的有限运算序列
二、填空题
6.数据结构一般包括逻辑结构、存储结构和数据运算三个方面的内容.
7.数据的逻辑结构可分为线性结构、非线性结构两大类.
&数据的存储结构（物理结构）一般可以用顺序存储结构、链式存储结构、索引存储结构
结构等四种存储方法表示.
9.在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑的时间、执行算法所需要的存储空间及算法应易于理解、易于编程、易于调试等三点。
10.设有一批数据元素，为了最快地存取某元素，宜用顺序结构存储，为了方便的插入一个元素，宜用链式结构存储.
三、应用题
设n为正整数，利用大“0”记号，写出下列各程序段的时间复杂度.
B.解决问题的计算方法
D.排序算法
for（i=1;i<=n;i++）{
y=y+1;
for（j=1;j<=2*n;j++）
x=x+1;
分析:
（B）
（D）
（B）
（C）
及散列存储
执行算法所需要
}
语句“y=y+1；”执行n次，语句“x=x+1”各执行2n2次，故该程序段的时间复杂度为0（n2）.
12.s=0;
while（n>=（s+1）*（s+1））
s=s+1;
分析：
语句“s=s+1”执行.n次，故该程序段的时间复杂度为0（.n）.
13.x=1;
sum=0;
for（i=0;i<=n;i++）{
x=x*i;
sum=sum+x;
}
分析：
语句“x=x*i”和“sum=sum+x;"各执行n次，故该程序段的时间复杂度为0（n）.
14.for（i=1;i<=n;i++）
if（3*iv=n）
for（j=3*i;j<=n;j++）{
x++;
y=3*x+2;
}
分析：
语句“x++”和"y=3*x+2;”各执行6n（n1）次，故该程序段的时间复杂度为0（n2）.
15.for（i=1;i<=n;i++）
for（j=1;j<=i;j++）{
x=x+1;
}
一1
分析：
语句“x=x+1”执行2n（n1）次，故该程序段的时间复杂度为o（n2）.
16.sum=0;i=0;
while（i<=100）{
sum=sum+i;
i++;
}
分析：
语句“sum=sum+i;”和“i++;”各执行100次，故该程序段的时间复杂度为0
（1）.
17.x=1;
s=0;
for（i=1;i<=n;i++）{
++x;
s+=x;
}
for（j=1;j<=n;j++）
for（k=1;k<=n;k++）{
x++;
s=s+x;
}
分析：
语句“++x;”执行n次，语句"x++;”和"s=s+x”各执行n2次，故该程序段的时间复杂度为0（n2）.
第2章线性表
练习题
一、单项选择题
1在长度为n的顺序表的第i（1in1）个位置上插入一个元素，元素的移动次数为（A）
A.nilB.niC.iD.i1
2•若一个顺序表中第一个元素的存储地址为1000,每个元素占4个地址单元，那么，第6个元素的存
储地址应是（A）
A.1020B.1010C.1016D.1024
3•带头结点的单链表（以head为头指针）为空的判断条件是（C）
A.head!
=NULLB.head>next==head
C.head>next==NULLD.head==NULL
4.在单循环链表中，p指向表任一结点，判断表不是访问结束的条件是（B）
A.p!
=NULLB.p!
=headC.p>next!
=headD.p>next!
=NULL
5.在一个单链表中，已知q指向p所指向结点的前趋结点，若在p、q所指结点之间插入一个s所指
向的新结点，则执行的操作是（A）
A.q>next=s;s>next=pB.p>next=s;s>next=q
C.s>next=p>next;p>next=sD.p>next=s>next;s>next=p
6.在一个单链表中，若删除p指向结点的后继结点，则执行的操作是（A）
A.q=p>next;p>next=p>next>next;free（q）;
B.p=p>next;q=p>next;p=q>next;free（q）;
C.q=p>next>next;p=p>next;free（q）;
D.p=p>next>next;q=p>next;free（q）;
二、填空题
7.在一个长度为n的顺序表中删除第i个元素，需要向前移动ni个元素.
&在顺序表中插入或删除一个元素，需要平均移动表长的一半个元素，具体移动的元素个数与插入或
删除的位置有关.
9.顺序表中逻辑上相邻的元素在物理存储位置上一定相邻，链表结构中逻辑上相邻的元素在物理位置上不一定相邻.
10.已知顺序表中一个元素的存储位置是x,每个元素占c个字节，求其后继元素位置计算公式为xc,
而已知单链表中某一结点由p指向，求此后继结点存储地址的操作为p>next.
11.在用p指针访问单链表时，判断不是访问结束的条件是p!
NULL;在访问单循环链表时，判断不
是访问表结束的条件是p!
head.
12.已知p指向双向链表的中间某个结点，从给定的操作语句中选择合适的填空.
（1）在p结点后插入s结点的语句序列是I、G、A、D.
（2）在p结点前插入s结点的语句序列是C、N、H、B.
（3）删除p结点的直接后继结点的语句序列是J、Q、E、M.
（4）删除p结点的直接前趋结点的语句序列是K、P、F、M.
（5）删除p结点的语句序列是0、R、L.
A.p>nextsB.p>priorsC.s>nextp
D.s>priorpE.p>nextp>next>nextF.p>priorp>prior>prior
H.p
>prior>nexts
I.s>next
p>next
K.q
p>prior
L.free（p）
N.s
>priorp>prior
O.p>prior
>next
p>next
pQ.p
>next>next>prior
pR.p>next
>prior
p>prior
head
中删除所有数据域值为
x的结点的算法，
但不完善，
请在相
G.p>next>priors
J.qp>next
M.free（q）
P.p>prior>prior>next
13.下面是一个在带头结点的单链表
应的地方填上适当的语句，使之成为完整的算法.
voidDeleX（LinkListhead,DataTypex）{
LinkNode*p,*q,*s;
Phead;
qp>next;
while（q!
=NULL）
if（q>datax）
{
sq;
qq>next;free（s）;
p>nextq;}else{
pq;
qq>next;
}
}
三、算法设计题
14.设有两个顺序表A和B,且都递增有序。
试写一算法，从A中删除与B中相同的那些元素（即计
算AB）.
SeqListSubtraction（SeqListA,SeqListB）
{
inti,j,k0;//令匹配位置为0
for（i0;ifor（jk;jif（A.Data[i]B.Data[j]）
{
kj;//记录比较到的位置
for（ji;jA.Data[j]A.Data[j1];//删除相同的元素
A.Length;
break;
}
}
returnA;
15.已知head是指向一个带头结点的单链表的头指针，p指向该链表的任一结点。
试写一算法，将p
所指向的结点与其后继结点交换位置.
voidExchange（LinkListhead,LinkNode*p）
{
LinkNode*q,*s,*r;
qp>next;
if（q!
NULL）//判断所指结点是否是最后一个结点
{
if（phead）//判断所指结点是否是头结点
{
headhead>next;//头结点指针域所指结点变成新的头结点
shead>next;//记录第2个结点
head>nextp;//新的头结点指针域指向原头结点
p>nexts;//原头结点变成第1个结点后指针域指向第2个结点
}
else{
rhead;
while（r>next!
p）
rr>next;//查找p指向结点直接前趋
r>nextq;//p指向结点直接前趋指针域指向p指向结点直接后继
p>nextq>next;//p指向结点指针域指向p指向结点直接后继的直接后继
q>nextp;//p指向结点直接后继指针域指向p
}
}
elseprintf（p指向的结点无后继节点！
”
}
16.已知两条单链表A和B分别表示两个集合，其元素值递增有序。
试写一算法，求A和B的交集C,
要求C同样以元素值递增的单链表形式存储.
LinkListIntersection（LinkListA,LinkListB）
{
LinkNode*p,*q,*r,*s;
LinkListC（LinkNode*）malloc（SizeOf（LinkNode））;
rC;pA;sB;
while（p!
null&&q
!
null）{
if（p
>data<
q>data）
p
p>next;
else
if（p
>data>q>data）
q
q>next;
else{
s
（LinkNode*）malloc（SizeOf（LinkNode））;
s
>datap>data;
s
>nextNULL;
r>nexts;
r
s;
p
p>next;
qq>next;
}
}
17.设有一个带头结点的双向循环链表，head为链表的头指针。
试写一算法，实现在值为x的结点之
前插入一个值为y的结点.
voidlnsert（DlinkListhead,DataTypex,DataTypey）
{
DlistNode*p,*s;
s（DlistNode*）malloc（SizeOf（DlistNode））;
s>datay;
phead>next;
while（p!
head&&p>data!
x）
pp>next;//查找结点值为x的结点
if（phead）
printf（没有值为x的结点！
”）；
else
{
s>nextp;
s>priorp>prior;
p>prior>nexts;
p>priors;
}
}
第3章栈和队列
练习题
一、单项选择题
1.栈的操作原则是（C）
A.顺序进出B.后进后出C.后进先出D.先进先出
2.进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为（B）
A.4B.5C.6D.7
3.按字母a,b,c,d,e顺序入栈，则出栈的输出序列不可能是（B）
A.decbaB.dceabC.abcdeD.edcba
4.判断一个顺序栈st（最多元素为StackSize为栈满的条件表达式是（D）
A.st.top!
StackSizeB.st.top!
0C.st.top!
1D.st.topStackSize1
5.在向顺序栈中压入元素时（C）
A.先存入元素，后移动栈顶指针B.谁先谁后无关紧要
C.先移动栈顶指针，后压入元素D.同时进行
6.—个队列的入队序列是1,3,5,7,9，则出队的输出序列只能是（B）
A.9,7,5,3,1B.1,3,5,7,9
C.1,5,9,3,7D.9,5,1,7,3
7.判断一个顺序队列sq（最多元素为QueueSize）为空队列的条件表达式为（A）
A.sq.rearsq.frontB.sq.rear0
C.sq.frontQueueSizeD.sq.rearQueueSize1
&判断一个循环队列cq（最多元素为QueueSize）为满队列的条件表达式为（C）
A.cq.rearcq.frontB.cq.rearQueueSize
C.（cq.rear1）%QueueSizecq.frontD.cq.rear%QueueSize1cq.front
二、填空题
9.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为b、c、e、d、a.
10.假设S.data[maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置。
能做进栈操作的条件是
S.topxS.data[S.top].
11.设顺序栈存放在S.data[maxsize]中，栈底位置是maxsize1,则栈空条件是S.topmaxsize,栈满条件是S.top0.
12.若循环队列用数组data[m]存储元素值，用front和rear分别作为头尾指针，则当前元素个数为（rearfrontm）%m.
13.栈和队列都是线性结构；对于栈，只能在栈顶插入和删除元素；对于队列，只能在队尾插入元素，在队头删除元素.
14.从循环队列中删除一个元素时，其操作是先取出队头元素，后移动队头指针.
三、解答题
15.如果编号为1,2,3的3辆列车进入一个栈式结构的站台，那么可能得到的3辆列车的出栈序列有哪些？
不可能出现的序列是什么？
答：
可能出现的出栈序列有1、2、3,1、3、2,2、1、3,2、3、1,3、2、1，不可能出现的序列是3、1、2。
16.假设输入栈的元素为a、b、c,在栈S的输出端得到一个输出序列为a、b、c,试写出在输入端所
有可能的输入序列.
答：
可能的输入序列有ab、c,a、c、b,b、ac,c、b、a,c、a、b.
17.简述下面所给算法的功能（假设栈元素为整数类型）
（1）voidex31（SeqStack*S）
{
intA[80],i,n0;
while（!
empty（s））{
A[n]pop（s）;//将栈内元素依次存入数组
n;
}
for（i0;ipush（S,A[i]）;〃将数组元素依次压入栈内
}
答：
该算法的功能是将通过一个数组将栈内的所有元素逆序存放.
（2）voidex32（SeqStack*S,intc）{
SeqStackT;
intd;
while（!
StackEmpty（S））{
dpop（S）;
if（d!
c）push（T,d）;
while（!
StackEmpty（T））{
dpop（T）;
push（S,d）;
}
}
答：
该算法的功能是通过一个中间栈，删除栈S中所有值为c的元素.
18
char）.
•写出下列程序段的输出结果（栈结点数据域为字符型
SeqStackS;
charx=c：
y=k'';
push（S,x）;〃压入'，栈内'
push（S,a"）;〃压入'，栈内'a'
push（S,y）;〃压入''栈内'cak'
x=pop（S）;//弹出C到x,栈内Ca'push（S,t"）；〃压入CC栈内Cat'push（S,x）;〃压入''栈内'atk'
x=pop（S）;//弹出'到x,栈内'at'push（S,压入'栈内'ats'while（!
StackEmpty（S））{
y=pop（S）;
putchar（y）;//依次弹出并输出栈内元素
}
putchar（x）;//输出/k/
答：
程序段的输出结果是stack.
19•在循环队列的顺序存储结构下，分别写出入队（插入元素）、出队（删除元素）时修改队尾、队头
指针的操作语句以及求队列长度的公式.
答：
入队时修改队尾指针的语句为cq.rear（cq.rear1）%QueueSize,出队时修改队头指针的操作语句为cq.front
（cq.front1）%QueueSize求队列长度的公式为（cq.rearcq.frontQueueSize）%Queue
四、算法设计题
20.利用两个栈S1和S2模拟一个队列，如何用栈的运算来实现队列的插入和删除运算？
试写出算法.
设模拟的队列如下图所示.top1为队头指针，top2为队尾指针：
top1frontS2——>top2rear
voidInsert（DataTypex,SeqStack*S1,SeqStack*S2）DataTypeDelete（SeqStack*S1,SeqStack*S2）
{{
if（top2S2.Size）
printf（“QueueFull）;”
if（top1>top2）printf（QueueEmpty"）;
top2;
if（top1<1）
xS1.data[top1];
if（top2>0）
else
xS2.data[top1];
S2.data[top2]
x;
top1++;
elseS1.data[top2]
x;
returnx;
21.试设计一个算法，实现输入一字符串并检查字符串中是否含有圆括号，当圆括号匹配时输出括号内的字符串，否则给出出错信息（提示：
利用栈记录左括号出现后的字符）
stringMatch（）{
InitStack（S）;
ch=getchar（）;
while（ch!
=‘'{
if（ch==（'）'{
push（S,ch）;
ch=getchar（）;
while（ch!
=‘'&&ch!
=）'{
push（S,ch）;
ch=getchar（）;
}
}
elseif（ch=='）{
while（（!
StackEmpty（S））&&GetTop（S）!
=（（）'putchar（pop（S））;
if（StackEmpty）
printf（NoMatch”；
}
elsech=getchar（）;
}
if（StackEmpty（S））printf（NoMatch”；
}
22.
.//初始化栈
//读取第一个字符
//当前字符不为结束字符时，进入循环
//检测到左括号
//将左括号压入栈中
//读取下一个字符
//字符不为结束字符和右括号时，进入循环
//将字符压入栈中
//读取下一个字符
//读取到的字符为右括号时，进入循环
//栈不空且栈顶元素不为左括号，进入循环
//退栈并输出退栈的字符
//如果栈为空，表示输入字符串仅包含右括
//号，输出"无匹配"信息
//读取到的字符不是括号，继续读取
//如果栈为空，表示输入字符串不包含括号
//输岀“无匹配”信息
n（nk）项（fo，fi，…，fni）
试利用循环队列（长度为k）存储，编写求斐波那契序列的前
0
n
0
的算法，其函数定义如下：
f（n）
1
n
1
f（n
2）
f（n1）n
2
intFibonacci（inti）
r
{
if（i==0）
return0;
elseif（i==1）
return1;
else
return（Fibonacci（i
2）+
Fibonacci（i
1））;
}
voidFibCirQueue（CirQueue*Q,intk,intn）
{
Q>rear=0;
for（inti=0;iQ>rear=i;
if（i>=k）Q>rear=Q>rear%k;
Q>data[Q>rear]=Fibonacci（i）;
第4章多维数组和广义表
练习题
一、单项选择题
1.对矩阵的压缩存储是为了
A.方便运算B.节省空间C.方便存储
2.二维数组M的元素是4个字符（字符占一个存储
升级会员 