江西师范大学计算机信息工程学院863数据结构与程序设计历年考研真题汇编附答案

江西师范大学2014年全日制硕士研究生入学考试试题专业：081200计算机科学与技术科目：863数据结构与程序设计注：考生答题时，请写在考点下发的答题纸上，写在本试题纸或其他答题纸上的一律无(本试题共计6页)一、单项选择题(每小题2分，共20分)1.在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动()个元素。2.已知循环队列的存储空间为数组data[21],且当前队列的头指针和尾指针的值分别为8和3,则该队列的当前长度为()。3.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是()。A.队列B.栈C.线性表D.有序表4.一棵含18个结点的二叉树的高度至少为()。5.非空的循环单链表head的尾结点(由p所指向)满足()。nextNULLBnextheadCNULLDhead(f,d),(e,d)},对该图进行深度优先遍历，得到的顶点序列正确的是()。7.对于哈希函数H(key)=key%13,被称为同义词的关键字是()。8.下列说法错误的是()。A.冒泡排序在数据有序的情况下具有最少的比较次数。B.直接插入排序在数据有序的情况下具有最少的比较次数。C.二路归并排序需要借助O(n)的存储空间。D.基数排序适合于实型数据的排序。9.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为()。A.插入排序B.归并排序C.冒泡排序D.堆排序10.设二叉排序树中关键字由1至1000的整数构成，现要检索关键字为363的结点，下述关键字序列哪一个不可能是二叉排序树上搜索到的序列()。1.若一个算法中的语句频度之和为T(n)=10n+2nlog₂n,则算法的时间复杂度为2.如果入栈序列是1,3,5,…,97,99,且出栈序列的第一个元素为99,则出栈序列中第30个元素为3.某二叉树的先根遍历序列为ABDC,中根遍历序列为BDAC,则该二叉树根结点的右4.若对序列(15,2,48,60,89,25)采用二路归并法升序排序，则进行一趙归并后产生的序列为。5.算术表达式a*(b+c)-d的对应的后缀表达式是。6.假设一个6阶的下三角矩阵B按列优先顺序压缩存储在一维数组A中，其中A[0]存储矩阵的第一个元素bu,则A[14]存储的元素是。7.顺序循环队列中(数组的大小为n),队头指示front指向队列的第1个元素，队尾指示rear指向队列最后元素的后1个位置，则循环队列中存放了n-1个元素，即循环队列满的条件为8.在含100个结点的完全二叉树中，叶子结点的个数为。9.包含有n个顶点的有向强连通图最多条边。10.如下图所示的有向无环图可以排出种不同的拓扑序列。1.阅读下面的递归程序，写出程序的运行结果。if(n>=1)11typedefintdatatype;typedefstructnodetypedefbintnode*bintree;if(*t==NULL)return;elseiflchildNULLrchildNULLrettypedefintdatatype;typedefstructnodetypedeflinknodelinkl ; 四、解答题(每小题10分，共40分)小堆)的过程。(1)写出从结点0出发深度优先遍历序列；(2)画出从0结点出发用Prim方法建立最小生成树的过程图示。012345五、算法与程序设计题(第1、2题每小题14分，第3小题18分，共46分)答题要求：根据设计思想和实现步骤，采用C语言写出对应的算法程序，关键之处序树。081200计算机科学与技术081200计算机科学与技术数据结构与程序设计江西师范大学2013年全日制硕士研究生入学考试试题注：考生答题时，请写在考点下发的答题纸上，写在本试题纸或其他答题纸上的一律无效。(本试题共计7页)一、单项选择题(每小题2分，共20分)1.若将数据结构形式定义为二元组(K,R),其中K是数据元素的有限集合，则RA.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合2.以下算法的时间复杂度为()}2.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为()3.若要在单链表中的结点*p之后插入一个结点*s,则应执行的语句是()A.nextnextnextnextnextnext4.操作系统为实现函数嵌套调用的管理，通常需要设立一个存储区，记录函数调用转移的断点，该存储区的逻辑结构是()5.对于一棵具有n个结点，度为4的树来说，()A.树的高度至多是n-3B.树的高度至多是n-4C.第i层至多有4(i-1)个节点D.至少在某一层上正好有4个节点6.下列二叉树中，不平衡的二叉树是()Dn个顶点的强连通图中至少含有()A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边.已知一个有向图如下所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为().用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时，序列的变化情况如下：则所采用的排序方法是()A.选择排序B.希尔排序C.归并排序D.快速排序0.在最好和最坏情况下的时间复杂度均为O(nlog₂n)且稳定的排序方法是()A.快速排序B.堆排序C.归并排序D.基数排序1.数据的逻辑结构在计算机存储器内的表示，称为数据的。2.已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的结点。5.假设一个6阶的下三角矩阵B按列优先顺序压缩存储在一维数组A中，其中A[0]6.在含100个结点的完全二叉树中，叶子结点的个数为7.在无向图中，若从顶点a到顶点b存在,则称a与b之间是连通的。10.在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为。三、程序填空与程序分析题(每小题6分，共24分)1.函数getprime()的功能是将2到100之间的所有素数存入数组a,并返回所存入的if(j>k)1;//函数调用2.字符串采用带头结点的单链表存储，其结构定义如下：函数index(t,s)的功能是求子串s在主串t中的第一次出现的起始位置，如果s不在t中，则返回NULL,请将程序补充完整。/*r指示主串t当前比较的位置*//*q指示子串s当前比较的位置*/}希尔排序(shell)过程可表示如下，请将其补充完整。j=i-d;j=j-d;} }typedefchardatatype;typedefbintnode*bintree;typedefstructstack(1)画出此二叉树；(2)写出该二叉树的后序遍历结果。2.序列{12,18,33,29,35,92,88,36}是否构成大根堆(最大堆),如不够成，110,111,00,0111和010。(2)若这些字符在电文中出现的频度分别为：3,35,13,15,20,5和9,求该哈简要注释。(1)创建该图的邻接表(出边表)表示；(2)输出该图中出度最大的结点值。北京航空航天大学2013年数据结构与C语言程序设计考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的答题一律无效(本题单不参与阅卷)。一、单项选择题(本题共20分，每小题各2分)1.对于长度为n的线性表，建立其对应的单链表的时间复杂度为。2.一般情况下，在一个双向链表中插入一个新的链结点，。A.需要修改4个指针域内的指针；B.需要修改3个指针域内的指针；C.需要修改2个指针域内的指针；D.只需要修改1个指针域内的指针。3.假设用单个字母表示中缀表达式中的一个运算数(或称运算对象),并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*(C/D-E),当从左至右扫描到运算数E时，堆栈中的运算符依次是。(注：不包含表达式的分界符)4.若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70,则后序遍历序列D.70,60,80,30,40,20,50。5.分别以6,3,8,12,5,7对应叶结点的权值构造的哈夫曼(Huffman)树的深度6.下列关于图的叙述中，错误的是。A.根据图的定义，图中至少有一个顶点；9.在一棵m阶B-树中，除根结点之外的任何分支结点包含关键字的个数至少是。是A.(13,27,49',38,49,76,97,6B.(13,38,27,49',49,76,9C.(13,38,49',27,49,97,76,65);D.(13,38,49',27,49,76,97,65)。3.若完全二叉树的叶结点的数目为k,且最下面一层的结点数大于1,则该完全二4.若深度为8的完全二叉树的第7层有10个叶结点，则该二叉树的结点总数5.在具有n个顶点的有向图中，每个顶点的度最大可以达到。6.若对有向图进行拓扑排序，则能够得到拓扑序列的条件是。7.已知长度为10的顺序表中数据元素按值从小到大排列。若在该表中进行折半查8.若在一棵m阶B-树的某个结点中插入一个新的关键字值而引起结点产生分裂，则该结点中原有的关键字值的数目是。9.有一种排序方法可能会出现这种情况：最后一趟排序开始之前，序列中所有的元素都不在其最终应该在的位置上，这种排序方法是。10.若按照泡排序法的思想将序列(2,12,16,5,10)中元素按值整个排序过程中所进行的元素之间的比较次数为三、综合题(本题共20分，每小题各5分)问：这三种方案之间相比较各有什么优点和缺点?(1)多个堆栈共享一个连续的存储空间；(2)分别建立多个采用顺序存储结构的堆栈；(3)分别建立多个采用链式存储结构的堆栈。2.已知二叉树采用二叉链表存储结构，根结点指针为T,链结点类型定义为：typedefstructnode{/*数据域*//*指向左、右子树的指针域*/3.对给定AOE网(如题三3图所示),请完成(1)分别求出各活动a(i=1,2,…,14)的最早开始时间与最晚开始时间；(请以表格(2)求出所有关键路径。(请以图形方式画出各关键路径)(1)请利用除留余数法构造出合适的散列函数；(2)请画出利用该散列函数依次将序列中各关键字值插入到散列表以后表的状态。四、算法设计题(本题15分)中数据元素按值从小到大进行排序的算法：第1趟排序将最小值元素放在A[1]中，最大值元素放在A[n]中；第2趟排序将次小值元素放在A[2]中，次大值元素放在A[n-l]五、填空题(本题共20分，每小题各2分)1.已知某等比数列的第一项a;为1,公比为3,下列程序的功能是输出该数列中小于1000的最大项an及其对应的n。 f}的元素是否按值从小到大排列。若是一个递增数组，则函数返回true,否则，函数返 }for(i=0;i<N;i++){}}FUNC3(a,&x,&y);/*x,y中分别存放主对角线与副对角线上的元素之和*/printf(“%d,%d\n”,x,y)}4.下列程序的功能是先通过键盘输入一正整数，然后调用一递归函数FUNC4,该函数将正整数转换为对应的数字字符组成的字符串显示在屏幕上。例如：若输入的正整数为583,则屏幕上显示的是字符串583。请在程序的空白处(方框内)填入合适内容，使程序完整。if}}5.下列程序的功能是将小写字母转换成对应的大写字母后的第2个字母，例如：将a转换成C,将b转换成D,其中，y转换成A,z转换成B。while((ch=getchar())!}6.下列函数FUNC6的功能是删除字符串s中的所有空白字符，包括Tab字符、回)strcpy(s,c);}break}}}}}六、简答题(本题共20分，每小题各5分)七、程序设计题(本题15分)八、程序设计题(本题20分)北京航空航天大学2012年硕士研究生入学考试试题科目代码：991考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的答题一律无效(本题单不参与阅卷)。一、填空题(本题共20分，每小题各2分)4.若一棵度为4的树中度为1、2、3和4的结点个数分别为4、2、1和1,则该树。否是稀疏矩阵?为什么?(这里我们假设：当矩阵中非零元素的数目小于整个矩阵总素的数目的5%时认为该矩阵为稀疏矩阵)/*第1条语句*1/*第2条语句*//*第3条语句*1/*第4条语句*3.证明：具有n个顶点的无向图最多有nx(n-1)/2条边。四、算法设计题(本题15分)已知某具有n个顶点的有向图采用邻接表方法存储，其中，用以存储有向边信息的typedefstructedge{intadjvex;/*某有向边的终止顶点在顶点结点中的位置*/structedge"next;/*指向下一个边结点*/用以存储顶点信息的顶点结点类型为typedefstructver{intindegree;/*某顶点的入度*/vertypevertex;/*某顶点的数据信息*/ELink*link;/*指向以该顶点为出发点的第一个边结点并且n个顶点结点构成一个数组结构G[0.n-1]。请写一个算法，该算法判断给定的顶点扑序列，算法返回1,否则，算法返回0。五、单项选择题(本题共20分，每小题各2分)C.必须是字母或者下划线D.可以是字母、数字和下划线之一2.若整型变量x的初值为6,则计算表达式“x+=x-=x*x”之后，x的值是。3.下列4个程序段中，不是无限循环的是。A.N个指向double类型变量的指针D.具有N个指针元素的一维指针数组，其每一个元素都只能指向double类5.下列4个叙述中，正确的是A.对函数func的定义B.对函数func的调用p=(char*)malloc(sizeof(char)*}D.各成员所需内存量的总和}10.若要以a+方式打开一个已经存在的文件，则下列叙述中，正确的是。行添加和读操作行重写和读操作C.文件被打开时，原有的文件内容被删除，只能进行写操作D.以上三种说法都不正确六、简答题(本题共20分，每小题各5分)3.在C语言中，全局变量和局部变量的主要区别是什么为什么?七、填空题(本题共20分，每小题各2分)1.下列代码的功能包括：定义一个x数组，说明一个结构体，同时对变量t进行初始化，使得t的a成员的值为50,b成员的值为x数组的首地址。请在空白处(方框内)填入合适的内容，以完成上述功能。2.下列函数的功能是根据公式计算s的值，其中，n通过形参传入(n≥0),计算结果通过形参指针传回。请在函数的空白处(方框内)填入合适的内容，使函数完整。①}鼠外的升文表，中言哥)苏3.下列程序实现将输入的一个小写字母循环后移5个位置后输出。例如，若输入字请在程序的空白处(方框内)填入合适的内容，使程序完整。4.下列自定义函数的功能是实现两个字符串的比较。请在函数的空白处(方框内)填入合适的内容，使函数完整。 while(*s&&*t&&*s==①}5.下列程序的功能是将已经按升序排好序的两个字符串str1和str2中的字符再按升请在程序的空白处(方框内)填入合适的内容，使程序完整。①{ } 情箭书文的望类anol回效(AJ)lf*}ptr2--;11printf("position=%ld\n"position八、程序设计题(本题15分)请编写一C语言程序，该程序的功能是确定字符串中首次出现的某字符在串中的位置(即该字符是字符串中的第几个字符),然后从字符串中删除该字符。要求：的位置，删除该字符(注：不考虑非首次出现的该字符的删除),并且显示删除前后的字②通过键盘输入字符串以及被确定的字符。题单上的答题一律无效(本题单不参与阅卷)。一、单项选择题(本题共20分，每小题各2分)A.线性表的顺序存储结构中隐式地存储了数据元素之间的逻辑关系B.线性表的顺序存储结构一定需要占用一片地址连续的存储空间C.线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系2.若front和rear分别表示链接队列的队入一个由p指的新元素的过程是依次执行A.二叉树的度可以小于2B.二叉树的度等于2C.二叉树中至少有一个结点的度为2D.二叉树中每一个结点的度都为24.若某二叉树有40个叶结点，则该二叉树的结点总数最少是5.若采用邻接矩阵存储一个有向图，且邻接矩阵主对角线以下元素均为0,则该有向图的拓扑序列。C.不存在D.无法确定A.AOE网是一个带权的连通图B.AOE网是一个带权的强连通图A.顺序查找法适合于采用顺序存储结构和链式存储结构的线性表的查找B.对于相同元素，顺序查找法一定能够查找到表中首次出现的元素C.对于相同元素，折半查找法一定能够查找到表中首次出现的元素8.在二叉排序树中进行查找的平均时间效率主要与下列因素之一有关，该C.被查找结点的度D.二叉排序树的存储结构9.下列4种排序方法中，每一趟排序结束时不一定能够确定一个元素排序A.插入排序B.快速排序10.下列4种排序方法中，当待排序的序列中元素初始时已经按值有序，排二、简答题(本题共20分，每小题各5分)1.等概率情况下，在长度为n的顺序表中插入和删除一个数据元素分别需要平均移动多少个元素?移动的元素个数主要取决于哪几个因素?适?为什么?接矩阵存储方法和邻接表存储方法哪一种更合适?为什么?4.什么是小顶堆积(Heap)?在小顶堆积中，值最大的元素可能处在什么位置?(可以借助一棵二叉树描述)三、综合题(本题共20分，每小题各5分)1.下列算法的功能是删除长度为n的顺序表A中重复出现的多余元素，即j=i+1;/*从第i+1个元素开始逐个与第i个元素比较*/n--;/*修改表的长度*/②3.已知某3阶B树如题三3图所示，请画出在该B3.已知某3阶B树如题三3图所示，请画出在该B树中插入关键字20以后得到的B树。2.请将由题三2图给定的树转换为一棵二叉树。题三2图题三3图其中，叶结点的data域中已经存放了该叶结点对应的权值。请写一非递归算法，五、程序阅读题(本题共20分，每小题各2分)do{3.下列程序的输出结果是。4.下列程序的输出结果是。printf("%d\n",strlen(strcat(strl,str2}p=a,printf(“%d\n”,*(++p)6.下列程序的输出结果是printf(“%c%c%c”,*s,*(s+1),*s+18.下列程序的输出结果是。printf(“%d\n”,fun(fun(a+c,b),a-c))9.下列程序的输出结果是}if(infopenfileltxtNULLwhile(*str1!='.")if((infopenfileltxtNULL六、填空题(本题共20分，每小题各4分)dd3.下列程序段的功能是计算1000!的末尾含有多少个零。请在程序段的空白处填上必要的内容，使程序段完整。(提示：只要计算出1000!中含有因数5的个数即可)*b=&y;①while((ch=getchar())fprintf(③七、程序设计题(本题15分)请编写一C语言程序，该程序的功能是先通过键盘输入一个整数n,然后调八、程序设计题(本题20分)请设计一C语言函数(注：只须写出函数，不必写出完整程序),该函数的功素依次循环右移k个位置。例如，对于某数组，当k=3时(即把数组所有元素循环右移3个位置),是将1.已知双向循环链表的结点构造为1.已知双向循环链表的结点构造为,在链表中出指针q所指北航2010年硕士研究生入学考试试题-数据结构与C语言程序设计北京航空航天大学2010年硕士研究生入学考试试题科目代码：993考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的答题一律无效(本题单不参与阅卷)。一、单项选择题(本题共20分，每小题各2分)结点的后面插入指针为p的结点的过程是依次执行。A.p->llink=q;p->rlink-q->rlink;qr>rlinkllinkB.p->llink-q;p->rlink=q-rlinkrinkrlinkllinkepC.pe>llink=q;prlinkrlinkrlinkrlinkllinkD.p->llink=q;p->rlink-q->rlink;qriinkllinkllinkp2.对于采用链式存储结构的队列，在进行副除操作时,A.只需修改队头指针B.只需修改队尾指针C.队头指针和队尾指针都需要修改D.队头指针和队尾指针都可能需要修改3.将中缀表达式转换为等价的后缀表达式的过程中要利用堆栈保存运算符。对于中缀表达式A-(B+C/D)xE,当扫描读到操作数E时，堆栈中保存的运算符依次是4.若完全二叉树的第7层有10个叶结点，那么，该二叉树结点数目最大是,5.对于具有k条边的有向图，其对应的邻接表中边结点的数目为。6.通过拓扑排序能够得到拓扑序列的图一定是。二、简答题(本题共20分，每小题各5分)4.着某地区有10000名学生参加数学竞赛，只录取成绩优异的前10名，并将他们按三、综合题(本题共20分，每小题各5分)1B分别写出该有向图所有可能的拓扑序列，2CD题三、1图2.己知二叉树的中序遍历序列为C,A,D,F,B,E,按层次遍历序列为A,C,B,D,E,F,请画出该二又树。3.已知散列函数为H(k)=kMOD7,井采用线性探测再散列法处理冲突，请画出在下列散列表中依次插入关键字17,27以后的表的状态。4.请写出下列递归算法的功能。四、算法设计题(本题15分)已知非空二叉树采用二叉链表结构，链结点构造为,根结结点不是二叉树的根结点)的兄弟结点的算法。若二叉树中存在该兄弟结点，算法给出该兄弟结点的位置，否则，算法给出NULL。要求：写算法之前先用文字简要给出算法的核心思想。五、单项选择题(本题共20分，每小题各1分)1.在C语言中，要求参加运算的操作数必须是整数的运算符是,2.若变量x为整型，变量y为实型，变量i为双精度型，则表达式20**x'+i*y的值的A.intB.floatC.doubleD.不确定3.对于关系a<bSc,对应的C语言表达式应该是。9.9.若有定义：inta[10];,则对数组a元素的正确引用的是B.(a<b)AND(b<*c)C.(a<b<*c)D.(a<b)&(b<=c)4.以下关于输入的叙述中，正确的是A.只有格式控制，没有输入项，也能进行正确的输入，如scanf("x=%d,y=%d");B.当输入实型数据时，格式控制部分应规定小数点后的位数，如C.当输入数据时，必须指明变量的地址，如scanf("%f",&f);D.输入项可以是一个实型常量，如scanf("%f",3.14);5.对于以下程序段：此处的do-while循环的结束条件是A.s的值不等于100井且k的值小于3B.s的值等于100并且k的值大于等于3C.s的值不等于100或者k的值小于3D.s的值等于100或者k的值大于等于36.执行语句for(j=1:j++<4;);后变量j的值是