华侨大学2011年硕士研究生入学考试专业课试卷

Size: px

Start display at page:

Download "华侨大学2011年硕士研究生入学考试专业课试卷"

盆衫能
5 years ago
Views:

1 华侨大学 2016 年硕士研究生入学考试专业课试卷 ( 答案必须写在答题纸上 ) 招生专业计算机技术 ( 专业学位 ) 科目名称数据结构与 C++ 科目代码 850 第一部分数据结构 ( 总分 75 分 ) 一. 单项选择题 ( 每题 1.5 分, 共 12 分 ) 1. 下列关于顺序存储结构的叙述哪一个是错误的?( ) A. 存储密度大 B. 插入操作不方便 C. 不可随机访问任意结点 D. 存储单元的地址是连续的 2. 已知二叉树的空指针域是 m, 则该二叉树的结点个数是 ( ) A. m B. m-1 C. m+1 D. m+2 3. 一棵树高为 H 的完全二叉树的节点总数至少是 ( ) A. 2 H-2 B. 2 H-1-1 C. 2 H-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 的结点个数分别为 2,4,1, 则 T 中的叶子数为 ( ) A.5 B.6 C.7 D.8 6. 右图给出由 7 个顶点组成的无向图从顶点 4 出发, 对它进行深度优先遍历得到的顶点序列不可能是 ( ) A B 第 1 页共 10 页

2 C D 若用线性探测法将关键字相同的 m 个记录存入哈希表中, 总共至少需要进行 ( ) 次探测 A. m B. m+1 C. m(m+1)/2 D.1+m(m+1)/2 8. 下列顶点序列中, 哪一个不是右边的有向无环图的拓扑有序 A B 序列 ( ) A. ADBECF B. ADBEFC C D C. ADEFCB D. DABECF E F 二. 问答题 ( 共 38 分 ) 1. (2 分 ) 三维数组 a[5][4][7]( 下标从 0 开始计,a 有 5*4*7 个元素 ), 每个元素的长度是 2, 则 a[2][3][4] 的地址是 ( 设 a[0][0][0] 的地址是 1000, 数据以行为主方式存储 ) 2. (4 分 ) 考虑如下程序段, int i, j, temp=0; for(i=0; i<n; i++) //n>3 for(j=i; j<n; j++) if(temp<i) temp++; return temp; (1) 第二个 for 语句中的 j<n 判断语句的执行频度是 ( 2 分 ) (2) 语句 temp++ 的执行频度是 ( 2 分 ) 3. (2 分 ) 有一个时间复杂度为 O(n 2 ) 的算法, 在有 30 个元素的数组上运行需耗时 4 毫秒, 则在 300 个元素的数组上运行大约需要毫秒 4. (7 分 ) 已知一颗二叉树的先序遍历结点序列是 ABDGCEHIF, 中序遍历结点序列是 BGDAHEICF, 回答如下问题 : (1) 画出这棵二叉树 (3 分 ) (2) 这棵二叉树的后序遍历结点序列是 (2 分 ) (3) 在 (1) 中画出的二叉树中添加后序线索, 构成后序线索二叉树 (2 分 ) 5. (5 分 ) 设哈希表的地址范围为 0~13, 哈希函数为 :H (K)=K MOD 11, K 为关键字, 第 2 页共 10 页

3 用线性探测再散列法处理冲突, 输入关键字序列 : (11,20,31,17,15,21,25,13,2,9), 造出哈希表, 试回答下列问题 : (1) 画出哈希表示意图 (3 分 ) (2) 假定每个关键字的查找概率相等, 求查找成功时的平均查找长度 (2 分 ) 6. (5 分 ) 有一组键值 20,50,13,38,40,23,11,32,20, 请采用希尔排序方法由小到大进行排序 ( 增量 d[1]=5,d[2]=3,d[3]=1), 请写出每趟的排序结果 7. (2 分 ) 请画出如下森林的孩子兄弟法表示的二叉树 B A 8. (6 分 ) 考虑无向网 G: (1) 给出邻接表表示的存储结构 ( 要求邻接表的每个顶点的邻接链表按结点域升序排列, 每一表结点包含所表示的边的权值 ) (2 分 ) (2) 给出从顶点 E 开始的广度优先顶点访问序列 ( 根据邻接表进行遍历 ) (2 分 ) (3) 根据普里姆 (Prim) 算法, 从结点 B 开始, 画出无向图 G 的最小生成树 (2 分 ) 9. (5 分 ) 假设有一组记录的关键字为 {3, 4, 8, 2, 6, 1, 9, 5, 7, 请给出利用堆排序的方法建立初始大顶堆的过程三. 程序设计题 ( 共 25 分 ) C 1. (12 分 ) 给定一棵二叉链表表示的二叉排序树 T, 输入整数 k(k 一定存在于 T), 编写程序输出值为 k 的结点所在的层次 ( 设根结点处于第 1 层 ), 并求出其平衡因子, 即值为 k 的结点的左右子树高度差 1 B F 3 2. (13 分 ) 对于邻接表表示的有向图 G, 编写程序完成如下任务 : 2 6 G H I J K E A C 无向网 G 3 G 2 第 3 页共 10 页 4 D M P L N O

4 (1) 写出邻接表的存储结构定义 (3 分 ) (2) 对于 G 中任意的两个顶点 Vi 和 Vj, 如果同时存在 <Vi,Vj> 和 <Vj,Vi> 两条有向边, 则将这两条边删除 (10 分 ) 第二部分 C++ ( 共 75 分 ) 一选择题 ( 单选, 每小题 2 分, 共 20 分 ) 1. 以下非法的常量表示是 ( ) A)E-2 B) "Hqu_cst" C)0xf5 D) '\x41' 2. 表达式 (!-1&&2+3>4) 的值是 ( ) A) -1 B) 0 C) 1 D) 2 3. 表达式 (-1>0?1:2,3) 的值为 ( ) A)-1 B)2 C)3 D)1 4. 若已定义 :#define M 3+4, 则表达式 M*2 的值为 ( ) A) 14 B) 6 C) 8 D) 以下不正确的语句组是 ( ) A)char s[10]="hqu"; B)char* s="hqu"; C)char s[10]; s="hqu"; D)char s[]="hqu"; 6. 下面程序的运行结果为 ( ) A) a2b3c4d5e B) a C) 2 D) 编译出错 char s[]="1a2b3c4d5e",*p=s+2; cout<<p[-1]<<endl; 7. 下面程序的运行结果为 ( ) A) 4 B) 5 C) 3 D) 6 int f(char *s) { char *p=s; while(*p) p++; return(p-s); 第 4 页共 10 页

5 char *s="abcd"; cout<<f(s)<<endl; 8. 下面程序段运行后,x 的值为 ( ) int a[]={1,2,3,4,5,6,7,8,i,x=1,*p; p=&a[1]; for(i=0;i<3;i++) x*=*(p+i); A) 1 B) 24 C) 6 D) 以下叙述错误的是 ( ) A) 构造函数可以重载 B) 派生类成员函数可以访问基类的公有成员 C) 析构函数可以重载 D) 类的友元函数不是类的成员函数 10. 下面程序的运行结果是 ( ) A) constructing... destructing... B) constructing... C) destructing... D) constructing... constructing... destructing... destructing... #include <iostream> class A{ public: A(){ cout<<"constructing..."<<endl; ~A(){cout<<"destructing..."<<endl; ; A a[2]; 二阅读程序, 回答相关问题 ( 共 30 分 ) 1. 写出以下程序的运行结果 (7 分 ) 第 5 页共 10 页

6 void fun(int a[],int n){ int pass,k,lenofsort,temp; lenofsort=n/2; for(pass=1;pass<=lenofsort-1;pass++) for(k=1;k<=n-pass-1;k+=2) if(a[k]>a[k+2]){ temp=a[k]; a[k]=a[k+2]; a[k+2]=temp; int b[]={-11,22,-33,44,-55,-66,77,-88,99,k; fun(b,sizeof(b)/sizeof(int)); for(k=0;k<sizeof(b)/sizeof(int);k++) cout<<b[k]<<' '; cout<<endl; 2. 写出下面程序的运行结果 (7 分 ) int BiSearch(int a[],int n,int x,int& count){ count=1; int low=0,high=n-1,mid; while(low<=high){ mid=(low+high)/2; if( x==a[mid] ) return mid; else{ count++; if(x>a[mid]) low=mid+1; else high=mid-1; return -1; int b[]={-11,22,33,44,55,66,77,88,y=88,num; 第 6 页共 10 页

7 if(bisearch(b,sizeof(b)/sizeof(int),y,num)==-1){ cout<<"no found!"<<endl; cout<<"the count of searching is "<<num<<endl; else{ cout<<y<<" is in b["<<bisearch(b,sizeof(b)/sizeof(int),y,num)<<"]" <<endl; cout<<"the count of searching is "<<num<<endl; 3. 下面程序中函数 void HeadInsert(char s1[],char s2[]) 的功能 : 将字符串 s2 插入到字符串 s1 的最前面在一对 /**/ 之间补充程序, 并给出程序的运行结果 ( 8 分 ) #include <iostream> #include<cstring> void HeadInsert(char s1[],char s2[]){ int i,lenofs1=strlen(s1),lenofs2=strlen(s2); for(i=lenofs2;i>=0;i--) s1[/**/ (1) /**/]=s1[i]; for(i=0;i<=lenofs2-1;i++) s1[i]=/**/ (2) /**/; char str1[200]="abcd",str2[100]="lmn"; HeadInsert(str1,str2); cout<<"str1:"<<str1<<endl; 4. 下面程序中, 类 student 是类 person 的派生类, 在一对 /**/ 之间补充程序, 并写出程序的运行结果 (8 分 ) #include<cstring> class person{ protected: char name[20]; int age; public: person(char *n,int a){ 第 7 页共 10 页

8 cout<<"person "<<n<<" being constructed!"<<endl; age=a; strcpy(name,n); ~person(){ cout<<"person "<<name<<" being destructed!"<<endl; ; class student:public person{ int score; public: student(char *n,int a,int s):/**/ (3) /**/{ score=a; cout<<"student "<<n<<" being constructed!"<<endl; ~student(){ /**/ (4) /**/ ; person p("zhangjun",18); student s("lihua",19,89); 四编程题 ( 共 25 分 ) 1. 编写程序, 将一个 N N 矩阵中主对角线的元素和反对角线的元素对换 (10 分 ) 如 : 若 A= , 则对换后 A= 请补充完成下面带头结点的单链表类 LinkList 中指定的 2 个成员函数的定义 (15 分 ) 第 8 页共 10 页

9 struct Node{ // 单链表中的结点类型 int data; // 假设表中元素类型为 int Node* next; ; class LinkList{ // 带头结点的单链表类的定义 Node* head,*tail; //head 为指向头结点的指针,tail 为指向链表中最后一个 // 结点的指针 int length; public: LinkList(int data[],int n){ // 补充完成该构造函数的定义分 // 建立一个由 n 个元素 (data[0]-data[n-1]) 构成的带头结点的单链表 (1)? //LinkList LinkList(){ // 建立一个空的带头结点的单链表 cout<<"construct an empty linked list..."<<endl; head=tail=new Node; head->next=null; length=0; LinkList(LinkList& list){ // 补充完成该拷贝构造函数的定义 ---8 分 (2)? //LinkList void Print(void){ // 输出链表中的各元素值 cout<<"the content of the list:"; if(length==0) { cout<<"empty linked list!"<<endl; return; Node* t=head->next; while(t!=null){ cout<<t->data<<", "; t=t->next; cout<<endl; //Print 第 9 页共 10 页

10 ~LinkList(){ // 类的析构函数定义 cout<<"destrcting..."<<length<<endl; if(length==0) delete head; // 若为空表, 则销毁头结点 else{ Node *t; while(head->next!=null){ // 逐个删除各个结点, 并释放其空间 t=head->next; head->next=t->next; // 删除当前剩余链表中的第一个结点 delete t; length--; delete head; // 最后销毁单链表的头结点 //else //~LinkList ; // 类 LinkList 定义结束第 10 页共 10 页

华侨大学 2013 年硕士研究生入学考试专业课试卷 ( 答案必须写在答题纸上 ) 招生专业计算机技术科目名称数据结构与 C++ 科目代码 850 第一部分数据结构 ( 共 75 分 ) 一单项选择题 ( 每小题 2 分, 共 24 分 ) 1. 执行下面程序段时, 则 S 语句的语句频度是

华侨大学 2013 年硕士研究生入学考试专业课试卷 ( 答案必须写在答题纸上 ) 招生专业计算机技术科目名称数据结构与 C++ 科目代码 850 第一部分数据结构 ( 共 75 分 ) 一单项选择题 ( 每小题 2 分, 共 24 分 ) 1. 执行下面程序段时, 则 S 语句的语句频度是 () for(int i =1;i