华侨大学-850数据结构与C++【2015】考研真题
免费
2023-06-21
999+
175.21KB
10 页
侵权投诉
第 1 共 10
华侨大学 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. 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 的结点个数分别 2，4，1，则 T中的叶子数
。
A．5 B．6 C．7
D．8
6. 右图给出由 7 个点组成的无向图。从点
4 出发，对它进行深度优先遍历得到的点
序列不可能是( )。
A．4127635 B．4513276
第 2 共 10
C．4135276 D．4521376
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
二. 问答共 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 关键，
AB
C D
E F
第 3 共 10
用线性探测再散列法处理冲突，输入关键序列: (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分请画出如森林的孩子弟法表示的二叉树。
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 分
1. 12 分给定一棵二叉链表表示的二叉排序树 T，输入整数 kk一定在于 T， 编
写程序输出值 k的结点所在的层次根结点处于第 1层，并求出其平衡因子，
即值 k的结点的左右子树高度差。
2. 13 分对于邻接表表示的有向图 G，编写程序完成如任：
3
4
1
4
3
5
2
2
6
3
A
B
C
D
F
G
E
无向网 G
A
B C
G
H
I J K
L
MO
P
N
标签： #华侨大学
摘要：
展开>>
收起<<
第1N共10N华侨大学2016年硕士研究生入学考试专业课试卷c答案必须写在答题纸上d招生专业计算机技术g专业学位h科目名称数据结构与C科目代码850第一部分数据结构总分75分一单N选择N每N15分共12分1列关于N序储结构的叙述哪一个是错误的？A储密度大B插入操作不方便C不可随机A问任意结点D储单s的地址是连续的2已知二叉树的空指针域是m则该二叉树的结点个数是。AmBm1Cm1Dm23一棵树高jH的完全二叉树的节点总数至少是。A2H2B2H11C2H1D无法确定4在一个向链表中若要删除指针p所指的结点则执行。AfreepppriornextpnextpnextpriorppriorBpnext...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
