当前位置:文档之家› 数据结构考前复习(2015-2016)

数据结构考前复习(2015-2016)

数据结构考前复习(2015-2016)
数据结构考前复习(2015-2016)

数据结构(2015-2016)

第1章绪论

1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案:

数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况下,数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。

数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象:是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。

数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。

逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构:数据对象在计算机中的存储表示,也称为物理结构。

抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案:

例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构,即线性结构。

这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用指针进行链接,则称为链式存储结构。

即相同的逻辑结构,可以对应不同的存储结构。

3.简述逻辑结构的四种基本关系并画出它们的关系图。

答案:

(1)集合结构

数据元素之间除了“属于同一集合”的关系外,别无其他关系。例如,确定一名学生是否为班级成员,只需将班级看做一个集合结构。

(2)线性结构

数据元素之间存在一对一的关系。例如,将学生信息数据按照其入学报到的时间先后顺序进行排列,将组成一个线性结构。

(3)树结构

数据元素之间存在一对多的关系。例如,在班级的管理体系中,班长管理多个组长,每位组长管理多名组员,从而构成树形结构。

(4)图结构或网状结构

数据元素之间存在多对多的关系。例如,多位同学之间的朋友关系,任何两位同学都可以是朋友,从而构成图形结构或网状结构。

其中树结构和图结构都属于非线性结构。

四类基本逻辑结构关系图

4.存储结构由哪两种基本的存储方法实现?

答案:

(1)顺序存储结构

顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系,通常借助程序设计语言的数组类型来描述。

(2)链式存储结构

顺序存储结构要求所有的元素依次存放在一片连续的存储空间中,而链式存储结构,无需占用一整块存储空间。但为了表示结点之间的关系,需要给每个结点附加指针字段,用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。

5.选择题

(1)在数据结构中,从逻辑上可以把数据结构分成()。

A.动态结构和静态结构 B.紧凑结构和非紧凑结构

C.线性结构和非线性结构 D.内部结构和外部结构

答案:C

(2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。

A.存储结构 B.存储实现

C.逻辑结构 D.运算实现

答案:C

(3)通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着()。

A.数据具有同一特点

B.不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致

C.每个数据元素都一样

D.数据元素所包含的数据项的个数要相等

答案:B

(4)以下说法正确的是()。

A.数据元素是数据的最小单位

B.数据项是数据的基本单位

C.数据结构是带有结构的各数据项的集合

D.一些表面上很不相同的数据可以有相同的逻辑结构

答案:D

解释:数据元素是数据的基本单位,数据项是数据的最小单位,数据结构是带有结构的各数据元素的集合。

(5)算法的时间复杂度取决于()。

A.问题的规模B.待处理数据的初态

C.计算机的配置D.A和B

答案:D

解释:算法的时间复杂度不仅与问题的规模有关,还与问题的其他因素有关。如某些排序的算法,其执行时间与待排序记录的初始状态有关。为此,有时会对算法有最好、最坏以及平均时间复杂度的评价。

(6)以下数据结构中,()是非线性数据结构

A.树 B.字符串 C.队列 D.栈

答案:A

6.试分析下面各程序段的时间复杂度。

(1)x=90; y=100;

while(y>0)

if(x>100)

{x=x-10;y--;}

else x++;

答案:O(1)

解释:程序的执行次数为常数阶。

(2)for (i=0; i

for (j=0; j

a[i][j]=0;

答案:O(m*n)

解释:语句a[i][j]=0;的执行次数为m*n。

(3)s=0;

for i=0; i

for(j=0; j

s+=B[i][j];

sum=s;

答案:O(n2)

解释:语句s+=B[i][j];的执行次数为n2。

(4)i=1;

while(i<=n)

i=i*3;

答案:O(log3n)

解释:语句i=i*3;的执行次数为?log3n?。

(5)x=0;

for(i=1; i

for (j=1; j<=n-i; j++)

x++;

答案:O(n2)

解释:语句x++;的执行次数为n-1+n-2+……+1= n(n-1)/2。(6)x=n; //n>1

y=0;

while(x≥(y+1)* (y+1))

y++;

答案:O(n)

解释:语句y++;的执行次数为?n?。

第2章线性表

1.选择题

(1)顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()。

A.110 B.108 C.100 D.120

答案:B

解释:顺序表中的数据连续存储,所以第5个元素的地址为:100+2*4=108。

(2)在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是()。

A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)

B.在第i个结点后插入一个新结点(1≤i≤n)

C.删除第i个结点(1≤i≤n)

D.将n个结点从小到大排序

答案:A

解释:在顺序表中插入一个结点的时间复杂度都是O(n2),排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构,访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位,时间复杂度是O(1)。

(3)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动的元素个数为()。

A.8 B.63.5 C.63 D.7

答案:B

解释:平均要移动的元素个数为:n/2。

(4)链接存储的存储结构所占存储空间()。

A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针

B.只有一部分,存放结点值

C.只有一部分,存储表示结点间关系的指针

D.分两部分,一部分存放结点值,另一部分存放结点所占单元数

答案:A

(5)线性表若采用链式存储结构时,要求内存中可用存储单元的地址()。

A.必须是连续的B.部分地址必须是连续的

C.一定是不连续的D.连续或不连续都可以

答案:D

(6)线性表L在()情况下适用于使用链式结构实现。

A.需经常修改L中的结点值B.需不断对L进行删除插入

C.L中含有大量的结点D.L中结点结构复杂

答案:B

解释:链表最大的优点在于插入和删除时不需要移动数据,直接修改指针即可。

(7)单链表的存储密度()。

A.大于1 B.等于1 C.小于1 D.不能确定

答案:C

解释:存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比,假设单链表一个结点本身所占的空间为D,指针域所占的空间为N,则存储密度为:

D/(D+N),一定小于1。

(8)将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是()。

A.n B.2n-1 C.2n D.n-1

答案:A

解释:当第一个有序表中所有的元素都小于(或大于)第二个表中的元素,只需要用第二个表中的第一个元素依次与第一个表的元素比较,总计比较n次。

(9)在一个长度为n的顺序表中,在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动()个元素。

A.n-i B.n-i+1 C.n-i-1 D.I

答案:B

(10) 线性表L=(a1,a2,……a n),下列说法正确的是()。

A.每个元素都有一个直接前驱和一个直接后继

B.线性表中至少有一个元素

C.表中诸元素的排列必须是由小到大或由大到小

D.除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。

答案:D

(11) 创建一个包括n个结点的有序单链表的时间复杂度是()。

A.O(1) B.O(n) C.O(n2) D.O(nlog2n)

答案:C

解释:单链表创建的时间复杂度是O(n),而要建立一个有序的单链表,则每生成一个新结点时需要和已有的结点进行比较,确定合适的插入位置,所以时间复杂度是O(n2)。

(12) 以下说法错误的是()。

A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B.顺序存储的线性表可以随机存取

C.由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活

D.线性表的链式存储结构优于顺序存储结构

答案:D

解释:链式存储结构和顺序存储结构各有优缺点,有不同的适用场合。

(13) 在单链表中,要将s所指结点插入到p所指结点之后,其语句应为()。

A.s->next=p+1; p->next=s;

B.(*p).next=s; (*s).next=(*p).next;

C.s->next=p->next; p->next=s->next;

D.s->next=p->next; p->next=s;

答案:D

(14) 在双向链表存储结构中,删除p所指的结点时须修改指针()。

A.p->next->prior=p->prior; p->prior->next=p->next;

B.p->next=p->next->next; p->next->prior=p;

C.p->prior->next=p; p->prior=p->prior->prior;

D.p->prior=p->next->next; p->next=p->prior->prior;

答案:A

(15) 在双向循环链表中,在p指针所指的结点后插入q所指向的新结点,其修改指针的操作是()。

A.p->next=q; q->prior=p; p->next->prior=q; q->next=q;

B.p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

C.q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D.q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

答案:C

2.算法设计题

(1)将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。

[题目分析]

合并后的新表使用头指针Lc指向,pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等,只摘取La 表中的元素,删除Lb表中的元素,这样确保合并后表中无重复的元素。当一个表到达表尾结点,为空时,将非空表的剩余元素直接链接在Lc表的最后。

[算法描述]

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

{//合并链表La和Lb,合并后的新表使用头指针Lc指向

pa=La->next; pb=Lb->next;

//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

Lc=pc=La; //用La的头结点作为Lc的头结点

while(pa && pb)

{if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;}

//取较小者La中的元素,将pa链接在pc的后面,pa指针后移

else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}

//取较小者Lb中的元素,将pb链接在pc的后面,pb指针后移

else //相等时取La中的元素,删除Lb中的元素

{pc->next=pa;pc=pa;pa=pa->next;

q=pb->next;delete pb ;pb =q;

}

}

pc->next=pa?pa:pb; //插入剩余段

delete Lb; //释放Lb的头结点

}

(2)将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

[题目分析]

合并后的新表使用头指针Lc指向,pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,依次摘取其中较小者重新链接在Lc表的表头结点之后,如果两个表中的元素相等,只摘取La表中的元素,保留Lb表中的元素。当一个表到达表尾结点,为空时,将非空表的剩余元素依次摘取,链接在Lc表的表头结点之后。

[算法描述]

void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, )

{//合并链表La和Lb,合并后的新表使用头指针Lc指向

pa=La->next; pb=Lb->next;

//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

Lc=pc=La; //用La的头结点作为Lc的头结点

Lc->next=NULL;

while(pa||pb )

{//只要存在一个非空表,用q指向待摘取的元素

if(!pa) {q=pb; pb=pb->next;}

//La表为空,用q指向pb,pb指针后移

else if(!pb) {q=pa; pa=pa->next;}

//Lb表为空,用q指向pa,pa指针后移

else if(pa->data<=pb->data) {q=pa; pa=pa->next;}

//取较小者(包括相等)La中的元素,用q指向pa,pa指针后移

else {q=pb; pb=pb->next;}

//取较小者Lb中的元素,用q指向pb,pb指针后移

q->next = Lc->next; Lc->next = q;

//将q指向的结点插在Lc 表的表头结点之后

}

delete Lb; //释放Lb的头结点

}

(3)已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出A与B的交集,并存放于A链表中。

[题目分析]

只有同时出现在两集合中的元素才出现在结果表中,合并后的新表使用头指针Lc指向。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,如果两个表中相等的元素时,摘取La表中的元素,删除Lb表中的元素;如果其中一个表中的元素较小时,删除此表中较小的元素,此表的工作指针后移。当链表La和Lb有一个到达表尾结点,为空时,依次删除另一个非空表中的所有元素。

[算法描述]

void Mix(LinkList& La, LinkList& Lb, LinkList& Lc)

{ pa=La->next;pb=Lb->next;

pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

Lc=pc=La; //用La的头结点作为Lc的头结点

while(pa&&pb)

{ if(pa->data==pb->data)∥交集并入结果表中。

{ pc->next=pa;pc=pa;pa=pa->next;

u=pb;pb=pb->next; delete u;}

else if(pa->datadata) {u=pa;pa=pa->next; delete u;}

else {u=pb; pb=pb->next; delete u;}

}

while(pa) {u=pa; pa=pa->next; delete u;}∥ 释放结点空间

while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间

pc->next=null;∥置链表尾标记。

delete Lb; //释放Lb的头结点

}

(4)已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。

[题目分析]

求两个集合A和B的差集是指在A中删除A和B中共有的元素,即删除链表中的相应结点,所以要保存待删除结点的前驱,使用指针pre指向前驱结点。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,如果La表中的元素小于Lb表中的元素,pre置为La表的工作指针pa删除Lb表中的元素;如果其中一个表中的元素较小时,删除此表中较小的元素,此表的工作指针后移。当链表La和Lb有一个为空时,依次删除另一个非空表中的所有元素。

[算法描述]

void Difference(LinkList& La, LinkList& Lb,int *n)

{∥差集的结果存储于单链表La中,*n是结果集合中元素个数,调用时为0

pa=La->next; pb=Lb->next;

∥pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

pre=La; ∥pre为La中pa所指结点的前驱结点的指针

while(pa&&pb)

{if(pa->datadata){pre=pa;pa=pa->next;*n++;}

∥ A链表中当前结点指针后移

else if(pa->data>q->data)q=q->next; ∥B链表中当前结点指针后移 else {pre->next=pa->next; ∥处理A,B中元素值相同的结点,应删除

u=pa; pa=pa->next; delete u;} ∥删除结点

}

}

(5)设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A中的元素为非零整数,要求B、C表利用A表的结点)。

[题目分析]

B表的头结点使用原来A表的头结点,为C表新申请一个头结点。从A表的第一个结点开始,依次取其每个结点p,判断结点p的值是否小于0,利用前插法,将小于0的结点插入B表,大于等于0的结点插入C表。

[算法描述]

void DisCompose(LinkedList A)

{ B=A;

B->next= NULL; ∥B表初始化

C=new LNode;∥为C申请结点空间

C->next=NULL; ∥C初始化为空表

p=A->next; ∥p为工作指针

while(p!= NULL)

{ r=p->next; ∥暂存p的后继

if(p->data<0)

{p->next=B->next; B->next=p; }∥将小于0的结点链入B表,前插法

else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表,前插法

p=r;∥p指向新的待处理结点。

}

}

(6)设计一个算法,通过一趟遍历在单链表中确定值最大的结点。

[题目分析]

假定第一个结点中数据具有最大值,依次与下一个元素比较,若其小于下一个元素,则设其下一个元素为最大值,反复进行比较,直到遍历完该链表。

[算法描述]

ElemType Max (LinkList L ){

if(L->next==NULL) return NULL;

pmax=L->next; //假定第一个结点中数据具有最大值

p=L->next->next;

while(p != NULL ){//如果下一个结点存在

if(p->data > pmax->data) pmax=p;//如果p的值大于pmax的值,则重新赋值

p=p->next;//遍历链表

}

return pmax->data;

(7)设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。

[题目分析]

从首元结点开始,逐个地把链表L的当前结点p插入新的链表头部。

[算法描述]

void inverse(LinkList &L)

{// 逆置带头结点的单链表 L

p=L->next; L->next=NULL;

while ( p) {

q=p->next; // q指向*p的后继

p->next=L->next;

L->next=p; // *p插入在头结点之后

p = q;

}

}

(8)设计一个算法,删除递增有序链表中值大于mink且小于maxk的所有元素(mink 和maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)。

[题目分析]

分别查找第一个值>mink的结点和第一个值≥maxk的结点,再修改指针,删除值大于mink且小于maxk的所有元素。

[算法描述]

void delete(LinkList &L, int mink, int maxk) {

p=L->next; //首元结点

while (p && p->data<=mink)

{ pre=p; p=p->next; } //查找第一个值>mink的结点

if (p)

{while (p && p->datanext;

// 查找第一个值≥maxk的结点

q=pre->next; pre->next=p; // 修改指针

while (q!=p)

{ s=q->next; delete q; q=s; } // 释放结点空间

}//if

}

(9)已知p指向双向循环链表中的一个结点,其结点结构为data、prior、next三个域,写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。

[题目分析]

知道双向循环链表中的一个结点,与前驱交换涉及到四个结点(p结点,前驱结点,前驱的前驱结点,后继结点)六条链。

[算法描述]

void Exchange(LinkedList p)

∥p是双向循环链表中的一个结点,本算法将p所指结点与其前驱结点交换。

{q=p->llink;

q->llink->rlink=p;∥p的前驱的前驱之后继为p

p->llink=q->llink;∥p的前驱指向其前驱的前驱。

q->rlink=p->rlink;∥p的前驱的后继为p的后继。

q->llink=p;∥p与其前驱交换

p->rlink->llink=q;∥p的后继的前驱指向原p的前驱

p->rlink=q;∥p的后继指向其原来的前驱

}∥算法exchange结束。

(10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。

[题目分析]

在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动(删第i个元素,第i+1至第n个元素要依次前移)。本题要求删除线性表中所有值为item的数据元素,并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(i=1,j=n),从两端向中间移动,凡遇到值item的数据元素时,直接将右端元素左移至值为item的数据元素位置。

[算法描述]

void Delete(ElemType A[ ],int n)

∥A是有n个元素的一维数组,本算法删除A中所有值为item的元素。

{i=1;j=n;∥设置数组低、高端指针(下标)。

while(i

{while(i

if(i

第3章栈和队列

1.选择题

(1)若让元素1,2,3,4,5依次进栈,则出栈次序不可能出现在()种情况。

A.5,4,3,2,1 B.2,1,5,4,3 C.4,3,1,2,5 D.2,3,5,4,1

答案:C

解释:栈是后进先出的线性表,不难发现C选项中元素1比元素2先出栈,违背了栈的后进先出原则,所以不可能出现C选项所示的情况。

(2)若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为()。

A.i B.n-i C.n-i+1 D.不确定

答案:C

解释:栈是后进先出的线性表,一个栈的入栈序列是1,2,3,…,n,而输出序列的第一个元素为n,说明1,2,3,…,n一次性全部进栈,再进行输出,所以p1=n,p2=n-1,…,pi=n-i+1。

(3)数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素个数的公式为()。

A.r-f B.(n+f-r)%n C.n+r-f D.(n+r-f)%n

答案:D

解释:对于非循环队列,尾指针和头指针的差值便是队列的长度,而对于循环队列,差值可能为负数,所以需要将差值加上MAXSIZE(本题为n),然后与MAXSIZE(本题为n)求余,即(n+r-f)%n。

(4)链式栈结点为:(data,link),top指向栈顶.若想摘除栈顶结点,并将删除结点的值保存到x中,则应执行操作()。

A.x=top->data;top=top->link;B.top=top->link;x=top->link;

C.x=top;top=top->link;D.x=top->link;

答案:A

解释:x=top->data将结点的值保存到x中,top=top->link栈顶指针指向栈顶下一结点,即摘除栈顶结点。

(5)设有一个递归算法如下

int fact(int n) { //n大于等于0

if(n<=0) return 1;

else return n*fact(n-1); }

则计算fact(n)需要调用该函数的次数为()。

A. n+1 B. n-1 C.n D.n+2

答案:A

解释:特殊值法。设n=0,易知仅调用一次fact(n)函数,故选A。

(6)栈在()中有所应用。

A.递归调用B.函数调用C.表达式求值D.前三个选项都有答案:D

解释:递归调用、函数调用、表达式求值均用到了栈的后进先出性质。

(7)为解决计算机主机与打印机间速度不匹配问题,通常设一个打印数据缓冲区。主

机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的

逻辑结构应该是()。

A.队列 B.栈C.线性表D.有序表

答案:A

解释:解决缓冲区问题应利用一种先进先出的线性表,而队列正是一种先进先出的线

性表。

(8)设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次进入栈S,

一个元素出栈后即进入Q,若6个元素出队的序列是e2、e4、e3、e6、e5和e1,则栈S的

容量至少应该是()。

A.2 B.3 C.4 D.6

答案:B

解释:元素出队的序列是e2、e4、e3、e6、e5和e1,可知元素入队的序列是e2、e4、

e3、e6、e5和e1,即元素出栈的序列也是e2、e4、e3、e6、e5和e1,而元素e1、e2、e3、

e4、e5和e6依次进入栈,易知栈S中最多同时存在3个元素,故栈S的容量至少为3。

(9)若一个栈以向量V[1..n]存储,初始栈顶指针top设为n+1,则元素x进栈的正确

操作是( )。

A.top++; V[top]=x; B.V[top]=x; top++;

C.top--; V[top]=x; D.V[top]=x; top--;

答案:C

解释:初始栈顶指针top为n+1,说明元素从数组向量的高端地址进栈,又因为元素

存储在向量空间V[1..n]中,所以进栈时top指针先下移变为n,之后将元素x存储在V[n]。

(10)设计一个判别表达式中左,右括号是否配对出现的算法,采用()数据结构

最佳。

A.线性表的顺序存储结构 B.队列

C. 线性表的链式存储结构

D. 栈

答案:D

解释:利用栈的后进先出原则。

(11)用链接方式存储的队列,在进行删除运算时()。

A. 仅修改头指针

B. 仅修改尾指针

C. 头、尾指针都要修改

D. 头、尾指针可能都要修改

答案:D

解释:一般情况下只修改头指针,但是,当删除的是队列中最后一个元素时,队尾指

针也丢失了,因此需对队尾指针重新赋值。

(12)循环队列存储在数组A[0..m]中,则入队时的操作为()。

A. rear=rear+1

B. rear=(rear+1)%(m-1)

C. rear=(rear+1)%m

D. rear=(rear+1)%(m+1)

答案:D

解释:数组A[0..m]中共含有m+1个元素,故在求模运算时应除以m+1。

(13)最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是

()。

A. (rear+1)%n==front

B. rear==front

C.rear+1==front D. (rear-l)%n==front

答案:B

解释:最大容量为n的循环队列,队满条件是(rear+1)%n==front,队空条件是rear==front。

(14)栈和队列的共同点是()。

A. 都是先进先出

B. 都是先进后出

C. 只允许在端点处插入和删除元素

D. 没有共同点

答案:C

解释:栈只允许在栈顶处进行插入和删除元素,队列只允许在队尾插入元素和在队头删除元素。

(15)一个递归算法必须包括()。

A. 递归部分

B. 终止条件和递归部分

C. 迭代部分

D. 终止条件和迭代部分

答案:B

2.算法设计题

(1)将编号为0和1的两个栈存放于一个数组空间V[m]中,栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空,当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化,判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下:

Typedef struct

{int top[2],bot[2]; //栈顶和栈底指针

SElemType *V; //栈数组

int m; //栈最大可容纳元素个数

}DblStack

[题目分析]

两栈共享向量空间,将两栈栈底设在向量两端,初始时,左栈顶指针为-1,右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向、迎面增长,栈顶指针指向栈顶元素。

[算法描述]

(1) 栈初始化

int Init()

{S.top[0]=-1;

S.top[1]=m;

return 1; //初始化成功

}

(2) 入栈操作:

int push(stk S ,int i,int x)

∥i为栈号,i=0表示左栈,i=1为右栈,x是入栈元素。入栈成功返回1,失败返回0 {if(i<0||i>1){ cout<<“栈号输入不对”<

if(S.top[1]-S.top[0]==1) {cout<<“栈已满”<

switch(i)

{case 0: S.V[++S.top[0]]=x; return(1); break;

case 1: S.V[--S.top[1]]=x; return(1);

}

}∥push

(3) 退栈操作

ElemType pop(stk S,int i)

∥退栈。i代表栈号,i=0时为左栈,i=1时为右栈。退栈成功时返回退栈元素

∥否则返回-1

{if(i<0 || i>1){cout<<“栈号输入错误”<

switch(i)

{case 0: if(S.top[0]==-1) {cout<<“栈空”<

else return(S.V[S.top[0]--]);

case 1: if(S.top[1]==m { cout<<“栈空”<

else return(S.V[S.top[1]++]);

}∥switch

}∥算法结束

(4) 判断栈空

int Empty();

{return (S.top[0]==-1 && S.top[1]==m);

}

[算法讨论]

请注意算法中两栈入栈和退栈时的栈顶指针的计算。左栈是通常意义下的栈,而右栈入栈操作时,其栈顶指针左移(减1),退栈时,栈顶指针右移(加1)。

(2)回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈) [题目分析]

将字符串前一半入栈,然后,栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较,若相等,则再出栈一个元素与后一个字符比较,……,直至栈空,结论为字符序列是回文。在出栈元素与串中字符比较不等时,结论字符序列不是回文。

[算法描述]

#define StackSize 100 //假定预分配的栈空间最多为100个元素

typedef char DataType;//假定栈元素的数据类型为字符

typedef struct

{DataType data[StackSize];

int top;

}SeqStack;

int IsHuiwen( char *t)

{//判断t字符向量是否为回文,若是,返回1,否则返回0

SeqStack s;

int i , len;

char temp;

InitStack( &s);

len=strlen(t); //求向量长度

for ( i=0; i

Push( &s, t[i]);

while( !EmptyStack( &s))

{// 每弹出一个字符与相应字符比较

temp=Pop (&s);

if( temp!=S[i]) return 0 ;// 不等则返回0

else i++;

}

return 1 ; // 比较完毕均相等则返回 1

}

(3)设从键盘输入一整数的序列:a1, a2, a3,…,a n,试编写算法实现:用栈结构存储输入的整数,当a i≠-1时,将a i进栈;当a i=-1时,输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。

[算法描述]

#define maxsize 栈空间容量

void InOutS(int s[maxsize])

//s是元素为整数的栈,本算法进行入栈和退栈操作。

{int top=0; //top为栈顶指针,定义top=0时为栈空。

for(i=1; i<=n; i++) //n个整数序列作处理。

{cin>>x); //从键盘读入整数序列。

if(x!=-1) // 读入的整数不等于-1时入栈。

{if(top==maxsize-1){cout<<“栈满”<

else s[++top]=x; //x入栈。

else //读入的整数等于-1时退栈。

{if(top==0){ cout<<“栈空”<

else cout<<“出栈元素是”<< s[top--]<

}

}//算法结束。

(4)从键盘上输入一个后缀表达式,试编写算法计算表达式的值。规定:逆波兰表达式的长度不超过一行,以$符作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如:234 34+2*$。

[题目分析]

逆波兰表达式(即后缀表达式)求值规则如下:设立运算数栈OPND,对表达式从左到右扫描(读入),当表达式中扫描到数时,压入OPND栈。当扫描到运算符时,从OPND退出两个数,进行相应运算,结果再压入OPND栈。这个过程一直进行到读出表达式结束符$,这时OPND 栈中只有一个数,就是结果。

[算法描述]

float expr( )

//从键盘输入逆波兰表达式,以‘$’表示输入结束,本算法求逆波兰式表达式的值。

{float OPND[30]; // OPND是操作数栈。

init(OPND); //两栈初始化。

float num=0.0; //数字初始化。

cin>>x;//x是字符型变量。

while(x!=’$’)

{switch

{case‘0’<=x<=’9’:

while((x>=’0’&&x<=’9’)||x==’.’) //拼数

if(x!=’.’) //处理整数

{num=num*10+(ord(x)-ord(‘0’)); cin>>x;}

else //处理小数部分。

{scale=10.0; cin>>x;

while(x>=’0’&&x<=’9’)

{num=num+(ord(x)-ord(‘0’)/scale;

scale=scale*10; cin>>x; }

}//else

push(OPND,num); num=0.0;//数压入栈,下个数初始化

case x=‘’:break; //遇空格,继续读下一个字符。

case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;

case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;

case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;

case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;

default: //其它符号不作处理。

}//结束switch

cin>>x;//读入表达式中下一个字符。

}//结束while(x!=‘$’)

cout<<“后缀表达式的值为”<

}//算法结束。

[算法讨论]假设输入的后缀表达式是正确的,未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符,认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数,每读入一个数字字符,前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点,认为数的整数部分已完,要接着处理小数部分。小数部分的数要除以10(或10的幂数)变成十分位,百分位,千分位数等等,与前面部分数相加。在拼数过程中,若遇非数字字符,表示数已拼完,将数压入栈中,并且将变量num恢复为0,准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断,因此在结束处理数字字符的case后,不能加入break语句。

(5)假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。

①下面所示的序列中哪些是合法的?

A. IOIIOIOO

B. IOOIOIIO

C. IIIOIOIO

D. IIIOOIOO

②通过对①的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false(假定被判定的操作序列已存入一维数组中)。

答案:

①A和D是合法序列,B和C 是非法序列。

②设被判定的操作序列已存入一维数组A中。

int Judge(char A[])

//判断字符数组A中的输入输出序列是否是合法序列。如是,返回true,否则返回false。

{i=0; //i为下标。

j=k=0; //j和k分别为I和字母O的的个数。

while(A[i]!=‘\0’) //当未到字符数组尾就作。

{switch(A[i])

{case‘I’: j++; break; //入栈次数增1。

case‘O’: k++; if(k>j){cout<<“序列非法”<

}

i++; //不论A[i]是‘I’或‘O’,指针i均后移。}

if(j!=k) {cout<<“序列非法”<

else { cout<<“序列合法”<

}//算法结束。

[算法讨论]在入栈出栈序列(即由‘I’和‘O’组成的字符串)的任一位置,入栈次数(‘I’的个数)都必须大于等于出栈次数(即‘O’的个数),否则视作非法序列,立即给出信息,退出算法。整个序列(即读到字符数组中字符串的结束标记‘\0’),入栈次数必须等于出栈次数(题目中要求栈的初态和终态都为空),否则视为非法序列。

(6)假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空、入队和出队等算法。

[题目分析]

置空队就是建立一个头节点,并把头尾指针都指向头节点,头节点是不存放数据的;判队空就是当头指针等于尾指针时,队空;入队时,将新的节点插入到链队列的尾部,同时将尾指针指向这个节点;出队时,删除的是队头节点,要注意队列的长度大于1还是等于1的情况,这个时候要注意尾指针的修改,如果等于1,则要删除尾指针指向的节点。

[算法描述]

//先定义链队结构:

typedef struct queuenode

{Datatype data;

struct queuenode *next;

}QueueNode; //以上是结点类型的定义

typedef struct

{queuenode *rear;

}LinkQueue; //只设一个指向队尾元素的指针

(1)置空队

void InitQueue( LinkQueue *Q)

{ //置空队:就是使头结点成为队尾元素

QueueNode *s;

Q->rear = Q->rear->next;//将队尾指针指向头结点

while (Q->rear!=Q->rear->next)//当队列非空,将队中元素逐个出队

{s=Q->rear->next;

Q->rear->next=s->next;

delete s;

}//回收结点空间

}

(2)判队空

int EmptyQueue( LinkQueue *Q)

{ //判队空。当头结点的next指针指向自己时为空队

return Q->rear->next->next==Q->rear->next;

}

(3)入队

void EnQueue( LinkQueue *Q, Datatype x)

{ //入队。也就是在尾结点处插入元素

QueueNode *p=new QueueNode;//申请新结点

p->data=x; p->next=Q->rear->next;//初始化新结点并链入

Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点

}

(4)出队

Datatype DeQueue( LinkQueue *Q)

{//出队,把头结点之后的元素摘下

Datatype t;

QueueNode *p;

if(EmptyQueue( Q ))

Error("Queue underflow");

p=Q->rear->next->next; //p指向将要摘下的结点

x=p->data; //保存结点中数据

if (p==Q->rear)

{//当队列中只有一个结点时,p结点出队后,要将队尾指针指向头结点

Q->rear = Q->rear->next;

Q->rear->next=p->next;

}

else

Q->rear->next->next=p->next;//摘下结点p

delete p;//释放被删结点

return x;

}

(7)假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag== 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

[算法描述]

(1)初始化

SeQueue QueueInit(SeQueue Q)

{//初始化队列

Q.front=Q.rear=0; Q.tag=0;

return Q;

}

(2)入队

SeQueue QueueIn(SeQueue Q,int e)

{//入队列

if((Q.tag==1) && (Q.rear==Q.front)) cout<<"队列已满"<

else

{Q.rear=(Q.rear+1) % m;

Q.data[Q.rear]=e;

if(Q.tag==0) Q.tag=1; //队列已不空

}

return Q;

}

(3)出队

ElemType QueueOut(SeQueue Q)

{//出队列

if(Q.tag==0) { cout<<"队列为空"<

else

{Q.front=(Q.front+1) % m;

e=Q.data[Q.front];

if(Q.front==Q.rear) Q.tag=0; //空队列

}

return(e);

}

(8)如果允许在循环队列的两端都可以进行插入和删除操作。要求:

①写出循环队列的类型定义;

②写出“从队尾删除”和“从队头插入”的算法。

[题目分析] 用一维数组 v[0..M-1]实现循环队列,其中M是队列长度。设队头指针front和队尾指针rear,约定front指向队头元素的前一位置,rear指向队尾元素。定义front=rear时为队空,(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展,队尾端入队向下标大的方向发展。

[算法描述]

#define M 队列可能达到的最大长度

typedef struct

{elemtp data[M];

int front,rear;

}cycqueue;

elemtp delqueue ( cycqueue Q)

//Q是如上定义的循环队列,本算法实现从队尾删除,若删除成功,返回被删除元素,否则给出出错信息。

{if (Q.front==Q.rear) { cout<<"队列空"<

Q.rear=(Q.rear-1+M)%M; //修改队尾指针。

框架结构毕业设计任务书和指导书范本

框架结构毕业设计任务书和指导书 1 2020年4月19日

毕业设计基本要求 1目的 (1)综合运用所学专业理论知识与设计技能,处理建筑设计中有关方针、政策、功能、经济、安全、美观等方面的问题。解决总体、单体、空间等关系,以创造富有时代气息的优美建筑形象与环境。依据建筑设计完成结构体系的布置、结构在各种荷载工况下的计算、构造和施工图。 (2)掌握一般建筑工程的设计思路,进而举一反三熟悉有关建筑工程的设计、施工、预算等建设过程。为即将走上工作岗位奠定基础。 (3)学以致用,学习科学技术和技能的目的是应用。一个工程师在设计、建设实际工程中应具备的知识,都是我们在毕业设计中应予以加强的。因此深切领悟总体概念设计、掌握具体理论设计和实际工程技术处理措施的结合作为重点来训练。 (4)树立正确的设计思想,全面对待建筑与结构的关系, 2 2020年4月19日

培养勤奋、严谨、认真的工作作风及分析解决一般工程技术问题的能力。 (5)掌握调查研究、理论联系实际的学习方法,养成既能独立思考,又能相互配合密切合作的工作态度。 (6)使学生对一般工业与民用建筑的土建设计的内容和构成有比较全面的了解,并熟悉有关设计标准、规范、手册和工具书,增强毕业后到生产第一线工作的适应能力。 2成果形式及要求 (1)计算书和说明书: 字数应不少于1万字,书写要工整,字迹要清楚,可采用计算机打印。计算书内容要阐明设计依据或标准,方案构思、特点、必要的经济指标,结构选型、构造处理、材料特点及计算上的主要问题,还应包括结构计算全过程,计算要正确、完整、思路清晰、简图明了。计算书格式:应严格按照毕业设计手册中的要求。 (2)图纸: 3 2020年4月19日

大学数据结构期末知识点重点总结(考试专用)

.. ;.. 第一章 概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作,涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型,反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据(结点集合K )以及这些数据之间的 一组二元关系(关系集合R )来表示:(K, R) 结点集K 是由有限个结点组成的集合,每一个结点代表一个数据或一组有明确结构的数据 关系集R 是定义在集合K 上的一组关系,其中每个关系r (r ∈R )都是K ×K 上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型(char )、指针类型(pointer ) b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型;复合数据类型本身,又可参与定义结构更为复杂的结点类型 4.数据结构的分类:线性结构(一对一)、树型结构(一对多)、图结构(多对多) 5.四种基本存储映射方法:顺序、链接、索引、散列 6.算法的特性:通用性、有效性、确定性、有穷性 7.算法分析:目的是从解决同一个问题的不同算法中选择比较适合的一种,或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a .大Ο分析法:上限,表明最坏情况 b .Ω分析法:下限,表明最好情况 c .Θ分析法:当上限和下限相同时,表明平均情况 第二章 线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外,均有唯一的后继 d.除第一元素之外,均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性:元素的类型相同;元素顺序地存储在连续存储空间中,每一个元素唯一的索引值;使用常数作为向量长度 b. 线性表中任意元素的存储位置:Loc(ki) = Loc(k0) + i * L (设每个元素需占用L 个存储单元) c. 线性表的优缺点: 优点:逻辑结构与存储结构一致;属于随机存取方式,即查找每个元素所花时间基本一样 缺点:空间难以扩充 d.检索:ASL=【Ο(1)】 e .插入:插入前检查是否满了,插入时插入处后的表需要复制【Ο(n )】 f.删除:删除前检查是否是空的,删除时直接覆盖就行了【Ο(n )】 4.链表 4.1单链表 a.特点:逻辑顺序与物理顺序有可能不一致;属于顺序存取的存储结构,即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表:head 和tail 指向单链表的头结点 c.链表的插入(q->next=p->next; p->next=q;)【Ο(n )】 d.链表的删除(q=p->next; p->next = q->next; delete q;)【Ο(n )】 e.不足:next 仅指向后继,不能有效找到前驱 4.2双链表 a.增加前驱指针,弥补单链表的不足 b.带头结点的怎么判定空表:head 和tail 指向单链表的头结点 c.插入:(q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;) d.删除:(p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;) 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针,不用花费附加开销;线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度;允许线性表的长度有很大变化;能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时,不宜使用顺序表;线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时,不应选择链表;当指针的存储开销与整个结点内容所占空间相 比其比例较大时,应该慎重选择 第三章 栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表;其特点后进先出;插入:入栈(压栈);删除:出栈(退栈);插入、删除一端被称为栈顶(浮动),另一端称为栈底(固定);实现分为顺序栈和链式栈两种 b.应用: 1)数制转换 while (N) { N%8入栈; N=N/8;} while (栈非空){ 出栈; 输出;} 2)括号匹配检验 不匹配情况:各类括号数量不同;嵌套关系不正确 算法: 逐一处理表达式中的每个字符ch : ch=非括号:不做任何处理 ch=左括号:入栈 ch=右括号:if (栈空) return false else { 出栈,检查匹配情况, if (不匹配) return false } 如果结束后,栈非空,返回false 3)表达式求值 3.1中缀表达式: 计算规则:先括号内,再括号外;同层按照优先级,即先乘*、除/,后加+、减-;相同优先级依据结合律,左结合律即为先左后右 3.2后缀表达式: <表达式> ::= <项><项> + | <项> <项>-|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ? <常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp 为中缀表达式,PostfixExp 为后缀表达式 初始化操作数栈OP ,运算符栈OPND ;OPND.push('#'); 读取InfixExp 表达式的一项 操作数:直接输出到PostfixExp 中; 操作符: 当‘(’:入OPND; 当‘)’:OPND 此时若空,则出错;OPND 若非空,栈中元 素依次弹出,输入PostfixExpz 中,直到遇到‘(’为止;若 为‘(’,弹出即可 当‘四则运算符’:循环(当栈非空且栈顶不是‘(’&& 当前运算符优先级>栈顶运算符优先级),反复弹出栈顶运 算符并输入到PostfixExp 中,再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP ; while (表达式没有处理完) { item = 读取表达式一项; 操作数:入栈OP ; 运算符:退出两个操作数, 计算,并将结果入栈} c.递归使用的场合:定义是递归的;数据结构是递归的;解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行,删除操作在另一端进行,则称此线性表为队列 b.循环队列判断队满对空: 队空:front==rear ;队满:(rear+1)%n==front 第五章 二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶结点的层数 d.如果一棵二叉树的任何结点,或者是树叶,或者恰有两棵非空子树,则此二叉树称作满二叉树 e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2;最下面一层的结点都集中在该层最左边的位置上,则称此二叉树为完全二叉树 f.当二叉树里出现空的子树时,就增加新的、特殊的结点——空树叶组成扩充二叉树,扩充二叉树是满二叉树 外部路径长度E :从扩充的二叉树的根到每个外部结点(新增的空树叶)的路径长度之和 内部路径长度I :扩充的二叉树中从根到每个内部结点(原来二叉树结点)的路径长度之和 2.性质 a. 二叉树的第i 层(根为第0层,i ≥0)最多有2^i 个结点 b. 深度为k 的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树,度为0的结点比度为2的结点多一个。n0 = n2 + 1 d. 满二叉树定理:非空满二叉树树叶数等于其分支结点数加1 e. 满二叉树定理推论:一个非空二叉树的空子树(指针)数目等于其结点数加1 f. 有n 个结点(n>0)的完全二叉树的高度为?log2(n+1)?,深度为?log2(n+1)?? g. 对于具有n 个结点的完全二叉树,结点按层次由左到右编号,则有: 1) 如果i = 0为根结点;如果i>0,其父结点编号是 (i-1)/2 2) 当2i+1∈N ,则称k 是k'的父结 点,k'是的子结点 若有序对∈N , 则称k'k ″互为兄弟 若有一条由 k 到达ks 的路径,则 称k 是的祖先,ks 是k 的子孙 2.树/森林与二叉树的相互转换 a.树转换成二叉树 加线: 在树中所有兄弟结点之间加一连线 抹线: 对每个结点,除了其最左孩子外,与其余孩 子之间的连线 旋转: 45° b.二叉树转化成树 加线:若p 结点是双亲结点的左孩子,则将的右孩子,右孩子的右孩子,所有右孩子,都与p 的双亲用线连起来 线 调整:将结点按层次排列,形成树结构 c.森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 为轴心,顺时针旋转,构成二叉树型结构 d.二叉树转换成森林 抹线:将二叉树中根结点与其右孩子连线,及沿右分支搜索到 的所有右孩子间连线全部抹掉,使之变成孤立的二叉树 还原:将孤立的二叉树还原成树 3.周游 a.先根(次序)周游 若树不空,则先访问根结点,然后依次先根周游各棵子树 b.后根(次序)周游 若树不空,则先依次后根周游各棵子树,然后访问根结点 c.按层次周游 若树不空,则自上而下自左至右访问树中每个结点 4.存储结构 “左子/右兄”二叉链表表示法:结点左指针指向孩子,右结点指向右兄弟,按树结构存储,无孩子或无右兄弟则置空 5. “UNION/FIND 算法”(等价类) 判断两个结点是否在同一个集合中,查找一个给定结点的根结点的过程称为FIND 归并两个集合,这个归并过程常常被称为UNION “UNION/FIND ”算法用一棵树代表一个集合,如果两个结点在同一棵树中,则认为它们在同一个集合中;树中的每个结点(除根结点以外)有仅且有一个父结点;结点中仅需保存父指针信息,树本身可以 存储为一个以其结点为元素的数组 6.树的顺序存储结构 a. 带右链的先根次序表示法 在带右链的先根次序表示中,结点按先根次序顺序存储在一片连续的存储单元中 每个结点除包括结点本身数据外,还附加两个表示结构的信息字段,结点的形式为: info 是结点的数据;rlink 是右指针,指向结点的下一个兄弟;ltag 是一个左标记,当结点没有子结点(即对应二 叉树中结点没有左子结点时),ltag 为 1,否则为 0 b. 带双标记位的先根次序表示法 规定当结点没有下一个兄弟(即对应的二叉树中结点没有右子结点时)rtag 为1,否则为0 c. 带双标记位的层次次序表示法 结点按层次次序顺序存储在一片连续的存储单元中 第七章 图 1.定义 a.假设图中有n 个顶点,e 条边: 含有e=n(n-1)/2条边的无向图称作完全图 含有e=n(n-1) 条弧的有向图称作有向完全图 若边或弧的个数e < nlogn ,则称作稀疏图,否则称作稠密图 b. 顶点的度(TD)=出度(OD)+入度(ID) 顶点的出度: 以顶点v 为弧尾的弧的数目 顶点的入度: 以顶点v 为弧头的弧的数目 c.连通图、连通分量 若图G 中任意两个顶点之间都有路径相通,则称此图为连通图 若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量 d.强连通图、强连通分量 对于有向图,若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图 否则,其各个极大强连通子图称作它的强连通分量 e.生成树、生成森林 假设一个连通图有n 个顶点和e 条边,其中n-1条边和n 个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树 对非连通图,则将由各个连通分量构成的生成树集合称做此非连通图的生成森林 2.存储结构 a.相邻矩阵表示法 表示顶点间相邻关系的矩阵 若G 是一个具有n 个顶点的图,则G 的相邻矩阵是如下定义的n ×n 矩阵: A[i,j]=1,若(Vi, Vj)(或)是图G 的边 A[i,j]=0,若(Vi, Vj)(或)不是图G 的边 b.邻接表表示法 为图中每个顶点建立一个单链表,第i 个单链表中的结点表示依附于顶点Vi 的边(有向图中指以Vi 为尾的弧)(建立单链表时按结点顺序建立) 3.周游 a. 深度优先周游: 从图中某个顶点V0出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发,深度优先搜索遍历图中的其余顶点,直至图中所有与V0有路径相通的顶点都被访问到为止 b. 广度优先周游: 从图中的某个顶点V0出发,并在访问此顶点之后依次访问V0的所有未被访问过的邻接点,随后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有与V0有路径相通的顶点都被访问到为止,若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止 4.拓扑排序 拓扑排序的方法是:1)选择一个入度为0的顶点且输出之 2)从图中删掉此顶点及所有的出边 3)回到第1步继续执行,直至图空或者图不空但找不到无前驱(入度为0)的顶点为止 5.单源最短路径(Dijkstra 算法) 6.每对顶点间的最短路径(Floyd 算法) 7.最小生成树 a.Prim 算法 b.Kruskal 算法 c.两种算法比较:Prim 算法适合稠密图,Kruskal 算法适合稀疏图 第八章 内排序 算法 最大时间 平均时间 直接插入排序 Θ(n2) Θ(n2) 冒泡排序 Θ(n2) Θ(n2) 直接选择排序 Θ(n2) Θ(n2) Shell 排序 Θ(n3/2) Θ(n3/2) 快速排序 Θ(n2) Θ(nlog n) 归并排序 Θ(nlog n) Θ(nlog n) 堆排序 Θ(nlog n) Θ(nlog n) 桶式排序 Θ(n+m) Θ(n+m) 基数排序 Θ(d ·(n+r)) Θ(d ·(n+r)) 最小时间 S(n) 稳定性 Θ(n) Θ(1) 稳定 Θ(n) Θ(1) 稳定 Θ(n2) Θ(1) 不稳定 Θ(n3/2) Θ(1) 不稳定 Θ(nlog n) Θ(log n) 不稳定 Θ(nlog n) Θ(n) 稳定 Θ(nlog n) Θ(1) 不稳定 Θ(n+m) Θ(n+m) 稳定 Θ(d ·(n+r)) Θ(n+r) 稳定 第十章 检索 1.平均检索长度(ASL )是待检索记录集合中元素规模n 的函数, 其定义为: ASL= Pi 为检索第i 个元素的概率;Ci 为找到第i 个元素所需的比较次数 2.散列 a.除余法 用关键码key 除以M(取散列表长度),并取余数作为散列地址 散列函数为:hash(key) = key mod M b.解决冲突的方法 开散列方法:把发生冲突的关键码存储在散列表主表之外(在主表外拉出单链表) 闭散列方法:把发生冲突的关键码存储在表中另一个位置上 c.线性探查 基本思想:如果记录的基位置存储位置被占用,就在表中下移,直到找到一个空存储位置;依次探查下述地址单元:d0+1,d0+2,...,m-1,0, 1,..., d0-1;用于简单线性探查的探查函数是:p(K, i) = i d.散列表的检索 1.假设给定的值为K ,根据所设定的散列函数h ,计算出散列地址h(K) 2. 如果表中该地址对应的空间未被占用,则检索失败,否则将该地址中的值与K 比较 3. 若相等则检索成功;否则,按建表时设定的处理冲突方法查找探查序列的下一个地址,如此反复下去,直到某个地址空间未被占用(可以插入),或者关键码比较相等(有重复记录,不需插入)为止 e.散列表的删除:删除后在删除地点应加上墓碑(被删除标记) f.散列表的插入:遇到墓碑不停止,知道找到真正的空位置 第十一章 索引技术 1.概念: a.主码:数据库中的每条记录的唯一标识 b.辅码:数据库中可以出现重复值的码 2.B 树 a.定义:B 树定义:一个m 阶B 树满足下列条件: (1) 每个结点至多有m 个子结点; (2) 除根和叶外 其它每个结点至少有??个子结点; (3) 根结点至少有两个子结点 例外(空树,or 独根) (4) 所有的叶在同一层,可以有??- 1到m-1个关键码 (5) 有k 个子结点的非根结点恰好包含k-1个关键码 b.查找 在根结点所包含的关键码K1,…,Kj 中查找给定的关键码值(用顺序检索(key 少)/二分检索(key 多));找到:则检索成功;否则,确定要查的关键码值是在某个Ki 和Ki+1之间,于是取pi 所指结点继续查找;如果pi 指向外部结点,表示检索失败. c.插入 找到的叶是插入位置,若插入后该叶中关键码个数

框架结构设计步骤及要点

框架结构设计步骤及要点 1. 结构设计说明: 主要是设计依据,抗震等级,人防等级,地基情况及承载力,防潮抗渗做法,活荷载值,材料等级,施工中的注意事项,选用详图,通用详图或节点,以及在施工图中未画出而通过说明来表达的信息。如混凝土的含碱量不得超过3kg/m3等等。 2. 各层的结构布置图:包括: (1).预制板的布置(板的选用、板缝尺寸及配筋)。标注预制板的块数和类型时, 不要采用对角线的形式。因为此种方法易造成线的交叉, 宜采用水平线或垂直线的方法, 相同类型的房间直接标房间类型号。应全楼统一编号,可减少设计工作量,也方便施工人员看图。板缝尽量为40, 此种板缝可不配筋或加一根筋。布板时从房间里面往外布板, 尽量采用宽板, 现浇板带留在靠窗处, 现浇板带宽最好≥200(考虑水暖的立管穿板)。如果构造上要求有整浇层时, 板缝应大于60。整浇层厚50, 配双向φ6250, 混凝土C20。纯框架结构一般不需要加整浇层。构造柱处不得布预制板。地下车库由于防火要求不可用预制板。框架结构不宜使用长向板,否则长向板与框架梁平行相接处易出现裂缝。建议使用PMCAD的人工布板功能布预制板,自动布板可能不能满足用户的施工图要求,仅能满足定义荷载传递路线的要求。 (2).现浇板的配筋(板上、下钢筋,板厚尺寸)。板厚一般取120、140、160、180四种尺寸或120、150、180三种尺寸。尽量用二级钢包括直径φ10(目前供货较少)的二级钢,直径≥12的受力钢筋,除吊钩外,不得采用一级钢。钢筋宜大直径大间距,但间距不大于200,间距尽量用200。(一般跨度小于6.6米的板的裂缝均可满足要求)。跨度小于2米的板上部钢筋不必断开,钢筋也可不画,仅说明钢筋为双向双排钢筋多少上下钢筋间距宜相等,直径可不同,但钢筋直径类型也不宜过多。顶层及考虑抗裂时板上筋可不断,或50%连通,较大处附加钢筋,拉通筋均应按受拉搭接钢筋。板配筋相同时,仅标出板号即可。一般可将板的下部筋相同和部分上部筋相同的板编为一个板号,将不相同的上部筋画在图上。当板的形状不同但配筋相同时也可编为一个板号。应全楼统一编号。当考虑穿电线管时,板厚≥120,不采用薄板加垫层的做法。电的管井电线引出处的板,因电线管过多有可能要加大板厚至180(考虑四层32的钢管叠加)。宜尽量用大跨度板,不在房间(尤其是住宅)加次梁。说明分布筋为φ8200。板顶标高不同时,板的上筋应分开或倾斜通过。现浇挑板阳角加辐射状附加筋(包括墙上的阳角)。现浇挑板阴角的板下宜加斜筋。顶层应建议甲方采用现浇楼板,以利防水,并加强结构的整体性及方便装饰性挑沿的稳定。外露的挑沿、雨罩、挑廊应每隔10~15米设一10mm的缝,钢筋不断。尽量采用现浇板,不采用予制板加整浇层方案。卫生间做法可为70厚+10高差(取消垫层)。8米以下的板均可以采用非预应力板。L、T或十字形建筑平面的阴角处附近的板应现浇并加厚,双向双排配筋,并附加45度的4根16的抗拉筋。现浇板的配筋建议采用PMCAD软件自动生成,一可加快速度,二来尽量减小笔误。自动生成楼板配筋时建议不对钢筋编号,因工程较大时可能编出上百个钢筋号,查找困难,如果要编号,编号不应出房间。配筋计算时,可考虑塑性力重分布,将板上筋乘以0.8~0.9的折减系数,将板下筋乘以1.1~1.2的放大系数。值得注意的是,按弹性计算的双向板钢筋是板某几处的最大值,按此配筋是偏于保守的,不必再人为放大。支承在外圈框架梁上的板负筋不宜过大,否则将对梁产生过大的附加扭距。一般:板厚>150时采用φ10200;否则用φ8200。PMCAD生成的板配筋图应注意以下几点:1.单向板是按塑性计算的,而双向板按弹性计算,宜改成一种计算方法。 2.当厚板与薄板相接时,薄板支座按固定端考虑是适当的,但厚板就不合适,宜减小厚板支座配筋,增大跨中配筋。 3.非矩形板宜减小支座配筋, .资料. . .

2010级数据结构期末复习题(E)

一、是非题 1.数据结构概念包括数据之间的逻辑结构,数据在计算机中的存储方式和数据的运 算三个方面。.......................( T ) 2.线性表的逻辑顺序与物理顺序总是一致的........( F ) 3.线性表中的每个结点最多只有一个前驱和一个后继。......( T ) 4.线性的数据结构可以顺序存储,也可以链接存储。非线性的数据结构只能链接存 储。.......................( F ) 5.栈和队列逻辑上都是线性表。..........................( T ) 6.单链表从任何一个结点出发,都能访问到所有结点........( F ) 7.单链表形式的队列,头指针F指向队列的第一个结点,尾指针R指向队列的最后 一个结点。.................................................( T ) 8.在用单链表表示的链式队列中,队头在链表的链尾位置。....( F ) 9.多维数组是向量的推广。..............................( T ) 10.栈是一种先进先出的线性表。....( F ) 11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......( T ) 12.设串S的长度为n,则S的子串个数为n(n+1)/2。...........( F ) 13.一般树和二叉树的结点数目都可以为0。................( F ) 14.按中序遍历二叉树时,某结点的直接后继是它的右子树中第1个被访问的结 点。....( T ) 15.后序序列和中序序列能唯一确定一棵二叉树。....( T ) 16.对于一棵具有n个结点,其高度为h的二叉树,进行任—种次序遍历的时间复杂 度为O(n) .............( T ) 17.网络的最小代价生成树是唯一的。...( T ) 18.图的拓扑有序序列不是唯一的。...( T ) 19.进行折半搜索的表必须是顺序存储的有序表。...( T ) 二、单选题 1.算法指的是( D ) A.计算机程序 B.解决问题的计算方法 C.排序算法 D.解决问题的有限运算序列 2.线性表采用链式存储时,结点的存储地址(B ) A.必须是不连续的 B.连续与否均可 C.必须是连续的 D.和头结点的存储地址相连续 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为(C ) A.O(1) B.O(n) C.O(m) D.O(m+n) 4.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。 A.O(n) B.O(1) C.O(n2) D.O(log2n)T 5.线性表L在( B )情况下适用于使用链式结构实现。 A.需经常修改L中的结点值 B.需不断对L进行删除插入 C.L中含有大量的结点 D.L中结点结构复杂 6.设单链表中结点的结构为(data,1ink)。已知指针q所指结点是指针p所指结点 的直接前驱,若在*q与*p之间插入结点*s,则应执行下列哪一个操作?( B ) A.s一>1ink=p一>1ink;p一>1ink=s B.q一>1ink=s;s一>link=p C.p一>link=s一>1ink;s一>1ink=p

数据结构期末考试复习笔记

判断: 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因 此属于同一数据对象正确 4.在线性表的顺序存储结构中,逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中,插入和删除元素时,移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A,B,C,D,可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中,任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下,不能做出出栈操作,否则产生溢出正确 13.在前序遍历二叉树的序列中,任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空: 1.在N个节点的顺序表中删除一个节点平均需要移动((N-1)/2)个节点,具体的移 动次数取决于(表长N和删除位置) 2.在单链表中除首节点外,任意节点的存储位置都由(直接前驱)节点中的指针指示 3.树中节点的最大层次称为树的(度) 4.由一颗二叉树的前序序列和(中)序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度(最小)的二叉树 6.二插排序树任意节点的关键字值(大于)其左子树中各节点的关键字值(小于)其 右子树中的各节点关键字值 7.二分查找法,表中元素必须按(关键字有序)存放 选择: 1.用单链表方式存储的线性表,储存每个节点需要两个域,一个数据域,另一个是(B 指针域) 2.设A1,A2,A3为三个节点;P,10,,2代表地址,则如下的链表存储结构称为(B 单链表) 3.单链表的存储密度(C 小于1) 4.在线性表中(B 中间元素)只有一个直接前驱和一个直接后续 5.两个指针P和Q,分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是(D P==Q) 6.在栈中存取数据的原则是(B 后进先出) 7.顺序栈判空的条件是(C top==-1) 8.串是一种特殊的线性表,其特殊性体现在(B 数据元素是一个字符) 9.求字符串T和字符串S中首次出现的位置的操作为(C 串的模式匹配) 10.深度为H的二叉树至多有(B 2H-1)个节点

《数据结构》期末复习题答案

1.以下与数据的存储结构无关的术语是( c ) C、哈希表 2.一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( B ) B、108 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是(C ) C、head–>next= =head 4.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是(D ) D、2,3,5,1,6,4 5.下列关键字序列中,构成小根堆的是(A ) A、{12,21,49,33,81,56,69,41} 6.下列数据结构中,不属于二叉树的是(A ) A、B树 7.用顺序存储的方法来存储一棵二叉树,存放在一维数组A[1..N]中,若结点A[i]有右孩子,则其右孩子是(C )。 C、A[2i+1] 8.设树T的高度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1,则T中叶子数为(D ) D、8 9.有数据{53,30,37,12,45,24,96},从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,则应选择下 面哪个序列输入(B ) B、37,24,12,30,53,45,96 10.对下面有向图给出了四种可能的拓扑序列,其中错误的是(C ) C、5,1,6,3,4,2 11.m阶B-树中所有非终端(除根之外)结点中的关键字个数必须大于或等于( B ) B、[m/2]-1 12.散列文件也称为( C ) B 、索引文件 13.数据结构是(D ) D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看,数据元素的直接前驱为0个或1个的数据结构只能是(C ) C、线性结构和树型结构 15.设p为指向双向循环链表中某个结点的指针,p所指向的结点的两个链域分别用p→llink和p→rlink表示,则同样表示p

框架结构设计的技术措施

框架结构设计的技术措施探析 摘要:钢筋混凝土的框架结构由四部门组成,分别是楼板、柱、梁以及基础承重构件。在允许的高度情况下,框架结构的设计需要提供较大的空间,来适合多种使用功能的要求。被人们广泛的应用于工业多层厂房以及仓库中。本文从现浇板截面及配筋、人工调整框架节点配筋及填充墙、框架柱模板结构设计、强化建筑物框架结构设计的管理措施、框架结构设计中的其他问题五个方面进行了框架结构设计技术的探析说明。 关键词:框架;结构设计;技术探析 abstract: the reinforced concrete frame structure composed by four departments, respectively is floor, column, beam and foundation bearing component. at the height of the allowed, frame structure design need to provide larger space, to suit a variety of use function requirements. is widely used in the industry of multi-story factory buildings and warehouse. this paper, from the site casting integrated section and reinforcement, artificial adjustment framework node reinforcement and fill walls, frame column template structure design, strengthen the building of the frame structure design management measures, frame structure design of the other problem five on the frame structure design technology analysis shows.

数据结构复习重点归纳

数据结构复习重点归纳 (适于清华严版教材) 一、数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为:概论,线性表,栈和队列,串,多维数组和广义表,树和二叉树,图,查找,内排,外排,文件,动态存储分配。 对于绝大多数的学校而言,“外排,文件,动态存储分配”三章基本上是不考的,在大多数高校的计算机本科教学过程中,这三章也是基本上不作讲授的。所以,大家在这三章上可以不必花费过多的精力,只要知道基本的概念即可。但是,对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史,那么这部分朋友就要留意这三章了。 按照以上我们给出的章节以及对后三章的介绍,数据结构的章节比重大致为:概论:内容很少,概念简单,分数大多只有几分,有的学校甚至不考。 线性表:基础章节,必考内容之一。考题多数为基本概念题,名校考题中,鲜有大型算法设计题。如果有,也是与其它章节内容相结合。 栈和队列:基础章节,容易出基本概念题,必考内容之一。而栈常与其它章节配合考查,也常与递归等概念相联系进行考查。 串:基础章节,概念较为简单。专门针对于此章的大型算法设计题很少,较常见的是根据KMP进行算法分析。 多维数组及广义表:基础章节,基于数组的算法题也是常见的,分数比例波动较大,是出题的“可选单元”或“侯补单元”。一般如果要出题,多数不会作为大题出。数组常与“查找,排序”等章节结合来作为大题考查。 树和二叉树:重点难点章节,各校必考章节。各校在此章出题的不同之处在于,是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析,绝大多数学校在本章都曾有过出大型算法设计题的历史。 图:重点难点章节,名校尤爱考。如果作为重点来考,则多出现于分析与设计题型当中,可与树一章共同构成算法设计大题的题型设计。 查找:重点难点章节,概念较多,联系较为紧密,容易混淆。出题时可以作为分析型题目给出,在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查,也可以与树一章结合来考查。 排序:与查找一章类似,本章同属于重点难点章节,且概念更多,联系更为紧密,概念之间更容易混淆。在基本概念的考查中,尤爱考各种排序算法的优劣比较此类的题。算法设计大题中,如果作为出题,那么常与数组结合来考查。 二、数据结构各章节重点勾划: 第0章概述本章主要起到总领作用,为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点:数据结构的基本概念,时间和空间复杂度的概念及度量方法,算法设计时的注意事项。本章考点不多,只要稍加注意理解即可。 第一章线性表作为线性结构的开篇章节,线性表一章在线性结构的学习乃至整个数据结构学科的学习中,其作用都是不可低估的。在这一章,第一次系统性地引入链式存储的概念,链式存储概念将是整个数据结构学科的重中之重,无论哪一章都涉及到了这个概念。 总体来说,线性表一章可供考查的重要考点有以下几个方面: 1.线性表的相关基本概念,如:前驱、后继、表长、空表、首元结点,头结点,头指针等概念。 2.线性表的结构特点,主要是指:除第一及最后一个元素外,每个结点都只有一个前趋和只有一个后继。 3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现:表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。 4.线性表的链式存储方式及以下几种常用链表的特点和运算:单链表、循环链表,双向链表,双向循环链表。其中,单链表的归并算法、循环链表的归并算法、双 向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外,近年来在不少学校中还多次出现要求用递归算法实现单链表输出(可能是顺序也可能是倒序)的问题。 在链表的小题型中,经常考到一些诸如:判表空的题。在不同的链表中,其判表空的方式是不一样的,请大家注意。 5.线性表的顺序存储及链式存储情况下,其不同的优缺点比较,即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储 结构的各自好处。 第二章栈与队列栈与队列,是很多学习DS的同学遇到第一只拦路虎,很多人从这一章开始坐晕车,一直晕到现在。所以,理解栈与队列,是走向DS高手的一条必由之路,。 学习此章前,你可以问一下自己是不是已经知道了以下几点: 1.栈、队列的定义及其相关数据结构的概念,包括:顺序栈,链栈,共享栈,循环队列,链队等。栈与队列存取数据(请注意包括:存和取两部分)的特点。 2.递归算法。栈与递归的关系,以及借助栈将递归转向于非递归的经典算法:n!阶乘问题,fib数列问题,hanoi问题,背包问题,二叉树的递归和非递归遍历问 题,图的深度遍历与栈的关系等。其中,涉及到树与图的问题,多半会在树与图的相关章节中进行考查。 3.栈的应用:数值表达式的求解,括号的配对等的原理,只作原理性了解,具体要求考查此为题目的算法设计题不多。 4.循环队列中判队空、队满条件,循环队列中入队与出队算法。 如果你已经对上面的几点了如指掌,栈与队列一章可以不看书了。注意,我说的是可以不看书,并不是可以不作题哦。 第三章串经历了栈一章的痛苦煎熬后,终于迎来了串一章的柳暗花明。

数据结构期末复习总结超详细1

数据结构复习要点带答案 算法的五大特性:(有零个或多个输入)、(有一个或多个输出)、(有穷性)、(确定性)、(可行性)。 算法指的是()。 A 对特定问题求解步骤的一种描述,是指令的有限序列;算法分析的目的是(分析算法的效率以求改 进),算法分析的两个主要方面是(空间性能和时间性能)。 1.算法质量的标准:时间复杂度是测量一个算法优劣的重要标准。 时间复杂度的计算:设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为(Ο(1)),若为n*log25n,则表示成数量级的形式为(Ο(nlog2n))。 【分析】:用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。 2.数据、数据元素、数据项的关系:(数据元素)是数据的基本单位,在计算机程序中通常作为一个整体 进行考虑和处理;(数据项)是数据的最小单位,(数据元素)是讨论数据结构时涉及的最小数据单位。 【分析】数据结构指的是数据元素以及数据元素之间的关系。 3.设有数据结构(D,R),其中D={1, 2, 3, 4, 5, 6},R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。 试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1-3所示,它是一种图结构。 4.栈的特性:栈是限定仅在表尾进行插入和删除操作的线性表,允许插入和删除的一段叫做栈顶,另一 端叫做栈底,不含任何数据元素的栈叫做空栈。(栈)可作为实现递归函数调用的一种数据结构。 【分析】递归函数的调用和返回正好符合后进先出性。 栈的特点是先进后出,即:进去的早,出来的晚! 54321进栈,5在栈底,1在栈顶! 出一次栈,则栈顶的1先出来,2成为新的栈顶。 ABCD入栈,D成为新的栈顶。 全部出栈:D C B A 2 3 4 5 综上,所有元素退栈顺序为:1 D C B A 2 3 4 5 5.入栈:template V oid SeqStack::Push(T x) { if ( top==StackSize-1) throw “上溢”; top++; data[top]=x; } 6.出栈的指针的操作:template T SeqStack::Pop() { if ( top== -1) throw “下溢”; x=data[top--]; return x; }顺序栈基本操作时间复杂度为O(1).

相关主题
相关文档 最新文档