选择题：在一个具有n个结点的用链表表示线性表的优点是中,删除第i个结点元素（1<i<n），需要移动 个结点元素？

来源：蜘蛛抓取(WebSpider) 时间：2022-11-15 05:49 标签： 用链表表示线性表的优点是

2018 年攻读硕士学位研究生入学考试试题

1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考

2、所有答案必须写在答题纸上，写在其他地方无效。

3、填（书）写必须使用 0.5mm 黑色签字笔。

4、考试结束，将答题纸和试题一并装入试卷袋中交回。

5、本试题满分 150 分，考试时间 3 小时。

一、选择题（本大题共15 小题，每小题 2 分，共30 分）

1.下面程序段的时间复杂度是（）。

2.在n 个元素的顺序表中插入或删除一个元素，需要平均移动表中（）个

3.设循环队列中数组的下标范围是0, ..., m－1，其头指针front 指向队首元

素，rear 指向队尾元素，则队列的长度为（）。

4.设计一个十进制转换为八进制的算法，采用（）数据结构最佳。

5.若某个栈的输入序列为1, 2, 3,…, n，输出序列的第一个元素为n，则第i

6.六个元素按6，5，4，3，2，1 的顺序进栈，下列哪个出栈序列是错误的

7.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）二叉

A．空或只有一个结点B．高度等于其结点数

C．任一结点无左孩子D．任一结点无右孩子

8.高度为k 的完全二叉树至少有（）个结点（空树高度为0）。

9.设高度为h 的二叉树上只有度为0 和度为2 的结点，则此二叉树中至多有

10.数组A 中，每个元素的长度为3 个字节，行下标i 从1 到8，列下标j

从1 到10，从首地址SA 开始连续存放在存储器内，该数组按行优先存放时，元素A[8][5]的起始地址为（）。

1.任何一个无向连通图的最小生成树（）。

12.对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示，则表头

向量的大小为n；所有邻接表中的结点总数是（）。

13.设结点x 和结点y 是二叉树T 中的任意两个结点，若在先序序列中x 在

y 之前，而在后序序列中x 在y 之后，则x 和y 的关系是（）

14.关于下面的图形，哪个说法正确（）。

B.顶点2 的入度为2；

C.顶点4 的出度为2；

15.下列序列中，（）是执行第一趟快速排序后得到的序列（排序的关键

二、填空题（本大题共 10 小题，每小题 3 分，共 30 分）

1.采用顺序查找方法查找长度为n 的线性表时，在等概率情况下查找成功的

2.已知数据表A 中每个元素距其最终位置不远，则采用排序

3.图G 是一个非连通图，共有28 条边，则该图至少有 _________ 个顶点。

4.设一循环队列Q 中，rear 指针指向队尾元素的下一个位置，front 指针指

向队首元素，则判断队列中元素为空的条件是。

5. 在大根堆中，关键字最小的元素可能存放在堆的任一 结点上。

7. 有 n 个顶点的连通图用邻接矩阵表示时，该矩阵至少有 个非零元素。

9. 广义表（（a ），（（b ），c ），（（（d ））））的长度是 ，深度是 _______ 。

10. 在有 n 个结点的二叉链表中，空链域的个数为 。

三 、问答题（本大题共 6 小题，每小题 10 分，共 60 分）

（1） 画出该二叉树；

（2） 写出此二叉树的后序序列； （3） 画出与此二叉树对应的森林。

2. 图 G 各顶点的连接关系及相应权值如下图所示：

（1） 画出图的邻接矩阵存储图示；

（2） 从顶点 1 开始对图进行广度优先遍历，写出遍历结果； （3） 使用 Kruskal 算法求该图的最小生成树，给出形成过程。

3. 设散列表的长度为 8，散列函数 H(k)=k mod 7，初始记录关键字序列为

（1） 分别给出用线性探测法和链地址法作为解决冲突方法的过程； （2） 计算（1）中两种解决冲突方法的平均查找长度。

4. 已知一个图的顶点集 V 和边集 E 分别为：

（1）画出该图的邻接表存储图示；

（2）按拓朴排序算法进行排序，试给出得到的拓朴排序的序列。

5.假设一个线性链表的类名为linkedList，链表结点的类名为ListNode，它

包含两个数据成员data 和link。data 存储该结点的数据，link 是链接指

针。下面给定一段递归打印一个链表中所有结点中数据的算法：

试问此程序在什么情况下不实用？给出具体修改后的可实用的程序？

6.对于如下图所示的AOE 网络，计算各活动弧的e(a i)（活动a i的最早开

始时间）和l(a j)（活动a j的最迟开始时间）函数值、各事件（顶点）的

ve(v i)（事件v i的最早发生时间）和vl(v j)（事件v j的最迟发生时间）函

数值；列出各条关键路径。

四、问答题（本大题共 2 小题，每小题 15 分，共 30 分）

1. 现有关键字序列{45，24，37，53，12，93，47，60}，按以下要求完成：

（1）根据给定的关键字序列构造一棵二叉查找（排序）树，以二叉链表形式存储，进行中序遍历可以得到从小到大排列的有序序列，请写出构

造过程（不要求算法）。

在一个具有n个结点的有序单链表中插入____个新结点并仍然有序的时间复杂度为()

【超详细】数据结构总结及思维导图（王道考研）

  • 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
  • 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的
  • 数据的逻辑结构分为线性结构和非线性结构
    • 集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 类似于数学上的集合
    • 线性结构 结构中的数据元素之间只存在一对一的关系。比如排队
    • 树形结构 结构中的数据元素之间存在一对多的关系。比如家族族谱
    • 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 比如地图
  • 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。
      站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

我要回帖

更多关于 用链表表示线性表的优点是 的文章

 

随机推荐