《计算机考研数据结构统考历年真题2009-2015年》由会员分享，可在线阅读，更多相关《计算机考研数据结构统考历年真题2009-2015年（13页珍藏版）》请在金锄头文库上搜索。
1、目前刚整理了 2009-2015 的试题过几天 2016 的也会上传上去 希望对你有帮助。 。 。 。 。 。 2009 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓 冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取 出数据。该缓冲区的逻辑结构应该是 A.栈B.队列C.树D.图 2.设栈 S和队列 Q 的初始状态均为空，元素abcdefg依次进入栈 S。若每个 元素出栈后立即进入队列Q，且 7 个元素出队的顺序是bdcfeag ，则栈 S 的容量 至少是A1 B.2 C.3 D.4 3.给定二叉树图所示。设N 代表二叉树的根， L 代表根结点的左子
2、树， R 代 表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方 式是ALRN 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、I
3、I 和 III 7.下列关于无向连通图特性的叙述中，正确的是 I所有顶点的度之和为偶数II.边数大于顶点个数减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，
4、28 C3，8，12，5，20，15，22，28，19 D.3，12，5，8，28，20，15，22，19 10.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法 之一得到的第二趟排序后的结果，则该排序算法只能是 A起泡排序B.插入排序C.选择排序D.二路归并排序 41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路 径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目 标顶点之间存在路径，现有一种解决该问题的方法： 设最短路径初始时仅包含初始顶点，令当前顶点u 为初始顶点； 选择离 u 最近且尚未在最短路径中的一个顶点v，加
5、入到最短路径中，修 改当前顶点 u=v； 重复步骤，直到u 是目标顶点时为止。 请问上述方法能否求得最短路径？若该方法可行，请证明之； 否则，请举例 说明。 42.（15 分）已知一个带有表头结点的单链表，结点结构为 假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可 能高效的算法，查找链表中倒数第k 个位置上的结点（ k 为正整数）。若查找成 功，算法输出该结点的data值，并返回 1；否则，只返回 0。要求： （1）描述算法的基本设计思想 （2）描述算法的详细实现步骤 （3） 根据设计思想和实现步骤， 采用程序设计语言描述算法 （使用 C 或 C+ 或 JAVA 语言实
6、现），关键之处请给出简要注释。 2010 1、若元素 a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允 许连续三次进行退栈工作，则不可能得到的出栈序列是（） A：dcebfa B：cbdaef C ：dbcaef D ：afedcb 2、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则 不可能得到的顺序是（） A：bacde B ：dbace C ：dbcae D ：ecbad 3、下列线索二叉树中（用虚线表示线索） ，符合后序线索树定义的是（） data link 4、在下列所示的平衡二叉树中插入关键字48 后得到一棵新平衡二叉树， 在 新平衡二叉树中， 关键
7、字 37所在结点的左、 右子结点中保存的关键字分别是 （ ） A：13，48 B ：24，48 C ：24，53 D ：24，90 5、在一棵度为 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：树中任一非叶结点的权值一定不小于
8、下一任一结点的权值 7、若无向图 G-（V.E）中含 7 个顶点，则保证图G在任何情况下都是连通 的，则需要的边数最少是（） A：6 B ：15 C ：16 D ：21 8、对下图进行拓补排序，可以得到不同的拓补序列的个数是（） a b c d e A：4 B ：3 C ：2 D ：1 9、已知一个长度为 16 的顺序表 L，其元素按关键字有序排列，若采用折半 查找法查找一个不存在的元素，则比较次数最多是（） A：4 B ：5 C ：6 D ：7 10、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正 确的是（） A：递归次数与初始数据的排列次序无关 B：每次划分后，先处理较长的
9、分区可以减少递归次数 C：每次划分后，先处理较短的分区可以减少递归次数 D：递归次数与每次划分后得到的分区处理顺序无关 11、对一组数据（ 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）= （ke
10、y 3）MODT，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7 问题： （1）请画出所构造的散列表； （2）分别计算等概率情况下， 查找成功和查找不成功的平均查找长度。 42.（13 分）设将 n(n,1) 个整数存放到一维数组R 中，试设计一个在时间和 空间两方面尽可能有效的算法， 将 R中保有的序列循环左移P （0Pn） 个位置， 即将 R 中的数据由（ X0X1 Xn-1）变换为（ XpXp+1 Xn-1X0X1 Xp-1）要 求： （1）给出算法的基本设计思想。 （2）根据设计思想，采用 C或 C+ 或 JAVA语言表述算法关键之处给出注释。 （3）说明你所设计算法的时间复
11、杂度和空间复杂度 2011 1. 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是 x = 2; while ( x S(1)-S(0) BS(0)-S(1)-main() Cmain()-S(0)-S(1) DS(1)-S(0)-main() 2先序序列为a,b,c,d的不同二叉树的个数是 A13 B14 C 15 D 16 3 下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈 夫曼树的是 A24，10，5 和24，10，7 B24 ，10 ，5 和 24 ，12 ，7 C24 ，10 ，10和24，14，1 1 D 24，10，5 和24，14，6 4现在
12、有一颗无重复关键字的平衡二叉树（ AVL树）,对其进行中序遍历可得到 一个降序序列。下列关于该平衡二叉树的叙述中，正确的是 A根节点的度一定为2 B树中最小元素一定是叶节点 C最后插入的元素一定是叶节点D树中最大元素一定是无左子树 5 设有向图G=(V,E) ， 顶点集V=V0,V1,V2,V3， 边集 E=,，, 若从顶点 V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个 数是 A2 B3 C4 D5 6求下面带权图的最小（代价）生 成树时，可能是克鲁斯卡（ kruskal ）算 法第二次选中但不是普里姆（ Prim）算 法（从 V4 开始）第2 次选中的边是 A(V1,V3) B
13、(V1,V4) C(V2,V3) D(V3,V4) left weight right 7下列选项中，不能构成折半查找中关键字比较序列的是 A500，200，450 ，180 B500 ，450，200，180 C180 ，500，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 B2 C3 D4 11希尔排序的组内排序采用的是（） A直接插入排序B折半插入排序 C快速排序D归并排序 41. 用单链表保存m 个整数，节点的结构为(data,link) ，且 |data|=2)个顶点的邻接 矩阵为B 则，Bm(2=m=n)非零元素的 含义是什么？
