广东专升本数据结构知识点总结

广东专升本数据结构知识点总结

①数据结构（逻辑结构）其4类基本结构：集合、线性结构、树形结构、图

状结构和网状结构。

②物理结构（存储结构）其4种存储结构：顺序存储结构、链式存储结构、

索引存储结构和散列存储结构。

③算法5个重要特性：有穷性、确定性、可行性、输入和输出。

通常从四个方面评价算法的质量：正确性、易读性、强壮性和高效

率。

④线性表是由n20个数据元素组成的有限序列。其特点为逻辑关系上相

邻的两个元素在物理位置上也相邻。

⑤在顺序表中实现的基本运算：

插入：平均移动结点次数为n/2;平均时间复杂度均为。（n工

删除：平均移动结点次数为（n-1）/2;平均时间复杂度均为O（nX

⑥存储位置计算：每个元素需占用L个存储单元第一个单元的存储地址作

为数据元素的存储位置线性表的第i个数据元素ai的存储位置为

LOC（ai）=LOC（al）+（i-l）*L,al的存储位置，通常称做线性表的起始位置或基

地址。

⑦线性表的链式存储结构:数据元素ai的存储映像称为结点，包括2个域:

存数据的数据域、存后继存储位置的指针域。

⑧线性链表（单链表）特点：每个结点只包含1个指针域。在单链表的第一

个结点之前附设的一个结点，称之为头结点。

⑨假设L是LinkList型变量，则L为单链表的头指针，它指向表中第一个

结点。

L->next为第一个结点地址，L->next=NULL为空表。

回收结点：free(q)。

⑩栈：是限定仅在栈顶(表尾)进行插入或删除操作的线性表。表头端称

为栈底，不含有元素的空表称为空栈；栈又称为后进先出的线性表。

⑪队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而

另一端删除元素。允许插入的一端叫做队尾，允许删除的一端则称为队头。

⑫链队列：用链表示的队列。一个队列需要头指针和尾指针才能确定唯一。

⑩栈：是限定仅在栈顶(表尾)进行插入或删除操作的线性表。表头端称

为栈底，不含有元素的空表称为空栈；栈又称为后进先出的线性表。

⑪队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而

另一端删除元素。允许插入的一端叫做队尾，允许删除的一端则称为队头。

⑫链队列：用链表示的队列。一个队列需要头指针和尾指针才能确定唯一。

⑬循环队列：两个指针front指示队列头元素和rear指示队列尾元素的位

置。初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，"尾

指针增1";每当删除队列头元素时，"头指针增1"o

⑭串：是由零个或多个字符组成的有限序列。

⑮数组的存储位置计算：假设每个数据元素需占用L个存储单元，则二维

数组A中任一元素A[ij]的存储位置可由下式确定：

以行序为主序的存储结构：LOC(i,j)=LOC(OQ)+(n*i+j)*L;(n为行数)

以列序为主序的存储结构:LOC(i,j)=LOC(0,0)+(n*j+i)*L;(n为列数)

⑯广义表：是线性表的推广，在广义表的定义中，ai可以是单个元素，也

可以是广义表，分别称为广义表LS的原子和子表。

©二叉树的性质：

性质1:在二叉树的第K层上至多有2k-l个结点(K之1)。

性质2:深度为k的二叉树至多2k-l个结点(kN1)。

深度为k的二叉树至少有k个结点(k?l)。

深度为k的完全二叉树至少有2k-l个结点(kNl)。

性质3:对任何一棵二叉树T,如果其终端结点数为NO,度为2的结

点数为N2,则N0=N2+l。总结点个数N=N0+Nl+N2o

性质4:具有n个结点的完全二叉树的深度为[Iog2n]+1。

⑱满二叉树：一颗深度为k且有2的k次方减1个结点的二叉树。

⑲完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结

点都与深度为k的满二叉树中编号从1至n的结点——对应。

⑳树转换成二叉树：连兄弟，留长子，删孩子。

注意：由于树根没有兄弟结点，固树转换为二叉树后，二叉树根结点的

右子树必为空。

①森林转换成二叉树：连树根及兄弟，留长子，删孩子。

②二叉树转换成树：连左孩子的右孩子及其右孩子…，删原树右孩子。

③赫夫曼树：又称最优树，是一类带权路径长度最短的树。

WPL=23+43+52+71=35

④赫夫曼编码：在赫夫曼树上，左分支代表0,右分支代表L由根结点

到指定结点的路径(从上到下把0、1连起来)，就是该结点的赫夫曼编码；如上

图(d)中a为0,b为10,c为110,d为111。

⑤无向完全图：有n(n-l)/2条边的无向图。

有向完全图：有n(n-l)条边的有向图。

⑥邻接矩阵：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非零元素

的个数等于边个数的2倍，第i行和第i列中非零元素的个数等于该结点的度。

⑦邻接表：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非零元素

的个数等于边个数的2倍，第i行和第i列中非零元素的个数等于该结点的度。

⑧深度优先遍历：

⑨广度优先遍历：

⑩最小生成树：

普里姆算法(Prim):连相邻权值最小的。

克鲁斯卡尔算法(Kruskal):先连权值最小的，再依次连。

@拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序的操作。

顺序查找法平均查找长度：

⑫ASL=(n+l)/2o

折半查找法(二分查找法)平均查找长度：ASL=(n+l)/n*log2(n+l)-l

索引顺序表查找法(分块查找法评均查找长度:ASLMog2(n/s+l)+s/2。

⑬直接插入排序：将一个记录插入到已排好序的有序表中，从而得到一个

新的、记录数增1的有序表。

⑭冒泡排序：首先将一个记录的关键字和第二个记录的关键字进行比较，

若为逆序(即L.r[l].key>L.r[2].key),则将两个记录交换之，然后比较第二个记

录和第三个记录的关键字。以此类推，直至第n-1个记录和第n个记录的关键

字进行过比较为止。

⑮快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分

记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行

排序，以达到整个序列有序。

①巾页序表是随机存储结构，当线性表的操作主要是查找时，宜采用以插入

和删除操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在

表的首尾两端，则宜采用尾指针表示的单循环链表。

②在顺序栈中有"上溢"和"下溢"的现象，"上溢"是栈顶指针指出栈的

外面是出错状态，"下溢"可以表示栈为空栈，因此用来作为控制转移的条件。

③队列是一种运算受限的线性表，允许删除的一端称为队头（front）,允

许插入的一端称为队尾（rear）,队列的操作原则是先进先出的，又称作FIFO

表。队列也有顺序存储和链式存储两种存储结构。

④循环队列：判定循环队列是空还是满，方法有三种：

一种是另设一个布尔变量来判断；

第二种是少用一个元素空间，入队时先测试（（rear+1）%m=front）?

满：空；

第三种就是用一个计数器记录队列中的元素的总数。

⑤队列的链式存储结构称为链队列，为了便于在表尾进行插入（入队）的

操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地

确定。链队列不存在队满和上溢的问题。

在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修

改头尾指针并使队列变空。

⑥串是零个或多个字符组成的有限序列。

空串：是指长度为零的串，也就是串中不包含任何字符（结点）

空白串：指串中包含一个或多个空格字符的串。

⑦子串在主串中的序号就是指子串在主串中首次出现的位置。空串是任意

串的子串，任意串是自身的子串。

⑧串的基本运算有：

求串长strlen(char*s)串复制strcpy(char*to,char*from)

字符定位strchr(char*s,chare)串联接strcat(char*to,char*from)

串比较charcmp(char*sl,char*s2)

⑨地址的计算方法：

按行优先顺序排列的数组：LOCa(ij)=LOCa(ll)+((i-1)*n+(j-l))

*d

按列优先顺序排列的数组：LOCa(ij)=LOCa(ll)+((j-l)*n+(i-l))

*d

⑩图的存储结构：

邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的；无向图中

邻接矩阵是对称的；有向图中行是出度，列是入度。

邻接表表示法：用顶点表和邻接表构成不是唯一的；顶点表结构vertex|

firstedge，指针域存放邻接表头指针；邻接表是用头指针确定。

⑪图的遍历：

深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。

广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。

⑫直接插入排序：

⑬直接选择排序：

⑭冒泡排序：

⑮快速排序：

①n个结点的二叉树共有2n个指针域，其中有n-1个指针域是存放了

地址，有n+1个指针是空指针。

②在一个具有n个顶点的无向完全图中，包含有e条边，在一个具有n

个顶点的有向完全图中，包含有2e条边。

③在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为

O(log2n),整个堆排序过程的时间复杂度为O(nlog2n)0

④AOV网是一种有向无回路的图。

⑤设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构，则该

哈夫曼树中总共有2m个空指针域。(m个叶子节点的哈夫曼树总共有2m-l

个节点)

⑥设顺序循环队列Q[0:M-1]的头指针和尾指针分别为F和R,头指针F

总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该

循环队列中的元素个数为(R-F+M)%M。

⑦快速排序的最坏时间复杂度为0(n2),平均时间复杂度为O(nlog2n)。

⑧数据的物理结构主要包括顺序存储结构和链式存储结构两种情况。

⑨二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。

在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+Iog2n。

⑩设有n个无序的记录关键字，则直接插入排序的时间复杂度为0(n2),

快速排序的平均时间复杂度为O(nlog2n)o

⑪设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的

语句序列为p>llink->rlink=p->rlink;p->rlink->llink=p->rlink(设结点中的

两个指针域分别为llink和rlinkX

⑫设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够

存储m-1个队列元素；当前实际存储(R-F+M)%M个队列元素(设头指针F

指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置X

⑬设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则

顶点i和顶点j互为邻接点的条件是A[i][j]=lo

⑭数据项是不可分割的构成数据元素的最小单位；数据元素是数据的基本

单位。

⑮设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链

表仍然保持有序，则该操作的时间复杂度为O(n)o

两方面：一是插入时间复杂度。(1)；二是保持有序时间复杂度0(n)

⑯设一棵m叉树中度数为0的结点数为NO度数为1的结点数为NI〃.•…，

度数为m的结点数为Nm,则N0=I+N2+2N3+3N4+……+(m-l)Nm0

【注解】由2叉树的性质引申出，对于任何一颗树T,如果其终端结点树为

nO度为i的结点数为ni,则n0=l+n2+2n3+-+(i-l)ni

⑰设有一个顺序共享栈S[0:n-l]其中第一个栈项指针topi的初值为-1,

第二个栈顶指针top2的初值为n,则判断共享栈满的条件是topl+l=top2o

⑱在图的邻接表中用顺序存储结构存储表头结点的优点是可以随机访问

到任一个顶点的简单链表。

⑲设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件

是head==0o

不带头结点是head==NULL,带头结点是head->next==NULL

设带有头结点的单向循环链表的头指针变量为head,则其判空条件是

head->next==heado

⑳设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的

条件是只有一个孩子节点（或高度等于其结点数）。

①设指针变量front表示链式队列的队头指针，指针变量rear表示链式队

列的队尾指针，指针变量s指向将要入队列的结点X,则入队列的操作序列为

（注意：入队要从队尾入）

rear->next=s;rear=so

②设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X,

则进行插入操作的语句序列为s->next=p->next;p->next=s（设结点的指针

域为nextX

③设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列

为空的条件为F==R

④设二叉树中结点的两个指针域分别为Ichild和rchild,则判断指针变量

P所指向的结点为叶子结点的条件是

p->lchild==NULL&&p->rchild==NULLo

⑤散列表中解决冲突的两种方法是开放定址法和链地址法。

⑥设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为

top=top->next;

若指针变量top指向当前顺序栈的栈顶，则删除栈顶元素的操作序列为

top=top-l

⑦设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点

X,则在结点A的后面插入结点X的操作序列为

s->left=p;s->right=p->right;p->right=s;p->right->left=s;

(设结点中的两个指针域分别为left和right'

⑧解决散列表冲突的两种方法是开放定址法和链地址法。

⑨设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X,

则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next;

p->next=s。

⑩设指针变量head指向双向链表中的头结点，指针变量p指向双向链表

中的第一个结点则指针变量p和指针变量head之间的关系是p-head->rlink

和head=p->llink(设结点中的两个指针域分别为llink和rlinkX

⑪设指针变量p指向双向链表中结点A指针变量s指向被插入的结点X,

则在结点A的后面插入结点X的操作序列为

s->left=p;s->right=p->right;p->right->left=s;p->right=s;o

⑫设散列表中有m个存储单元，散列函数H(key)=key%p,则p最好

选择小于等于m的最大素数。

⑬设顺序线性表的长度为30,分成5块，每块6个元素，如果采用分块查

找，则其平均查找长度为6.5。

设分块查找中将长为n的表分成均等的b个块，每块s个元素，则b=

(n/s)上取整。

如果索引表中采用顺序查找，则ASL=(b+1)/2+(s+1)/2;

如果索引表中采用折半查找，则ASL=(s+l)/2+log2(b+l)-l;

⑭设指针p指向单链表中结点A,指针s指向被插入的结点X,则在结点

A的前面插入结点X时的操作序列为：

s->next=p->next;2)p->next=s;3)t=p->data;

p->data=s->data;5)s->data=t;

⑮设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列

双向循环链表存储方式最节省运算时间。

如果只是插入元素，单向循环列表就可以了；

如果还需要删除元素，就要双向循环列表，可以最快的找到尾节点的前一

个节点。

⑰有N个关键字排序，各排序最大最小情况如下：

⑱快速排序算法的平均时间复杂度为O(nlog2n)直接插入排序算法的平

均时间复杂度为。6人2)。

⑲设一棵m叉树脂的结点数为n,用多重链表表示其存储结构，则该树中

有n(m-l)+l个空指针域。

【注解】m叉树n个结点，得出总的指针域为m*n,不为空的指针域就等

于分枝数，根结点没有分支指向它，推出非空指针域为n-1，总指针域减非空指

针域就等于空的指针域即m*n-(n-1)

⑳设指针变量p指向单链表中结点A,则删除结点A的语句序列为：

q=p->next;p->data=q->data;p->next=q->next;feee(q);

①数据结构从逻辑上划分为三种基本类型：线性结构，树型结构和图型

结构。

②设无向图G中有n个顶点e条边：则用邻接矩阵作为图的存储结构进行

深度优先或广度优先遍历时的时间复杂度为0(nA2);

用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度

为O(n+e)o

③邻接表是图的一种链式存储结构。

④树最适合用来表示元素之间具有分支层次关系的数据。

⑤在一个单链表中，若要删除由指针q所指向结点的后继结点(若存在),

则执行p=q->next;q->next=p->next操作。

⑥常对数组进行的两种基本操作是索引和修改。

⑦在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和

p之间插入s所指结点，则执行q->next=s;s->next=p操作。

⑧设有两个串p和q,求q在p中首次出现的位置的运算称作模式匹配。

⑨一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有

n=2m-l成立。

⑩实现图的广度优先搜索遍历算法需要使用队列，深度优先搜索遍历算法

需要使用栈。

⑪顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻

的元素的物理位置不一定相邻。

⑫树的先序对应二叉树的先序，树的后序对应二叉树的中序。

⑬在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为：0(1)。

⑭设SQ为循环队列，存储在数组d[m]中，则SQ出队操作对其队头

指针front的修改是front=(front+l)%m。

对于一个以顺序实现的循环队列,队头、队尾指针分别为f、

,其判空的条件是判满的条件是

rr=f,(r+l)%m=fo

①设计一个判别表达式中括号是否匹配出现的算法，采用栈的数据结构

最佳。

②设广义表L=((a,b,c)),则L的长度为1,深度为2。

③衡量查找算法效率的主要标准是平均查找长度。

④栈和队列都是限制存取点的线性结构。

⑤在稀疏矩阵的三元组M序表中，每个三元组表示矩阵中非零元素的行号、

列号和数据值。

⑥顺序结构逻辑上相邻的结点物理上也是相邻的。因此，其存储密度大，

存储空间利用串高。

⑦含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为n+1,

非空指针个数为

n-lo

⑧在数据结构中，从存储结构上可以将之分为顺序存储和非顺序存储；从

逻辑结构上可以将之分为线性结构和非线性结构。

⑨深度优先遍历类似二叉树的先序遍历；广度优先遍历类似二叉树的层

次遍历。

⑩n个顶点的有向图最多有n(n-l)条边;无向图最多有n(n-l)/2条边。

⑪如果要求用线性表既能较快地查找，又能适应动态变化的要求，则可采用

分块查找。

⑫任意一棵二叉树的叶子结点在其先序、中序和后序序列中的相对位置

不发生变化。

⑬在单链表指针为p的结点之后插入指针为s的结点，正确的操作是

s->next=p->next;p->next=so

⑭某算法的时间复杂度是0(n人2),表明该算法的执行时间与r«A2成正

比。

⑮对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头

向量的大小为n,占用的存储空间为2eo

⑯对于顺序表，访问某结点的时间复杂度为0(1),删除某结点的时间复

杂度为0(n)。

©以数据集｛4,5,6,7,10,12,18｝为结点权值，画出构造的哈弗曼树，并计算

其带权路径长度。

⑱广义表(a,(b,c),d,e)的表头为ao

已知广义表L=(a,(b,(c,(d)),e),f),则：

Ll=Tail(L)=((b,(c,(d)),e),f)

L2=Head(Ll)=(b,(c,(d)),e)

L3=Tail(L2)=((c,(d)),e)

L4=Head(L3)=(c,(d))

L5=Head(L4)=c

⑲树最适合用来表示的结构是元素间具有分支层次关系的结构。

⑳图G是一个非连通无向图，共有28条边，则该图至少有9个顶点。

①栈的特点是一个线性结构，数据先进后出，且只能在栈顶进行增删操作。

②与数据元素本身的形式、内容、相对位置、个数无关的是数据的逻辑结

构。

③数据结构被形式定义为(D,R),其中D是数据元素的有限集合，R是

D上的关系有限集合。

④当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空,

则向这个栈插入一个元素时，首先应执行top一语句修改top指针。

⑤设有一个字符串S="abcdefgh",问该串的最大子串个数为37。

⑥若StrIndex(S,T)表示求T在S中的位置的操作则对于S="Beijingand

Nanjing",T="jing",StrIndex(S,T)的结果为4。

⑦字符串按存储方式可以分为：顺序存储、链接存储和堆分配存储。

⑧在C语言中，以字符\0表示串值的终结。

⑨A[N,N]是对称矩阵，将下三角(含对角线)以行序存储到一维数组

arr[N(N+l)/2]中,则对任一上三角元素arr[i,j]对应arr[k]的下标k是：解析如

下

⑩有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2个

字节，则用三元组表示该矩阵时，所需的字节数是66。

⑪已知广义表LS=((a,b,c),(d,e,f)),对其运用Head和Tail运算，

取出其中原子e的运算是Head(Tail(Head(Tail(LS))))

⑫画出广义表((((a),b)),(((),d),(e,f)))的链式存储结构图示。

⑬引入二叉线索树的目的是加快查找结点的前驱或后继的速度。

⑭利用二叉链表存储一般树，则根结点的右指针是空；因为左孩子右兄

弟，根节点无兄弟。

⑮深度优先遍历类似于二叉树的先序遍历；广度优先遍历类似于二叉树

的层次遍历。

⑯用邻接表表示图进行广度优先遍历时，通常借助队列来实现算法。

用邻接表表示图进行深度优先遍历时，通常借助栈来实现算法。

©拓扑排序方法可以判断出一个有向图是否有环。

⑱图中的一条路径长度为k,该路径所含的顶点数为K+1。

⑲数据的最小单位是数据项。

⑳设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单

链表仍然保持有序，则该操作的时间复杂度为

O(n)o

①在图的邻接表中用顺序存储结构存储表头结点的优点是可以随机访问

到任意点的简单链表。

②设一棵m叉树中度数为0的结点数为NO,度数为1的结点数为

NI.........度数为m的结点数为Nm,则N0=l+N2+2N3+3N4+......

+(m-l)Nm„

③设有一个n阶的下三角矩阵A,如果按照行的顺序将下三角矩阵中的

元素(包括对角线上元素)存放在n(n+l)个连续的存储单元中，则A[i][j]与

A[0][0]之间有i*(i+l)/2+j-l或i*(i+l)/2+i个数据元素。

④设一条单链表的头指针变量为head且该链表没有头结点，则其判空条

件是

head==0o

head为指向表头结点的指针，分别写出带有头结点的单链表、单项循环链

表和双向循环链表判空的条件：

单链表NULL==head->next

单向循环head==head->next

双向循环head==head->next&&head==head->prior

⑤head为指向表头结点的指针，分别写出不带有头结点的单链表、单项

循环链表和双向循环链表判空的条件：

单链表NULL==head

单向循环head==head->next

双向循环head==head->next&&head==head->prior

⑥设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列

为空的条件为F==R。

⑦散列表中解决冲突的两种方法是开放地址法和链接法。

⑧设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列

为

top=top->nexto

⑨设关键字序列为(KI,K2,Kn),则用筛选法建初始堆必须从第n/2

个元素开始进行筛选。

⑩建立一个长度为的有序单链表的时间复杂度为A

nO(n2)o

设顺序表的长度为则顺序查找的平均比较次数为

⑪n,(n+l)/2o

⑫设顺序线性表的长度为30,分成5块，每块6个元素，如果采用分

块查找，则其平均查找长度为6.5。

⑬在堆排序中，对n个记录建立初始堆需要调用n/2次调整算法。

⑭已知一棵完全二叉树中共有768结点则该树中共有384个叶子结点。

⑮一个一维数组a[10]中存储着有序表(15,26,34,39,45,56,58,63,74,76),

根据折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等

概率情况下进行成功搜索时的平均搜索长度。度为1的结点个数：3;平均搜索

长度:29/10.

⑯一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度

为

O(l)o

解析：数组是随机访问的数据结构，平均时间复杂度为。(1)

⑰含n个顶点的无向连通图中至少含有n-1条边。

⑱顺序表中，逻辑上相邻的元素，其物理位置也相邻，在链表中，逻辑上相邻

的元素，其物理位置不一定相邻。

⑲利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组

元素对应一个非零元素的行号、列号和值。

⑳数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储(或存储结

构)无关，是独立于计算机的。

①区分循环队列的满与空，有三种方法，它们是少用一个存储单元、设置

一个标志位和设置一个计数器。

②根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表

分成单链表和双链表。

③数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。

④最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的

条件是rear==front;队满条件是(rear+1)%n==front;当前队列中的元

素个数为

(rear-front+n)%no

⑤一个递归算法必须包括终止条件和递归部分。

⑥循环队列存储在数组中，则入队时的操作为rear=(rear+l)

mod(m+l)o

⑦设计一个判别表达式中左，右括号是否配对出现的算法，采用栈数据

结构最佳。

⑧元素的移动次数与关键字的初始排列次序无关的是：基数排序

元素的比较次数与初始序列无关是：选择排序

算法的时间复杂度与初始序列无关的是：直接选择排序

⑨若一个栈以向量V[1…n]存储，初始栈顶指针top为n+l,则下面x进

栈的正确操作是：

top=top-l;V[top]=xo

⑩利用带头结点的二叉链表存储树，则根结点的右指针是空。二叉链表：

左孩子右兄弟，根节点没有兄弟，所以为空。

⑪设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较h

次。

⑫入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的

情况。正确，链式存储结构是动态分配空间的。

⑬用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数

有关。图的邻接矩阵存储所占用空间大小只与顶点个数有关，更准确地说，设顶

点n个，则与rT2成正比

⑭设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂

度为0(1).

⑮堆是完全二叉树，完全二叉树不一定是堆。

⑯不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的

时间复杂度均为0(n)。

⑰设一组初始记录关键字序列(kl,k2.........kn)是堆，则对i=l,2，…，

而言满足的条件为

n/2ki<=k2i&&ki<=k2i+lo

⑱设一组初始记录关键字序列为(345,253,674,924,627),则用基

数排序需要进行3趟的分配和回收才能使得初始关键字序列变成有序序列。

⑲设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的

最多比较次数不超过Iog2n+lo

⑳画出广义表LS=((),(e)z(a,(b,c,d)))的头尾链表存储结构。

21设散列表的地址范围是［0...9］,散列函数为H(key)=(key2+2)

MOD9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入

散列表的存储结构。

H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=Hf7)=6

①二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。

在有序表上进行二分杳找时的查找长度不超过二叉判定树的高度1+Iog2n。

②设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列

双向循环链表存储方式最节省运算时间。

③将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是

n次，最多2n-l次。

④循环队列存储在数组中，则入队时的操作为

rear=(rear+l)%(m+l)o

入队是：rear=(rear+l)%(m+l)〃m+l代表有m+1个空间它是0

到m的数组

出队是：front=(front+1)%(m+1)

⑤循环队列放在一维数组AO..M-1］中，endl指向队头元素，end2指向

队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能

容纳M-1个元素。初始时为空。则队空：endl==end2;队满:

endl==(end2+l)modM

⑥一个栈的入栈序列为1,2,3，…，n,其出栈序列是pl,p2,p3...,

若则可能取值的个数是

pnop2=3,p3n-1;

⑦图的BFS生成树的树高小或相等DFS生成树的树高。

【例题】线性表(al,a2,..„an)采用顺序存储结构。试问：

(1)在等概率的前提下，平均每插入一个元素需要移动的元

素个数为多少？

(2)若元素插在ai与ai+1之间(04isn-1)的概率为，

则平均每插入一个元素所要移动的元素个数又是多少？

①线性表的顺序存储结构是一种随机存取的存储结构，线性结构的链式

存储是一种顺序存取的存储结构。

②数据结构是一门研究非数值计算的操作对象以及它们之间的关系和

运算等的学科。

③一个数据结构在计算机存储器内的表示称为存储结构。

④链栈和顺序栈相比较，有一个较为明显的优点是通常不会出现栈满的情

况。

⑤引入循环队列的目的是为了克服"假溢出"现象。

⑥区分循环队列的满与空，只有两种方法，它们是牺牲一个存储单元和

设标记。

⑦设循环队列存放在向量data[O…M]中，则队头指针front在循环意义下

的出队操作可表示为front=(front+l)%(M+l),若用牺牲一个单元的办法来区

分队满和队空(设队尾指针则队满的条件为

rear),front==(rear+l)%(M+l)o

⑧对于长度为n且顺序存储的线性表，在任何位置上操作都是等概率的情

况下，插入一个元素需要平均移动表中的元素个数；删除一个元素平均需要移

动表中元素。

⑨在一个不带头结点的单链表中，在表头插入或删除与在其他位置上插入

或删除其操作过程不相同。

⑩在线性表的顺序存储中，元素之间的逻辑关系是通过存储位置决定的；

在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。

⑪单链表表示法的基本思想是用指针表示结点的逻辑关系。

⑫数据的逻辑结构是指数据元素间的逻辑关系，数据的存储结构是数据在

计算机中的表示(又称映像)方法，是数据的逻辑结构在计算机中的存储实现。

⑬数据的物理结构包括数据元素的表示和数据元素间关系的表示。

⑭程序=数据结构+算法。

⑮线性表L=(al,a2，…,an)用数组表示，假定删除表中任一元素的概率相

同，则删除一个元