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

一、填空题

1．

线性表

【答案】(n﹣1)/2

【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。

2． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有 检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

3． 在下面的程序段中，对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次。

4． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)

【答案】93

【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。

5． 假定查找有序表 中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。

【答案】

表

第 2 页，共 61 页 用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。 在B 【解析】折半查找时每个的次数如表所示:

平均查找次数为

6． 已知二维数组

【答案】1196 。 中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4

7． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储

8． 实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++＝*t++或(*s++＝*t++)!＝'\0’

9． 模式串

【答案】01122312

10．一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。

【答案】有穷性；确定性；可行性

11．对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

12．从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;

13．空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

第 3 页，共 61 页 的next 函数值序列为_____。 ；2；k

14．高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】

。当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为

一个元素时，此时堆的元素个数最少，元素个数为。

15．有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)

【答案】3个

【解析】以3，4先出栈的序列有34521、34215、34251共3个。

二、单项选择题

16．在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）

A. 将文件内容读到内存中

B. 将文件控制块读到内存中

C. 修改文件控制块中的读写权限

D. 将文件的数据缓冲区首指针返回给用户进程

【答案】B

【解析】概念

17． 当字符序列作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ）。

A.4个

B.5个

C.3个

D.6个

图

【答案】C

【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t ，有两种结果

因此总共有3种结果。

18．执行完下列语句段后，f 值为（ ）。

第 4 页，共 61 页 和，若首字符为，

则只有一种结果