华北电力大学数据结构

1、声明此文件为参加2015年考研华北电力大学844数据结构初试的考生，根据回忆总结的题目。相关题目可能与实际考试中的题目有出入，但是难度相当，可以作为备考华电计算机技术专硕的考生做为练习习题使用。第一题选择，10道题20分，很简单，比王道上的题要简单的多把王道的题做了，选择基本没问题。第二题填空题10空20分，也很简单。第3题简答15分5问，第4题算法题55分4道题5小问。第5题40分两道大题都很简单。最后给大家些建议：卷子中除了算法题外，其他都很简单。建议大家多看算法，主要是键表，树，图（主要是深度优先和广度优先遍历算法）。另外考试大纲上没有写哈西表，但实际会考。今年有两小题共5分考哈西表。最

2、后说一句：考研的路很漫长，如果选择了，希望大家坚持到底，尤其到了10份以后更要坚持。祝学弟们考研成功！华电2015年初试考生2015年4月17日 华北电力大学（北京）2015年硕士研究生入学模拟试题 考试科目：844数据结构 （闭卷考试，时间120分钟，总分150分）I 选择填空部分（考生注意：答案必须写在答题纸上）得 分一、单项选择题（每小题2分，共20分)阅卷人1. 数据结构中，与所使用的计算机无关的是数据的（ ）结构；A、存储 B、物理 C、逻辑 D、物理和存储2.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ ）A、访问第i个结点（1in）和求第i个结点的直接前驱（2in）

3、 B、在第i个结点后插入一个新结点（1in）C、删除第i个结点（1in）D、将n个结点从小到大排序3.有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。A、8 B、63.5 C、63 D、74. 线性表L在（ ）情况下适用于使用链式结构实现。5. A、需经常修改L中的结点值 B、需不断对L进行删除插入 C、L中含有大量的结点 D、L中结点结构复杂5.不含任何结点的空树( )A、是一棵树; B、是一棵二叉树; C、是一棵树也是一棵二叉树; D、既不是树也不是二叉树6.从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（ ）A、希尔排序

4、 B、归并排序 C、插入排序 D、选择排序7.已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是( )A、 0 2 4 3 1 6 5 B、 0 1 3 5 6 4 2 C、 0 1 2 3 4 6 5 D、 0 1 2 3 4 5 68.已知完全二叉树有28个结点，则整个二叉树有( )个度为1的结点。A、 0; B、 1; C、 2; D、 不确定9. 设输入序列为1,2,3,4,5借助一个栈不可能得到的输出序列是( )A 、 1,2,3,4,5 B 、5,4,3,2,1 C 、 4,3,1,2,5 D、 1,3,2,5,410.任何一个无向连通图的最小生成树( )A、只

5、有一棵 B、 一棵或多棵 C、一定有多棵 D、可能不存在得 分二、填空题（每空2分，共20分）阅卷人1.数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。2. 在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。4.顺序栈S,栈顶指针为top,则栈置空操作是 .5.在如下一维数组A中折半查找36和85时,所需比较的次数分别为 和 . 25,36,40,45,48,56,60,68,72,856.在有N(N0)个结点的二叉链表中，空链域的个数是： 。7.设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序

6、顺序存储，则元素a32,58的存储地址为 。8.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 。 主观题部分得 分三、简答题（每题3分，共15分）阅卷人1. 散列的基本思想是什么?举出五种常用的散列函数的构造方法.2.什么是冲突?处理冲突的方法是什么?3.一个深度为L的满K叉树有如下性质:第L层上的结点是叶子结点,其余各层上每个结点都有K棵非空子树,如果按层次顺序从1开始对全部结点编号,问:(1) 各层的结点的数目是多少?(2) 编号为n的结点的双亲结点(若存在)编号是多少?(3) 编号为n的结点的第i个孩子(若存在)编号是多少?4. 说明线性表、栈与队的异同点。5.对分（折半）查找

7、适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？得 分四、算法题（共55分）阅卷人1.试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（ij）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。（15分）2.用两种方法编写按层次顺序（同一层自左至右）遍历二叉树的算法。（20分）3.试编写算法,将数组int An中的所有奇数移到所有偶数之前.要求时间复杂度为O(n).（10分）4.从循环单链表中查找出最大值的算法.（10分）得 分五、综合题（每题10分，共40分）阅卷人1.试利用Dijkstra算法

8、求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。（20分） 2.已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。(2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。(3) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 华北电力大学（北京）20

9、15年硕士研究生入学模拟试题参考答案 考试科目：844数据结构 （闭卷考试，时间120分钟，总分150分）I 选择填空部分（考生注意：答案必须写在答题纸上）得 分一、单项选择题（每小题2分，共20分)阅卷人答案：CABBC DCBCA 得 分二、填空题（每空2分，共20分）阅卷人答案：操作对象 关系表中一半 表长和该元素在表中的位置s-top=-12 4N+18950O(n2) 主观题部分得 分三、简答题（每题3分，共15分）阅卷人答案：1.散列的基本思想是:以结点的关键字K为自变量,通过一个确定的函数关系f,计算出对应的函数值f(K),把这个值解释为结点的存储地址,然后到相应的单元里去取要找

10、的结点.散无函数的构造方法:1.数字选择法2.平方到中法3.折叠法4.除余法5基数转换法6随机数法2.若某个散列函数H对于不相等的关键字key1和key2得到相同的散列地址(即H(key1)=H(key2)则将该现象称为冲突.解决冲突的方法有:开放定址法和链地址法3.（1）K(I-1)(1=Inextarc，level-) level+; k=p-adjvex; if(!visitedk&exist_path(k,j) return 1;/i下游的顶点到j有路径 /for /else if (level=1) return 0;/exist_path_DFS 2.思路：既然要求从上到下，从左到

11、右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，以此产生了按层次输出的效果。level(liuyu*T)/* liuyu *T,*p,*q100; 假设max已知*/int f,r;f=0; r=0; /*置空队*/r=(r+1)%max;qr=T; /*根结点进队*/while(f!=r) /*队列不空*/f=(f+1%max);p=qf; /*出队*/printf(%d,p-data); /*打印根结点*/if(p-l

12、child)r=(r+1)%max; qr=p-lchild; /*若左子树不空，则左子树进队*/ if(p-rchild)r=(r+1)%max; qr=p-rchild; /*若右子树不空，则右子树进队*/ return(0);法二：void LayerOrder(Bitree T)/层序遍历二叉树 InitQueue(Q); /建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); /LayerOrder 3. move(a,n)int a