《2018年福建华侨大学数据结构考研真题.doc》由会员分享，可在线阅读，更多相关《2018年福建华侨大学数据结构考研真题.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2018年福建华侨大学数据结构考研真题第一部分 数据结构 (共75分)一. 单项选择题（每题2分，共10分）1. 在一个单链表中，将指针q所指结点作为指针p所指结点的后继进行插入的操作是( )。 A. q-next=p; p-next=q; B. q-next=p-next ; p-next=q; C. q-next=p; p=p-next; D. p-next=q; q-next=p; 2. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为2，则叶子结点个数为()。A4B5C6D73. 对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。A 直接插入 B. 二
2、分法插入 C. 快速排序 D. 归并排序4. 设有一个电文，其中有5个不同字符，每个字符的出现次数分别为5，3，4，2，6，那么将这个电文进行哈夫曼编码后得到的电文有多少个二进制位？（ ）。A.55B60C65D705. 后缀算数表达式串“2 4 * 5 -”的计算结果为( )A. 1 B. 2 C. 3 D. 4二. 问答题（共40分）1. （8分）已知二叉树T的后序遍历序列是DCBFHGEA，中序遍历序列是BDCAFEHG。（1） 画出二叉树T的树形；（4分）（2） 用虚线在T上添加先序线索。（4分）2. （10分）设无向图G包含A、B、C、D、E、F、G 7个顶点，我们用(A, B, 5
3、)表示顶点A和B之间有一条权值为5的无向边。则图G由如下无向边构成：(A,B,2)、(A,D,3)、(A,C,1)、(B,D,2)、(D,C,5)、(E,B,6)、(E,D,1)、(E,C,3)。（1） 画出图G的带权邻接表，要求带权邻接表的每个顶点的邻接链表中表结点的顶点序号按升序排列；（5分）（2） 请基于该邻接表画出普里姆（Prim）算法从顶点A出发得到的最小生成树，请给出生成过程；（5分）3. （12分）已知一组记录的关键字为（15，25，18，5，27，1，39，33，6，17，13，28，23）。按哈希函数H(Key) = Key MOD 13和线性探测再散列处理冲突的方法在地址空
4、间A0.13中构造哈希表，画出地址空间A0.13中每个位置存放记录的关键字，如果没有存放记录则留空。并计算等概率情况下，查找成功的平均查找长度。4. （10分）设有一个关键字输入序列（4，5，6，1，2，3），试从空树开始构造平衡二叉排序树，画出每加入一个结点后二叉树的形态，若发生不平衡，请指出平衡调整的类型并画出调整结果。然后计算在等概率情况下，查找成功的平均查找长度ASL。三程序设计题（共25分）1. （10分）写一个算法将结点数据降序排列的单向链表中的重复结点删除。2. （15分）已知一无向图G以邻接表作为存储结构，请（1）写出邻接表存储结构的定义.（2分）（2）编写程序输出图中的所有简
5、单环路（简单环路是除了第一个和最后一个结点相同外，其余结点均不同的一条路径）。（13分）第二部分 C+ (共75分)一. 选择题（单选，每小题2分，共20分）1. 以下程序的运行结果为（ ）。 #includeusing namespace std;void main(void) int i=1,j=0; if(-i&j+) couti,jendl; else couti,jendl;A) A) 0 ,0 B)1,0 C)0,1 D) 1,12. 若有定义：int i=2,j=5;，表达式(i+,j-)的值为（ ）。 A) 2 B) 5 C)3 D) 43. 下面程序段的执行结果为（ ）。 i
6、nt a25=1,2,-3,4,-5,6,7,8,-9,-10,*p=a1; cout*(p+1)endl; A) -5 B) 6 C)7 D) 84. 以下程序的运行结果为（ ）。 #include using namespace std;void main(void)char s10=123abc,abcd; couts1+1endl;A)abc B)abcd C) 23abc D) bcd5. 下面程序的运行结果为（ ）。 #includeusing namespace std;void main(void)int a3=1,2,3,4,5,6,(*p)3=a;cout*(*p+1)en
7、dl;A） 1 B） 3 C） 2 D） 56. 下面程序的运行结果为（ ）。 #includeusing namespace std;void main(void)int *p=new int10,k;for(k=0;k10;k+) pk=2*k-1;cout*p+endl;A) 1 B) -1 C) 3 D) 07. 下列关于构造函数的描述中,错误的是（ ）。 A) 类中必须含有程序员自定义的构造函数 B) 构造函数可以重载C) 构造函数的参数可以带有默认缺省值 D) 构造函数可以不带参数8. 下列叙述正确的是（ ）。 A) 派生类的对象可以直接访问基类的公有成员B) 运算符可以重载为类的
8、友元函数 C) 派生类的基类只能有一个 D) 类的成员函数不可以直接访问类的私有成员9. 假定Desk为一个类，则该类的拷贝构造函数的声明语句为（ ）。 A) copy Desk&(Desk d); B) Desk*(Desk d);C) Desk(const Desk& d); D) void Desk(copy Desk *d);10. 下面程序的运行结果是（ ）。 #includeusing namespace std;class A public:virtual void show()coutin class Aendl;class B:public Apublic:void show
9、() coutin class Bshow();A） in class A B） in class A in class BC) in class B in class A D) in class B二. 阅读下面程序，给出程序的运行结果（每小题8分，共24分） 1.#includeusing namespace std;#define N 4void main(void)int aNN=1,2,0,4,5,0,7,8,0,0,1,2,3,0,5,1,i,j,t;coutoriginal a:endl; for(i=0;iN;i+)for(j=0;jN;j+)coutaij ;coutendl
10、;for(i=0;i4;i+)for(j=0;ji;j+) t=aij; aij=aji; aji=t;coutupdated a:endl;for(i=0;iN;i+)for(j=0;jN;j+)coutaij ;coutendl;2.#include#include using namespace std;class Student int num; char name20; static int count;public: Student(char* s,int n) coutconstrcting sendl; num=n; strcpy(name,s); count+; Studen
11、t(const Student& s) char temp80=copyof; coutcopy constructing.s.nameendl; num=s.num; strcat(temp,s.name); strcpy(name,temp); count+; void print() coutnum:num,name:nameendl; static int getcount() return count; Student() coutname being destructing.endl; ;int Student:count=0;void main(void)Student s1(Y
12、umei,100102),s2(Liuhua,100203),s3(s1); coutcount=Student:getcount()endl;3.#include#includeusing namespace std;void main(void)char str80=hqu,qinghua,buaa,xmu,nuaa,s80; int k,i=0,j=sizeof(str)/sizeof(char80)-1;while(ij)strcpy(s,stri);strcpy(stri,strj);strcpy(strj,s);i+,j-;for(k=0;ksizeof(str)/sizeof(c
13、har80);k+)coutstrk ;coutendl;三. 编程题（共31分）1. 1. 编写程序，随机输入正整数n,输出它的“逆向数据”。比如，输入的n为1234,则输出4321。（8分）2.2. 定义非递归函数int BiSearch(int a, int n, int x, int& count)，函数的功能：数组a存储有n个已经升序排列的元素，使用二分法查找x在数组a中的位置，若查找成功，返回其所在的下标值，若查找失败，返回-1。参数count存储查找过程中所需要的比较次数。编写完整C+程序，调用该函数。（11分）3.编写程序实现以下功能：（1）定义一个描述学生基本情况的类，数据成员包括学号、姓名、C+成绩、英语成绩、高数成绩等。包括的主要成员函数有：构造函数 输出学生基本信息 求总成绩 求平均成绩。（2）重载输出操作符实现学生类对象的输出。（3）编写main函数，测试以上所要求的各种功能。(12分）