2018年南京工业大学828数据结构与操作系统真题.docxVIP

2018年南京工业大学828数据结构与操作系统真题

南京工业大学

2018年硕士研究生入学考试初试试题（A卷）

科目代码：828科目名称：数据结构与操作系统满分：150分

注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；

③本试题纸须随答题纸一起装入试题袋中交回！

第一部分：数据结构（共90分）

单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。每小题2分，共30分）

1、通常所说的时间复杂度是指。

A.语句的频度

B.算法的时间消耗

C.渐进时间复杂度

D.最坏的时间复杂度

2、等概率条件下,在由n个结点构成的顺序表上做插入结点操作,需平均移动的结点数为。

A.n

B.(n-1)/2

C.n/2

D.(n+1)/2

3、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是。

A.O(1)

B.O(n)

C.O(n2)

D.O(logan)

4、从一个栈顶指针为top的链栈中删除一个结点时,用x保存被删除的结点,20应执行下列命令。

A.x=top:top-topnext

B.top=Top-next;=topdata

B.C.x=Top-data;D,x=Top-data;Top-top-next

5、循环队列SQ队满的条件是。

A.SQ-rear=SQ-froat;

B.(SQ-rear+1)%MAXLEN=SQ-froat

C.SQ-rear+2=SQL-froat

D.(SQ-rear+2)%MAXLEN=SQLfroat

6、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作(称为输出受限的双端队列),若五个元素a,b,c,d,e依次进队,则不可能得到的出队顺序是。

A.bacde

B.dbace

C.dbcae

D.ecbad

7、对特殊矩阵采用压缩存储的目的主要是为了。

A.表达变得简单

B.对矩阵元素的存取变得简单

C.去掉矩阵中的多余元素

D.减少不必要的存储空间

8、一颗具有25个叶结点的完全二叉树最多有个结点。

A.48

B.49

C.50

D.51

9、在线索二叉树中,t所指结点没有左子树的充要条件是。

A.t-left=NULL

B.t-Itag=TRUE

C.t-Itag=TRUE且t-left=NULL

D.以上都不对

10、设有一个二维数组A[m][n],假设A[O][0]存放位置在644,A[2][2]存放位置在676,每个元素占一个空间,则A[3][3]存放位置为。

A.688

B.678

C.692

D.696

11、将一棵树转换为二又树后,这棵二叉村的形态是。

A.唯一的,根结点没有左孩子

B.唯一的,根结点没有右孩子

C.有多种,根结点都没有左孩子

D.有多种,根结点都没有右孩子

12、在图1中,从顶点a出发,按深度优先遍历,不可能得到的顶点的序列为。

A.a,b,e,c,d,f

B.a,b,e,c,f,d

C.a,c,d,f,b,e

D.a,b,c,d,f,e

13、下面关于工程计划的AOE网的叙述中，不正确的是。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成

C.所有关键活动都提前完成，那么整个工程将会提前完成

D.某些关键工程若提前完成，那么整个工程将会提前完成

14、分别以下列列序构造二叉排序数(二叉查找树,与用其他三个数列所构造的结果不同的是。

A(30,10,40,5,50,20,35)B.(30,40,5,50,10,20,35)

C.(30,40,10,50,5,35,20)

D.(30,10,5,20,40,50,35)

15、有一组关键字(3,12,258,33,15,22,64,20,55,26),采用除留余数法构造散列函数,H(key)=keymod11,则将发生次冲突。

A.3

B.4

C.5

D.6

二、综合应用题（5小题，共60分）

16、已知一个箭头结点的单项箭表,试完成函数voldcopyList(LISTh1,listh2),实现将链表h1中的所有元素复制到链表h2中,具体要求如下:

(1)定义链表的结点的抽象数据类型node,其所包涵的数据为:intdata,并定义链表结点的型LIST(node类型的指针);

(2)在(1)的基础上完成函数copyList。

17、试完成求二叉树的叶子结点的函数intleafNunt(BTREE,T),具体如下:

(1)定义用左右键方法表示的二叉树的抽象数据类型node和型BTREE(node)类型的指针,

(2)编写函数leafNunt(BREET),返回树T的叶子结点的个数。

18、现在所有如下9个元素:7、16、49、82、5、31、6、2、44