2016929_55_856 数据结构（C语言版）-2016(1).zip

参考答案(A)参考答案(A)一、选择题（10 小题，每题 2 分，共 20 分）一、选择题（10 小题，每题 2 分，共 20 分）DBACD ADCAB 二、填空题（10 小题，每题 2 分，共 20 分）二、填空题（10 小题，每题 2 分，共 20 分）1.关系和操作 2.O(n)3.栈 4.1 5.146.A2i+2 7.2 8.队列 9.Dijkstra 10.11三、综合应用题（7 小题，每题 10 分，共 70 分）三、综合应用题（7 小题，每题 10 分，共 70 分）1.（1）k=2i+j-3 （2）i=(k+1)/3+1 j=(k+1)/3+(k+1)%32.（1）（2）先序：eadcbjfghi中序：abcdjefhgi后序：bcjdahigfe（3）（4）3.散列函数 H(k)=k%190123456789101112131415161718193820214224252645293133204111111121112成功：ASL=14/12=7/6不成功：ASL=(4+3+2+1+6+5+4+3+2+1+2+1+2+1+3+2+1+1+1+1)/20=46/20=2.34.（1）（2）72 91 （3）72 45 31（4）查找成功的平均查找长度：（1+2*2+4*3+6*4）/13=41/13不成功时的平均查找长度：(2*3+12*4)/14=54/14=27/75.（1）快速排序一趟后的结果：25 35 16 40 72 87 61 50 （2）堆排序进行升序初始堆：87 72 61 50 40 16 25 35 （3）堆排序 1 趟以后的结果：72 50 61 35 40 16 25 87 （4）1 趟冒泡排序后的结果：35 40 61 72 16 25 50 87 （5）1 趟归并排序后的结果：35 40 61 87 16 72 25 506.（1）事件V1V2V3V4V5V6V7V8V9V10V11最早发生时间01510655080160190220250270最迟发生时间0151565205801602052202502703431577064888497124105459172（2）活动a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14e100015106510801908016050220250190l15051557651659520580160205220250210（3）关键路径：a1-a3-a5-a9-a10-a12-a13（4）127.V1V6V7V2V4V5V36418512 8 V1V6V7V2V4V5V364185128四、算法设计（第 1 题 10 分，第 2，3 题各 15 分，共 40 分）四、算法设计（第 1 题 10 分，第 2，3 题各 15 分，共 40 分）1.int List_Delete(struct LNode*L,KeyType x)int c=0;if(L=NULL)return 0;p=L;while(p-next)if(p-next-data=x)c+;s=p-next;p-next=s-next;free(s);else p=p-next;if(L-data=x)c+;p=L;L=L-next;free(p);return c;2.typedef struct node ElenType data;struct node*next;LinkStack;void InitStack(LinkStack&L)L=NULL;void Push(LinkStack&L,ElemType x)p=(LinkList*)malloc(sizeof(LinkList);p-data=x;p-next=L;L=p;void Pop(LinkStack&L,ElemType&x)if(L=NULL)return;p=L;L=L-next;x=p-data;free(p);void Peek(LinkStack&L,ElemType&x)if(L=NULL)return;x=L-data;int Empty(LinkStack L)return L=NULL;void ClearStack(LinkStack&L)while(L)p=L-next;free(L);L=p;int GetLen(LinkStack L)int i=0;p=L;while(p)i+;p=p-next;return i;3.void CreatHuffman（Huffman HT ，int n，int w ）for（i=0；in；i+）HTi.lchild=-1;HTi.rchild=-1;HTi.weight=wi;HTi.parent=-1;for（i=n；i2*n-1；i+）search(HT,i-1,s1,s2);HTi.weight=HTs1.weightHTs2.weight;HTi.lchild=s1;HTi.rchild=s2;HTi.parent=-1;第 1 页 共 3 页姓 名：报 考 专 业：准 考 证 号 码：密封线内不要写题2016 年攻读硕士学位研究生入学考试试题2016 年攻读硕士学位研究生入学考试试题科目名称：数据结构（C 语言版）（A 卷B 卷）科目代码：856考试时间：3 小时 满分 150 分可使用的常用工具：无 计算器 直尺 圆规（请在使用工具前打）注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。一、选择题(共 10 小题，每小题 2 分，共 20 分)1.以下说法正确的是（）。A）数据元素是数据的最小单位B）数据项是数据的基本单位 C）数据结构是带有结构的各数据项的集合D）一些表面上很不相同的数据可以有相同的逻辑结构 2.在顺序表（长度为 127）中插入一个元素平均要移动（）个元素。A）8 B）63.5 C）63 D）73.若完全二叉树的结点总数为 1001，则度为 1 的结点有（）个。A）0 B）1 C）500 D）501 4.二叉树先序遍历 x 在 y 之前，后序遍历 x 在 y 之后，则 x 是 y 的（）。A）左兄弟 B）右兄弟 C）祖先 D）后裔 5.二叉树在线索化后，仍不能有效求解的问题是（）。A）前序线索二叉树中求前序后继 B）中序线索二叉树中求中序后继 C）中序线索二叉树中求中序前驱 D）后序线索二叉树中求后序后继 6.下列关于 AOE 网的叙述中，不正确的是（）。A）某些关键活动提前，则整个工程将会提前完成 B）任一关键活动提前，则整个工程将会提前完成 C）所有关键活动提前，则整个工程将会提前完成 D）关键活动不按期完成会影响整个工程的完成时间7.12 个数据有序顺序存储，采用二分查找，查找失败时的 ASL 值是（）。A）37/12 B）63/13 C）39/12 D）49/13 8.二叉查找树的查找效率与二叉树的（）有关。A）高度 B）结点的多少 C）树型 D）结点的位置 9.用函数 H(k)=key%17 构造散列表，则链地址法解决冲突需（）个链表。A）17 B）13 C）16 D）任意 10.在快速排序过程中，下列结论正确的是（）。A）左、右两个子表都已各自排好序 B）左边的元素都不大于右边的元素 第 2 页 共 3 页 C）左边子表长度小于右边子表长度 D）左、右两边元素的平均值相等 二、填空题(共 10 小题，每小题 2 分，共 20 分)1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（）等的学科。2.在单链表（长度为 n）给定值 x 的结点后插入新结点的时间复杂度为（）。3.判断表达式中左右括号是否配对的算法采用（）数据结构最佳4.设广义表 L=(a,b,c)，则 L 的长度为（）。5.由 4 个结点可以构造出（）种不同的二叉树。6.用数组 A0n-1存储完全二叉树，则 Ai的右子女是结点（）。7.在一个图中，所有顶点的度数之和等于所有边数的（）倍。8.为了实现图的广度优先搜索，除了一个标志数组标志已访问的结点外，还需（）存放被访问的结点以实现遍历。9.求图中一个顶点到其它各个顶点最短路径的算法是（）算法。10.具有 12 个记录的序列，采用冒泡排序最少的比较次数是（）。三、综合应用题(共 7 小题，每小题 10 分，共 70 分)1.将三对角矩阵 A1.n，1.n的非零元素逐行存放于数组 B0.3n-3中，使得Bk=Ai，j，求：（1）用 i，j 表示的变换公式 （2）用表示 i，j 的变换公式2.设二叉树的顺序存储结构如下：012345678910 11 12 13 14 15 16 17 18 19eafdgcjhib（1）画出该二叉树的逻辑结构（2）写出其先序、中序、后序序列（3）画出其后序线索二叉树（4）把它转换成对应的森林3.给定序列（26,25,20,33,21,24,45,204,42,38,29,31），要用散列法进行存储，散列函数采用除留余数法，用线性探测法解决冲突，负载因子为 0.6。（1）设计哈希函数（2）画出哈希表 （3）计算等概率情况下查找成功和失败的平均查找长度4.对有序表(31,34,45,57,64,70,72,84,88,91,97,105,124)折半查找，要求 （1）画出描述折半查找过程的判定树；（2）若查找元素 91，需依次与那些元素比较?（3）若查找元素 30，需依次与那些元素比较?（4）分别求等概率情况下查找成功和不成功时的平均查找长度。5.已知关键字序列（40，35，61，87，72，16，25，50），（1）写出用快速排序方法升序排列该序列一趟后的结果 （2）写出用堆排序进行升序排列时的初始堆 （3）写出堆排序 1 趟以后（交换与调整之后）的结果第 3 页 共 3 页 （4）写出 1 趟冒泡排序后的结果 （5）写出 1 趟归并排序后的结果6.有以下 AOE 网：（1）求各事件的最早/迟发生时间 （2）求各活动的最早/迟开始时间（3）给出其关键路径 （4）其拓扑序列共有多少种 V1V2V3V4V5V6V8V7V9V10V11a1=15a2=10a3=50a4=8a5=15a6=40a7=110a8=15a9=80a10=60a11=15a12=30a13=20a14=40a0=07.分别用 Prim 和 kruskal 算法构造最小生成树。（需标示每一步构造过程）V1V6V7V2V4V5V36423252018510128157四、算法设计(第 1 题 10 分，第 2，3 题各 15 分，共 40 分)1.设计算法，在不带头结点的单链表 L 上实现删除 data 域值为 x 的所有结点，返回删除结点的个数；int List_Delete（struct LNode *L，KeyType x）2.采用链式存储实现栈的操作（数据元素类型为 ElemType），包括栈的初始化InitStack、入栈 Push、出栈 Pop、取栈顶元素 Peek、判栈空 Empty、清空栈ClearStack 以及返回栈中元素个数 GetLen 等操作，并作简单注释。3.根据给定的 n 个权值可以构造一颗哈夫曼树。若哈夫曼树采用顺序存储结构，每个结点的数据结构采用如下格式。Typedef struct unsigned int weight;/结点的权值 unsigned int parent,lchild,rchild;/分别存放双亲、左右孩子的下标 Huffman;试设计如下算法 CreatHuffman，根据给定的 n 个权值构造一颗哈夫曼树。void CreatHuffman(Huffman HT,int n,int w);其中：HT 为构造的哈夫曼树，n 表示权值个数，w 用来存储所有权值下图是根据权值 7，5，2，4 所构造出来的哈夫曼树（-1 表示空）。