第三章数据结构与算法

第三章数据结构与算法

.3.1线性结构

•3.1.1线性表

•L线性表的定义

•一个线性表是n个元素的有限序列(nNO),通常表示为(al,a2,a3.........an).

•2、线性表的JI顺序存储(11度序表)

•是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两

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

•优点：可以随机存取表中的元素，按序号直找元素的速度很快.

•缺点：插入和删除操作需要移动元素。

•3、线性表的链式存储(链表)

•是指用节点来存储数据元素，元素的节点地址可以连续，也可以不连续。节点空间只有在

需要时才申请，无需事先分配。

•优点：插入和删除操作不需要移动元素

•缺点：只能按JII页序访问元素，不能进行随机存取。

•链表的类别

•单链表

•循环链表

•双链表

•3.1.2栈

•栈和队列都是一种特殊的线性表，栈是按"后进先出"的规贝L进行操作的。

•(1)顺序栈：用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素。存储空间是预先

定义或申请的，因此可能会出现栈满的情况。每一个元素入栈时都要判断栈是否已满。需要设

置一个沿旨针指到栈顶。需要附设指针top指示栈顶元素的位置。

•(2)链栈：用链表存储栈中的元素.栈中元素的插入和删除仅在栈顶进行，因此不必设置头节

点，链表的头指针就是栈顶指针。

•3.1.3队列

•队列是一种“先进先出"的线性表，队尾入队头出。

•队列的M页序存储

•⑴期队列

•(2)循环队列

•队列的链式存储(链队列)

•为了便于操作，可以给链队列添加一个头节点，并令头指针指向头节点。队列为空的判定

条件就是头指针和尾指针的的值相同，并且均指向头节点.

.3.1.4串

•字符串是一串文字及符号的简称，是一种特殊的线性表。

•字符串的基本数据元素是字符，常常把一个串作为一个整体来处理。

•串是仅由字符构成的有限序列，是取值范围受限的线性表.一般记为S='ala2…an滇中S是

串名，单引号括起来的字符序列是串值。

•串长：即串的长度，指字符串中的字符个数。

•空串:长度为0的空串，空串不包含任何字符。

•空格串：由一个或多个空格组成的串。

•子串：由串中任意长度的连续字符构成的序列称为子串。

•串相等：指两个串长度相等且对应位置上的字符也相同。

•串比较：两个串比较大小时以字符的ASCH码值作为依据。

•串的存储结构

•(1)顺序存储：用一组地址连续的存储单元来存储串值的字符序列。

•(2)链式存储：字符串可以采用链表作为存储结构，当用链表存储串中的字符时，每个结

点中可以存储一个字符，也可以存储多个字符。

•3.2数组和矩阵

•3.2.1数组

•一维数组是长度固定的线住表,数组中的每个数据元素类型相同。n维数组是定长线性表任维

数上的扩张，即线性表中的元素又是一个线性表。

•由于数组一般不做插入和删除，目元素个数和元素之间的关系不再发生变动，那么数组适合采

用顺序存储结构。

•数组元素的存储方式及相关计算：二维数组的存储结构可分为以行为主序(按行存储)和以列

为主序(按列存储)两种方法。

•设每个数据元素占用L个单元，m、n为数组的行数和列数，那么：

•以行为主序优先存储的地址计算公式为：

•Loc(aij)=Loc(all)+((i-l)xn+(j-l))xL

•以列为主序优先存储的地址计算公式为：

•Loc(aij)=Loc(all)+((j-l)xm+(i-l))xL

.3.2.2矩阵

•特殊矩阵的压缩存储的问题

•对多个值相同的元素可以只分配一个存储单元，零元素不分配存储单元.

•下面主要讨论对称矩阵、三对角矩阵、稀疏矩阵。

•(1)对称矩阵

•若矩阵Anxn中的元素有aij=aji(1。，j<n)的特点，则称之为对称矩阵。

a11,a12»a13»a14、1,3,5,12

a21>a22,a23>a243,10,9,8

a31>a32»a33>a345,9,7,6

a41>a42»a43>a4412,8,6,13

•则矩阵Anxn的n2个元素可以压缩存储到可以存放n(n+l)/2个元素的存储空间中。

•假设以行为主序存储下三角(包括对角线)中的元素，并以一个一维数组B[n(n+l)/2]作

为n阶对称矩阵A中元素的存储空间，则B[k](0<k<n(n+l)/2)与矩阵元素之间存

在-对应关系

1券当立〕

心但+一当y

•(2)三对角矩阵

•对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，其余的矩阵元

素都为零。

•下囿主要考虑三对角矩瘁，即只有主对角线及其左右两边为非零兀素。-若以行为主序将n

阶三对角矩阵Anxn的非零元素存储在一维数组B[k](0<k<3n-2)中，则元素位置之间

的对应关系为:k=3x(i-l)-l+j-i+l=2i+j-3(l<ij<n)

•(3)稀疏矩阵

•在一个矩阵中,若非零元素的个数远远少于零元素的个数，且三嗜元素的分布没有规律，

则称之为稀疏矩阵。

•可以用一个三元组(ijaij)唯一确定矩阵中的一个元素。

512,

9,0,0,0,0I(1,2,12),(1,3,9)

0,0,0,0,0,0,0

-3,0,0,0,0,14,0(3,1,-3),(3,6,14)

0,0,24,0,0,0,0(4,3,24)

0,18,0,0,0,0,0(5,2,18)

力，0,0,70,0,'(6.1,15),(6,4,-7)

•3.3树和二叉树

•33.1树及二叉树的定义

•树

•定义：树是n(*0)个结点的有限集合。当n=0时称为空树。在任一非空树中,有且仅有

一个称为根的结点：其余结点可分为m(m1)个互不相交的有限集T1,T2…,Tm,其中每个

集合又都是一棵树，并且称为根结点的子树。

•33.2树的相关概念

•树的相关概念

•L双亲、孩子和兄弟

•2、结点的度：一个结点的子树的个数记为该结点的度。

•3、叶子结点：也称为终端结点，指度为零的结点。

•4、内部结点：度不为零的结点称为分支结点或^终端结点.除根结点之外，分支BCDE

FG结点也称为内部结点.

•5、结点的层次：根为第一层，根的孩子在第二层，依此类推。

•6、树的高度：一棵树的最大层次数记为树的高度(或深度).

•7、有序(无序)树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则

称该树为有序树,否则称为无序树。

•8、森林：m(m20)棵互不相交的树的集合。

•3.3.3二叉树的性质

•二叉树

•定义：二叉树是n(nNO)个结点的有限集合,它或者是空树(n=0),或者是由一个根结点及

两棵不相交的、分别称为左子树和右子树的二叉树所组成.

•树和二叉树的区别

•(1)二叉树中结点的子树要区分左子树和右子树，即使只有一棵子树，而树中不用区分。

•(2)二叉树中结点的最大度为2,而树中无限制。

•二叉树的性质

•1、二叉树第i()层上至多有2i-l个节点。

•2、深度为k的二叉树至多有2k-l个结点(kNl)。

•3、对任何一棵二叉树,若其终端结点数为nO,度为2的结点数为n2,则n0=n2+l。

•3.3.4满二叉树和完全二叉树

•满二叉树的定义：若深度为k的二叉树有2k-l个结点，则称其为满二叉树。

•完全二叉树：当深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二

叉树中编号为1~n的结点一对应时，称之为完全二叉树。

•3.3.5二叉树的存储结构

•二义树的存储结构

•(1)顺序存储

•(2)链式存储

•二叉树的遍历

•遍历是按某种策略访问树中的每个结点，且仅访问一次。

•依据访问根结点次序的不同，可分为前序遍历法、中序遍历法、后序遍历法。

•(1)中序遍历法：(左、根、右)A、中序遍历根的左子树。B、访问根结点。C、中序遍

历根的右子树。依此类睢。

•(2)前序遍历法：先访问根结点(根、左、右)

•(3)后序遍历法：后访问根结点(左、右，根)

•(4)层序遍历法：按层从上至下、每层从左至右的III页序遍历。

D根左边狎结点，先治历左边的「树।(}A{J

2)8左边为空,则先造历B.然后遍历B的石子树：B()A.)

3)B的右广树中.乂疗根结点D.D的左边仃结点,则先Gk；D：BGDA{

4)根结点A的左子树遍历完毕,再是A结点,而是A的行f树

5)右手M中,C的左边只有一个结点E,则先EA；C:BGDAEC{)

6〉C的右子树中.F的左右都只有一个鳍点.6是HFhBGOMCHFI

•3.3.6最优二叉树

•最优二叉树

•最优二叉树又称哈夫曼阿，是一类带权路径长度最短的树，

•权：是一个人为的概念，表示计算机对每个结点的访问频率。

•路径长度：是每一个结点到根结点的路径的长度。

•结点的带权路径长度：是指从该结点到根结点之间的路径长度与该结点权的乘积。

•树的带权路径长度为树中所有叶子结点的带权路径长度之和。

WPl=(2“*5+7)X2=36⑹WPl=(2+4)X3CX2+7X1=35(C)WPl，4+5)X3+7X2*2X1:43

•构造最优二叉树的哈夫曼方法

•(1)根据给定的n个权值｛wl,w2，…，wn｝构成n棵二叉树的集合F=｛T1,T2，…，Tn),

其中每棵树Ti只有一个带权为wi的根结点，其左右子树均空。

•(2)在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构

造二叉树的根结点的权值为其左、右子树根结点的权值之和。

•(3)从F中删除这两棵树，同时将新得到的二叉树加入到F中。重复(2)(3)步，直^

F中只含一棵树时为止，这棵树便是最优二叉树(哈夫曼树)。

•最优二叉树的一个应用是对字符集中的字符进行编码和译码。

•例：现在有一组权值｛30,25,15,22,8｝,下面我们来演示利用这组权值构造最优二叉树

(哈夫曼树)的过程。

•3.3.7二叉树的遍历

•3.3.8二叉查找树

•二叉查找树

•二叉查找树又称为二叉排序树。它或者是一棵空树，或者是具有如下性质的二叉树：

•(1)若它的左子树非空，则左子树上所有结点的关键码值均小于根结点的关键码值。

•(2)若它的右子树非空，则右子树上所有结点的关键码值均大于根结点的关键码值。

•(3)左、右子树本身就是两棵二叉直找树。

•对二叉查找树进行中序遍历，可得到一个关键码递增有序的结点序列。

•二叉查找树的作用：使用二叉查找树来有找树中的数值比普通的二叉树更为方便。

•3.4图

.3.4.1图的定义

•一个图G(Graph)是由两个集合：V和E所组成的，V是有限的非空顶点(Vertex)集合，

E是用顶点表示的边(Edge)集合，图G的顶点集和边集分别记为V(G)和E(G),而将

图G记作G=(V,E)。

•可以看出，一个顶点集合与连接这些顶点的边的集合可以唯一表示一个图。

•在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。

•3.4.2图的相关概念

•有向图：图中每条边都是有方向的。从顶点VI到顶点vj表示为，而从顶点vj到顶点VI表示为。

有向边也称为弧。起点称为弧尾，终点称为弧头。

•左侧有向图a的顶点集合为:V(a)={l,2,3,4}边的集合为:E(a)={<l,2>,<1,3>,<4,

2>,<1,4>,<4,1>)

•无向图：图中每条边都是无方向的。顶点vi和vj之间的边用(vi,yj)表示。在无向图中，(vi,yj)和

(Yj,vi)表示的是同一条边。

•左侧无向图b的顶点集合为：V(b)={l,2,3,4,5}边的集合为：E(b)={(l,2),Q,3),Q,4),

(4,5),(2,3),(3,4)，⑶5)}

•完全图：若一个无向图具有n个顶点,而每一个顶点与其他n-1个顶点之间都有边，则称之为

无向完全图。显然，含有n个顶点的无向完全图共有n(n-l)/2条边，类似地，有n个顶点的

有向完全图中弧的数目为n(n-l),即任意两个不同顶点之间都存在方向相反的两条弧

•度

•出度和入度

•路径

•子图

•连通图

•强连通图

•网

•3.5排序算法

•3.5.1直接插入排序

•直接插入排序

•具体做法是：在插入第i个记录时，RI,R2........Ri-1已经排好序，将记录Ri的关键字

ki依次与关键字ki-1,ki-2，…，kl进行比较，从而找到Ri应该插入的位置，插入位置及

其后的记录依次向后移动。

•待排序列：3512672951

•第1步：35

•第2步：1235

•第3步：123567

•第4步：12293567

•第5步：1229355167

•3.5.2冒泡排序

•冒泡排序

•首先将第一个记录的关耀字和第二个记录的关键字进行比狡，若为逆序，则交换两个记录

的值，然后比较第二个记录和第三个记录的关键字，依此类推。

•待^序歹！I：3512672951

•第一次冒泡排序：

•①：1235672951

•②：1235672951

•③：1235296751

•(4):1235295167

•第二次冒泡排序：

•①：1235295167

•②：1229355167

•3.5.3简单选择排序

•简单选择排序

•n个记录进行简单选择排序的基本方法是：通过n-i次关键字之间的比较,从n-i+1个记录中

选出关键字最小的记录，并和第i(l<i<n)个记录进行交换，当i等于n时所有记录有序排列。

•待^序列：3512672951

•①：找出最小值12,与第一个关键字进行交换：1235672951

•②：找出剩下4个记录中的最小值29,与第二个关键字交换：1229673551

•③：找出剩下3个记录中的最小值35,与第三个关键字交换：1229356751

•④：找出剩下2个记录中的最小值51,与第四个关键字交换：1229355167

•3.5.4希尔排序

•希尔排序

•希尔排序又称“缩小增量排序"，是对直接插入排序方法的改进。

•先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的

记录基本有序时，再对全体记录进行一次直接插入排序。

•待排序列：48376496751226485403

•dl=5（距离为5的倍数的记录为同一组）：48376496751226485403dl=5

•排序后：12264854034837649675

•d2=3（距离为3的倍数的记录为同一组）:12264854034837649675d2=3

•排序后：12034837264854649675

•d3=l（距离为1的倍数的记录为同一组，即所有记录为一组）：120348372648

54649675d3=l

•排序后：03122637484854647596

•3.5.5快速排序

•快谢师

•通过一趟HE序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录

的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录继续进行快速排序，从而

使整个序列有序

•具体做法：附设两个位置指示变量i和j,它们的初值分别指向序列的第一个记录和最后一个记录。

设枢轴记录（通常是第一个记录）的关键字为pivot,则首先从j所指位置起向前搜索，找至悌

一个关键字小于pivot的记录时将该记录向前移到i指示的位置，然后从i所指位置起向后搜索,

找到第一个关键字大于pivot的记录时将该记录向后移到j所有位置，重复该过程直至i与j相

等为止。

•3.5.6堆排序

•堆排序（HeapSort）是一种基于堆这种数据结构所设计的排序算法。

•堆是一个近似完全二叉树的结构,并同时满足堆积的性质：即子结点的键值或索引总是小于

（或者大于）它的父节点。

•堆排序的基本思想是将待排序的序列构造成一个大顶堆或小顶堆，此时整个序列的最大值（或

最小值）就是堆顶的根节点。接下来，将其与末尾元素进行交换，此时末尾就为最大值。然后

1糠余n-1个序列重新构造成一个堆，这样会得到n个元素中的次大值。如此反复执行,便能

得到一个有序序列了。

•3.5.7归并排序

•一句话总结

•1、直接插入排序：按顺序插入待排关犍字，插入时依次查找位置，直接插入，后面的依次后移。

•2、冒泡排序：依次把相邻的两个记录进行比较，然后交换位置。

•3、简单选择排序：每次选择最小的，与第一个没有排过序的记录交换。

•4、希尔排序：间隔若干个空的记录分为一组，进行直接插入排序，依次将间隔缩小到1为止。

•5、快渤E序：设两个指针指示头尾，从尾开始，首尾交替轮流和枢轴记录（第一个记录）进行

I：匕较，并交换位置。

•6、堆排序：反复将待排序列建立成堆，并取堆顶。

•7、归并排序：两两归并为一组,再四个记录归并为一组，依此类推。

•总结与比较

1排序方法最好时间|平均时间最坏时间辅助空间检定性

直接插入排序0(n)OM)。(20(1)也定

简单选择排序0(20(M)。(20(1)不程定

甘泡排序0(n)0(由。(20(1)板定

希尔排序—0（n】巧—。⑴不稔定

快速排序。(。。密力〜。（）不稳定

O(nlog2n)O(nlog2n)2n

堆排序

O(nlog2n)O(nlog2n)O(nlog2n)0(1)不稳定

归并排序O(nlog2n)O(nlog2n)O(nlog2n)0(n)卷定

•3.6查找算法

•查找表及查找效率

•查找表定义：是指由同一类型的数据元素（或记录）构成的集合。

•静态查找表：只进行"直询"和"检索"操作。

•动态查找表：除了直询和检索外可能还会进行插入和删除操作。

•关键字：是数据元素（或记录）的某个数据项的值，用它来识别（标识）这个数据元素（或记录）。

•查找：根据给定的某个值，在直找表中确定是否存在一个其关键字等于给定值的记录或数据元

素.

•平均查找长度（ASL）:对于查找算法来说，其基本操作是"将记录的关键字与给定值进行比

较"。因此，通常以"其关键字和给定值进行匕瞰的记录个数的平均值”作为衡量查找算法好

坏的依据。

•3.6.1顺序查找

•从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定

值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查

找失败。

•直找效率低，但是算法简单且适应面广。

•362折半食找（二分食找）

•基本思想：先令查找表中间位置记录的关键字和给定值匕蹶，若相等，则查找成功；若不等，

则缩小范围，直至新的直找区间中间位置记录的关键字等于给定值或者直找区间没有元素时

（查找不成功）为止。

•这种方法要求查找表进行顺序存储并且按关键字有序排列。

•查找效率比顺序查找要高，但要求关键字有序排列。

•适用于表不易变动，且又经常进行查找的情况。

•折半查找断定树

•从折半杳找的过程来看，可以用一棵二叉树来描述。通常称这个描述折半查找二叉树的过

程称为折半查找判定树，

•363索引顺序查找(分块查找)

•是对JII页序查找的一种改进

•将表分成若干块，每一块中的关键字不一定有序，但块之间是有序的。

•3.6.4树表查找

•二叉查找树是一种动态查找表，表结构本身是在查找过程中注态生成的。

•设关键字序列为｛46,25,54,13,29,91)

46

2554

132991

构造的二叉杳找柯

•3.6.5哈希查找

•前面几种查找方法中，记录的存储位置和关键码之间不存在碓定的关系，因此查找时都要建立

在对关键字进行比较的基础之上。

•哈希函数：关键字作为自变量，关键字存放的地址作为因变量。Hi=Hash(Key)

•这一映射过程称为哈希造表或散列,所得的存储位置称为哈希地址或散列地址。

•冲突：对于某个哈希函数Hash和两个关键字K1和K2,如果K10K2而Hash(Kl)=Hash(K2),

则称出现了冲突。-采用哈希法主要考虑的两个问题是哈希函数的构造和冲突的解决。

•冲突的处理

•(1)开放定址法：Hi=(Hash(key)+di)%mi=l,2，…,k(k<m-l)

•其中,Hash(key)为哈希函数,m为哈希表的表长，di为增量序列。常见的增量序列有如

下三种：

•di=l,2,3，…,m-1,称为线性探测再散列。

•€11=12,-12,22,-22,32，…,±k2(k<m/2),称为二次探测再散列。-di=伪随机序列，称为随

机探测再散列。

•例：设关健码序列为47,34,19,12,52,38,33,57,63,21,哈希表表长为13,

哈希函数为Hash(key)=keymod11,用线性探测法解决冲突构造哈希表.

•(2)链地址法：它将具有相同哈希函数值的记录组织成一个链表，当链域的值为NULL时,

表示已没有后继记录°・地址里存放的是指针，而不是关键字，将哈希函数值相同的记录组

成一个链表

•例：哈希表表长为11,哈希函数为hash(key)=keymod11,对于关键码序列为47,

34,12,52,38,33,27,3,使用链地址法构造哈希表。

•真题

•12年第21题

•对于二维数组中的一个元素a[ij](lsi、jsN),存储在之前的元素个数()。

•A.与按行存储或按列存储方式无关

•B.在i=j时与按行存储或按列存储方式无关

•C.在按行存储方式下比按列存储方式下要多

•D.在按行存储方式下比按列存储方式下要少

•解析

•B

•18年第8题

•设有n阶三对角矩阵A,即非零元素都位于主对角线以及与主对角线平行且紧邻的两条对角线

上，现7寸该矩阵进行按行压缩存储，若其压储空间用数组B表示，A的元素下标从0开始，

B的元素下标从1开始。已知A[0,0]存储在B[l],A[n-Ln-l]存储在B[3n-2],那么非零元素

A[ij](O<i<n,O<j<n,li-j|<l)存储在B[()]

•A.2i+j-lB.2i+jC.2i+j+lD.3i-j+l

•解析

•C

•18年第9题

•用哈希表存储元素时，需要进行冲突(碰撞)处理，冲突是^旨()。

•A.关键字被依次映射到地址编号连续的存储位置

•B.关键字不同的元素被映射到相同的存储位置

•C.关键字相同的元素被映射到不同的存储位置

•D.关键字被映射到哈希表之外的位置

•解析

•B

•19年第5题

•令序列X、Y、Z的每个元素都按顺序进栈，且每个元素进栈和出栈仅一次。则不可能得到的

出栈序列是（）.

•A.XYZB.XZYC.ZXYD.YZX

•解析

•C

•19年第6题

•以下关于单链表存储结构特征的叙述中，不正确的是（）.

•A.表中结点所占用存储空间的地址不必是连续的

•B.在表中任意位置进行插入和删除操作都不用移动元素

•C.所需空间与结点个数成正比

•D.可随机访问表中的任一结点

•解析

•D

•19年第7题

•B-树是一种平衡的多路查找树.以下关于B-树的叙述中，正确的是（）。

•A.根结点保存树中所有关键字且有序排列

•B.从根结点到每个叶结点的路径长度相同

•C.所有结点中的子树指针个数都相同

•D.所有结点中的关键字个数都相同

•解析

•B

•A.根结点保存树中所有关键字且有序排列。这个叙述是不正确的。B-树的根结点并不保存

树中所有的关键字，而是保存了一部分关键字，并且这些关键字是有序排列的。

•B.从根结点到每个叶结点的路径长度相同。这个叙述是正确的。B-树的定义保证了从根结

点到每个叶结点的路径长度都是相同的，这是B-树保持平衡的关键特性之一。

•C.所有结点中的子树指针个数都相同。这个叙述是不正确的。B-树的不同结点中的子树指

针个数可能不同，这取决于该结点所在的层级和该结点所拥有的关键字数量。

•D.所有结点中的关键字个数都相同。这个叙述也是不正确的。B-树的不同结点中的关键字

个数可能不同，但每个结点中的关键字个数会遵循一定的范围，这个范围与B树的阶数

（即最大子树数）有关，

•19年第8题

•对于给定的关键字序列｛47,34,13,12,52,38,33,27,5｝若用链地址法（拉链法）解决冲突来构造哈

希表，且哈希函数为H（key）=key%ll,则（）»

•A.哈希地址为1的链表最长

•B.哈希地址为6的链表最长

•C.34和12在同一个链表中

•D.13和33在同T链表中

•解析

•C

•给定的哈希函数H(key)=key%11来计算每个关键字对应的哈希地址。

•计算每个关键字的哈希地址：

•47%11=10

•34%11=1

•13%11=2

•12%11=1

•52%11=7

•38%11=5

•33%11=0

•27%11=5

•5%11=5

•根据计算出的哈希地址，我们可以得到以下链表结构：

•哈希地址0:33

•哈希地址1:34->12

•哈希地址2:13

•哈希地址5:38->27->5

•哈希地址7:52

•哈希地址10：47

•现在，我们可以根据题目选项进行判断：

•A.哈希地址为1的隧表最长

•哈希地址为1的链表有两个元素(34和12),不是最长的。

•B.哈希地址为6的髓表最长

•哈希地址为6的链表是空的，所以这个选项不正确。

•C.34和12在同一个链表中

•确实，34和12的哈希地址都是1,所以它们在同一个链表中。

•D.13和33在同一个链表中

•13的哈希地址是2,而33的哈希地址是0,所以它们不在同一个链表中。

•19年第9题

•某有向图G的邻接表如下图所示，可看出该图中存在弧<V2,V3>,而不存在从顶点明出发的弧。

以下关于图G的叙述中，错误的是（）。

•A.G中存在回路B.G中每个顶点的入度都为1

•C.G的邻接矩阵是对称的D.不存在弧<V3M>

•解析

•C

•对称邻接矩阵意味着图是无向图。然而，根据邻接表，G是一个有向图（因为存在<v2,v3>

这样的有向弧），所以其邻接矩阵不可能是对称的。因此，C选项是错误的。

•19年第10题

•已知有序数组a的前10000个元素是随机整数，现需查找某个整数是否在该数组中。以下方法

中，（）的查找效率最高。

•A.二分查找法B.顺序查找法C.逆序查找法D.哈希查找法

•解析

•A

•A.二分查找法：这是一种在有序数组中查找特定元素的算法。每次查找都会将搜索空间减

半，因此效料E常高。对于包含10000个元素的数组，二分直找法大约需要进行

Iog2（10000）次比较，即大约14次比较就能找到目标元素或确定元素不存在。由于数组是

有序的，二分查找法是一个很好的选择。

•B.顺序查找法：这种方法会从头到尾遍历整个数组，直到找到目标元素或遍历完整个数组。

在最坏的情况下JII页序直找法需要进行10000次比较才能确定元素是否存在。因此，对于

大型有序数组"II页序查找法的效率相对较低。

•C.逆序查找法：通常逆序查找法并不是一种独立的直找方法，而是指从数组的末尾开始有

找。即使是从末尾开始，对于大型数组来说，其效率仍然与III页序查找法相近，因为都需要

遍历大部分或全部数组元素。因此，逆序查找法在效率上并不优于N页序查找法。

•D.哈希直找法：哈希查找法通过计算哈希值来直接定位元素在数组中的位置，其查找效率

通常非常高，接近于常数时间复杂度。然而，哈希直找法的前提是已经建立了哈希表，并

且哈希函数能够有效地将元素映射到唯一的位置。在这个问题中，并没有提到已经建立了

哈希表,因此哈希查找法可能不是最直接的选择。

•20年第5~7题

•在常见的数据结构中，（）是只能通过访问它的一端来实现数据存储和检索的一种线性数据结

构，它的修改遵循先进后出的原则；（）是一种先进先出的爱性表。（）是取值范围受限的线

性表。

•(5)A.链表B.队列C.栈D.串

•(6)A.链表B.队列C.栈D.串

•(7)A.链表B.队列C.栈D.串

•解析

•CBD

•20年第8题

•二叉树遍历是按照某种策略访问树中的每个节点，且仅访问一次。按照遍历左子树要在遍历右

子树之前进行的原则，根据访问()位置的不同，可得到二叉t对的前序、中序和后序三种遍历

方法。

•A.根节点B.导航节点C.叶子结点D.兄弟节点

•解析

•A

•20年第9题

•以下有关霍夫曼树的说法中，错误的是()。

•A.霍夫曼树又被称为最优二叉树

•B・霍夫曼树是一种带权路径长度最短的树

•C.具有n个叶子节点的权值为WtW2……,Wn的最优二叉树是唯一的。

•D.霍夫曼树可以用来进彳亍通信电文的编码和解码

•解析

•C

•霍夫曼树，也被称为最优二叉树，主要用于数据压缩中的编码,特别是用于构建霍夫曼编

码.这种树是根据给定的权值来构造的，目的是使得树的带权路径长度(WPL)最短。

•虽然对于给定的权值集合，存在一棵带权路径长度最短的二叉树(即霍夫曼树)，但这并

不意味着只有一棵这样的树。实际上，可能存在多棵具有相同最短带权路径长度的最优二

叉树.例如，对于某些特定的权值集合,可能有多种不同的方式构建霍夫曼树，而这些树

都会具有相同的WPL.

•20年第10题

•查找算法中，()要求查找表进行I顿序存储并且按照关键字有序排列，一般不进行表的插入和

删除操作。

•A.顺序查找B.折半杳找C.分块查找D.动态查找

•解析

•B

•21年第5题

•-个栈的输入序列为123,45不可能导到的输出序列是（）。

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

•解析

•B

•21年第6题

•（）算法是不稳定的排序算法.

•A.简单选择B.冒泡C.直接插入D.归并排序

•解析

•A

•简单选择排序是不稳定的排序算法。

•简单选择排序的思路是：设待排序的记录存放在数组中。第i趟从巾]开始，通过

次比较，从个记录中选出关键字最小的记录，记为交换向和经过

n-in-i+1r[k],r[k]e

n-1趟，交换完成。

•21年第7题

•（）是一种先进先出的线性表，只允许在表的一端插入元素,而在表的另一端删除元素。

•A.栈B.队列C.串D.树

•解析

•A

•21年第8、9题

•一颗5层的二叉树，其最多有（）个结点，第5层最多有（）个结点。

•(8)A.15B.16C31D.32

•(9)A.15B.16C.31D.32

•解析

•CB

•对于一颗5层的二叉树，我们需要计算最多能有多少个节点，以及第5层最多有多少个节

点。

•首先，我们来看二叉树的性质。在二叉树中，第i层最多有2人（i-1）个节点。这是因为第一

层（根节点层）有1个节点（2人0）,第二层最多有2个节点（2人1）,第三层最多有4

个节点（2人2）,以此类推。

•对于整个二叉树来说，如果它有n层，那么它最多有2An-1个节点。这是因为每一层的

节点数相加，从第一层到第n层，形成一个等比数列的和，公式为：1+2+2人2+…+

A（）A

2n-l=2n-lo

•现在，我们来计算：

•(8)对于一颗5层的二叉树，其最多有多少个节点？

•根据公式2M-1,当n=5时，最多有2^5-1=31个节点。所以答案是C31.

•(9)第5层最多有多少个节点？

•根据二叉树的性质，第i层最多有2人(i-1)个节点。所以第5层最多有2人(5-1)=2人4=

16个节点。所以答案是B.16。

•21年第10题

•()排序又被称为缩小增量排序，是对直接插入排序方法的改进。

•A.简单选择B.冒泡C.快速D.希尔

•解析

•D

•D.希尔排序又被称为缩小熠量排序，是对直接插入排序方法的改进。希尔排序是稳定排

序算法，由DLShell于1959年提出。该方法的基本思想是将整个待排序列分割成若干个

子序列，然后分别进行直接插入排序，待整个序列中的元素基本有序时，再对全体元素进

行一次直接插入排序。因此，正确答案是D.希尔。

•22年第6题

•计算机在处理算术表达式78+21*(36-34)时,先将其转换成"()"的后缀形式表示，然后

利用()进行计算。

•(5)A.7821+36*34-B.78213634-*+C.78213634+*-D.3634-21*78+

•(6)A.栈B.队列C.数组D.串

•解析

•BA

•后缀形式的转换过程如下：

•先处理括号内的表达式：36-34得到2

•将2与乘号、21结合，执行乘法：21*2得到42

•将42与加号、78结合,执行加法：78+42得到120

•22年第7题

•依次在初始为空的队列中插入元素5、6、7、8以后，紧接着做了两次删除操作，此时的队头

元素是()o

•A.5B.6C.7D.