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

《计算机数据结构今年考研真命题及其答案.doc》由会员分享，可在线阅读，更多相关《计算机数据结构今年考研真命题及其答案.doc（25页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、20091.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据 缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区 中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图 2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。若每个 元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 bdcfeag，则栈 S 的容量 至少是 A1 B.2 C.3 D.4 3.给定二叉树图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍 历方式是 A

2、LRN B.NRL C.RLN D.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则完全 二叉树的结点个数最多是 A39 B.52 C.111 D.119 6.将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点 的父结点，则在原来的森林中，u 和 v 可能具有的关系是 I父子关系 II.兄 弟关系 III.u 的父结点与 v 的父结点是兄弟关系 A.只有 II B.I 和 II C.I 和 III D.I、II 和 III 7.下列关于无向连通图特性的叙述中，正确的是 I所有顶点的度之和为偶数 I

3、I.边数大于顶点个数减 1 III.至少有一个顶 点的度为 1 A.只有 I B.只有 II C.I 和 II D.I 和 III 8.下列叙述中，不符合 m 阶 B 树定义要求的是 A根节点最多有 m 棵子树 B.所有叶结点都在同一层上 C各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接 9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插 入关键字 3，调整后得到的小根堆是 A3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28 C3，8，12，5，20，15，22，28，19 D.3，12，5，8，2

4、8，20，15，22，19 10.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法 之一得到的第二趟排序后的结果，则该排序算法只能是 A起泡排序 B.插入排序 C.选择排序 D.二路归并排序41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路 径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到 目标顶点之间存在路径，现有一种解决该问题的方法： 设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点； 选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中， 修改当前顶点 u=v； 重复步骤，直到 u 是目标顶点

5、时为止。 请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举 例说明。 42.（15 分）已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可 能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。若查找 成功，算法输出该结点的 data 值，并返回 1；否则，只返回 0。要求： （1）描述算法的基本设计思想 （2）描述算法的详细实现步骤 （3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C 或 C+或 JAVA 语言实现），关键之处请给出简要注释。20101、若元素 a,b,c,d,e,f 依

6、次进栈，允许进栈、退栈操作交替进行。但不允 许连续三次进行退栈工作，则不可能得到的出栈序列是（ ） A：dcebfa B：cbdaef C：dbcaef D：afedcb 2、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则 不可能得到的顺序是（ ） A：bacde B：dbace C：dbcae D：ecbad 3、下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）4、在下列所示的平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树， 在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是datalink（ ）A：13，48 B：24，48 C

7、：24，53 D：24，905、在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点， 1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶节点个数是（ ） A：41 B：82 C：113 D：122 6、对 n(n 大于等于 2)个权值均不相同的字符构成哈夫曼树，关于该树的 叙述中，错误的是（ ） A：该树一定是一棵完全二叉树 B：树中一定没有度为 1 的结点 C：树中两个权值最小的结点一定是兄弟结点 D：树中任一非叶结点的权值一定不小于下一任一结点的权值 7、若无向图 G-（V.E）中含 7 个顶点，则保证图 G 在任何情况下都是连通 的，则需

8、要的边数最少是（ ） A：6 B：15 C：16 D：21 8、对下图进行拓补排序，可以得到不同的拓补序列的个数是（ ）abcdeA：4 B：3 C：2 D：1 9、已知一个长度为 16 的顺序表 L，其元素按关键字有序排列，若采用折 半查找法查找一个不存在的元素，则比较次数最多是（ ） A：4 B：5 C：6 D：7 10、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中， 正确的是（ ） A：递归次数与初始数据的排列次序无关 B：每次划分后，先处理较长的分区可以减少递归次数 C：每次划分后，先处理较短的分区可以减少递归次数 D：递归次数与每次划分后得到的分区处理顺序无关 11、对

9、一组数据（2，12，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：基数排序 41.（10 分）将关键字序列（7、8、11、18、9、14）散列存储到散列列表 中，散列表的存储空间是一个下标从0 开始的一个一维数组散列函数维：H（key）=（key3）MODT，处理冲突采用线性探测再散列法，要求装填（载） 因子为 0.7 问题：（1）请画出所构造的散列表；（2）分别计算等概率情况下，查找成功

10、和查找不成功的平均查找长 度。 42.（13 分）设将 n(n,1)个整数存放到一维数组R 中，试设计一个在时间和空间两方面尽可能有效的算法，将R 中保有的序列循环左移P（0Pn）个位置，即将 R 中的数据由（X0X1Xn-1）变换为（XpXp+1Xn-1X0X1Xp-1） 要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C 或 C+或 JAVA 语言表述算法关键之处给出注 释。（3）说明你所设计算法的时间复杂度和空间复杂度20111.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是x = 2;while ( x S(1)-S(0) BS(0)-S(1)-main()

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

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

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

14、2 C3 D4 11希尔排序的组内排序采用的是（） A直接插入排序 B折半插入排序 C 快速排序 D归并排序41. 用单链表保存m 个整数，节点的结构为 (data,link)，且|data|=2)个顶点的邻 接矩阵为B 则，Bm(2link; /*p 和 q 指向链表表头结点的下一个结点*/while(p!=NULL) if(countlink;/*q 移到下一个结点*/p=p-link; /*p 移到下一个结点*/ if(countdata); /*查找成功*/return (1);/else/SearchN 2010 1-5：DCDCB 6-11：ACBBDA41.（1）构造的散列表如下

15、下标0123456789关键字71481130189（2）查找成功的平均查找长度: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

16、s1=0;e1=n-1;s2=1;e2=n-1;while(s1!=e1|s2!=e2)mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(Amid1=Bmid2) return Amid1;if(Amid1len2) longList=L1-next; shortlist=L2-next; L=len1-len2;/表长之差/ifelse longList=L2-next; shortlist=L1-next; L=len2-len1;/表长之差 /else While(L-) longList=longList-next; while(longList!=NULL) if(l

17、ongList=shortList)/同步寻找共同结点 return longList; else longList=longList-next; shortlist=shortlist-next; /else/while return NULL; /Search_First_Common （3）算法的时间复杂度为 O(len1+len2)，空间复杂度为 O(1)。2013 1-5：DCDBA 6-10：CCDCA41.（1）给出算法的基本设计思想：（4 分）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然 后 重新计数，确认Num是否是主元素。算法可分为以下两步：选

18、取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保 存 到 c 中记录 Num的出现次数为1； 若 遇 到 的 下 一 个 整 数 仍 等 于Num则计数加一，否则计数减一；当计数减到0 时，将遇到的下一个整数保存到c 中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。判断 c 中元素是否是真正的主元素：再次扫描该数组，统计c 中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。（2）算法实现：（7 分 ） int Majority ( int A , int n ) int i, c, count=1; / /

19、c 用来保存候选主元素，count 用来计数 c = A0; / / 设置 A0为候选主元素 for ( i=1; i 0) count-;/ / 处理不是候选主元素的情况else / / 更换候选主元素，重新计数c = Ai;count = 1;/else/for if ( count0 ) for ( i=count=0; i n/2 ) return c; / / 确认候选主元素 else return -1; / / 不存在主元素/Majority42.（1）采用顺序存储结构，数据元素按其查找概率降序排列。（2 分） 采用顺 序查找方法。（1 分 ） 查找成功时的平均查找长度= 0.3

20、51+0.352+0.153+0.154=2.1。（2 分） （2）【答案一 】采用链式存储结构，数据元素按其查找概率降序排列，构成单链 表。（2 分）采用顺序查找方法。 （1 分） 查找成功时的平均查找长度=0.351+0.352+0.153+0.154=2.1。（2 分） 【答案二 】采用二叉链表存储结构，构造二叉排序树，元素存储方式见下图。（2 分）2014 1-5：CBADC 6-11：DDDDBC41解答：考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶 子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。1）算法的基本设计思想：基于先序递归遍历的算法思想是用一个

21、 static 变量记录 wpl，把每个结点 的深度作为递归函数的一个参数传递，算法步骤如下：若该结点是叶子结点， 那么变量 wpl 加上该结点的深度与权值之积；若该结点非叶子结点，那么若左 子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算 法，深度参数均为本结点的深度参数加一；最后返回计算出的 wpl 即可。基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数， 当遍历到叶子结点时，累计 wpl；当遍历到非叶子结点时对该结点的把该结点 的子树加入队列；当某结点为该层的最后一个结点时，层数自增 1；队列空时 遍历结束，返回wpl2)二叉树结点的数据类型定义如下：t

22、ypedef struct BiTNodeint weight;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;3)算法代码如下：基于先序遍历的算法：intWPL(BiTreeroot)return wpl_PreOrder(root,0);/intintwpl_PreOrder(BiTreeroot,intdeep)static int wpl=0;/定义一个 static 变量存储 wplif(root-lchild=NULLif(root-lchild!=NULL)/若左子树不空，对左子树递归遍历wpl_PreOrder(root-lchil

23、d,deep+1);if(root-rchild!=NULL)/若右子树不空，对右子树递归遍历wpl_PreOrder(root-rchild,deep+1);return wpl;/wpl_PreOrder基于层次遍历的算法：#defineMaxSize100 /设置队列的最大容量int wpl_LevelOrder(BiTree root)BiTree qMaxSize; /声明队列，end1为头指针，end2 为尾指针int end1, end2; /队列最多容纳 MaxSize-1 个元素end1=end2=0; /头指针指向队头元素，尾指针指向队尾的后一个元素int wpl=0, d

24、eep=0; /初始化 wpl和深度BiTree lastNode; /lastNode 用来记录当前层的最后一个结点BiTree newlastNode; /newlastNode 用来记录下一层的最后一个结点lastNode=root; /lastNode 初始化为根节点newlastNode=NULL; /newlastNode 初始化为空qend2+=root; /根节点入队while(end1!=end2) /层次遍历，若队列不空则循环BiTree t=qend1+; /拿出队列中的头一个元素if(t-lchild=NULL /若为叶子结点，统计 wplif(t-lchild!=NU

25、LL) /若非叶子结点把左结点入队qend2+=t-lchild;newlastNode=t-lchild; /并设下一层的最后一个结点为该结点的左结点if(t-rchild!=NULL) /处理叶节点qend2+=t-rchild;newlastNode=t-rchild;/ifif(t=lastNode)/若该结点为本层最后一个结点，更新 lastNodelastNode=newlastNode;deep+=1; /层数加 1/if/whilereturn wpl; /返回 wpl/wpl_LevelOrder注意：上述两个算法一个为递归的先序遍历，一个为非递归的层次遍历，上述两个算法一个

26、为递归的先序遍历，一个为非递归的层次遍历， 读读者者应应当当选选取取自自己己最最擅擅长长的的书书写写方方式式。直观看去，先序遍 历 代 码 行 数 少，不用运用 其他工具，书写也更容易，希望读者能掌握。在先序遍历的算法中，static是一个静 态变量，只在首次调用函数时声明 wpl 并赋值为 0，以后的递归调用并不会使 得 wpl 为0，具体用法请参考相关资料中的 static 关键字说明，也可以在函数之外预先设 置一个全局变量，并初始化。不过考虑到历年真题算法答案通常都直接仅仅由 一个函数构成，所以参考答案使用static。若对 static 不熟悉的同学可以使用以下 形式的递归：int w

27、pl_PreOrder(BiTree root,intdeep)int lwpl, rwpl; /用于存储左子树和右子树的产生的 wpllwpl=rwpl=0;if(root-lchild=NULLif(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+语言基础好的同学可以使用更简便

28、的以下形式语言基础好的同学可以使用更简便的以下形式：int wpl_PreOrder(BiTree root,int deep)if(root-lchild=NULLreturn(root-lchild!=NULL?wpl_PreOrder(root-lchild,deep+1):0)+(root-rchild!=NULL?wpl_PreOrder(root-rchild,deep+1):0);/wpl_PreOrder这个形式只是上面方法的简化而已，这个形式只是上面方法的简化而已，本本质质是是一一样样的的，而这个形式代码更短，而这个形式代码更短，在在 时时间间有有限限的的情情况况下下更更具具

29、优优势势，能能比比写写层层次次遍遍历历的的考考生生节节约约很很多多时时间间， 所以读者应当在保证代码正确的情况下，尽量写一些较短的算法， 为其他题目赢得更多的时间。但是，对于基础不扎实的考生，还是建议使用 写对把握更大的方法，否则可能会得不偿失。例如在上面的代码中，考生容 易忘记三元式(x?y:z)两端的括号，若不加括号，则答案就会是错误的。2015 1-5：DCCBD 6-11：AACBBA41.(1) 算法思想： 定义一个大小为 N 的数组，初始化为 0.在遍历链表的同时将数 组中索引值为节点的值 的绝对值的元素置1.如果此元素已经为1，说明此节点之前已 经 有与此节点的值的绝对值相 等的

30、节点，需将此节点删除。(2) 节点的数据结构定义如下： typedef struct Node Int data; Struct Node * next; Node; (3) int an; / 全局数组标志节点的绝对值的值是否出现过 void DeleteABSEqualNode(Node * head) memset(a,0,n); / 初始化为0 if (head = NULL) return NULL; Node * p = head; Node * r = headwhile (p != NULL) if (aabs(p-data) = 1)/如果此绝对值已经在节点值的绝对值中出现过

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