南京林业大学考研真题—数据结构2022

南京林业大学年攻读硕士学位研究生入学考试2022数据结构试题注意事项答案一律写在答题纸上；

1.答案卷应字迹清晰、语义切当；

2.算法应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，可加之必要的注释；

3.算法可用（类）语言、语言等你所熟悉的高级语言编写，但要注明语种

4.PASCAL C--是非题（判断列各题是否正确，正确的由舌号内打,错的打“每小题分，共5V220分））.数据的逻辑结构独立于计算机，物理结构依赖于计算机

（1）.线性表、栈和队列的逻辑结构彻底相同（2』褥存储方式只能用于存储线性结构（）

3.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的春4群勾（）.先根遍历树和先序遍历与该树对应的二叉树，其结果不同（）

5.外部排序与外部设备的特性无关（）

6.不使用递归，也可以实现二叉树的先序、中序和后序遍历（）

7.在哈夫曼编码中，当两个字符浮现的频率相同时，其编码也相同，对于这种情况应作特殊姐8里（）.有回路的图不能进行拓扑排序（）9）二叉排序树的查找和折半查找的时间性能相同（

10..二叉树采用链式存储结构，设计一个计算一棵给定二叉树深度的递归算法分36,对于一棵二叉排序树，设计分别满足如下条件的算法分410实现在二叉排序树上的查找操作若找到与给定数据值相等的结点，返回该结点的指针；1若未找到，返回空指针NULL实现在二叉排序树上的插入操作若上存在与给定数据值相等的结点，给出2BST Itis!〃信息，不插入；若上不存在与给定数据值相等的结点，则插入exist BST二.单项选择题本大题共小题，每小题分，共分

15230.规则集合结构运算A B.C.D..对于页序存储的线性表，设其长度为，在任何位置上插入或者删除操作都是等概率的2JII n插入一个元素时大约要挪移表中的个元素A.n/2B.n+l/2C.n-l/2D.n线性表采用链式存储时,其地址

3.o必须是连续的部份地址必须是连续的A.B.一定是不连续的连续与否均可以C.D..设有一个空栈，栈顶指针为十六进制,下同，且设每一个入栈元素需要个单位存储41000H1空间,现有输入序列为，经过1,2,3,4,5PUSH,PUSH,POP,PUSH,POP,PUSH,POP,后，栈顶指针是PUSH oA.1002H B.1003H C.1004H D.1005H

5.1等有关二叉树的概念推广到三叉树，则一棵有244个结点的彻底三叉树的高度是_____o.数组］的每一个元素占个字节，将臀列优先次序存储在起始地A.4B.5C.6D.76AO

50..65址为内存单元中,则元素的地址是1000A[5,5]oA.1175B.1180C.1205D.

1210.设森林对应的二叉树为有个结点，的根为的右子树结点个数为森林7F B,B mB p,p n,F中第一棵树的结点个数是____________.条件不足，无法确定A.m-n B.m-n+1C.n+1D.有个顶点的强连通图至少有条边8nA.n+1B.n C.n-1D.nn-l.堆是一种实用的数据结构以下关键字序列是一个堆9A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94,31,72D.16,23,53,31,94,

72.关键路径是网中10AOV从源点到汇点的最短路径.从源点到汇点的最长路径A.B.最长的回路最短的回路C D..折半查找的时间复杂度是11OA.On2B.on C.onlog nD.olog n

22.具有线性结构的数据结构是12树结构图结构广义表文件结构A.B.C.D.设无向图中顶点数为则图最多有条边

13.G n,GA.n B.n-1C.nn-l/2D.nn-l.设某有向图中有个顶点，条边，进行拓扑排序时总的时间复杂度为14n eoA.onlog eB.oe+n C.oelog nD.oe*n

22.不满足平衡查找树概念的是15o树树折半查找判定树树A.BST B.AVL C.D.B+三.填空题本大题共小题，每小题分，共分

10220.分析以下程序段的时间复杂度为用大记号表示执行时间为正整数的函数10nx=n;；y=oWhilex=y+l*y+1y++;.为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，2应将两栈的分别设在这片内存空间的两端，这样，惟独当时,才产生上溢.一个的对称矩阵，如果以相同的元只存储一次的原则进行压缩存储，则其压缩后的存储3n*n容量为广义表的长度为,深度为4•a,b,c,d,e,f,g,h一棵有出门＞个结点的~度树，若用多重链表表示,树中每一个结点都有个链域，则在

5.=1d树的个链域中，有个是空链域，惟独个是非空链域nd.若二叉树有个结点，当执行中序遍历的递归程序时，在最坏情况下为处理递归调用所设的6n栈需要个单元.一棵有个叶子结点的哈夫曼树上，其结点总数为7n,对于含有个顶点条边的无向连通图，算法合用于求网的最小代价生成树,8n eprim而算法合用于求网的最小代价生成树Kruskal

9.Dijkstra最短路径算法从源点到其余各顶点的最短路径长度按___________次序产生，设有-------1|4550_______►_______向图如下，则当源点取顶点1时，从顶点1到2的最短路径长度是_______冒泡排序算法不会改变具有相同排序码的记录的相对次序，故冒泡排序算法是

10.对个不同的元素进行冒泡排序（从小到大），在最坏情况下比较次数为n o四.解答题（本大题共小题，共分）420153

③④证明在求解阶汉诺塔问题中，至少应执行的操作次数为（分）

1.n move2-l4n0，，，.给出以为目标串，=匕为模式串的快速匹配过2S=aabcbabcaabcaaba Tbcaaba KMP程（分）6已知一棵度为的树中有个度为的结点，色个度为的结点,……，个度为的结

3.m112nm m点，计算该树中共有多少叶子结点有多少非终端结点？（分）4（已知关键字序列为）,依照此顺序建立一棵阶树,给出

4.20,30,50,60,70,803B_？（建立的过程及结果树若删除了和树的形态如何分）5060,B-6五.算法补充（本大题共小题，共分）430一元稀疏多项式以循环单链表按降幕罗列，结点有三个域,系数域，指数域

1.coef exp和指针域现对链表求一阶导数，链表的头指针为,头结点的域为next haexp-1（）derivative LinkListha{q=ha;pa=ha-next;（（））while1{ifpa-exp==O{2—3;freepa;pa=q;else{pa-coef=4;pa-exp=pa-exp-l;q=pa;pa=pa-next;.判断带头结点的双向循环链表是否对称相等的算法如下所示，请填空补充完整2S双向循环链表的存储结构为typedef struct DuLNode{ElemType data;struct DuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;int functionDuLinkLists DuLinkListp,q;int j=l;p=s-next;q=s-prior;________while p!=q5if p-data==q-data{2;}else j=0;return j;.采用三元组顺序存储表示，求稀疏矩阵的转置矩阵的快速转置算法如下，请补充完3M T敕it-O㊀MAXSIZE100typedef struct{加曙元的行下协的」下标int i,j;IElemType e;}Triple;typedef struct{〃三曙元三元组表，未用data[O]Triple data[MAXSIZE+1];〃矩阵的行数、歹擞、三嘻元的个数int mu,nu,tu;}TSMatrix;Void FastTransposeSMartixTSMatrixM,TSMatrix T{Tnu;T.nu=M.mu;T.tu=M.tu;ifT.tu{for col=l;col=M.nu;col++num[col]=0;fort=l;t=M.tu;t++++num

[8];cpot

[1]=1;forcol=2;col=M.nu;col++cpot[col]=9;for p=l;p=M.tu;p++{col=M.data[p].j;q^cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;—10;）旗法中弓入了两个辅助向量和,该算法勺时间复杂度为i Inum cpot（）11下面是中序线索树的遍历算法，树由头节点且由指针指向树的结点有五个域，分别为4•thr数据域,左、右孩子域和左、右标志域,规定标志域是线索，是data Ichild,rchild Itag,rtag10指向孩子的指针（头结点的域指向二叉树的根结点,头结点的域指向中序遍历时访Ichild rchild问的最后一个结点二叉树中序序列中的第一个结点的域指针和最后f结点的域指Ichild rchild针均指向头结点）inorderthreadthr{p=thr-1chiId;whil^12{while13p=14线printf d”,p-data;while p-rtag=l{p=p-rchild;绘printf d”,p-data;P=15;六.算法设计本大题共小题，共分330设计一个算法，求出带有头结点的线性链表中数据域值为的结点序号该序号应从链表

1.x的第一个数据结点算起，若链表中无此结点则序号为分06o.用个单元的一维数组构成一个循环队列，设计分别满足如下条件的算法分2n8实现在循环队列上的入队操作1实现在循环队列上的出队操作2计算队列中现有元素的个数3。