当前位置：问答库＞考研试题

一、填空题

1． 已知t) ，LEN(t)＋1))

:

【答案】 ；；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。

2． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。

【答案】比较；移动

3． —个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

4． 已知有序表为(12，18，24，35，47，50，62，83，90，115，134) 当用二分法查找90时，需次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2; 4; 3

【解析】二分法查找元素次数列表

查找100是找到115就停止了。

5． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

6． 深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】

7． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。

【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)

【解析】当i ＝l 时，赋值语句就被执行了一次。当i ＝2时，赋值语句被执行了1＋2次。当i ＝3时，赋值语句被执行了1＋2＋3次。...... 可以推出赋值语句总共被执行了1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋... ＋n) ＝n(n＋1)(n＋2)/6次。

8． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。

【答案】完全；只有一个叶结点的二叉树

9． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；

10．设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。

【答案】（ ）；(（ ）) ；2；2

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

11．当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。

【答案】0；n+1；top[l]+l＝top[2]

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

12．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

二、单项选择题

13．若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1, 则该二叉树的中序遍历序列不会是（ ）。

A.1, 2, 3, 4

B.2, 3, 4, 1

C.3, 2, 4, 1

D.4, 3, 2, 1

【答案】C

【解析】题目中的二叉树的先序序列和后序序列正好相反, 这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。

从左至右, 这8棵二叉树的中序序列分别为:

(1)4, 3, 2, 1,

(2)3, 4, 2, 1

(3)2, 4, 3, 1

(4)2, 3, 4, 1

(5)1, 4, 3, 2

(6)1, 3, 4, 2

(7)1, 2, 4, 3

(8)1, 2, 3, 4

显然选项C 的中序序列不会出现。

14．在OSI 参考模型中，自下而上第一个提供端到端服务的层次是（ ）.

A. 数据链路层

B. 传输层

C. 会话层

D. 应用层

【答案】B

【解析】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路层不满足题意. 题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范，都不涉及传输. 所以本题答案应该是B 项. 在OSI 模型中网络层提供的是主机到主机的通信服务.

15．下列序列中，（ ）是执行第一趟快速排序后所得的序列。 A. B. C. D.

【答案】C

【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。