基本信息

---

下载

文档摘要

---

2025年西安电子科技大学计算机学院复试试题

一、数据结构与算法

1.单项选择题

（1）在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。

A.O(1)

B.O(n)

C.O(n^2)

D.O(log?n)

答案：B。分析：在有序单链表中插入新结点，需遍历链表找到合适位置，平均要遍历约n/2个结点，时间复杂度为O(n)。

（2）若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是n，则第i个输出元素是（）。

A.n-i

B.n-i+1

C.i

D.不确定

答案：B。分析：栈是后进先出结构，输