2017年福州大学考研真题-863数据结构与程序设计
- 格式：pdf
- 大小：219.07 KB
- 文档页数：7
下载文档原格式
合集下载
数据结构精选考研试题
[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：[20分]1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？3、什么是结构化程序设计？4、哈希方法的基本思想5、给出一不稳定排序方法名称与实例二、构造结果：[24分]（1）确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。
for i:=1 to n dofor j:=1 to I dofor k:=1 to j do x:=x+1（2）画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。
（3）已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．（4）假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．（5）在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i为关键字中第一字母在字母表中的序号。
要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。
（6）构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。
三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。
[15分]四、编写一非递归算法，对一棵二叉排序树实现中序遍历。
[15分]五、编写程序，完成下列功能：[15分]1．读入整数序列，以整数0作为序列的结束标志（0不作为序列元素），建立一个单链表。
2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。
例：输入序列为：1，8，4，3，0六、给出有向图G的邻接表表示。
找出其一棵最小生成树。
[11分][注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：[20分]1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？3、什么是结构化程序设计？4、哈希方法的基本思想5、给出一不稳定排序方法名称与实例二、构造结果：[24分]（1）确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。
【最新试题库含答案】2017考研计算机真题及答案
2017考研计算机真题及答案：篇一：2017考研计算机专业考研备考资料2017考研计算机专业考研备考资料计算机专业已成为当前考研最热门专业之一，纵观近几年报名录取情况会发现：报考人数在逐年增加，竞争压力在持续升温，而录取概率却非常小。
今天小编为同学们推荐一些优质权威的计算机专业课复习资料，以帮助同学们提升复习效果。
考试内容计算机科学与技术学科的初试科目调整后为4门：政治理论（100分）、外国语（100分）、数学一（150）和计算机学科专业基础综合（150分）。
计算机学科专业基础综合科目，主要考查考生掌握相关基础知识、基本理论和分析问题解决问题的能力。
考试实行联合命题，考试内容包括：数据结构、计算机组成原理、操作系统和计算机网络。
各阶段资料推荐第一阶段（3～7月）这一阶段为基础复习阶段，复习资料应该选择和大纲吻合的教材以及配套的习题。
数据结构可以选用严蔚敏主编、清华大学出版社出版的C语言版的《数据结构》，习题建议选用李春葆主编、清华大学出版社出版的《数据结构习题与解析》。
计算机组成原理有两个版本的教材可供选择：一个是白中英主编、科学出版社出版的《计算机组织与结构》（最新版是第4版）及配套习题；另一个是唐朔飞主编、高等教育出版社出版的《计算机组成原理》及配套习题。
操作系统建议选用：汤子瀛主编、西安电子科技大学出版社出版的《计算机操作系统》，配套习题可以选用李春葆主编、清华大学出版社出版的《操作系统习题与解析》。
计算机网络选用谢希仁主编、电子工业出版社出版的《计算机网络》（最新版是第5版）及配套习题。
在复习书本知识的基础上，同学们可以配合网络课程学习。
该阶段我们推荐考试点网络免费课程： 2017年考研计算机专业备考指南。
该节课对同学们帮助非常大，尤其是一战学子。
第二阶段（７～10月）第二阶段为强化复习、重点深入阶段，时间一般是7～10月份。
该阶段可以选用的教材有：高等教育出版社出版的的《计算机专业基础综合考试大纲解析》、复旦大学出版社出版的《计算机专业基础综合考试复习指南》。
算法与数据结构试卷--福州大学
一、选择题（10*2%=20%）1．代码段for (j=1; j<=n;j++) 的时间复杂性是B。
for (k=n; k>=1; k/=2)count++;A、O(n2)B、O(nlogn)C、O(logn)D、O(n)2．对某个无向图的邻接矩阵来说，下列叙述正确的是 A 。
A、第i行上的非零元素个数和第i列上的非零元素个数一定相等B、矩阵中的非零元素个数等于图中的边数C、第i行与第i列上的非零元素的总数等于顶点vi的度数D、矩阵中非全零行的行数等于图中的顶点数3．循环双链表中在p所指结点之后插入结点s的操作是D。
A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->nextB、p->next=s; p->next->prior=s; s->prior=p; s->next=p->nextC、s->prior=p; s->next=p->next; p->next=s; p->next->prior=sD、s->prior=p; s->next=p->next; p->next->prior=s; p->next=s4．4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态如图，，不可能的出栈顺序是C。
A、a4，a3，a2，a1B、a3，a2，a4，a1C、a3，a1，a4，a2D、a3，a4，a2，a15．下列四种排序方法中，不稳定的方法是D。
A、插入排序B、冒泡排序C、归并排序D、选择排序6．单个结点二叉树的高度为0，所有含有15个结点的二叉树中，最小高度是D。
A、6B、5C、4D、37．在一个具有n个顶点的无向图中，要连通全部顶点至少需要B条边。
A、nB、n-1C、n/2D、n+18．快速排序法的运行效率取决于D。
福州大学2017考研各专业报录比统计
电气工程与自动化学院 电力电子与电力传动 104 电气工程与自动化学院 电工理论与新技术 15
电气工程与自动化学院 控制理论与控制工程 53 检测技术与自动化装 电气工程与自动化学院 置 电气工程与自动化学院 系统工程 1 6
2
1
0
1
全日制
1
1
0
0
全日制
中国高端辅导品牌 专注教育 20 年
电气工程与自动化学院 模式识别与智能系统 14 电气工程与自动化学院 * 电气工程 电气工程与自动化学院 * 电气工程 电气工程与自动化学院 * 控制工程 195 110 12
4 88 9 21 2 2 3 17 16 25 8 5 11 85 5 30
1 66 9 11 1 0 0 7 9 5 3 2 11 70 2 30
资源循环科学与工程 4 安全科学与工程 * 地质工程 * 环境工程 * 环境工程 政治经济学 西方经济学 23 7 33 5 10 11
中国高端辅导品牌 专注教育 20 年
经济与管理学院
世界经济 人口、资源与环境经
17
2
2
0
0
全日制
经济与管理学院 济学 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 经济与管理学院 区域经济学 财政学 金融学 产业经济学 国际贸易学 数量经济学 * 金融 * 应用统计 * 国际商务 统计学 * 工业工程 * 物流工程 管理科学与工程 ★信息管理与信息系 经济与管理学院 统 经济与管理学院 经济与管理学院 ★物流管理 ★金融工程
722 197 98 55 4 9
江西师范大学计算机信息工程学院863数据结构与程序设计历年考研真题专业课考试试题
目 录
2013年江西师范大学863数据结构与程序设计考研真题 2014年江西师范大学863数据结构与程序设计考研真题 2015年江西师范大学863数据结构与程序设计考研真题 2016年江西师范大学863数据结构与程序设计考研真题 2017年江西师范大学863数据结构与程序设计考研真题 2018年江西师范大学863数据结构与程序设计考研真题
2013年江西师范大学863数据结构 与程序设计考研真题
2014年江西师范大学863数据结构 与程序设计考研真题
2015年江西师范大学863数据结构 与程序设计考研真题
2016年江西师范大学863数据结构 程序设计考研真题2017年江西师范大学863数据结构 与程序设计考研真题
2018年江西师范大学863数据结构 与程序设计考研真题
2013年江西师范大学863数据结构与程序设计考研真题 2014年江西师范大学863数据结构与程序设计考研真题 2015年江西师范大学863数据结构与程序设计考研真题 2016年江西师范大学863数据结构与程序设计考研真题 2017年江西师范大学863数据结构与程序设计考研真题 2018年江西师范大学863数据结构与程序设计考研真题
2013年江西师范大学863数据结构 与程序设计考研真题
2014年江西师范大学863数据结构 与程序设计考研真题
2015年江西师范大学863数据结构 与程序设计考研真题
2016年江西师范大学863数据结构 程序设计考研真题2017年江西师范大学863数据结构 与程序设计考研真题
2018年江西师范大学863数据结构 与程序设计考研真题
2015年度福州大学863数据结构与程序设计模拟题3标准答案
模拟题三参考答案1．C。
【解析】考查时间复杂度。
在程序中，执行频率最高的语句为“i=i*3”。
设该基本语句一共执行了k次，根据循环结束条件，有n>2*3k≥n/3，由此可得算法的时间复杂度为O(log3n)。
2．A。
【解析】考查出入栈操作的性质。
当P1=3，表示3最先出栈，前面1、2应在栈中，此时若出栈操作，则p2应为2；此时若进栈操作（进栈1次或多次），则p2为4、5、…、n都有可能，故选A。
3. B。
【解析】考查队列的应用。
图的广度优先搜索类似于树的层序遍历（形象地想象成一个扇形，以搜索起点为中心，逐层向相连的外圈搜索），同样需要借助于队列。
前序遍历二叉树是一个递归的过程，通常可以借助于栈，将递归算法转换为非递归算法。
图的深度优先搜索类似于树的前序遍历，也是一个递归的过程，通常也可以借助栈来实现。
4．C。
【解析】考查平衡二叉树的性质。
在平衡二叉树的结点最少情况下，递推公式为N0=0，N1=1，N2=2，N h=1+N h-1+N h-2（h为平衡二叉树高度，N h为构造此高度的平衡二叉树所需最少结点数）。
通过递推公式可得，构造5层平衡二叉树至少需12个结点，构造6层至少需要20个。
5．C。
【解析】考查二叉排序树的构造过程。
画出三个选项ABC构造的二叉排序树的草图即可知道答案，C和AB构造的树形不同；再画出最后一个选项D构造的二叉排序树即可验证答案，D和AB两项的相同。
6．B。
【解析】考查几种特殊二叉树的特点。
二叉判定树描述了折半查找的过程，肯定是高度平衡的，因此不可能是A。
对于B，此图中所有结点的关键值均大于左子树中结点关键值，且均小于右子树中所有结点的关键值，B 符合。
对于C，此图中存在不平衡子树，错误。
对于D，此图不符合小根堆或大根堆的定义。
7．C。
【解析】考查哈夫曼树的构造。
将16个权值相等（设为m）的字母看成16个独立的结点；从中任选两个结点构成一棵新的二叉树（共8棵），新树的权值为2m；再从8棵树中任选2棵构成新的二叉树（共4棵），新树的权值为4m，……，如此继续，刚好能构成一棵满二叉树。
计算机考研专硕院校信息汇总
计算机考研专硕院校信息汇总1.中山大学（985）广东省广州软件工程：867专业基础（数据结构）620)软件学院院系：100 本专：100 推免：60 专业：40621)（1）101思想政治理论（2）204英语二（3）302数学二（4）867专业基础（数据结构）复试专业课：F62 01计算机综合考试①《离散数学》，耿素云、屈婉玲，高等教育出版社，1998。
②《C程序设计》第二版，谭浩强编，清华大学出版社，1999。
计算机技术：（408）综合350)信息科学与技术学院院系：287 专硕：143 推免：100 一般：43 (470)中山大学-卡内基梅隆大学联合工程学院（922）数据结构与计算机原理本专：40分数线：300；270；2702.华南理工大学（985）广东省广州计算机技术：（831）计算机专业综合(数据结构、操作系统)008)计算机科学与工程学院院系：133 专业招生人数:55① 101思想政治理论② 204英语1③302数学1④831计算机专业综合(数据结构、操作系统) 复试笔试科目：902上机能力测试:数据库复试科目参考书：《数据库系统概论》(第三版)王能斌著，,电子工业出版社；《数据库系统概念》(第四版)中文版，杨冬青、唐世渭等编译，机械工业出版社；《数据库系统教程》王能斌著，电子工业出版社软件工程：（408）综合(023)软件学院院系：74推免：373.暨南大学（211）广东省软件工程和计算机技术：（830）数据结构(010)信息科学技术学院院系：110 推免：20 软件工程专业：10①101思想政治理论②204英语二③302数学二④830数据结构830数据结构1．严蔚敏、吴伟民, 数据结构（C语言版）,清华大学出版社出版2．严蔚敏, 吴伟民,《数据结构习题解析》,清华大学出版社出版复试科目：C语言程序设计加试科目：①离散数学②计算机基础！！华南师范大学广东省软件工程：（918)计算机综合考试（操作系统、程序设计）(019)计算机学院院系：62 推免：164.华东师范大学（985）上海市085211 数据结构（含c语言）计算机技术1.上机考试：主要考查学生运用计算机编程解决问题的能力，上机语言为C或C++。
历年卷------算法与数据结构(福州大学) - 副本
14、平衡二叉树中结点的平衡因子不可能是（ ） 。 A、0 B、-1 C、1 D、2 15、下列有关二叉搜索树上的运算说法正确的是（ ） 。 A、 从根结点起在二叉搜索树上查找某元素，若当前结点存放的元素比被查找元素 大，则在当前结点的右子树中继续查找 B、在二叉搜索树中删除一个元素时，若被删元素所在结点存在左右子树，可用其 左子树中最右下结点中的元素替代被删元素，并将该最右下结点的左子树挂接 为其父结点的右子树。调整结构后的二叉树仍为一棵二叉搜索树。 C、从根结点起在二叉搜索树中查找某元素 y 的直接前驱元素，若当前结点存放的 元素 x 小于 y，则以 x 作为 y 直接前驱的候选者，并继续在当前结点的左子树 中进行查找 D、从根结点起在二叉搜索树中查找某元素 y 的直接后继元素，若当前结点存放的 元素 x 等于 y，则在当前结点的左子树中继续查找
得分 评卷人
1、以下函数的时间复杂度为（ ） 。 int Rsum ( int a[], int n ) { if ( n>0 ) return Rsum ( a, n-1 ) + a[n-1]; return 0; } A、O(1) B、O(n2) C、O(n) D、O(nlog2n) 2、下列不属于顺序存储结构特点的是（ ） 。 A、可对元素进行随机访问 B、非表尾的插入和删除操作需要移动表中大量元素 C、相邻元素在内存中的物理位置也是相邻的 D、采用该存储结构的线性表空间可动态扩充 3、设在带哨兵结点的单链表中，链结点的指针域为 next，在指针 p 所指结点后插入由 指针 y 所指的新结点，应使用的语句为（ ） 。 A、p->next=y->next; y->next=p; B、y->next=p->next; p->next=y; C、p->next=y->next; p->next=y; D、y->next=p->next; y->next=p;
2017年福州大学837经济学综合考研真题(回忆版)
2017年福州大学837经济学综合考研真题（回忆版）聚英厦大考研网整理了2017年福州大学837经济学综合考研真题（回忆版），仅供大家参考，欢迎广大考生纠正补充，希望能对2018年考研的同学们有所帮助。
一、判断题（10*2）二、名词解释（5*5）1、规模经济2、生产者剩余3、流动性陷阱4、索洛余量5、资本有机构成三、简答及作图题（3*10）1、我国对外开放的理论依据和客观依据。
2、垄断或不完全竞争为什么会造成低效率？3、画图说明总支出曲线和总需求曲线的区别。
四、计算题（2*15）（ps.今年只考了两题，但都很简单，只要课本习题都会做考试一般没问题）1、已知某完全竞争市场的需求函数为D=6300-400P，短期市场供给函数为SS=3000+150P；单个企业在LAC曲线最低点的价格为6，产量为50；单个企业的成本规模不变。
（1）求市场的短期均衡价格和均衡产量；（2）判断（1）中的市场是否同时处于长期均衡，求企业内的厂商数量；（3）如果市场的需求函数变为D`=8000-400P，短期供给函数为S`=4700-400P，求市场的短期均衡价格和均衡产量；（4）判断（3）中的市场是否同时处于长期均衡，并求行业内的厂商数量；（5）判断该行业属于什么类型；（6）需要新加入多少企业，才能提供（1）到（3）所增加的行业总产量？2、假设某经济的消费函数为c＝100＋0.8yd，投资i＝50，政府购买性支出g＝200，政府转移支付tr＝62.5，税率为0.25。
税收（单位均为10亿美元）（1）求均衡收入。
（2）试求投资乘数、政府支出乘数、税收乘数、转移支付乘数、平衡预算乘数。
（3）假定该社会达到充分就业所需要的国民收入为1 200，试问：(1)增加政府购买；(2)减少税收；(3)以同一数额增加政府购买和税收(以便预算平衡)实现充分就业，各需多少数额？（4）如果将题干中的比例税换为定量税t＝250，上述结果有什么不同？五、论述题（50分）（ps.今年论述整体不那么主流，尤其是考的公共选择理论，所以大家复习的时候一定要全面，尤其是市场失灵和经济增长这两章，几乎每年都必出论述题）1、某些商品的政府限价会造成供不应求状态，有些学者认为取消政府就可以解决这个问题，请用需求价格和均衡价格理论说这种做法的可行性，并用我国的商品举一个例子说明。
福州大学863数据结构与程序设计_模拟题1答案
模拟题一参考答案一、单项选择题1．B。
考查栈和队列的特点及应用。
C和D直接排除，缓冲区的特点需要先进先出，若用栈，先进入缓冲区的数据则要排队到最后才能打印，不符题意，故选B。
2．C。
考查栈的最大递归深度。
时刻注意栈的特点是先进后出。
出入栈的详细过程见表栈内的最大深度为3，故栈S的容量至少是3。
3．D。
考查二叉树的特殊遍历。
分析遍历后的结点序列，可以看出根结点是在中间被访问的，而右子树结点在左子树之前，得遍历的方法是RNL。
本题考查的遍历方法并不是二叉树的三种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。
4．B。
考查平衡二叉树的定义。
根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过1。
而其余三个答案均可以找到不符合的结点。
5．C。
考查完全二叉树的特点。
完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。
第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。
若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2=16个叶结点，故完全二叉树的结点个数最多为27-1-16=111个结点。
6．B。
考查森林和二叉树的转换。
森林与二叉树的转换规则为“左孩子右兄弟”。
在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。
情形Ⅰ：若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。
情形Ⅱ：结点u和v是兄弟结点的关系，但二者之中还有一个兄弟结点k，则转换后，结点v就变为结点k的右孩子，而结点k则是结点u的右孩子，符合要求。
情形Ⅲ：结点v的父结点要么是原先的父结点或兄弟结点。
若结点u的父结点与v的父结点是兄弟关系，则转换之后，不可能出现结点u是结点v的父结点的父结点。
7．A。
考查无向连通图的特性。
每条边都连接了两个结点，则在计算顶点的度之和时，这条边都被计算了两次，故所有顶点的度之和为边数的两倍，显然必为偶数。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
6.写出以下程序的运行结果。 #include <iostream>
using namespace std; fun ( ); fun ( ); void main ( ) {
fun ( ); fun ( ); } void fun ( ) { static int a = l; int i = 5; a++; i++; cout<<"i="<<i<<",a="<<a<<endl; }
int main ( ) { A *a = new B(15);
delete a; return 0; }
11.写出以下程序的运行结果。 #include <iostream> using namespace std; class A {
public: void f ( ) {cout<<"Call A's function f ( )"<<endl;}
} }
9.写出以下程序的运行结果。 #include <iostream.h> #include <math.h> using namespace std; class Point {
public: Point (int xx =0, int yy = 0) { X = xx; Y = yy; cout<<"构造函数被调用"<<endl; } Point(Point &p); int GetX ( ) {return X;} int GetY ( ) {return Y;}
cout<<w; cout<<endl; } } void main ( ) { print(4); }
3.写出以下程序的运行结果 #include <iostream> using namespace std; void main ( ) {
int j, k; for (j=5; j>0; j--) {
12.写出所有 ABC 为入栈序列的可能的出栈序列。
13.给定数列 5、3、6、8、2、9、7、4。根据给定数列写出插入排序前四趟的过程。
14.将 23、15、27、31、8、5、18 初始化为极小化堆并执行两次 DeleteMin 操作。
15.用 kruskal 算法对下图构造最小支撑树。
16.设散列函数 H(k)=kmod7，散列表的地址空间为 0-6，对关键字序列{32, 13, 49, 18, 22, 38, 21}。 (1)按链地址法处理冲突的办法构造哈希表（开散列）。 (2)按照线性探测法构造哈希表（闭散列）。
for (k=j; k>0; k--) cout<<"*";
cout<<endl; } }
4.写出以下程序的运行结果。 #include <iostream> using namespace std; void main ( ) {
int Array[3]; Array[0] = 10; Array[l] = 20; Array[2] = 30; int *pArray; pArray = &Array[0]; cout<<"pArray points to the value."<<endl; cout<<*pArray<<endl; cout<<*(pArray+1)<<endl; }
}; class B: pubilc A {
public: B(int i) {cout << "B::B ( ) called.\n"; buf = new char[i];} virtual ~B ( ) {delete []buf; cout<<"B::B ( ) called.\n";}
private: char *buf;
8.写出以下程序的运行结果。 #include <iostream>
using namespace std; void main ( ) {
int b[2][4] = {12, 36, 62, 14, 56, 98, 74, 63}; int (*p)[4] = b; int i, j; for (i=0; i<2; i++) {
10.写出以下程序的运行结果。 #include <iostream> using namespace std; class A {
public: A ( ) {cout << "A::A ( ) called.\n";} virtual ~A ( ) {cout << "A::A ( ) called.\n";}
public: void g ( ) {cout<<"Call C's function g ( )"<<endl;}
} int main ( ) {
C cc; cc.B::f ( ); cc.B::g ( ); cc.g ( ); return 0; }
四、算法计算题。
11.顺序表用数组实现，在实现插入一个数平均需要移动多少个数？实现删除一个数平均需要移动多少个 数?
} class B {
public: void f ( ) {cout<<"Call B's function f ( )"<<endl;} void g ( ) {cout<<"Call B's function g ( )"<<endl;};
} class C:public A, public B {
17.用 3、5、6、2、4、9 构造二叉搜索树。写出其是 AVL 树时的情况。
五、程序设计题。
18.给定一个十进制位 N，试求其二进制中 1 的个数，算法满足下列复杂度。 (1)时间复杂度为 O(nlogn)。 (2)复杂度只与二进制数中 1 的个数有关。 (3)时间复杂度为 O(1)。
19.快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部 分的所有数据都要小，然后在按此方法对这两部分数据 分别进行快速排序，整个排序过程可以递归进行， 以此达到整个数据变成有序序 列。试写出一个快速排序改进算法，使得在最坏情况下，快速排序的时间 复杂度为 O(nlogn)。
for (j=0; j<4; j++) cout<<*(*(p+i)+j)<<" ";
cout<<endl; } for (i=0; i<20; i++)
for (i=0; i<2; i++) { for (j=3; j>=0; j--) cout<<p[i][j]<<" "; cout<<endl;
福州大学
2017 年招收攻读硕士学位研究生入学考试
863 数据结构与程序设计
一、程序阅读题（每小题 4 分，共计 48 分）。
1.写出以下程序的运行结果。 #include <iostream> using namespace std; void main ( ) {
int b[3][5] = {11, 2, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35}; int (*p)[5]; p = b; for (int j=0; j<5; j++)
7.写出以下程序的运行结果。 #include <iostream> using namespace std; class Point {
public: Point (int xx=0, int yy = 0) {X = xx; Y = yy; countP++;} int GetX ( ) {return X;} int GetY ( ) {return Y;} void GetC ( ) {cout<<"Object id="<<countP<<endl;}
private: int X, Y;
} Point::Point(Point &p) {
X = p.X; Y = p.Y; cout<<"Point 拷贝构造函数调用"<< {
public: Distance (Point xp1, Point xp2); double GetDis ( ) {return dist;}
private: int X, Y; static int countP;
}; int Point::countP = 0; void main ( ) {
Point A(4, 5); cout<<"Point A,"<<A.GetX ( )<<","<<A.GetY ( ); A.GetC ( ); cout<<"Point B,"<<B.GetX ( )<<","<<B.GetY ( ); B.GetC ( ); }
cout<<*(*p+j)<<","; cout<<endl; }
using namespace std; fun ( ); fun ( ); void main ( ) {
fun ( ); fun ( ); } void fun ( ) { static int a = l; int i = 5; a++; i++; cout<<"i="<<i<<",a="<<a<<endl; }
int main ( ) { A *a = new B(15);
delete a; return 0; }
11.写出以下程序的运行结果。 #include <iostream> using namespace std; class A {
public: void f ( ) {cout<<"Call A's function f ( )"<<endl;}
} }
9.写出以下程序的运行结果。 #include <iostream.h> #include <math.h> using namespace std; class Point {
public: Point (int xx =0, int yy = 0) { X = xx; Y = yy; cout<<"构造函数被调用"<<endl; } Point(Point &p); int GetX ( ) {return X;} int GetY ( ) {return Y;}
cout<<w; cout<<endl; } } void main ( ) { print(4); }
3.写出以下程序的运行结果 #include <iostream> using namespace std; void main ( ) {
int j, k; for (j=5; j>0; j--) {
12.写出所有 ABC 为入栈序列的可能的出栈序列。
13.给定数列 5、3、6、8、2、9、7、4。根据给定数列写出插入排序前四趟的过程。
14.将 23、15、27、31、8、5、18 初始化为极小化堆并执行两次 DeleteMin 操作。
15.用 kruskal 算法对下图构造最小支撑树。
16.设散列函数 H(k)=kmod7，散列表的地址空间为 0-6，对关键字序列{32, 13, 49, 18, 22, 38, 21}。 (1)按链地址法处理冲突的办法构造哈希表（开散列）。 (2)按照线性探测法构造哈希表（闭散列）。
for (k=j; k>0; k--) cout<<"*";
cout<<endl; } }
4.写出以下程序的运行结果。 #include <iostream> using namespace std; void main ( ) {
int Array[3]; Array[0] = 10; Array[l] = 20; Array[2] = 30; int *pArray; pArray = &Array[0]; cout<<"pArray points to the value."<<endl; cout<<*pArray<<endl; cout<<*(pArray+1)<<endl; }
}; class B: pubilc A {
public: B(int i) {cout << "B::B ( ) called.\n"; buf = new char[i];} virtual ~B ( ) {delete []buf; cout<<"B::B ( ) called.\n";}
private: char *buf;
8.写出以下程序的运行结果。 #include <iostream>
using namespace std; void main ( ) {
int b[2][4] = {12, 36, 62, 14, 56, 98, 74, 63}; int (*p)[4] = b; int i, j; for (i=0; i<2; i++) {
10.写出以下程序的运行结果。 #include <iostream> using namespace std; class A {
public: A ( ) {cout << "A::A ( ) called.\n";} virtual ~A ( ) {cout << "A::A ( ) called.\n";}
public: void g ( ) {cout<<"Call C's function g ( )"<<endl;}
} int main ( ) {
C cc; cc.B::f ( ); cc.B::g ( ); cc.g ( ); return 0; }
四、算法计算题。
11.顺序表用数组实现，在实现插入一个数平均需要移动多少个数？实现删除一个数平均需要移动多少个 数?
} class B {
public: void f ( ) {cout<<"Call B's function f ( )"<<endl;} void g ( ) {cout<<"Call B's function g ( )"<<endl;};
} class C:public A, public B {
17.用 3、5、6、2、4、9 构造二叉搜索树。写出其是 AVL 树时的情况。
五、程序设计题。
18.给定一个十进制位 N，试求其二进制中 1 的个数，算法满足下列复杂度。 (1)时间复杂度为 O(nlogn)。 (2)复杂度只与二进制数中 1 的个数有关。 (3)时间复杂度为 O(1)。
19.快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部 分的所有数据都要小，然后在按此方法对这两部分数据 分别进行快速排序，整个排序过程可以递归进行， 以此达到整个数据变成有序序 列。试写出一个快速排序改进算法，使得在最坏情况下，快速排序的时间 复杂度为 O(nlogn)。
for (j=0; j<4; j++) cout<<*(*(p+i)+j)<<" ";
cout<<endl; } for (i=0; i<20; i++)
for (i=0; i<2; i++) { for (j=3; j>=0; j--) cout<<p[i][j]<<" "; cout<<endl;
福州大学
2017 年招收攻读硕士学位研究生入学考试
863 数据结构与程序设计
一、程序阅读题（每小题 4 分，共计 48 分）。
1.写出以下程序的运行结果。 #include <iostream> using namespace std; void main ( ) {
int b[3][5] = {11, 2, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35}; int (*p)[5]; p = b; for (int j=0; j<5; j++)
7.写出以下程序的运行结果。 #include <iostream> using namespace std; class Point {
public: Point (int xx=0, int yy = 0) {X = xx; Y = yy; countP++;} int GetX ( ) {return X;} int GetY ( ) {return Y;} void GetC ( ) {cout<<"Object id="<<countP<<endl;}
private: int X, Y;
} Point::Point(Point &p) {
X = p.X; Y = p.Y; cout<<"Point 拷贝构造函数调用"<< {
public: Distance (Point xp1, Point xp2); double GetDis ( ) {return dist;}
private: int X, Y; static int countP;
}; int Point::countP = 0; void main ( ) {
Point A(4, 5); cout<<"Point A,"<<A.GetX ( )<<","<<A.GetY ( ); A.GetC ( ); cout<<"Point B,"<<B.GetX ( )<<","<<B.GetY ( ); B.GetC ( ); }
cout<<*(*p+j)<<","; cout<<endl; }