Skip to content

数据结构每日一题 2020 August#

目录#

1. Week 1#

1.1. Mon#

若无向图G = （V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是 [中国科学技术大学]

A. 6

B. 15

C. 16

D. 21

答案 答案：C
解析：若保证无向图在任何情况下都是连通的，即任意变动图G中的边，图G始终保持连通，首先需要G的任意6个结点构成完全联通子图G1，需要15条边，然后在添加一条边使第7结点与G1连起来，共需16条边

1.2. Tue#

在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是 [中国科学技术大学]

A. 41

B. 82

C. 113

D. 122

答案 答案：B
解析：树的公理：点数比段数多1，n -1 = 20*4 + 3*10 + 1*2 + 10*1 ，所以n = 122 + 1 = 123 ，其他节点的数量总和为 m = 20 + 10 + 1 +10 = 41 ，所以，叶子节点数为n-m = 123 -41 = 82。

1.3. Wed#

用两个栈S1和S2模拟一个队列操作，若入队列的操作是栈S1入栈，则出队列的操作是 [北京交通大学925-2018]

A. 栈S1出栈

B. 栈S2出栈

C. 若栈S1不空，栈S1出栈；否则栈S2出栈再入栈S1直到栈S2空，栈S1出栈

D. 若栈S2不空，栈S2出栈；否则栈S1出栈再入栈S2直到栈S1空，栈S2出栈

答案 答案：D
解析：利用两个栈S1和S2来模拟一个队列，当需要向队列中插入一个元素时，用S1来存放已经输入的元素，即S1执行入栈操作，当需要出队时，则对S2执行出栈操作。由于从栈中取出元素的顺序是原顺序的逆序，所以先将S1的所有元素全部出栈并入栈到S2中，再在S2中进行出栈操作，就能实现出队操作，而在执行此操作之前，先判断S2是否为空，否则会导致顺序混乱。

1.4. Thu#

模式串T= 'abcaabbcabcaabdab' ， T的next数组值及nextval数组值为 [北京交通大学925]

A.01112231123456712和01100111011001702

B.01112121124567112和01102131011021701

C.01112231123456712和01102131011021701

D.01112121124567112和01100111011001702

答案 答案：C
解析：
id 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
char a b c a a b b c a b c a a b d a b
maxl 0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1 2
next 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
nextval 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 如果 next[i] = next[next[i]]，则 nextval[i] := next[next[i]]，否则 nextval[i] := next[i]。

1.5. Fri#

设有一组关键字{25,46,73,9,14,92,45,31,20,51},用链地址法构造哈希表，哈希函数为H(key)= key MOD 11，则查找不成功时的平均查找长度为 [北京交通大学925-2017]

A. 11/10

B. 12/11

C. 13/10

D. 10/11

答案 答案：D
解析：10个数字mod 11 后结果为 [3,2,7,9,3,4,1,9,9,7]，查找失败时 地址0 比较0次 地址1 比较1次 地址2 比较1次 地址3 比较2次 地址4 比较1次 地址5 比较0次 地址6 比较0次 地址7 比较2次 地址8 比较0次 地址9 比较3次 地址10 比较0次ASL失败=（1+0+1+2+1+0+0+2+0+3+0）/11 =10/11。

2. Week 2#

2.1. Sat#

1.设一段文本中包含字符{a, b, c, d, e}，其出现次数相应为{3, 2, 5, 1, 1}。则经过哈夫曼编码后，文本所占总位数为 [浙江大学878-2017]

A.12

B.25

C.26

D.36

答案 答案：B
根据哈夫曼树，5编码为1，3编码为11，2编码为110，两个1编码为1110和1111，最后的总位数为，5*1 + 3*2 + 2*3 + 2* 4 = 25。

2.2. Sun#

若有一二叉树的总结点数为98，只有一个儿子的结点数为48，则该树的叶结点数是多少？[浙江大学878-2013]

A. 25

B. 50

C. 不确定

D. 这样的树不存在

答案 答案：D
解析：总结点个数为 n0 + n1 + n2，
我们可以得到98 = n0 + n1 + n2
且n1 = 48，同时n0 = n2 + 1
两个式子联立，得到n0 = 51/2 因为结点数不可能是小数，所以不存在这样的树。

3. Week 3#

3.1. Mon#

具有11个顶点的连通无向图，边的总数最多为 ，边的总数最少为 [中南大学943-2016-填空题第8题改编]

A. 10，55

B. 55，10

C. 110，11

D. 11，110

答案 答案：B
解析：对于连通无向图，边的总数最多的情况是此图为无向完全图的时候，此时对于n个顶点，有n*(n-1)/2条边，此题n=11，于是边最多为11*（11-1）/2=55条边的总数最少的情况是此图为树的情况，对于树来说，n个顶点有n-1条边，于是此题中最少10条边。

3.2. Tue#

对广义表A=（（a,（b）），（c，（）），d）执行操作gettail(gethead(gettail(A)))的结果是 [宁波大学916-2019]

A. （）

B. （（））

C. d

D. （d）

答案 答案：B
解析：考察广义表的基本操作。 Head（）函数：取广义表中的第一个元素 Tail（）函数：取广义表中除第一个元素，剩下的元素构成的广义表
于是我们对A先进行一次Tail操作得（（c，（）），d） 再进行一次Head操作得（c，（）） 最后进行一次Tail操作得（（））

3.3. Wed#

在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是 [哈尔滨工程大学]

  1. 归并排序的程序代码更短
  2. 归并排序占用的空间更少
  3. 归并排序的运行效率更高

A. 仅2

B. 仅3

C. 仅1、2

D. 仅1、3

答案 答案：B
解析：选择排序的时间复杂度最优最坏和平均都为O（n2） ，而归并的时间复杂度则都为O(nlog2n), 可见归并的效率高；
越优的算法的步骤就一般会越复杂， 例如冒泡和选择代码都很简单， 所以归并比选择代码复杂; 归并是属于用空间换时间的算法，在堆区new出了空间，而选择排序不需要创建空间，空间复杂度为O(1)。

3.4. Thu#

对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是 [哈尔滨工程大学]

A. 2

B. 1

C. 4

D. 3

答案 答案：C
解析：9和-1替换，7和4替换，增量为4。

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

增量一般初始化为序列长度 的 ，即 。然后比较 和 的大小，若为升序排序，且 ，则交换位置。每遍历完一轮以后 ，当时排序结束。

算法平均复杂度为 。

template <typename _RIter>
void insert_sort(_RIter st, _RIter ed, int delta) {
    for(_RIter i = st + delta; i < ed; i += delta) {
        for(_RIter j = i; j > st; j -= delta)
            if(*j < *(j - delta)) std::swap(*j, *(j - delta));
            else break;
    }
}

template <typename _RIter>
void shell_sort(_RIter st, _RIter ed) {
    for(int delta = ed - st; delta; delta /= 2)
        for(int i = 0; i < delta; i++)
            insert_sort(st + i, ed, delta);
}

4. Week 4#

4.1. Tue#

图G是n个顶点的无向完全图,则下列说法不正确的为: [中国科学院大学-2018]

A. G的邻接多重表需要n(n-1)个边结点和n个顶点结点

B. G的连通分量个数最少

C. G为连通图

D. G所有顶点的度的总和为n(n-1)

答案 答案：A
解析：在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大。
A. 边的条数为C（n,2）=n(n-1)/2。与十字链表类似，在临街多重表中，每条边用一个结点表示。
B. G是完全图，必定是连通图。所以连通分量只有其自身
C. G是完全图，必定是连通图
D. 每个顶点都与其余n-1个顶点相连，则n个顶点度的和为n(n-1)
Back to top