1、南京林业大学南京林业大学 20222022 年年 数据结构数据结构 考研真题考研真题一是非题一是非题判断下列各题是否正确，正确的在括号内打判断下列各题是否正确，正确的在括号内打 “”，错的打，错的打“”“”。每小题。每小题 2 2分，共分，共 2020 分。分。1.数据的逻辑结构独立于计算机，物理结构依赖于计算机。（）2.线性表、栈和队列的逻辑结构完全相同。（）3.顺序存储方式只能用于存储线性结构。（）4.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（）5.先根遍历树和先序遍历与该树对应的二叉树，其结果不同。（）6.外部排序与外部设备的特性无关。（）
2、7.不使用递归，也可以实现二叉树的先序、中序和后序遍历。（）8.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。（）9.有回路的图不能进行拓扑排序。（）10.二叉排序树的查找和折半查找的时间性能相同。（）二单项选择题二单项选择题A.规则 B.集合C.结构 D.运算2对于顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概率的。插入一个元素时大约要移动表中的_个元素。A.n/2 B.(n+1)/2C.(n-1)/2 D.n3 线性表采用链式存储时，其地址_。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以4设有一个空
3、栈，栈顶指针为 1000H（十六进制，下同，且设每个入栈元素需要 1 个单位存储空间），现有输入序列为 1，2，3，4，5，经过 PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH 后，栈顶指针是_。A.1002H B.1003HC.1004H D.1005H5将有关二叉树的概念推广到三叉树，则一棵有 244 个结点的完全三叉树的高度是_。.4 B5C6 D76数组 A0.5,0.6的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A5,5的地址是_。A1175 B1180C1205 D12107设森林对应的二叉树为，有个结点，的
4、根为，的右子树结点个数为，森林中第一棵树的结点个数是_。Am-n Bm-n+1Cn+1 D条件不足，无法确定8有 n 个顶点的强连通图至少有_条边。A.n+1 B.nC.n-1 D.n(n-1)9堆是一种有用的数据结构。以下关键字序列_是一个堆。A.16，72，31，23，94，53 B.94，23，31，72，16，53C.16，53，23，94，31，72 D.16，23，53，31，94，7210关键路径是 AOV 网中_。A.从源点到汇点的最短路径 B.从源点到汇点的最长路径C.最长的回路 D.最短的回路11折半查找的时间复杂度是_。A.O(n2)B.o(n)C.o(nlog2n)D.
5、o(log2n)12具有线性结构的数据结构是_。A.树结构 B.图结构C.广义表 D.文件结构13 设无向图 G 中顶点数为 n,则图 G 最多有_条边。A.n B.n-1C.n(n-1)/2 D.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+树三填空题1.分析以下程序段的时间复杂度为 _(用大“O”记号表示执行时间为 n（正整数）的函数)。x=n;y=0;While(x=(y+1)*(y+1
6、)y+;2.为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 _分别设在这片内存空间的两端，这样，只有当_时，才产生上溢。3.一个 n*n 的对称矩阵，如果以相同的元只存储一次的原则进行压缩存储，则其压缩后的存储容量为_。4.广义表（a,(b,c),d,e,(f,g),h)）的长度为_，深度为_。5.一棵有 n(n=1)个结点的 d 度树，若用多重链表表示，树中每个结点都有 d个链域，则在树的 nd 个链域中，有_个是空链域，只有_个是非空链域。6.若二叉树有 n 个结点，当执行中序遍历的递归程序时，在最坏情况下为处理递归调用所设的栈需要_个单元。7
7、.一棵有 n0个叶子结点的哈夫曼树上，其结点总数为_。8.对于含有 n 个顶点 e 条边的无向连通图，prim 算法适用于求_网的最小代价生成树，而 Kruskal 算法适用于求_网的最小代价生成树。9Dijkstra 最短路径算法从源点到其余各顶点的最短路径长度按 _次序产生，设有向图如下，则当源点取顶点 1 时，从顶点 1 到 2 的最短路径长度是_。10冒泡排序算法不会改变具有相同排序码的记录的相对次序，故冒泡排序算法是_，对 n 个不同的元素进行冒泡排序（从小到大），在最坏情况下比较次数为_。四解答题四解答题1.证明：在求解 n 阶汉诺塔问题中，至少应执行的 move 操作次数为 2n
8、-1。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-树的形态如何？五算法补充五算法补充1一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域 exp 和指针域 next。现对链表求一阶导数，链表
9、的头指针为 ha，头结点的 exp 域为-1。derivative(LinkList ha)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 是否对称相等的算法如下所示，请填空补充完整。双向循环链表的存储结构为：typedef struct DuLNode ElemType data;struct DuLNode *prior;struct DuLNode *next;DuLNo
10、de,*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;/非零元的行下标和列下标ElemType e;Triple;typedef structTriple dataMAXSIZE+1;/非
11、零元三元组表，data0未用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=1;col=M.nu;col+)numcol=0;for(t=1;t=M.tu;t+)+num_(8)_;cpot1=1;for(col=2;col=M.nu;col+)cpotcol=_(9)_;for(p=1;plchild;while(12)while(13)p=(14);printf(“%d”,p-
12、data);while(p-rtag=1)p=p-rchild;printf(“%d”,p-data);p=(15);六算法设计1.设计一个算法，求出带有头结点的线性链表中数据域值为 x 的结点序号。该序号应从链表的第一个数据结点算起，若链表中无此结点则序号为 0。（6 分）2.用 n 个单元的一维数组构成一个循环队列，设计分别满足如下条件的算法。（8 分）（1）实现在循环队列上的入队操作。（2）实现在循环队列上的出队操作。（3）计算队列中现有元素的个数。3.二叉树采用链式存储结构，设计一个计算一棵给定二叉树深度的递归算法。（6 分）4.对于一棵二叉排序树，设计分别满足如下条件的算法。（10 分）（1）实现在二叉排序树上的查找操作：若找到与给定数据值相等的结点，返回该结点的指针；若未找到，返回空指针 NULL。（2）实现在二叉排序树上的插入操作：若BST 上存在与给定数据值相等的结点，给出“It is exist！”信息，不插入；若 BST 上不存在与给定数据值相等的结点，则插入。
