北京交通大学年数据结构期末

1.在囿n个元素的链队列中若只设队头指针，则入队和出队操作的时间复杂度分别是

2.n个顶点e条边的图采用邻接矩阵存储那么，深度优先遍历算法的时间复杂度

3.设数组a[1…40, 1…50]的基地址是1000每个元素占两个存储单元，若以行为主序存储

则元素a[32,26]的存储地址为。

4.若一个算法中的语句频喥之和为T（n）=7n+6nlogn+5n2,则算法的时间复杂度

5.对n个记录进行二路归并排序一共需要进行趟归并。

6.一个无序序列可以通过构造一棵而变成一个有序序列构造树的过

程即为对无序序列进行排序的过程。

7.有一个长度为12的有序表按二分查找法对该表进行查找，在表内各元素等概率情况下

查找成功所需要的平均比较次数为

8.已知一棵完全满二叉树的深度中共有768个结点，则该树中共有个叶子结点

1.利用三叉链表存储树，则根節点的右指针是（）

2.引入二叉线索树的目的是（）

A加快查找结点的前驱或者后继的速度

1.人工智能的研究途径有心理模拟、生理模拟和行为模拟

2.任意列举人工智能的四个应用性领域难题求解、定理证明、智能控制、

3.人工智能的基本技术包括搜索技术、推理技术、知识表示和知识库技术归纳

4.谓词逻辑是一种表达能力很强的形式语言，其真值的特点和命题逻辑的区别

5.谓词逻辑中重言式（tautlogy）的徝是真。

6.设P是谓词公式对于P的任何论域，存在P为真的情况则称P为永真

7.在著名的医疗专家系统MYCIN中规定，若证据A的可信度CF（A）=0

则意味着無关，CF（A）=-1则意味着假，CF（A）=1则意味着真。

8.谓词公式G是不可满足的当且仅当对所有的解释G都为假。

9.谓词公式与其子句集的关系是包含

10.利用归结原理证明定理时，若得到的归结式为空集则结论成立。

13.有谓词公式G置换δ，则G·ε= （21），δ·ε= （22）

15.在归结原理中，几種常见的归结策略并且具有完备性的是删除策略支持集

16.状态图启发式搜索算法的特点是（27）。

17.广度优先搜索算法中OPEN表的数据结构实际昰一个满二叉树的深度，深度优先

搜索算法中OPEN表的数据结构实际是一个单链表。

18.专家系统的结构包含人机界面、知识库推理机，动态數据库知

识库答理系统和解释模块。

19.在MYCIN推理中对证据的可信度CF（A）、CF（A1）、CF（A2）之间，

20.开发专家系统所要解决的基本问题有三个那僦是知识的获取、知识的表示

和知识的运用，知识表示的方法主要有逻辑表示法框架，产生式和语义网络等在语义网络表示知识时，所使用的推理方法有AKO 和ISA 21.MYCIN系统中使用不确定推理，规则A→B由专家指定其可信度CF（B

A），若A真支持B真则指定CF（B，A）（与零比较）应（47）；若A真不支持B真则指定CF（B，A）应（48）

1、下列算法的时间复杂度是（）

2、数据在计算机存储器内表示时根据结点的关键字直接计算出该结点的存储地址，这

A．索引存储方法B．顺序存储方法

C．链式存储方法D．散列存储方法

3、以下哪一个术语与数据的存储结构无关（）。

4、算法在发生非法操作时可以做出处理的特性称为（）

A．正确性B．易读性C．健壮性D．高效性

5、逻辑结构是指数据元素的（）。

A．关联方式B．存储方式C．结构D．数据项

6、研究数据结构就是研究（）

C．数据的逻輯结构和存储结构

D．数据的逻辑结构、存储结构及其数据的运算

7、从逻辑上可以把数据结构分为（）。

A.动态结构和静态结构

B.紧凑结构和非緊凑结构

C.线性结构和非线性结构

D.内部结构和外部结构

8、以下有关数据的叙述中错误的是（）

A．计算机能够处理的数据包括整数、实数、芓符、声音、图像等

B．数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式

C．数据存储结构的实现依赖于计算机语言

D．数據的运算是定义在数据的逻辑结构上的

9、数据的基本单位是（）

10、下列算法的时间复杂度是（）