2018年福建华侨大学数据结构考研真题.doc

发布时间：2022-09-18 发布人：admin 分类：说明书资料大小：0.06M 资料格式：doc 举报版权申诉

第1页 / 共6页

第2页 / 共6页

第3页 / 共6页

第4页 / 共6页

第5页 / 共6页

第6页 / 共6页

A) A) 0 ,0 B)1,0 C)0,1 D

A) 2 B) 5 C)3 D) 4

2018 年福建华侨大学数据结构考研真题第一部分数据结构 (共 75 分) 一. 单项选择题（每题 2 分，共 10 分） 1. 在一个单链表中，将指针 q 所指结点作为指针 p 所指结点的后继进行插入的操作是 ( )。 A. q->next=p; C. q->next=p; p->next=q; p=p->next; B. q->next=p->next ; D. p->next=q; q->next=p; p->next=q; 2. 在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 2，则叶子结点个数为( A．4 )。 B．5 C．6 D．7 3. 对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。 A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序 4. 设有一个电文，其中有 5 个不同字符，每个字符的出现次数分别为 5，3，4，2，6，那么将这个电文进行哈夫曼编码后得到的电文有多少个二进制位？（）。 A.55 B．60 C．65 D．70 5. 后缀算数表达式串“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)表示顶点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和线性探测再散列处理冲突的方法在地址空间 A[0..13]中构造哈希表，画出地址空间A[0..13]中每个位置存放记录的关键字，如果没

有存放记录则留空。并计算等概率情况下，查找成功的平均查找长度。 4. （10分）设有一个关键字输入序列（4，5，6，1，2，3），试从空树开始构造平衡二叉排序树，画出每加入一个结点后二叉树的形态，若发生不平衡，请指出平衡调整的类型并画出调整结果。然后计算在等概率情况下，查找成功的平均查找长度ASL。三．程序设计题（共 25 分） 1. （10 分）写一个算法将结点数据降序排列的单向链表中的重复结点删除。 2. （15 分）已知一无向图 G 以邻接表作为存储结构，请（1）写出邻接表存储结构的定义.（2 分）（2）编写程序输出图中的所有简单环路（简单环路是除了第一个和最后一个结点相同外，其余结点均不同的一条路径）。（13 分）第二部分 C++ (共 75 分) 一. 选择题（单选，每小题 2 分，共 20 分） 1. 以下程序的运行结果为（）。 #include using namespace std; void main(void){ int i=1,j=0; if(--i&&j++) cout< using namespace std; void main(void){ char s[][10]={"123abc","abcd"}; cout<

using namespace std; void main(void){ int a[][3]={1,2,3,4,5,6},(*p)[3]=a; cout<<*(*p+1)< using namespace std; void main(void){ int *p=new int[10],k; for(k=0;k<10;k++) p[k]=2*k-1; cout<<*p++< using namespace std; class A{ public: virtual void show(){ cout<<"in class A"<show(); }

A）in class A B）in class A in class B C) in class B in class A D) in class B 二. 阅读下面程序，给出程序的运行结果（每小题 8 分，共 24 分） 1. #include using namespace std; #define N 4 void main(void){ int a[N][N]={1,2,0,4,5,0,7,8,0,0,1,2,3,0,5,1},i,j,t; cout<<"original a:"< #include using namespace std; class Student{ int num; char name[20]; static int count; public: Student(char* s,int n){

cout<<"constrcting "<

三. 编程题（共 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 分）

分享到：

赞收藏

资料库

2018年福建华侨大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料