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

1、南京林业大学 2021年攻读硕士学位研究生入学考试数 据 结 构 试题注意事项：1. 答案一律写在答题纸上；2. 答案卷应字迹清楚、语义确切；3. 算法应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，可加上必要的注释；4. 算法可用（类）PASCAL语言、C语言等你所熟悉的高级语言编写，但要注明语种。一 是非题：（判断下列各题是否正确，正确的在括号内打W”，错的打“X”。每小题2分，共20 分）1. 数据的逻辑结构独立于计算机，物理结构依赖于计算机。（ ）2. 线性表、栈和队列的逻辑结构完全相同。（ ）3. 顺序存储方式只能用于存储线性结构。（ ）4. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的 存储结构。（ ）5. 先根遍历树和先序遍历与该树对应的二叉树，其结果不同。（ ）6. 外部排序与外部设备的特性无关。（）7. 不使用递归，也可以实现二叉树的先序、中序和后序遍历。（ ）8. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊 处理。（ ）9. 有回路的图不能进行拓扑排序。（ ）10. 二叉排序树的查找

2、和折半查找的时间性能相同。（ ）二单项选择题(本大题共15小题，每小题2分，共30分)。A.规则B集合C结构D运算2对于顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时大约要移动表中的个元素。A.n/2 B.(n+1)/2 C.(n-1)/2 D.n3 线性表采用链式存储时，其地址。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续与否均可以4 设有一个空栈，栈顶指针为1000H (十六进制，下同，且设每个入栈元素需要1个单位 存储空间)，现有输入序列为1 ,2,3,4,5，经过PUSH , PUSH , POP , PUSH , POP , PUSH , POP , PUSH后，栈顶指针是。A.1002H B.1003H C.1004H D.1005H5将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是。A. 4 B . 5 C . 6 D . 76 数组A0.5,0.6的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的 内存单元中，则元素A5,5的地址是。A1175 B1180 C

3、1205 D12107设森林F对应的二叉树为B,B有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是。A . m-n B . m-n+1 C . n+1 D .条件不足，无法确定8有n个顶点的强连通图至少有条边。A. n+1 B. n C.n-1D.n(n-1)9堆是一种有用的数据结构。以下关键字序列是一个堆。A.16，72，31，23，94，53B.94，23，31，72，16，53C.16，53，23，94，31，72D.16，23，53，31，94，7210 .关键路径是AOV网中。A.从源点到汇点的最短路径B.从源点到汇点的最长路径C.最长的回路D.最短的回路11折半查找的时间复杂度是。A.O(n2) B.o(n) C.o(nlog2n) D.o(log2n)12具有线性结构的数据结构是。A.树结构 B.图结构 C.广义表 D文件结构13 .设无向图G中顶点数为n,则图G最多有条边。A.n B.n-1C.n(n-1)/2D.n(n-1)14 设某有向图中有n个顶点，e条边，进行拓扑排序时总的时间复杂度为A. o(nlog2e) B. o(e+n)C.

4、o(elog2n) D. o(e*n)15不满足平衡查找树概念的是。A.BST树 B.AVL树 C.折半查找判定树D.B+树三填空(本大题共10小每小题2分，共20分)1. 分析以下程序段的时间复杂度为(用大“O”记号表示执行时间为n(正整数)的函数)。x=n;y=0;While(x=(y+1)*(y+1)y+;2. 为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的分别设在这片内存空间的两端，这样，只有当时，才产生上溢。3. 一个n*n的对称矩阵，如果以相同的元只存储一次的原则进行压缩存储，则其压缩后的存储容量为。4广义表(a,(b,c),d,e,(f,g),h)的长度为，深度为。5.棵有n(n=1)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在树的 nd 个链域中，有个是空链域，只有个是非空链域。6若二叉树有n个结点，当执行中序遍历的递归程序时，在最坏情况下为处理递归调用所设的栈需要个单元。7.棵有n0个叶子结点的哈夫曼树上，其结点总数为。8对于含有n个顶点e条边的无向连通图，prim算法适用于求网的最小代价生成树，而 K

5、ruskal 算法适用于求网的最小代价生成树。10冒泡排序算法不会改变具有相同排序码的记录的相对次序，故冒泡排序算法是，对 n 个不同的元素进行冒泡排序（从小到大），在最坏情况下比较次数为。四解答题：（本大题共 4小题，共20分）1. 证明：在求解n阶汉诺塔问题中，至少应执行的move操作次数为2n-1。（4分）2. 给出以S=aabcbabcaabcaaba为目标串，T=abcaaba为模式串的KMP快速匹配过程。（6 分）3. 已知一棵度为m的树中有：个度为1的结点，n2个度为2的结点，nm个度为m 的结点，计算该树中共有多少叶子结点?有多少非终端结点？（4分）4. 已知关键字序列为（20,30,50,60,70,80 ）,依照此顺序建立一棵3阶B-树，给出建立的过程及结果树。若删除了 50和60,B-树的形态如何？（6分）五算法补充：（本大题共 4小题,共30分）1 . 一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp 和指针域next。现对链表求一阶导数，链表的头指针为ha，头结点的exp域为-1。derivative（LinkList ha）

6、q=ha;pa=ha-next;while（ ） if(pa-exp=O)_(2)_:_(3)_ : free(pa); pa=q:else pa-coef= (4):pa-exp = pa-exp-1： q=pa: pa=pa-next:2判断带头结点的双向循环链表 S 是否对称相等的算法如下所示，请填空补充完整。 双向循环链表的存储结构为：typedef struct DuLNode ElemType data:struct DuLNode* prior:struct DuLNode* next:DuLNode,* DuLinkList:int function(DuLinkList s)DuLinkList p,q:int j=1:p=s-next:q=s-prior:while(p!=q& _(5)if(p-data= =q-data) (6):(7)else j=0:return j:3.采用三元组顺序存储表示，求稀疏矩阵 M 的转置矩阵 T 的快速转置算法如下，请补充完 整。#define MAXSIZE 100typedef structint i,j:/非零元的行下标和

7、列下标ElemType e;Triple;typedef structTriple dataMAXSIZE+l;非零元三元组表，dataO未用int mu,nu,tu; /矩阵的行数、列数、非零元的个数TSMatrix;Void FastTransposeSMartix(TSMatrix M,TSMatrix &T) T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu) for(col=l;col=M.nu;col+) numcol=0;for(t=1;tv=M.tu;t+)+num _ (8);cpotl=l;for(col=2;col=M.nu;col+)cpotcol= _ (9);for(p=1;plchild;while( (12) while( (13) p= (14)printf( “ %d ”,p-data);while(p-rtag=1) p=p-rchild;printf( “%d ”,p-data);p= (15)；六算法设计：（本大题共 3小题，共30分）1设计一个算法，求出带有头结点的线性链表中数据域值为x的结点序号。该序号应从链表 的第一个数据结点算起，若链表中无此结点则序号为 0。（6 分）2. 用 n 个单元的一维数组构成一个循环队列，设计分别满足如下条件的算法。（8 分）（1）实现在循环队列上的入队操作。（2）实现在循环队列上的出队操作。（3）计算队列中现有元素的个数。3. 二叉树采用链式存储结构，设计一个计算一棵给定二叉树深度的递归算法。（6分）4. 对于一棵二叉排序树，设计分别满足如下条件的算法。（10分）（1）实现在二叉排序树上的查找操作：若找到与给定数据值相等的结点，返回该结点的指 针；若未找到，返回空指针NULL。（2 ）实现在二叉排序树上的插入操作：若BST上存在与给定数据值相等的结点，给出“It is exist ! ”信息，不插入；若BST上不存在与给定数据值相等的结点，则插入。

《南京林业大学考研真题—数据结构2021》由会员枫**分享，可在线阅读，更多相关《南京林业大学考研真题—数据结构2021》请在金锄头文库上搜索。