《数据结构》期末考试试题及答案

《数据结构》期末考试试题及答案

《数据结构》期末考试试题及答案

(2003-2004学年第2学期)

单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C

一、1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（c）。

(A)、正确性(B).可行性(C).健壮性(D).输入性

2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d）。

for(i=n-1；i>=0；i--)

for(j=0；j(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（a）。（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（d）。（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（c）层上。（A）、k-1（B）、k（C）、k-1和k（D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11（B）、13（C）、48（D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（a）遍历方法的推广。（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（a b）Q（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;7试写出求该二叉树叶子结点数的算法5voidCountLeaves(Bi

(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)

3．折半查找法适用于（a）。

（A）、有序顺序表（B）、有序单链表

（C）、有序顺序表和有序单链表都可以（D）、无限制

4．顺序存储结构的优势是（d）。

（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问

5．深度为k的完全二叉树，其叶子结点必在第（c）层上。

（A）、k-1（B）、k（C）、k-1和k（D）、1至k

6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）

（A）、11（B）、13（C）、48（D）、37

7．图的Depth-First Search(DFS)遍历思想实际上是二叉树（a）遍历方法的推广。

（A）、先序（B）、中序（C）、后序（D）、层序

8．在下列链队列Q中，元素a出队的操作序列为（a b）

Q

（A）、p=Q.front->next; p->next= Q.front->next;

（B）、p=Q.front->next; Q.front->next=p->next;7试写出求该二叉树叶子结点数的算法5voidCountLeaves(Bi