2015数据结构复习-C++版-学生

《2015数据结构复习-C++版-学生》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构(C++版)复习要点考试说明：考试时间为120分钟，总分100分。考试题型为：一、单选题：（每小题1分，本大题共10分）二、填空题：（每空2分，本大题共20分）三、简答题:（每小题5分，本大题共50分）四、算法设计题:（每小题10分，本大题共20分）第一章绪论本章主要介绍了一些基本概念。对于本章内容的掌握主要以概念为主。主要知识要点1、理解数据、数据元素、数据项、数据对象、数据类型、数据结构的概念。2、掌握如何用二元组来表示一个数据结构。掌握数据的四类基本逻辑结构（集合、线性结构、树型结构、图状或网状结构）。3、理解顺序存储方法和链式存储方法是怎样存

2、储数据的。4、时间复杂度和空间复杂度（给程序能写出复杂度），常用操作的时间复杂度。例题：1.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（D）。A．线性结构B.树型结构C.物理结构D.图型结构2.下面程序的时间复杂为（B）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A.

3、O(n)B.O(n2)C.O(n3)D.O(n4)3.数据的物理结构主要包括____顺序___和___链式____两种情况。4.下面程序段的时间复杂度是i=s=0;while(s=n的时候停止，即k=关于n的表达式是根号的,n1/2第二章线性表本章主要介绍了线性表的定义、存储方式的描述和基本运算以及实现算法。要求掌握并能灵活应用概念及性质。主要知识

4、要点1、掌握线性表定义、逻辑特性、空表、文件、前驱元素、后继元素的概念。2、掌握顺序存储及顺序表的定义。掌握顺序存储结构的优缺点，插入删除操作算法。数据元素的存储位置取决于第一个数据元素的存储位置LOC(ai)=LOC(a1)+(i-1)×C3、掌握线性链表的定义。掌握链式存储结构的优缺点，单链表插入删除操作算法，单链表、双向循环链表的插入与删除操作，头结点的作用，单链表的判空条件。4、掌握静态链表的概念。例题1、顺序表中逻辑上相邻的元素的物理位置（一定）相邻。单链表中逻辑上相邻的元素的物理位置（不一定）相邻。2、线性表的顺序存储、链式存储有哪些特点？3、线

5、性表的两种存储结构其中（顺序）存储密度较大；（顺序）存储利用率较高；（顺序）可以随机存取；（链式）不可以随机存取；（链式）插入和删除操作比较方便。4、设指针变量p指向单链表中结点A前驱，若删除单链表中结点A，则需要修改指针的操作序列为（C）。A.q=p->next；p->data=q->data；p->next=q->next；free(q)；B.q=p->next；q->data=p->data；p->next=q->next；free(q)；C.q=p->next；p->next=q->next；free(q)；D.q=p->next；p->data=q

6、->data；free(q)；5、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL6、在一个单链表中，已知q所指结点是p所指结点的前趋结点，若在q和p之间插入S结点，则执行（C）。A.S->next=p->next;p->next=S;B．p->next=S->next;S->next=p;C.q->next=S;S->next=p;D.p->next=S;S->next=q;7、在一个长度为n的向量中删除第i个元素

7、（1<=i<=n）时，须向前移动（n-i）个元素。8、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表9、编写算法实现顺序表的就地逆置，即要求利用原顺序表的存储单元，把数据元素序列（a0，a1，…，an－1）逆置为（an－1，…，a1，a0）。10、设计在单链表中删除具有某种特性的结点的算法。11、在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A01234567data605078903440

8、next357204112、设顺序线性表中有n个数据