南京林业大学考研真题-数据结构2004

朽木易折，金石可镂。千里之行，始于足下。第页/共页南京林业大学2004年攻读硕士学位研究生入学考试数据结构试题注重事项：1.答案一律写在答题纸上；2.答案卷应字迹清晰、语义确切；3.算法应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，可加上须要的注释；4.算法可用（类）PASCAL语言、C语言等你所认识的高级语言编写，但要注明语种。单项挑选题（本大题共15小题，每小题2分，共30分）算法指的是（）。A．计算机程序B．解决问题的计算主意C．排序算法D．解决问题的有限运算序列线性表采用链式存储时，结点的存储地址（）。A．必须是不延续的B．部分地址必须是延续的C．延续与否均可D．和头结点的存储地址相延续若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为s1,s2,s3,…sn,若s1=n,则si为（）。A．iB．n=iC．n-i+1D．以上都不对算法的时光复杂度取决于（）。A．问题的规模B．待处理数据的初态C．A与B都对D．算法的易读性将两个各有n1和n2个元素的有序表(递增)归并成一个有序表，仍保持其递增顺序，则最少的比较次数是（）。A．n1B．n2C．n1+n2-1D．min(n1,n2)一个非空广义表的表头（）。A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子深度为6的二叉树至多有（）个结点。A．32B．40C．63D．64下面哪一个主意可以判断出一个有向图中是否有环（回路）（）。A．广度优先遍历B．拓朴排序

C．求最短路径D．求关键路径按照二叉树的定义，具有3个结点的二叉树有()种。A．3B．4C．5D．6在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。A．eB．2eC．n2－eD．n2－2e某二叉树的先序序列和后序序列正巧相反，则该二叉树一定是()的二叉树。A．空或惟独一个结点B．任一结点惟独左孩子

C．高度等于其结点数D．任一结点惟独右孩子一个具有n个顶点的无向图最多有()条边。A．nB．n(n-1)C．n(n-1)/2D．2n用某种排序主意对关键字序列（25，84，21，47，15，27，68，35，20）举行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序主意是（）。A．挑选排序B．希尔排序C．归并排序D．迅速排序假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时光复杂度是()。A．O(n)B．O(e)C．O(n+e)D．O(n*e)下述二叉树中,哪一种满意性质：从随意结点出发到根的路径上所经过的结点序列按其关键字有序：（）。A．哈夫曼树B．AVL树C．堆D．二叉排序树填空题：（本大题共15小题，每小题2分，若有两个空格，每个空格1分，共30分）1．评价算法的效率性能从利用计算机资源角度看主要从和两个方面举行分析。2．有一个含头结点的单重循环链表，头指针为head,则判断其是否为空的条件为：。3．用数组Queue（其下标在0～n-1中，共有n个元素）表示一个循环队列，front为当前队头元素的前一位置，rear为队尾元素的位置。假定队列中元素个数总小于n，则队列中元素个数为：。4．设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b,d,c,f,e,a,则栈S的容量至少应该是。5．设n行n列的上三角矩阵A已压缩存储到一维数组B[1..n*(n+1)/2]中，且按行为主序存储，则aij对应的B中的存储位置为。6．从任何一个结点开始都能胜利寻找其他结点的单链表是表。7．设SS[1..maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，当栈未满时，将元素e压入栈需执行下列语句：和。8．所有结点的前驱和后继的个数都没有限制的数据结构是结构。9．若一个二叉树的叶子结点，是某子树的中序遍历序列中的最后一个结点，则它必是该子树的序列中的最后一个结点。10．用二分法寻找一个线性表时，要求线性表必须以方式存储，且

。11．采用散列法实现寻找时，需要解决的主要问题有：和。12．设广义表L=（（（a））），则该广义表的长度是，深度是。13．有向图G有n个顶点{v1,v2,…,vn}，它的邻接矩阵为A，A[i,j]=1表示vi到vj存在邻接关系，而A[i,j]=0表示不存在邻接关系。则G中顶点vi的度为。14．n个顶点的有向强连通图用邻接矩阵表示时，该矩阵至少有个非零元素。15．若一个二叉树含有n个结点，则它的二叉链表中必有个空的链域。是非题：（判断下列各题是否准确，准确的在括号内打

“√”，错的打“×”。每小题2分，共20分）1．线性表的逻辑顺序与存储顺序总是一致的。（）2．消除递归不一定需要使用栈。（）3．队列是后进先出的线性表。（）4．任何一个数据结构至少有一个结点没有前驱。（）5．将一棵树转换成二叉树后，根结点没有左子树。（）6．若采用以行序为主序三元组表示法存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（）7．对于不同的存储结构，应采用不同的检索主意。（）8．倘若一个二叉树中没有度为1的结点，则必为满二叉树。（）9．树和二叉树的逻辑结构是一致的。（）10．不仅需要使用内存，而且还要使用外存的排序称为外排序。（）解答题：（本大题共5小题，每小题4分，共20分）1．将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树。(注：括号无需在树中浮上)2．子串的定位运算通常称为串的模式匹配，是各种串处理系统中最重要的运算之一，其中KMP匹配算法是效率较高的主意。请问KMP匹配算法的基本思想是什么？求字符串’ababaababcabb’的NEXT数组。3．假设用下述两种结点的链表作广义表的存储结构：tag=1hp(表头指针)tp(表尾指针)表结点tag=0data(值域)原子结点试画出广义表LA=((((a),b)),(((),(d)),(e,f)))的存储结构。4．（1）若一棵二叉树先序遍历与中序遍历的次序分离为:先序序列:ABDEHCFGI；中序序列：DBEHAFCIG。试画出这棵二叉树。（2）给出二叉树的先序和中序序列、中序和后序序列、先序和后序序列。试问是否在任何情况下都可决定唯一的一棵二叉树；若有不能者，请举出一个反例说明之。5．设有向图G为：VV1V3V4V2写出所有的拓朴序列；在图中添加一条弧，使得仅可能有唯一的拓朴序列。算法阅读题：（本大题共2小题，每小题5分，共10分）1．设有算法如下:typedefintKeyType;typedefstruct{KeyTypekey;OtherTypeother_data;}ListType;voidfunction(ListTypeR[],intlength){inti,j;for(i=2;i<length;i++){R[0]=R[i];j=i-1;while(R[0].key<R[j].key){R[j+1]=R[j];j=j-1;}R[j+1]=R[0];}}请回答下面两个问题：（1）该算法的功能是什么？（2）这个算法是否稳定？并请说明你的理由。2．设有算法如下：#defineNULL0typedefstructnode{KeyTypekey;structnode*lchild,*rchild;}BSN,*BST;voidunknown(BST*bs,KeyTypekey){BSTs;

if(*bs==NULL){s=(BST)malloc(sizeof(BSN));s->key=key;s->lchild=NULL;s->rchild=NULL;*bs=s;}elseif(key==(*bs)->key)printf(“Thenodeexistsinthebinarytree!”);

elseif(key<(*bs)->key)

unknown(&((*bs)->lchild),key);

else

unknown(&((*bs)->rchild),key);}函数unknown实现了对二叉排序树的一种运算；（1）试说明unknown的功能。（2）若root是BST型变量，且root指向如下二叉树的根结点，试画出执行完unknown(root,‘X’)后，root指向的二叉树。WWRYAZroot六、算法设计题：（本大题共3小题，共４0分）１．已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT(抽象数据类型)函数和少量工作变量，编写一个算法，将队列Q中的所有元素逆置。（本题15分）其中：栈的ADT函数有：InitStack(S);将栈S初始化为空栈Push(S,x);新元素x进栈Pop(S,&x);出栈，返回栈顶值给xintIsEmpty(