数据结构每日一题 2020 Otc#
目录#
1. Week 1#
1.1. Mon#
已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则完全二叉树的结点个数最多是 [郑州大学]
A. 39
B. 52
C. 111
D. 119
答案
答案：C解析：1、第六层只有六个节点，且为叶节点（常想到的）——节点最少情况；
2、第六层满节点，但是其中的八个节点没有孩子节点，因此其也是叶节点（不易想到）——节点最多情况； 本题正是考察第二种情况。
首先，前六层满节点，那么节点个数为：26-1=63
其次，第六层有26-1 =32个节点，其中有8个没有孩子节点，说明第七层有（32-8）*2=48个节点。
因此，最多情况下共有：63+48=111个节点。
1.2. Tue#
散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的 方法是散列文件的关键。[济南大学846-2017]
A．散列函数
B．除余法中的质数
C．冲突处理
D．散列函数和冲突处理
答案
content答案：D解析：本题考查散列表的基础知识。
散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，有可能多个关键字对应一个相同的计算结果，即对应同一个存放地址，这就会产生冲突。这种冲突与散列函数的选取是密切相关的，好的散列函数计算后的结果冲突就少，这也与冲突发生后处理方法有着紧密的联系，好的处理方法在处理一次冲突后不会引起另一次冲突的发生。
2. Week 2#
2.1. Mon#
在单链表中，增加头结点的目的是 。[北京理工大学]
A．方便运算的实现
B．使单链表至少有一个结点
C．标识表结点中首结点的位置
D．说明单链表是线性的链式存储实现
答案
答案：A解析：根据单位链表(包含头结点)的结构，只要掌握了表头，就能够访问整个链表，因此增加头结点的目的是为了便于运算的实现。
此外还有: (1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
2.2. Tue#
设有6个结点的无向图，该图至少应有 条边才能构成一个连通图。[清华大学]
A. 5
B. 6
C. 7
D. 8
答案
答案：A解析：首先确定这道题询问的是连通图。因为有两种图，一种是完全连通图，一种是连通图。完全图是指任意两个结点之间都有一个边相连,也就是结点两两相连；连通图是指任意两个结点之间都有一个路径相连，也就是说只要有连线能相通就好。以其中一个点去连接其余5个点，这样至少5条边就可以构成连通图。
2.3. Wed#
将5个不同的数据进行排序，至多需要比较 次比较。[深圳大学]
A. 8
B. 4
C. 11
D. 10
答案
答案：D解析：5个数据，最坏的情况下，两两均要进行一次比较。即：5 *（5-1）/ 2 = 10，故选 D
2.4. Thu#
设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过 [南京大学-845-2017]
A.log2n + 1
B.log2n - 1
C.log2n
D.log2(n+1)
答案
答案：A解析：因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：
一次二分剩下：n/2
两次二分剩下：n/2/2 = n/4
……
m次二分剩下：n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为n/(2^m)=1; 2^m=n; 此时时间复杂度为log2（n），再与最后一个元素比较复杂度+1，所以时间复杂度为：log2(n)+1。
2.5. Fri#
顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为 [武汉科技大学]
A．21
B．23
C．41
D．62
答案
答案：B解析：法一：利用公式：分块查找成功的平均查找长度为ASL=(s^2+s+n)/2s。在本题中，n=123，s=123/3=41，故平均查找长度为23。
法二：123个元素分成A\B\C三块，每块41个元素，对于A块里面的元素，查找过程的第一步是首先找到A块，再在A块中找到某个元素，由于是顺序查找，找到A块只需一步，然后再在A块中查找指定元素；由于是顺序查找，因此找到第一个元素需要一步，找到第二个元素需要2步，以此类推，找到第41个元素需要41步。
因此，A块中个元素查找长度之分别为2，3，4，···42
对于B块，原理一样，但是找到B块本身需要比找到A块多一步，因为是顺序查找
因此，B块中各个元素查找长度为3，4，5，···43
同理，C块中各个元素查找长度为4，5，6，···44
所以平均查找长度为
2+3+4+...+42
+3+4+5+...+43
+4+5+6+...+44
再除以元素总数123，最后结果是23。
2.6. Sat#
已知一算术表达式的中缀形式为A+BC-D/E，后缀形式为ABC+DE/-，其前缀形式为 [北京航空航天大学]
A．-A+B*C/DE
B．-A+B*CD/E
C．-+*ABC/DE
D．-+A*BC/DE
答案
答案：D解析：将算术表达式的中缀形式作为一棵二叉树的中序遍历序列，将后缀形式作为这棵二叉树的后序遍历序列，再由二叉树的中序遍历序列和后序遍历序列唯一的确定这棵二叉树，在对其进行先序遍历，就可得出算术表达式的前缀形式。
2.7. Sun#
设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是______。[北方交通大学]
A．N1
B．N1+N2
C．N3
D．N2+N3
答案
答案：D解析：由森林转换的二叉树中，根结点即为第一棵树的根结点。根结点的左子树是由第一棵树中除了根结点以外其余结点组成的；根结点的右子树是由森林中除第一棵树外其他树转换来的。
3. Week 3#
3.1. Mon#
一棵完全二叉树上有1001个结点，其中叶子结点的个数是 [西安电子科技大学833-2015]
A．250
B．500
C．501
D．505
答案
答案：C完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
解析1：由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001，所以1002=2n0+n1，在完全二叉树树中，n1只能取0或1，在本题中只能取0，故n=501，因此选C。 解析2：该完全二叉树的层数为10，如果为满二叉树，则节点个数为1023个，但已知节点数为1001个，则叶子节点个数为512 - (22 / 2) = 501。
3.2. Tue#
深度为6(根的层次为1)的二叉树至多有 个结点。[西安电子科技大学833-2015]
A．64
B．32
C．31
D．63
答案
答案：D解析：二叉树是满二叉树时节点最多，满二叉树有2^n-1个节点。
3.3. Wed#
将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度是 。[北京工业大学]
A．0(1)
B．0(n)
C．0(m)
D．O(m+n)
答案
答案：C解析：
1. 先遍历到长度为m的链表的表尾O（m）
2. 将长度为m的表尾连接到长度为n的链表的表头O（1）
3. 最后一个节点接入NULL O（1）
4. Week 4#
4.1. Tue#
对于一个具有N个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为 [厦门大学]
A. N
B. (N-1)^2
C. (N+1)^2
D. N^2
答案
答案：D解析：需要n行n列。首先“邻接矩阵”是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} 。G的邻接矩阵是一个具有下列性质的n阶方阵：
①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。
4.2. Wed#
对有18个元素的有序表R[1...18]作二分查找，则查找A[3]的比较序列的下表依次为 [吉林大学-941-2017]
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
答案
答案：D解析：
在[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]中寻找3，利用二分法的查找的过程；
第一次尝试，[1,18]区间，（1+18）/ 2 = 9, 发现9大于3，所以肯定在左边；
第二次尝试，[1,8]区间，因为上一步发现9大了，所以确定上限是8，（1+8）/ 2 = 4，4大于3；
第三次尝试，[1,3]区间，道理如上，（1+3）/ 2 = 2，2小与2；
第四次尝试，[3,3]，3==3，找到了。
4.3. Thu#
对一组记录的关键码为（46,79,56,38,40,84），如果采用堆排序方法，则建立的初始堆是 [吉林大学-941-2017]
A 79,46,56,38,40,84
B 84,56,79,40,46,38
C 84,79,56,46,40,38
D 84,79,56,38,40,46
答案
答案：D解析：为一个无序序列建立堆的过程就是对完全二叉树从下往上反复"筛选(筛选法调整堆)"的过程。因为完全二叉树的最后一个非叶结点的编号为(n/2)-1,所以"筛选"只需从编号(n/2)-1的结点开始。按照筛选法将完全二叉树调整成满足堆的定义，则得出来的就是初始堆。
构造初始结构：(看选项，使用大顶堆)
46
79 56
38 40 84
从最后一个非叶子结点开始，依次调整：
46
79 84
38 40 56
84
79 46
38 40 56
84
79 56
38 40 46
即84,79,56,38,40,46
4.4. Fri#
在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是 [北京航空航天大学-991-2013]
A. G中有弧
B. G中有一条从Vi到Vj的路径
C. G中没有弧
D. G中有一条从Vj到Vi的路径
答案
答案：D解析：若Vi在Vj前，且有一条从Vj到Vi的路径，则必有环；有环就不是拓扑排序。
4.5. Sat#
栈是一种先进后出的数据结构，一个序列的进栈顺序为abcde，那么不可能的出栈顺序为 [上海海事大学-821]
A. dcbae
B. abcde
C. adbec
D. edcba
答案
答案：C解析：栈的出栈是遵循先进后出的原则，abcde的进栈顺序并不是一次性的按照abcde入栈，也可能是先入栈一部分再出栈一部分在进行入栈，整体的入栈顺序是不变的依然是abcde。所以拿A选项分析，可以是先入栈abcd，再出栈dbca，再入栈e，再出栈e的步骤进行入栈出栈操作。所以不可能的顺序是选项C。
出栈的元素顺序可以遵守的规律如下：
在原序列中相对位置比它靠前的，也就是比它先入栈的，出栈顺序必须是逆序；
在原序列中相对位置比它大的，也就是比它后入栈的，出栈顺序没有要求；
以上两点可以间插进行。
以选项中出栈的第一个元素为基准，判断它后面的元素是否满足上述规律