桂林电子科技大学-910数据结构A【2017】考研真题
2023-06-20
999+
167.5KB
4 页
侵权投诉
桂林电子科技大学
2017 年硕士研究生统一入学考试试题
科目代码:910 科目名称:数据结构 A卷
注意：答案必须全部写在答题纸上，写在试题上无效；答案要标注题号，答题纸要填写姓名和考号，并标注页
码与总页数；交卷时，将答题纸与试题一起装入试卷袋，密封签字。
一、 选择题（20 分，共 10 小题，每小题 2 分）
1. 设数据结构 B=<K，R>，其中 K={a，b，c，d}，R={<d，c>，<c，b>，<b，d>, <b，a>}，则 B
是（ ）。
A．线性结构 B．树型结构 C．图型结构 D．索引结构
2. 若线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则下面最适合
的存储结构是（ ）。
A．带头指针的单链表 B．带头指针的双链表
C．带头指针的单循环链表 D．带尾指针的单循环链表
3.图1中，（a）是结点结构，（b）是双向链表片段，若要删除（b）中 p指针指向结点的后继结
点，则正确的操作是（ ）。
图1 双向链表
A．p->rlink->data=p->data; p->llink->rlink=p->rlink; p->rlink->llink=p->llink; free(p);
B．p->rlink->data=p->data; p->rlink=p->rlink->llink; p->rlink->rlink->llink=p; free(p);
C．p->rlink=p->rlink->llink; p->rlink->rlink->llink=p; free(p->rlink);
D．p->rlink->rlink->llink=p; p->rlink=p->rlink->llink; free(p->rlink);
4. 设栈 S和队列 Q的初始状态为空，元素 a，b，c，d ，e，f依次进栈，一个元素出栈后即进入
队列 Q。如果 6个元素出队列的顺序是 b，d，c，f，e，a，则栈 S的容量至少应该是（ ）。
A．2 B．3 C．4 D．5
5．给定有序表{ 16，23，32，45，51，62，73，79，80 }，若采用二分检索法查找关键码值为 62
的数据元素，（ ）次比较后查找成功。
A．1 B．2 C．3 D．4
6. 给定一棵具有 n个结点的二叉树，在不违背二叉树定义以及不改变根结点的基础上，向二叉树
中任意一个可插入结点的位置插入一个新的结点，则生成的新二叉树有（ ）。种可能。
A．n-1 B．n C．n+1 D．2n
7. 下列排序方法中，哪一种方法的比较次数与记录的初始排列状态无关？（ ）
A、直接插入排序 B、冒泡排序 C、快速排序 D、直接选择排序
8. 若让一个具有 n个顶点的有向图是强连通图，则至少需要（ ）条狐。
A．n B．n+1 C．2n D．n(n-1)
9．对任何一棵非空二叉树 T，设 N0、N1 和N2 分别是度数为 0、1、2的结点数，则下列等式中成
立的是（ ）。
第 1 页 共 4 页
a b c
llink rlinkdata
p
（a）
（b）
c
A. N0=N1+1 B. N0=N1+N2 C. N0=N2+1 D. N0=2N2+1
10．对二叉排序树进行（ ）遍历可将其元素进行升序排序。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 不确定
二、请给出下面算法的功能描述（10 分）
struct Node;
typedef struct Node* PNode;
struct Node{
DataType info;
PNode link;
};
typedef struct Node * LinkList;
int Test(LinkList list, DataType value)
{
LinkList first=list;
while( ( first!=null ) && (first->link!=null))
{
LinkList tmp=first->link;
if ( tmp->info==value )
{
first->link=tmp->link;
free tmp;
}
else
first=first->link;
}
}
三 、 设 哈 希函 数 H （k）=（3 * k ） mod 11 ， 散 列 地 址 空间 为 0 ～10 。 给定 关 键 字 序 列
（35，13，49，24，62，21，14，81，12）。（共 10 分）
（1）若采用拉链法解决冲突，请构造哈希表。（6分）
（2） 请基于（1）的结果，给出等概率情况下查找成功时的平均查找长度。（4分）
四、请证明：任意一棵具有 N个结点的满二叉树（N>0）的叶子结点数目为（N+1）/2。（10 分）
五、给出一组排序码：56，32，65，24，16，9，43，39，若对其进行堆排序（按升序排列）：
（共 10 分）
（1）请给出构建的大根堆（6分）
（2）请给出前 3趟堆排序，每一趟排序后堆的结果。（4分）
六、设一数列的输入顺序为 12345，若采用栈结构，并以 A 和 D 分别表示入栈和出栈操作，试
问：能否得到下面的输出顺序，如果能，给出合法的入栈和出栈的操作顺序；如果不能解释为什
第 2 页 共 4 页
摘要：
展开>>
收起<<
桂林电子科技大学2017年硕士研究生统一入学考试试题科目代码:910科目名称:数据结构A卷注意：答案必须全部写在答题纸上，写在试题上无效；答案要标注题号，答题纸要填写姓名和考号，并标注页码与总页数；交卷时，将答题纸与试题一起装入试卷袋，密封签字。一、选择题（20分，共10小题，每小题2分）1.设数据结构B=，其中K={a，b，c，d}，R={，，
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
