计算机数据结构今年考研真题及答案

《计算机数据结构今年考研真题及答案》由会员分享，可在线阅读，更多相关《计算机数据结构今年考研真题及答案（23页珍藏版）》请在金锄头文库上搜索。

1、20091.为解决电脑与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区， 主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是4.以下二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层设根为第 1 层有8 个叶结点，则完全二叉树的结点个数最多是A.只有 IIB.I 和 IIC.I 和 IIID.I、II 和 III7.以下关于无向连通图特性的表达中，正确的选项是8.以下表达中，不符合 m 阶 B 树定义要求的是9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆最小堆，插入关键字 3，调整后得到的小根堆是

2、A3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.假设数据元素序列 11，12，13，7，8，9，23，4，5 是采用以下排序方法之一得到的第二趟排序后的结果，则该排序算法只能是41.10 分带权图权值非负，表示边连接的两顶点间的距离的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。 假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点；选择离 u 最近且尚未在最短

3、路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v；重复步骤，直到 u 是目标顶点时为止。请问上述方法能否求得最短路径？假设该方法可行，请证明之；否则，请举例说明。42.15 分已知一个带有表头结点的单链表，结点结构为datalink假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点k 为正整数。假设查找成功，算法输出该结点的 data 值，并返回 1；否则，只返回 0。要求：1描述算法的基本设计思想2描述算法的详细实现步骤3 根据设计思想和实现步骤， 采用程序设计语言描述算法 使用 C 或 C+或 JAVA 语

4、言实现，关键之处请给出简要注释。201020101、假设元素 a,b,c,d,e,f 依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是 A：dcebfa B：cbdaef C：dbcaef D：afedcb2、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是 A：bacde B：dbace C：dbcae D：ecbad3、以下线索二叉树中用虚线表示线索，符合后序线索树定义的是 4、 在以下所示的平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树， 在新平衡二叉树中， 关键字 37 所在结点的左、 右子结点中保存的关

5、键字分别是 A：13，48 B：24，48 C：24，53 D：24，905、在一棵度为 4 的树 T 中，假设有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶节点个数是 A：41 B：82 C：113 D：1226、对n(n 大于等于 2)个权值均不相同的字符构成哈夫曼树，关于该树的表达中，错误的选项是A：该树一定是一棵完全二叉树B：树中一定没有度为 1 的结点C：树中两个权值最小的结点一定是兄弟结点D：树中任一非叶结点的权值一定不小于下一任一结点的权值7、假设无向图 G-V.E中含 7 个顶点，则保证图 G 在任何情况

6、下都是连通的，则需要的边数最少是 A：6 B：15 C：16 D：218、对以下图进行拓补排序，可以得到不同的拓补序列的个数是 eacbdA：4 B：3 C：2 D：19、已知一个长度为 16 的顺序表 L，其元素按关键字有序排列，假设采用折半查找法查找一个不存在的元素，则比较次数最多是 A：4 B：5 C：6 D：710、采用递归方式对顺序表进行快速排序，以下关于递归次数的表达中，正确的选项是 A：递归次数与初始数据的排列次序无关B：每次划分后，先处理较长的分区可以减少递归次数C：每次划分后，先处理较短的分区可以减少递归次数D：递归次数与每次划分后得到的分区处理顺序无关11、对一组数据2，1

7、2，16，88，5，10进行排序，假设前三趟排序结果如下 第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88则采用的排序方法可能是：A：起泡排序 B：希尔排序 C：归并排序 D：基数排序问题：1请画出所构造的散列表；2分别计算等概率情况下， 查找成功和查找不成功的平均查找长度。42.13 分设将 n(n,1)个整数存放到一维数组R 中，试设计一个在时间和空间两方面尽可能有效的算法， 将 R 中保有的序列循环左移P 0Pn 个位置，即将 R 中的数据由X0X1Xn-1变换为XpXp+1Xn-1X0X1Xp-1要求：1给出算法的基本设

8、计思想。2 根据设计思想， 采用 C 或 C+或 JAVA语言表述算法关键之处给出注释。3说明你所设计算法的时间复杂度和空间复杂度201120111.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是x = 2;while ( x n/2 )x = 2*x;A.O(log2n) B.O(n) C.O(n log2n) D.O(n2)3.已知循环队列存储在一维数组A0.n-1 中， 且队列非空时front和rear分别指向队头元素和队尾元素。假设初始时队列为空，且要求第 1 个进入队列的元素存储在 A0处，则初始时 front 和 rear 的值分别是A.0, 0 B.0, n-1 C

9、.n-1, 0 D.n-1, n-14.假设一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是5.假设一棵二叉树的前序遍历序列和后序遍历序列分别为 1, 2, 3, 4和 4,3, 2, 1，则该二叉树的中序遍历序列不会是A.1, 2, 3, 4 B.2, 3, 4, 1 C.3, 2, 4, 1 D.4, 3, 2, 16.已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是7.对于以下关键字序列， 不可能构成某二叉排序树中一条查找路径的序列是A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 3

10、5C.21, 89, 77, 29, 36, 38 D.12, 25, 71, 68, 33, 348.以下关于图的表达中，正确的选项是I. 回路是简单路径II. 存储稀疏图，用邻接矩阵比邻接表更省空间III.假设有向图中存在拓扑序列，则该图不存在回路A.仅 II B.仅 I、II C.仅 III D.仅 I、III9.为提高散列(Hash)表的查找效率，可以采取的正确措施是I. 增大装填(载)因子II. 设计冲突(碰撞)少的散列函数III.处理冲突(碰撞)时防止产生聚集(堆积)现象A.仅 I B.仅 II C.仅 I、II D.仅 II、III10.为实现快速排序算法，待排序序列宜采用的存储

11、方式是11.已知序列 25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是41.(8 分)已知有 6 个顶点(顶点编号为 0 5)的有向带权图 G，其邻接矩阵A 为上三角矩阵，按行为主序 (行优 先)保存在如下的一维数组中。要求：(1)写出图 G 的邻接矩阵 A。(2)画出有向带权图 G。(3)求图 G 的关键路径，并计算该关键路径的长度。42.(15 分)一个长度为 L(L1)的升序序列 S，处在第L/2个位置的数称为S 的中位数。例如，假设序列 S1=(11, 13, 15, 17, 19)，则 S1 的中位数是 1

12、5。两个序列的中位数是含它们所有元素的升序序列的中位数。 例如， 假设 S2=(2, 4,6, 8, 20)，则 S1 和 S2 的中位数是 11。现有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求:(1)给出算法的基本设计思想。(2)根据设计思想， 采用 C 或 C+或 JAVA 语言描述算法， 关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。20121、求整数 n(n0)阶乘的算法如下，其时间复杂度是()intfact(intn)if(n=1)return1;returnn*fact(n-1);A.O

13、(log2n)B.O(n)C.(nlog2n)D.O(n2)2、已知操作符包括+、-、*、/、(和)。将中缀表达式 a+b-a*(c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+时， 用栈来存放暂时还不能确定运算次序的操作符，假设栈初始时为空，则转换过程中同时保存栈中的操作符的最大个数是()3、假设一颗二叉树的前序遍历序列为 a,e,b,d,c，后续遍历序列为 b,c,d,e,a，则根节点的孩子节点()4、假设平衡二叉树的高度为 6，且所有非叶节点的平衡因子均为 1，则该平衡二叉树的节点总数为()5、对有 n 个节点、e 条边且使用邻接表存储的有向图进行广度优先遍

14、历，其算法时间复杂度()A.O(n)B.O(e)C.O(n+e)D.O(n*e)6、假设用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结构是()A.存在，且唯一B.存在，且不唯一7、如下有向带权图，假设采用迪杰斯特拉Dijkstra算法求源点 a 到其他各顶点的最短路径，得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是()A.d,e,fB.e,d,fC.f,d,eD.f,e,d8、以下关于最小生成树的说法中，正确的选项是()、最小生成树的代价唯一、所有权值最小的边一定会出现在所有的最小生成树中、使用普里姆P

15、rim算法从不同顶点开始得到的最小生成树一定相同、使用普里姆算法和克鲁斯卡尔Kruskal算法得到的最小生成树总不相同、9、已知一棵 3 阶 B-树，如以下图所示。删除关键字 78 得到一棵新 B-树，其最右叶结点中的关键字是()B.60,62C.62,6510、 在内部排序过程中， 对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。 以下排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是().简单项选择择排序.希尔排序.快速排序.堆排序.二路归并排序、11对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是()二、问答题。二、问答题。41、10 分设有

16、 6 个有序表 A、B、C、D、E、F，分别含有10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数到达最小。请答复以下问题。1给出完整的合并过程，并求出最坏情况下比较的总次数。2根据你的合并过程，描述 N(N2)个不等长升序表的合并策略，并说明理由。42、13 分假定采用带头结点的单链表保存单词，当两个单词有相同的后时缀，则可共享相同的后缀存储空间，例如，“loaging”和“being”，如以下图所示。设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构

17、为data,next，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置如图中字符 i 所在结点的位置 p。要求：1给出算法的基本设计思想。2 根据设计思想， 采用 C 或 C+或 java 语言描述算法关键之处给出注释。3说明你所设计算法的时复杂度。201320131. 已知两个长度分别为 m 和 n 的升序链表， 假设将它们合并为一个长度为m+n 的降序链表，则最坏情况下的时间复杂度是A. O(n)B. O(m*n)C. O(min(m,n)D. O(max(m,n)2. 一个栈的入栈序列为1, 2,3, ,n ， 其出栈序列是 p1, p2

18、, p3, pn。 假设p2 = 3，则 p3 可能取值的个数是:A. n-3B. n- 2C. n-1D. 无法确定3. 假设将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树T 中，则 T 中平衡因子为 0 的分支结点的个数是A. 0B. 1C. 2D. 34. 已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权外部路径长度最小是A. 27B. 46C. 54D. 565. 假设 X 是后序线索二叉树中的叶结点， 且 X 存在左兄弟结点 Y， 则 X 的右线索指向的是A. X 的父结点B. 以 Y 为根的子树的最左下结点C. X 的左兄弟结点

19、YD. 以 Y 为根的子树的最右下结点6. 在任意一棵非空二叉排序树 T1 中，删除某结点 v 之后形成二叉排序树T2，再将 v 插入 T2 形成二叉排序树 T3。以下关于 T1 与 T3 的表达中，正确的选项是I. 假设 v 是 T1 的叶结点，则 T1 与 T3 不同II. 假设 v 是 T1 的叶结点，则 T1 与 T3 相同III. 假设 v 不是 T1 的叶结点，则 T1 与 T3 不同IV. 假设 v 不是 T1 的叶结点，则 T1 与 T3 相同A. 仅 I、IIIB. 仅 I、IVC. 仅 II、IIID. 仅 II、IV7. 设图的邻接矩阵 A 如下所示。各顶点的度依次是A.

20、 1，2，1，2B. 2，2，1，1C. 3，4，2，3D. 4，4，2，28. 假设对如下无向图进行遍历，则以下选项中，不是广度优先遍历序列的是A. h，c，a，b，d，e，g，f B. e，a，f，g，b，h，c，dC. d，b，c，a，h，e，f，g D. a，b，c，d，h，e，f，g9、 以下的 AOE 网表示一项包含 8 个活动的工程。 通过同时加快假设干活动的进度可以缩短整个工程的工期。以下选项中， 加快其进度就可以缩短整个工程的工期的是：A c和 eB d 和 eC f 和 dDf 和 h10、在一棵高为 2 的 5 阶 B 树中，所含关键字的个数最少是A 5B 7C 8D14

21、A= ( 0 ，5，5，3，5，7，5，5 )，侧 5 为主元素；又如 A= ( 0 ，5，5，3，5，1，5，7 )， 则A中没有主元素。假设 A中的 n 个元素保存在一个一维数组中，请计一个尽可能高效的算法，找出A的主元素。假设存在主元素，则输出该元素；否则输出-1。要求：1给出算法的基本设计思想。2根据设计思想，采用C 或 C+或 Java 语言描述算法，关键之处给出释。3说明你所设计算法的时间复杂度和空间复杂度。42.10分 设 包 含4 个数据元 素的集 合S= do，for ， repeat ， while，各元素查找概率依次为： ，p3=0. 15 ，。 将S 保存在一个长度为

22、4 的顺序表中， 采用折半查找法，查找成功时的平均查找长度为。请答复：1假设采用顺序存储结构保存 S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？2假设采用链式存储结构保存 S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？20141. 以下程常段的时间复杂度是count=0;for(k=1;k=n;k*=2)for(j=1;j=n;j+1)count+;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)2. 假设栈初始为空， 将中缀表达式a bcdef后缀表达式的过程中，当扫描

23、到 f 时，栈中的元素依次是A B. C.g转换为等价 D. 3. 循环两列放在一维数组 A0M-1中，end1 指向队头元素，end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1 个元素。初始时为空，以下判断队空和队满的条件中，正确的选项是A.队空：end1=end2；队满：end1=(end2+1)modMB.队空：end1=end2;队满：end2=(end1+1)mod(M-1)C.队空：end2=(end1+1)modM ;队满：end1=end2+1modMD.队空：end1=end2+1modM;队满：end2=(end1+1)mod(

24、M-1)4. 假设对如下的二叉树进行中序线索化，则结点 x 的左、右线索指向的结点分别是A.e,cB.e,aC.d,cD.b,aabcdx5. 将森林 F 转换为对应的二叉树 T，F 中叶结点的个数等于A.T 中叶结点的个数B.T 中度为 1 的结点个数6. 5 个字符有如下 4 种编码方案，不是前缀编码的是A.01,0000,0001,001,1B.011,000,001,010,1C.000,001,010,011,100D.000,001,010,011,1007. 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是A.3,1,2,4,5,6B.3,1,2,4,6,5C.3,1,4,2

25、,5,6D.3,1,4,2,6,514362e58. 用哈希散列方法处理冲突碰撞时可能出现堆积聚集现象，以下选项中，会受堆积现象直接影响的是A.存储效率B.数列函数9.在一棵具有 15 个关键字的 4 阶 B 树中，含关键字的结点数最多是10. 用希尔排序方法对一个数据序列进行排序时，假设第 1 趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量间隔可能是11. 以下选项中，不可能是快速排序第 2 趟排序结果的是A.2,3,5,4,6,7,9B.2,7,5,6,4,3,9C.3,2,5,4,7,6,9D.4,2,3,5,7,6,941.13 分二叉树的带权路径长度WP

26、L是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树 T，采用二叉链表存储，节点结构为：其中叶节点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根节点的指针，设计求 T 的 WPL 的算法。要求：1给出算法的基本设计思想；2使用 C 或 C+语言，给出二叉树结点的数据类型定义；3根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。leftweightright20151已知程序如下：int s(int n) return (n=0) ? 0 : s(n-1) +n; void main() coutS(1)-S(0) BS(0)-S(1)-main()C

27、main()-S(0)-S(1) D S(1)-S(0)-main()2先序序列为 a,b,c,d的不同二叉树的个数是A13B14 C 15 D 163 以下选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A24，10，5 和 24，10，7 B 24 ，10 ，5 和 24 ，12 ，7C24 ，10 ，10和 24，14，11 D 24，10，5 和 24，14，64现在有一颗无重复关键字的平衡二叉树AVL 树,对其进行中序遍历可得到一个降序序列。以下关于该平衡二叉树的表达中，正确的选项是A根节点的度一定为 2 B树中最小元素一定是叶节点C最后插入的元素一定是叶

28、节点 D树中最大元素一定是无左子树5 设有向图G=(V,E) ， 顶 点 集V=V0,V1,V2,V3 ， 边集 E=,，,假设从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A2 B3 C 4 D 56求下面带权图的最小 代价 生成树时，可能是克鲁斯卡 kruskal算法第二次选中但不是普里姆 Prim算法从V4 开始第2 次选中的边是 A(V1,V3) B (V1,V4)C(V2,V3) D (V3,V4)7以下选项中，不能构成折半查找中关键字比较序列的是A500，200，450，180 B 500，450，200，180C180，500，200，450D180，200，

29、500，4508已知字符串 S 为“abaabaabacacaabaabcc”. 模式串t 为“abaabc”,采用 KMP算法进行匹配， 第一次出现 “失配”(si != ti)时，i=j=5,则下次开始匹配时，i 和 j 的值分别是Ai=1 ，j=0 B i=5，j=0 C i=5，j=2 D i=6 ，j=29以下排序算法中元素的移动次数和关键字的初始排列次序无关的是A直接插入排序 B起泡排序C基数排序 D快速排序10已知小根堆为8，15，10，21，34，16，12，删除关键字8 之后需重建堆，在此过程中，关键字之间的比较数是A1 B2 C 3 D 411希尔排序的组内排序采用的是A直

30、接插入排序 B折半插入排序 C 快速排序 D归并排序41. 用单链表保存 m 个整数， 节点的结构为 (data,link) ，且|data|=2)个顶点的邻接矩阵为 B 则，Bm(2=mlink; /*p 和 q 指向链表表头结点的下一个结点*/while(p!=NULL)if(countlink;/*q 移到下一个结点*/p=p-link; /*p 移到下一个结点*/if(countdata); /*查找成功*/return (1);/else/SearchN201020101-5：DCDCB 6-11：ACBBDA41.1构造的散列表如下下标0123456789关键字7148113018

31、92查找成功的平均查找长度:ASL 成功=12/7。查找不成功的平均查找长度:ASL 不成功=18/7。42. 1 给出算法的基本设计思想： 先将 n 个数据 x0x1xpxn-1 原地逆置，得到 xn-1xpxp-1x0,然后再将前 n-p 个和后 p 个元素分别原地逆置， 得到最终结果:xpxp+1xn-1x0x1xp-1。2算法实现：void reverse(int r,int left,int right)int k=left,j=right,temp; /k 等于左边界 left,j 等于右边界 rightwhile(k0&pn)reverse(r,0,n-1);/将全部数据逆置re

32、verse(r,0,n-p-1);/将前 n-p 个元素逆置reverse(r,n-p,n-1);/将后 p 个元素逆置3说明算法复杂性：上述算法的时间复杂度为 O(n),空间复杂度为 O(1)。201120111-5：ABBCC6-10：DACBA41.高分笔记图最后一题42.(1)算法的基本设计思想：(5 分)1) 比较笨的方法：将两升序序列归并排序，然后求其中位数，时间复杂度是 O(n)，空间复杂度 O(n)。2) 高效的方法：分别求两个升序序列 A 和 B 的中位数，设为 a 和 b。如果 a=b，则 a 或者 b 即为所求的中位数。原因：如果将两序列归并排序，则最终序列中，排在子序列

33、 ab 前边的元素为先前两序列中排在 a 和 b 前边的元素;排在子序列 ab 后边的元素为先前两序列a 和 b 后边的元素。所以子序列ab 一定位于最终序列的中间，有因为a=b，显然a 就是中位数。如果 ab(假设 a原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如a ab b的序列出现，中位数必然出现在的序列出现，中位数必然出现在(a(a，b)b)范围内。因此可以做如下处理：舍范围内。因此可以做如下处理：舍弃弃 a a 所在序列所在序列 A A 之中比较小的一半，之中比较小的一半， 同时舍弃同时舍弃 b b 所在序

34、列所在序列 B B 之中比较大的一半。之中比较大的一半。在保留的两个升序序列中求出新的中位数在保留的两个升序序列中求出新的中位数 a a 和和 b b，重复上述过程，重复上述过程，直到两个序列直到两个序列只含一个元素为止，则较小者即为所求中位数。只含一个元素为止，则较小者即为所求中位数。(2)算法实现(高效方法)：(8 分)int Search(int A, int B, int n)int s1,e1,mid1,s2,e2,mid2;s1=0;e1=n-1;s2=1;e2=n-1;while(s1!=e1|s2!=e2)mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(Ami

35、d1=Bmid2)return Amid1;if(Amid1len2) longList=L1-next; shortlist=L2-next; L=len1-len2;/ 表长之差 /if else longList=L2-next; shortlist=L1-next; L=len2-len1;/ 表长之差 /else While(L-) longList=longList-next; while(longList!=NULL) if(longList=shortList)/ 同步寻找共同结点 return longList; else longList=longList-next; sh

36、ortlist=shortlist-next; /else /while return NULL;/Search_First_Common3算法的时间复杂度为 O(len1+len2)，空间复杂度为O(1)。201320131-5：DCDBA 6-10：CCDCA41.1给出算法的基本设计思想：4 分算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然 后 重新计数， 确认Num是否是主元素。 算法可分为以下两步：选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数 Num保 存 到 c中记录 Num的出现次数为1； 假 设 遇到的 下 一 个整数仍等于Nu

37、m则计数加一，否则计数减一；当计数减到 0 时，将遇到的下一个整数保存到c中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，假设大于 n/2，则为主元素；否则，序列中不存在主元素。2算法实现： 7 分 int Majority ( int A , int n )int i, c, count=1; / / c 用来 保存 候选主 元素 ，count 用来计数 c = A0; / /设置 A0为候选主元素for ( i=1; i 0) count-;/ /处理不是候选主元素的情况el

38、se / /更换候选主元素，重新计数 c = Ai;count = 1;/else/forif ( count0 )for ( i=count=0; i n/2 ) return c; / / 确认候选主元素else return -1; / / 不存在主元素/Majority42.1采用顺序存储结构，数据元素按其查找概率降序排列。2 分 采 用 顺序 查 找 方 法 。1 分 查 找 成 功 时 的 平 均 查 找 长 度 = 。2分2 【答案一】 采用链式存储结构，数据元素按其查找概率降序排列，构成单链表。2 分采用顺序查找方法。1 分 查找成功时的平均查找长度。2 分 【答案二】 采用二

39、叉链表存储结构，构造二叉排序树，元素存储方式见以下图。2 分201420141-5：CBADC 6-11：DDDDBC41 解答：考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。1算法的基本设计思想：基于先序递归遍历的算法思想是用一个 static变量记录 wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下：假设该结点是叶子结点，那么变量 wpl 加上该结点的深度与权值之积；假设该结点非叶子结点，那么假设左子树不为空，对左子树调用递归算法，假设右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加

40、一；最后返回计算出的 wpl即可。基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶子结点时，累计 wpl；当遍历到非叶子结点时对该结点的把该结点的子树加入队列；当某结点为该层的最后一个结点时，层数自增1；队列空时遍历结束，返回wpl2)二叉树结点的数据类型定义如下：typedef struct BiTNodeint weight;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;3)算法代码如下：基于先序遍历的算法：intWPL(BiTreeroot)returnwpl_PreOrder(root,0);/intintwpl

41、_PreOrder(BiTreeroot,intdeep)static int wpl=0;/定义一个 static变量存储 wplif(root-lchild=NULL&root-lchild=NULL)/ 假设为叶子结点， 累积 wpl wpl+=deep*root-weight;if(root-lchild!=NULL)/ 假设左子树不空，对左子树递归遍历wpl_PreOrder(root-lchild,deep+1);if(root-rchild!=NULL)/假设右子树不空，对右子树递归遍历wpl_PreOrder(root-rchild,deep+1);return wpl;/wp

42、l_PreOrder基于层次遍历的算法：#defineMaxSize100/设置队列的最大容量int wpl_LevelOrder(BiTree root)BiTree qMaxSize;/声明队列，end1为头指针，end2 为尾指针int end1, end2;/队列最多容纳 MaxSize-1 个元素end1=end2=0;/头指针指向队头元素，尾指针指向队尾的后一个元素int wpl=0, deep=0;/初始化 wpl和深度BiTree lastNode;/lastNode 用来记录当前层的最后一个结点BiTree newlastNode; /newlastNode 用来记录下一层的

43、最后一个结点lastNode=root;/lastNode 初始化为根节点newlastNode=NULL;/newlastNode 初始化为空qend2+=root; /根节点入队while(end1!=end2)/层次遍历，假设队列不空则循环BiTree t=qend1+; / 拿出队列中的头一个元素if(t-lchild=NULL&t-lchild=NULL) wpl+ =deep*t-weight;/假设为叶子结点，统计 wplif(t-lchild!=NULL) /假设非叶子结点把左结点入队qend2+=t-lchild;newlastNode=t-lchild;/并设下一层的最后一

44、个结点为该结点的左结点if(t-rchild!=NULL)/处理叶节点qend2+=t-rchild;newlastNode=t-rchild;/ifif(t=lastNode)/假设该结点为本层最后一个结点，更新 lastNodelastNode=newlastNode;deep+=1;/层数加 1/if/whilereturn wpl; /返回 wpl/wpl_LevelOrder注意：上述两个算法一个为递归的先序遍历，上述两个算法一个为递归的先序遍历，一个为非递归的层次遍历，读一个为非递归的层次遍历，读者应当选取自己最擅长的书写方式。者应当选取自己最擅长的书写方式。直 观 看 去 ， 先

45、 序 遍历代码行数少 ， 不 用 运 用 其 他 工具 ， 书 写 也 更 容 易，希望读者能掌握。在先序遍历的算法中，static是一个静态变量，只在首次调用函数时声明 wpl 并赋值为 0，以后的递归调用并不会使得wpl 为0，具体用法请参考相关资料中的 static关键字说明，也可以在函数之外预先设置一个全局变量，并初始化。 不过考虑到历年真题算法答案通常都直接仅仅由一个函数构成，所以参考答案使用static 。假设对 static 不熟悉的同学可以使用以下形式的递归：int wpl_PreOrder(BiTree root,intdeep)int lwpl, rwpl;/用于存储左子树

46、和右子树的产生的 wpllwpl=rwpl=0;if(root-lchild=NULL&root-lchild=NULL) /假设为叶子结点，计算当前叶子结点的wplreturn deep*root-weight;if(root-lchild!=NULL) /假设左子树不空，对左子树递归遍历lwpl=wpl_PreOrder(root-lchild,deep+1);if(root-rchild!=NULL) /假设右子树不空，对右子树递归遍历rwpl=wpl_PreOrder(root-rchild,deep+1);return lwpl+rwpl;/wpl_PreOrderC/C+C/C+语

47、言基础好的同学可以使用更简便的以下形式语言基础好的同学可以使用更简便的以下形式：int wpl_PreOrder(BiTree root,int deep)if(root-lchild=NULL&root-lchild=NULL) /假设为叶子结点，累积wplreturn deep*root-weight;return(root-lchild!=NULL?wpl_PreOrder(root-lchild,deep+1):0)+(root-rchild!=NULL?wpl_PreOrder(root-rchild,deep+1):0);/wpl_PreOrder这个形式只是上面方法的简化而已，本

48、质是一样的，而这个形式代码更短，在这个形式只是上面方法的简化而已，本质是一样的，而这个形式代码更短，在时间有限的时间有限的 情情 况况 下下 更更 具具 优优 势势 ， 能能 比比 写写 层层 次次 遍遍 历历 的的 考考 生生 节节 约约 很很 多多时时 间间 ， 所 以 读 者 应 当 在 保 证 代 码 正 确 的 情况下，尽量写一些较短的算法，为其他题目赢得更多的时间。但是，对于基础不扎实的考生，还是建议使用写对把握更大的方法，否则可能会得不偿失。例如在上面的代码中，考生容易忘记三元式 (x?y:z) 两端的括号，假设不加括号，则答案就会是错误的。201520151-5：DCCBD 6

49、-11：AACBBA41.(1)算法思想： 定义一个大小为 N 的数组，初始化为0.在遍历链表的同时将数组中索引值为节点的值的绝对值的元素置1.如果此元素已经为 1，说明此节点之前已经有与此节点的值的绝对值相等的节点，需将此节点删除。(2)节点的数据结构定义如下：typedef struct Node Int data;Struct Node * next;Node;(3) int an;/全局数组标志节点的绝对值的值是否出现过void DeleteABSEqualNode(Node * head) memset(a,0,n); / 初始化为0if (head = NULL) return N

50、ULL; Node * p = head;Node * r = headwhile (p != NULL) if (aabs(p-data) = 1)/如果此绝对值已经在节点值的绝对值中出现过则 删除当前节点r-next = p-next;delete p;p = r-next; /ifelse / 否则，将数组中对应的元素置1，并将指针指向下一个元素aabs(p-data) = 1; r = p;p = p-next;/else /whilereturn head; /DeleteABSEqualNode(4) 只遍历一次链表，所以时间复杂度为O(n)，因为申请大小为 n 的数组 ，所以空间复杂度为 O(n)，n 为节点绝对值的最大值。42.(1)邻接矩阵为：20 行 3 列的元素的含义是顶点 0 到顶点3 的最短距离为 2.3 Bm 中非零元素的含义是：假设此顶点位于 i 行 j 列， 如果i=j， 则表示i 顶点到自己的距离为 0；如果ij，则表示顶点 i 到达不了顶点j。