2007 年招收攻读硕士学位研究生入学统一考试试题
科目名称:计算机系统结构
考生须知:
1.本试卷满分为 150 分,全部考试时间总计 180 分钟。
2.所有答案必须写在答题纸上,写在试题纸上或草稿纸上一律无效。
数据结构部分(共 70 分)
一、选择题(共 10 分,每题 1 分)
1、对于顺序存储的线性表,访问结点和增加结点的时间复杂度为( )
A. O(n) O(n) B. O(n) O(1) C .O(1) O(n) D .O(1) O(1)
2、对于一个头指针为 head 的带头结点的单链表,判断该表为空的条件是( )。
A. head=NULL B.head? next=NULL
C.head? next=head D.head!=NULL
3、在双向链表中删除指针 p 所指的结点时需要修改指针( )。
A. p? llink ? rlink=p ? rlink ; p? rlink ? llink=p ? llink
B.p? llink=p ? llink ? llink ; p? llink ? rlink=p
C.p? rlink ? llink=p ;p? rlink=p ? rlink ? rlink
D. p? rlink=p ? llink ? llink ;p? llink=p ? rlink ? rlink
4、若一个栈的输入序列为 1、2、3、…、n,输出序列的第一个元素为 i,则第 j 个输出元素
为( )。
A. i-j-1 B .i-j C .j-i+1 D.不确定
5、若度为 m 的哈夫曼树中,其叶结点个数为 n,则非叶结点的个数为( )。
A. n-1 B.
/ 1n m -
? ?
? ?
C. D.
( 1) /( 1)n m- -
?
?
?
?
/( 1) 1n m- -
? ?
? ?
6、一棵二叉树的前序遍历序列为 ABCDEFG ,它的中序遍历序列可能是( )。
A. CABDEFG B.ABCDEFG
C.DACEFBG D.ADBCFEG
7、一棵左右子树都不空的二叉树在前序线索化后,其中空的链域的个数为( )
A. 0 B.1 C.2 D.不确定
8、从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序,则该二叉树
是( )。
A.二叉排序树 B. Huffman 树 C.堆 D.二叉平衡树
9、若邻接表中有奇数个表结点,则一定是( )。
A.图中有奇数个结点 B.图中有偶数个结点
C.图为无向图 D.图为有向图
科目名称:计算机系统结构 第 1 页 共 4 页