2017年上海海事大学信息工程学院828数据结构及程序设计之数据结构考研导师圈点必考题汇编一、填空题1 串是一种特殊的线性表，其特殊性表现在_; 串的两种最基本的存储方式是_、_; 两个串相等的充分必要条件是_。【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等 2 克鲁斯卡尔算法的时间复杂度为_，它对_图较为适合。【答案】O （eloge ）; 边稀疏 3 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。 【答案】【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。 4 在基于关键字比较且时间为O （nl g2n ）的排序中，若要求排序是稳定的，则可选用_，则可选用_排序。 排序；若要求就地排序（及辅助空间为0（1）【答案】归并；堆 5 数据结构是研讨数据的_和_以及它们之间的相互关系，并对与这种结构定义相应的_，设计出相应的_。；算法 【答案】逻辑结构；物理结构；操作（运算） 6 G 是一个非连通无向图，共有28条边，则该图至少有_个顶点。【答案】9【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。7 在拓扑分类中，拓扑序列的最后一个顶点必定是_的顶点。【答案】出度为0【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。 8 线性表【答案】（n 1）/2 用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。【解析】删除第一个元素需要移动n i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为 9 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_，【答案】比较；移动 10一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 11每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_。 【答案】【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。 12数组的存储结构采用_存储方式。【答案】顺序存储结构【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。 13求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树e【答案】克鲁斯卡尔【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。 14有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_。（3在4之前出栈）【答案】3个【解析】以3, 4先出栈的序列有34521、34215、34251共3个。.，则它的后庁序列是_。设上述二叉树是由某棵树转换而成，则该树的15在一棵m阶的个数是_。 【答案】【解析】m阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字 树除根结点和叶子结点外，结点中关键字个数最多是最少二、选择题16若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。A.X 的双亲B.X 的右子树中最左的结点C.X 的左子树中最右的结点D.X 的左子树中最右的叶结点【答案】C【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。 17站点A 、B 、C 通过CDMA 共享链路，A 、B 、C 的码片序列（chipping sequence）分别是和C 收到A 发送的数据是（ ）A.000B.101C.110D.111【答案】B【解析】用A 的码片与信息做内积运算 18用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。A. 仅修改队头指针B. 仅修改队尾指针C. 队头、队尾指针都可能要修改D. 队头、队尾指针都要修改【答案】C【解析】用不带头结点的单链表存储队列，一般删除操作仅修改队头指针，但当队列中只有一个结点时，进行删除操作要将队头、队尾指针都修改成NULL 。 19对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。A. 每次分区后，先处理较短的部分若C 从链路上收到的序列是则一、填空题考研试题