2、作业1.填空题。（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与表长和该元素在表中的位置。（2）线性表中结点的集合是的，结点间的关系是的。（3）向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。（4）顺序表中逻辑上相邻的元素的物理位置。单链表中逻辑上相邻的元素的物理位置相邻。2.试写一算法，对单链表实现就地逆置。第三章栈和队列课后作业1、填空题。（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。（2）
3、是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。（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’;Pu
4、sh(S,x);Push(S,’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．简述空串和空格串（或称空格符串）的区别。2．已知下列字符串a='THIS’,f='ASAMPLE’,c='GOOD’,d='NE’,b='',s=Concat(a,Concat(SubString(f,2,7),Con
5、cat(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)各是什么？第五章数组和广义表课后作业1、选择题。（1）设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储
6、，则元素a[32,58]的存储地址为8950。（2）一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是288个字节。（3）三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。（4）求下列广义表操作的结果：①GetHead【((a,b),(c,d))】=（a,b）;②GetHead【GetTail【((a,b),(c,d))】】=(c,d);③GetHead【Ge
7、tTail【GetHead【((a,b),(c,d))】】】=b;④GetTail【GetHead【GetTail【((a,b),(c,d))】】】=(d);2、递归算法比非递归算法花费更多的时间，对吗？为什么？不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已第六章树和二叉树课后作业1、填空题。（1）一棵完全二叉树有
8、1000个结点，则它必有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。（2）用二叉链表存储n个结点的二叉树(n>0)，共有n+1_个空指针域；采用三叉链表存储，共有n+2个空指针域。（3）由3个结点所构成的二叉树有5种形态。2、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。.层序序列为ABCDEFGHIJ可得出根结点为A,由中序序列为DBGEHJA
