【数据结构】习题集

《【数据结构】习题集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》习题集第一章序论思考题：1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型作业题：1.2设有数据结构（D，R），其中D={d1,d2,d3,d4}R={r1,r2}r1={,,,,,}r2={(d1,d2),(d1,d3),(d1,d4),(d2,d4),(d2,d3)}试绘出其逻辑结构示意图。1.3设n是正整数。试写出下列程序段中用记号“△”标注的语句的频度：(1)i=1;k=0;while(i<=n-1){△k+=10*i;i++;}(2)i=1;k=0

2、;do{△k+=10*i;i++;}while(i<=n-1)(3)i=1;k=0;do{△k+=10*i;i++;}while(i==n);(4)i=1;j=0;while(i+j≤n){△if(i=(y+1)*(y+1)){△y++;}(6)x=91;y=100;while(y>0){△if(x>100){x-=10;y--;}elsex++;}(7)for(i=0;i

3、输出顺序读入的三个整数X,Y和Z的值。1.5已知k阶斐波那契序列的定义为：f0=0,f1=0,……,fk-2=0,fk-1=1；fn=fn-1+fn-2+……+fn-k,n=k,k+1,……试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。第二章线性表思考题：2.1描述以下三个概念的区别：头指针、头结点、首元结点。2.2描述以下几个概念：顺序存储结构、链式存储结构、顺序表、有序表。作业题：2.3已知顺序表La中数据元素按非递减有序排列。试写一个算法，将元素x插到La的合适位置上，保持该表的有序性。2.4已知单链表La中数据元素按非递减有序排列。按两种不

4、同情况，分别写出算法，将元素x插到La的合适位置上，保持该表的有序性：（1）La带头结点；（2）La不带头结点。2.5试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a1,a2,...,an-1,an）逆置为(an,an-1,...,a2,a1)2.6试写一个算法，对带头结点的单链表实现就地逆置。第14页2.7已知线性表L采用顺序存储结构存放。对两种不同情况分别写出算法，删除L中值相同的多余元素，使得L中没有重复元素：(1)L中数据元素无序排列；(2)L中数据元素非递减有序排列。2.8将2.7题中L的存储结构改为单链表，写出相应的实现算法。2.9设有两个非递减有序的单链表A

5、和B。请写出算法，将A和B“就地”归并成一个按元素值非递增有序的单链表C。2.10设有一个长度大于1的单向循环链表，表中既无头结点，也无头指针，s为指向表中某个结点的指针,如图2-1所示。试编写一个算法，删除链表中指针s所指结点的直接前驱。s待删结点图2-12.11已知线性表用带头结点的单链表表示，表中结点由三类字符组成：字母、数字和其他字符。试编写算法，将该线性链表分割成三个循环单链表，每个循环单链表中均只含有一类字符。2.12已知线性表用顺序存储结构表示，表中数据元素为n个正整数。试写一算法，分离该表中的奇数和偶数，使得所有奇数集中放在左侧，偶数集中放在右侧。要求：(1)不借助辅助数组

6、;(2)时间复杂度为O(n)。2.13设以带头结点的双向循环链表表示的线性表L=(a1,a2,a3,...,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。第三章栈和队列思考题：3.1简述栈和线性表的差别。3.2如果进栈序列为A、B、C、D，写出所有可能的出栈序列。第14页3.3简述栈和队列的相同点和差异。3.4已知栈S中存放了8个数据元素，自栈底至栈顶依次为(1,2,3,4,5,6,7,8)。（1）写出在执行了函数调用algo1(S)后，S中的元素序列。（2）在（1）的基础上，又执行了函数调用algo2(S,5)，写出此时S中的元

7、素序列。voidalgo1(Stack&S){inta[10],i,n=0;while(!StackEmpty(S)){n++;Pop(S,a[n]);}for(i=1;i<=n;i++)Push(S,a[i]);}voidalgo2(Stack&S,inte){StackT;intd;InitStack(T);while(!EmptyStack(S)){Pop(S,d);if(d!=e)Push(T,d);}while