《数据结构》各章课后作业.doc

《《数据结构》各章课后作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、这个是数据结构课后习题，大家用笔抄在本子上做，下周交，和实验报告，一起交，请转发给不在群里的你的室友，谢谢！《数据结构》各章课后作业第一章课后作业1.简述线性结构与非线性结构的不同点。2．分析下面各程序段的时间复杂度（每小题5分，共20分）（2）s=0;for（i=0;i

2、or(j=1;j<=n-i;j++)x++;第二章课后作业1.填空题。（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与表长和该元素在表中的位置。（2）线性表中结点的集合是有限的，结点间的关系是一对一的。（3）向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。（4）顺序表中逻辑上相邻的元素的物理位置。单链表中逻辑上相邻的元素的物理位置相邻。2.试写一算法，对单链表实现就地逆置。第三章课后作业1、填空题。（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端

3、称为。（2）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。（3）在具有n个单元的循环队列中，队满时共有个元素。2．计算题。设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？3.写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’

4、a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}第四章课后作业1．算法填空题。本算法是在S中找子串t。若找到。则返回子串t第一次出现在主串s中的位置，否则返回-1。intindex(chars[],chart[]){inti=0,j=0;while(①){if(s[i+j]==t[j])j++;else{②;③;}}if(④)retruni;elseretur

5、n–1;}2．写出子串t=”ABCABCACAB”的next值和nextval值。解：j12345678910模式串ABCABCACABnext[j]nextval[j]第五章课后作业1、选择题。（1）设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。（2）一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是个字节。（3）三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三

6、个数据项，分别表示该元素的、和。（4）求下列广义表操作的结果：①GetHead【((a,b),(c,d))】=;②GetHead【GetTail【((a,b),(c,d))】】=;③GetHead【GetTail【GetHead【((a,b),(c,d))】】】=;④GetTail【GetHead【GetTail【((a,b),(c,d))】】】=;2、递归算法比非递归算法花费更多的时间，对吗？为什么？第六章课后作业1、填空题。（1）一棵完全二叉树有1000个结点，则它必有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子

7、树。（2）用二叉链表存储n个结点的二叉树(n>0)，共有_个空指针域；采用三叉链表存储，共有个空指针域。（3）由3个结点所构成的二叉树有种形态。2、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。3、编写递归算法，计算二叉树中叶子结点的数目。第七章课后作业1、填空题。（1）图有、等存储结构，遍历图有、等方法。（2）有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。（3）如果n个顶点的图是一个环，则它有棵生成树。（4）图的逆邻接表存储结构只适用于图。（5）用Dijkstra算法求某一顶点到其余

8、各顶点间的最短路径是按路径长度的次序来得到最短路径的。（6）拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。2、求解下图的最小生