2007-2008学年《数据结构》B.doc

华侨大学《数据结构》试卷（B）
系别： 班级： 学号：
姓名： 考试日期： 年 月 日
题号一二三四五总分得分一、选择填空题（每题1.5分，共15分）
1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为（）。
An Bn/2 C(n+1)/2 D(n-1)/2
2、已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（）。
AO(1) BO(m) CO(n) DO(m+n)
3、若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（）。
A4 B5 C6 D7
4、由权值分别为11，8，6，2，5的叶子结点生成一棵赫夫曼树，它的带权路径长度WPL为（）。
A24 B71 C48 D53
5、已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到（）。
AP=″SCIENCE″BP=″STUDY″CS=″SCIENCE″DS=″STUDY″
6、二维数组A[4][7]按列优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4]的存储地址为（）。
A139 B145C158D162
7、下列陈述中正确的是()。
A二叉树是度为2的有序树
B二叉树中结点只有一个孩子时无左右之分
C二叉树中必有度为2的结点
D二叉树中最多只有两棵子树，并且有左右之分
8、n个顶点的无向完全图中含有向边的数目最多为()。
An-1Bn Cn(n-1)/2Dn(n-1)
9、假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为()。
Afront==rear Bfront!=NULL
Crear!=NULL Dfront＝＝NULL
10、下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？()
A直接插入排序 B冒泡排序 C快速排序 D简单选择排序
二、填空题（每空1分，共10分）
1、若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 。
2、数据结构的存储结构包括顺序、 、索引和散列等四种。
3、假设一个10阶的下三角矩阵A，按行优先顺序压缩存储在一维数组C中，则C数组的大小应为____________________。
4、一棵高度为4的二叉树中最少含有 个结点，最多含有 个结点；一棵高度为4的完全二叉树中，最少含有 个结点，最多含有 个结点。
5、在对长度为n的关键字序列进行堆排序的过程中，对堆顶元素进行堆调整的筛选运算的时间复杂度为 ，整个堆排序过程的时间复杂度为 。
6、若对序列{49，38，65，97，76，13，27，50}采用冒泡排序法排序，则第二趟结束后序列的状态是 。
三、解答题（每题5分，共30分）
1、指出下面算法中，带下划线的语句的语句频度，并估计该算法的时间复杂度。
intfun(intn)
{
s=0; t=0;
for(i=1;i<n;i++){
s+=2;
for(j=n;j>=i;j--)t++;
}
returns+t;
}
2、设循环队列的总长度为5，入队的序列为A1，A2，A3，A4，然后A1，A2出队，最后A5，A6入队，请画出最后的循环队列，并写出在循环队列中判断队空和队满的条件。
3、某二叉树bt中序遍历序列为：ABCEFGHD，后序遍历序列为：ABFHGEDC，请构造该二叉树（画出树形），并画出对应的先序线索（不带头结点）。
A
B
D
E
C
无向图G
4、试画出如下图的无向图G的邻接表表示，要求邻接表中的各顶点的邻接链表中的表结点按顶点序号从小到大排列。根据你所给出的邻接表，给出从A出发的深度优先搜索序列，并给出其深度优先搜索dfs生成树。
5、设有一个关键字输入序列{31，55，11，37，46，73，7}，试从空树开始构造平衡二叉排序树，画出每加入一个结点时二叉树的形态，若发生不平衡，请指出平衡调整的类型和调整结果。最后，计算在等概率情况下，查找成功的平均查找长度ASL。
6、判别序列{12，2，16，30，8，28，4，10，20，6，18}是否为大顶堆，如果不是，则写出将其调整为大顶堆的过程（用树形表示）。
四、算法阅读题（每题5分，共15分）
1、head为不带头结点的单链表头