2012-2019年三峡大学836数据结构真题合辑

2012-2019年三峡大学836数据结构真题合辑三峡大学2012年研究生入学考试试题(A卷)科目代码：838科目名称：数据结构（考生必须将答案写在答题纸上，总分150分，考试时间180分钟）一、选择题(每小题2分，共40分)1、线性表采用链式存储时，结点的存储地址（）。A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续2、已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行（）操作。A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s->next;s->next=pD.p->next=s;s->next=q3、设有一个顺序栈S,元素按S1,S2,S3,S4,S5,S6顺序进栈，若6个元素的出栈顺序为S2,S3,S4,S6,S5,S1,则顺序栈的容量至少应为（）。A.2B.3C.4D.54、如下陈述中正确的是（）。A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串5、设有一个二维数A[m][n]，假设A[0][0]寄存位置在544，A[5][5]寄存位置在624，每个元素占一个空间，A[2][2]在（）位置。A.592B.586C.576D.6086、设有5个字符呈现的频度分别为1,2,3,5,4，则对应的哈夫曼树的带权途径长度为（）。A.34B.33C.35D.157、含n个顶点和e条边的无向图的邻接矩阵中非零元素的个数为（）。A.eB.2eC.n2-eD.n2-2e第2页8、长度为500的有序表采用折半查找时，查找成功最大比力次数为（）。A.8B.9C.10D.119、快速排序在下列哪种情况下最易发挥其长处（）。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊10、下列关键字序列中，（）是堆。A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94，31,72D.16,23,53,31,94,7211、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…,pn,若p1=n，则pi为（）。A.iB.n=iC.n-i+1D.不确定12、具有n(n>0)个结点的完全二叉树的深度为（）。A.log2(n)B.log2(n)+1C.log2(n)+1D.log2(n)-114、用邻接表表示图进行广度优先遍历时，通常是采用（）数据结构来实现算法的。A.栈B.队列C.树D.图15、深度优先遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.条理遍历16、有8个结点的无向图最多有（）条边。A.14B.28C.56D.11217、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中哪些元素比较大小，查找结果是失败。（）A.20，70，30，50B.30，88，70，50C.20，50D.30，88，50第3页18、任何一个无向连通图的最小生成树（）。A.只要一棵B.一棵或多棵C.肯定有多棵D.可能不存在19、链表合用于哪类查找（）。A.顺序B.二分法C.顺序，也能二分法D.随机20、把一棵树转换为二叉树后，这棵二叉树具有什么样的形态特征（）。A.是唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子二、填空题(每小题1分，共30分)1、对于一个表长为n的顺序表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。（要求用大O表示法表示）2、神枪手依次压入10颗子弹进入枪膛，编号分别为1-10，则消灭第4个敌人的子弹编号是。3、已知一采用空闲单元法的循环队列容量为20，队列的首、尾指针分别用f和r表示，f＝3，r＝18时队列的长度为，f＝15，r＝7时队列的长度为。4、设有一个10阶的对称矩阵A[10][10]，每个数据占2个字节，A[0][0]的存储地点是24，则A[3][8]的地点是，若采用紧缩存储体式格局按即将矩阵中下三角部分的元素存入一维数组B中，A[0][0]存入B[0]中，则A[8][5]在B[]中的下标是，A[5][8]在B[]中的下标是。5、一棵深度为6的满二叉树有个分支结点和个叶子结点。6、是被限定为只能在表的一端进行插入和删除运算的线性表。7、已知某二叉树的中序遍历结果是：DEBAC，后序遍历结果是：EDBCA，则该树的先序遍历序列是，层序遍历序列是。8、若采用基于二叉树的递归遍历办法编写建立和销毁树的函数，那末建立应该基于遍历函数修改，而销毁树应该基于遍历函数修改。9、稀疏图适合采用存储布局，其对应的最小天生树算法是基于归并的，最好用算法来求解。第4页10、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地点为。11、设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。12、如果一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。13、GetHead【GetTail【((a,b),(c,d))】】=。14、写出下列程序段的时间复杂度，要求用大O表示法表示。s=0;i=1;fori=0;i<n;i++)while(i<=n)for(j=0;j<n;j++)i=i*3;s+=B[i][j];sum=s;答：答：三、综合题(共50分)1、试写出模式串T=“FGFFGF”的next函数值和nextval函数值(6分)。jTnext[j]nextval[j]1F2G3F4F5G6F第5页2.根据下图回答下列问题。（14分）V2a1=3a3=4V1a4=2a2=2V3a8=5V4a7=4V6a6=5V7a10=3a5=6V5a9=5(1)要完成该AOE网中工程，最短时间是多少？（不考虑单位）（5分）(2)上图中的关键路径是什么（用顶点序列表示）？将活动a10的时间改成2可否提前完成？（3分）(3)若忽略边的权值将上图看成一个AOV网，并约定当存在多个入度为的结点时先输出编号较小的结点，则请写出拓扑排序结果。（3分）(4)若忽略边的方向性将上图看成无向网，各边权值为经济代价，请给出该无向网的一棵最小天生树。（3分）3、已知数据序列为：2，，3，5，8，7，4，6，2（10分）(1)在一个初始值为空的二叉排序树中顺次查找这些结点（动态查找，无则插入），请画出该二叉排序树的最终形态。（4分）(2)如果在查找过程中需要对该二叉排序树举行动态平衡化，请画出从空树到最终的平衡二叉树的组织过程，要求标明结点平衡因子。（6分）4、待散列的线性表为（42，7，34，21，20），散列用的一维地点空间为[0..6]，假定选用的散列函数是H（K）=K%7，若发生冲突采用线性探查法处理。（5分）(1)计算出每个元素的散列地点并在下图中填写出散列表：（3分）0123456(2)求出在查找每一个元素概率相等情况下的平均查找长度。（2分）5、已知待排序关键字序列是38，19，50，61，32，23，11，14，15请回答下列排序问题(要求排成升序序列)：（10分）(1)若采用间接插入排序，第一个位置前移的元素枢纽字是？(2分)(2)若采用希尔排序(di＝5,3,1),第一个位置前移的元素枢纽字是？(2分)(3)若采用间接选择排序，第一个位置前移的元素枢纽字是？(2分)第6页(4)若采用快速排序，第一个位置前移的元素关键字是？(2分)(5)若采用堆排序，利用筛选操作建堆过程中最先交换的两个元素关键字是？(2分)6、一棵度为k的树中有n1个度为1的结点，n2nk个度为k的结点，则该树中有多少个叶子结点，并证明。（5分）四、程序题(共30分)1、已知x和y是整型全局变量，初值均为，root为二叉树的根结点。（8分）voidABC(NODE*root){if(root){ABC(root->lchild);if(!root->lchild&&!root->rchild)x++;if(!root->lchild||!root->rchild)y++;ABC(root->rchild);}}（1）该算法是在二叉树哪种遍历程序基础上修改成的？（2分）（2）执行该算法后x和y中保存的值分别是什么？（3分）（3）试用x和y表示二叉树的总结点数n。（3分）2、阅读程序，回答问题。（12分）（1）voidproc_1(adjlistGL,inti,intn){printf(“%d”,i);visited[i]=true;edgenode*p=GL[i];while(p!=NULL){intj=p->adjvex;if(!visited[j])proc_1(GL,j,n);p=p->next;}}第7页该函数实现的是()的()操纵，采用的存储布局是()，算法履行时系统内部需要调用()数据结构。（4分）（2）voidproc_2(StackS,inte){StackT;intd;InitStack(&T);While(!EmptyStack(S)){Pop(&S,&d);if(d!=e)Push(&T,d);}While(!EmptyStack(T)){Pop(&T,&d);Push(&S,d);}}简述proc_2的功能。（4分）（3）voidproc_3(Queue*Q){StackS;intd;InitStack(&S);While(!EmptyQueue(*Q)){DeleteQueue(Q,&d);Push(&S,d);}While(!EmptyStack(S)){Pop(&S,&d);EnterQueue(Q,d);}}简述proc_3的功能。（4分）第8页3、算法填空，使之可以对降序序列进行二分查找,要求找到则返回元素在查找表中位置，否则返回。（10分）intbinarysearch(splistst,intn,keytypekey)｛//降序序列函数，st顺序表n表长key关键字intmid,low,high,find;find=0;low=1;high=n;while((low<=high)＆＆（find==0）)｛(1);if(key>st[mid].key)(2);elseif(key<st[mid].key)(3);else｛(4);//找到printf(“findst[%d].key==%d\n”,mid,key);(5);//返回｝｝if(find==0)return(0);｝/*binarysearch二分查找*/第1页共5页三峡大学2013年研究生入学测验试题(A卷)科目代码：838科目名称：数据结构（考生必须将答案写在答题纸上，总分150分，考试时间180分钟）一、选择题(每小题2分，共40分)1、线性表采用链式存储时，结点的存储地址（）。A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续2、已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行（）操作。A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s->next;s->next=pD.p->next=s;s->next=q3、设有一个按次栈S,元素按S1,S2,S3,S4,S5,S6按次进栈，若6个元素的出栈按次为S2,S3,S4,S6,S5,S1,则按次栈的容量至少应为（）。A.2B.3C.4D.54、设有两个串p和q，求q在p中首次出现的位置的运算称作（）。A.连接B.模式匹配C.求子串D.求串长5、设有一个二维数A[m][n]，假设A[0][0]寄存位置在544，A[5][5]寄存位置在624，每个元素占一个空间，A[2][2]在（）位置。A.592B.586C.576D.6086、设有5个字符出现的频度分别为2,7,5,4，则对应的哈夫曼树的带权路径长度为（）。A.34B.33C.35D.157、含n个顶点和e条边的无向图的邻接矩阵中非零元素的个数为（）。A.eB.2eC.n2-eD.n2-2e第2页8、长度为500的有序表采用折半查找时，查找成功最大比力次数为（）。A.8B.9C.10D.119、快速排序在下列哪种情况下最易发挥其长处（）。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊10、下列关键字序列中，（）是堆。A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94，31,72D.16,23,53,31,94,7211、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…,pn,若p1=n，则pi为（）。A.iB.n=iC.n-i+1D.不确定12、一棵具有257个结点的完全二叉树，它的深度为（）。。A.7B.8C.9D.1014、用邻接表表示图进行广度优先遍历时，通常是采用（）这种数据结构来实现算法的。A.栈B.队列C.树D.图15、深度优先遍历相似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历16、有8个结点的无向图最多有（）条边。A.14B.28C.56D.11217、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中哪些元素比较大小，查找结果是失败。（）A.20，70，30，50B.30，88，70，50C.20，50D.30，88，50第3页18、任何一个无向连通图的最小生成树（）。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在19、链表适用于哪种查找（）。A.顺序B.二分法C.顺序，也能二分法D.随机20、把一棵树转换为二叉树后，这棵二叉树具有什么样的形态特征（）。A.是唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子二、填空题(每小题2分，共30分)1、对于一个表长为n的顺序表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。（要求用大O表示法表示）2、神枪手依次压入10颗子弹进入枪膛，编号分别为1-10，则消灭第4个敌人的子弹编号是。3、一棵深度为6的满二叉树有个分支结点和个叶子结点。4、是被限定为只能在表的一端进行插入和删除运算的线性表。5、已知某二叉树的中序遍历结果是：DEBAC，后序遍历结果是：EDBCA，则该树的先序遍历序列是。6、设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。7、如果一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。8、由3个结点所构成的二叉树有种形态。9、写出下列程序段的时间复杂度，要求用大O表示法表示。s=0;i=1;fori=0;i<n;i++)while(i<=n)for(j=0;j<n;j++)i=i*3;s+=B[i][j];sum=s;答：答：第4页3、综合题(共60分)1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？(10分)2、说明线性表、栈与队的异同点。（10分）3、根据下图回答下列问题。（20分）V2a1=3a3=4V1a4=2a2=2V3a8=5V4a7=4V6a6=5V7a10=3a5=6V5a9=5(5)要完成该AOE网中工程，最短时间是多少？（不考虑单位）（5分）(6)上图中的关键路径是什么（用顶点序列表示）？将活动a10的时间改成2可否提前完成？（5分）(7)若忽略边的权值将上图看成一个AOV网，并约定当存在多个入度为的结点时先输出编号较小的结点，则请写出拓扑排序结果。（5分）(8)若疏忽边的方向性将上图看成无向网，各边权值为经济代价，请给出该无向网的一棵最小生成树。（5分）4、待排序枢纽字序列是38，19，50，61，32，23，11，14，15请回答下列排序问题(要求排成升序序列)：（10分）(5)若采用间接插入排序，第一个位置前移的元素枢纽字是？(3分)(6)若采用间接选择排序，第一个位置前移的元素枢纽字是？(3分)(7)若采用快速排序，第一个位置前移的元素枢纽字是？(2分)(4)若采用堆排序，利用筛选操作建堆过程中最先交换的两个元素关键字是？(2分)5、已知数据序列为：2，，3，5，8，7，4，6，2在一个初始值为空的二叉排序树中顺次插入这些结点，请画出该二叉排序树的最终形态。（10分）第5页四、阅读程序，回答问题。（20分，每题10分）（4）voidproc_1(StackS,inte){StackT;intd;InitStack(&T);While(!EmptyStack(S)){Pop(&S,&d);if(d!=e)Push(&T,d);}While(!EmptyStack(T)){Pop(&T,&d);Push(&S,d);}}简述proc_1的功能。（10分）（5）voidproc_2(Queue*Q){StackS;intd;InitStack(&S);While(!EmptyQueue(*Q)){DeleteQueue(Q,&d);Push(&S,d);}While(!EmptyStack(S)){Pop(&S,&d);EnterQueue(Q,d);}}简述proc_2的功能。（10分）三峡大学2013年研究生入学测验试题(A卷)科目代码：839科目名称：计算机网络（考生必须将答案写在答题纸上）（注：本科目总分150分，测验工夫为180分钟。）一、填空题(每空1分，共10分，在答题纸上按按次写上题号和答案)(1)是将各类息传感装备经由过程互联网，把物品与物品结合起来而形成的一个巨大收集，被誉为环球经济兴起的下一个增长点。(2)第三代移动通（3G）采用IMT-2000国际标准，是在中国TD-SCDMA、美国CDMA2000和欧洲WCDMA三个标准提案综合谈判基础上形成的，其技术核心是。(3)NGN支持多种业务，能够实现业务与传送分离，控制功能独立，接口开放，具有服务质量(QoS)保证和支持通用移动性，其核心技术是基于。(4)采用802.11系列协议Wi-Fi成为互联网一种重要补充网络。它在MAC层采用的道争用和谈是。(5)现代密码技术中解决数字签名、密钥分配、认证等主要依靠体制。(6)本地专用网需要采用技术才能实现访问互联网。(7)具有四层体系结构，是Internet采用的标准协议体系。(8)是IETF设计的下一代互联网和谈，提议供给与mobileip和ipsec保持兼容的移动性和安全性。(9)是具有自我复制、破坏计算机功能或者数据的程序代码。(10)加密技术的安全性主要取决于的长度和密文分析的时间代价。二、单项选择题(每小题1分，共10分,在答题纸上按顺序写上题号和答案)(1)Internet所采用的交换技术是__A.电路交换B.报文交换C.分组交换D．程控交换(2)下面协议中,用于WWW传输控制的是__A.URLB.SMTPC.HTMLD.HTTP(3)从通讯和谈的角度来看，路由器是在__上实现收集互联A.物理层B.链路层C.收集层D.传输层(4)PPP协议在SONET/SDH中使用零比特填充法实现同步传输的比特串为，则在接收站提交给数据链路层的代码为：__A.B.C.D.A.全双工B.半双工C.单工D.上述三种均不是(6)以下不属于内部网关协议的是A．RIPB.OSPFC.BGPD.RIP2(7)与10Bast-T以太网相比，100Base-T以太网中传输的最小帧长__A.为10Bast-T以太网的最小帧长的十分之一B.与10Bast-T以太网的最小帧不异C.为10Bast-T以太网的最小帧长的十分之一D.由于速度进步，因而无最小帧长的限制A、调制解调器B、网卡C、收集线D、都不是(10)DNS的中文含义是__。A、邮件体系B、地名体系C、服务器体系D、域名服务体系3、判断题(每题1分，共10分。在答纸上顺次写上答案，精确打✓，毛病打×)（1）物理层的义务就是透亮地传送帧。（2）所有交换机都是工作在数据链路层以下的。（3）在IP网络中，网络层交换的数据单元是IP分组。（4）时延带宽积的物理意义透露表现链路的极限数据容量。（5）是内网地址。（6）IPV4是32位地址,而IPV6是64位地址。（7）UDP报文中地址是32位表示的端口号,用来区分应用层进程的。（8）防火墙用于两个网络之间的接入控制，主要解决内网的安全问题。（9）IP地址是16位表示的是全球唯一的地址,每个主机都只能有一个唯一的IP地址。（10）无线传感器网络具有完整的网络体系结构，包括物理层、MAC层、网络层、传输层和应用层五层结构。四、问答题（每小题10分，共40分）1）分类IP地点体系中经常利用IP地点有哪几类？各类地点的起止地点为几何？2）试说明计算机收集拓扑布局。有哪几种常见的收集拓扑类型？3）什么叫做以太网？以太网有哪两个主要标准？4）OSI体系结构包括哪几层？1、设有一电话线路，当前的道带宽为3.1kHz,道的极限速率为31kbps。现在想对其进行改造，准备将极限速率增加50%，试问：（10分）1）噪比至少增加多少倍？2）根据上题计算结果，进步收集的极限传输速率与与噪比有何联系关系？2、设某CIDR路由器建立了以下路由表:（10分）目的网络网络前缀22()23()25(28)25(28)194.5.153.(92)-*(默认)分别为下列目的地址的分组计算其下一跳:1)652)13)22六、综合应用题（20+20，共40分）1、设有一网络拓扑如右下图所示。圆形图中字母表示路由器节点。各结点链路之间的带宽开销标示在链路上(假设所有网络到邻近路由节点的带宽开销为0)。试写出(1)(2)题中A点的路由表(目的网络，距离，下一跳路由)，并用路由节点顺序表示各条目的路由路径，如N4,2,D,（AD）（20分）(1)若采用RIP路由协议；(2)若改用OSPF路由和谈（带宽为开销）；下一跳接口接口1R1R2R3R44CN13EN3A23B37N23DN421F3N52、现有一单位的网络规划如右下图。单位只申请到一个C类地点拟分派C类地点数：剩下的IP地点作为后备扩大用。现在有如下限制条件：（20分）1）N2有计算机60台，需要划分2个vlan,且PC0需要外网访问服务器SV0；2）网络内部可以使用堆叠的hub或交换机举行局域网扩大；3）路由器和三层交换机SW1都支持CIDR协议。请根据上述基本条件，进行如下网络实施设计：1）提出合理的地址划分方案；2）申明N2的Vlan施行步骤，若何实现PC0需要外网拜候服务器SV0。SW1N2PC0SV0R2R4N4R01R02N1R1R3N3三峡大学2014年研究生入学考试试题(A卷)科目代码：838科目称号：数据布局考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、填空题(每小题2分，共30分)1.有一算法的计算次数f（n）=+0.001n2+1000nlgn，则该算法的复杂度用大O表示法应该是（）A.O()B.O(1)C.O(n2)D.O(nlgn)2、链表的特征是（）A．逻辑连续,物理连续B.逻辑连续,物理不连续C．逻辑不继续,物理继续D.逻辑继续,物理不肯定继续3、已知链表中某结点指针为p，在其后插入一个指针s指向的新结点，则需执行下列哪个指令A．p->next=sB.p->next=s;s->next=p->next;C.s->next=p->next;p->next=s;D.s->next=p->next;s->next=p;4.设有一个顺序栈P，元素按P1,P2,P3,P4.P5顺序进栈，若5个元素的出栈顺序为P2,P3,P5,P4,P1，则顺序栈的容量至少应为（）。A.2B.3C.4D.55、设有一个二维数A[10][10]，假设A[2][0]的寄存位置在1020，按行优先存储，每个元素占2空间，A[5][5]在（）位置。A．1102B.1100C.1088D.10906、结点的权重分别是1,2,3,3,3，则对应哈弗曼树的带权途径长度为（）A.26B.27C.28D.307、已知某二叉树先序遍历结果为ABCDEF，中序遍历果为BCAEFD，则其后序遍历结果是（）.A．BCDEFAB.CBFEDAC.ABDCEFD.BCEFDA8、在10个顶点的无向图的邻接表中，除头结点外，共有（）个链表结点。A.10B.20C.30D.159.在单链表中删除一个指定元素的复杂度是（）A、O(n)B.O(n2)C.O(1)D.O(nlog2n)第2页10、在长度为100的二叉排序树中举行查找一个存在的元素，最多比力（）次。A.8B.7C.6D.111、图的广度优先遍历过程中，需要用到（）作为辅助数据布局包管同层结点拜候的精确按次。A、按次表B、链表C、栈D、队列12、待散列的线性表为（98，35，27，42，67，56），假定选用的散列函数是H（K）=K%7，则与98冲突元素个数是（）A、B、1C、2D、313、快速排序最坏情况下的复杂度是（）A、O(n)B.O(n2)C.O(1)D.O(nlog2n)14、下列算法中属于稳定排序的是（）A.堆排序B.简单选择排序C.快速排序D.二分插入排序15、对于数据量不大且接近有序时，适合采用（）A.堆排序B.间接插入排序C.快速排序D.冒泡排序二、判断题题(每题2分，共20分,对的打√，错的打×)1.数据结构的逻辑结构决定了其存储结构。（）2.比较算法复杂度需在同一运行环境下的运行比较时间（）3.对于最大指数很大，非零项很少的一元多项式加法适合采用链式存储结构存储。（）4.当队中有元素时，队尾元素不克不及出队。（）5.除了内存溢出，链栈一般不会满。（）6.给定二叉树先序遍历序列和后序遍历序列一般不能唯一确定树结构。（）7.图的非关键活动时间可以任意安排。（）8.稠密图采用毗邻矩阵的存储效力要高于毗邻表。（）9.二分查找办法不成以对链表举行。（）10.当排序长度大且数据随机但不要求稳定时，最适合采用堆排序算法。（）3、填空题(每个空2分，共30分)1．用21把钥匙试开1把锁（只有一把能开），平均需要试（）次。2.15辆车依次开进了一个死胡同，但第5辆车要开走，后面需要退出（）辆车。3.采用空闲单元法的循环队列容量为100，若f=25，r=47，则队长（），若f=55，r=25，则队长是（）。4.数组A[10][10]采用列优先存储，每个数据占4个字节，A[0][0]起始地址是2000，该数组的存储空间需要（）个字节；A[8][7]的存储地址是（）.第3页5、设一棵完全二叉树具有1001个结点，则它有()个叶子结点，有()个度为2的结点，有()个结点只要非空左子树，第4个叶子结点编号是()．6.10个顶点的无向完全图有（）条边，9个顶点有向完全图有（）条边。7.在长度为11的递增有序表中二分查找第5个元素，需要比力（）次。8.稠密图适合采用（）存储布局，对应的最小天生树算法应该是基于（）归并较好。四、计算题。（共50分）1.建二叉排序树的序列是：2，4，1，3，9，请画出该二叉排序树结构，并计算基于该树进行查找的平均查找长度。（10分）2.根据下图回答下列问题（20分）V4a1=2V1a2=2a4=2V7a8=6V5a3=4a5=5a7=4V6a6=4V3a9=2V2a10=4（1）要完成该AOE网中工程，最短时间是多少？（不考虑单位）（5分）（2）上图中的关键路径是什么（用顶点序列表示）？将活动a8的时间改成5可否提前完成？（5分）（3）若忽略边的权值将上图看成一个AOV网，并约定当存在多个入度为的结点时先输出编号较小的结点，则请写出拓扑排序结果。（5分）（4）若疏忽边的方向性将上图看成无向网，各边权值为经济代价，请给出该无向网的一棵最小天生树。（5分）3.已知待排序关键字序列是38，19，50，61，32，23，11，15，14请回答下列排序问题(要求排成升序序列)：（20分）(1)若采用直接插入排序，第二个位置前移的元素关键字是？(4分)(2)若采用希尔排序(di＝5,3,1),第二个位置前移的元素关键字是？(4分)(3)若采用简单选择排序，第二个位置前移的元素关键字是？(4分)(4)若采用快速排序，第二个位置前移的元素枢纽字是？(4分)(5)若采用堆排序，利用筛选操作建堆过程中第二次交换的两个元素关键字是？(4分)第4页五、程序题(每题10分，共20分)1.x和y是整型全局变量，初值均为，root为二叉树的根结点。（10分）voidABC(NODE*root){if(root){ABC(root->lchild);ABC(root->rchild);if(root->lchild&&root->rchild)x++;if(root->lchild||root->rchild)y++;}}（1）该算法是在二叉树哪类遍历程序根蒂根基上修改成的？（3分）（2）履行该算法后x和y中储存的值分别是什么？（4分）（3）试用x和y表示二叉树的总结点数n。（3分）2.算法填空，使之可以对降序序列进行二分查找,要求找到则返回元素在查找表中位置，否则返回（5分）。intbinarysearch(splistst,intn,keytypekey)｛//降序序列函数，st按次表n表长key枢纽字intmid,low,high,find;find=0;low=1;high=n;while((low<=high)＆＆（find==0）)｛（1）;if(key>st[mid].key)（2）;elseif(key<st[mid].key)(3);else｛(4);//找到printf(“findst[%d].key==%d\n”,mid,key);(5);//返回位置｝｝return(0);｝/*binarysearch二分查找*/三峡大学2015年研究生入学测验试题(B卷)科目代码：838科目名称：数据结构考试时间为3小时，卷面总分为150分答案必须写在答题纸上（本套试题出现的代码采用C语言规定）一、单选题（每题2分，共30分）1.某线性表中最经常利用的操纵是存取第i个元素及其先驱的值，采用（）存储体式格局最省工夫。A.按次表B.带头结点的单向链表C.带头结点的双向循环链表D.带尾指针的单向循环链表2.下列选项中，（）是链表不具有的特点。A.插入和删除运算不需要移动元素B.所需存储空间与线性表的长度成正比C.不必事先估计存储空间大小D.可以随机访问表中任意元素3.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S,如果每个元素出栈后立即进入队列Q,且7个元素出队的顺序为b,d,c,f,e,a,g,则栈S的容量至少是（）A.2B.3C.5D.74.设队列中有A,B,C,D,E这5个元素，个中队首元素为A.如果对这个队列反复履行下列操纵：1）输出队首元素；2）把队首元素插入到队尾；3）删除队首元素；4）再次删除队首元素。前述操纵直到队空为止，则可能取得输出序列（）A.ACECCB.ACEC.ACECCCD.ACEC5.下列排序算法中，（）算法可能会出现下面的情况，即当初始数据有序时，花费时间反而最多。A.堆排序B.冒泡排序C.快速排序D.希尔排序6.在关键字随机分布的前提下，用平衡的二叉排序树进行查找，其平均查找长度同（）数量级相当。A.按次查找B.二分查找C.快速查找D.都不精确7.对于一个有向图，若一个顶点的度为k1,出度为k2,则对应的邻接表中，该结点单链表的边结点数目为（）A.k1B.k2C.k1-k2D.k1+k2第2页8.已知一个有向图G具有n个顶点和e条弧，用邻接表来存储表示需要（）个弧结点。A.nB.n2C.eD.2e9.哈希表的长度m=10,哈希函数H(key)=key%7,枢纽字为k的记实在定址时发生了冲突，若采用开放地点法（也称再散列法）办理冲突，则新地点的计算公式为（）A.(H(k)+di)/10B.(H(k)+di)/7C.(H(k)+di)%10D.(H(k)+di)%710.一个带头结点的非空循环单链表，其尾指针是R,则其首元素结点的地点为（）A.R->nextB.*(R->next->next)C.&(R->next->next)D.R->next->next11.下列枢纽字序列，不成能构成某二叉排序树的查找途径的序列是（）A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,3412.若7个顶点的无向图是连通的，则其边数至少是（）A.6B.7C.8D.1413.一个完全二叉树的第6层（树根为第1层）有8个叶子结点，则该树的结点个数最多为（）A.39B.52C.111D.11914．快速排序在下列()情况下最容易发挥其长处。A.被排序的数据中含有多个排序码B.被排序数据已基本有序C.被排序数据完全无序D.被排序数据的最大值和最小值相差悬殊15.对n个不同的元素进行冒泡排序，在下列（）情况下换位次数最多。A.元素从小到大排列好B.元素从大到小排列好C.元素无序D.元素根本有序二、填空题（每空2分，共30分）1.在n个元素的按次表中删除一个元素，需要均匀移动（）次。2.循环单链表以list为头指针，结点的指针域next,指针p所指结点为表尾结点的条件是（）。3．一个长度为N的数组空间存放循环队列，头尾指示器分别为front和rear,则该队列元素个数为（）。4．广义表（（a,b），（a,(b)））的深度是（）。5.如果结点A有3个兄弟，B是A的双亲，则B的度是（）。6.有一个图的毗邻矩阵按行顺次是[[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]]，图中有（）条边，度最大的的极点的度是（）。7.在一组记实（54,38,96,23,15,72,60,45,83）举行插入排序时，当把第7个记实60插入到有序表时，为寻觅插入位置需比力（）次第3页8.对于n个记录的集合进行冒泡排序，在最坏情况下所需时间是（），若对其进行快速排序，在最坏情况下所需时间是()9.假设用循环单链表实现队列，结点指针域为next,若队列非空，且尾指针为R,则将新结点S加入队列时，需履行三条语句（）；（）；R=S;.10.n个极点的连通无向图至少有（）条边，最多有（）条边11.在程序段：for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)x++;中，x++履行了（）次。3、计算题（每题10分，共50分）1.假设有6行8列的二维数组A(下标从开始),每个元素占6个字节，存储器按字节编址。已知A的首地址为1000,计算：1)数组A共占用多少字节。（2分）2）数组A的最后一个元素地址（3分）3）按行存储时A[3][6]的地址（2分）按列存储时A[3][6]的地址(3分)。2.一棵度为k的树中n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，则该树中有多少个叶子结点(5分)并证明之（5分）。3.二叉树的先根次序访问序列为GFKDAIEBCHJ，中根次序访问序列为DIAEKFCJHBG，画出这个树（10分）。4.对图一，从顶点开始访问，给出深度优先和广度优先搜索结果（各5分）。12435图16785.给定关键字序列（8,3,25,19,12,30,47,34），按次序插入建立一个二叉排序树，画出这个树（10分）。四、程序题（每题20分，共40分）1已知一个带有表头结点的单链表，结点结构为{data,link}。假设链表中只给出了头指针list.在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法获得该结点的data的值，并返回1；否则返回回0.采用C语言实现函数intsearch(RecordType*list,intk，DataType*d)。（不得使用额外大内存）2二叉树的数据为正整数，按按次体式格局存储与数组A中，对比完全二叉树缺失结点的地方存0.编写C言语函数intCount（intA[]）计算二叉树中非叶子结点的数目。第1页共4页三峡大学2016年研究生入学考试试题(A卷)科目代码：838科目名称：数据结构考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、选择题(每题3分，共60分)1、数据在存储器内表示时，物理地址与逻辑地址相同且连续，称为（）。A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构2、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。A.110B.108C.100D.1203、栈中元素的进出原则是（）。A.先进先出B.后进先出C.栈空则进D.栈满则出4、如下陈述中正确的是（）。A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串5、设有一个二维数B[m][n]，假设B[0][0]存放位置在544，B[2][2]存放位置在576，每个元素占一个空间，B[5][5]在（）位置。A.592B.586C.624D.6086、设5个字符的频度分别为1,2,3,4,5，其哈夫曼树的带权途径长度为（）。A.34B.33C.35D.377、链式存储的存储布局所占存储空间：（）。A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值第2页C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数8、下述几种排序方法中，要求内存最大的是（）。A．插入排序B．快速排序C．归并排序D．选择排序9、二叉树长短线性数据布局，关于它的存储，以下哪个描述精确（）。A．它不克不及用按次存储布局存储B．按次存储布局和链式存储布局都能存储C．按次存储布局和链式存储布局都不克不及利用D．它不克不及用链式存储布局存储10、用改进的起泡排序算法对n个元素举行排序时最多比力次数为()。A.nB.n-1C.n2D.n(n-1)/211、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…,pn,若p1=n，则pi为（）。A.iB.n=iC.n-i+1D.不确定12、若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为（）。A.79,46,56,38,40,84B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,3813、线性表Ｌ在什么情况下适用于使用链式结构实现（）。A．需经常修改Ｌ中的结点值B．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点D．Ｌ中结点结构复杂14、向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动多少个元素（）。A．8B．62C．63D．6415、深度优先遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.条理遍历16、任何一个无向连通图的最小生成树（）。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在第3页17、有7个结点的无向图最多有多少条边（）。A.14B.28C.56D.2118、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中哪些元素比较大小，查找结果是失败（）。A.20，70，30，50B.30，88，70，50C.20，50D.30，88，5019、链表适用于哪种查找（）。A.按次B.二分法C.按次，也能二分法D.随机20、把一棵树转换为二叉树后，这棵二叉树具有什么样的形态特征（）。A.是唯独的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子二、填空题(每小题2分，共30分)1、快速排序的平均时间复杂度是，它在最坏情况下的时间复杂度是。（要求用大O表示法表示）2、一棵具有257个结点的完全二叉树，它的深度为。3、已知一采用空闲单元法的循环队列容量为20，队列的首、尾指针分别用f和r表示，f＝3，r＝18时队列的长度为，f＝15，r＝7时队列的长度为。4、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。5、如果一棵完全二叉树具有500个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只要非空左子树，有个结点只要非空右子树。6、由3个结点所构成的二叉树有种形态。7、在对一组记实（54，38，96，23，15，72，60，45，83）举行间接插入排序时，当把第7个记实60插入到有序表时，为了寻觅插入位置至少需要比力次。8、稠密图适合采用存储布局。第4页3、综合题(共60分)1、描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？（15分）2、根据下图回答问题（15分）V2a1=3a3=4V1a4=2a2=2V3a5=6V5a9=5V4a7=4a6=5V7a10=3V6a8=5（1）要完成该AOE网中工程，最短时间是多少？（不考虑单位）（5分）（2）上图中的关键路径是什么（用顶点序列表示）？将活动a10的时间改成2能否提前完成？（5分）（3）若忽略边的权值将上图看成一个AOV网，并约定当存在多个入度为的结点时先输出编号较小的结点，则请写出拓扑排序结果。（5分）3、假设用于通的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。（15分）4、已知一棵度为k的树中有n1个度为1的结点，n2n6个度为6的结点，则该树中有多少个叶子结点，并证明。（5分）5、请对下图的无向带权图,要求写出详细过程：（10分）（1）按普里姆算法求其最小天生树；（从极点a开始）（5分）（2）按克鲁斯卡尔算法求其最小生成树。（5分）三峡大学2017年研究生入学考试试题(A卷)科目代码：836科目名称：数据结构考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、填空题（每空2分，共20分）1）__________是组成数据的基本单位，是数据集合的个体。2）数据布局的存储布局分为按次存储布局和__________两种。3）以下程序段:for(i=1;i<=9;i++)for(j=i+1;j<=10;j++)x++;个中语句x++履行的次数为__________。4)在带头结点循环单链表L（L同时透露表现头指针，结点指针域用next透露表现）中，判断指针p所指结点是否为表尾结点的条件是__________。5）当两个对顶栈共享一个存储区时，可利用一维数组stack[M]实现（下标从到M-1），两个栈的栈顶指针分别为top[1]和top[2]，则栈满的条件是__________。6）若用一个大小为6的数组来实现循环队列，且当前的rear和front的值分别为和3，当从队列中删除2个元素后，再加入3个元素后，rear的值为______。7）设一个哈希表表长M为200，用除留余数法构造哈希函数，及H（K）=K%P，为使函数具有较好机能，P应选_________。8）在树布局中，一个结点的子树个数称为此结点的_________。9）图遍历中的两种主要遍历方法分别是_________和广度优先搜索。10）为肯定数据元素在列表中的位置，需和给定值举行比力的枢纽字个数的盼望值，称为查找算法在查找成功时的_________。第2页二、单项选择题（每小题3分，共30分）1）有一个带头结点的单链表L，则判断其是否为空链表的条件是（）A.L==NULLB.L->next==NULLC.L->next==LD.L!=NULL2）若线性表最经常利用的操纵是存取第i个元素及其先驱的值，可采用（）存储体式格局最节流工夫。A.单向链表B.双向链表C.单向循环链表D.顺序表3）某个栈的入栈的序列为A,B,C,D,E,F,G，则可能的出栈序列为（）A.ABCDEFGB.GABCDEFC.DCBAGEFD.BAFDCEG4）评价一个算法性能好坏的重要标准是（）A.算法易于调试B.算法易于理解C.算法的精确性D.算法的工夫复杂度5）已知哈希表的长度m=20，哈希函数H(key)=key%19，关键字为k的记录在定位时产生了冲突，若采用开放定址解决冲突，则新地址的计算公式为（）A.(H(k)+di)%20C.(H(k)+di)/19B.(H(k)+di)%19D.(H(k)+di)/206）栈和队列的共同特点是（）A.只允许在端点处插入和删除元素B.都是先进后出C.都是后进先出D.没有共同点7）以下数据结构中哪一个是非线性结构？（）A.队列B.栈C.线性表D.二叉树8）链表不具备的特点是（）A.可随机访问任一结点B.插入删除不需要移动元素C.不用事先估计存储空间D.所需空间与其长度成反比9）与单链表相比，双链表的长处之一是（）A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活10）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）A.O(0)B.O(1)C.O(n)D.O(n2)第3页三、简答题（每小题10分，共50分）1、给出四种根本数据布局称号及其干系图示。2、数据结构研究内容主要包括数据的逻辑结构和数据的物理结构。请分别简述逻辑布局和物理布局的含义，并扼要指出线性表的两种常见物理布局。3、一棵二叉树的中序序列和后序序列分别以下，请画出该二叉树。中序序列：DIGJLKBAECHF后序序列：ILKJGDBEHFCA4、给定表（19，14，22，15，20，21，56，10）1）按元素在表中的次序，建立一棵二叉排序树；2）对1）中所建立的二叉排序树进行中序遍历，写出遍历序列；5、已知一维数组中的数据为（18，12，25，53，18），1）试写出插入排序（升序）过程，2）并指出具有n个元素的插入排序的工夫复杂度是几何？4、组织题（共30分）1、对以下枢纽字序列建立一个长度为20的哈希表（ZuoPing,ZuoWencheng,LiuJinqiao,LiMengting,LiWeiwen,ZhuZequn,WanQiubo），哈希函数为H(K)=(K中第一个字母在字母表中的序号)%19，用线性探测法解决冲突。要求给出如下结果：1）计算出每个关键字对应的哈希地址，如果有冲突，需要给出线性探测法解决冲突后的哈希地址。需要给出每个哈希地址的计算过程，并绘制构造好的哈希表。2）计算在等几率情形下查找成功时的均匀查找长度。五、编程美满程序（共20分）下列c语言编写的程序，主要完成如下功能：1）初始化三个带头结点的单链表La，Lb，Lc；2）连续读入一组整数（比如123-1-2-34-4-550），并将非零整数第4页依次存储在单链表La中（注意：碰到第一个结束输入）；3）将La分解成两个带头结点的单链表Lb和Lc，个中Lb中寄存负整数，Lc中寄存正整数。要求Lb和Lc利用La中的结点空间。4）在分解后，能表现Lb中所有的负整数，Lc中所有的正整数。请根据上述已知条件，并结合下面的代码，完成下面三个问题：1）在voidDisplayList(LinkListL)函数体中，写出代码，使之能显示单链表L中的数据元素；2）voidDivideList(LinkListLa,LinkListLb,LinkListLc)函数体中，写出代码，使之能将La分解成满足上述要求的Lb和Lc。3）假定在主函数中调用CreateFromTail(La)时，输入的整数系列是：123-1-2-34-4-550，请给出主函数调用DivideList(La,Lb,Lc);后，调用DisplayList(Lb);和DisplayList(Lc);后的屏幕输出结果。//----------------------------------------------代码-------------------------------------------------#include<stdio.h>#include<stdlib.h>#defineElemTypeintstructtag_node/*结点类型定义*/{ElemTypedata;structtag_node*next;};typedefstructtag_nodeNode;typedefstructtag_node*LinkList;voidInitList(LinkList*L);voidCreateFromTail(LinkListL);voidDisplayList(LinkListL);voidDivideList(LinkListLa,LinkListLb,LinkListLc);第5页main(){LinkListLa,Lb,Lc;InitList(&La);//初始化单链表LaInitList(&Lb);//初始化单链表LbInitList(&Lc);//初始化单链表Lcprintf("组织链表La:请输入一系列整数，并以输入整数竣事输入\n");CreateFromTail(La);//输入数据，构造单链表LaDivideList(La,Lb,Lc);//将La分解成Lb和Lcprintf("\nAfterdividing:");DisplayList(Lb);//显示LbDisplayList(Lc);//显示Lc}voidInitList(LinkList*L){*L=(LinkList)malloc(sizeof(Node));(*L)->next=NULL;}voidCreateFromTail(LinkListL){Node*r,*s;intc;intflag=1;r=L;while(flag)/*flag初值为1，当输入时，置flag为，建表结束*/{scanf("%d",&c);if(c!=0){s=(Node*)malloc(sizeof(Node));/*建立新结点s*/s->data=c;r->next=s;第6页r=s;}else{flag=0;s->next=NULL;}}}voidDisplayList(LinkListL){//请写出代码，实现表现单链表L中所有数据元素的功能//注意，答案写在答题纸上}voidDivideList(LinkListLa,LinkListLb,LinkListLc){//请写出代码，实现将La分解成两个带头结点的单链表Lb和Lc的功能//注意，答案写在答题纸上}//第3问的答案也写在答题纸上三峡大学2019年硕士研究生入学测验试题(A卷)科目代码：836科目称号：数据布局考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、选择题(每题3分，共60分)1、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。A.110B.108C.100D.1202、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为（）。A.存储布局B.逻辑布局C.按次存储布局D.链式存储布局3、栈中元素的进出原则是（）。A.先进先出B.后进先出C.栈空则进D.栈满则出4、如下陈述中正确的是（）。A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空缺串5、设有一个二维数B[m][n]，假设B[0][0]存放位置在544，B[2][2]存放位置在576，每个元素占一个空间，B[5][5]在（）位置。A.592B.586C.624D.6086、设有5个字符出现的频度分别为1,2,3,4,5，则对应的哈夫曼树的带权路径长度为（）。A.34B.33C.35D.377、链接存储的存储结构所占存储空间：（）。A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值第2页C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数8、下述几种排序方法中，要求内存最大的是（）。A．插入排序B．快速排序C．归并排序D．选择排序9、二叉树长短线性数据布局，关于它的存储，以下哪个描述精确（）。A．它不克不及用按次存储布局存储B．按次存储布局和链式存储布局都能存储C．按次存储布局和链式存储布局都不克不及利用D．它不克不及用链式存储布局存储10、一组记实的枢纽字为{46,79,56,38,40,84}，利用快速排序的办法，以第一个记实为基准取得的一次划分结果为()。A.{38,40,46,56,79,84}B.{40,38,46,79,56,84}C.{40,38,46,56,79,84}D.{40,38,46,84,56,79}11、若一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…,pn,若p1=n，则pi为（）。A.iB.n=iC.n-i+1D.不确定12、若一组记实的排序码为{46,79,56,38,40,84}，则利用堆排序的办法建立的初始堆为（）。A.{79,46,56,38,40,84}B.{84,79,56,38,40,46}C.{84,79,56,46,40,38}D.{84,56,79,40,46,38}13、线性表Ｌ在什么情形下合用于利用链式布局实现（）。A．需常常修改Ｌ中的结点值B．需不竭对Ｌ举行删除插入C．Ｌ中含有大量的结点D．Ｌ中结点结构复杂14、向一个有128个元素的按次表中插入一个新元素并保持原先按次稳定，均匀要移动几何个元素（）。A．8B．62C．63D．6415、深度优先遍历相似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历16、任何一个无向连通图的最小天生树（）。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在第3页17、有8个结点的无向图最多有几何条边（）。A.14B.28C.56D.2818、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中哪些元素比较大小，查找结果是失败（）。A.20，70，30，50B.30，88，70，50C.20，50D.30，88，5019、链表适用于哪种查找（）。A.按次B.二分法C.按次，也能二分法D.随机20、把一棵树转换为二叉树后，这棵二叉树具有什么样的形态特征（）。A.是唯独的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子二、填空题(每空2分，共30分)1、快速排序的平均时间复杂度是，它在最坏情况下的时间复杂度是。（要求用大O表示法表示）2、一棵具有257个结点的完全二叉树，它的深度为。3、已知一个采用空闲单元法的循环队列容量为20，队列的首、尾指针分别用f和r表示，f＝3，r＝18时队列的长度为，f＝15，r＝7时队列的长度为。4、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。5、如果一棵完全二叉树具有500个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只要非空左子树，有个结点只要非空右子树。6、由3个结点所构成的二叉树有种形态。7、在对一组记实（54，38，96，23，15，72，60，45，83）举行间接插入排序时，当把第7个记实60插入到有序表时，为了寻觅插入位置至少需要比力次。8、稠密图适合采用存储结构。第4页三、综合题(共60分)1、描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？（10分）2、给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树，并给出后序遍历序列。（10分）3、已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？（10分）4、当输入为abc#时，写出调用pr函数的输出结果。（10分）voidpr(){charch;scanf(“%c”,&ch);if(ch!=‘#’)pr();printf(“%c”,ch);}5、请对下图的无向带权图：（10分）（1）按普里姆算法求其最小生成树；（从顶点a开始）（5分）（2）按克鲁斯卡尔算法求其最小天生树。（5分）要求写出详细过程6、已知一棵度为k的树中有n1个度为1的结点，n26个度为6的结点，则该树中有几何个叶子结点，并证明。（10分）第1页共4页三峡大学2014年研究生入学考试试题(A卷)科目代码：938科目称号：数据布局（考生必须将答案写在答题纸上，总分150分，考试时间180分钟）一、选择题(每题3分，共60分)1、线性表采用链式存储时，结点的存储地点（）。A.必须是不继续的B.继续与否都可C.必须是继续的D.和头结点的存储地点相继续2、已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行（）操作。A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s->next;s->next=pD.p->next=s;s->next=q3、设有一个按次栈S,元素按S1,S2,S3,S4,S5,S6按次进栈，若6个元素的出栈按次为S2,S3,S4,S6,S5,S1,则按次栈的容量至少应为（）。A.2B.3C.4D.54、设有两个串p和q，求q在p中首次呈现的位置的运算称作（）。A.毗连B.形式匹配C.求子串D.求串长5、设有一个二维数A[m][n]，假设A[0][0]寄存位置在544，A[5][5]寄存位置在624，每个元素占一个空间，A[2][2]在（）位置。A.592B.586C.576D.6086、设有5个字符呈现的频度分别为2,7,5,4，则对应的哈夫曼树的带权途径长度为（）。A.34B.33C.35D.157、含n个顶点和e条边的无向图的邻接矩阵中非零元素的个数为（）。A.eB.2eC.n2-eD.n2-2e第2页8、长度为500的有序表采用折半查找时，查找成功最大比较次数为（）。A.8B.9C.10D.119、快速排序在下列哪种情况下最易发挥其长处（）。A.被排序的数据中含有多个不异排序码B.被排序的数据已根本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差差异10、下列枢纽字序列中，（）是堆。A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94，31,72D.16,23,53,31,94,7211、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…,pn,若p1=n，则pi为（）。A.iB.n=iC.n-i+1D.不肯定12、一棵具有257个结点的完全二叉树，它的深度为（）。。A.7B.8C.9D.1014、用毗邻表透露表现图举行广度优先遍用时，平日是采用（）这类数据布局来实现算法的。A.栈B.队列C.树D.图15、深度优先遍历相似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历16、有8个结点的无向图最多有（）条边。A.14B.28C.56D.11217、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将顺次与表中哪些元素比力大小，查找结果是失利。（）A.20，70，30，50B.30，88，70，50C.20，50D.30，88，50第3页18、