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
相关内容
相关标签