福州大学20XX年招收硕士/博士研究生入学考试试卷
招生学院 数学与计算机科学学院 招生专业 计算机相关专业
考试科目 数据结构程序设计 科目编号 450
一、单项选择题（30 points 3points each blank）
1下列程序的时间复杂度为（）
(C语言版) （PASCAL语言版）
for（i=1;i<=n;i++）{ for i:=1 to n do
k=1; begin k:=1;
while(k
A.O(n) B.O(nlogn) C. O(n^2) D. O(1)
2在对n个元素的序列进行排序时，堆排序所需的辅加存储空间是（）
A.O(logn) B.O（1) C. O(n) D. O(nlogn)
3．若二叉树上只有度为0和2的结点，且度为0的结点数为h，则该二叉树的结点数为（）
A2h-1 B. h C. 2h D. h+1
4．中缀表达式 （a+b）*（c+d）+（e+f）*h的相应后缀表达式为（）
A.ab+cd+*ef+h*+ B.ab+cd+e*f+h*+
C.abc+d+*ef+h*+ D.ab+cd+*ef+h+*
5．模式串ABBABABBAB的前缀函数为（）
A.000120XX12 B.100120XX12 C. 0001212345 D. 1001212345
6．设一个栈输入序列为：1，2，……n（1
C.…（k ^2）…k…（k ^3）… D. …（k ^3）…k…（k ^2）…
