数据结构练习册A.docx

习题册数据结构强化班专属资料 提供全程答案解析2019 年 408 真题【数据结构部分】一、单项选择题：下列每题给出的四个选项中，只有一个选项符合试题要求。1设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是x=0；while（n=（x+1）*（x+1）x=x+l；AO（log n）BO（n1/2）C O（n）DO（n2）2若将一棵树 T 转化为对应的二叉树 BT，则下列对 BT 的遍历中，其编历序列与 T 的后根遍历序列相同的是A先序遍历B中序遍历C后序遍历D按层遍历3对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是A56B57C58D604在任意一棵非空平衡二叉树（AVL 树）T1中，删除某结点 v 之后形成平衡二叉树 T2，再将 v 插入 T2形成平衡二叉树 T3。下列关于 T1与 T3的叙述中，正确的是（I）若 v 是 T1的叶结点，则 T1与 T3可能不相同（II）若 v 不是 T1的叶结点，则 T1与 T3一定不相同（III）若 v 不是 T1的叶结点，则 T1与 T3一定相同A仅B仅C仅、D仅、5下图所示的 AOE 网表示一项包含 8 个活动的工程活动 d 的最早开始时间和最迟开始时间分别是A3 和 7B12 和 12C12 和 14D15 和 156用有向无环图描述表达式（x+y）*（x+y）/x），需要的顶点个数至少是A5B6C8D97选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是数据的规模数据的存储方式算法的稳定性数据的初始状态A仅B仅、C仅、D、8现有长度为 11 且初始为空的散列表 HT，散列函数是 H（key）=key%7，采用线性探查（线性探测再散列）法解决冲突将关键字序列 87，40，30，6，11，22，98，20 依次5插入到 HT 后，HT 查找失败的平均查找长度是A4B525C6D6299设主串 T=“abaabaabcabaabc”模式串 S=“abaabc”，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A9B10C12D1510 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是A5，2，16，12，28，60，32，72B2，16，5，28，12，60，32，72C2，12，16，5，28，32，72，60D5，2，12，28，16，32，72，6011设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是A1B2C3D4二、综合应用题41（13 分）设线性表 L=（a1，a，a3，an-2，an-1，an）采用带头结点的单链表保存，链表中结点定义如下：typedef struct nodeint data；struct node*next；NODE；请设计一个空间复杂度为 O（1）且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L=（a1，an，a2，an-1，a3，an-2，）。要求：（1）给出算法的基本设计思想（2）根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。（3）说明你所设计的算法的时间复杂度。42（10 分）请设计一个队列，要求满足：初始时队列为空；入队时，允许增加队列占用空间；出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；入队操作和出队操作的时间复杂度始终保持为 O（1）。请回答下列问题：（l）该队列应该选择链式存储结构，还是顺序存储结构？（2）画出队列的初始状态，并给出判断队空和队满的条件（3）画出第一个元素入队后的队列状态。（4）给出入队操作和出队操作的基本过程。6参考答案：一、单项选择题1B2B3C4A5C6A7D8C9B10D11B41【答案要点】（l）算法的基本设计思想：算法分 3 步完成。第 1 步，采用两个指针交替前行，找到单链表的中间结点；第 2步，将单链表的后半段结点原地逆置；第 3 步，从单链表前后两段中依次各取一个结点，按要求重排。（2）算法实现：void change_list（NODE*h）NODE*p，*q，*r，*s；p=q=h；while（q-next！=NULL）/寻找中间结点 p=p-next；/p 走一步q=q-next；if（q-nexl！=NULL）q=q-next；/q 走两步q=p-next；/p 所指结点为中间结点，q 为后半段链表的首结点p-next=NULL；while（q！=NULL）/将链表后半段逆置 r=q-next；q-next=p-next；p-next=q；q=r；s=h-next；/s 指向前半段的第一个数据结点，即插入点q=p-next；/q 指向后半段的第一个数据结点p-next=NULL；while（q！=NULL）/将链表后半段的结点插入到指定位置r=q-nex1；/r 指向后半段的下一个结点q-next=s-next；/将 q 所指结点插入到 s 所指结点之后s-next=q；s=q-next；/s 指向前半段的下一个插入点q=r；（3）算法的时间复杂度：参考答案的时间复杂度为 O（n）。42【答案要点】（l）采用链式存储结构（两段式单向循环链表），队头指针为 front，队尾指针为 rear。（2）初始时，创建只有一个空闲结点的两段式单向循环链表，头指针 front 与尾指针7rear 均指向空闲结点。如下图所示。队空的判定条件：front=rear。队满的判定条件：front=rear-next。（3）插人第一个元素后的队列状态：（4）操作的基本过程：2018 年 408 真题【数据结构部分】一、单项选择题：下列每题给出的四个选项中，只有一个选项符合试题要求。1若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F()依次执行下述各步操作：（1）从 S1 中依次弹出两个操作数 a 和 b；（2）从 S2 中弹出一个运算符 op；（3）执行相应的运算 bop a；（4）将运算结果压人 S1 中。假定 S1 中的操作数依次是 5,8,3,2（2 在栈顶），S2 中的运算符依次是*,-,+（+在栈顶）。调 用 3 次 F()后，S1 栈顶保存的值是。A-15B15C-20D202现有队列 Q 与栈 S，初始时 Q 中的元素依次是 1,2,3,4,5,6（1 在队头），S 为空。若仅允 许下列 3 种操作：出队并输出出队元素；出队并将出队元素人栈；出栈并输出出栈元素，则不能得到的输出序列是。A1,2,5,6,4,3B2,3,4,5,6,1C3,4,5,6,1,2D6,5,4,3,2,13设有一个 1212 的对称矩阵 M，将其上三角部分的元素 mi,j（1ij12）按行优先存人 C 语言的一维数组 N 中，元素 m6,6 在 N 中的下标是。8入队操作若（front=rear-next）/队满则在 rear 后面插入一个新的空闲结点；入队元素保存到 rear 所指结点中；rear=rear-next；返回。出队操作若（front=rear）/队空则出队失败，返回；取 front 所指结点中的元素 e；fromt=front-next；返回e。A50B51C55D664设一棵非空完全二叉树 T 的所有叶结点均位于同一层，且每个非叶结点都有 2 个子结点。若 T 有 k 个叶结点，则 T 的结点总数是。A2k-1B2kC?2D2?15已知字符集a,b,c,d,e,f，若各字符出现的次数分别为 6,3,8,2,10,4，则对应字符集中各字符的哈夫曼编码可能是。A00,1011,01,1010,11,100B00,100,110,000,0010,01C10,1011,11,0011,00,010D0011,10,11,0010,01,0006已知二叉排序树如下图所示，元素之间应满足的大小关系是。Ax1x2x5Bx1x4x5Cx3x5x4Dx4x3x57下列选项中，不是如下有向图的拓扑序列的是。A1,5,2,3,6,4B5,1,2,6,3,4C5,1,2,3,6,4D5,2,1,6,3,48高度为 5 的 3 阶 B 树含有的关键字个数至少是。A15B31C62D2429现有长度为 7、初始为空的散列表 HT，散列函数 H(k)=k%7，用线性探测再散列法解 决冲突。将关键字 22,43,15 依次插人到 HT 后，查找成功的平均查找长度是。A1.5B1.6C2D310对初始数据序列（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），则两趟排序采用的 增量（间隔）依次是。A3,1B3,2C5,2D5,311在将数据序列（6,1,5,9,8,4,7)建成大根堆时，正确的序列变化过程是。个数是9A.6,1,7,9,8,4,56,9,7,1,8,4,59,6,7,1,8,4,59,8,7,1,6,4,5B.6,9,5,1,8,4,76,9,7,1,8,4,59,6,7,1,8,4,59,8,7,1,6,4,5C.6,9,5,1,8,4,79,6,5,1,8,4,79,6,7,1,8,4,59,8,7,1,6,4,5D.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二、综合应用题41(13 分)给定一个含 n(n1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数 组中未出现的最小正整数。例如,数组-5,3,2,3中未出现的最小正整数是 1；数组1,2,3中未出 现的最小正整数是 4。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。42(12 分)拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市，题 42 图中无向边上的权值表示两个城市间备选光缆的铺设费用。请回答下列问题。（1）仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。（2）题 42 图可采用图的哪一种存储结构？给出求解问题（1）所使用的算法名称10参考答案：一、单项选择题1B2C3A4A5A6C7D8B9C10D11A41【答案要点】（l）算法的基本设计思想：设要查找的数组中未出现的最小正整数为 K。K 取值范围之内是1,n+1。采用类似计数排序的思想分配一个数组 Bn,用来标记 A 中是否出现了 1n 之间的正整数。从左至右依次扫描数组元素 Ai 并标记数组 B。若 Ai 是负数、零或是大于 n，则忽略该值，否则根据计数排序的思想将 BAi-1置为 1。标记完毕，遍历数组 B，查找第一个值为 0 的元素，其下标+1 即为目标元素 K；找不到 0 时，K=n+1。（2）算法实现：int findMissMin(int A,int n)int i,*B;/标记数组B=(int*)malloc(sizeof(int)*n);/分配空间memset(B,0,sizeof(int)*n);/赋初值为 0for(i=0;i0&Ai=n)/若 Ai的值介于 1n，则标记数组 BBAi-1=1;for(i=0;irlink；/*q 指向 p 所指结点的直接后继结点*/if(q-rlink!=NULL)/*若 q 所指结点不是链表的最后结点*/q-rlink-llink=p；/*将结点 P 插入到结点 q 的直接后继结点的前面*/p-rlink=q-rlink；/*将结点 q 的直接后继结点插入到结点 p 的后面*/P-llink-rlink=q；/*将结点 q 插入到结点 p 的前面*/q-llink=p-llink；q-rlink=p；37p-llink=q；2.设某堆栈采用顺序存储结构，元素利，a1,a2,a3,a4,a5,a6批依次进栈，若 6 个元素的出栈顺序为 a2，a3，a4，a6，a5，a1,则堆栈的容量至少应该是多少个元素的空间？请利用图示说明你的结论。3.己知某二叉树采用顺序存储结构(如题三 3 图所示)，其中，空白处表示结点不存在。请分别给出该二叉树的前序遍历序列和后序遍历序列。题三 3 图4.已知某无向图采用邻接表存储，邻接表如题三 4图 所示。请分别写出从顶点 A 出发进行深度优先遍历与 广度优先遍历后得到的遍历序列。四、算法设计题(本题 15 分)己知长度为 n 的顺序表 A 中元素按值从小到大排列，请写出在该顺序表中插入一个新的数据元素 item 的非递归算法。要求：插入新元素之前采用折半査找法确定新元素的插入位置。382018 年中国科学院大学数据结构部分39402019 年华中科技大学数据结构与算法分析一、名词解释（20 分）时间复杂度哈夫曼树稳定排序拓扑排序链式存储结构二、选择题（40 分）1.算法的空间复杂度与（）有关。A.源程序长度B.计算机内存大小C.编译程序D.问题规模大小2.以下关于线性表错误的是（）。A.线性表元素个数有限B.线性表可以顺序表示和链式表示C.数组是线性表D.可以给线性表中每个元素一个序号3.有一个栈，元素 ABCDE 依次进栈，这 5 个元素，出栈顺序为 CBAED，则栈容量至少为？（）。A.2B.3C.5D.44.一个进行产生数据供另外一个进程处理，两个进程间的速度可能不同步，使用下列哪个数据结构可以有助于解决两个进程间的同步问题？（）。A.栈B.队列C.树D.图5.一个长度为 8 的串的字串有（）个。A.8B.9C.3741D.2566.一个树含有 30 个节点，则它的最大高度为（）。A.5B.4C.6D.307.某二叉树有两个节点 p 与 q，对该树进行中序遍历时，p 在 q 的前面，则（）。A.p 是 q 的祖先B.q 是 p 的祖先C.p 在 q 左边D.q 在 p 左边8.有 n 个顶点的无向连通图最少有（）条边。A.n+1B.nC.n-1D.n（n-1）/29.下列关于查找的说法，错误的是（）。A.对含有 n(n0）个元素的哈希表进行查找，最坏情况下的查找代价为 O（n）B.对于所有数据结构上的所有查找算法，最好的查找代价为 O（1）C.在数组上进行查找，数组中元素必须有序D.在单链表上进行查找的最好情况下的代价为 O（1）10.为了更好的实现快速排序算法，待排序元素宜采用下列哪个结构存储？（）。A.单链表B.数组C.双链表D.循环链表三.简答题（40 分）1。求 T(n)=2T(n/4)+n的非递归解并证明（10 分）2.证明 n 个节点的无向联通图最少有 n-1 条边（7 分）423 求时间复杂度（7 分）void pipi（int n）int p=1，r=n；while（r0）p=p*2;r=r/2;4 前序遍历和后续遍历能否确定一个二叉树，中序遍历先序遍历能否确定一颗二叉树，并分别解释原因（6 分）5 如何用优先队列实现先进先出队列？实现后的出队与入队操作的时间复杂度是多少？（10 分）四.代码题（50 分）1.C 语言算法实现二叉树中求最小值，并分析时间复杂度。2.C 语言算法实现邻接链表转化成邻接矩阵，并分析时间复杂度。3.大小为 n 的数组中双端队列 C 语言算法实现相关操作，出入队时间复杂度 O(1)。432019 年华中科技大学 887 数据结构与算法分析参考答案一、名词解释（20 分）时间复杂度【皮皮解析】算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n)。它表 示随问题规模 n 的增大，算法执行时间的增长率和 f(n）的增长率相同，称作算法的渐近时 间复杂度，简称为时间复杂度。其中 f(n）是问题规模 n 的某个函数。哈夫曼树【皮皮解析】在含有 N 个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树或最优二叉树。稳定排序【皮皮解析】假设 Ri=Rj，且在排序之前 Ri 领先于 Rj，若在排序后的序列中 Ri 仍然领先于 Rj，则称所用的排序算法是稳定的，反之则称所用的算法是不稳定的拓扑排序【皮皮解析】：将有向图中的顶点以线性方式进行排序,通过偏序得到图的全序。即对于任 何连接自顶点 u 到顶点 v 的有向边，在最后的排序结果中，顶点 u 总是在顶点 v 的前面。链式存储结构【皮皮解析】：线性表的存储结构有顺序存储结构和链式存储结构两种，前者称为顺 序表，后者称为链表，其中顺序表是保存在一片连续的存储空间中的，而链表则是通过指针来与其他数据进行联系，每个数据元素除了存储元素本身信息，还要存储与其他数据之间的 关系。二、选择题（40 分）1.算法的空间复杂度与（）有关。A.源程序长度B.计算机内存大小C.编译程序D.问题规模大小【皮皮解析】：D2.以下关于线性表错误的是（）。A.线性表元素个数有限B.线性表可以顺序表示和链式表示C.数组是线性表D.可以给线性表中每个元素一个序号【皮皮解析】：C443.有一个栈，元素 ABCDE 依次进栈，这 5 个元素，出栈顺序为 CBAED，则栈容量至少为？（）。A.2B.3C.5D.4【皮皮解析】：B4.一个进行产生数据供另外一个进程处理，两个进程间的速度可能不同步，使用下列哪个数据结构可以有助于解决两个进程间的同步问题？（）。A.栈B.队列C.树D.图【皮皮解析】：B 先进先出5.一个长度为 8 的串的子串有（）个。A.8B.9C.37D.256【皮皮解析】：B长度为 8 的子串有 1 个，长度为 7 的子串有 2 个，长度为 6 的子串有 3 个，长度为 5的子 串有 4 个，长度为 1 的子串有 8 个，空串 1 个，共有(1+8)*8/2+1=37 个。6.一个树含有 30 个节点，则它的最大高度为（）。A.5B.4C.6D.30【皮皮解析】：D，一条线7.某二叉树有两个节点 p 与 q，对该树进行中序遍历时，p 在 q 的前面，则（）。A.p 是 q 的祖先B.q 是 p 的祖先C.p 在 q 左边D.q 在 p 左边【皮皮解析】：CPB、D 排除qqA 排除/P458.有 n 个顶点的无向连通图最少有（）条边。A.n+1B.nC.n-1D.n（n-1）/2【皮皮解析】：C9.下列关于查找的说法，错误的是（）。A.对含有 n(n0）个元素的哈希表进行查找，最坏情况下的查找代价为 O（n）B.对于所有数据结构上的所有查找算法，最好的查找代价为 O（1）C.在数组上进行查找，数组中元素必须有序D.在单链表上进行查找的最好情况下的代价为 O（1）【皮皮解析】：C 折半查找的要求10.为了更好的实现快速排序算法，待排序元素宜采用下列哪个结构存储？（）。A.单链表B.数组C.双链表D.循环链表【皮皮解析】：B三.简答题（40 分）1.求 T(n)=2T(n/4)+n的非递归解并证明（10 分）【皮皮解析】：A=2，b=4f(n)=n=n(log4(2)=n(1/2),e=3/2 符合 case3T(n)=O(f(n)=n【不建议直接写主定理，使用递归解法确保 10 分】递归解法T(n)=2T(n/4)+nT(n/4)=2T(n/8)+(n/4)T(n)=2(2T(n/8)+(n/4)+n=4 T(n/8)+2(n/4)+n=n【逐渐减小】462.证明 n 个节点的无向连通图最少有 n-1 条边（7 分）【皮皮解析】：设 G 中结点为 v1、v2、vn。由连通性，必存在与 v1 相邻的结点，不妨设它为 v2（否则可重新编号），连接 v1 和v2，得边 e1，还是由连通性，在 v3、v4、vn 中必存在与 v1 或 v2 相邻的结点，不妨 设为 v3，将其连接得边 e2，续行此法，vn 必与 v1、v2、vn-1 中的某个结点相邻，得 新边 en-1，由此可见 G 中至少有 n-1 条边。【数学归纳法】、【反证法】均可3 求时间复杂度（7 分）void pipi（int n）int p=1，r=n；while（r0）p=p*2;r=r/2;【皮皮解析】：logn4.前序遍历和后序遍历能否确定一个二叉树，中序遍历与先序遍历能否确定一颗二叉树，并分别解释原因（6 分）【皮皮解析】：前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。475 如何用优先队列实现先进先出队列？实现后的出队与入队操作的时间复杂度是多少？（10 分）【皮皮解析】：何为优先队列呢？全书中的名词解释中有提到基本操作有：empty()/判断一个队列是否为空pop()/删除队顶元素top()/返回优先队列的队顶元素push()/加入一个元素size()/返回优先队列中拥有的元素个数优先队列类似队列，但是在这个数据结构中的元素按照一定顺序排列【谁最大先输出谁】或者【谁最小先输出谁】题目中要求【谁先进入就先输出谁】只需把数据中添加一个时间属性 按这个时间属性进行输出即可struct nodeint time;/以入队的时间的先后进行输出int x；/存储数据a；入队 n，time 初试为 1a.time+;a.x=n;priority_queue.push(a);出队priority_queue.pop重载优先级队列friend bool operator n2.time;/自定义优先级以时间为输出48四.代码题（50 分）1.C 语言算法实现二叉树中求最小值，并分析时间复杂度。【皮皮解析】：时间复杂度 O（n）void Find(BiTree T)if(T=NULL)return;elseif(T-datadata;Find(T-lchild);Find(T-rchild);2.C 语言算法实现邻接链表转化成邻接矩阵，并分析时间复杂度。【皮皮解析】：领接链表进行遍历 g.edgesip-adjvex=1;即可void ListToMat(ALGraph*G,MGraph&g)int i;/将邻接表 G 转换成邻接矩阵 gArcNode*p;for(i=0;in;i+)p=G-adjlisti.firstarc;while(p!=NULL)g.edgesip-adjvex=1;p=p-nextarc;g.n=G-n;g.e=G-e;3.大小为 n 的数组中双端队列 C 语言算法实现相关操作，出入队时间复杂度O(1)。【皮皮解析】：分别在数组的末尾定义 1 个队头队尾即可492018 年华中科技大学数据结构与算法分析一名词解释（25 分）1.1 递归函数1.2 空间复杂度1.3 满二叉树1.4 装填因子1.5 再哈希法二选择题（25 分）2.1 ABCD 入栈，不可能的出栈顺序是（）。A.ABCDB.BACDC.DCABD.DCBA2.2 下列函数，fun（5）的结果是（）。int fun（int n）if（n1）return 0；printf(%d,n)；return（1+fun（2*n/3）+fun（n/3）；A.96421116B.9642112123211C.5321116D.543212.3 堆排序的时间复杂度（）。A.log（n）B.n*log（n）C.nD.n22.4 一棵树的中序 DJGBEHAFIC，先序 ABDGJEHCFI,则后序是（）。A.JGBHEBIFCAB.GBDEFIHCAC.JGDEHBIFCAD.都不对2.5 基数排序的时间复杂度和（）无关。A.基数的选择B.数组的最大元素C.数组长度D.数组是否排序三简答题（60 分）3.1 有 3 扇关闭着的门，其中 2 扇门后面各有一只羊，另一扇门后面有一辆车。参与者：一个游戏者和一个主持人。主持人事先知道各扇门后的物品，而游戏者不知道。游戏目的：游戏者选择到车。游戏过程：1、游戏者随机选定一扇门；2、在不打开此扇门的情况下，主持人打开另一扇有羊的门。3、此时面对剩下 2 扇门，游戏者有一次更改上次选择的机会。问：（画出判定树）游戏者是否应该改变上次的选择，以使选到车的概率较大？3.2(1、8、2、3、4、5、6、7)利用数组建成一个小根堆并使用堆排序将其排序成唯一的降序数组。要求画出所有中间过程。503.3 12 个权值为 3、4、6、8、12、15、18、22、25、33、36、58画出哈夫曼树并设计编码。3.4 15，25，36，47，58，69表长 11。H（k）=k%11用二次探测再散列处理冲突，画出散列表。3.5 用算法设计的思想，不全部计算出来求 3 的 96 次方的第十位数值。四算法设计（40 分）（请使用类 C 语言编写）4.1 求二叉树的结点个数，如果根节点为空，则返回 0。4.2 打印出非递减数组 a 与 b 的升序并集（去除重复元素）。512018 年华中科技大学 887 数据结构与算法分析真题手打（解析）1名词解释（25 分）1.1 递归函数解析：对于某一函数 f（x），其定义域是集合 A，若对于 A 集合中的某一个值 X0，其函数 值 f（x0）由 f（f（x0）决定，那么就称 f（x）为递归函数。1.2 空间复杂度解析：空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做 S(n)=O(f(n)。1.3 满二叉树解析：也称丰满二叉树，一棵深度为 h 且有 2h-1 个结点的二叉树。1.4 装填因子解析：填入表中的元素个数/散列表的长度。1.5 再哈希法解析：（蛤六）这种方法是同时构造多个不同的哈希函数：Hi=RH1（key）i=1，2，k当哈希地址 Hi=RH1（key）发生冲突时，再计算 Hi=RH2（key），直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。2选择题（25 分）2.1 ABCD 入栈，不可能的出栈顺序是（C）。A.ABCDB.BACDC.DCABD.DCBA2.2 下列函数，fun（5）的结果是（C）。(卷子上的错题，选什么都对)int fun（int n）if（n1;544算法设计（40 分）（请使用类 C 语言编写）4.1 求二叉树的结点个数，如果根节点为空，则返回 0。typedef struct Bintreenodeint data；struct Bintreenode*right；struct Bintreenode*left；*Bintreenode；解析：第一步：写明算法的整体思想/*算法思想：使用后序递归算法遍历该树，如果有结点，则计数（count）+，如果根结点为空，则返回 0。*/第二步：编写程序int count=0；/count 记录拥有两个子女节点的节点个数int Count_Node(Bintreenode*root)/输入：根节点if(!root)/非空时Count_Node(root-left);Count_Node(root-right);/计数（count）+，count+;/ifreturn count;/Count_Node第三步：进行时间复杂度的分析 遍历整棵树。时间复杂度为 O（n）。4.2 略552019 年暨南大学数据结构2019 年全国硕士研究生统一入学考试自命题试题（A 卷）*招生专业与代码：计算机科学与技术、软件工程、网络空间安全、工程硕士研究方向：计算机系统结构 081201，计算机软件与理论 081202，计算机应用技术 081203，软件工程 083500，计算机技术(专业学位)085211，网络空间安全 083900考试科目名称及代码：数据结构 830考试科目：数据结构共 5 页，第 1页56考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、单项选择题(每题 2 分，共 30 分)1.在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系()。A不一定相同B互为逆序C都不相同D都相同2.深度为 4 的二叉树至多有结点数为（）。A.18B.14C.15D.163.在一个具有 n 个顶点的有向图中，若所有顶点的入度数之和为 m，则所有顶点的度数之和为（）。AmBm-1Cm+1D2m4.快速排序在()情况下最不利于发挥其长处。A.被排序的数据量太大.B.被排序数据中含有多个相同的关键字C.被排序的数据完全无序D.被排序的数据已基本有序5.一组记录的关键字为（45,80,55,40,42,85）,则利用堆排序的方法建立的初始堆为（）。A.（80,45,55,40,42,85)B.(85,80,55,40,42,45)C.(85,80,55,45,42,40)D.(85,55,80,42,45,40)6.对有 18 个元素的有序表（下标为 118）作折半查找,则查找 A3的比较序列的下标为()。A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,37.具有 n 个顶点的完全有向图的边数为()。A.n(n-1)/2B.n(n-1)C.n2D.n2-18.利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素35 要进行（）。A.4 次B.5 次C.3 次D.2 次9.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。A求最短路径的 Floyd 方法B求最短路径的 Dijkstra 方法C广度优先遍历算法D深度优先遍历算法10.对于一个具有 n 个顶点的无向连通图，它包含的连通分量的个数为（）。A0B1CnDn+111.在一个单链表中,若 p 所指的结点不是最后一个结点,在 p 之后插入 s 所指的结点,则执行()。A.s-next=p;p-next=sB.p-next=s;s-next=pC.p=s;s-next=p-nextD.s-next=p-next;p-next=s12.设 F 是由 T1、T2 和 T3 三棵树组成的森林，与 F 对应的二叉树为 B，T1、T2 和 T3 的结点数分别为 N1、N2和 N3，则二叉树 B 的根结点的左子树的结点数为（）。A.N1-1B.N2-1C.N2+N3D.N1+N313.设输入元素 1,2,3,P,A，输入次序为：123PA，元素经过栈后到达输出序列。当所有元素均达到输出序列，下面（）序列可以作为高级语言的变量名。A.123PAB.PA321C.12AP3D.PA12314.在一个链队列 Q 中，删除一个结点需要执行的指令是（）。A.Q.rear=Q.front-next;B.Q.rear-next=Q.rear-next-next;C.Q.front-next=Q.front-next-next;D.Q.front=Q.rear-next;15.如果 T2 是由树 T 转换而来的二叉树,那 T 中结点的后序就是 T2 中结点的()。A.先序B.中序C.后序D.层次序二填空题(每空 2 分，共 20 分)1.设根结点在第一层，那么具有 n 个结点的完全二叉树，其高度为。2.对于一个循环队列 Q0.m-1，队头、队尾指针分别为 f、r，其判空的条件是，判满的条件是。3.在堆排序，希尔排序，快速排序，归并排序算法中，占用辅助空间最多的是。4.已知二维数组 Amn采用行序为主序存储，每个元素占 k 个存储单元，并且第一个元素的存储地址是 Loc(A00),则 Aij的地址是。5.若某记录序列的关键字序列是（235，346，021，558，256），用链式基数排序方法排序，第一次收集的结果是。6.设 Hash 表为 m=11，散列函数 H(k)=k%11，表中已有 4个 结 点，地 址分 别 为：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7，其余地址为空。如果用二次探测再散列处理冲突，关键字为 49 的结点的地址是。7.在一个 3 阶的 B-树上，每个结点包含的子树相同，最多为个结点，最少为个结点。8.一个连通图的是一个极小连通子图。三判断题（每题 1 分，共 10 分，正确的选 t，错误的选 f）1.对于 n 个记录的集合进行冒泡排序，在最坏情况下的时间复杂度是 O(n2)。()2.包含两个结点的所有二叉树都是相同的。（）3.一个图按广度优先遍历的结果是唯一的。()4.用 Prime 算法和 Kruskal 算法求得的图的最小生成树一定相同。（）5.线性表中的每一个元素都有一个前驱和后继元素。()6.在 n 个顶点的无向图中，若边数n-1，则该图必是连通图。（)7.完全二叉树的某结点若无左孩子，则必是叶子结点。（)8.在 B-树,有 n 棵子树的结点中有 n 个关键字。（）9.在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。（)10.用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。（）考试科目：数据结构共 5 页，第 2页57四.简答题（40 分）1.设 G 为有 n 个顶点的无向连通图，证明 G 至少有 n-1 条边。（7 分）2.什么是线索二叉树？一棵二叉树的中序遍历序列为 djbaechif，前序遍历序列为 abdjcefhi,请画出该二叉树的后序线索二叉树。（7 分）3.已知某通讯电文仅有 A、B、C、D、E、F 六个字符构成，其出现频率分别为 23,5,14,8,25,7,请给出他们的 Huffman 编码以及求解过程。(7 分）4、给定一棵二叉链表存储的二叉树，试用文字描述判定一棵二叉树是否是完全二叉树的算法基本思想。（7 分）5.已知一棵完全二叉树共有 67 个结点，试求:（7 分）(1)树的深度；(2)度为 1 的结点数；(3)叶子结点数；6.对给定的一组关键字序列（29,18,25,47,58,12,51,10）,写出用归并排序方法进行排序的变化过程。（5 分）五算法填空（共 2 小题，每空 2 分，共 20 分）1.若二叉排序树 T 中存在其关键字等于 key 的数据元素时，则下面算法删除该数据元素结点，并返回 TRUE；否则返回 FALSE。请在_处填上适当内容，使其成为一个完整算法。typedef struct BiTNode TElemTypedata;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;Status DeleteBST(BiTree&T,KeyType key)if(!T)return FALSE;elseif(EQ(key,T-data.key)return Delete(T);else if(LT(key,T-data.key)return DeleteBST(T-lchild,key);else return DeleteBST(T-rchild,key);考试科目：数据结构共 5 页，第 3页58Status Delete(BiTree&p)BiTree q,s;if(!p-rchild)q=p;(1)free(q);else if(!p-lchild)q=p;(2)free(q);else q=p;(3);while(4)q=s;s=s-rchild;p-data=s-data;if(q!=p)q-rchild=s-lchild;else(5)free(s);return TRUE;2.下面是快速排序算法。请在_处填上适当内容，使其成为一个完整算法。#define Maxsize 100typedef intkeytype;typedef structkeytype key;Infotype otherinfo;RedType;typedef struct RedType rMaxsize+1;int length;SqList;void Qsort(SqList&L,int low,int high)if(lowhigh)pivotloc=Partition(L,low,high);(6);Qsort(L,pivo