《2016年福建华侨大学数据结构考研真题.doc》由会员分享，可在线阅读，更多相关《2016年福建华侨大学数据结构考研真题.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2016年福建华侨大学数据结构考研真题第一部分数据结构（总分75分）一.单项选择题（每题1.5分，共12分）1.下列关于顺序存储结构的叙述哪一个是错误的？（）A存储密度大B插入操作不方便C不可随机访问任意结点D存储单元的地址是连续的2.已知二叉树的空指针域是m，则该二叉树的结点个数是（）。A.mB.m-1C.m+1D.m+23.一棵树高为H的完全二叉树的节点总数至少是（）。4.在一个双向链表中，若要删除指针p所指的结点，则执行()。A.free(p);p-prior-next=p-next;p-next-prior=p-prior;B.p-next-prior=p-prior;free(p);
2、p-prior-next=p-next;C.p-next-prior=p-next;p-prior-next=p-prior;free(p);D.p-prior-next=p-next;p-next-prior=p-prior;free(p);5.设树T的度为3，其中度为1，2，3的结点个数分别为2，4，1，则T中的叶子数为（）。A5B6C7D86.右图给出由7个顶点组成的无向图。从顶点4出发，对它进行深度优先遍历得到的顶点序列不可能是()。A4127635B4513276C4135276D45213767.若用线性探测法将关键字相同的m个记录存入哈希表中，总共至少需要进行()次探测。AmB.
3、m+1C.m(m+1)/2D.1+m(m+1)/28.下列顶点序列中，哪一个不是右边的有向无环图的拓扑有序序列（）。A.ADBECFB.ADBEFCC.ADEFCBD.DABECF二.问答题（共38分）1.（2分）三维数组a547（下标从0开始计，a有5*4*7个元素），每个元素的长度是2，则a234的地址是。(设a000的地址是1000,数据以行为主方式存储)。2.（4分）考虑如下程序段，（1）第二个for语句中的“jn”判断语句的执行频度是。（2分）（2）语句“temp+”的执行频度是。（2分）3.（2分）有一个时间复杂度为O(n2)的算法，在有30个元素的数组上运行需耗时4毫秒，则在30
4、0个元素的数组上运行大约需要毫秒。4.（7分）已知一颗二叉树的先序遍历结点序列是ABDGCEHIF，中序遍历结点序列是BGDAHEICF，回答如下问题：(1)画出这棵二叉树（3分）(2)这棵二叉树的后序遍历结点序列是（2分）(3)在(1)中画出的二叉树中添加后序线索，构成后序线索二叉树（2分）5.（5分）设哈希表的地址范围为013，哈希函数为：H(K)=KMOD11,K为关键字，用线性探测再散列法处理冲突，输入关键字序列:(11,20,31,17,15,21,25,13,2,9)，造出哈希表，试回答下列问题：(1)画出哈希表示意图（3分）(2)假定每个关键字的查找概率相等，求查找成功时的平均查
5、找长度。（2分）6.（5分）有一组键值20,50,13,38,40,23,11,32,20,请采用希尔排序方法由小到大进行排序（增量d1=5,d2=3,d3=1），请写出每趟的排序结果。7.（2分）请画出如下森林的孩子兄弟法表示的二叉树。8.（6分）考虑无向网G：(1)给出邻接表表示的存储结构（要求邻接表的每个顶点的邻接链表按结点域升序排列，每一表结点包含所表示的边的权值）。(2分)(2)给出从顶点E开始的广度优先顶点访问序列（根据邻接表进行遍历）。（2分）(3)根据普里姆（Prim）算法，从结点B开始，画出无向图G的最小生成树。(2分)9.（5分）假设有一组记录的关键字为3,4,8,2,6,
6、1,9,5,7，请给出利用堆排序的方法建立初始大顶堆的过程。三.程序设计题（共25分）1.（12分）给定一棵二叉链表表示的二叉排序树T，输入整数k（k一定存在于T），编写程序输出值为k的结点所在的层次（设根结点处于第1层），并求出其平衡因子，即值为k的结点的左右子树高度差。2.（13分）对于邻接表表示的有向图G，编写程序完成如下任务：（1）写出邻接表的存储结构定义。（3分）（2）对于G中任意的两个顶点Vi和Vj，如果同时存在和两条有向边，则将这两条边删除。（10分）第二部分C+(共75分)一、选择题（单选，每小题2分，共20分）1.以下非法的常量表示是（）。A)E-2B)Hqu_cstC)0x
7、f5D)x412.表达式(!-1&2+34)的值是（）。A)-1B)0C)1D)23.表达式(-10?1:2,3)的值为（）。A）-1B）2C）3D）14.若已定义:#defineM3+4,则表达式M*2的值为（）。A)14B)6C)8D)115.以下不正确的语句组是（）。A）chars10=Hqu;B）char*s=Hqu;C）chars10;s=Hqu;D）chars=Hqu;6.下面程序的运行结果为（）。A)a2b3c4d5eB)aC)2D)编译出错7.下面程序的运行结果为（）。A)4B)5C)3D)68.下面程序段运行后，x的值为（）。inta=1,2,3,4,5,6,7,8,i,x=
8、1,*p;p=&a1;for(i=0;i3;i+)x*=*(p+i);A)1B)24C)6D)1209.以下叙述错误的是（）。A)构造函数可以重载B)派生类成员函数可以访问基类的公有成员C)析构函数可以重载D)类的友元函数不是类的成员函数10.下面程序的运行结果是（）。A)constructing.destructing.B)constructing.C)destructing.D)constructing.constructing.destructing.destructing.二、阅读程序，回答相关问题（共30分）1.写出以下程序的运行结果。（7分）四、编程题(共25分)1.编写程序，将一个NN矩阵中主对角线的元素和反对角线的元素对换（10分）。如：