南宁营销型网站,电脑搭建网站需要空间,一站式网站建设与运营,泸州房地产新闻目录
Δ前言
一、绪论 1.1 数据结构的基本概念 : 1.2 算法和算法评价 :
二、线性表 2.2 线性表的顺序表示 : 2.3 线性表的链式表示 :
三、栈、队列和数组 3.1 栈 3.2 队列 3.3 栈和队列的应用 3.4 数组和特殊矩阵
四、串 4.2 串的模式匹配
五、树与二叉树 5.1 树的基…目录
Δ前言
一、绪论 1.1 数据结构的基本概念 : 1.2 算法和算法评价 :
二、线性表 2.2 线性表的顺序表示 : 2.3 线性表的链式表示 :
三、栈、队列和数组 3.1 栈 3.2 队列 3.3 栈和队列的应用 3.4 数组和特殊矩阵
四、串 4.2 串的模式匹配
五、树与二叉树 5.1 树的基本概念 5.2 二叉树的概念 5.3 二叉树的遍历和线索二叉树 5.4 树、森林 5.5 树与二叉树的应用
六、图 || 七、查找 || 八、排序 Δ前言 博文中涉及的题目均来自《王道数据结构考研复习指导》《竟成408考研复习全书》以及《408统考历年真题》其中真题部分包括09~22年的所有选择题真题。这篇博文只收录了408—数据结构的选择题部分大题部分单独另出博文。注意事项——①点击文章侧边栏目录或者文章开头的目录可以进行跳转。②解析多是一些解题方法和解题思路很多解析都是up自己写得实在简单的题目up没有写解析请读者自己思考。良工不示人以朴up所有文章都会适时补充完善。大家如果有问题都可以在评论区进行交流或者私信up。感谢阅读 一、绪论 1.1 数据结构的基本概念 : 1.以下属于逻辑结构的是(C)。 A.顺序表 B.哈希表 C.有序表 D.单链表 Note : 顺序表、哈希表和单链表是三种不同的数据结构既描述逻辑结构又描述存储结构和数据运算。而有序表是指关键字有序的线性表仅描述了元素之间的逻辑关系它既可以链式存储又可以顺序存储故属于逻辑结构。 2.以下与数据的存储结构无关的术语是(D)。 A.循环队列 B.链表 C.哈希表 D.栈 Note : 数据的存储结构有顺序存储、链式存储、索引存储和散列存储。A选项循环队列是用顺序表实现的队列是一种数据结构。D选项栈是一种抽象数据类型可采用顺序存储或链式存储只表示逻辑结构。数据的逻辑结构独立于其存储结构。 1.2 算法和算法评价 : 3.以下算法的时间复杂度为(D)。
void fun(int n) {int i 1;while (in) i i*2;
} A.O(n) B.O(n^2) C.O(nlog[2]n) D.O(log[2]n) Note : 设最内层语句i i*2; 执行了t次则根据while判断条件有i 2^t n两边同取对数得t log[2]n即T(n) O(log[2]n)。 4.有以下算法其时间复杂度为(C)。
void fun(int n) {int i 0;while (i*i*i n)i;
} A.O(n) B.O(nlog[2]n) C.O(n^1/3) D.O(n^1/2) Note : 设最内层语句i; 执行了t次则根据while判断条件有i tt^3 n所以t n^1/3即T(n) O(n^1/3)。 5.程序段如下(王道书上这题的代码有误不能实现冒泡排序我进行了修正)
for (i n-1; i 0; i--) for (j 0; j i; j) if (a[j] a[j1]) //exchange code 其中n为正整数则最后一行语句的频度在最坏情况下是(D)。 A.O(n) B.O(nlog[2]n) C.O(n^3) D.O(n^2) Note : 该程序段实现的是冒泡排序。冒泡排序是一种稳定的排序方法其平均时间复杂度为O(n^2)最坏情况下的时间复杂度也为O(n^2)。 6.以下算法中加下划线的语句的执行次数为(A)。
int m 0, i, j;for (i 1; i n; i)for (j 1; j 2*i; j)m; //这条语句加了下划线 A.n(n1) B.n C.n 1 D.n^2 Note : m初始值为0“m;”每执行一次m的值加一。先算内层内层for循环执行次数为Σ[1,2i] 1 2i外层for循环继续对2i求和所以总的执行次数为Σ[1,n] 2i 2Σ[1,n] i n(n 1)。 7.[2011真题] 设n是描述问题规模的非负整数下面的程序片段的时间复杂度是(A)。
x 2;
while (x n/2)
x 2*x; A.O(log[2]n) B.O(n) C.O(nlog[2]n) D.O(n^2) Note : 设while循环内层语句x 2*x;执行了t次则x 2^(t 1)根据while判断条件有2^(t 1) n/2∴t log[2](n/2) - 1 log[2]n - 1∴T(n) O(log[2]n)。 8.[2012真题] 求整数n(n ≥ 0) 的阶乘的算法如下其时间复杂度是(B)。
int fact(int n) {if (n 1) return 1;return n*fact(n-1);
} A.O(log[2]n) B.O(n) C.O(nlog[2]n) D.O(n^2) Note : 这是一个简单的递归函数整个程序的基础操作只有递归处的乘法运算n次嵌套递归会进行n次压栈每次递归都执行一次乘法所以共执行n次乘法。∴T(n) O(n)。 9.[2013真题] 已知两个长度分别为m和n的升序链表若将它们合并为长度为 m n 的一个降序链表则最坏情况下的时间复杂度是(D)。 A.O(n) B.O(mn) C.O(min{m,n}) D.O(max{m,n}) Note : 类似于“归并排序”的思想每次从两个升序链表中取出两个元素进行比较已经选出去的元素不会再进行比较∵要建立一个降序链表∴每次将两个元素之中更小的那个元素利用头插法插入到新的降序链表中若其中一个链表已经没有元素可以比较全比完了则直接将另一个链表剩余的元素依次头插到新链表中即可。在最坏情况下比如两个链表的元素大小交替出现时eg : A链表——135B链表——246比较的次数会达到m n - 1次。而由题设条件可知有不等式2max(m,n) mn-1因此T(n) O(max{m,n})。 10.[2014真题] 下列程序段的时间复杂度是(C)。
count 0;
for (k 1; k n; k * 2)for (j 1; j n; j)count; A.O(log[2]n) B.O(n) C.O(nlog[2]n) D.(n^2) Note : 此题比较特殊外层for循环和内层for循环没有关系循环变量没有关联所以可以分别单独计算内外层的时间复杂度相乘即是最终结果。先算内层设count;执行了t次由内层for的循环判断条件语句可知t n再算外层同样由外层for循环的判断条件语句可知t log[2]n所以总的时间复杂度为O(nlog[2]n)。 11.[2017真题] 下列函数的时间复杂度是(B)。
int func(int n) {int i 0, sum 0;while (sum n) sum i;return i;
} A.O(log[2]n) B.O(n^1/2) C.O(n) D.(nlog[2]n) Note : 设while循环内层语句sum i; 执行了t次可知sum 0 1 2 3 4 ... ii t根据while判断条件有i*(i1) / 2 n所以T(n) n^1/2。 12.[2019真题] 设n是描述问题规模的非负整数下列程序段的时间复杂度是(B)。
x 0;
while (n (x1) * (x1))
x x 1; A.O(log[2]n) B.O(n^1/2) C.O(n) D.O(n^2) Note : 设while循环内层语句x x 1; 执行了t次则x t根据while判断条件有(t 1)^2 n∴T(n) O(n^1/2)。 二、线性表 2.2 线性表的顺序表示 : 13.线性表的顺序存储结构是一种(A)。 A.随机存取的存储结构 B.顺序存取的存储结构 C.索引存取的存储结构 D.散列存取的存储结构 Note : 此题“存取方式”指的是读写方式。顺序表是一种支持随机存取的存储结构只要根据起始地址加上元素的序号可以访问到顺序表中任意一个元素。 14.一个线性表最常用的操作是存取任一指定序号的元素并在最后进行插入、删除操作则利用(A)存储方式可以节省时间。 A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表 Note : 此题ABCD中只有顺序表可以按元素序号进行随机存取而不需要进行链表的遍历且在顺序表最后进行增删操作时不需要移动任何元素因此时间开销小。 15.在一个长度为n的顺序表中删除第i (1 ≤ i ≤ n) 个元素时需向前移动(C)个元素。 A.n B.i - 1 C.n-i D.n-i1 Note : 注意题干中说的是“删除”操作所以要移动n-i个元素。Δ注意线性表中元素的位序是从1开始的而数组中元素的下标是从0开始的。 16.设线性表有n个元素严格来说以下操作中(C)在顺序表上实现要比在链表上实现的效率高。 Ⅰ.输出第i (1 ≤ i ≤ n) 个元素值 Ⅱ.交换第3个元素和第4个元素的值 Ⅲ.顺序输出这n个元素的值 A.Ⅰ B.Ⅰ、Ⅲ C.Ⅰ、Ⅱ D.Ⅱ、Ⅲ Note : 对于Ⅰ和Ⅱ由于顺序表具有“随机存取”的特性因此在顺序表上实现“改查”效率更高。对于Ⅲ要求遍历整个线性表因此顺序表上和链表上时间复杂度相同。 2.3 线性表的链式表示 : 17.下列关于线性表的说法中正确的是(D)。 Ⅰ.顺序存储方式只能用于存储线性结构 Ⅱ.取线性表的第i个元素的时间与i的大小有关 Ⅲ.静态链表需要分配较大的连续空间插入和删除不需要移动元素 Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n) Ⅴ.若用单链表来表示队列则应该选用带尾指针的循环链表 A.Ⅰ、Ⅱ B.Ⅰ、Ⅲ、Ⅳ、Ⅴ C.Ⅳ、Ⅴ D.Ⅲ、Ⅳ、Ⅴ Note : 对于Ⅰ顺序存储方式同样可以存储树和图比如一棵只有树干的树对于Ⅱ取出线性表中的第i个元素所需要的时间应该考虑线性表的存储方式以及所取的元素在表中的位置如果是顺序存储由于顺序表满足“随机存取”的特性因此不管i多大取出一个元素的时间复杂度都是O(1)而如果是链式存储越靠后的元素取出所需的时间越长遍历链表。 18.给定有n个元素的一维数组建立一个有序单链表的最低时间复杂度是(D)。 A.O(1) B.O(n) C.O(n^2) D.O(nlog[2]n) Note : 若先建立单链表然后通过直接插入排序从前往后查找元素的位置并依次插入直接插入排序算法的时间复杂度为O(n^2)若先对数组进行排序再建立对应的单链表对数组进行排序最好的时间复杂度是O(nlog[2]n)而建立单链表的时间复杂度是O(n)根据时间复杂度计算的加法原则【T(n) T1(n) T2(n) O(f(n)) O(g(n)) O(max{f(n), g(n)})即多项相加只保留最高阶的项且系数置为1】总的时间复杂度为O(nlog[2]n)。 19.将长度为n的单链表链接在长度为m的单链表后面其算法的时间复杂度是(C)。 A.O(1) B.O(n) C.O(m) D.O(nm) Note : 由于题中没有提到m链表设有尾指针因此要先遍历m链表找到该单链表的尾结点故时间复杂度为O(n)。 20.在一个长度为n的带头结点的单链表h上设有尾指针r则执行()操作与链表的表长有关。 A.删除单链表中的第一个元素 B.删除单链表中的最后一个元素 C.在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 Note : 注意在408统考中当提到一个链表具有头结点时这通常隐含了该链表有一个指向头结点的头指针。对于B选项删除单链表中最后一个元素时需要修改其前驱的next指针域以及修改尾指针r的指向。 21.在长度为n的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是(B)。 A.O(1) B.O(n) C.O(n^2) D.O(log[2]n) Note : 假设单链表是递增有序先找到大于x的结点的直接前驱p在p之后插入该结点。故T(n) O(n) O(1) O(n)。 22.设对n(n1) 个元素的线性表的运算只有四种删除第一个元素删除最后一个元素在第一个元素之前插入新元素在最后一个元素之后插入新元素则最好使用(C)。 A.只有尾结点指针没有头结点指针的循环单链表 B.只有尾结点指针没有头结点指针的非循环双链表 C.只有头结点指针没有尾结点指针的循环双链表 D.既有头结点指针又有尾结点指针的循环单链表。 Note : 重点关注“删除最后一个元素”的操作对于A和D如果要删除最后一个元素必须修改其直接前驱的指针域和尾结点指针因此需要遍历整个链表时间复杂度为O(n)。对于B删除第一个元素时需要通过结点的prior指针依次往前找到链表的头结点时间复杂度为O(n)。对于C四种操作的时间复杂度均为O(1)。 23.某线性表用带头结点的循环单链表存储头指针为head当head-next-nexthead成立时线性表长度可能是(D)。 A.0 B.1 C.2 D.可能为0或1 Note : 注意循环单链表为空时head-next......-nexthead恒成立因为头结点的指针域始终指向了自己。 24.[2016真题] 已知一个带有表头结点的双向循环链表L结点结构为[prev, data, next]其中prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点正确的语句序列是(D)。 A.p-next-prev p-prev; p-prev-next p-prev; free(p); B.p-next-prev p-next; p-prev-next p-next; free(p); C.p-next-prev p-next; p-prev-next p-prev; free(p); D.p-next-prev p-prev; p-prev-next p-next; free(p); 25.[2016真题] 已知表头元素为c的单链表在内存中的存储状态如下表所示 : 现将f 存放于1014H处并插入单链表若f在逻辑上位于a和e之间则a,e,f的“链接地址”依次是(D)。 A.1010H, 1014H, 1004H B.1010H, 1004H, 1014H C.1014H, 1010H, 1004H D.1014H, 1004H, 1010H 26.[2021真题] 已知头指针h指向一个带头结点的非空单循环链表结点结构为[data,next]其中next是指向直接后继结点的指针p是尾指针q是临时指针现要删除该链表的第一个元素正确的语句序列是(D)。 A.h-next h-next-next; q h-next; free(q); B.q h-next; h-next h-next-next; free(q); C.q h-next; h-next q-next; if(p ! q) p h; free(q); D.q h-next; h-next q-next; if(p q) p h; free(q); Note : 当q和p指向相同时该非空单循环链表只有一个元素只有首结点因此在free(q)之前需要修改尾指针的指向令其指向头结点这样free(q)之后整个链表为空。 三、栈、队列和数组 3.1 栈 27.若一个栈的输入序列是123...n输出序列的第一个元素是n则第i个输出元素是(D)。 A.不确定 B.n - i C.n - i - 1 D.n - i 1 Note : 根据栈“先进后出”的特性当输出序列的第一个元素是n时表明之前的n - 1个元素已经按顺序依次入栈∴此时得到的输出序列一定是原序列的逆序列而n, n-1, ..., 3, 2, 1序列中第i个元素为n - i 1。 28.一个栈的输入序列为123...n输出序列的第一个元素是i则第j个输出元素是(D)。 A.i - j - 1 B.i - j C.j - i 1 D.不确定 Note : To be, or not to be, that is the question. 29.若一个栈的输入序列是P1, P2, ..., Pn输出序列是1, 2, 3, ..., n, 若P3 1则P1的值(C)。 A.可能是2 B.一定是2 C.不可能是2 D.不可能是3 Note : 由题设条件可知P3是第一个出栈的元素根据栈“先进后出的特性可知当P3出栈时P1,P2一定还在栈中所以下一个出栈的元素不可能是P1而下一个输出的元素是2所以P1不可能是2。 30.已知一个栈的入栈序列是1,2,3,4其出栈序列为P1, P2, P3, P4则P2, P4不可能是(C)。 A.2,4 B.2,1 C.4,3 D.3,4 Note : 对于C选项当P2 4P3 3时可知P1只能为1或2不论P1是1还是2当P2出栈的时候3一定还在栈中而出栈序列下一个元素是P3所以P4不可能为3。 31.[2009真题] 设栈S 和队列Q 的初始状态均为空元素abcdefg依次进入栈S若每个元素出栈后立即进入队列Q且7个元素出队的顺序是bdcfeag则栈S 的容量至少是(C)。 A.1 B.2 C.3 D.4 32.[2010真题] 若元素a, b, c, d, e, f依次进栈允许进栈、退栈操作交替进行但不允许连续3次进行退栈操作不可能得到的出栈序列是(D)。 A.dcebfa B.cbdaef C.bcaefd D.afedcb 33.[2011真题] 若元素a, b, c, d, e依次进入初始为空的栈中若元素进栈后可停留、可出栈直到所有元素都出栈则在所有可能的出栈序列中以元素d开头的序列个数是(B)。 A.3 B.4 C.5 D.6 34.[2013真题] 一个栈的入栈序列为1, 2, 3, ..., n出栈序列是P1, P2, P3, ..., Pn。若P2 3则P3可能取值的个数是(C)。 A.n - 3 B.n - 2 C.n - 1 D.无法确定 Note : 由栈“先进后出”的特性可知P3可以取到大于3的任何数进一步分析可知P3亦可取到1和2所以P3只取不到3即P3可能取值的个数是n - 1。 35.[2017真题] 下列关于栈的叙述中错误的是(C)。 Ⅰ.采用非递归方式重写递归程序时必须使用栈 Ⅱ.函数调用时系统要用栈保存必要的信息 Ⅲ.只要确定了入栈次序即可确定出栈次序 Ⅳ.栈是一种受限的线性表允许其在两端进行操作。 A.仅Ⅰ B.仅Ⅰ、Ⅱ、Ⅲ C.仅Ⅰ、Ⅲ、Ⅳ D.仅Ⅱ、Ⅲ、Ⅳ Note : 对于Ⅰ计算斐波那契数列迭代实现只需要一个循环即可实现。 36.[2018真题] 若栈S1 中保存整数栈S2 中保存运算符函数F()依次执行下述各步操作 1从S1 中依次弹出两个操作数a 和 b。 2从S2 中弹出一个运算符op。 3执行相应的运算b op a。 4将运算结果压入S1 中。 假定S1 中的操作数依次是5, 8, 3, 22在栈顶S2 中的运算符依次是*、-、在栈顶。调用3次F()后S1栈顶保存的值是(B)。 A.-15 B.15 C.-20 D.20 37.[2020真题] 对空栈S 进行Push 和 Pop操作入栈序列为a, b, c, d, e经过Push, Push, Pop, Push, Pop, Push, Push, Pop操作后得到的出栈序列是(D)。 A.b, a, c B.b, a, e C.b, c, a D.b, c, e 3.2 队列 38.若用数组A[0...5] 来实现循环队列且当前rear和front的值分别为1 和 5当从队列中删除一个元素再加入两个元素后rear 和 front的值分别为(B)。 A.3 和 4 B.3 和 0 C.5 和 0 D.5 和 1 Note : 循环队列默认front指向队头元素rear指向队尾元素的下一个元素。可知数组A的最大容量是6且当前队列中有2个元素A[5]和A[0]其中队头元素是A[5]队尾元素是A[0]删除一个元素后front指向从5变成0加入两个元素后rear指向从1变成3。 39.用链式存储方式的队列进行删除操作时需要(D)。 A.仅修改头指针 B.仅修改尾指针 C.头尾指针都要修改 D.头尾指针可能都要修改 Note : 注意是“删除”操作若删除的队头元素不是队列中唯一一个元素则仅需要修改头指针若删除的元素是队列中唯一一个元素则头尾指针都需要进行修改删除后队列为空即令rear front。 40.假设循环单链表表示的队列长度为n队头固定在链表尾若只设头指针则进队操作的时间复杂度为(A)。 A.O(n) B.O(1) C.O(n^2) D.O(nlog[2]n) Note : 队头在链表尾说明队尾在链表头而队列的“进队/入队”操作是在队尾进行的对应于此题即在链表头进行又因为该循环单链表只设了头指针所以删除表头结点的操作本身只需要O(1)的时间复杂度但是删除后要维护链表“循环”的特性因此需要遍历链表找到链表表尾结点故总的时间复杂度T(n) O(1) O(n) O(n)。 41.若以1, 2, 3, 4作为双端队列的输入序列则既不能由输入受限的双端队列得到又不能由输出受限的双端队列得到的输出序列是(C)。 A.1, 2, 3, 4 B.4, 1, 3, 2 C.4, 2, 3, 1 D.4, 2, 1, 3 Note : 结论记住即可C选项输入或者输出受限的双端队列都得不到该输出序列。B选项输入受限可得输出受限不可得。D选项输出受限可得输入受限不可得。 42.[2010真题] 某队列允许在其两端进行入队操作但仅允许在一端进行出队操作若元素a,b,c,d,e依次入此队列后再进行出队操作则不可能得到的出队序列是(C)。 A.b,a,c,d,e B.d,b,a,c,e C.d,b,c,a,e D.e,c,b,a,d Note : 对于“输出”受限的双端队列求出队序列时只需要关心能不能通过入队操作“插”成一个想要的输出序列。 43.[2011真题] 已知循环队列存储在一维数组A[0...n-1]中且队列非空时front 和 rear分别指向队头元素和队尾元素。若初始时队列为空且要求第一个进入队列的元素存储在A[0]处则初始时front 和 rear的值分别是(B)。 A.0, 0 B.0, n - 1 C.n - 1, 0 D.n - 1, n - 1 Note : 注意此题中rear的指向与默认的循环队列不同此题中rear直接指向了队尾元素这意味着在进行“入队”操作时“送值”和“指针移动”的顺序会发生改变在默认的循环队列中rear指向队尾元素的下一个位置那么在入队时需要先送值再进行指针移动(即rear指针顺时针移动1位)而在此题中需要先令rear指针 1再送值。因此若想第一个进入队列的元素存储再A[0]处由于是先移动指针再送值rear在初始队列为空时必须指向A[0]之前的一个位置而根据循环队列的特性A[0]再往前就是数组的末尾了即n - 1。而由于入队操作不修改front指针所以front指针直接指向0处。 PS : 注意此题中对队列的判空条件为——Q.rear - 1) Q.front。 44.[2014真题] 循环队列放在一维数组A[0...M-1] 中end1指向队头元素end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中正确的是(A)。 A.队空end1 end2; 队满end1 (end2 1) mod M B.队空end1 end2; 队满end2 (end1 1) mod (M - 1) C.队空end2 (end1 1) mod M; 队满end1 (end2 1) mod M D.队空end1 (end2 1) mod M; 队满end2 (end1 1) mod (M - 1) Note : 由题设条件可知这是一个标准的默认循环队列此题中end1代表frontend2表示rear。显然选A。关于“队满”条件的判定联系取余运算mod引入的原因以及顺序存储的队列——数据结构的定义[宏定义MaxSize]。 45.[2016真题] 设有如下图所示的火车车轨入口到出口之间有n条轨道列车的行进方向均为从左至右列车可驶入任意一条轨道。现有编号为1~9的9列列车驶入的次序依次是8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为1~9则n至少是(C)。 A.2 B.3 C.4 D.5 Note : 若要使乱序驶入的火车以“1~9”的顺序依次驶出需要满足两个条件——①每条轨道上的列车都是降序排列每条轨道上都是编号小的列车先出来②编号为1的列车必须位于某条轨道的第一位。可知选C。 46.[2018真题] 现有队列Q 与栈S 初始时Q中的元素依次是1234561在队头S为空。若仅允许下列3种操作①出队并输出出队元素②出队并将出队元素入栈③出栈并输出出栈元素则不能得到的输出序列是(C)。 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 Note : 根据队列“先进先出”的特性若没有栈S参与队列Q的出队序列是唯一的即1,2,3,4,5,6顺序输出因此若想让队列前面的元素之后再输出就必须让这些元素先进栈之后再出栈。对于C选项由于输出序列的第一个元素为3可知元素1,2此时一定在栈中根据栈“先进后出”的特性可知2一定比1先出栈所以不可能得到C选项中的序列。 47.[2021真题] 初始为空的队列Q的一端仅能进行入队操作另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是12345则不能得到的出队序列是(D)。 A.5,4,3,1,2 B.5,3,1,2,4 C.4,2,1,3,5 D.4,1,3,2,5 3.3 栈和队列的应用 48.利用栈求表达式的值时设立运算数栈OPEN。假设OPEN只有两个存储单元则在下列表达式中不会发生溢出的是(B)。 A.A-B*(C-D) B.(A-B)*C-D C.(A-B*C)-D D.(A-B)*(C-D) Note : 可以将ABCD分别从中缀转化为后缀可得A: ABCD-*-B: AB-C*D-C: ABC*-D-D: AB-CD-*可知ACD都会溢出。 49.[2009真题] 为解决计算机主机与打印机之间速度不匹配的问题通常设置一个打印数据缓冲区主机将要输出的数据依次写入缓冲区而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是(B)。 A.栈 B.队列 C.树 D.图 50.[2012真题] 已知操作符包括、-、*、/、(、)。将中缀表达式ab-a*((cd)/e-f)g转换为等价的后缀表达式abacde/f-*-g时用栈来存放暂时还不能确定运算次序的操作符。栈初始为空时转换过程中同时保存在栈中的操作符的最大个数是(A)。 A.5 B.7 C.8 D.11 Note : 注意栈中存放的是还不能确定运算次序的操作符即当一个运算符已经确定了运算次序时它就要出栈。中缀表达式从左往后看第一个号ab很快就确定了运算次序因此第一个号不会停留在栈中继续-, *, (, (, 一直到扫描到d之前这五个操作符都没有确定运算次序因此这五个运算符都还停留在栈中∴选A。 51.[2014真题] 假设栈初始为空将中缀表达式a/b(c*d-e*f)/g转换为等价的后缀表达式的过程中当扫描到f时栈中的元素依次是(B)。 A.(*- B.(-* C./(*-* D./-* Note : 由于中缀表达式的运算符位于操作数的中间因此当扫描到中缀表达式中的运算符时还无法确定该操作符的运算次序还不能输出所以需要一个栈来存放这些还不能确定的操作符。依然是中缀表达式从左往后看第一个/号很快就确定了运算次序a/b当扫描到b时第一个/号出栈不会在栈中停留继续(这两个运算符也不能确定次序依次压栈继续c*d次序确定因此第一个*号不会在栈中停留继续-*依次压栈。所以在扫描到f时栈中的元素依次是, (, -, *四个运算符。 52.[2015真题] 已知程序如下
int S(int n)
{ return (n 0) ? 0 : S(n-1) n; }
void main()
{ coutS(1); } 程序运行时使用栈来保存调用过程的信息自栈底到栈顶保存的信息依次对应的是(A)。 A.main() - S(1) - S(0) B.S(0) - S(1) - main() C.main() - S(0) - S(1) D.S(1) - S(0) - main() 3.4 数组和特殊矩阵 53.有一个n*n的对称矩阵A将其下三角部分按行存放在一维数组B中而A[0][0]存放于B[0]中则第i 1行的对角元素A[i][i]存放于B中的(A)处。 A.(i 3)i / 2 B.(i 1)i / 2 C.(2n - i 1)i / 2 D.(2n - i - 1)i / 2 Note : 由题设条件可知矩阵下标从[0][0]开始并且对应存储的数组B下标也是从[0]开始。由于是按行存放∴到第i行第i列的A[i][i]一共有1 2 ... i1个元素第0行共1个元素即A[0][0]即一共有(i 2)(i 1) / 2个元素对应于数组B下标即(i 2)(i 1) / 2 - 1即(i 3)i / 2。PS : 亦可“特值代入”取i 1A[1][1]对应于B[2]中。 54.在一个二维数组A中假设每个数组元素的长度为3个存储单元行下标i为0~8列下标j为0~9从首地址SA开始连续存放。在这种情况下元素A[8][5]的起始地址为(D)。 A.SA 141 B.SA 144 C.SA 222 D.SA 255 Note : 直接计算当前元素A[8][5]前面有几个元素即可。 55.将三对角矩阵A[1...100][1...100]按行优先存入一维数组B[1...298]中A中元素A[66][65]在数组B中的位置k为(B)。 A.198 B.195 C.197 D.196 Note : 由题设条件可知矩阵下标从[1][1]开始并且对应存储的数组B下标也是从[1]开始。注意三对角矩阵的特点除了第一行和最后一行只有2个非零元素外每一行都存放有3个非零元素。具体解题方法同上一题算就完事儿A[66][65]前面有194个元素∴它自己的位置就是194 1 195。 56.若将n阶上三角矩阵A按列优先级压缩存放在一维数组B[1...n(n1)/21]中则存放到B[k]中的非零元素a[i,j]1i,jn的下标i, j 与k的对应关系是(C)。 A.i(i1)/2 j B.i(i-1)/2 j - 1 C.j(j-1)/2 i D.j(j-1)/2 i - 1 Note : 仍然注意到矩阵A 和 数组B的下标范围。假设B[k]个元素位于矩阵的第j列由于矩阵采取“列优先”进行存储所以前面j-1列共j(j-1)/2个元素而B[k]位于第j列的第i行由下标关系可知B[k]是第j列的第i个元素所以B[k]本身的行列下标和数组下标的关系就是在j(j-1)/2的基础上加上一个i。 57.若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[1...n(n1)/21]中则存放到B[k]中的非零元素a[i,j]1i,jn的下标i, j 与k的对应关系是(B)。 A.(j - 1)(2n - j 1)/2 i - j B.(j - 1)(2n - j 2)/2 i - j 1 C.(j - 1)(2n - j 2)/2 i - j D.(j - 1)(2n - j 1)/2 i - j - 1 Note : 回顾——“n, n-1, ..., 3, 2, 1”序列中第i个元素为n - i 1。 由于是列优先存储设B[k]位于矩阵中第j列仍然先分析前面j - 1列的元素第1列有n个元素第j - 1列有n - (j - 1) 1 n - j 2个元素所以前面 1 到 j-1 列一共的元素是Σ[1, j-1] (j-1)(2n - j 2)/2。由于B[k]位于矩阵第j列而第j列一共有n - j 1个有效元素即第j列从上往下有n - (n-j1) j - 1个零元素对于下三角矩阵位于上三角区的零元素是不会被存储在对应的数组B中的所以第j列到B[k] 真正存储的有效元素是i - (j-1) i - j 1。所以ijk最后的对应关系就是把前j - 1列存储的元素和第j 列存储的元素加起来即(j-1)(2n - j 2)/2 i - j 1。 58.[2016真题] 有一个100阶的三对角矩阵M其元素m[i,j]1 i,j 100按行优先依次压缩存入下标从0开始的一维数组N中。元素m[30,30] 在N中的下标是(B)。 A.86 B.87 C.88 D.89 Note : 认真计算即可注意计算元素个数时元素m也包含在内因为题干问的就是元素m在数组中的下标。同时注意矩阵和数组下标的表示范围。 59.[2017真题] 适用于压缩存储稀疏矩阵的两种存储结构是(A)。 A.三元组表和十字链表 B.三元组表和邻接矩阵 C.十字链表和二叉链表 D.邻接矩阵和十字链表 Note : 十字链表将行单链表和列单链表结合起来存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法可用于表示树或森林。 60.[2018] 设有一个12*12的对称矩阵M将其上三角部分的元素m[i,j]1 i j 12按行优先存入C语言的一维数组N中元素m[6,6]在N中的下标是(A)。 A.50 B.51 C.55 D.66 Note : ①“上三角部分”包括主对角线元素区分于“上三角区”的概念。 ②C语言一维数组下标默认从0开始。本题对称矩阵下标从1开始。 ③m[6,6] 在本题的对称矩阵中是第6行第一个元素对角线元素。 61.[2020真题] 将一个10*10对称矩阵M的上三角部分的元素m[i,j]1 i j 10按列优先存入C语言的一维数组N中元素m[7,2] 在N中的下标是(C)。 A.15 B.16 C.22 D.23 Note : 利用对称矩阵的特性m[7,2] 实则就是存储m[2,7]从而计算即可注意是列优先。 62.[2021真题] 二维数组A 按行优先方式存储每个元素占用1个存储单元。若元素A[0][0]的存储地址是100A[3][3]的存储地址是220则元素A[5][5]的存储地址是(B)。 A.295 B.300 C.301 D.306 Note : 设每行有x个元素由A[0][0] 和 A[3][3]的存储地址可知3x 3 (220-100)得x 39∴A[5][5]的存储地址为100 (39*5 5) 300。 四、串 4.2 串的模式匹配 63.[2015真题] 已知字符串S为 abaabaabacacaabaabcc模式串t为 abaabc。采用KMP算法进行匹配第一次出现“失配”s[i] ≠ s[j]时i j 5则下次开始匹配时i 和 j的值分别是(C)。 A.i1, j0 B.i5, j0 C.i5,j2 D.i6, j2 Note : 注意到S[]下标从0开始。由于采用KMP算法进行匹配因此主串S的指针i不变∴i 5模式串t的指针回退到相同前缀处进行比较∴j 2。 64.[2019真题] 设主串T abaabaabcabaabc模式串S abaabc采用KMP算法进行模式匹配到匹配成功时为止在匹配过程中进行的单个字符间的比较次数是(B)。 A.9 B.10 C.12 D.15 Note : 当第一次出现“失配”时比较了6次第6次时失配主串指针保持不变模式串从第三个字符开始比较因此再比较4次共10次。 五、树与二叉树 5.1 树的基本概念 回顾——树的性质设T表示一棵树n为树的结点总数h为树的高度k为树的度数 ①n等于T中所有结点的度数之和加1。 ②T的第i层i≥1最多有k^(i-1) 个结点。 ③T中最多有(k^h - 1) / (k -1)个结点。 ④T的最小高度为⌈log[k](n(k - 1) 1)⌉。注意向上取整符号 ⑤T的最大高度为n - k 1。 65.树的路径长度是从树根到每个结点的路径长度的(A)。 A.总和 B.最小值 C.最大值 D.平均值 Note : “树的路径长度” 概念要区分于哈夫曼树的带权路径长度。WPL 树中所有叶结点的带权路径长度(经过的边数 * 该结点权值)之和。 66.对于一棵具有n个结点、度为4的树来说(A)。 A.树的高度至多是n - 3 B.树的高度至多是n - 4 C.第i层上至多有4(i - 1)个结点 D.至少在某一层上正好有4个结点 Note : 要想让已知结点数的树尽可能地高就必须让这棵树尽可能地瘦长即每层结点数尽可能的少设树高为h根据题设条件可知h 3 n∴h n - 3。对于D选项应该是某个结点正好有四个结点而不是某一层。 67.[2010真题] 在一棵度为4的树T中若有20个度为4的结点10个度为3的结点1个度为2的结点10个度为1的结点则树T的叶结点个数是(B)。 A.41 B.82 C.113 D.122 Note : 设树T中共有x个叶结点。利用树的性质①可知20*4 10*3 1*2 10*1 1 20 10 1 10 x解得x 82。 5.2 二叉树的概念 68.设高度为h的二叉树上只有度为0和度为2的结点则此类二叉树中所包含的结点数至少为(B)。 A.h B.2h - 1 C.2h 1 D.h 1 Note : 画图已知高度h题干问“结点数至少”因此二叉树要尽可能地瘦高可知除了根结点所在的第一层外每一层都是2个结点∴总的结点数 2(h - 1) 1 2h - 1所以选B。 69.设二叉树有2n个结点且m n则不可能存在(C)的结点。 A.n个度为0 B.2m个度为0 C.2m个度为1 D.2m个度为2 Note : ①“排除法”设n 3即构造一棵有6个结点的二叉树画图由题干条件可知m 1或m 2排除(A)(B)(D)。 ②“直接法”利用二叉树的性质1可求。 70.设二叉树只有度为0和度为2的结点其结点个数为15则该二叉树的最大深度为(C)。 A.4 B.5 C.8 D.9 Note : 解法同68题。设二叉树深度为h得2h - 1 15∴h 8。 71.高度为h的完全二叉树最少有(C)个结点。 A.2^h B.2^h 1 C.2^(h-1) D.2^h - 1 Note : “排除法”画一棵完全二叉树最下面一层只有最左面一个左孩子结点秒了。 72.一棵有124个叶子结点的完全二叉树最多有(B)个结点。 A.247 B.248 C.249 D.250 Note : ∵有124个叶子结点∴二叉树至少有8层(2^7)而124个叶子结点可以分布在最后一层(即第8层) 和 倒数第二层(第7层)。注意由于是完全二叉树最后一层每删除两个连续叶子结点上一层就会暴露出一个叶子结点(注意这个叶子结点本身是完全二叉树本就有的结点)∴为了使完全二叉树整体有最多的结点并且还要满足124个叶子结点的要求可知最后一层应该删除7个结点这样第8层共121个叶子结点加上上一层暴露出来的3个结点正好是124个叶子结点而这么做的话要比删除8个结点多出1个结点——即最后一层的左孩子结点。由于前面7层加起来有127个结点所以结点总数 127 121 248。 73.已知一棵有2011个结点的树其叶结点个数是116该树对应的二叉树中无右孩子的结点个数是(D)。 A.115 B.116 C.1895 D.1896 Note : “特值法”秒了。由于2011 - 116 1895画图前面1895层每层一个结点最后一层有116个叶结点根据普通树转化为二叉树的原则只有最后一行的前115个结点有右孩子其他所有结点均没有右孩子。 74.[2009真题] 已知一棵完全二叉树的第6层设根为第1层有8个叶结点则该完全二叉树的结点个数最多是(C)。 A39 B.52 C.111 D.119 Note : 注意第6层有8个叶结点会有两种情况——①第6层就是最后一层最后一层共有8个叶结点②第6层不是最后一层8个叶结点是最后一层删除连续的叶结点后上一层所暴露出来的叶结点。 题干问整棵树的结点个数最多所以考虑第二种情况。1~6层共有2^6 - 1 63个结点。而第7层最后一层的叶结点个数是第7层总的叶结点数 - 删除的叶结点数 2^6 - 8*2 64 - 16 48。所以整棵树的结点总数 63 48 111个。 75.[2011真题] 若一棵完全二叉树有768个结点则该二叉树中叶结点的个数是(C)。 A.257 B.258 C.384 D.385 Note : 768个结点∴至少有10层10层全满为2^10 - 1 1023个结点。前面9层一共有2^9 - 1 511个结点所以第10层最后一层一共有768 - 511 257个结点叶结点。又因为257是奇数所以第9层存在一个只有左孩子的非叶结点。第10层全满有2^9 512个结点∴第9层由于删除而暴露出的叶结点的个数 (512 - 257 - 1) / 2 254 / 2 127。∴该二叉树总的叶结点个数 257 127 384。 76.[2018真题] 设一棵非空完全二叉树T的所有叶结点均位于同一层且每个非叶结点都有2个子结点。若T有k个叶结点则T的结点总数是(A)。 A.2k - 1 B.2k C.k^2 D.2^k - 1 Note : 由题设条件可知这是一棵满二叉树且最后一层有k个结点叶结点。由二叉树的性质1可知k n2 1得n2 k - 1∴结点总数 n0 n2 k (k - 1) 2k - 1。 77.[2020真题] 对于任意一棵高度为5且有10个结点的二叉树若采用顺序存储结构保存每个结点占1个存储单元仅存放结点的数据信息则存放该二叉树需要的存储单元至少是(A)。 A.31 B.16 C.15 D.10 Note : 尤其注意题干中“任意”这两个字。由于二叉树已经限定是5层所以存储的结点数的范围是(2^4 - 1) 1 到 2^5 - 1即16 到 31又因为题干问的是“至少”即满足任意性的所有可能的二叉树所以是31。如果问的是最少则为16。 5.3 二叉树的遍历和线索二叉树 78.设nm为一棵二叉树上的两个结点在中序遍历时n在m前的条件是(C)。 A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙 Note : 根据中序遍历“左根右”的特点要想让n在m之前遍历需要满足以下三种情况之一①n在m的左子树上②n是m的左兄弟③m在n的右子树上。可知以上三种情况均满足“n在m左方”。 79.设nm为一棵二叉树上的两个结点在后序遍历时n在m前的条件是(D)。 A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙 Note : 后序遍历的特点是“左右根”因此只要满足n是m子孙n一定会在m之前遍历。 80.先序为A,B,C后序为C,B,A的二叉树共有(D)。 A.1棵 B.2棵 C.3棵 D.4棵 Note : 后序特性“左右根”因此BC在A的左右子树的情况都要考虑到可直接画出。 81.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反则该二叉树一定满足(C)。 A.所有的结点均无左孩子 B.所有的结点均无右孩子 C.只有一个叶结点 D.是任意一棵二叉树 Note : 根据80题的图形排除法秒了。先序ABC后序CBA 82.线索二叉树是一种(C)结构。 A.逻辑 B.逻辑和存储 C.物理 D.线性 Note : 物理结构 存储结构 83.若X是二叉中序线索树中一个有左孩子的结点且X不为根则X的前驱为(C)。 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右的结点 D.X的左子树中最右的叶结点 Note : 中序遍历又因为X有左孩子所以X的前驱一定为其左子树的遍历序列中最后的一个结点。其左子树的遍历仍然满足“左根右”的特性注意X的左子树中最右的结点可能是一个右孩子最右的叶结点也可能是一个只有左孩子的分支结点。 84.(C)的遍历仍需要栈的支持。 A.前序线索树 B.中序线索树 C.后序线索树 D.所有线索树 Note : 后序遍历“左右根”最后访问根结点但由于根结点的右孩子不一定为空所以需要一个栈来保存相关信息。 85.[2009真题] 给定二叉树如下图所示。设N代表二叉树的根L代表根结点的左子树R代表根结点的右子树。若遍历后的结点序列是3175624则其遍历方式是(D)。 A.LRN B.NRL C.RLN D.RNL 86.[2010真题] 下列线索二叉树中用虚线表示线索符后后序线索树定义的是(D)。 87.[2011真题] 一棵二叉树的前序遍历序列和后序遍历序列分别是1,2,3,4 和 4,3,2,1该二叉树的中序遍历序列不会是(C)。 A.1,2,3,4 B.2,3,4,1 C.3,2,4,1 D.4,3,2,1 88.[2012真题] 若一棵二叉树的前序遍历序列为a,e,b,d,c后序遍历序列为b,c,d,e,a则根结点的孩子结点(A)。 A.只有e B.有eb C.有ec D.无法确定 Note : 由先序“根左右”后序“左右根”的特性可知a为根结点e一定为a的左孩子或右孩子假设e为a的左孩子则只需要判断a是否有右孩子又因为后序遍历序列中e后面紧接着遍历a可知a的孩子结点只有e。 89.[2013真题] 若X是后序线索二叉树中的叶结点且X存在左兄弟结点Y则X的右线索指向的是(A)。 A.X的父结点 B.以Y为根的子树的最左下结点 C.X的左兄弟结点Y D.以Y为根的子树的最右下结点 90.[2014真题] 若对下图所示的二叉树进行中序线索化则结点X的左、右线索指向的结点分别是(D)。 A.e,c B.e,a C.d,c D.b,a 91.[2015真题] 先序序列为a,b,c,d 的不同二叉树的个数是(B)。 A.13 B.14 C.15 D.16 Note : ①技巧——先序序列和中序序列的关系相当于以先序序列为入栈次序以中序序列为出栈次序。根据卡特兰数(1/n1)*C[2n,n]将n 4代入可得14。 ②亦可直接手动写出所有可能结果先假设b,c,d均在A的左子树上有5种可能根据对称关系可知b,c,d都在A的左子树或右子树上的情况共有10种可能。再写出b,c,d不在同一棵子树下的情况共4种可能注意当A既有左孩子又有右孩子时不存在对称情况因为要满足先序遍历“根左右”的特性左右子树不能随便交换。 92.[2017真题] 某二叉树的树形如下图所示其后序序列为e,a,c,b,d,g,f树中与结点a同层的结点是(B)。 A.c B.d C.f D.g 93.[2017真题] 要使一棵非空二叉树的先序序列与中序序列相同其所有非叶结点须满足的条件是(B)。 A.只有左子树 B.只有右子树 C.结点的度均为1 D.结点的度均为2 Note : 先序“根左右”中序“左根右”当树中所有分支结点都没有左孩子时可知两序列相同。此题亦可通过画图的方式用排除法。对于C选项并不是充分条件。 5.4 树、森林 94.利用二叉链表存储森林时根结点的右指针是(D)。 A.指向最左兄弟 B.指向最右兄弟 C.一定为空 D.不一定为空 Note : AB选项表述不清楚。但D选项一定对。森林转换为二叉树当森林中只有一棵树时根结点的右指针域为空当森林中出现第二棵树时根结点的右指针将指向原先第二棵树的根结点。 95.设F是一个森林B是由F变换来的二叉树。若F中有n个非终端结点则B中右指针域为空的结点有(C)个。 A.n - 1 B.n C.n 1 D.n 2 Note : 对于F中的非终端结点其所有孩子结点在转换之后最后一个孩子结点的右指针域一定为空所以森林中的n个非终端结点对应到二叉树中会出现n个右指针域为空的结点。又因为森林中最后一棵树的根结点转换到二叉树中是二叉树根结点的最右孩子结点其右指针域也为空。所以总的右指针域为空的结点有n 1个。 结论——树转换为二叉树时对应二叉树中无右孩子的结点个数 分支结点数 1。 96.[2009真题] 将森林转换为对应的二叉树若在二叉树中结点u 是结点v 的父结点的父结点则在原来的森林中u 和 v可能具有的关系是(B)。 Ⅰ.父子关系 Ⅱ.兄弟关系 Ⅲ.u 的父结点与v 的父结点是兄弟关系。 A.只有Ⅱ B.Ⅰ和Ⅱ C.Ⅰ和Ⅲ D.Ⅰ、Ⅱ和Ⅲ Note : 尝试画出二叉树中可能出现的情况对于Ⅰu的左孩子的右孩子是v对于Ⅱu的右孩子的右孩子是v对于Ⅲ直接证明不太好证想到“反证法”假设Ⅲ成立则无法得到“结点u 是结点v 的父结点的父结点”的题目条件所以假设不成立Ⅲ不成立。 97.[2011真题] 已知一棵有2011个结点的树其叶结点个数是116该树对应的二叉树中无右孩子的结点个数是(D)。 A.115 B.116 C.1895 D.1896 Note : 见本篇博文5.2 二叉树的概念——73题原题。 98.[2014真题] 将森林F转换为对应的二叉树TF中叶结点的个数等于(C)。 A.T中叶结点的个数 B.T中度为1的结点个数 C.T中左孩子指针为空的结点个数 D.T中右孩子指针为空的结点个数 Note : 森林中的叶结点若其有右兄弟则转为二叉树后其右指针不为空但转为二叉树后其左指针一定为空。 99.[2016真题] 若森林F有15条边、25个结点则F包含树的个数是(C)。 A.8 B.9 C.10 D.11 Note : 结论——由于一棵树中除根结点外每个结点都有唯一确定的双亲(父结点)所以除根结点外每个结点唯一对应有一条边∴在n个结点的树中有n - 1条边即每棵树的结点数比边数多1。对应于此题25 - 15 10结点数共比边数多10所以森林中有10棵树。 100.[2019真题] 若将一棵树T转化为对应的二叉树BT则下列对BT的遍历中其遍历序列与T的后根遍历序列相同的是(B)。 A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历 101.[2020真题] 已知森林F及与之对应的二叉树T若F的先根遍历序列是a,b,c,d,e,f中根遍历序列是b,a,d,f,e,c则T的后根遍历序列是(C)。 A.b,a,d,f,e,c B.b,d,f,e,c,a C.b,f,e,d,c,a D.f,e,d,c,b,a Note : 实质是求二叉树的先序中序和后序遍历序列的问题。 102.[2021真题] 某森林F对应的二叉树为T若T的先序遍历序列是a,b,d,c,e,g,f中序遍历序列是b,d,a,e,g,c,f则F中树的棵树是(C)。 A.1 B.2 C.3 D.4 5.5 树与二叉树的应用 103.设哈夫曼编码的长度不超过4若已对两个字符编码为1 和 01则还最多可对(C)个字符编码。 A.2 B.3 C.4 D.5 Note : 哈夫曼编码属于前缀编码而前缀编码的特点是“没有一个编码是另一个编码的前缀”由此特性可知若想进行最多的编码应该从长度更长的编码开始考虑因此得到0000000100100011四个。 104.一棵哈夫曼树共有215个结点对其进行哈夫曼编码共能得到(B)个不同的码字。 A.107 B.108 C.214 D.215 Note : 在哈夫曼编码Huffman Coding中“不同的码字”unique code words指的是代表不同字符或符号的、互不相同的编码。 105.若度为m的哈夫曼树中叶子结点个数为n则非叶子结点的个数为(C)。 A.n - 1 B.⌊n/m⌋ - 1 C.⌈(n - 1)/(m - 1)⌉ D.⌈n/(m - 1)⌉ - 1 Note : 回顾——在n个结点的树中有n - 1条边即每棵树的边的个数总是等于结点数减去1。 由一般哈夫曼树(二叉树)的定义可知度为m的哈夫曼树中只有度为0和度为m的结点设度为m的结点即非叶子结点的个数为x每个度为m的结点都贡献了m条边根据树的性质边的个数也等于总结点数 - 1因此可列出等式mx n x - 1移项化简可得x ⌈(n - 1)/(m - 1)⌉。 106.下列关于并查集的叙述中(D)是错误的。 A.并查集是用双亲表示法存储的树 B.并查集可用于实现克鲁斯卡尔算法 C.并查集可用于判断无向图的连通性 D.在长度为n的并查集中进行查找操作的时间复杂度为O(log[2]n) Note : 未做路径优化的并查集在最坏情况下的时间复杂度为O(n)。 107.[2010真题] nn≥2个权值均不相同的字符构成哈夫曼树关于该树的叙述中错误的是(A)。 A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 108.[2014真题] 5个字符有如下4种编码方案不是前缀编码的是(D)。 A.01, 0000, 0001, 001, 1 B.011, 000, 001, 010, 1 C.000, 001, 010, 011, 100 D.0, 100, 110, 1110, 1100 109.[2015真题] 下列选项中给出的是从根分别到达两个叶结点路径上的权值序列属于同一棵哈夫曼树的是(D)。 A.24,10,5 和 24,10,7 B.24,10,5 和 24,12,7 C.24,10,10 和 24,14,11 D.24,10,5 和 24,14,6 Note : 注意24 10 14。24 ≠ 10 12。 110.[2017真题] 已知字符集{a,b,c,d,e,f,g,h}若各字符的哈夫曼编码依次是01001000000101001011110001则编码序列0100011001001011110101的译码结果是(D)。 A.a c g a b f h B.a d b a g b b C.a f b e a g d D.a f e e f g d Note : 根据首尾译码可排除AB又因为中间连续两个“001”即连续两个e所以选D。 111.[2018真题] 已知字符集{a,b,c,d,e,f}若各字符出现的次数分别为6,3,8,2,10,4则对应字符集中各字符的哈夫曼编码可能是(A)。 A.00, 1011, 01, 1010, 11, 100 B.00, 100, 110, 000, 0010, 01 C.10, 1011, 11, 0011, 00, 010 D.0011, 10, 11, 0010, 01, 000 Note : 由前缀编码的特点首先排除BC构造哈夫曼树可知根结点到6的路径为2所以排除D。 112.[2019真题] 对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点则n的值是(C)。 A.56 B.57 C.58 D.60 113.[2021真题] 若某二叉树有5个叶结点其权值分别为1012162130则其最小的带权路径长度WPL是(B)。 A.89 B.200 C.208 D.289 Note : 回顾——树的WPL的定义树中所有叶结点的带权路径长度之和称为该树的带权路径长度。 六、图 || 七、查找 || 八、排序 每次写博文写到2万字左右CSDN的编辑器就开始一卡一卡的可能是我的网络有点拉。没办法第六章“图”的习题带有大量图片如果继续在这篇博文里面写“图、查找、排序”都完成预计一共有4万字左右估计要卡爆了。人不能让尿憋死还是老方法剩余的“图、查找、排序”的内容单独另开一篇博文作为补充可不是因为我能再氵一篇博文(。 补充的博文写完后我会把链接挂在下面。 System.out.println(END------------------------------------);
