一、单项选择题列出的四个选项中只有一个选项是符合题目要求的2. 对于shell排序来说，给定的一组排序数值为
49,38,65,97,13,27,49,55,04
则第二趟排序后的结果为
- A.04,13,27,49,49,38,55,65,76,97
- B.04,13,27,38,49,49,55,65,76,97
- C.13,04,49,38,27,49,55,65,97,76
- D.13,27,49,55,04,49,38,65,97,76
A B C D
12. 下面的程序在执行时，S语句共被执行了
次。
i=1;
while(i＜=n)
{for(j=i;j＜n;j++)
{ S ;
}
i=i+1;
}
A B C D
二、填空题1. ______的有向图，其全部顶点有可能排成一个拓扑序列。
2. 朴素的串匹配算法的特点是简单，但是其效率较低，其时间匹配算法的最坏时间是______(假设模式串的长度是m，目标串的长度是n)。
3. 任何连通图的连通分量只有一个，即______。
4. 设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找与k相等的元素，若查找成功，则至少需要比较______次，至多需比较______次。
5. 在非空队列中，头指针始终指向______，而尾指针始终指向______。
6. 数组的长度是______，线性表的长度是______。
7. 如果一个图中有n条边，则此图的生成树含有______条边，所以生成树是图的边数______的连通图。
8. 设二维数组A[10··20,5··10]按行优先存储·，每个元素占4个存储单元，A[10,5]的存储地址是1000，则A[15,10]的存储地址是______。
9. 顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类：即______和______。
10. 在线性表的顺序存储中，元素之间的逻辑关系是通过______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过______决定的。
三、解答题1. 试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同的形态。
含有三个结点的树只有两种形式[见(1)和(2)]；含有3个结点的二叉树有5种形态[见(3)，(4)，(5)，(6)，(7)]
对于一棵普通的树来说，图(4)，(5)，(6)，(7)是完全相同的，但如果它们作为二叉树，则表示不同的二叉树，因为在一棵二叉树中，每个结点的孩子都有左右之分，即使某节含有一个孩子，则此孩子结点仍有左右点之分。
2. 已知串S=‘(xyz)
*’，t=‘(x+z)*y’，试利用串的基本运算将s串转化为t串，t串转化为s串。
t=CONCAT(Rep(sup(s,1,5),‘y’,‘+’),Rep(sub(s,6,1),‘*’,‘*y’))
s=CONCAT(Rep(sub(t,1,5),‘+’,‘y’)，Rep(sub(t,6,2),‘*y’,‘*’))
A=(n,an,an-1，…，a1，a0)
A=(m，1m-1，bm-1，1m-2，bm-2，…，10，b0)
其中：m为非零项的个数，1i，bi分别为非零项的指数和系数。试分析：3. 两种表示方法对存储空间的需要情况；
第一种表示需要n+2个实数存储单元，其中n为多项式的最高幂数；第二种表示需要2m+1个实数存储单元，其中m为非零系数的个数。显然，当非零系数较少时
，第二种表示法需要较少的存储空间。
4. 进行多项式相加，采用哪一种表示方法处理较为简单?
采用每种表示法处理多项式相加比较简单，只需将次数较低的多项式的各项的系数加到次数较高的多项式的相应项的系数上去即可。而第二种方法要查找到相同的指数才能将系数相加，相加之和可能为0，这就要修改项数m；另外当某个多项式中有的项而在另一个多项式中没有，显然其和也应作相应的修改。
5. 假设有一个容量为5的队列，假设其初始状态为front=rear=0，则对此队列进行下列操作之后，请画出此时的头、尾指针的变化情况和相应的队列内元素的存储情况。
(1)队列为空(即没有任何元素进入)；
(2)A，B，C入队；
(3)A出队；
(4)B，C出队，此时队列为空。
四、算法阅读题1. 以下运算实现在循环队上的入队列，请在______处用适当的语句予以填充。
int EnCycQueue(CycquetaeTp*sq,DataType x)
{ if((sq—＞rear+1)%maxsize==______)
{error("队满");return(0);)
else{______;
______;
return(1);
}
}
sq—＞front sq—＞rear=(sq—＞rear+1)%maxsize sq—＞data[sq—＞rear]=x
2. 以下程序段采用先根遍历方法求二叉树的叶子数，请在______处填充适当的语句。
void countleaf(bitreptr t,int*count)/*根指针为t，假定叶子数count的初值为0*/
{ if(t!=NULL)
{ if((t—＞lchild==NULL)&&(t—＞rchild==NULL))______;
countleaf(1—＞lehild,count);
______;
}
}
*count++ eountleaf(1—＞rehild,count)
3. 以下为冒泡排序的算法。请分析算法，并在______处用适当的语句予以填充。
void bubblesort(int n,list r) /*fiag为特征位，定义为布尔型*/
{ for(i=1;i＜=______，i++)
{______;
for(j=1;j＜=______;j++)
if(r[j+1].key＜r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=P;}
if(flag)return;
}
}
4. 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的三元组a.data的次序进行转置(快速转置)，请在______处用适当的语句予以填充。
Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b)
{ (*b)．mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;
if(a.tu)
{ for(col)=1;______col++)unm[col]=0
for(t=1;t＜=a.tu;t++)num[a.data[t].j]++;
cpot[1]=1;
for(col=2;col＜=a.nu;col++)cpot[col]=______;
for(p=1;p＜=a.tu;p++)
{ col=a.data[p].j;
q=cpot[col];
(*b).data[q].i=a．data[p].j;
(*b).data[q].j=a.data[p].i;
(*b).data[q].v=a.data[p].v;
______;
}
}
}
col—＞=a.nu cpot[col-1]+num[col-1] cpot[col]++
五、算法设计题1. 假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。
要解答该题必须分析结点所在的状态，这可以通过结点的标志域来进行。对一个结点来说，当前的结点可能由：(1)其双亲结点转换；(2)其左子树遍历结束转换；(3)其右子树遍历结束转换。所以算法主要执行按这三种状态进行处理或处理当前结点切换结点的状态。从而可将算法描述为：
void postorder(r)/*后序遍历此二叉树*/
bitree*t/*设为bitree类型的结点含四个域：flag，parent，lchild，rehild，其中flag的域初值为0，指针t指向根结点*/
{ bitree * P;
P=t;
while(p!=Null)
switch(—＞flag)
{ case 0:p—＞flag=1;
if(p—＞lchild!=Null)
p=p—＞lehild;
break;
case 1:p—＞flag=2
if(jp—＞rchild!=Null)
p=p—＞rchild;
break;
case 2:p—＞flag=0;
printf(p—＞data);
p=jp—＞parent;
break;
default;
}
} /*postorder*/
深色：已答题 浅色：未答题