1、 第 1 页 共 10 页 华侨大学 2016 年硕士研究生入学考试专业课试卷（答案必须写在答题纸上）招生专业 计算机技术（专业学位）科目名称 数据结构与 C+科目代码 850 第第一一部分部分 数据结构数据结构 （总分（总分 7575 分）分）一一.单项选择题（每题单项选择题（每题 1.51.5 分，共分，共 1212 分）分）1.下列关于顺序存储结构的叙述哪一个是错误的？（）A存储密度大 B插入操作不方便 C不可随机访问任意结点 D存储单元的地址是连续的 2.已知二叉树的空指针域是 m，则该二叉树的结点个数是（）。A.m B.m-1 C.m+1 D.m+2 3.一棵树高为 H 的完全二叉树
2、的节点总数至少是（）。A.2H-2 B.2H-1-1 C.2H-1 D.无法确定 4.在一个双向链表中，若要删除指针 p 所指的结点，则执行()。A.free(p);p-prior-next=p-next;p-next-prior=p-prior;B.p-next-prior=p-prior;free(p);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
3、 的结点个数分别为 2，4，1，则 T 中的叶子数为（）。A5 B6 C7 D8 6.右图给出由 7 个顶点组成的无向图。从顶点4 出发，对它进行深度优先遍历得到的顶点序列不可能是()。A4127635 B4513276 第 2 页 共 10 页 C4135276 D4521376 7.若用线性探测法将关键字相同的 m 个记录存入哈希表中，总共至少需要进行()次探测。A m B.m+1 C.m(m+1)/2 D.1+m(m+1)/2 8.下列顶点序列中，哪一个不是不是右边的有向无环图的拓扑有序序列（）。A.ADBECF B.ADBEFC C.ADEFCB D.DABECF 二二.问答题（共问答
4、题（共 3838 分）分）1.（2 分）三维数组 a547（下标从 0 开始计，a 有 5*4*7 个元素），每个元素的长度是 2，则 a234的地址是 。(设 a000的地址是 1000,数据以行为主方式存储)。2.（4 分）考虑如下程序段，int i,j,temp=0;for(i=0;i3 for(j=i;jn;j+)if(tempi)temp+;return temp;（1）第二个 for 语句中的“jn”判断语句的执行频度是 。（2 分）（2）语句“temp+”的执行频度是 。（2 分）3.（2 分）有一个时间复杂度为O(n2)的算法，在有 30 个元素的数组上运行需耗时 4 毫秒，则
5、在 300 个元素的数组上运行大约需要 毫秒。4.（7 分）已知一颗二叉树的先序遍历结点序列是 ABDGCEHIF，中序遍历结点序列是BGDAHEICF，回答如下问题：(1)画出这棵二叉树（3 分）(2)这棵二叉树的后序遍历结点序列是 （2 分）(3)在(1)中画出的二叉树中添加后序线索，构成后序线索二叉树（2 分）5.（5 分）设哈希表的地址范围为 013，哈希函数为：H(K)=K MOD 11,K 为关键字，ABCDEF 第 3 页 共 10 页 用线性探测再散列法处理冲突，输入关键字序列:(11,20,31,17,15,21,25,13,2,9)，造出哈希表，试回答下列问题：(1)画出哈
6、希表示意图（3 分）(2)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。（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）算法，从结点
7、 B 开始，画出无向图 G 的最小生成树。(2 分)9.（5 分）假设有一组记录的关键字为3,4,8,2,6,1,9,5,7，请给出利用堆排序的方法建立初始大顶堆的过程。三三.程序设计题（共程序设计题（共 2525 分）分）1.（12 分）给定一棵二叉链表表示的二叉排序树 T，输入整数 k（k 一定存在于 T），编写程序输出值为 k 的结点所在的层次（设根结点处于第 1 层），并求出其平衡因子，即值为 k 的结点的左右子树高度差。2.（13 分）对于邻接表表示的有向图 G，编写程序完成如下任务：34 1 4352 2 6 3 A B C D F G E 无向网无向网 G A AB BC CG
8、GH HI IJ JK KL LM MO OP PN N 第 4 页 共 10 页（1）写出邻接表的存储结构定义。（3 分）（2）对于 G 中任意的两个顶点 Vi 和 Vj，如果同时存在和两条有向边，则将这两条边删除。（10 分）第二部分第二部分 C+(C+(共共 7575 分分)一、选择题一、选择题（单选，每（单选，每小小题题 2 分，分，共共 20 分）分）1.以下非法的常量表示是（）。A)E-2 B)Hqu_cst C)0 xf5 D)x41 2.表达式(!-1&2+34)的值是（）。A)-1 B)0 C)1 D)2 3.表达式(-10?1:2,3)的值为（）。A）-1 B）2 C）3
9、D）1 4.若已定义:#define M 3+4,则表达式 M*2 的值为（）。A)14 B)6 C)8 D)11 5.以下不正确的语句组是（）。A）char s10=Hqu;B）char*s=Hqu;C）char s10;s=Hqu;D）char s=Hqu;6.下面程序的运行结果为（）。A)a2b3c4d5e B)a C)2 D)编译出错#include using namespace std;void main(void)char s=1a2b3c4d5e,*p=s+2;coutp-1endl;7.下面程序的运行结果为（）。A)4 B)5 C)3 D)6#include using na
10、mespace std;int f(char*s)char*p=s;while(*p)p+;return(p-s);void main(void)第 5 页 共 10 页 char*s=abcd;coutf(s)endl;8.下面程序段运行后，x 的值为（）。int a=1,2,3,4,5,6,7,8,i,x=1,*p;p=&a1;for(i=0;i3;i+)x*=*(p+i);A)1 B)24 C)6 D)120 9.以下叙述错误的是（）。A)构造函数可以重载 B)派生类成员函数可以访问基类的公有成员 C)析构函数可以重载 D)类的友元函数不是类的成员函数 10.下面程序的运行结果是（）。A
11、)constructing.destructing.B)constructing.C)destructing.D)constructing.constructing.destructing.destructing.#include using namespace std;class A public:A()coutconstructing.endl;A()coutdestructing.endl;void main(void)A a2;二、阅读二、阅读程序程序，回答相关问题回答相关问题（共（共 30 分）分）1.写出以下程序的运行结果。（7 分）#include using namespace
12、 std;第 6 页 共 10 页 void fun(int a,int n)int pass,k,lenofsort,temp;lenofsort=n/2;for(pass=1;pass=lenofsort-1;pass+)for(k=1;kak+2)temp=ak;ak=ak+2;ak+2=temp;void main(void)int b=-11,22,-33,44,-55,-66,77,-88,99,k;fun(b,sizeof(b)/sizeof(int);for(k=0;ksizeof(b)/sizeof(int);k+)coutbk;coutendl;2.写出下面程序的运行结果。
13、（7 分）#include using namespace std;int BiSearch(int a,int n,int x,int&count)count=1;int low=0,high=n-1,mid;while(lowamid)low=mid+1;else high=mid-1;return-1;void main(void)int b=-11,22,33,44,55,66,77,88,y=88,num;第 7 页 共 10 页 if(BiSearch(b,sizeof(b)/sizeof(int),y,num)=-1)coutNo found!endl;coutThe count
14、 of searching is numendl;else couty is in bBiSearch(b,sizeof(b)/sizeof(int),y,num)endl;coutThe count of searching is numendl;3.下面程序中函数 void HeadInsert(char s1,char s2)的功能：将字符串 s2 插入到字符串 s1 的最前面。在一对/*/之间补充程序，并给出程序的运行结果。（8 分）#include using namespace std;#include void HeadInsert(char s1,char s2)int i,l
15、enofs1=strlen(s1),lenofs2=strlen(s2);for(i=lenofs2;i=0;i-)s1/*/(1)/*/=s1i;for(i=0;i=lenofs2-1;i+)s1i=/*/(2)/*/;void main(void)char str1200=abcd,str2100=lmn;HeadInsert(str1,str2);coutstr1:str1endl;4.下面程序中，类 student 是类 person 的派生类，在一对/*/之间补充程序，并写出程序的运行结果。（8 分）#include#include using namespace std;class
16、 person protected:char name20;int age;public:person(char*n,int a)第 8 页 共 10 页 coutperson n being constructed!endl;age=a;strcpy(name,n);person()coutperson name being destructed!endl;class student:public person int score;public:student(char*n,int a,int s):/*/(3)/*/score=a;coutstudent n being construct
17、ed!endl;student()/*/(4)/*/;void main(void)person p(zhangjun,18);student s(Lihua,19,89);四四、编程题、编程题(共共 25 分分)1.编写程序，将一个 NN 矩阵中主对角线的元素和反对角线的元素对换（10 分）。如：若 A=6543210987654321 ,则对换后 A=3546201986751324 2.请补充完成下面带头结点的单链表类 LinkList 中指定的 2 个成员函数的定义。（15 分）#include using namespace std;第 9 页 共 10 页 struct Node
18、/单链表中的结点类型 int data;/假设表中元素类型为 int Node*next;class LinkList/带头结点的单链表类的定义 Node*head,*tail;/head 为指向头结点的指针，tail 为指向链表中最后一个/结点的指针 int length;public:LinkList(int data,int n)/补充完成该构造函数的定义-7 分/建立一个由 n 个元素（data0-datan-1）构成的带头结点的单链表 （1 1）?/LinkList LinkList()/建立一个空的带头结点的单链表 coutconstruct an empty linked lis
19、t.next=NULL;length=0;LinkList(LinkList&list)/补充完成该拷贝构造函数的定义-8 分 （2 2）?/LinkList void Print(void)/输出链表中的各元素值 coutThe content of the list:;if(length=0)coutEmpty linked list!next;while(t!=NULL)coutdatanext;coutendl;/Print 第 10 页 共 10 页 LinkList()/类的析构函数定义 coutDestrcting.lengthnext!=NULL)/逐个删除各个结点，并释放其空间 t=head-next;head-next=t-next;/删除当前剩余链表中的第一个结点 delete t;length-;delete head;/最后销毁单链表的头结点 /else/LinkList ;/类 LinkList 定义结束
