2017年广西桂林电子科技大学数据结构考研真题A卷.doc

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

第1页 / 共5页

2017年广西桂林电子科技大学数据结构考研真题A卷.doc.pdf-第2页.jpg

第2页 / 共5页

2017年广西桂林电子科技大学数据结构考研真题A卷.doc.pdf-第3页.jpg

第3页 / 共5页

2017年广西桂林电子科技大学数据结构考研真题A卷.doc.pdf-第4页.jpg

第4页 / 共5页

2017年广西桂林电子科技大学数据结构考研真题A卷.doc.pdf-第5页.jpg

第5页 / 共5页

文本预览

2017 年广西桂林电子科技大学数据结构考研真题 A 卷一、选择题（20 分，共 10 小题，每小题 2 分） 1. 设数据结构 B=，其中 K={a，b，c，d}，R={，，, }，则 B 是（）。 A．线性结构 B．树型结构 C．图型结构 D．索引结构 2. 若线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则下面最适合的存储结构是（）。 A．带头指针的单链表 B．带头指针的双链表 C．带头指针的单循环链表 D．带尾指针的单循环链表 3.图 1 中，（a）是结点结构，（b）是双向链表片段，若要删除（b）中 p 指针指向结点的后继结点，则正确的操作是（）。 A．p->rlink->data=p->data; p->llink->rlink=p->rlink; p->rlink->llink=p->llink; 图 1 双向链表 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 的结点数，则下列等式中成立的是（）。 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 分别表示入栈和出栈操作，试问：能否得到下面的输出顺序，如果能，给出合法的入栈和出栈的操作顺序；如果不能解释为什么。（共 10 分）（1）能否得到输出顺序为 32514 的序列。（5 分）（2）能否得到输出顺序为 42135 的序列。（5 分）七、已知一棵二叉树的先根序列（A,B,D,E,C,F,G）和中根序列（D,B,E,A,F,G,C）（共 10 分）（1）画出这棵二叉树。（5 分）（2）将（1）得到的二叉树转换为树林。（5 分）八、已知元素个数为 11 的字典，其关键码集合为{10、18、3、4、9、13、15、2、21、7、

8}，试按元素的次序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树。 (10 分) 九、有一份电文中共使用 8 个字符：a、b、c、d、e、f、g、h，它们出现的频率是 5, 29, 7, 8, 14, 23, 3, 11 （共 15 分）（1）试画出对应的哈夫曼树；（5 分）（2）每个字符的哈夫曼编码；（5 分）（3）求带权外部路径长度(WPL)。（5 分）十、已知一个带权图 G 的顶点集 V 和边集 E 分别为： V = { v1，v2，v3，v4，v5}， E ={(v1，v2)，(v1，v3)，(v1，v4)，(v2，v4)，(v2，v5)，(v3，v4)，(v4，v5) }， E 中各边对应的权值如下： (v1，v2)：3， (v1，v3)：10， (v1，v4)：7， (v2，v4)：5， (v2，v5)：7， (v3，v4)：9， (v4，v5)：15 请完成：（共 15 分）（1）画出图 G；（3 分）（2）画出图 G 的邻接表表示；（3 分）（3）写出从顶点 v1 出发进行深度优先搜索（DFS）产生的深度优先生成树；（4 分）（4）从顶点 v1 开始，用 Prim 算法构造图 G 的一棵最小生成树，并画出生成过程（5 分）十一、算法设计题（15 分）拟采用带头结点的单链表来存储线性表中的数据元素，但要求单链表中数据元素的存储顺序与线性表中数据元素的顺序逆序。即若线性表中的数据元素序列是 a1,a2,……, an-1,an,则实现的单链表的数据元素的序列是 an,an-1, ……，a2,a1（请见图 2）。

图 2 逆序建单链表示意图十二．二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。设二叉树结点结构为：(lchild,data,bf,rchild), lchild,rchild 是左右儿子指针；data 是数据元素；bf 是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。（15 分）

分享到：

赞收藏

资料库

2017年广西桂林电子科技大学数据结构考研真题A卷.doc

相关推荐

考研

热门标签

最新资料