南京邮电大学
2006年攻读硕士学位研究生入学考试
数据结构 试题
考生注意：本试卷共4页。所有答题均写在答题纸上(包括单选和填空题)，请务必准确标明所答题的题号和填空号。
单选题(每题3分，共30分)
可以使用大O记号表示一个算法的时间复杂度。下列标识中不正确的是___D___。
n^2+2n=O(n^3) B. nlog_2 n+2n=O(n^2)
C. n^2+nlogn=O(n^2 log_2 n) D. n^2+nlog_2 n=O(nlog_2 n)
下列术语中，_____B_____与数据的存储结构无关。
循环队列 B. 堆栈 C. 散列表 D. 单链表
设线性表非空，采用下列_____D_____所描述的链表可以在O(1)时间内在表尾插入一个新结点。
带表头结点的单链表，一个链表指针指向表头结点
带表头结点的单循环链表，一个链表指针指向表头结点
不带表头结点的单链表，一个链表指针指向标的第一个结点
不带表头结点的单循环链表，一个链表指针指向表的第一个节点
设主串为“abceabceyabceabceab”，字串为“abceabcea”。则在KMP匹配第一趟失配后下一趟匹配开始时，子串指针指示的字符是____A____。
a B. b C. c D. e
二叉树中第5层上的结点个数最多为____C____，假定根节点层次为1.
8 B. 15 C. 16 D. 32
用DFS遍历一个有向无环图，并在DFS算法退栈返回时打印当前顶点，则输出的顶点序列是____C____。
A. 拓扑有序的 B. 无序的
C. 逆拓扑有序的 D. 按顶点编号次序的
下面____A____算法可用于求无向图的所有连通分量
广度优先遍历 B. 拓扑排序
C. 求最短路径 D. 求关键路径
设有以元素10，9，20，6，8，23，21，17为叶结点的8路合并胜方树。在输出一个元素后，将有一个新元素补充到相应的叶结点中。在重构的胜方树中，应有____D____个元素需要修正。
1 B. 2 C. 3 D. 4
在一棵二叉搜索树上搜索一个元素的平均时间复杂度为____D____。 | 
