当前位置:问答库>考研试题

2018年鲁东大学信息与电气工程学院828计算机科学与技术专业基础之数据结构考研仿真模拟五套题

  摘要

一、填空题

1. 堆是一种有用的数据结构。堆排序是一种_____排序,堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时,堆排序的时间复杂度是_____,所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。

【答案】选择;完全二叉树;

2.

线性表

【答案】(n﹣1)/2

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

3. 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10],每个元素占2个单元,按行优先顺序存储,第一个元素的存储起始位置为b ,则存储位置为b+50处的元素为_____。

【答案】A[2][3]

【解析】令这个元素的行标为i ,列标为j 。则它的存储位置是(ll*i+j +l ﹣l)*2+b 。当其值为b +50时,则i =2,j =3。

4. 顺序查找n 个元素的顺序表,若查找成功,则比较关键字的次数最多为_____次;当使用监视哨时,若查找失败,则比较关键字的次数为_____。

【答案】n ; n+1

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时,需要多一个存储空间来存监视哨。

5. 设数组

址为_____。

【答案】9174;8788

【解析】设一个元素的行标为i ,列标为j 。若以行序为主存储顺序,则它的存储地址为2000+((i﹣l)*80+j ﹣

1) 2。若以列序为主存储顺序,则它的存储地址为2000+((j﹣l)*50+i ﹣l)*2。

;O(1);满足堆的性质 用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是_____。 的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素a[45,68]的存储地址为_____;若以列序为主序顺序存储,则元素a[45,68]的存储地

6. 已知二叉排序树的左右子树均不为空,则_____上所有结点的值均小于它的根结点值,_____上所有结点的值均大于它的根结点的值。

【答案】左子树;右子树

【解析】二叉排序树(binary sort tree)或者是一棵空树,或者是具有下列性质的二叉树:①若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;②若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;③它的左、右子树也分别为二叉排序树。

7. 从平均时间性能而言,_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

8. 设为哈夫曼树的叶结点数目,则该哈夫曼树共有_____个结点。 【答案】

【解析】哈夫曼树只有度为0和2的节点。

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

【答案】0;n+1;top[l]+l=top[2]

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

10.求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】

二、单项选择题

11.一个具有1025个结点的二叉树的高h 为( )。

A.11

B.10

C.11至1025之间

D.10至1024之间

【答案】C

【解析】当一棵树是完全二叉树时,其高度最低,此时高度为11,当一棵树的结点在一条线上时,此时最高,这时二叉树的高度是1025。

12.以下与数据的存储结构无关的术语是( )。

A. 循环队列

B. 链表

C. 哈希表

D. 栈

【答案】D

【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。

13.某计算机主存容量为64KB ,其中ROM 区为4KB ,其余为RAM 区,按字节编址. 现要用2K ×8位的ROM 芯片和4K ×4位的RAM 芯片来设计该存储器,则需要上述规格的ROM 芯片数和RAM 芯片数分别是( )

A.1、15

B.2、15

C.1、30

D.2、30

【答案】D

【解析】主存储器包括RAM 和ROM 两部分,由于ROM 区为4KB ,则RAM 区为60KB. 存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种. 选用2Kx8位的ROM 芯片,只需采用2片芯片进行字扩展便可得到4KB 的ROM 区;选用4Kx4位的RAM 芯片,需采用(60)/4*2片芯片进行字和位同时扩展便可得60KB 的RAM 区.

14.可以用( )定义一个完整的数据结构。

A. 数据元素

B. 数据对象

C. 数据关系

D 抽象数据类型

【答案】D

【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素,数据元素之间的关系,以及可以进行的操作。

15.下列关于最小生成树的叙述中, 正确的是( )。

Ⅰ. 最小生成树的代价唯一

Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ. 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同

IV. 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅲ

D. 仅Ⅱ、Ⅳ