南京林业大学考研真题数据结构.docx
- 文档编号:2746899
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:10
- 大小:27.05KB
南京林业大学考研真题数据结构.docx
《南京林业大学考研真题数据结构.docx》由会员分享,可在线阅读,更多相关《南京林业大学考研真题数据结构.docx(10页珍藏版)》请在冰点文库上搜索。
南京林业大学考研真题数据结构
南京林业大学2021年攻读硕士学位研究生入学考试
数据结构试题
注意事项:
1.答案一律写在答题纸上;
2.答案卷应字迹清楚、语义确切;
3.算法应对主要数据类型、变量给出说明,所写算法应结构清晰、简明易懂,可加上必要的注释;
4.算法可用(类)PASCAL语言、C语言等你所熟悉的高级语言编写,但要注明语种。
一.是非题:
(判断下列各题是否正确,正确的在括号内打 “√”,错的打“×”。
每小题2分,共20分)
1.数据的逻辑结构独立于计算机,物理结构依赖于计算机。
()
2.线性表、栈和队列的逻辑结构完全相同。
()
3.顺序存储方式只能用于存储线性结构。
()
4.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。
()
5.先根遍历树和先序遍历与该树对应的二叉树,其结果不同。
()
6.外部排序与外部设备的特性无关。
()
7.不使用递归,也可以实现二叉树的先序、中序和后序遍历。
()
8.在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应作特殊处理。
()
9.有回路的图不能进行拓扑排序。
()
10.二叉排序树的查找和折半查找的时间性能相同。
()
二.单项选择题(本大题共15小题,每小题2分,共30分)。
A.规则B.集合C.结构D.运算
2.对于顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的。
插入一个元素时大约要移动表中的______个元素。
A.n/2B.(n+1)/2C.(n-1)/2D.n
3.线性表采用链式存储时,其地址______。
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续与否均可以
4.设有一个空栈,栈顶指针为1000H(十六进制,下同,且设每个入栈元素需要1个单位存储空间),现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POP,PUSH,POP,PUSH后,栈顶指针是______。
A.1002HB.1003HC.1004HD.1005H
5.将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度是______。
A.4B.5C.6D.7
6.数组A[0..5,0..6]的每个元素占5个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是______。
A.1175B.1180C.1205D.1210
7.设森林F对应的二叉树为B,B有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是______。
A.m-nB.m-n+1C.n+1D.条件不足,无法确定
8.有n个顶点的强连通图至少有______条边。
A.n+1B.nC.n-1D.n(n-1)
9.堆是一种有用的数据结构。
以下关键字序列______是一个堆。
A.16,72,31,23,94,53B.94,23,31,72,16,53
C.16,53,23,94,31,72D.16,23,53,31,94,72
10.关键路径是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.nB.n-1C.n(n-1)/2D.n(n-1)
14.设某有向图中有n个顶点,e条边,进行拓扑排序时总的时间复杂度为______。
A.o(nlog2e)B.o(e+n)C.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算法适用于求______网的最小代价生成树,而Kruskal算法适用于求______网的最小代价生成树。
9.Dijkstra最短路径算法从源点到其余各顶点的最短路径长度按________次序产生,设有向图如下,则当源点取顶点1时,从顶点1到2的最短路径长度是______。
①②⑤
③④⑥
10.冒泡排序算法不会改变具有相同排序码的记录的相对次序,故冒泡排序算法是______,对n个不同的元素进行冒泡排序(从小到大),在最坏情况下比较次数为______。
四.解答题:
(本大题共4小题,共20分)
1.证明:
在求解n阶汉诺塔问题中,至少应执行的move操作次数为2n-1。
(4分)
2.给出以S=’aabcbabcaabcaaba’为目标串,T=’abcaaba’为模式串的KMP快速匹配过程。
(6分)
3.已知一棵度为m的树中有:
n1个度为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(LinkListha)
{q=ha;
pa=ha->next;
while(___
(1)___)
{if(pa->exp==0){___
(2)___;
___(3)___;
free(pa);
pa=q;
}
else{pa->coef=___(4)___;
pa->exp=pa->exp-1;
q=pa;
pa=pa->next;
}
}
}
2.判断带头结点的双向循环链表S是否对称相等的算法如下所示,请填空补充完整。
双向循环链表的存储结构为:
typedefstructDuLNode{
ElemTypedata;
structDuLNode*prior;
structDuLNode*next;
}DuLNode,*DuLinkList;
intfunction(DuLinkLists)
{
DuLinkListp,q;
intj=1;
p=s->next;
q=s->prior;
while(p!
=q&&___(5)___)
if(p->data==q->data){___(6)___;
___(7)___;
}
elsej=0;
returnj;
}
3.采用三元组顺序存储表示,求稀疏矩阵M的转置矩阵T的快速转置算法如下,请补充完整。
#defineMAXSIZE100
typedefstruct{
inti,j;//非零元的行下标和列下标
ElemTypee;
}Triple;
typedefstruct{
Tripledata[MAXSIZE+1];//非零元三元组表,data[0]未用
intmu,nu,tu;//矩阵的行数、列数、非零元的个数
}TSMatrix;
VoidFastTransposeSMartix(TSMatrixM,TSMatrix&T){
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu){
for(col=1;col<=M.nu;col++)num[col]=0;
for(t=1;t<=M.tu;t++)++num[___(8)___];
cpot[1]=1;
for(col=2;col<=M.nu;col++)
cpot[col]=___(9)___;
for(p=1;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)___;
}
}
}
该算法中引入了两个辅助向量num和cpot,该算法的时间复杂度为:
___(11)___。
4.下面是中序线索树的遍历算法,树由头节点且由指针thr指向。
树的结点有五个域,分别为:
数据域data,左、右孩子域lchild,rchild和左、右标志域ltag,rtag,规定标志域1是线索,0是指向孩子的指针。
(头结点的lchild域指向二叉树的根结点,头结点的rchild域指向中序遍历时访问的最后一个结点。
二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域指针均指向头结点。
)
inorderthread(thr)
{p=thr->lchild;
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上存在与给定数据值相等的结点,给出“Itisexist!
”信息,不插入;若BST上不存在与给定数据值相等的结点,则插入。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 南京 林业大学 考研 数据结构