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

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

第1页 / 共7页

第2页 / 共7页

第3页 / 共7页

第4页 / 共7页

第5页 / 共7页

第6页 / 共7页

第7页 / 共7页

文本预览

2018 年广西桂林电子科技大学数据结构考研真题一、单项选择题（10 小题，每小题 3 分，共 30 分） 1. 下面代码段的时间复杂度是（） int m=0, sum=0; while (mlink->link = p->link； B．p->link = p->link->link；p->link->link = p->link； C．temp=p->info; p->info=p->link->info; p->link->info=temp; D．无法实现上述操作 4. 给定函数 fact(int n)，若执行 fact(4)，则函数执行过程中发生的出栈操作次数是（） int fact(int n) { int res=n; if (n>1) res=res*fact(n-1); return res;

} A．2 B．3 C．4 D．不确定 5. 链栈与顺序栈相比，一个比较明显的优点是（） A.插入操作效率高 B.通常不会出现栈满的情况 C.取栈顶元素效率高 D.删除操作效率高 6.在初始为空的队列中依次将元素1，2，3，4，5，6依次进队列后，又连续进行了三次出队操作，则此时队列的头元素是（） A．3 B．4 C．5 D．6 7. 一棵度为4的树，n0, n1, n2, n3,n4分别是树中度为0，1 ，2 ，3 ，4的结点的个数则有（） A．n0 = n1 + n2 + n3 + n4 B．n0 = 2*n4 + n3 + 1 C．n0 = 4*n4 + 3*n3 + 2*n2 + n1 D．n0 = 3*n4 + 2*n3 + n2 + 1 8. 下列关于平衡二叉排序树的描述，错误的是（） A．基于同一关键码集合构造的各种二叉排序树中，平衡二叉排序树的检索效率最好 B．平衡二叉排序树中每个结点的左、右子树高度之差的绝对值不超过 1 C．在平衡二叉排序树中，动态插入或删除后，每个结点的左右子树能基本保持平衡 D．平衡二叉排序树适合构造动态字典 9. 下列排序方法中，哪一种方法的比较次数与记录的初始排列状态无关？（） A. 直接插入排序 B. 冒泡排序 C. 快速排序 D. 直接选择排序 10. 有向图的边集为{, , , , , , }，下面正确的拓扑排序是（） A．aebdcf B．acefbd C．aecdcf D．不存在拓扑序列二、简答题（5 小题，每小题 10 分，共 50 分） 1. 给定一个字符串 C=“a0a1……an-1an”，其采用顺序队列结构存储，现需要将其逆序，即变换成“anan-1……a1a0”，变换后的结果仍然存储在原队列中。若给定一个顺序栈作为辅助结构，请给出实现策略。（请简单地用文字描述主要步骤）（10 分） 2. 请证明：一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于 n+1。（10 分） 3. 假定用于通信的电文仅由 7 个字符 a，b，c，d, e，f，g 组成，各个字符在电文中出现

的频率分别为 0.09，0.26, 0.2，0.18，0.01，0.14,0.12。试为这 7 个字符：（1）构造哈夫曼树（6 分）（2）给出每个字符对应的哈夫曼编码（4 分） 4. 关键码集合 B =（5，30，38，57，20，10，71，31，15，36，76），设散列表为 HT[0..6]，散列函数为 H(key) = key % 7 并用拉链法解决冲突，请完成如下内容：（1）构造散列表（6 分）（2）计算等概率情况下查找成功时的平均查找长度（4 分） 5. 请从图 2 中的顶点 D 出发，采用 Dijkstra 算法构造 D 到各顶点的最短路径（给出每一步的构造结果即可）（10 分）图 2 三、阅读以下代码，按照要求完成题目（3 小题，每小题 10 分，共 30 分） 1. 请基于图 3 所示，给出在该双向链表中删除 current 指针指向结点的操作（该结点的前驱、后继都不为空），要求不能增加辅助指针。每个结点由 llink、info、rlink 三个字段构成，分别表示当前结点的左指针域、数据域和右指针域。（10 分） //双向链表结点定义 typedef stuct Node{ DataType info; struct Node *llink; //指向前驱的指针 struct Node *rlink; //指向后继的指针 }Node;

Node *current; 图 3 双向链表 2. 下面是关于二分法检索的代码，请将其补充完整；数据元素存储在顺序表中，且按降序排列。（10 分） //记录定义如下： typedef struct { int key; /* 字典元素的关键码字段*/ int value; /* 字典元素的属性字段 */ }DicElement; typedef struct { int MAXNUM int n; /*n 为字典中元素的个数 */ DicElement *element; /* 降序存储的字典元素：element[0]～element[n-1] */ } SeqDictionary; //二分法检索 int binarySearch(SeqDictionary *pdic, int key, int *position) { //检索字典 pdic 中是否存在关键码为 key 的元素。检索成功，返回 1；否则返回 0. int low, mid, high; low=0; high = pdic->n-1; while( （1） ) { mid= （2） ; /* 当前检索的中间位置 */ if(pdic->element[mid].key==key) /* 检索成功 */ { *position=mid; return(1); } else if(pdic->element[mid].key>key) （3） ; else （4） ;

} *position=low; return(0); /* 检索失败 */ } 3. 根据以下给定的函数 traverse，以图 4 描述的二叉树 bt 为函数输入，请写出运行结果。（10 分） struct BinTreeNode; typedef struct BinTreeNode *PBinTreeNode; struct BinTreeNode{ DataType info; PBinTreeNode llink; PBinTreeNode rlink; }; typedef struct BinTreeNode *BinTree; void traverse( BinTree bt ) { if(t==NULL) return; traverse(rightChild (bt)); //rightChild(bt)是取 bt 二叉树的右子树函数 traverse(leftChild (bt)); //leftChild(bt)是取 bt 二叉树的左子树函数 visit(root(bt)); //root(bt)是取 bt 二叉树的根结点，visit(x)表示访问结点 x } 图 4

四、给定一组排序码： 29，32，52，66，8，14，43，20，若对其进行堆排序（1）请构建大根堆（5 分）（2）请给出前 3 趟堆排序、每一趟排序后的结果（5 分）五、无向带权图 G={A，B，C，D，E}，其邻接矩阵存储如图 5 所示。请基于该邻接矩阵存储结构回答以下问题：（1）图 G 是连通图吗？（3 分）（2）给出从顶点 C 出发的广度优先遍历序列（请注意该答案唯一，4 分）（3）给出从顶点 B 出发的深度优先遍历序列（请注意该答案唯一，4 分）（4）请使用 Kruskal 算法构造图 G 的最小生成树，要求给出构造过程中的每一步结果（9 分）图 5 六、众数指在一组数据中出现次数最多的数，例如若数据集合是{1,2,9,5,9,6,9}，则其众数是 9；若数据集合是{1,8,9,5,9,8,6,8,9}，由于 8 和 9 都出现了 3 次，则其众数是 8 和 9。请设计一个有效的算法，在 10 万个顺序存储的数据元素集合（无序存储）中找出众数，并分析所设计算法的时间复杂度。（10 分） //顺序存储结构定义 #define MAXNUM 1000000 struct SeqList{ int MAXNUM; int n; //n 是当前取 105 DataType *element; }; //找众数 DataType findMode(SeqList *sList) {

}

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料