2021 年江苏南京林业大学数据结构考研真题一．是非题：（判断下列各题是否正确，正确的在括号内打 “√”，错的打“×”。每小题 2 分，共 20 分）1.数据的逻辑结构独立于计算机，物理结构依赖于计算机。（ ）2.线性表、栈和队列的逻辑结构完全相同。（ ）3.顺序存储方式只能用于存储线性结构。（ ）4.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ ）5.先根遍历树和先序遍历与该树对应的二叉树，其结果不同。（ ）6.外部排序与外部设备的特性无关。（）7.不使用递归，也可以实现二叉树的先序、中序和后序遍历。（ ）8.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。（ ）9. 有回路的图不能进行拓扑排序。（ ）10. 二叉排序树的查找和折半查找的时间性能相同。（ ）二．单项选择题（本大题共 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 个结点的完全三叉树的高度是______。Ａ. 4 B．5 C．6 D．76．数组 A[0..5,0..6]的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000的内存单元中，则元素 A[5,5]的地址是______。A．1175 B．1180 C．1205 D．12107．设森林Ｆ对应的二叉树为Ｂ，Ｂ有ｍ个结点，Ｂ的根为ｐ，ｐ的右子树结点个数为ｎ，森林Ｆ中第一棵树的结点个数是______。A．m-n B．m-n+1 C．n+1 D．条件不足，无法确定8．有 n 个顶点的强连通图至少有______条边。A. n+1 B. n C.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.o(log2n)12．具有线性结构的数据结构是______。A.树结构 B.图结构 C.广义表 D.文件结构13． 设无向图 G 中顶点数为 n,则图 G 最多有______条边。A.n B.n-1 C.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+树三．填空题：（本大题共 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个...
