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

2018年西安理工大学计算机科学与工程学院863数据结构考研基础五套测试题

  摘要

一、填空题

1. 栈是_____的线性表,其运算遵循_____的原则。

【答案】操作受限(或限定仅在表尾进行插入和删除操作) ;后进先出

2. 遍历图的过程实质上是_____,广度优先遍历图的时间复杂度____;深度优先遍历图的时间复杂度_____,两者不同之处在于_____,反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程;0(n+e);0(n+e);访问顶点的顺序不同;队列和栈

【解析】广度优先遍历图使用队列这种数据结构,深度优先遍历图使用栈这种数据结构。

3. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接,请填空完善之。

h 为附加头结点指针

(_____)

_____;

【答案】(1)p!=NULL //链表未到尾就一直进行

(2)q //将当前结点作为头结点后的第一元素结点插入

4. 实现字符串拷贝的函数strcpv 为:

(_____)

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

5. 已知t) ,LEN(t)+1))

:

【答案】 ;;ASSIGN(S,U) ;ASSIGN(V,SUBSTR(S,INDEX(S,,求REPLACE(S,V ,m) =_____。

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

二、单项选择题

7. 将森林转换为对应的二叉树,若在二叉树中,结点u 是结点v 的父结点的父结点,则在原来的森林中,u 和v 可能具有的关系是( ).

(1)父子关系

(2)兄弟关系

(3)U的父结点与V 的父结点是兄弟关系

A. 只有(1)

B.(1)和(2)

C.(1)和(3)

d.(1)、(2)和(3)

【答案】B

【解析】首先,在二叉树中,若结点U 是结点v 的父结点的父结点,那么u 和v 的关系有如下4种情况:

接下来,根据森林与二叉树的转换规则,将这4种情况还原成森林中结点的关系. 其中: 情况(1),在原来的森林中u 是v 的父结点的父结点;

情况(2),在森林中u 是v 的父结点;

情况(3),在森林中u 是v 的父结点的兄弟;

情况(4),在森林中u 与v 是兄弟关系.

由此可知,题目中的(1)、(2)是正确的.

8. 若X 是后序线索二叉树中的叶结点, 且X 存在左兄弟结点Y , 则X 的右线索指向的是 ( )

A.X 的父结点

B. 以Y 为根的子树的最左下结点

C.X 的左兄弟结点Y

D. 以Y 为根的子树的最右下结点

【答案】A

【解析】根据后续线索二叉树的定义, X 结点为叶子结点且有左兄弟, 那么这个结点为右孩子结点, 利用后续遍历的方式可知X 结点的后继是其父结点, 即其右线索指向的是父结点。

9. 链表不具有的特点是( )。

A. 插入、删除不需要移动元素

B. 可随机访问任一元素

C. 不必事先估计存储空间

D. 所需空间与线性长度成正比

【答案】B

【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置,线性表中的任一数据元素都可随机存取。

10.在一个文件被用户进程首次打开的过程中, 操作系统需做的是( )

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

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

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

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

【答案】B

【解析】概念

11.元素a , b , c , d , e 依次进入初始为空的栈中, 若元素进栈后可停留、可出栈, 直到所有元素都出栈, 则在所有可能的出栈序列中, 以元素d 开头的序列个数是( )。

A.3

B.4

C.5

D.6

【答案】B

【解析】d 首先出栈后的状态如下图所示。

此时可有以下4种操作:

(1)e进栈后出栈, 出栈序列为decba 。

(2)c出栈, e 进栈后出栈, 出栈序列为dceba 。

(3)cb出栈, e 进栈后出栈, 出栈序列为dcbea 。

(4)cba出栈, e 进栈后出栈, 出栈序列为dcbae 。

12.要连通具有n 个顶点的有向图,至少需要( )条边。

A.n -1

B.n

C.n+1

D.2n

【答案】B