当前位置：文档之家 › 2014暨南大学数据结构

2014暨南大学数据结构

  • 格式：doc
  • 大小：97.00 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

暨南大学830数据结构2014年考研专业课真题试卷

暨南大学830数据结构2014年考研专业课真题试卷

B.1，5，10，6，7，8，9，2 D.9，8，7，6，5，4，3，7
二．填空题(每空 2 分，共 20 分)
1. 线性结构中元素之间存在一对一关系，树型结构中元素之间存在
图型结构中元素之间存在
关系.
2. 单链表中设置头结点的作用是
3.由 n 个权值构成的哈夫曼树共有
个结点.
4.已知一个图的邻接矩阵表示，删除所有从第 i 个结点出发的边的方法是
法是(
).
A. 归并排序
B. 快速排序
C. 直接插入排序
D. 堆排序
考试科目： 数据结构
共 4 页，第 1 页
暨南大学2014年考研专业课真题试卷（原版）
13. 在 AOE 网中，完成工程的最短时间是（
）.
A．从源点到汇点的最短路径的长度
B．从源点到汇点的最长路径的长度
C．最长的回路的长度
D．最短的回路的长度
a1=5 V1
1 a2=3
V2 a3=2
1
a4=12 V3
1a5=4
V4 a6=9
1 图1
a7=7 V5
a1=5
5 a8=3
1
V6 a9=6
1
3.简述下列算法的功能.（6 分） void process( Sqlist &L) //L 为线性表,用顺序存储结构表示
{ int i=0, j; While （i<L.length && L.elem[i]!=X） i++; for (j=i+1;j<L.length; j++) if (L.elem[j]!=X) { L.elem[i]=L.elem[j]; i++; } L.length=i;

暨南大学830数据结构2010,2012--2020年考研真题

暨南大学830数据结构2010,2012--2020年考研真题

考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2 分，共 30 分)
1. 下述关于顺序存储结构优点的说法，哪个是正确的（ ）
A. 插入运算方便
B. 可方便地用于各种逻辑结构的存储表示
C. 存储密度大
D. 删除运算方便
2. 假设根结点为第 1 层，深度为 h 层的二叉树至少有( ) 个结点(h>1)；
A．3
B．4
C．5
D．6
13. 有一个 100*90 的整数稀疏矩阵，其中非 0 元素个数为 10；设每个整数占用 3 个字节，则
用三元组表示该矩阵时，总共需要的存储空间为( )字节。
A．30
B．33
C．90
D．99
14. 在一个双向链表中，当删除结点 p 时，错误的操作序列为 ( )。
A. p=p->prev; p->next->prev=p; p->next=p->next->next;
2020 年全国硕士研究生统一入学考试自命题试题 B 卷
********************************************************************************************
学科、专业名称：网络空间安全 研究方向：网络空间安全 083900 考试科目名称及代码：数据结构 830
4. 以下关于递归算法的论述，不正确的是( )
A. 递归算法的代码可读性好
B. 递归算法可以提高程序运行效率
C. 递归调用层次太深有可能造成堆栈溢出 D. 递归调用层次太深会占用大量内存
5. 设有字符集合{4,6,3,W,S}，将字符序列 6W43S 中的字符按顺序进入堆栈，出栈可发生在任

数据结构暨南大学期末试卷试题

数据结构暨南大学期末试卷试题

数据结构暨南大学期末试卷试题一、判断题(共10分)1. 当静态链表采用数组实现时，插入与删除操作仍需移动元素。

2. 栈也是一种线性表，也同样有顺序存储结构和链式存储结构。

3. 二叉树的三种遍历算法区别仅在于对树根、左右子树访问先后顺序的不同。

4. 邻接表是图的一种顺序存储结构。

5. 二叉树就是度数为2的树。

6. 在哈希表中勿需比较就可找到记录在表中的位置。

7. 线性表的链式存储结构既方便其存取操作，也方便其插入与删除操作。

8. 顺序存储结构既适合于完全二叉树，也同样适合于一般的二叉树。

9.一个算法是正确的、高效率的，还不能说它就是一个“好”的算法。

10. 快速排序与堆排序的平均时间复杂度相同。

二、概念填空(共20分，每题2分)1.对顺序存储结构的线性表，设表长为La;在各元素插入为等概率条件下，插入一个数据元素需平均移动表中元素_______ 个;在最坏情况下需移动表中元素_______ 个。

2.从逻辑角度看，四种基本的数据结构可分为__________、___________、____________和____________;两种存储结构为_____________和_________________。

3.一个深度为,的满k(k>2)叉树，其第i层(若存在)有________个结点;编号为p(p>1)的结点其父结点(父结点为非根结点)编号是___________________。

4.具有n个结点的完全二叉树的深度为____________;编号为p(<n)的结点其右孩子(若存在)结点编号是___________。

5.堆栈被称为一个_____________的线性表;队列被称为一个_____________的线性表。

6.静态查找表的查找方法主要有:有序表查找及________________________;在n个记录中进行折半查找，当查找不成功时，与关键字比较次数最多为_____________________。

2014数据结构大纲解析

2014数据结构大纲解析

一、数据结构考查目标1. 掌握数据结构的基本概念、基本原理和基本方法。

2. 掌握数据的逻辑结构、存储结构及其基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

3. 能够运用数据结构的基本原理和方法进行问题的分析和求解，具备采用C或C++语言设计与实现算法的能力。

二、数据结构考点解析2014年计算机统考大纲完全解析系列共由八篇构成，在第一篇中，我们列出了大纲的变化的对比，在第一时间着重对整个考试的性质，考查目标，新大纲的变化以及相应的备考策略做了介绍。

在第二篇我们简单的分析这些变化。

在接下来的四篇中，我们将分别详细解读大纲所规定的四门课程的考查内容，并给出有针对性的复习提示。

今天我们首先来解析一下计算统考大纲数据结构部分及其相关知识点。

数据结构占了45分，和计算机组成原理部分同一个比重，在以往各年计算机专业的研究生入学考试中，几乎没有学校不考查数据结构的内容，而且绝大部分考试中，数据结构这一门都占据了重要的地位，这足以体现计算机专业研究生选拔对数据结构课程的要求之重。

2014年的统考大纲对数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法;掌握数据的逻辑结构、存储结构及其基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析;能够综合运用数据结构的基本原理和方法进行问题的分析和求解，具备采用C或C++语言设计与实现算法的能力。

这个考查目标与13年大纲的考查目标相比去掉了对java语言设计和实现算法的能力。

要求运用数据结构的基本原理和方法进行分析问题，要求学生能够活学活用，事实上，可以看出研究生入学考试对知识实际应用能力的加强。

大纲仍要求学生具备采用C或C++语言设计与实现算法的能力，但是考生不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。

暨南大学2014年在广东各专业录取分数线(理科统计)

暨南大学2014年在广东各专业录取分数线(理科统计)

625 606 611 611 606 612 615 618 608 611 612 614 614 608
611 604 605 607 604 604 604 608 603 603 606 603 605 604
614 605 607 609 605 606 607 610 605 606 608 606 609 605
11
11
622
610
612
5463
16
16
617
611
613
6937
24
24
609
606
607
9623
17
17
618
607
609
6598
36
36
615
609
611
7572
21
21
615
610
611
7679
30
30
615
609
610
7553
15
15
610
608
609
9192
13
13
610
608
609
9134
20
20
609
603
606
9606
29
29
610
603
606
9253
14
14
611
605
607
9024
23
23
611
603
607
9011
14
181
10
10
611
609
610
8968
6
6
620

《暨南大学830数据结构2011-2019年考研真题及答案解析》

《暨南大学830数据结构2011-2019年考研真题及答案解析》
Ⅱ 历年考研真题试卷答案解析.............................................................................................49
暨南大学 2011 年招收攻读硕士学位研究生入学考试试题答案解析................................ 49 暨南大学 2012 年招收攻读硕士学位研究生入学考试试题答案解析................................ 64 暨南大学 2013 年招收攻读硕士学位研究生入学考试试题答案解析................................ 79 暨南大学 2014 年招收攻读硕士学位研究生入学考试试题答案解析（A 卷）..................... 96 暨南大学 2015 年招收攻读硕士学位研究生入学考试试题答案解析（B 卷）................... 113 暨南大学 2016 年招收攻读硕士学位研究生入学考试试题答案解析（A 卷）................... 130 暨南大学 2017 年招收攻读硕士学位研究生入学考试试题答案解析（A 卷）................... 144
3. 线性表的动态链表存储结构与顺序存储结构相比，优点是（ ）。
A. 所有的操作算法实现简单
B. 便于随机存取
C. 便于插入与删除
D. 便于节省存储器空间
4．若进栈序列为 1，2，3，4，5，6， 且进栈和出栈可以穿插进行，则可能出现的出
栈序列为（ ）。
A． 3，2，6，1，4，5
B．5，6，4，2，3，1
五、算法填空， （每空 2 分，共 16 分）
1.下面的算法是一个在元素按值递增排列，并以带头结点的单链表作存储结构的线性表

2014春 算法与数据结构 期中 上机考试(开卷)

2014春算法与数据结构期中上机考试(开卷)说明：(1) 每两人一组选1题。

不同的组所选择的题目不能相同。

(2) 开卷考试。

(3) 考试时间90分钟。

(4) 所有输入输出都是对文件操作。

(5) 工程构建时界面、数据与业务处理是分离的；函数的申明、定义与实现分别在不同的文件中，也是分离的。

1、用十字链表表示稀疏矩阵，并实现稀疏矩阵加法。

2、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

3、已知线性表L递增有序。

试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。

4、写一算法，从顺序表中删除自第i个元素开始的k个元素。

5、已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。

试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。

6、试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。

（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。

（2）以单链表作存储结构。

7、假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C.8、假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。

已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。

9、已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

暨南大学830数据结构2010,2012--2020年考研专业课真题

2020年全国硕士研究生统一入学考试自命题试题B卷********************************************************************************************学科、专业名称：网络空间安全研究方向：网络空间安全083900考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、单项选择题(每题2分，共30分)1. 下述关于顺序存储结构优点的说法，哪个是正确的（）A. 插入运算方便B. 可方便地用于各种逻辑结构的存储表示C. 存储密度大D. 删除运算方便2. 假设根结点为第1层，深度为h层的二叉树至少有( ) 个结点(h>1)；A. 2hB. 2h-1C. 2h+1D. 2h-13. 用单向链表来实现容量为n的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是( )A. 入栈操作的复杂度为O(1)B. 出栈操作的复杂度为O(1)C. 删除底部元素的复杂度为O(1)D. 插入一个新的堆栈底部元素复杂度为O(1)4. 以下关于递归算法的论述，不正确的是( )A. 递归算法的代码可读性好B. 递归算法可以提高程序运行效率C. 递归调用层次太深有可能造成堆栈溢出D. 递归调用层次太深会占用大量内存5. 设有字符集合{4,6,3,W,S}，将字符序列6W43S中的字符按顺序进入堆栈，出栈可发生在任何时刻。

则以下的出栈序列错误的是（）。

A. 64WS3B. 4W36SC. 6W34SD. WS4366. 在管理城市道路交通网络据时，最适合采用（）数据结构来对其进行存储。

A．有向图B．无向图C．树D．矩阵7. 具有k个顶点的完全有向图的边数为( )。

A. k(k-1)B. k(k-1)/2C. k2-1D. k2+18. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.A. 单链表B. 双链表C. 单循环链表D. 顺序表9. 由权为6,3,2,8的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（）。

暨南大学 数据结构 历年试题

一、判断题（每小题2分，共10分）。

1. 线性表的逻辑顺序与物理顺序总是一致的。

( )2. 堆排序是不稳定的排序方法。

( )3. 在非空二叉树中，任一结点均有两棵二叉树。

( )4. 一个无序的元素序列可以通过构造一棵二叉排序树而变成一个有序的元素序列。

( )5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。

( )二、单项选择题（每小题2分，共10分）1. 表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素需要移动元素的平均次数为（），删除一个元素需要移动元素的平均次数为（）。

A. (n-1)/2B. nC. n-1D. n/22. 对于一个头指针为L的带头结点的单链表，判定该表为空表的条件是（）。

A. L=NULL;B.L->next=NULL;C. L->next==L;D. L!=NULL;3. 以下数据结构中，（）是非线性数据结构。

A. 树B. 字符串C. 数组D. 栈4. 对线性表进行折半查找时，要求线性表必须（）。

A. 以顺序方式存储。

B. 以链式方式存储。

C. 以顺序方式存储，且结点按关键字有序排序。

D. 以链式方式存储，且结点按关键字有序排序。

5.在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。

A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序三、填空题（每小题2分，共10分）1. 在内部排序中，平均比较次数最少的是_________，要求附加的内存容量最大的是_________。

2. 由n个权值构成的赫夫曼树共有_________个结点。

3. 在单链表中，除首元结点外，任一结点的存储位置由_________指示。

4. 栈结构允许进行删除操作的一端称为栈的_________。

5. 设GetHead(p)为求广义表p的表头函数，GetTail(p)为求广义表p的表尾函数。

其中( )是函数符号，运算GetTail(GetHead((a,b),(c,d)))的结果是_________。

暨南大学_830数据结构2010--2017_考研真题／硕士研究生入学考试试题

A．求关键路径的方法B．求最短路径的Dijkstra方法
C．广度优先遍历算法D．深度优先遍算法
19.通过一趟排序就能从整个记录序列中选择出具有最大（或最小）关键字的记录，这种排序方法是( )。
A.堆排序B.快速排序C.直接插入排序D.归并排序
20.设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为( )。
13.在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。（）
14.在n个顶点的无向图中，若边数>n-1，则该图必是连通图。（）
15.一颗满二叉树同时又是一颗平衡树。（）
四.应用题（35分）
A. p->next=p->next->next B. p=p->next
C. p=p->next->next D. p->next=p
二．填空题(每空2分，共30分)
1.在堆排序，希尔排序，快速排序，归并排序算法中，占用辅助空间最多的是。
2.在散列表(hash)查找中，评判一个散列函数优劣的两个主要条件是：
A.单链表B.双链表C.单循环链表D.顺序表
6.线性表的链接实现有利于( )运算
A.插入B.读表元素C .查找D.定位
7.设连通图G的顶点数为n,则G的生成树的边数为( )
A. n B. n-1 C.2n D. 2n-1
8.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（）个元素。
A.n-i B.n-i+1 C.n-i-1 D. i
9.若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n,则第i个输出元素是（）
A.n-i B.n-i-1 C.n-i+1 D.不确定
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
考试科目：数据结构 共 4 页，第 4 页
);
2014 年招收攻读硕士学位研究生入学考试试题( A 卷)
********************************************************************************************
招生专业与代码：计算机系统结构 081201，计算机软件与理论 081202，计算机应用技术 081203，软件工程 083500，计算机技术(专业学位) 085211，软件工程(专业学位) 085212 考试科目名称及代码：数据结构 830
二．填空题(每空 2 分，共 20 分) 1. 线性结构中元素之间存在一对一关系，树型结构中元素之间存在 关系， 图型结构中元素之间存在 关系. 2. 单链表中设置头结点的作用是 . 3.由 n 个权值构成的哈夫曼树共有 个结点. 4. 已 知 一 个 图 的 邻 接 矩 阵 表 示 ， 删 除 所 有 从 第 i 个 结 点 出 发 的 边 的 方 法 是 . 5. 队列只允许在表的一端插入， 在另一端删除； 插入的一端叫 ， 删除的一端叫 ； 对队列的访问是按照 的原则进行的. 6. 在哈希查找方法中，要解决两方面的问题，它们分别是 及 .
考试科目：数据结构
1 1 1 1 1
15 25 40 图2
1
45
50 80
共 4 页，第 3 页
5.已知序列(12, 178, 200,530,765,149, 52,6),请采用链式基数排序方法对该序列作升序 排序, 给出排序过程.(12 分) 五．算法填空， （每空 2 分,共 20 分） 1. 以下算法功能是:插入元素 e 为新的栈顶元素,完成算法的空格部分. Status Push(SqStack &S, ElemType e) { if (S.top-S.base >= S.Stacksize) { S.base=(ElemType *) realloc(S.base, (S.Stacksize+STACKINCREME) * ① if ( ② ) exit (OVERFLOW); S.top=S.base+ ③ ; S.Stacksize=S.Stacksize+STACKINCREMENT; } *S.top= ④ ; top= ⑤ ; return OK; } 2.以下是图的广度遍历算法, 完成算法的空格部分. Void BFSTraverse( Graph G, Status(*visit)(int v)) { for (v=0;v<G.vexnum;++v) visited[v]=False; initQueue(Q); for (v=0; ⑥ ;++v) if (!visited[v]) { visited[v]=True; Visit(v); EnQueue(Q,v); while (!QueueEmpty(Q)) { ⑦ ; for (w=FirstAdjVex(G,u); w>=0 ; w=NextAdjVex(G,u,w )) if ( ⑧ ) { Visited[w]= ⑨ ; Visit(w); ⑩ ; } } } } 六．编写算法（25 分） 1. 设计将两个有序链表合并为一个有序链表的算法 . 假设有序链表的元素按照非递减排 列.(10 分) 2. 给定带权有向图 G 和源点 V0, 设计 V0 到其余顶点的最短路径.(15 分)
a1=5
a7=7 V7
1
V2 a3=2
1
V4
a5=4
5 a8=3
a6=9
1
1
图1
1 1
V6
1
V8 a9简述下列算法的功能.（6 分） void process( Sqlist &L) //L 为线性表,用顺序存储结构表示 { int i=0, j; While （i<L.length && L.elem[i]!=X） i++; for (j=i+1;j<L.length; j++) if (L.elem[j]!=X) { L.elem[i]=L.elem[j]; i++; } L.length=i; } 4.已知一棵 3 阶的 B-树如图 2 所示,依次插入关键字 30 及 90,分别画出每插入一个关键字后 所生成的 B-树. (7 分) 32 24
三．判断题（每题 1 分，共 10 分，正确的选 t，错误的选 f） 1.已知一颗树的先序序列和后序序列，一定能构造出该树. （ ） 2.双循环链表中，任一结点的前驱指针均为不空. （ ） 2 3.对于 n 个记录的集合进行冒泡排序，在最坏情况下的时间复杂度是 O(n ). ( ) 4. 快速排序是排序算法中最快的一种. （ ） 5. 设有序的关键字序列是（2，5，8，9，12，14，16，18，20，22，25），当用折半查找方 法查找关键字 22 时，需经 3 次比较运算. （ ） 6.向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度 h. （ ） 7.散列法存储的思想是由关键字值决定数据的存储地址。 （ ） 8.连通图的广度优先搜索中可以采用队列来暂存刚访问过的顶点. （ ） 9. 一棵 m 阶 B-树中每个结点最多有 m 棵子树，非终端结点最少有 2 棵子树. ( ) 10. 冒泡排序是稳定的. ( )
考试科目： 数据结构
共 4 页，第 1 页
13. 在 AOE 网中，完成工程的最短时间是（ ）. A．从源点到汇点的最短路径的长度 B．从源点到汇点的最长路径的长度 C．最长的回路的长度 D．最短的回路的长度 14. 设单链表中指针 p 指着结点 A,若要删除 A 之后的结点(若存在),则需要修改指针的操作为 ( ). A． p->next=p->next->next B． p=p->next C． p=p->next->next D． p->next=p 15.下面的序列中，( )是堆. A. 1，2，8，4，3，9，10，5 B.1，5，10，6，7，8，9，2 C. 9，8，7，6，4，8，2，1 D.9，8，7，6，5，4，3，7
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一．选择题(每题 2 分，共 30 分) 1.数据结构是研究数据的( )以及它们之间的相互关系. A. 理想结构,物理结构 B.理想结构,抽象结构 C. 物理结构,逻辑结构 D.抽象结构,逻辑结构 2.线性表的链接实现有利于( )运算 A.插入 B.读表元素 C. 查找 D.定位 3．从一个长度为 n 的顺序表中删除第 i 个元素（1≤i≤n）时，需向前移动（ ）个元素. A. n-i B. n-i+1 C. n-i-1 D. i 4.具有 n 个顶点的完全有向图的边数为( ). 2 2 A. n(n-1)/2 B. n(n-1) C. n D. n -1 5.快速排序在( )情况下最不利于发挥其长处. A. 被排序的数据量太大. B. 被排序数据中含有多个相同的关键字. C. 被排序的数据完全无序 D. 被排序的数据已基本有序 6. 线性表采用链式存储时,其地址( ). A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续与否均可以 7.一个栈的进栈序列是 a, b, c, d, e, 则栈的不可能的输出序列是( ) A. edcba B. decba C. dceab D. abcde 8. 采用顺序查找法查找长度为 n 的线性表时,每个元素的平均查找长度为 ( ) A. n B. n/2 C.(n+1)/2 D.(n-1)/2 9.下列哪种排序需要的附加存储开销最大( ). A 快速排序 B 堆排序 C 归并排序 D 插入排序 10.具有 6 个顶点的无向图至少应有（ ）条边才能确保是一个连通图. A．5 B．6 C．7 D．8 11.对具有 n 个结点的有序表中折半查找时，其时间复杂度是 ( ). A. O(log2n） B. O(nlog2n） C. O(n） D. O(n2） 12. 通过一趟排序就能从整个记录序列中选择出具有最大（或最小）关键字的记录，这种排序方 法是( ). A. 归并排序 B. 快速排序 C. 直接插入排序 D. 堆排序
考试科目：数据结构
共
4 页，第 2 页
四．简答题（共 45 分） 1.已知一棵二叉树的中序为 CDBAGFHE, 后序为 DCBGHFEA,画出这棵二叉树.(6 分) 2.如图 1 所示的 AOE 网(V1 表示工程的开始,V8 表示工程的结束), 假设工程从时间 0 开始, 求出所有事件和活动允许发生的最早及最晚时间,并给出关键路径.( 14 分) a1=5 V1 a2=3 V3 a4=12 V5