2008数据结构学位考试试卷B.doc

O八-O九学年第一学期
申请广州大学学士学位抽考课程试卷(B )
课程名称数据结构考试形式(闭卷)
系别专业班级学号姓名
试题
一
二
三
四
五
六
总分
评卷人
分值
20
10
20
30
20
100
得分
考试时间:2009年1月日
答题时间:120分钟
考试地点:
考试形式:闭卷
一、单项选择题(每题只有一个正确答案,每题1分,共20分)
分值
20
得分
为了实现图的深度优先遍历,其非递归的深度优先搜索算法使用的一个辅助数据结构为( )。
A. 栈 B. 队列 C. 二叉树 D. 树
设无向图的顶点个数为n,则该图最多有( )条边。
A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)
有向图的一个顶点的度为该顶点的( )。
A. 入度 B. 出度 C. 入度与出度之和 D. (入度+出度)/2
如果一个元素序列基本有序时,则选用( )方法较快。
B. 直接选择排序 C. 堆排序
利用5个值作为叶节点的权生成的哈夫曼树中共计有( )个节点。
B. 5 C. 9 D. 4
在对n个元素进行快速排序的过程中,第一次划分最多需要交换( )对元素。
A.「n/2」 -1 +1
在对n个元素进行直接选择排序的过程中,需要进行( )趟选择和交换。
B. n+1 C. n-1 D. n/2
下列排序算法中,____算法可能会出现下面情况:初始数据有序时,花费的时间反而最多。
  A、堆排序 B、冒泡排序  C、快速排序 D、直接插入排序
排序二叉树的_______遍历的序列是一个以关键字的递增的有序序列
A、先根遍历 B、中根遍历 C、后根遍历 D、层次遍历
在二叉搜索树中查找一个元素时,其时间复杂度大致为( )。
(n) B. O(1) (log2n) D. O(n2)
一个栈的输入序列是1,2,3,则栈的不可能的输出序列是_________。
A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,2
下面的二叉树中,__________是满二叉树.
A. B. C. D
.
有6个结点的无向图至少应有_______条边才能确保它是一个连通图。

下面程序段的时间复杂度是( )
for(i=0;i<n;i++)
for(j=1;j<m;j++)
A[i][j]=0;
(n) (m+n+1) (m+n) (m*n)
在单链表中,指针p指向元素为x的结点,实现“删除x的后继”的语句是( )
=p->next; ->next=p->next->next;
->next=p; =p->next->next;
在下列排序方法中,平均时间性能为O(nlogn)且空间性能最好的是( )

一个数组元素a[i]与( )的表示等价。
A.*(a+i) +i C.*a+i D.&a+i
含有n个结点的完全二叉树的深度为( )。
A.[log2n] B.[log