华侨大学-850数据结构与C++【2013】考研真题
免费
2023-06-21
999+
145.3KB
10 页
侵权投诉
共 10 页 第 1 页
1
华侨大学 2013 年硕士研究生入学考试专业课试卷
（答案必须写在答题纸上）
招生专业 计算机技术
科目名称 数据结构与 C++ 科目代码 850
第一部分 数据结构（共 75 分）
一、单项选择题（每小题 2分，共 24 分）
1.执行下面程序段时，则 S 语句的语句频度是（）。
for（int i =1;i<=n;i++）
for (int j =1; j <=i ; j++)
S;
A） n2 B） n2/2 C） n(n+1) D） n(n+1)/2
2. 在一个不带头结点的单链表 HL 中，若要向表头插入一个由指针p 指向的结点，则执行( )。
A）HL=p；p->next=HL； B）p->next=HL；HL=p；
C）p->next=HL；p=HL； D）p->next=HL->next；HL->next=p；
3.设栈 S 和队列 Q 的初始状态皆为空，元素 a1，a2，a3，a4，a5 和 a6 依次通过一个栈，
一个元素出栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3，a5，a4，a6，a2，a1 则栈
S 至少应该容纳（）个元素。
A）3 B）4 C）5 D）6
4. 一棵树高为 K（K≥1）的完全二叉树至少有（）个结点。
A）2k-1 B）2k C）2k+1 D）log2k
5.由权值分别为 3,8,6,2,5 的叶子结点生成一棵赫夫曼树，它的带权路径长度为（）。
A） 24 B）48 C）72 D）53
6. 假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示，则删除与某个顶点 vi 相关的边
的时间复杂度是（）。
A）O（n） B）O（e） C）O（n+e） D）O（n*e）
7. 图的深度优先遍历类似于树的（）。
A）先序遍历 B）中序遍历 C）后序遍历 D）层次遍历
8. 对一棵二叉排序树进行（）遍历，可以得到该二叉树的所有结点按值从小到大排列的序
列。
A）前序 B）后序 C）中序 D）按层次
9.设散列表长 m=14,散列函数 H（K）=K％11，已知表中已有 4 个结点：
r(15)=4; r(38)=5;
r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为 49 的结点地
址是（）。
A）8 B）3 C）5 D）9
10. 用某种排序方法对关键字序列（23，72，21，47，15，27，59，35，20）进行排序时，
共 10 页 第 2 页
2
前两趟的结果情况如下：
15，72，21，47，23，27，59，35，20
15，20，21，47，23，27，59，35，72
则所采用的排序方法是（）。
A）选择排序 B）起泡排序 C）归并排序 D）快速排序
11．n 个顶点的无向图中含有边的数目最多为（）。
A）n-1 B）n C）n(n-1)/2 D） n(n-1)
12.由权值分别为 11，8，6，2，5 的叶子结点生成一棵赫夫曼树，它的带权路径长度 WPL
为（）。
A）24 B）71 C）48 D）53
二、简答与应用题（30 分）
1. （8 分）假设链队列带头结点，其出队操作如下：
Status DnQueue_L(LinkQueue &Q ,ElemType &e){
//链队列 Q 出队，出队元素赋值给 e 中
if（Q.front = = Q.rear） return ERROR;
p = Q.front->next; e = p->data;
Q.front ->next = p->next;
if(Q.rear = = p) Q.rear = Q.front; //问题（1）
free(p);
return OK;
}// DeQueue_L
（1） （4 分）此处的 if 语句起什么作用（含义）？
对出队前若队列里只有一个结点的情况处理，此时需要修改 Q.rear 值。
（2） （4 分）假设链队列不带头结点，请补充下面的代码，以实现类似的链队列出队操作。
Status DnQueue_L(LinkQueue &Q ,ElemType &e){
//不带头结点的链队列 Q 出队，出队元素赋值给 e 中
if（Q.front==NULL） return ERROR; //空队列
if（Q.front==Q.rear）{ //只有一个结点的处理
e=Q.front.data;
p=Q.front;
______ (1) _____;
free(p); return OK;
}
p = Q.front; e = p->data;
______（2） ;
;
free(p); return OK;
共 10 页 第 3 页
3
}// DeQueue_L
2. （8 分）请对下图所示的二叉树进行中序线索化，为每个空指针建立相应的前驱和后继，
请用虚线箭头在图中画出结果。
3. （8分）考虑无向网G：
（1） （2分）给出邻接表存储结构（要求邻接表的每个顶点的邻接链表按结点域升序排列，
每一表结点包含所表示的边的权值）。
（2） （2分）请给出从顶点A开始的深度优先顶点访问序列（要求根据邻接表进行遍历）。
（3） （4分）根据克鲁斯卡尔（Kruscal）算法，画出无向图G的最小生成树。
4．（6 分）有一组关键字序列{26,38,73,21,54,35,167,32,7,223,52}，试用哈希函数
H(key)=key mod 13 和链地址（拉链）法解决冲突方法构造这组关键字的哈希表（设哈希表
的长度为 15）。
三、算法设计题（21 分）
1．（10 分）设单向链表的类型定义如下：
typedef int ElemType; //设表中元素类型为 int
typedef struct LNode{
ElemType data;
Node* next;
}*LinkList;
4
1
4
5
2
2
6
A
B
C
D
F
G
E
无向网 G
3
标签： #华侨大学
摘要：
展开>>
收起<<
共10页第1页1华侨大学2013年硕士研究生入学考试专业课试卷（答案必须写在答题纸上）招生专业计算机技术科目名称数据结构与C++科目代码850第一部分数据结构（共75分）一、单项选择题（每小题2分，共24分）1.执行下面程序段时，则S语句的语句频度是（）。for（inti=1;inext=HL；HL=p；C）p->next=HL；p=HL；D）p->next=HL->next；HL->next=p；3.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳（）...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
