(0012)《数据结构》复习思考题

本文格式为Word版，下载可任意编辑——(0012)《数据结构》复习思考题

（0012）《数据结构》复习思考题

一、常用的存储表示方法有哪几种?

二、以下程序段带标号语句的频度和时间繁杂度。

(1)I=0;

while(In)(a[I]!=k)

I++;//语句3

return(I);

(2)n为不小于1的整数（设k的初值等于1）

voidpp(intk)

{

if(k==n)//语句1

for(I=0;In;I++)//语句2

printf(a[I]);//语句3

else

{for(I=k-1;In;I++)//语句4

a[I]=a[I]+I;//语句5

pp(k+1);//语句6

}

}//pp

三、算法的时间繁杂度仅与问题的规模相关吗?

四、常用的存储表示方法有哪几种?

五、确定以下算法中输出语句的执行次数，并给出算法的时间繁杂度。

（1）voidcombi(intn)

{intI,j,k;

for(I=1;I=n;I++)

for(j=I+1;j=n;j++)

for(k=j+1;k=n;k++)

coutI,j,k;}

(2)voidbinary(intn)

{while(n){

coutn;

n=n/2;

}}

六、为什么在单循环链表中设置尾指针比设置头指针更好?

七、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

八、指出以下算法中的错误和低效之处，并把它改写为一个既正确又高效的算法。

StatusDeleteK(SqLista,intI,intk){//本过程从顺序存储结构的线性表a中删除第I个元素起的k个元素。

if(I1||k0||I+ka.length)returnERROR;

else{

for(count=1;countk;count++){//删除一个元素

for(j=a.Length;j=I+1;j--)a.elem[j-1]=a.elem[j];

a.length--;

}

rreturnOK;

}//DeleteK

九、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点指针，试编写算法在链表中删除指针s所指结点的前驱结点。

十、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点指针，试编写算法在链表中删除指针s所指结点的前驱结点。

十一、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间繁杂度

十二、已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min和max是两个给定的参数。请分析你的算法的时间繁杂度。

十三、若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：

（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；

（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；

（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。

十四、设两个栈共享空间v[0..m-1]，两栈的栈底分别设在向量的两端，且每个元素占一个分量。试设计这两个栈的插入和删除算法。

十五、

简述以下算法的功能。

(1)voidDemo1(SeqStack*S){

intI;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(I=0,In;I++)Push(S,arr[I]);

}//Demo1

(2)SeqStackS1,S2,tmp;

DataTypex;

…//假设栈tmp和S2已做过初始化

while(!StackEmpty(S1)){

x=Pop(S1);

Push(tmp,x);

}

while(!StackEmpty(tmp)){

x=Pop(tmp);

Push(S1,x);

Push(S2,x);

(3)voidDemo2(SeqStack*S,intm){

//设DataType为int型

SeqStackT;intI;

InitStack(T);

while(!StackEmpty(S))

if((I=Pop(S))!=m)Push(T,I);

while(!StackEmpty(T)){

I=Pop(T);Push(S,I);

}}

(4)voidDemo3(CirQueue*Q){

//设DataType为int型

intx;SeqStackS;

InitStack(S);

while(!QueueEmpty(Q))

{x=DeQueue(Q);Push(S,x);}

while(!StackEmpty(s))

{x=Pop(S);EnQueue(Q,x);}

}//Demo3

(5)CirQueueQ1,Q2;//设DataType为int型

intx,I,m=0;

…//设Q1已有内容，Q2已初始化过

while(!QueueEmpty(Q1))

{x=DeQueue(Q1);EnQueue(Q2,x);m++;}

for(I=0;In;I++)

{x=DeQueue(Q2);EnQueue(Q1,x);EnQueue(Q2,x);}

十六、写一算法voidStrReplace(char*T,char*P,char*S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。

十七、设有三对角矩阵An*n，将其三条对角线上的元素逐行地存储到向量B[0…3n-3]中，使得B[k]=aij,求：(1)用I,j表示k的下标变换公式。(2)用k表示I,j的下标变换公式。

十八、假设在二叉链表中增加两个域：双亲域（parent)以指示其双亲结点；标志域（mark取值0..2）以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

十九、分别写出下图所示各二叉树的前序、中序和后序序列。

二十、一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。假使按层次顺序(同层自左至右)从1开始对全部结点编号，问：

(1)各层的结点数目是多少?(2)编号为I的结点的双亲结点(若存在)的编号是多少?(3)编号为I的结点的第j个孩子结点(若存在)的编号是多少?(4)编号为I的结点的有右兄弟的条件是什么?其右兄弟的编号是多少?

二十一、编写算法完成以下操作：无重复地输出以孩子兄弟链表存储的树T中所有的边。输出形式为（k1,k2)…(ki,kj)…,其中ki,kj树结点中结点的标识。(提醒：修改二叉树遍历的递归算法，使其参数表增加参数father,指向被访问的当前结点的双亲结点。)

二十二、已知以二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

二十三、

在图所示的各无向图中：

(1)找出所有的简单环。

(2)哪些图是连通图?对非连通图给出其连通分量。

(3)哪些图是自由树(或森林)?

二十四、对下图所示的AOE-网，计算各活动弧的e(ai)和l(aj)函数值、各事件（顶点）的ve(vi)和vl(vj)函数值；列出各

条关键路径。

二十五、采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。

二十六、某校学生学号由8位十进制数字组成：c1c2c3c4c5c6c7c8。C1c2为入学时年份的后两砬；c3c4为系别：00～24分别代表该校的25个系：c5为0或1，0表示本科生，1表示研究生；C6c7c8为对某级某系某类学生的顺序编号，对于本科生，它不超过199，对于研究生，它不超过049，共有4个年级，四年级学生1996年入学。

（1）当在校生人数达极限状况时，将他们的学号散列到0～24999的地址空间，问装载因子是多少?

（2）求一个无冲突的哈希函数H1，它将在校生学号散列到0～24999的地址空间其簇聚性如何?

（3）设在校生总数为15000人，散列地址空间为0～19999，你是否能找到一个(2)中要求的H1？若不能，试设计一个哈希函数H2及其解决冲突的方法，使得多数学号可只经一次散列得到（可设各系各年级本科生平均人数为130，研究生平均人数为20）。

（4）用算法描述语言表达H2,并写出相应的查找函数。

二十七、

在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、5、1，29，请画出所得到的二叉查找树。

二十八、

画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数

二十九、以关键字序列(