2015级考研复习及面试用数据结构作业集判断-鲁法明

1-1 直接访问就是直接利用变量的地址直接进行访问。 F

1-2 可以用一个指针变量指向一个函数，然后通过该指针变量调用此函数。T

1-3 int (*p)[4]它表示p是一个指针数组，它包含4个指针变量元素。T

1-4 结构体变量可以作数组元素。T

1-5 函数名代表该函数的入口地址。因此，可用函数名给指向函数的指针变量赋值。T

1-6 结构体成员的类型必须是基本数据类型。F

1-7 指针数组的每个元素都是一个指针变量。T

1-8 结构体类型本身不占用内存空间，结构体变量占用内存空间。 T

1-9 char s=“C Language”;表示s是一个指向字符串的指针变量，把字符串的首地址赋予s。T

1-1 若用链表来表示一个线性表，则表中元素的地址一定是连续的。F

1-2 数据的逻辑结构是指数据的各数据项之间的逻辑关系。F

数据的逻辑结构是数据之间的逻辑关系，而不是数据内部的数据项的逻辑关系。

1-3 抽象数据类型中基本操作的定义与具体实现有关。F

1-1 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。T

1-2 N?2??logN和NlogN?2??具有相同的增长速度。F

1-3 2?N??和 NN??具有相同的增长速度。F

1-4 100logN是O(N)的。F

大O是不看系数的，故应该是O(logN)

1-5 (NlogN)/1000是O(N)的。F

是O（NlogN）的

1-6 在任何情况下，时间复杂度为O(n?2??) 的算法比时间复杂度为O(nlogn)的算法所花费的时间都长。F

1-7 对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。T

1-1 对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。T

1-2 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。T

1-3 对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。F

顺序储存，需要移动元素，从后往前移。故删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(N)，O(1)。

1-4 (neuDS)在顺序表中逻辑上相邻的元素，其对应的物理位置也是相邻的。T

1-5 (neuDS)所谓随机存取，就是通过首地址和元素的位序号值可以在O(1)的时间内找到指定的元素。T

随机存取就是直接存取，可以通过下标直接访问的那种数据结构，与存储位置无关，例如顺序表。

非随机存取就是顺序存取了，不能通过下标访问了，只能按照存储顺序存取，与存储位置有关，例如链表。

1-6 (neuDS)顺序存储的线性表不支持随机存取。F

1-7 (neuDS)在顺序表上进行插入、删除操作时需要移动元素的个数与待插入或待删除元素的位置无关。F

1-1 在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。F

单链表访问节点的时间复杂度为O(N)。

1-3 将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。F

为O(M)或O(N)。

1-4 (neuDS)单链表不是一种随机存取的存储结构。T

1-1 通过对堆栈S操作：Push(S,1),Push(S,2),Pop(S),3),Pop(S)。输出的序列为：123。F

堆栈的特点：后进先出。输出序列为231

1-2 若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j?i?1。F

1-3 若一个栈的输入序列为{1,2,3,4,5}，则不可能得到{3,1,5}这样的出栈序列。T

放进3、4后，1不可能比2先出。

1-1 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。F

1-2 在用数组表示的循环队列中，front值一定小于等于rear值。F

1-3不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。T

1-1某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。T

1-2某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。F

若前序和中序遍历序列正好一样，则该二叉树中任何结点一定都无左孩子。

1-3存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。F

没说是什么形状的二叉树。

1-4若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为…A…B…，而中序遍历序列为…B…A…。F

1-5若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。F

如果这个二叉树仅有左孩子和根节点，那么中序遍历的最后一个结点为根节点，而前序遍历的最后一个结点一定不是根节点。

1-6某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。T

1-7已知一棵二叉树的先序遍历结果是ABC,则CAB不可能是中序遍历结果。T

1-1对于一个有N个结点、K条边的森林，不能确定它共有几棵树。F

森林为互不相交的树的集合。

N个结点，K条边所以N-K即树的数量。

1-1对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。T

1-1无向连通图至少有一个顶点的度为1。F

连通无向图是指对图中任意顶点u,v,都存在路径使u、v连通。

任意一条边都代表u连v以及v连u。无向图是相对于有向图来说明的，就是说每条边都是双向边，而有向图每条边都是单向边，也就是说只能由一个点指向另一个点。

度是指顶点的邻接点的个数。注意不是连通的个数，因为，如果a，b之间有边，b，c之间有边，则说a与c连通。

1-2 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。F

1-3 用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。T

1-4 在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。T

一条边是一个顶点的入度，一个顶点的初度。所以所有顶点入度与出度之和等于所有边之和的2倍。

1-5 在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。T

1-6 如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。F

1-7 如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。T

1-8 无向连通图所有顶点的度之和为偶数。T

1-9 无向连通图边数一定大于顶点个数减1。F

大于等于顶点个数减1。

1-1 在一个有权无向图中，若b到a的最短路径距离是12，且c到b之间存在一条权为2的边，则c到a的最短路径距离一定不小于10。T

1-1对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。F

如果是逆序，那么交换元素次数肯定最多。但如果基本有正序，那么交换次数少。

1-2对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(NlogN)。F

快速排序，最坏的情况下，其时间复杂度为O(N2)。

1-3对N个记录进行归并排序，归并趟数的数量级是O(NlogN)。F

1-1对N个记录进行简单选择排序，比较次数和移动次数分别为O(N?2??)和O(N)。T

1-2对N个记录进行堆排序，需要的额外空间为O(N)。

堆排序，需要的额外空间为O(1)。

1-1KMP算法的特点是在模式匹配时指示主串的指针不会变小回溯。T

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!