精华内容
下载资源
问答
  • 数据结构期末复习重点(仅供参考)看这一篇就够了~

    千次阅读 多人点赞 2021-01-02 21:59:13
    数据结构期末复习重点一、线性结构1、串的模式匹配(区分目标串和模式串、nextval数组值、KMP算法匹配过程)2、利用栈对表达式求值二、非线性结构1、树与二叉树2、图三、查找与排序1、查找哈希表查找(哈希表的基本...

    一、线性结构

    1、串的模式匹配(区分目标串和模式串、nextval数组值、KMP算法匹配过程)

    区分目标串和模式串、nextval数组值

    在这里插入图片描述

    KMP算法匹配过程:

    在这里插入图片描述

    2、利用栈对表达式求值

    将所给的表达式转换成后缀表达式的过程

    在这里插入图片描述

    然后解析后缀表达式,对表达式求值的过程

    在这里插入图片描述

    二、非线性结构

    1、树与二叉树

    (1)哈夫曼树(思想)、哈夫曼编码和带权路径长度求解
    思想:在n0个带权叶子节点构成的所有二叉树中,带权路径长度WPL最小的二叉树成为哈夫曼树或者是最优二叉树。
    (2)二叉树的先序、中序和后序遍历的思想和求解。
    先序(DLR):先遍历根,再遍历左子树,最后遍历右子树。
    中序(LDR):先遍历左子树,再遍历根,最后遍历右子树。
    后续(LRD):先遍历左子树,再遍历右子树,最后遍历根。

    例题:
    1.给定5个字符a~f,他们的权值集合W={2,3,4,7,8,9},是构造关于W的一颗哈夫曼树,求其带权路径长度,WPL和各个字符的哈弗曼编码。

    取两个最小的值相加形成新的权值。
    第一步
    在这里插入图片描述
    第二步
    在这里插入图片描述
    第三步
    在这里插入图片描述
    第四步
    在这里插入图片描述

    最终结果
    在这里插入图片描述
    这样哈夫曼树就被构造出来了。
    加上对应字符。
    在这里插入图片描述
    哈夫曼编码思想,从根节点出发,(根节点为零),在左边写0,右边写1。
    比如d:000(根左左)。根表示根节点。
    e:001(根左右)
    f:010(右左)
    c:0110(右右左)
    a:01110(右右右左)
    b:01111(右右右右)
    WPL求值思想,根节点为零层,对应字符的层数乘与对应的值然后相加。
    WPL=(2+3)*4+4 *3+(7+8+9)*2=80
    遵从,左小右大。数值小的放左边,数值大的放右边。相同的,谁先出现,在左边。
    纠正一个小错误:组件构成的新的树,放在元素最后面,所以数值9在新组成数值9的左边。

    2、图

    (1)图的存储结构(邻接矩阵表示、邻接表表示、邻接矩阵的特点(有向图))
    (2)图的遍历(DFS、BFS的算法思想和结合某种存储结构进行遍历求解)
    (3)图的最短路径(单源点):Dijkstra算法思想、最短路径求解,求解时一定要给出求解步骤。

    图的遍历

    图的遍历:从给定图中任意指定的顶点(成为初始点)出发,按照某种搜索方式沿着图的边,访问图中的所有顶点,是每一个顶点仅被访问一次。

    深度优先遍历:深度优先遍历简称DFS(Depth First Search)

    广度优先遍历:广度优先遍历简称BFS(Breadth First Search)

    例题:
    1.在某交通运输网络中有8个城市,城市的分布情况如图1所示,顶点1-8分别表示8个不同的城市,城市间的交通路线用有向边表示,边上的数值代表城市间的距离权重。请完成以下操作:
    (1)写出图1的邻接矩阵和邻接表;
    (2)结合邻接矩阵存储结构,写出从城市1出发的一个深度优先遍历序列和一个广度优先遍历序列;
    (3)给出从城市1到其它城市的最短路径及最短路径长度;
    (4)求出图1的一个拓扑序列;
    (5)写出从城市1到城市8的关键路径。

    在这里插入图片描述

    1-1邻接矩阵

    在这里插入图片描述

    1-2邻接表

    在这里插入图片描述

    2-1深度优先遍历

    结果为:v1 v2 v3 v8 v4 v5 v7 v6
    结合邻接表理解。
    简单解析:v1下一个地址指向v2,v2下一个地址指向v3,v3下一个地址指向v8,v8下一个地址为null,返回到v3,v3都访问过了,返回到v2,v2里边v3,访问过了,访问v4,v4下一个地址是v5,v5指向v3,v3全都访问过,访问v7,v7指向v8,v8下一个地址为null,返回到…就是按这种思想进行遍历。

    2-2广度优先遍历

    结果为:v1 v2 v4 v6 v3 v5 v7 v8
    结合邻接表理解。

    简单解析:把v1当顶点,v1下一个地址指向v2,v2指向v4,v4指向v6,v6下一个地址为null,返回到v1的下一个地址的索引(也就是v2),把v2当顶点,v2下一个指向v3,v3指向v4,v4指向v5…知道所有顶点都被访问过一遍。

    三、查找与排序

    1、查找

    哈希表查找(哈希表的基本概念、3个因素、线性探测法解决冲突、哈希表的求解与建立)

    哈希表的基本概念:

    哈希表(hash table)又称三列表,其基本思路是,设要存储的元素个数为n,设置一个长度为m(m>=n)的连续内存单元,以每个元素的关键字ki(0<=i<=n-1)为自变量,通过一个称为哈希函数(hash function)的函数h(ki)吧ki映射为内存单元的地址(或下标)h(ki),并把该元素存储在这个内存单元中,h(ki)也成为哈希地址(hash address)。把如此构造的线性表存储结构称为哈希表。

    三个因素:
    ①哈希函数。
    ②处理冲突的方法。
    ③哈希表的装填因子。

    哈希函数的好坏首先影响出现冲突的频繁程度。
    假定哈希函数是“均匀的”,即不同的哈希函数对同一组随机的关键字,产生冲突的可能性相同。
    对同一组关键字,设定相同的哈希函数,则不同的处理冲突的方法得到的哈希表不同,它的平均查找长度也不同。
    若处理冲突的方法相同,其平均查找长度依赖于哈希表的装填因子。

    线性探测法
    线性探测法是从发生冲突的地址(设为d)开始,依次探测d的下一个地址(当到达下标为m-1的哈希表表尾时,下一个探测的地址是表首地址0),直到找到一个空闲单元为止(当m≥n时一定能找到一个空闲单元)。线性探测法的数学递推描述公式为:
    d0=h(k)
    di=(di-1+1) mod m (1≤i≤m-1)

    用线性探测解决冲突的例题:

    在这里插入图片描述

    解题过程如下:

    在这里插入图片描述
    构建哈希表:
    在这里插入图片描述
    在这里插入图片描述

    除留余数法:

    除留余数法是用关键字k除以某个不大于哈希表长度m的数p所得的余数作为希地址的方法。除留余数法的哈希函数h(k)为:
    h(k)=k mod p (mod为求余运算,p≤m) ,p最好是质数(素数)。

    采用除留余数法解决冲突例题:

    采用除留余数法哈希函数建立如下关键字集合的哈希表:{16,74,60,43,54,90,46,31,29,88,77}。
    除留余数法的哈希函数为:
       h(k)=k mod 13
    对构造的哈希表采用线性探测法解决冲突。
    解:h(16)=3,h(74)=9,h(60)=8,h(43)=4,
    h(54)=2,h(90)=12,h(46)=7,h(31)=5,
    h(29)=3 冲突
    d0=3,d1=(3+1) mod 13=4 冲突
    d2=(4+1) mod 13=5 仍冲突
    d3=(5+1) mod 13=6
    h(88)=10
    h(77)=12 冲突
    d0=12,d1=(12+1) mod 13=0
    建立的哈希表ha[0…12]如下表所示。
    在这里插入图片描述

    2、排序

    直接插入排序和折半查找(直接插入排序思想、折半查找的思想、直接插入排序和折半查找的求解过程)

    直接插入排序思想:

    假设待排序的记录存放在数组R[0…n-1]中。初始时,R[0]自成1个有序区,无序区为R[1…n-1]。从i=1起直至i=n-1为止,无序区的头元素,与有序的最后一个元素比较,一次从后往前比较,符合条件插入有序区,知道无序区元素个数为0.

    折半查找的思想:(效率较高)

    折半查找时, 先求位于查找区间正中的对象的下标
    mid,用其关键码与给定值k比较:
    Element[mid].key == k,查找成功;
    Element[mid].key > k,把查找区间缩小到表的前
    半部分,继续折半查找;
    Element[mid].key < k,把查找区间缩小到表的后半部分,继续折半查找。
    如果查找区间已缩小到一个对象,仍未找到想要查
    找的对象,则查找失败。

    例如:
    1.在关键字有序序列{2,4,7,9,10,14,18,26,32,40}中采用折半查找法查找关键字为7的元素。
    在这里插入图片描述
    折半查找的平均查找长度:
    在这里插入图片描述

    折半查找例题:
    1、折半查找有序表(4,6,10,12,20,30,50,70,88,100),若查找表中元素38,则它将依次与表中哪些元素比较大小,查找结果是失败。
    A. 20,30,50
    B. 20,70,50,30
    C. 20,70,30,50
    D. 30,20,50
    答案选 C
    2、折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素 __________比较大小。

    答案:28,6,12,20

    拓扑排序的思想:

    ①从有向图中选择一个没有前驱(入度为零)的定点并且输出他。
    ②从图中删去该顶点,并且删去从该顶点发出的全部有向边。
    ③重复上述两步,直到剩余的图中不再存在没有前驱的顶点为止。

    联系方式qq:1287440358 微信:Burial_DH

    展开全文
  • 数据结构期末复习资料,清华大学内部资料,对于应付考试的肯定有用啊,欢迎下载
  • 数据结构期末复习ppt

    2018-03-12 16:47:38
    数据结构期末复习ppt提纲,主要是对课程内容的重点概念回顾
  • 数据结构期末复习

    千次阅读 2020-03-14 15:27:09
    数据结构期末复习题目整理 主要是平时上课做题是PTA里面题目的整理,重点的易错题目有用不同颜色标出来 第一章 概论 1-1 NlogN​2​​和NlogN具有相同的增长速度。 (2分) T F 1-2 N​2​logN和NlogN​2​​具有相同...

    数据结构期末复习题目整理

    浙江财经大学 软件工程专业课之数据结构 期末题库整理
    主要是平时上课做题是PTA里面题目的整理,重点的易错题目有用不同颜色标出来
    文件链接://download.csdn.net/download/weixin_44382897/12249016

    第一章 概论

    1-1
    NlogN​2​​和NlogN具有相同的增长速度。 (2分)
    T F
    1-2
    N​2​logN和NlogN​2​​具有相同的增长速度。
    1-3
    2​N​​和N​N​​具有相同的增长速度。 (2分)
    T F
    1-4
    算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 (2分)
    T F
    1-5
    算法可以没有输入,但是必须有输出。 (2分)
    T F
    1-6
    数据的逻辑结构是指数据的各数据项之间的逻辑关系。 (2分)
    T F
    1-7
    抽象数据类型与计算机内部表示和实现无关。 (2分)
    T F
    1-8
    算法和程序没有区别,在数据结构中二者是通用的。 (2分)
    T F
    1-9
    算法的优劣与算法描述语言无关,但与所用计算机有关。 (2分)
    T F
    1-10
    数据结构包括数据对象集以及它们的逻辑结构和物理结构,还包括与数据对象相关联的操作集,以及实现这些操作的高效的算法。 (2分)
    T F
    1-11
    算法独立于具体的程序设计语言,与具体的计算机无关。 (2分)
    T F
    第一章答案:TFFTT TFFFT

    第三章 线性结构

    2-1
    数组A[1…5,1…6]每个元素占5个单元,将其按行优先次序存储在起始地址为1000的连续的内存单元中,则元素A[5,5]的地址为:(2分)
    A.1120
    B.1125
    C.1140
    D.1145
    2-2
    对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度为:(1分)
    A.O(1), O(1)
    B.O(1), O(N)
    C.O(N), O(1)
    D.O(N), O(N)
    2-3
    在N个结点的顺序表中,算法的时间复杂度为O(1)的操作是:(2分)
    A.访问第i个结点(1≤i≤N)和求第i个结点的直接前驱(2≤i≤N)
    B.在第i个结点后插入一个新结点(1≤i≤N)
    C.删除第i个结点(1≤i≤N)
    D.将N个结点从小到大排序
    2-4
    若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用哪种存储方式最节省时间? (2分)
    A.双链表
    B.单循环链表
    C.带头结点的双循环链表
    D.顺序表
    2-5
    线性表若采用链式存储结构时,要求内存中可用存储单元的地址 (1分)
    A.必须是连续的
    B.连续或不连续都可以
    C.部分地址必须是连续的
    D.一定是不连续的
    2-6
    在具有N个结点的单链表中,实现下列哪个操作,其算法的时间复杂度是O(N)? (2分)
    A.在地址为p的结点之后插入一个结点
    B.删除开始结点
    C.遍历链表和求链表的第i个结点
    D.删除地址为p的结点的后继结点
    2-7
    某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用什么存储方式最节省运算时间? (2分)
    A.单链表
    B.仅有尾指针的单循环链表
    C.仅有头指针的单循环链表
    D.双链表
    2-8
    若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间? (2分)
    A.单链表
    B.双链表
    C.单循环链表
    D.带头结点的双循环链表
    2-9
    线性表L在什么情况下适用于使用链式结构实现? (1分)
    A.需不断对L进行删除插入
    B.需经常修改L中的结点值
    C.L中含有大量的结点
    D.L中结点结构复杂
    2-10
    对于一个具有N个结点的单链表,在给定值为x的结点后插入一个新结点的时间复杂度为 (2分)
    A.O(1)
    B.O(N/2)
    C.O(N)
    D.O(N​2​​)
    2-11
    链表不具有的特点是: (1分)
    A.插入、删除不需要移动元素
    B.方便随机访问任一元素
    C.不必事先估计存储空间
    D.所需空间与线性长度成正比
    2-12
    设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是:(2分)
    A.h=t; t->next=h->next;
    B.t->next=h->next; h=t;
    C.h=t; t->next=h;
    D.t->next=h; h=t;
    2-13
    在单链表中,若p所指的结点不是最后结点,在p之后插入s所指结点,则执行 (2分)
    A.s->next=p; p->next=s;
    B.s->next=p->next; p=s;
    C.s->next=p->next; p->next=s;
    D.p->next=s; s->next=p;
    2-14
    带头结点的单链表h为空的判定条件是: (2分)
    A.h == NULL;
    B.h->next == NULL;
    C.h->next == h;
    D.h != NULL;
    2-15
    对于一非空的循环单链表,h和p分别指向链表的头、尾结点,则有:(2分)
    A.p->next == h
    B.p->next == NULL
    C.p == NULL
    D.p == h
    2-16
    在双向循环链表结点p之后插入s的语句是: (3分)
    A.p->next=s; s->prior=p; p->next->prior=s ; s->next=p->next;
    B.p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;
    C.s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
    D.s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
    2-17
    在双向链表存储结构中,删除p所指的结点,相应语句为:(3分)
    A.p->prior=p->prior->prior; p->prior->next=p;
    B.p->next->prior=p; p->next=p->next->next;
    C.p->prior->next=p->next; p->next->prior=p->prior;
    D.p->next=p->prior->prior; p->prior=p->next->next;
    2-18
    将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表,那么可能的最少比较次数是: (2分)
    A.1
    B.N
    C.2N
    D.NlogN
    2-19
    Suppose that each entry in the array A[1…5,1…6] occupies 5 units of space. If all the entries are stored row by row in a consecutive piece of memory, with address starting from 1000, then the address of A[5,5] must be: (2分)
    A.1120
    B.1125
    C.1140
    D.1145
    2-20
    已知表头元素为c的单链表在内存中的存储状态如下表所示:

    现将f存放于1014H处,并插入到单链表中,若f在逻辑上位于a和e之间,则a、e、f的“链接地址”依次
    是:(2分)
    A.1010H, 1014H, 1004H
    B.1010H, 1004H, 1014H
    C.1014H, 1010H, 1004H
    D.1014H, 1004H, 1010H
    2-21
    有一个100阶的三对角矩阵M,其三对角元素m​i,j​​(1≤i≤100,1≤j≤100)按行优先次序压缩存入下标从0开始的一维数组N中。元素m​30,30​​在N中的下标是:(2分)
    A.86
    B.87
    C.88
    D.89
    2-22
    下面的叙述正确的是( )。 (2分)
    A.线性表在链式存储时,查找第i个元素的时间同i的值成反比
    B.线性表在链式存储时,查找第i个元素的时间同i的值无关
    C.线性表在顺序存储时,查找第i个元素的时间同i 的值成正比
    D.线性表在顺序存储时,查找第i个元素的时间同i的值无关

    单选题答案: 1-5 CBADD
    6-10 CBDAC
    11-15
    16-20ACCCD
    21-22 CB

    1-1
    通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为:123。 (2分)
    T F
    1-2
    若一个栈的输入序列为1,2,3,…,N,输出序列的第一个元素是i,则第j个输出元素是j−i−1。 (2分)
    T F
    1-3
    若一个栈的输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。 (2分)
    T F
    1-4
    栈和队列的存储方式,既可以是顺序方式,也可以是链式方式。 (1分)
    T F
    1-5
    栈是插入和删除只能在一端进行的线性表;队列是插入在一端进行,删除在另一端进行的线性表。 (1分)
    T F
    1-6
    栈底元素是不能删除的元素。 (1分)
    T F
    1-7
    顺序栈中元素值的大小是有序的。 (1分)
    T F
    1-8
    在n个元素连续进栈以后,它们的出栈顺序和进栈顺序一定正好相反。 (1分)
    T F
    1-9
    栈顶元素和栈底元素有可能是冋一个元素。 (1分)
    T F

    1-10
    若用data[1…m]表示顺序栈的存储空间,则对栈的进栈、出栈操作最多只能进行m次。 (1分)
    T F
    1-11
    栈是一种对进栈、出栈操作总次数做了限制的线性表。 (1分)
    T F
    1-12
    对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。 (1分)
    T F
    1-13
    所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (1分)
    T F
    1-14
    在用数组表示的循环队列中,front值一定小于等于rear值。 (1分)
    T F
    1-15
    在对不带头结点的链队列作出队操作时,不会改变头指针的值。 (2分)
    T F
    1-16
    队列是一种插入和删除操作分别在表的两端进行的线性表,是一种先进后出的结构。 (2分)
    T F
    1-17
    不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。 (2分)
    T F
    1-18
    循环队列执行出队操作时会引起大量元素的移动。 (1分)
    T F
    1-19
    队列是一种插入和删除操作分别在表的两端进行的线性表,是一种先进后出的结构。 (1分)
    T F
    1-20
    n个元素进队的顺序和出队的顺序总是一致的。 (1分)
    T F

    判断题答案:1-5 FFTTT
    6-10 FFTTF
    11-15 FTFFF
    16-20 FTFFT

    2-1
    设栈S和队列Q的初始状态均为空,元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b、d、c、f、e、a、g,则栈S的容量至少是: (2分)
    A.1
    B.2
    C.3
    D.4
    2-2
    假设有5个整数以1、2、3、4、5的顺序被压入堆栈,且出栈顺序为3、5、4、2、1,那么为了获得这样的输出,堆栈大小至少为: (2分)
    A.2
    B.3
    C.4
    D.5
    2-3
    若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是? (2分)
    A.b c a e f d
    B.c b d a e f
    C.d c e b f a
    D.a f e d c b
    2-4
    设一个栈的输入序列是1、2、3、4、5,则下列序列中,是栈的合法输出序列的是? (2分)
    A.3 2 1 5 4
    B.5 1 2 3 4
    C.4 5 1 3 2
    D.4 3 1 2 5
    2-5
    有六个元素以6、5、4、3、2、1的顺序进栈,问哪个不是合法的出栈序列? (2分)
    A.2 3 4 1 5 6
    B.3 4 6 5 2 1
    C.5 4 3 6 1 2
    D.4 5 3 1 2 6
    2-6
    若一个栈的入栈序列为1、2、3、…、N,输出序列的第一个元素是i,则第j个输出元素是: (2分)
    A.i−j−1
    B.i−j
    C.j−i−1
    D.不确定
    2-7
    若一个栈的入栈序列为1、2、3、…、N,其输出序列为p​1​​、p​2​​、p​3​​、…、p​N​​。若p​1​​=N,则p​i​​为: (2分)
    A.i
    B.n−i
    C.n−i+1
    D.不确定
    2-8
    将5个字母ooops按此顺序入栈,则有多少种不同的出栈顺序可以仍然得到ooops? (2分)
    A.1
    B.3
    C.5
    D.6
    2-9
    令P代表入栈,O代表出栈。则将一个字符串3a+b/c变为3 a * b c / +的堆栈操作序列是哪个?(例如将ABC变成BCA的操作序列是PPOPOO。) (2分)
    A.PPPOOOPPOPPOOO
    B.POPOPOPPOPPOOO
    C.POPPOOPPOPOOPO
    D.POPPOOPPOPPOOO
    2-10
    令P代表入栈,O代表出栈。当利用堆栈求解后缀表达式1 2 3 + * 4 –时,堆栈操作序列是: (3分)
    A.PPPOOPOO
    B.PPOOPPOOPPOO
    C.PPPOOPOOPPOO
    D.PPPOOPOOPPOOPO
    2-11
    令P代表入栈,O代表出栈。若利用堆栈将中缀表达式3
    2+8/4转为后缀表达式,则相应的堆栈操作序列是: (3分)
    A.PPPOOO
    B.POPOPO
    C.POPPOO
    D.PPOOPO
    2-12
    若借助堆栈将中缀表达式a+bc+(de+f)g转换为后缀表达式,当读入f时,堆栈里的内容是什么(按堆栈自底向上顺序)? (3分)
    A.+(
    +
    B.+(+
    C.++(+
    D.abcde
    2-13
    设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4,则最后一个出栈的元素必定是: (2分)
    A.1
    B.3
    C.5
    D.1或者5
    2-14
    表达式a*(b+c)-d的后缀表达式是: (2分)
    A.a b c + * d -
    B.a b c d * + -
    C.a b c * + d -
    D.- + * a b c d
    2-15
    从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值,则执行: (2分)
    A.X= ST->data;
    B.X= ST; ST = ST->next;
    C.X= ST->data; ST = ST->next;
    D.ST = ST->next; X= ST->data;
    2-16
    若top为指向栈顶元素的指针,判定栈S(最多容纳m个元素)为空的条件是: (2分)
    A.S->top == 0
    B.S->top == -1
    C.S->top != m-1
    D.S->top == m-1
    2-17
    若采用带头、尾指针的单向链表表示一个堆栈,那么该堆栈的栈顶指针top应该如何设置? (2分)
    A.将链表头设为top
    B.将链表尾设为top
    C.随便哪端作为top都可以
    D.链表头、尾都不适合作为top
    2-18
    利用大小为n的数组(下标从0到n-1)存储一个栈时,假定栈从数组另一头开始且top==n表示栈空,则向这个栈插入一个元素时,修改top指针应当执行: (2分)
    A.top=0
    B.top++
    C.top–
    D.top不变
    2-19
    若栈采用顺序存储方式存储,现两栈共享空间V[m]:top[i]代表第i(i=1或2)个栈的栈顶;栈1的底在V[0],栈2的底在V[m-1],则栈满的条件是: (2分)
    A.|top[2]-top[1]|==0
    B.top[1]+top[2]m
    C.top[1]top[2]
    D.top[1]+1
    top[2]
    2-20
    给定一个堆栈的入栈序列为{ 1, 2, ⋯, n },出栈序列为{ p​1​​, p​2​​, ⋯, p​n​​ }。如果p​2​​=n,则存在多少种不同的出栈序列?(2分)
    A.1
    B.2
    C.n−1
    D.n
    2-21
    下列关于栈的叙述中,错误的是:(2分)
    1.采用非递归方式重写递归程序时必须使用栈
    2.函数调用时,系统要用栈保存必要的信息
    3.只要确定了入栈次序,即可确定出栈次序
    4.栈是一种受限的线性表,允许在其两端进行操作
    A.仅 1
    B.仅 1、2、3
    C.仅 1、3、4
    D.仅 2、3、4
    2-22
    若顺序栈的栈顶指针指向栈顶元素位置,则压入新元素时,应( )。 (2分)
    A.先移动栈顶指针
    B.先存入元素,再移动栈顶指针
    C.先后次序无关紧要
    D.同时进行
    2-23
    链式栈与顺序栈相比,一个比较明显的优点是( )。 (2分)
    A.插入操作更加方便
    B.通常不会出现栈满的情况
    C.不会出现栈空的情况
    D.删除操作更加方便
    2-24
    两栈共享数组存储空间,前一个栈的栈顶指针为p后一个栈的栈顶指针为q,能进行正常入栈操作的条件是( )。 (2分)
    A.p<=q
    B.p>q
    C.p<q-1
    D.p
    q-2
    2-25
    一个递归的定义可以用递归过程求解,也可以用非递归过程求解,但单从运行时间来看, 通常递归过程比非递归过程( )。 (2分)
    A.较快
    B.较慢
    C.相同
    D.无法确定
    2-26
    字符A,B,C依次进入一个栈,按出栈的先后顺序组成不同的字符串,则至多可以组成( )个不同的字符串。 (2分)
    A.14
    B.5
    C.6
    D.8
    2-27
    关于栈和队列的下列说法正确的是() (2分)
    A.栈的插入操作是在栈顶进行,插入时需将栈内所有元素后移;
    B.栈是后进先出的结构,出栈时除了栈顶元素,其余元素无需移动;
    C.循环队列的出队操作删除的是队头元素,采用循环队列存储时,其余队列元素均需要移动;
    D.链队列的入队操作在表尾进行,操作时间与队列长度成正比
    2-28
    若栈S​1​​中保存整数,栈S​2​​中保存运算符,函数F()依次执行下述各步操作:
    (1)从S​1​​中依次弹出两个操作数a和b;
    (2)从S​2​​中弹出一个运算符op;
    (3)执行相应的运算b op a;
    (4)将运算结果压入S​1​​中。
    假定S​1​​中的操作数依次是{ 5, 8, 3, 2 }(2在栈顶),S​2​​中的运算符依次是{ *, -, + }(+在栈顶)。调用3次F()后,S​1​​栈顶保存的值是:(2分)
    A.-15
    B.15
    C.-20
    D.20
    2-29
    现有队列 Q 与栈 S,初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }(1在队头),S 为空。若允许下列3种操作:(1)出队并输出出队元素;(2)出队并将出队元素入栈;(3)出栈并输出出栈元素,则不能得到的输出序列是:(2分)
    A.1, 2, 5, 6, 4, 3
    B.2, 3, 4, 5, 6, 1
    C.3, 4, 5, 6, 1, 2
    D.6, 5, 4, 3, 2, 1
    2-30
    为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是? (1分)
    A.堆栈
    B.队列
    C.树
    D.图
    2-31
    若已知一队列用单向链表表示,该单向链表的当前状态(含3个对象)是:1->2->3,其中x->y表示x的下一节点是y。此时,如果将对象4入队,然后队列头的对象出队,则单向链表的状态是: (1分)
    A.1->2->3
    B.2->3->4
    C.4->1->2
    D.答案不唯一
    2-32
    某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作,则不可能得到的出队序列是: (2分)
    A.b a c d e
    B.d b a c e
    C.e c b a d
    D.d b c a e
    2-33
    若用大小为6的数组来实现循环队列,且当前front和rear的值分别为0和4。当从队列中删除两个元素,再加入两个元素后,front和rear的值分别为多少? (2分)
    A.2和0
    B.2和2
    C.2和4
    D.2和6
    2-34
    如果循环队列用大小为m的数组表示,且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围,那么这样的循环队列可以容纳的元素个数最多为: (2分)
    A.m-1
    B.m
    C.m+1
    D.不能确定
    2-35
    如果循环队列用大小为m的数组表示,队头位置为front、队列元素个数为size,那么队尾元素位置rear为: (2分)
    A.front+size
    B.front+size-1
    C.(front+size)%m
    D.(front+size-1)%m
    2-36
    在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是( )。 (2分)
    A.f->next=s; f=s;
    B.r->next=s; r=s;
    C.s->next=s; r=s;
    D.s->next=f; f=s;
    2-37
    从一个顺序队列中删除元素时,首先要( )。 (2分)
    A.前移一位队首指针
    B.后移一位队首指针
    C.取出队首指针所指位置上的元素
    D.取出队尾指针所指位置上的元素
    2-38
    在一个顺序存储的循环队列中,若队尾指针指向队尾元素的后一个位置,则队头指针一般指向队头元素的( )。 (2分)
    A.前一个位置
    B.后一个位置
    C.当前位置
    D.后两个位置
    2-39
    在由n个元素组成的顺序存储的循环队列sq中,假定f和r分别为队头指针和队尾指针,则判断队满的条件是( )。 (2分)
    A.f (r+1)%n
    B.(r - 1)%n
    f
    C.f == r
    D.(f + 1)%n == f
    2-40
    循环顺序队列中是否可以插入下一个元素()。 (2分)
    A.与队头指针和队尾指针的值有关
    B.只与队尾指针的值有关,与队头指针的值无关
    C.只与数组大小有关,与队首指针和队尾指针的值无关
    D.与曾经进行过多少次插入操作有关
    2-41
    最不适合用作链队的链表是()。 (2分)
    A.只带队头指针的非循环双链表
    B.只带队头指针的循环双链表
    C.只带队尾指针的循环双链表
    D.只带队尾指针的循环单链表
    2-42
    用单链表表示的链队的队头在链表的()位置。 (2分)
    A.链头
    B.链尾
    C.链中
    D.均可以
    2-43
    假设链队列头指针直接指向队头元素,进行出队操作时需要的操作为( )。 (2分)
    A.仅修改头指针
    B.仅修改尾指针
    C.头、尾指针都必须修改
    D.头、尾指针可能都要修改
    2-44
    对于容量为n的循环队列Q,队尾指针是Q.rear,队头指针是Q.front,则出队时头尾指针需要进行的操作为 ( ) (2分)
    A.Q.rear=Q.rear+1
    B.Q.rear=(Q.rear+1) %n
    C.Q.front=Q.front+1
    D.Q.front=(Q.front+1) %n
    2-45
    循环队列的队满条件为( ) (2分)
    A.(sq.rear+1) % mazsize ==(sq.front+1) % maxsize;
    B.(sq.rear+1)% maxsize ==sq.front+1
    C.(sq.rear+1) % maxsize ==sq.front
    D.sq.rear ==sq.front
    2-46
    循环队列的队空条件为( ) (2分)
    A.(sq.rear+1) % mazsize ==(sq.front+1) % maxsize;
    B.(sq.rear+1)% maxsize ==sq.front+1
    C.(sq.rear+1) % maxsize ==sq.front
    D.sq.rear ==sq.front
    2-47
    设循环队列中数组的下标范围是0—n-1,其头尾指针分别为f和r,则其元素的个数为( ) (2分)
    A.r-f
    B.r-f +1
    C.(r-f)%n+1
    D.(r-f+n)%n
    2-48
    如果循环队列用大小为m的数组表示,队头位置为front、队列元素个数为size,那么队尾元素位置rear为:____。 (2分)
    A.front+size
    B.front+size-1
    C.(front+size)%m
    D.(front+size-1)%m
    2-49
    循环队列存储在数组A[0…m]中,其头尾指针分别为front和rear,头指针front总是指向队头元素,尾指针rear总是指向队尾元素的下一个位置,则元素e入队时的操作为( )。 (2分)
    A.A[rear]=e; rear=rear+1
    B.A[rear]=e; rear=(rear+1)%m
    C.A[rear]=e;rear=(rear+1)%(m+1)
    D.rear=(rear+1)%(m+1); A[rear]=e;
    2-50
    循环队列存储在数组A[0…n-1]中,其头尾指针分别为f和r,头指针f总是指向队头元素,尾指针r总是指向队尾元素的下一个位置,假设队列不空,元素出队时头尾指针的操作为( )。 (2分)
    A.f=(f+1)%n
    B.f=f+1
    C.r=(r+1)%n
    D.f=(f+1)%(n-1)

    第四章 树

    1-1
    某二叉树的前序和中序遍历序列正好一样,则该二叉树中的任何结点一定都无左孩子。 (2分)
    T F
    1-2
    已知一棵二叉树的先序遍历结果是ABC, 则CAB不可能是中序遍历结果。 (2分)
    T F
    1-3
    若一个结点是某二叉树的中序遍历序列的最后一个结点,则它必是该树的前序遍历序列中的最后一个结点。 (2分)
    T F
    1-4
    某二叉树的后序和中序遍历序列正好一样,则该二叉树中的任何结点一定都无右孩子。 (2分)
    T F
    1-5
    若A和B都是一棵二叉树的叶子结点,则存在这样的二叉树,其前序遍历序列为…A…B…,而中序遍历序列为…B…A…。 (2分)
    T F
    1-6
    若一个结点是某二叉树的中序遍历序列的最后一个结点,则它必是该树的前序遍历序列中的最后一个结点。 (2分)
    T F
    1-7
    二叉树通常有顺序存储结构和链式存储结构。 (2分)
    T F
    1-8
    具有10个叶结点的二叉树中,有9个度为2的结点。 (1分)
    T F
    1-9
    在含有n个结点的树中,边数只能是n-1条。 (1分)
    T F
    1-10
    完全二叉树中,若一个结点没有左孩子,则它必是树叶。 (1分)
    T F

    2-1
    树最适合于用来表示 (1分)
    A.有序数据元素
    B.无序数据元素
    C.元素之间无联系的数据
    D.元素之间具有分支层次关系的数据
    2-2
    设树T的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点? (3分)
    A.4
    B.6
    C.8
    D.10
    2-3
    某二叉树的中序序列和后序序列正好相反,则该二叉树一定是 (2分)
    A.空或只有一个结点
    B.高度等于其结点数
    C.任一结点无左孩子
    D.任一结点无右孩子
    2-4
    已知一棵二叉树的先序遍历结果是ABC,则以下哪个序列是不可能的中序遍历结果: (2分)
    A.ABC
    B.BAC
    C.CBA
    D.CAB
    2-5
    设n、m为一棵二叉树上的两个结点,在中序遍历时,n在m前的条件是 (3分)
    A.n在m左方
    B.n在m右方
    C.n是m祖先
    D.n是m子孙
    2-6
    设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少结点数和最多结点数分别为: (3分)
    A.2h, 2​h​​−1
    B.2h−1, 2​h​​−1
    C.2h−1, 2​h−1​​−1
    D.2​h−1​​+1, 2​h​​−1
    2-7
    按照二叉树的定义,具有3个结点的二叉树有几种? (2分)
    A.3
    B.4
    C.5
    D.6
    2-8
    二叉树中第5层(根的层号为1)上的结点个数最多为:(2分)
    A.8
    B.15
    C.16
    D.32
    2-9
    先序遍历图示二叉树的结果为 (2分)

    A.A,B,C,D,H,E,I,F,G
    B.A,B,D,H,I,E,C,F,G
    C.H,D,I,B,E,A,F,C,G
    D.H,I,D,B,E,F,G,A,C
    2-10
    已知一棵二叉树的树形如下图所示,其后序序列为{ e, a, c, b, d, g, f }。树中与结点a同层的结点是:(3分)

    A.c
    B.d
    C.f
    D.g

    1-1
    任何二叉搜索树中同一层的结点从左到右是有序的(从小到大)。 (2分)
    T F
    1-2
    在一棵二叉搜索树上查找63,序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。 (3分)
    T F
    1-3
    在一棵由包含4、5、6等等一系列整数结点构成的二叉搜索树中,如果结点4和6在树的同一层,那么可以断定结点5一定是结点4和6的父亲结点。 (3分)
    T F
    1-4
    二叉搜索树的查找和折半查找的时间复杂度相同。 (2分)
    T F
    1-5
    二叉排序树的后序遍历序列必然是递增的。(1分)
    T F
    1-6
    对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 (1分)
    T F
    1-7
    二叉搜索树的最小元素一定位于树根的左子树。 (2分)
    T F
    1-8
    二叉搜索树T的最大元素一定位于树根的右子树。 (2分)
    T F
    1-9
    任何AVL树的中序遍历结果是有序的(从小到大)。 (2分)
    T F
    1-10
    将1、2、3、4、5、6顺序插入初始为空的AVL树中,当完成这6个元素的插入后,该AVL树的先序遍历结果是:4、2、1、3、5、6。 (3分)
    T F
    1-11
    对AVL树中的任一结点,其右子树的高度一定比其左子树的高度要高。 (1分)
    T F
    1-12
    对AVL树中的任一结点,其左、右子树的高度一定是一样的。 (1分)
    T F
    1-13
    对一棵平衡二叉树,所有非叶结点的平衡因子都是0,当且仅当该树是完全二叉树。(2分)
    T F
    1-14
    若一棵平衡二叉树的所有非叶结点的平衡因子都是0,则其必为完美二叉树。(2分)
    T F
    1-15
    如果由结点{ 1, 2, 3, 4 }组成的AVL树的深度是3(根结点的深度是1),则结点2或者结点3一定有两个子结点。(2分)
    T F
    1-16
    如果由结点{ 1, 2, 3, 4 }组成的AVL树的深度是3(根结点的深度是1),则结点4有可能是根结点。(2分)
    T F
    2-1
    对二叉搜索树进行什么遍历可以得到从小到大的排序序列? (1分)
    A.前序遍历
    B.后序遍历
    C.中序遍历
    D.层次遍历
    2-2
    在有N个结点且为完全二叉树的二叉搜索树中查找一个键值,其平均比较次数的数量级为: (1分)
    A.O(logN)
    B.O(N)
    C.O(NlogN)
    D.O(N​2​​)
    2-3
    若二叉搜索树是有N个结点的完全二叉树,则不正确的说法是:(1分)
    A.平均查找效率是O(logN)
    B.最大值一定在最后一层
    C.最小值一定在叶结点上
    D.中位值结点在根结点或根的左子树上
    2-4
    已知8个数据元素为(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成一棵二叉搜索树后,最后两层上的结点总数为: (2分)
    A.1
    B.2
    C.3
    D.4
    2-5
    将下列数(88, 70, 61, 96, 120, 90)按顺序插入初始为空的AVL中,所形成的AVL树的前序遍历结果是: (2分)
    A.61,70,88,90,96,120
    B.90,70,61,88,96,120
    C.88,70,61,90,96,120
    D.88,70,61,96,90,120
    2-6
    将{5, 2, 7, 3, 4, 1, 6}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是:(3分)
    A.1, 2, 3, 4, 6, 7, 5
    B.1, 4, 2, 6, 3, 7, 5
    C.1, 4, 3, 2, 6, 7, 5
    D.5, 4, 3, 7, 6, 2, 1
    2-7
    若一棵二叉树的前序遍历序列是{ 4, 2, 1, 3, 6, 5, 7 },中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 },则下列哪句是错的?(3分)
    A.这是一棵完全二叉树
    B.所有的奇数都在叶子结点上
    C.这是一棵二叉搜索树
    D.2是5的父结点
    2-8
    若二叉搜索树是有N个结点的完全二叉树,则不正确的说法是:(1分)
    A.所有结点的平均查找效率是O(logN)
    B.最小值一定在叶结点上
    C.最大值一定在叶结点上
    D.中位值结点在根结点或根的左子树上
    2-9
    若一棵二叉树的后序遍历序列是{ 1, 3, 2, 6, 5, 7, 4 },中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 },则下列哪句是错的?(3分)
    A.这是一棵完全二叉树
    B.2是1和3的父结点
    C.这是一棵二叉搜索树
    D.7是5的父结点
    2-10
    已知二叉排序树如下图所示,元素之间应满足的大小关系是:(2分)

    A.x​1​​<x​2​​<x​5​​
    B.x​1​​<x​4​​<x​5​​
    C.x​3​​<x​5​​<x​4​​
    D.x​4​​<x​3​​<x​5​​
    1-1
    任何最小堆的前序遍历结果是有序的(从小到大)。 (2分)
    T F
    1-2
    任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的(从小到大)。 (2分)
    T F
    1-3
    在有N个元素的最大堆中,随机访问任意键值的操作可以在O(logN)时间完成。 (2分)
    T F
    1-4
    对N(≥2)个权值均不相同的字符构造哈夫曼树,则树中任一非叶结点的权值一定不小于下一层任一结点的权值。 (2分)
    T F
    1-5
    哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率,其哈夫曼编码不一定是唯一的,但是每个字符的哈夫曼码的长度一定是唯一的。(2分)
    T F
    2-1
    堆的形状是一棵: (1分)
    A.二叉搜索树
    B.满二叉树
    C.非二叉树
    D.完全二叉树
    2-2
    已知关键字序列(5,8,12,19,28,20,15,22)是最小堆(小根堆),插入关键字3,调整后得到的最小堆是: (2分)
    A.3,5,12,8,28,20,15,22,19
    B.3,5,12,19,20,15,22,8,28
    C.3,8,12,5,20,15,22,28,19
    2-3
    哪种树,树中任何结点到根结点路径上的各结点值是有序的? (1分)
    A.二叉搜索树
    B.完全二叉树
    C.堆
    D.以上都不是
    2-4
    下列的序列中,哪一组是堆? (2分)
    A.37,99,45,33,66,10,22,13
    B.99,45,66,13,37,10,22,33
    C.99,66,45,33,37,10,22,13
    D.99,66,22,33,37,13,45,10
    2-5
    在下述结论中,正确的是: (2分)
    ① 只有2个结点的树的度为1;
    ② 二叉树的度为2;
    ③ 二叉树的左右子树可任意交换;
    ④ 在最大堆(大顶堆)中,从根到任意其它结点的路径上的键值一定是按非递增有序排列的。
    A.①④
    B.②④
    C.①②③
    D.②③④
    2-6
    将 { 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7 } 逐个按顺序插入到初始为空的最小堆中,然后连续执行两次删除最小元素操作(DeleteMin),再插入4,16,此后堆顶的元素是什么? (2分)
    A.4
    B.5
    C.7
    D.9
    2-7
    在将数据序列( 6, 1, 5, 9, 8, 4, 7 )建成大根堆时,正确的序列变化过程是:(3分)
    A.6,1,7,9,8,4,5 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
    B.6,9,5,1,8,4,7 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
    C.6,9,5,1,8,4,7 → 9,6,5,1,8,4,7 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
    D.6,1,7,9,8,4,5 → 7,1,6,9,8,4,5 → 7,9,6,1,8,4,5 → 9,7,6,1,8,4,5 → 9,8,6,1,7,4,5
    2-8
    对N(N≥2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中,错误的是: (2分)
    A.树中一定没有度为1的结点
    B.树中两个权值最小的结点一定是兄弟结点
    C.树中任一非叶结点的权值一定不小于下一层任一结点的权值
    D.该树一定是一棵完全二叉树

    2-9
    已知字符集{ a, b, c, d, e, f, g, h }。若各字符的哈夫曼编码依次是 0100, 10, 0000, 0101, 001, 011, 11, 0001,则编码序列 0100011001001011110101 的译码结果是:(2分)
    A.acgabfh
    B.adbagbb
    C.afbeagd
    D.afeefgd

    (2 分)
    2-10
    对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点,则 n 的值是:(3分)
    A.56
    B.57
    C.58
    D.60
    2-11
    在并查集问题中,已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }(注:−n表示树根且对应集合大小为n),那么将元素6和8所在的集合合并(要求必须将小集合并到大集合)后,该集合对应的树根和父结点编号值分别是多少? (2分)
    A.1和-6
    B.4和-5
    C.8和-5
    D.8和-6
    2-12
    已知不相交集合用数组表示为{ 4, 6, 5, 2, -3, -4, 3 }。若集合元素从1到7编号,则调用Union(Find(7),Find(1))(按规模求并,并且带路径压缩)后的结果数组为:(2分)
    A.{ 4, 6, 5, 2, 6, -7, 3 }
    B.{ 4, 6, 5, 2, -7, 5, 3 }
    C.{ 6, 6, 5, 6, -7, 5, 5 }
    D.{ 6, 6, 5, 6, 6, -7, 5 }
    2-13
    将 {28, 15, 42, 18, 22, 5, 40} 逐个按顺序插入到初始为空的最小堆(小根堆)中。则该树的前序遍历结果为:(3分)
    A.5, 18, 15, 28, 22, 42, 40
    B.5, 15, 18, 22, 28, 42, 40
    C.5, 18, 28, 22, 15, 42, 40
    D.5, 15, 28, 18, 22, 42, 40
    2-14
    设最小堆(小根堆)的层序遍历结果为{5, 18, 15, 28, 22, 42, 40}。用线性时间复杂度的算法将该堆调整为最大堆(大根堆),则该树的中序遍历结果为:(3分)
    A.18, 28, 22, 15, 40, 5, 42
    B.18, 28, 22, 42, 15, 40, 5
    C.5, 22, 18, 42, 15, 40, 28
    D.22, 5, 18, 42, 40, 15, 28
    2-15
    以下对于堆和哈夫曼树的描述,错误的是: (2分)
    A.堆一定是完全二叉树。
    B.堆的任意非叶节点的左右子树(如果非空)互换,仍然是堆。
    C.哈夫曼树的任意非叶节点的左右子(如果非空)树交换后仍是哈夫曼树。
    D.对同一组权值{w1 ,w2 , …… , wn},可能存在不同构的两棵哈夫曼树。
    2-16
    以下对于堆和哈夫曼树的描述,正确的是: (2分)
    A.堆一定是一棵完全二叉树,因此适合采用链式存储实现。
    B.堆的任意非叶节点的左右子树(如果非空)互换,仍然是堆。
    C.哈夫曼树中没有度为1的结点。
    D.哈夫曼树的叶结点一定都在同一层。
    2-17
    将6、4、3、5、8、9顺序插入初始为空的最大堆(大根堆)中,那么插入完成后堆顶的元素为: (2分)
    A.3
    B.5
    C.6
    D.9
    2-18
    在有n(>1)个元素的最大堆(大根堆)中,最小元的数组下标可以是:(3分)
    A.1
    B.⌊n/2⌋−1
    C.⌊n/2⌋
    D.⌊n/2⌋+2
    2-19
    用线性时间复杂度的算法将给定序列{15, 26, 32, 8, 7, 20, 12, 13, 5, 19}调整为最小堆(小根堆),然后插入6。下列句子中错误的是:(3分)
    A.5是根
    B.从根到26的路径是{5, 6, 8, 26}
    C.32是12的左孩子
    D.7是19和15的父结点
    2-20
    关于Huffamn树,如下说法错误的是( ) (2分)
    A.多于1个叶子结点的Huffman树中不存在度为1的结点
    B.Huffman树中,任意调整结点左右孩子的顺序,不影响带权路径长度
    C.Huffamn树的带权路径长度最大
    D.Huffman树中,权值越大的叶子结点离根结点越近

    第六章图
    1-1
    无向连通图所有顶点的度之和为偶数。 (1分)
    T F
    1-2
    无向连通图边数一定大于顶点个数减1。 (1分)
    T F
    1-3
    无向连通图至少有一个顶点的度为1。 (1分)
    T F
    1-4
    用邻接表法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。 (1分)
    T F
    1-5
    用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。 (1分)
    T F
    1-6
    在一个有向图中,所有顶点的入度与出度之和等于所有边之和的2倍。 (1分)
    T F
    1-7
    在任一有向图中,所有顶点的入度之和等于所有顶点的出度之和。 (1分)
    T F
    1-8
    用一维数组G[]存储有4个顶点的无向图如下:
    G[] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
    则顶点2和顶点0之间是有边的。(2分)
    T F
    1-9
    无向图中的一条边,在其邻接表存储结构中对应两个弧结点。 (1分)
    T F
    1-10
    有向图的邻接矩阵是对称的。 (1分)
    T F
    1-11
    用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 (1分)
    T F
    1-12
    用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。 (1分)
    T F
    1-13
    n个顶点的无向图最多有n(n-1)条边。 (2分)
    T F
    1-14
    在有向图中,各顶点的入度之和等于各顶点的出度之和。(2分)
    T F
    1-15
    无论是有向图还是无向图,其邻接矩阵表示都是唯一的。(2分)
    T F
    1-16
    对同一个有向图来说,只保存出边的邻接表中结点的数目总是和只保存入边的邻接表中结点的数目一样多。(2分)
    T F
    1-17
    如果表示图的邻接矩阵是对称矩阵,则该图一定是无向图。(2分)
    T F
    1-18
    如果表示有向图的邻接矩阵是对称矩阵,则该有向图一定是完全有向图。(2分)
    T F
    1-19
    如果一个无向图有多于一个连通分量,则该图必不连通。 (2分)
    T F
    1-20
    若图G为连通图,则G的生成树是G的包含全部n个顶点的一个极大联通子图。 (2分)
    T F

    2-1
    下列关于无向连通图特征的叙述中,正确的是: (2分)
    1.所有顶点的度之和为偶数
    2.边数大于顶点个数减1
    3.至少有一个顶点的度为1
    A.只有1
    B.只有2
    C.1和2
    D.1和3
    2-2
    具有5个顶点的有向完全图有多少条弧? (2分)
    A.10
    B.16
    C.20
    D.25
    2-3
    在N个顶点的无向图中,所有顶点的度之和不会超过顶点数的多少倍? (2分)
    A.1
    B.2
    C.(N−1)/2
    D.N−1
    2-4
    一个有N个顶点的强连通图至少有多少条边? (2分)
    A.N−1
    B.N
    C.N+1
    D.N(N−1)
    2-5
    对于一个具有N个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是: (1分)
    A.N−1
    B.N
    C.(N−1)​2​​
    D.N​2​​
    2-6
    下面关于图的存储的叙述中,哪一个是正确的? (1分)
    A.用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
    B.用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
    C.用邻接表法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
    D.用邻接表法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
    2-7
    关于图的邻接矩阵,下列哪个结论是正确的? (1分)
    A.有向图的邻接矩阵总是不对称的
    B.有向图的邻接矩阵可以是对称的,也可以是不对称的
    C.无向图的邻接矩阵总是不对称的
    D.无向图的邻接矩阵可以是不对称的,也可以是对称的
    2-8
    在一个无向图中,所有顶点的度数之和等于所有边数的多少倍? (2分)
    A.1/2
    B.1
    C.2
    D.4
    2-9
    在一个有向图中,所有顶点的入度与出度之和等于所有边之和的多少倍? (2分)
    A.1/2
    B.1
    C.2
    D.4
    2-10
    下面给出的有向图中,有__个强连通分量。(2分)

    A.1 ({0,1,2,3,4})
    B.1 ({1,2,3,4})
    C.2 ({1,2,3,4}, {0})
    D.5 ({0}, {1}, {2}, {3}, {4})
    2-11
    下面给出的有向图中,各个顶点的入度和出度分别是:(1分)

    A.入度: 0, 2, 3, 1, 2; 出度: 3, 2, 1, 1, 1
    B.入度: 3, 2, 1, 1, 1; 出度: 0, 2, 3, 1, 2
    C.入度: 3, 4, 4, 2, 3; 出度: 3, 4, 4, 2, 3
    D.入度: 0, 1, 2, 1, 1; 出度: 3, 2, 1, 1, 1
    2-12
    下列有关图的叙述中,有几句是对的? (3分)
    1.如果e是有权无向图G唯一的一条最短边,那么边e一定会在该图的最小生成树上。
    2.如果无向图的宽度优先搜索的结果为1234…,且顶点1与顶点4之间存在一条边相连,那么顶点1与顶点3之间也一定有边相连。
    3.如果从有向图G(至少有2个顶点)的每一点均能通过深度优先搜索遍历到所有其它顶点,那么该图一定不存在拓扑序列。
    4.若图采用邻接矩阵表示,如果该矩阵不全为0,且矩阵主对角线以下全是0,那么说明该图一定是有向图。
    A.4句
    B.3句
    C.2句
    D.1句
    2-13
    如果G是一个有36条边的非连通无向图,那么该图顶点个数最少为多少?(3分)
    A.7
    B.8
    C.9
    D.10
    2-14
    给定有向图的邻接矩阵如下:

    顶点2(编号从0开始)的出度和入度分别是:(1分)
    A.3, 1
    B.1, 3
    C.0, 2
    D.2, 0
    2-15
    具有 100 个顶点和 12 条边的无向图至多有多少个连通分量? (2分)
    A.87
    B.88
    C.94
    D.95
    1-1
    在一个有权无向图中,若b到a的最短路径距离是12,且c到b之间存在一条权为2的边,则c到a的最短路径距离一定不小于10。 (3分)
    T F
    1-2
    P 是顶点 S 到 T 的最短路径,如果该图中的所有路径的权值都加 1,P 仍然是 S 到 T 的最短路径。 (2分)
    T F
    1-3
    对于带权无向图 G = (V, E),M 是 G 的最小生成树,则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。 (2分)
    T F

    2-1
    在一个有权无向图中,如果顶点b到顶点a的最短路径长度是10,顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的? (3分)
    1.c与a的最短路径长度就是13
    2.c与a的最短路径长度就是7
    3.c与a的最短路径长度不超过13
    4.c与a的最短路径不小于7
    A.1句
    B.2句
    C.3句
    D.4句
    2-2
    我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题? (1分)
    A.Dijkstra算法
    B.Kruskal算法
    C.深度优先搜索
    D.拓扑排序算法
    2-3
    数据结构中Dijkstra算法用来解决哪个问题? (1分)
    A.关键路径
    B.最短路径
    C.拓扑排序
    D.字符串匹配
    2-4
    若要求在找到从S到其他顶点最短路的同时,还给出不同的最短路的条数,我们可以将Dijkstra算法略作修改,增加一个count[]数组:count[V]记录S到顶点V的最短路径有多少条。则count[V]应该被初始化为: (3分)
    A.count[S]=1;对于其他顶点V则令count[V]=0
    B.count[S]=0;对于其他顶点V则令count[V]=1
    C.对所有顶点都有count[V]=1
    D.对所有顶点都有count[V]=0
    2-5
    对含有n个顶点、e条边的带权图求最短路径的Dijkstra算法的时间复杂度为____。(2分)
    A.O(n)
    B.O(n+e)
    C.O(n​2​​)
    D.O(ne)
    2-6
    Dijkstra算法是____方法求出图中从某顶点到其余顶点的最短路径的。 (2分)
    A.按长度递减的顺序求出图中某顶点到其余顶点的最短路径
    B.按长度递增的顺序求出图中某顶点到其余顶点的最短路径
    C.通过深度优先遍历求出图中某顶点到其余顶点的最短路径
    D.通过广度优先遍历求出图中某顶点到其余顶点的最短路径
    2-7
    使用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其他各顶点的最短路径,依次得到的各最短路径的目标顶点是:(2分)

    A.6, 7, 5, 3, 2, 4
    B.6, 2, 5, 7, 3, 4
    C.2, 3, 4, 5, 6, 7
    D.2, 4, 3, 6, 5, 7
    2-8
    试利用 Dijkstra 算法求下图中从顶点 A 到其他顶点的最短距离及对应的路径。下列那个序列给出了可能的顶点收集顺序? (2分)

    A.ACFEDBG
    B.ACDBFEG
    C.ACDGFBE
    D.ABCDEFG

    第五章散列查找


    1-1
    将M个元素存入用长度为S的数组表示的散列表,则该表的装填因子为M/S。 (1分)
    T F
    作者: DS课程组
    单位: 浙江大学
    1-2
    在散列中,函数“插入”和“查找”具有同样的时间复杂度。 (1分)
    T F
    作者: 冯雁
    单位: 浙江大学
    1-3
    即使把2个元素散列到有100个单元的表中,仍然有可能发生冲突。 (1分)
    T F
    作者: 陈越
    单位: 浙江大学
    1-4
    在散列表中,所谓同义词就是具有相同散列地址的两个元素。 (1分)
    T F
    作者: DS课程组
    单位: 浙江大学
    1-5
    在散列表中,所谓同义词就是被不同散列函数映射到同一地址的两个元素。 (1分)
    T F
    作者: DS课程组
    单位: 浙江大学
    1-6
    采用平方探测冲突解决策略(h​i​​(k)=(H(k)+i​2​​)%11, 注意:不是±i​2​​),将一批散列值均等于2的对象连续插入一个大小为11的散列表中,那么第4个对象一定位于下标为0的位置。 (3分)
    T F
    作者: DS课程组
    单位: 浙江大学
    1-7
    若用平方探测法解决冲突,则插入新元素时,若散列表容量为质数,插入就一定可以成功。 (1分)
    T F
    作者: DS课程组
    单位: 浙江大学


    2-1
    在散列表中,所谓同义词就是: (1分)
    A.两个意义相近的单词
    B.具有相同散列地址的两个元素
    C.被映射到不同散列地址的一个元素
    D.被不同散列函数映射到同一地址的两个元素
    作者: DS课程组
    单位: 浙江大学
    2-2
    在下列查找的方法中,平均查找长度与结点个数无关的查找方法是: (1分)
    A.顺序查找
    B.二分法
    C.利用哈希(散列)表
    D.利用二叉搜索树
    作者: DS课程组
    单位: 浙江大学
    2-3
    将M个元素存入用长度为S的数组表示的散列表,则该表的装填因子为: (2分)
    A.S+M
    B.M−S
    C.M×S
    D.M/S
    作者: DS课程组
    单位: 浙江大学
    2-4
    将10个元素散列到100000个单元的哈希表中,是否一定产生冲突? (1分)
    A.一定会
    B.可能会
    C.一定不会
    D.有万分之一的可能会
    作者: DS课程组
    单位: 浙江大学
    2-5
    设散列表的地址区间为[0,16],散列函数为H(Key)=Key%17。采用线性探测法处理冲突,并将关键字序列{ 26,25,72,38,8,18,59 }依次存储到散列表中。元素59存放在散列表中的地址是: (2分)
    A.8
    B.9
    C.10
    D.11
    作者: DS课程组
    单位: 浙江大学
    2-6
    采用线性探测法解决冲突时所产生的一系列后继散列地址: (1分)
    A.必须大于等于原散列地址
    B.必须小于等于原散列地址
    C.可以大于或小于但不等于原散列地址
    D.对地址在何处没有限制
    作者: DS课程组
    单位: 浙江大学
    2-7
    将元素序列{18,23,11,20,2,7,27,33,42,15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为:H(Key)=Key%11,采用线性探测法处理冲突。问:当第一次发现有冲突时,散列表的装填因子大约是多少? (3分)
    A.0.27
    B.0.45
    C.0.64
    D.0.73
    作者: DS课程组
    单位: 浙江大学
    2-8
    给定散列表大小为11,散列函数为H(Key)=Key%11。采用平方探测法处理冲突:h​i​​(k)=(H(k)±i​2​​)%11将关键字序列{ 6,25,39,61 }依次插入到散列表中。那么元素61存放在散列表中的位置是: (2分)
    A.5
    B.6
    C.7
    D.8
    作者: DS课程组
    单位: 浙江大学

    第七章排序

    叶珂璐
    题目集列表题目集概况题目列表提交列表排名

    共 251 分
    判断题(共 18 分)16/16

    单选题(共 43 分)25/25

    编程题(共 190 分)7/8
    8
    数据结构-第7章 排序
    判断题16
    单选题25
    编程题8
    1-1
    仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。 (1分)
    T F
    1-2
    对N个记录进行归并排序,归并趟数的数量级是O(NlogN)。 (2分)
    T F
    1-3
    对N个记录进行堆排序,需要的额外空间为O(N)。 (1分)
    T F
    1-4
    对N个记录进行简单选择排序,比较次数和移动次数分别为O(N​2​​)和O(N)。 (1分)
    T F
    1-5
    对N个记录进行快速排序,在最坏的情况下,其时间复杂度是O(NlogN)。 (1分)
    T F
    1-6
    希尔排序是稳定的算法。 (1分)
    T F
    1-7
    对N个不同的数据采用冒泡排序进行从大到小的排序,当元素基本有序时交换元素次数肯定最多。 (1分)
    T F
    1-8
    要从50个键值中找出最大的3个值,选择排序比堆排序快。 (2分)
    T F
    1-9
    堆排序是稳定的排序算法。( ) (1分)
    T F
    1-10
    在堆排序中,若要进行升序排序,则需要建立大根堆。( ) (1分)
    T F
    1-11
    堆是完全二叉树,完全二叉树不一定是堆。( ) (1分)
    T F
    1-12
    插入排序算法在每一趟都能选取出一个元素放在其最终的位置上。 (1分)
    T F
    1-13
    直接插入排序是不稳定的排序方法。 (1分)
    T F
    1-14
    排序算法中的比较次数与初始元素序列的排列无关。 (1分)
    T F
    1-15
    排序的稳定性是指排序算法中的比较次数保持不变,且算法能够终止。 (1分)
    T F
    1-16
    采用递归方式对顺序表进行快速排序,每次划分后,先处理较短的分区可以减少递归次数。 (1分)
    T F

    2-1
    对N个元素采用简单选择排序,比较次数和移动次数分别为: (1分)
    A.O(N​2​​), O(N)
    B.O(N), O(logN)
    C.O(logN), O(N​2​​)
    D.O(NlogN), O(NlogN)
    2-2
    对于10个数的简单选择排序,最坏情况下需要交换元素的次数为: (2分)
    A.9
    B.36
    C.45
    D.100
    2-3
    有组记录的排序码为{ 46,79,56,38,40,84 },则利用堆排序的方法建立的初始堆为: (2分)
    A.79,46,56,38,40,80
    B.84,79,56,46,40,38
    C.84,56,79,40,46,38
    D.84,79,56,38,40,46
    2-4
    对N个记录进行堆排序,最坏的情况下时间复杂度是: (1分)
    A.O(logN)
    B.O(N)
    C.O(NlogN)
    D.O(N​2​​)
    2-5
    对N个记录进行堆排序,需要的额外空间为: (1分)
    A.O(1)
    B.O(logN)
    C.O(N)
    D.O(NlogN)
    2-6
    设有100个元素的有序序列,如果用二分插入排序再插入一个元素,则最大比较次数是: (2分)
    A.7
    B.10
    C.25
    D.50
    2-7
    对一组包含10个元素的非递减有序序列,采用直接插入排序排成非递增序列,其可能的比较次数和移动次数分别是: (2分)
    A.100, 100
    B.100, 54
    C.54, 63
    D.45, 44
    2-8
    直接插入排序在最好情况下的时间复杂度为( )。 (2分)
    A.O(logn)
    B.O(n)
    C.O(n*logn)
    D.O(n​2​​)
    2-9
    对于序列{ 49,38,65,97,76,13,27,50 },按由小到大进行排序,下面哪一个是初始步长为4的希尔排序法第一趟的结果? (2分)
    A.13,27,38,49,50,65,76,97
    B.49,13,27,50,76,38,65,97
    C.49,76,65,13,27,50,97,38
    D.97,76,65,50,49,38,27,13
    2-10
    给定初始待排序列{ 15,9,7,8,20,-1,4 }。如果希尔排序第一趟结束后得到序列为{ 15,-1,4,8,20,9,7 },则该趟增量为: (2分)
    A.1
    B.2
    C.3
    D.4
    2-11
    对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。若第一趟排序结果为( 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ),第二趟排序结果为( 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ),则两趟排序采用的增量(间隔)依次是: (2分)
    A.3, 1
    B.3, 2
    C.5, 2
    D.5, 3
    2-12
    对N个不同的数据采用冒泡算法进行从大到小的排序,下面哪种情况下肯定交换元素次数最多? (1分)
    A.从小到大排好的
    B.从大到小排好的
    C.元素无序
    D.元素基本有序
    2-13
    对于7个数进行冒泡排序,需要进行的比较次数为: (2分)
    A.7
    B.14
    C.21
    D.49
    2-14
    采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是: (2分)
    A.每次划分后,先处理较长的分区可以减少递归次数
    B.每次划分后,先处理较短的分区可以减少递归次数
    C.递归次数与每次划分后得到的分区处理顺序无关
    D.递归次数与初始数据的排列次序无关
    2-15
    对N个记录进行快速排序,在最坏的情况下,其时间复杂度是: (1分)
    A.O(N)
    B.O(NlogN)
    C.O(N​2​​)
    D.O(N​2​​logN)
    2-16
    有组记录的排序码为{46,79,56,38,40,84 },采用快速排序(以位于最左位置的对象为基准而)得到的第一次划分结果为: (2分)
    A.{38,46,79,56,40,84}
    B.{38,79,56,46,40,84}
    C.{38,46,56,79,40,84}
    D.{40,38,46,56,79,84}
    2-17
    排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中,不可能是快速排序第二趟结果的是:(2分)
    A.5, 2, 16, 12, 28, 60, 32, 72
    B.2, 16, 5, 28, 12, 60, 32, 72
    C.2, 12, 16, 5, 28, 32, 72, 60
    D.5, 2, 12, 28, 16, 32, 72, 60
    2-18
    对给定序列{ 110,119,7,911,114,120,122 }采用次位优先(LSD)的基数排序,则两趟收集后的结果为: (2分)
    A.7, 110, 119, 114, 911, 120, 122
    B.7, 110, 119, 114, 911, 122, 120
    C.7, 110, 911, 114, 119, 120, 122
    D.110, 120, 911, 122, 114, 7, 119
    2-19
    给出关键字序列{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 },下面哪个选择是按次位优先(LSD)链式基数排序进行了一趟分配和收集的结果? (2分)
    A.→331→431→33→63→24→56→46→57→7→28
    B.→56→28→431→331→33→24→46→57→63→7
    C.→431→331→33→63→24→56→46→57→7→28
    D.→57→46→28→7→33→24→63→56→431→331
    2-20
    对一组数据{ 2,12,16,88,5,10 }进行排序,若前三趟排序结果如下: 第一趟排序结果:2,12,16,5,10,88 第二趟排序结果:2,12,5,10,16,88 第三趟排序结果:2,5,10,12,16,88 则采用的排序方法可能是: (2分)
    A.冒泡排序
    B.希尔排序
    C.归并排序
    D.基数排序
    2-21
    就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是: (1分)
    A.堆排序 < 归并排序 < 快速排序
    B.堆排序 > 归并排序 > 快速排序
    C.堆排序 < 快速排序 < 归并排序
    D.堆排序 > 快速排序 > 归并排序
    2-22
    排序方法中,从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置的方法称为: (1分)
    A.插入排序
    B.选择排序
    C.快速排序
    D.归并排序
    2-23
    在内部排序时,若选择了归并排序而没有选择插入排序,则可能的理由是:(2分)
    1.归并排序的程序代码更短
    2.归并排序占用的空间更少
    3.归并排序的运行效率更高
    A.仅 2
    B.仅 3
    C.仅 1、2
    D.仅 1、3
    2-24
    若数据元素序列{ 11,12,13,7,8,9,23,4,5 }是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是: (2分)
    A.冒泡排序
    B.选择排序
    C.插入排序
    D.归并排序
    2-25
    数据序列{ 3,2,4,9,8,11,6,20 }只能是下列哪种排序算法的两趟排序结果? (2分)
    A.冒泡排序
    B.选择排序
    C.插入排序
    D.快速排序

    展开全文
  • 这是个对你数据结构期末复习起到一定作用的复习资料
  • 数据结构期末复习知识点详解

    千次阅读 2020-12-04 23:50:51
    1、线性表顺序存储结构和链式存储结构的特点 顺序存储时,相连数据元素的存放地址也相邻,逻辑与物理统一;内存中可用的存储单元都是连续的 优点:存储密度大,易于查找和修改 缺点:插入和删除元素时不方便,存储...

    第二章、线性表

    1、线性表顺序存储结构和链式存储结构的特点

    1. 顺序存储时,相连数据元素的存放地址也相邻,逻辑与物理统一;内存中可用的存储单元都是连续的

    优点:存储密度大,易于查找和修改

    缺点:插入和删除元素时不方便,存储空间利用率低,预先分配空间可能造成浪费。

    1. 链式存储时,相邻数据元素可以随意存放,储存空间占两部分,一部分存放数值,一部分存放指针,表示该结点与其他结点的关系。

    优点:插入或者删除很方便,使用灵活,

    缺点,存储密度小,查找和修改需要遍历

    1. 使用情况
      顺序表适宜于做查找这样的静态操作;链表宜于做插入、删除这样的动态操作。

    若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;

    若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。

    顺序表的存储空间是静态分配的

    链表的存储空间是动态分配的

     

    基础知识题

    首元结点是指链表存储线性表中第一个数据结构a1的结点‘

       头结点是首元结点前的结点,数据域不储存数据,指针域指向首元结点’

       头指针是指向链表中第一个结点的指针,或为头节点或为首元结点

    1. (1)在顺序表中插入或者删除元素,需要平均移动n/2个元素,具体移动的元素个数与插入或者删除的位置有关
    1. 顺序表中,各元素物理位置上彼此相邻,链表中并不一定相邻
    2. 链表中,除了首元结点外,任一节点的位置由指针指示。
    3. 在单链表中设置头结点的作用是插入或者删除首元结点时不需要特殊处

    理。

     

     

    • 栈与队列

    1\循环队列头、尾指针的变化规律;队空与队满的判断条件Q.near 队尾 Q.front 队首

    If((Q.near+1)%SIZE ==Q.front) 队列满

    Q.base[Q.rear]=e

    Q.rear=(Q.rear+1)%SIZE

    2\入栈和出栈操作的过程和规律

    后进先出

    3\作业中的基础知识题

    3.2

    (1)线性表

    用一组地址连续的储存单元依次存储线性表的数据元素。以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。只要确定了数据元素的起始位置,就可随机地访问数据元素。但是这种表示方法不便于插入和删除元素,每插入或删除一个元素,都要移动插入或删除位置之后的数据元素在连续储存单元中的位置,而且除了重新分配内存,否则在程序运行过程中不能动态地增加储存单元的数量。

    (2)栈

    和线性表相似,栈也有两种储存方式,顺序栈和链式栈。

    顺序栈的实现在于使用了数组这个基本数据结构,数组中的元素在内存中的存储位置是连续的,且编译器要求我们在编译期就要确定数组的大小,这样对内存的使用效率并不高,一来无法避免因数组空间用光而引起的溢出问题,二在系统将内存分配给数组后,则这些内存对于其他任务就不可用;而链栈使用了链表来实现栈,链表中的元素存储在不连续的地址,由于是动态申请内存,所以我们可以以非常小的内存空间开始,另外当某个项不使用时也可将内存返还给系统。

     

    • 树和二叉树

    1\二叉树的性质

    1. 第i层至多有2的(i-1)次方个结点
    2. 深度为k的二叉树结点最大为2的k次方-1
    3. 终端结点为n个,度为2的结点数为k个,则n=k+1
    4. 具有n个结点的完全二叉树深度为[log₂n]+1
    5. 左右结点和根结点的关系

    2\二叉树的另外两种存储方式

    顺序存储结构,链式存储结构

    3\给定中序+先序(后序),画出二叉树

    中序,左中右,先中序左子树,再访问根节点,再中序右子树

    先序,中左右,先访问根结点,再先序访问左子树,再先序访问右子树

    后序,左右中,后序左子树,后序右子树,再访问根结点

     

     

    1.先在先序子序列中找到当前子树的根节点,即先序子序列的第一个节点是当前子树根节点

    2.在中序子序列中找到当前根节点的位置,并返回下标

    3.根据中序子序列中的当前子树根节点的位置,得到子树的左子树和右子树

    4.根据当前子树的左右子树,分别得到其在先序子序列和中序子序列中开始索引和结束索引

    5.根据得到的索引,判断左右子树是否为空,如果不为空则返回第一步继续执行,如果为空直接返回。

    后序同理

    4\二叉树与森林之间的相互转换

    使用左孩子右兄弟法

    5\哈夫曼树

    6\基本知识点

    6.19 树与二叉树之间的转换 左孩子右兄弟法

    第七章 图

    1、图的相关概念

    顶点,弧,弧尾,弧头

    无向图,有向图,完全图,有向完全图,稀疏图,稠密图

    连通分量,强连通分量 最小生成树(prim或者kruskal)

    2、图的存储结构

    邻接表,邻接矩阵,逆邻接表

    3、图的遍历

    深度,就是一直搜下去,找与之邻接的顶点

    广度,将层数一样的搜出来,在接着搜下一层

    4、求有向图的拓扑排序序列

    在图中找到一个没有前驱的顶点并将其输出;在图中删除该顶点和所有以它为尾的弧

    • 查找

    1、静态查找

    1.顺序查找,就是按index(序号)查找;2.折半查找,二分;3.分块查找,构造索引,分块中最大值/最小值为索引。

    2、哈希函数构造方法

    1.直接定址;2.数字分析(不重要);3.平方取中;4.除留余数5.折叠6.随机数

    3、哈希构造时处理矛盾的方法

    1.开放定址,其实就是对矛盾的数值根据一定的计算重新找到一个未被用过的地址

    2.再哈希,在产生矛盾时计算另一个构造哈希函数的方法

    3.链地址,感觉有点像图的邻接表存储的模型,只是模型

    4.公共溢出区,再开出一块空间,放矛盾的值

    4、基础知识点

    9.21 根据首字母排序 开放寻址法,使用线性探测就可以

    第十章 内部排序

    1、排序的方法

    (1)插入排序

    1.直接插入排序

    关键步骤 将需要插入的数字,从它原先序列的前一个位置开始向前比较

    1. 希尔排序

    d[1]=k 首先将序列分成k个组

    3.起泡排序,冒泡

     

     

     

     

     

     

     

     

     

     

    4.快速排序

    开始,从j开始比较,找到小的,交换,并从i开始比较;同理,又从j开始比较,直到i j重合

     

     

    5.简单选择排序

    从 后n-i+1的几率中找出最小值,与第i个记录进行交换

     

    6.堆排序

    主要是了解堆建立的过程

    在输出堆顶元素后,将最末位的元素交换到堆顶,再进行down操作

    7.归并排序

    将一维数组中相邻的两个有序序列归并成一个有序序列

    开始,一个元素即为一个有序序列,所以第一次排序为两两元素结合

     

     

    8.基数排序

     

    展开全文
  • 数据结果期末复习 几乎 所有重点都在里面 不挂科 一起努力把
  • 数据结构期末复习知识点(兼容版),
  • 里面有八套真题,号称牛逼得金光闪闪的八套题!每套题里边包括了期末考的考试重点及考题类型。如果你搞懂里边每一个题,那数据结构期末考不用愁,期末考必得高分!已经过历届学长学姐及本人验证过……
  • 10小时不太可能了,但是100个小时完全OK的! 送你份独家突击复习资料,以下正文: 据说在期末...数据结构的常考知识点对应的题型有哪些,我也不知道? 不要慌!我特地找到了自己原来突击数据结构时用到的资料,并且又

    10小时不太可能了,但是100个小时完全OK的! 送你份独家突击复习资料,以下正文: 据说在期末考试前夕,同学们的学习能力会变强!但是数据结构,毕竟作为一门特别难的科目,如果平时没有学好,那么很可能就会挂掉!尤其是对于基础不好的同学来说,这简直就是噩梦!

    大家现在担心的无非下面几点!我没认真学,都不知道数据结构到底学了些啥?数据结构的概念,模型规则太多了,又分布在书上的各个地方,找起来好麻烦!数据结构的常考知识点对应的题型有哪些,我也不知道?

    不要慌!我特地找到了自己原来突击数据结构时用到的资料,并且又花了很多的时间精力收集了更多高质量的资料,来帮你轻松战胜数据结构,轻松通过期末考试!

    数据结构的要点总结
    帮你快速搭建一个知识框架,快速弄清数据结构这门课到底学了些什么!

    数据结构常考题型总结(含答案详解)
    啥?不知道数据结构一般都考些啥题?不慌,下面我总结了数据结构的对应知识点的常考题型!

    以上就是数据结构的精华期末复习资料了!由于篇幅有限,只能展示这么多了!祝大家期末考试顺利!

    关注我 ,期末复习不迷路 一个拥有所有基础公共课+大部分专业课全网最全的期末复习资料的硬核学长!
     

    展开全文
  • 很好的广工期末数据结构试卷 里面包含考试重点 考试内容和考试试卷 看了准不会挂科
  • 期末重点都在上面了,平时没学好的,可以下载下来好好看看,应付考试还行
  • 数据结构期末考试复习总结PPT
  • 数据结构期末复习(三) 数组的存储结构 二维数组的顺序存储结构分为以行序为主序的存储方式和以列序为主序的存储方式。 以行序为主的存储方式就是常规的先存第0行的每列,再存第一行的每列,以此类推。以列为主的...
  • 附带答案,期末必备----重点难点,高分必得~~~~~~~
  • 河北工业大学 系统结构 期末复习 重点 考试必备资料
  • 考前必备,一份在手,考试不愁。 想要考出高分么,想要用较少的时间得到很好的效率吗 ,请大家顶一下我的资料。真的是一份难得的资料。 重点推荐。
  • 文章目录数据结构期末复习(第二章 线性表)Part 1、知识点总结1.1线性表的定义1.2线性表的特点1.3线性表的逻辑结构1.4 线性表的要点1.5 线性表的操作2.1 线性表的顺序存储表示2.1.1 初始化2.1.2插入2.1.3顺序线性表...
  • 数据结构期末考试提纲(重点复习知识汇总)

    千次阅读 多人点赞 2020-06-09 16:43:26
    数据结构期末复习系列【陆续更新】 查找(顺序表、树表、哈希表)·题型实练: https://blog.csdn.net/qq_45832958/article/details/106594323 内部排序·题型实练: ...数据结构期末考试提纲(重点复习知识汇总)一、...
  • 文章目录数据结构期末复习(第六章 树与二叉树)Part 1、知识点总结1.1树的基本概念1.2 树的基本术语1.3 树的表示形式2.1 二叉树的概念2.2 二叉树的性质2.3 二叉树的顺序存储结构2.4 二叉树的链式存储结构3.1 二叉树...
  • 文章目录0x01. 冒泡排序 0x01. 冒泡排序 void bubbleSort(int arr[],int len) { //冒泡排序核心算法 for (int i = 0; i < len-1; i++) { //i表示冒泡轮数 for (int j = 0;... arr[j+1]) {...
  • 作业 1简述逻辑结构和存储结构的联系 2数据结构和数据类型有什么区别 3分析以下算法的时间复杂度 void func(int n) {int i=0,s=0; while (s) {i++; s=s+i; } };顺序表算法设计练习;参考算法;顺序表算法设计练习;参考...
  • 文章目录数据结构期末复习(第三章 栈与队列)Part 1、知识点总结1.1.0 栈和队列的基本概念1.1.1 栈的基本概念1.1.2 栈的顺序存储表示1.1.2.1 栈的动态顺序存储表示1.1.2.2 基本实现1.1.2.3 栈的静态顺序存储表示1.1...
  • 当采用分块查找时,数据的组织方式为 数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数 据组成索引块 折半查找与二叉排序树的时间性能有时不相同 采用顺序查找法查找长度为 n 的...
  • SCAU 数据结构2020年期末复习???? 第1章:概念理解:数据结构,时间复杂度 概念: 数据元素是数据的基本单位 一个数据元素可由若干个数据项组成 数据项是不可分割的最小单位 数据对象是性质相同的数据元素的集合 ...
  • 数据结构期末考试复习&知识

    千次阅读 多人点赞 2020-06-15 19:38:31
    前言: 这里是大一期末数据结构备考的一些做题记录,包含了一些知识点和题目,比较多,零散。 文章目录 数组存储 栈 二叉树 哈夫曼树 排序 图 查找 数组存储 二维数组地址问题 一维数组: 对一个有n个数据的一维数组...
  • 第1章 数据结构绪论 第2章 线性表 第3章 栈和队列 第4章 串、 数组和广义表 第5章 树和二叉树 第6章 图 第7章 查找 第8章 排序 三.重点 第一章 第二章 第三章 第四章 第五章 第六章 第七章 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,933
精华内容 773
关键字:

数据结构期末复习重点

数据结构 订阅