中学信息学《数据结构》习题及参考答案文档格式.docx
《中学信息学《数据结构》习题及参考答案文档格式.docx》由会员分享，可在线阅读，更多相关《中学信息学《数据结构》习题及参考答案文档格式.docx（9页珍藏版）》请在冰点文库上搜索。
While（i i++;
}
（2） i=1;
do（i }while（I While（i @k+=10*i;
} （4） k=0;
for（i=1;
i @k++;
} （5） for（i=1;
i for（j=i;
j （6）i=1;
j=0;
While（i+jj）j++;
elsei++;
} （7）x=n;
y=o;
while（x>
=（y+1）*（y+1））{@y++;
} （8）x=91;
y=100;
while（y>
0）{ @if（x>
100）{x-=10;
y--;
}elsex++;
} ③假设n为2的乘幂，并且n>
2，试求下列算法的时间复杂度及变量count的值 。
intTime（intn）{ Count=0;
x=2;
While（x return（count） }//Time ②按增长率小到大的顺序排列下列各函数：
2100（3/2）n（2/3）n（4/3）n nn n3/2 n2/3 n!
n, log2n log22nlog2（log2n） nlog2n nlog2n ③已知有现实同一功能的两个算法，其时间复杂度分别为O和O， 假设现实计算机可连续运算的时间为107秒，又每秒可执行基本操 5 作10次。
试问在此条件下，这两个算法可解问题的规模各为多少？
哪个算法更适宜？
请说明理。
③设有以下三个函数：
f（n）=21n4+n2+1000 g（n）=15n4+500n3h（n）=5000+nlogn 请判断以下断言正确与否：
f（n）和O（g（n））
（2）h（n）和O（f（n）） （3）g（n）和O（h（n）） （4）h（n）和O（） （5）h（n）和O（nlogn） ③试设定若干n的值，比较两函数n2和50nlog2n的增长趋势，并确定n在什 么范围内，函数n2的值大于50nlog2n的值 ③判断下列各对函数f（n）和g（n）,n趋进于∞时，哪个函数增长更快？
试用数学归纳法证明：
算法设计题 ②试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。
③已知k阶裴波那契序列的定义为：
试编写k阶裴波那契序列的第项值的函数算法，k和m均以值调用的形式在函数参数表中出现。
③假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为：
项目名称性 别校 名成 绩得 分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。
④试编写算法，计算i!
.2i的值并存入数组a[0…arrsize-1]的第i-1个分量中。
假设计算机中允许的整数最大值为maxint,则当n>
arrsize或对某个k（1≤k≤n）使 k!
.2k>
maxint时，应按出错处理，注意选择你认为较好的出错处理方法。
④试编写算法求一元多项式的值 的值Pn（x0）并确定算法中每一语句的执行次数和整个算法的时间复杂度。
注意选择你认为较好的输入和输出方法。
本题的输入为aj（i=0,1,…..n）x0和n,输出为Pn（x0）。
第2章 线性表 基础知识题 ①描述以下三个概念的区别，头指针，头结点，首元结点。
①填空题。
在顺序表①中插入或删除一个元素，需要平均移动 元素，具体移动的元素与 有关。
顺序表中逻辑上相邻的元素的物理位置 紧邻。
单链表中逻辑的元素物理位置 紧邻。
在单链表中，除了首元结点外，任一结点的存储位置 指示。
在单链表中设置头结点的作用是 。
②在什么情况下用顺序表比链表好？
①对以下单链表分别执行下列各程序段，并画出结果意图。
Q=P->
next;
L=P->
next;
R->
data=R->
data;
data=P->
next->
P->
T=P;
While（T!
=NULL）{T->
data=T->
data*2;
T=T->
} （7）T=P while（T->
next!
=NULL）{T->
} ①画出执行下列各行语句后各指针及链表的示意图。
L=（LinKList）malloc（sizeof（LNode））;
P=L;
for（i=1;
i P->
next=（LinKList）malloc（sizeof（LNode））;
P=P->
P->
data=i*2–1;
} P->
next=NULL;
for（i=4;
i>
=4;
i--;
）Ins_LinkList（L,i+1,i*2）;
for（i=1;
I a.在P结点后插入S结点的语句序列是b.在P结点前插入S结点的语句序列是c.在表首插入S结点的语句序列是d.在表首插入S结点的语句序列是
（1）P->
next=S;
（2）P->
next=P->
（3）P->
next=S->
（4）S->
（5）S->
next=L;
（6）S->
next=NULL;
（7）Q=P;
（8）while（P->
next!
=Q）P=P->
（9）while（P->
=NULL）P=P->
（10）P=Q;
（11）P=L;
（12）L=S（13）L=P;
②已知L是带头结点的非空单链表，且P结点既不是首结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列是 a.删除P结点的直接后继结点的语句序列是 b.删除P结点的直接后继结点的语句序列是 c.删除P结点的语句序列是 d.删除首元结点的语句序列是 e.删除尾元结点的语句序列是 .
（1）P=P->
mext;
（2）P->
next=P;
（3）P->
next=P;
（4）S->
（5）While（P!
（6）While（Q->
=NULL）{P=Q;
Q=Q->
}（7）While（P->
=Q）P=P->
（8）While（P->
（9）While（P->
next（10）Q=P;
（11）Q=P->
（12）P=L;
（13）L=L->
（14）free（Q）;
②已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适 的合适语序序列。
a.在P结点后插入S结点的语句序列是b.在P结点前插入S结点的语句序列是c.删除P结点的直接后继结点的语句序列是 d.删除P结点的直接前驱结点的语句序列是 e.删除P结点的语句序列是
（1）P->
priou=P->
priou->
priou;
（4）P->
priou=S;
（5）S->
（6）S->
priou=P;
（7）S->
（8）S->
priou=P->
（9）P->
（10）P->
（11）P->
next->
priou=P;
（12）P->
（13）P->
（14）P->
priou=P->
（15）Q=P->
（16）Q=P->
（17）Free（p）;
（18）Free（Q）;
②简述以下算法的功能。
StatusA（LinkedListL）{//L是无表头结点的单链表 If（L&
L->
next）{ Q=L;
L=L->
While（P->
next）P=P->
P->
next=Q;
Q->
} returnOK;
}//A
（2）VoidBB（Lnode*s,Lodes*q）{ p=s;
while（p->
=q）q=p-next;
p->
next=s;
}//BB voidAA（Lnode*pa,Lnode*pb）{ //pa和pb分别是指向单循环链表的类型定义如下：
BB（pa,pb）;
BB（pb,pa）;
}//AA 算法设计题 本章算法设计题涉及的顺序表和线性表的类型定义如下：
#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ ElemType*elem;
//存储空间基址 int length;
//当前长度 int listsize;
//当前分配的存储容量 }SqList;
//顺序表类型typedefstructLnode{ElemType data;
StructLnode*next;
}Lnode,*LinkList;
//线性链表类型 ②指出以下算法中的错误和低效之处，并将它改写成一个既正确 又高效的算法。
StatusDeleteK（SqList&
a,inti,intk）{ //本过程从顺序存储结构的线性表中a中删除第i个元素起的k个元素 if（i,1||k）returnINFEASIBLE//参数不合法else{ for（count=1;
count //删除一个元素 for（j=;
j>
=i+1;
j--）[j-1]=[j];
;
}//DeleteK ②设顺序表中的数据元素递增有序。
试写一算法，将插入到顺序表的适当 位置上，以保持该表的有序性。
③设A=B=（b1,…,bm）均为顺序表，A’和B’分别为A和B中 同前缀为，在两表中除最大共同前缀后的子表分别为A’=和B’=若A’=B’=空表，则A=B；
若A’=空表，而B’≠空表，或者两者均不为空表，且A’的首元小于B’的首元，则A＜B；
否则A＞B。
试写一个比较A，B大小的算法。
②试写一算法在带头结点的单链表结构上的实现线性表操作LOCATE。
②试写一算法在带头结点的单链表结构上的实现线性表操作LENGTH。
②已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长 度分别为m和n。
试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。
请分析你的算法的时间复杂度。
③已知指针la和lb分别指向两个无头结点单链表的首元结点。
下列算法是从 表la中删除自第i个元素起共len个元素后，，将它们插入到表lb中第i个元素之前，试问此算法是否正确？
若有错，则请改正之。
StatusDleteAndInsertSub（Linkedla,LinkedListlb,inti,intj,intlen{ If（i while（knext;
k++;
}q=p;
while（knext;
}s=lb;
k=1;
}s->
next=p;
q->
next=s->
returnOK;
}//DeleteAndInsertSub ②试写一算法，在无头结点的动态单链表上实现线性表操作INSERT， 并和在带头结点的动态单链表上实现相同操作的算法进行比较。
②同题要求，试写一算法，实现线性表操作DELETE。
③已知线性表中的元素以值递增有序排列，并以单链表作存储结构，试写出一 高效算法，删除表中所有值大于mink且小于maxk的元素，同时释放被删除结点空间，并分析你的算法的时间复杂度 ②同题条件，试写出一高效算法，删除表中所有值相同的多余元素，同时释放被删除结点空间，并分析你的算法的时间复杂度。
③试写一算法，实现顺序表的就地逆置，即利用原表中的存储空间将线性表逆置为。
③是写一算法，对单链表实现就地逆置。
③设线性表A=B=，试写一个按下列规则合并A，B为 线性表C的算法，即使得 C=当m≤n时；
或者C=当m＞n时。
线性表A，B，C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成，注意：
单链表的长度值m和n均未显示存储。
④假设有两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结 构，请编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表的结点空间构造C表。
④假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合，现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列，试对顺序表编写求C的算法。
④对题。
试对单链表编写求C的算法 ④对题的条件作以下两点修改，对顺序表重新编写求得C的算法。
假设在同一表中可能存在值相同的元素，但要求新生成的表C 中的元素值各不相同；
利用A表空间存放表C。
④对题的条件作以下两点修改，对顺序表重新编写求得C的算法。
利用原表中的结点构造C，并释放A表中的无用节点空 间。
⑤已知A，B和C为三个递增有序的线性表C，现要求对A表中作如下操作；
删 除那些既在B表中出现又在C表中出现的元素。
试对顺序表编写实现上述操作算法，并分析你的算法的时间复杂度，。
⑤要求同题，试对单链表编写算法，请释放A表中的无用结点空间。
②假设某个单向循环链表的长度大于1，且表中即无头结点也无头指针。
已知s 为指向链表中的某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱节点。
②已知有一个单向循环链表，其每一个结点中含三个域：
pre，data和next，其中 data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，
④求解平方根的迭代函数定义如下；
其中，P是A的近似平方根，e是结果误差，试写出相应的递归函数算法，并消 除递归。
⑤已知Ackerman函数定义如下：
写出递归算法；
写出非递归算法， 根据非递归算法，画出求akm时栈的变化过程。
②假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾元素结 点，试编写相应的队列初始化、入队列和出队列的算法。
②如果希望循环队列中的元素都能得到利用，则需要设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针相同时的队列状态是“空”还是“满”。
试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围。
②假设将循环队列定义为：
以域变量rear和length分别指示循环队列中对尾 元素的位置和内含元素的个数，试给出此循环队列的对满条件，并写出相应的入队列和出队列的算法。
③假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’ 是回文，‘bcde’和‘ababa’则不是回文，试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。
④试利用循环队列编写求k阶斐波那契序列中前n+1项， 的算法,要求满足:
fn≤max而fn+1>
max,其中max为某个约定的常数。
。
③在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。
设每一个原始表示一个待处理表示一个待处理的作业，元素值表示作业的预计时间。
入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于对头和对尾作业的平均时间，则插入在对头，否则插入在对尾。
③假设在教科书节中图所示，铁道转轨网的输入端有n节车厢：
硬座、硬卧、和软卧等待调度，要求这三种车厢在输出端铁道上的排队次序为：
硬座在前，软卧在中，硬卧在后。
试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：
分别以字符‘E’和‘D’表示对双端队列的头端进行入队列和出队列的操作；
以字符A表示对双端队列的尾端进行入队列的操作。
第4章串 基础知识题 ①简述空串和空格串 ②对于教科书节所述串的各个基本操作，讨论是否可其他基本操作构造 而得？
如何构造？
①设s=‘IAMASTUDENT’,t=’GOOD’,q=’WORKER’.求：
StrLength（s）,StrLength（t）,SubString（s,8,7）,SubString（t,2,1）, Index（s,’A’）,Index（s,t）,Replace（s,’STUDENT’,q）, Concat（SubString（s,6,2）,Concat（t,SubString（s,7,8）））.①已知下列字符串 a=’THIS’,f=’ASAMPLE’,c=’GOOD’,d=’NE’,b=’’, s=Concat（a,Concat（SubString（f,2,7）,Concat（b,SubString（a,3,2））））, t=Replac（f,SubString（f,3,6）,c）, u=Concat（SubString（c,3,1）,d）,g=‘IS’ v=Concat（s,Concat（b,Concat（t,Concat（b,u））））, 试问：
s,t,v,StrLength（s）,Index（v,g）,Index（u,g）各是什么？
①试问执行以下函数会产生怎样的输出结果？
Voiddemonstrate（）{ StrAssign（s,’THISISABOOK’）;
Replace（s,SubString（s,3,7）,）’ESEARE’）;
StrAssign（t,Concat（s,’S’））;
StrAssign（u,’XYXYXYXYXYXY’）;
StrAssign（v,SubSting（u,6,3））;
StrAssign（w,’W’）;
Printf（‘t=’,t,’v=’,v,’u=’,Replace（u,v,w,））;
}//demonstrate ②已知；
s=’（XYZ）+*’,t=’（X+Z）*Y’试利用联接、求子串和置换等基本运算，将s 转化为t。
②令=‘aaab’,t=’abcabaa’,u=’abcaabbabcabaacbacba’.。
试分别求出它们的next 函数值和nextrval函数值。
②已知主串s=‘ABADABBAABADABBADADA’， 模式串pat=‘ADABBADADA’， 写出模式串的nextval函数值，并此画出KMP算法匹配的全过程③在以链表存储串值时，存储密度是结点大小和串长的函数假设每个字符占一个 字节，每个指针占4个字节，每个结点的大小为4的整数倍。
已知串长的分布函数为f且，求结点大小为4k，串长为l时的存储密度d。
算法设计题 在编写至题的算法时，请采用StringType数据类型；
StringType是串的一个抽象数据类型，它包含以下五种基本操作：
VoidStrAssign //将s的值赋给t。
s的实际参数可以是串变量或者串常量。
intStringCompare（StringTypes,StringTypet） //比较s和t。
若s>
t,返回值>
0，若s=t,返回值=0；
若s 返回s中的元素个数，即该串的长度。
StringTypeConcat（StringTypes,StringTypet）//返回s和t联接而成的新串 StringTypeSubString（StringTypes,intstart,intlen） //当1≤start≤StrLength（s）且0≤len≤StrLength（s）-start+1时//返回s中第start个字符起长度为len的子串，否则返回空串。
③编写对串求逆的递推算法。
③编写算法，求得所有包含在串s中而不包含在串t中的字符构成的新串r，以及r中每个字符在s中第一次出现的位置。
③编写一个实现串的置换操作Replace的算法。
③编写算法，从串s中删除所有和串t相同的子串。
④利用串的基本操作以及栈和集合的基本操作，编写“一个算术表达式的前缀 式求后缀式”的递推算法。
在编写至题的算法时，请采用教科书节中所定义的
升级会员 