桂林电子科技大学2018考研真题910数据结构.doc
第 1 页 共 7 页试题科目代码: 910 科目名称:数据结构注意:答案必须全部写在考点提供的答题纸上,写在试题上无效;答案要标注题号,答题纸要填写姓名和考号,并标注页码与总页数;交卷时,将答题纸与试题一起装入原试卷袋,用我校提供的密封条密封并签名。一、单项选择题(10 小题,每小题 3 分,共 30 分)1. 下面代码段的时间复杂度是( )int m=0, sum=0;while (mlink-link = p-link;Bp-link = p-link-link;p-link-link = p-link;Ctemp=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 (n1)res=res*fact(n-1);return res;第 2 页 共 7 页A2 B3 C4 D不确定5. 链栈与顺序栈相比,一个比较明显的优点是( )A.插入操作效率高 B .通常不会出现栈满的情况 C.取栈顶元素效率高 D.删除操作效率高6.在初始为空的队列中依次将元素1,2,3,4,5,6依次进队列后,又连续进行了三次出队操作,则此时队列的头元素是( )A3 B4 C5 D67. 一棵度为4 的树,n 0, n1, n2, n3,n4分别是树中度为 0,1 ,2 ,3 ,4的结点的个数则有( )An 0 = n1 + n2 + n3 + n4 Bn 0 = 2*n4 + n3 + 1 Cn 0 = 4*n4 + 3*n3 + 2*n2 + n1 Dn 0 = 3*n4 + 2*n3 + n2 + 18. 下列关于平衡二叉排序树的描述,错误的是( )A基于同一关键码集合构造的各种二叉排序树中,平衡二叉排序树的检索效率最好B平衡二叉排序树中每个结点的左、右子树高度之差的绝对值不超过 1 C在平衡二叉排序树中,动态插入或删除后,每个结点的左右子树能基本保持平衡D平衡二叉排序树适合构造动态字典9. 下列排序方法中,哪一种方法的比较次数与记录的初始排列状态无关?( )A. 直接插入排序 B. 冒泡排序 C. 快速排序 D. 直接选择排序10. 有向图的边集为, , , , , , ,下面正确的拓扑排序是( )Aaebdcf Bacefbd Caecdcf D不存在拓扑序列二、简答题(5 小题,每小题 10 分,共 50 分)1. 给定一个字符串 C=“a0a1an-1an”,其采用顺序队列结构存储,现需要将其逆序,即变换成“anan-1a1a0”,变换后的结果仍然存储在原队列中。若给定一个顺序栈作为辅助结构,请给出实现策略。 (请简单地用文字描述主要步骤) (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 分)第 3 页 共 7 页(2)给出每个字符对应的哈夫曼编码(4 分)4. 关键码集合 B =(5,30,38,57,20,10,71 ,31,15,36,76 ) ,设散列表为 HT0.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 NodeDataType info;struct Node *llink; /指向前驱的指针struct Node *rlink; /指向后继的指针Node;Node *current;ADCF EB8948 12 615 32 89第 4 页 共 7 页图 3 双向链表2. 下面是关于二分法检索的代码,请将其补充完整;数据元素存储在顺序表中,且按降序排列。(10 分)/记录定义如下:typedef struct int key; /* 字典元素的关键码字段 */int value; /* 字典元素的属性字段 */DicElement;typedef struct int MAXNUMint n; /*n 为字典中元素的个数 */DicElement *element; /* 降序存储的字典元素:element0elementn-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-elementmid.key=key) /* 检索成功 */ *position=mid; return(1); else if(pdic-elementmid.keykey) (3) ; else (4) ; *position=low; return(0); /* 检索失败 */ 第 5 页 共 7 页3. 根据以下给定的函数 traverse,以图 4 描述的二叉树 bt 为函数输入,请写出运行结果。 (10 分)struct BinTreeNode;typedef struct BinTreeNode *PBinTreeNode;struct BinTreeNodeDataType 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) 表示访问结点 xAB CE FDG H I Jbt图 4四、给定一组排序码: 29,32,52,66,8,14,43,20,若对其进行堆排序(1)请构建大根堆(5 分)(2)请给出前 3 趟堆排序、每一趟排序后的结果(5 分)五、无向带权图 G=A,B,C,D,E,其邻接矩阵存储如图 5 所示。请基于该邻接矩阵存储结构第 6 页 共 7 页回答以下问题:(1)图 G 是连通图吗?(3 分)(2)给出从顶点 C 出发的广度优先遍历序列(请注意该答案唯一,4 分)(3)给出从顶点 B 出发的深度优先遍历序列(请注意该答案唯一,4 分)(4)请使用 Kruskal 算法构造图 G 的最小生成树,要求给出构造过程中的每一步结果(9 分) G=02 20 124 7 98 124 07 8 9 18061860图 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 1000000struct SeqListint MAXNUM;int n; /n 是当前取 105DataType *element;/找众数DataType findMode(SeqList *sList)第 7 页 共 7 页