说明：此复习题为复习专用，其给定了期末考试的主要范围，并非给定考试原题，考试时相关的题目基本都要进行改动。因此同学们请注意，不要去背答案，要将题理解并做会。
请注意这决不是原题，只有弄会才可能通过）
1、数据结构主要研究的三个内容为以及定义在该结构上的。
2、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于。
3、数据结构被形式地定义为（d，r），其中d是的有限集，r是d上的有限集。
4、数据的结构在计算机内存中的表示是指（ ）
a.数据的存储结构 b.数据结构 c.数据的逻辑结构 d.数据元素之间的关系。
5、给出以下给定的两个程序段中划波浪线的语句的执行频度（次数）。
1） sum=0;
for(i=0;ifor(j=0; j（2） sum=0;
for(i=0;ifor(j=0; j<=i; j++)sum+=a[i][j];
(3) sum=0;
for(i=0;i for(j=0; j※6、分析以下各程序段的时间复杂度为（用大o记号表示）
1） i=s=0;
while(si++;
s+=i;2） i=1;
while(i<=n)
i=i*3;
1、n(n>=0)个元素的线性结构表示成(a1，a2,……an)，a1称为___元素，an称为___元素，i称为ai**性表中的对任意一对相邻结点ai、ai+1(1<=i2、在表长为n的顺序表的第i个位置插入一元素（1<=i<=n+1，插入的新元素作为第i个元素），则涉及到的元素的移动次数为若删除第i（1<=i<=n）个元素，则涉及到的元素的移动次数为。
3、线性表的顺序存储结构（顺序表）其存储空间。
a) 必须是连续的 b) 部分是连续的。
c) 一定是不连续的 d) 连续不连续都可以。
4、一个顺序表的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是。
a）110 b）108 c）100 d）120
5、顺序表的存取特点为单链表的存取特点为。
6、对于顺序表的优缺点，以下说法错误的是（ ）
①无需为表示结点间的逻辑关系而增加额外的存储空间。
②可以方便地随机存取表中的任一结点。
③插人和删除运算较方便。
④容易造成一部分空间长期闲置而得不到充分利用。
7、以下说法正确的是。
线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继。
线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低。
在顺序存储线性表中，插入和删除元素时，移动元素的个数与插入或删除位置有关。
顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动。
8、以下说法正确的是（ ）
顺序存储方式的优点是存储密度大、且插入、删除运算效率高。
链表的每个结点中都恰好包含一个指针。
线性表的顺序存储结构优于链式存储结构。
顺序存储结构属于静态结构，链式结构属于动态结构。
9、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
顺序表 ②单链表 ③双链表 ④单循环链表。
10、单链表中，增加头结点的目的是为了 (
使单链表至少有一个结点
标示表结点中首结点的位置。
使每个元素都能有前驱结点，从而方便运算的实现。
说明单链表是线性表的链式存储实现。
11、对于一单链表l(l为头指针，且结点的后继指针分量为next),其p结点（p为链表中某结点的指针）既不是第一个结点，也不是最后一个结点。
1）在p结点后插入s结点(s为某结点的指针)的语句序列是1】
（2）删除p结点的直接后继结点的语句序列是：q=p->next; 【2free(q);
3）若l为带头结点的单链表，则：
a) 在表首插入s结点的语句序列是： 【3
b) 单链表为空的判定条件为4
4）若l为不带头结点的单链表，则：
a) 在表首插入s结点的语句序列是5
b) 单链表为空的判定条件为6】
12、已知l是带表头结点的双向链表(l为头指针，且结点的后继指针分量为next，前驱指针为pre ),其p结点（p为链表中某结点的指针）既不是首元结点，也不是尾元结点。
a）在p结点后插入s结点(s为某结点的指针)的语句序列是：
s->next=p->next；s->pre= 【12】 =s; p->next=s;
b）在p结点前插入s结点(s为某结点的指针)的语句序列是：
s->pre=p->pre;s->next= 【34】 =s; p->pre=s;
c）删除p结点的直接后继结点的语句序列是：
q=p->next; p->next= 【56】 =p; free(q);
d) 删除p结点的直接前驱结点的语句序列是：
q=p>pre78】 =p; free(q);
e) 删除该p结点语句序列是： 【9】 =p->next; p->next->pre= 【10】 ;free(p);
f) 在表首插入s结点的语句序列是：
s->next=l->next11】 =l12l->next=s;
13、设带头结点的单链表类型定义如下：
typedef struct lnode
elemtype data; /elemtype 为数据元素类型。
struct lnode *next; /后继结点的指针。
*linkedlist;
1）函数inverselist(l)的作用是将一带头结点的单链表实现就地逆置的算法（即利用原来链表的空间，将单链表中的结点按原来相反的顺序存储）。填写空缺位置，使此该算法完整。
inverselist(linkedlist &l)
p=l->next;
l->next= null;
while ( p )
2） mergelist(la, lb)函数的作用是将两个递增有序的带头结点的单链表la, lb，利用原来的结点空间，合并成一个递增有序的链表la。填写空缺位置，使此该算法完整。
void mergelist (linkedlist &la, linkedlist &lb)
pa=la->next; pb=lb->next; s=la;
while( 【3】 )
else if (pa) s->next=pa;
else s->next= 【5】 ;
free(lb);
3）函数search(l,i)用来返回带头结点的单链表l的第i个元素的位置指针。填写空缺位置，使此该算法完整。
linkedlist search(linkedlist l, int i)
if( 【8】 )return p;
else return null;
（4）函数listlength(l)用来求一带头结点的单链表l的长度。请写出此函数的算法**。
14、函数deleteelem(int a,int n, int i)的作用为：在一个长度为n的数组中，删除其第i个元素。其中第数组的第一个元素为a[0]，第二个元素为a[1]，依次类推。
请写出此函数的算法**。
1、栈与队列是二种特殊的线性表，栈其亦称为 ；队列亦称为 。
2、现有一个空栈，现有4个元素其入栈顺序为a、b、c、d，则不可能得到了出栈顺序为。
a）a,b,c,d b) d,c,b,a c) c,a,b,d d) a,c,b,d
3、现有一个空栈，已知其入栈序列为1, 2, 3, …n，其输出序列为p1, p2, p3, …pn。若p1=n，则pi（1≤i≤n）为。
a）i b) n-i c) n-i+1 d) 不确定。
4、栈与队列的共同点是。
数据结构期末复习讲解
计算机1405杨程皓。版权所有，翻版必究。附录是最小生成树和拓扑排序的 及讲解，还有一些主要算法的演示。一 基本概念及基本结构。1 数据结构及其逻辑结构 存储 物理 结构的基本概念。答 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，在任何问题中，数据元素都不是孤立存在的，而是在他们之间存...
数据结构复习内容讲解
数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为 data structure d,s d 元素有限集还分成数值类型和非数值类型。s 关系有限集。数据 data 所有能被计算机识别 存储和处理的符号的集合 包括数字 字符 声音 图像等信息 数据元素 data element 是数据的...
数据结构作业习题答案 修订
第二章线性表。a.4 1 b.7 11 8 4 1 c.5 12 d.11 9 1 6 或 11 9 6 1 或 11 9 6 1 a.11 3 4 b.10 12 8 11 3 14 或 10 12 8 3 14 c.10 12 7 3 14 d.10 12 13 14 或 12 11 3 14 ...