中央广播电视大学2001——2003学年度第二学期期末考试
计算机第六学期数据结构试题
一、单选题（每小题2分，共8分）
1、在一个单链表HL中，若要向q所指结点之后插入一个由指针p指向的结点，则执行
A、HL=p;p->next=HL
B、p->next=HL;HL=p
C、P->next=q->next;q->next=p
D、p->next=q->next;q=p>next
2、在一棵深度为5的完全二叉树中，至少含有
个结点。
A、15
B、16 C、30
D、31
3、从一棵深度为h的二叉搜索树中查找一个元素时，其时间复杂度为
。
A、O(h)
B、O(h2)
C、O(log2h)
D、O(n*log2h)
4、由权值分别为3，8，10，2，6的叶子结点生成一棵哈夫曼树，该树中双分支结点数为
A、2 B、3
C、4 D、5
二、填空题（每空1分，共32分）
1、向一长度为n的有序单链表中插入一个元素时，为寻找插入位置需要平均比较
个元素。
2、在以HL为表头指针的单链表和循环单链表中，链表为空的条件分别为
和
3、在一个稀疏矩阵的带行指针向量的链接存储中，每个元素结点共包含有
个域，其中
个为指针域。
4、向一个链栈插入一个p所指向的结点时，需要把栈顶指针的值赋给p所指向的结点的
，然后把p赋给
。
5、在用一个维数
组A[N]存储一个顺序循环队列时，若队列的首、尾指针分别用f和r表示，则队列长度为
。
6、对于一棵具有30个结点的二叉树，若一个结点的编号为5，则它的左孩子结眯的编号为
，右孩子结点的编号为
，双亲结点的编号为
。
7、在一棵高度为7的理想平衡树中，最少含有
个结点，最多含有
个结点。
8、对于一个具有n个结点的堆，对其进行插入运算的时间复杂度和空间复杂度分别为
和
。
9、在一个具有n个顶点的无向连接通图中，至少包含有
条边，至多包含有
条边。
10、对于一个具有n个顶点和e条边的有向图和无向图，若采用邻接表表示，则所有顶点单链表中边结点的个数分别为
和
。
11、以二分查找方法从长度为20的有序表中查找一个元素时，平均查找长度为
。
12、假定一个线性表为（12，23，74，55，63，40，82，36，25，45，64，78），若散列函数为h(k)=k%17，则散列地址分别为4，5，6的元素个数依次为
、
、和
。
13、在线性表的散列存储中，装填因子又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则
等于
。
14、在一棵m阶B-树上，树根结点的子树最少为
个，最多为
个，其关键字个数最少为
，最多为
。
15、在对n个元素进行堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为
，空间复杂度为
。
16、归并排序的时间复杂度为
，空间复杂度为
。
三、运算题（每小题6分，共24分）
1、
假定一棵二叉树广义表表示为a(b(d)),c(e(,g)),f(,h))),分别写出对它进行先序、中序、后序、按层遍历的结果。
先序：
中序：
后序：
2、 已知一个图的顶点集V和边集G分别为：
V={0，1，2，3，4，5，6，7}；
E={（0，1）3，（0，3）5，（0，5）18，（1，3）7，（1，4）6，（2，4）10，（2，7）20，（3，5）15，（3，6）12，（4，6）8，（4，7）12}；
按照普里姆算法从顶点2出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
，
，
，
，
，
，
3、 已知一个图的顶点集V和边集G分别为；
V={0，1，2，3，4，5，6，7，8}
E={<0,1>,<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>}；
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（提示：可以先画出对应的图形，然后再运算）。
拓扑序列：
4、
假定一组记录的排序码为（46，79，56，38，40，80，25，34，68，16），则对其进行快速排序的第一次划分后，得到的结果为：
结果：
四、阅读算法，回答问题（每小题8分，共16分）
1、 void
AE(Stack&S)
{
InitStack(S);
Push(S,30);
Push(S,20*2);
Push(S,15);
Int x=3*Pop(S0+Pop(S);
Push(S,x);
Int I,a[4]={5,9,18,15};
X=0;
For (I=0;I<4;I++){Push(S,a[i]);x+=a[i];}
Push(S,x);
While (! StackEmpty(S)) count
<<Pop(S)<<’
’;
}
该算法被调用后得到的输出结果为：
2、 void
AJ(adjlist GL,int I,int n)
{
Queue Q;
InitQueue(Q);
Cout<<I<<’
‘;
Visited[i]=true;
Qinsert(Q,i);
While(!QueueEmpty(Q)){
Int k=Qdelete(Q);
Edgenode *p=GL[k];
While (p!=NULL)
{
int j=p->adjvex;
if(! Visited[j]) {
count<<j<<’
‘;
visited[j]=true;
Qinsert(Q,j);
}
p=p->next;
}
}
}
假定形参GL是边集为{（0，1），（0，2），（0，5），（1，3），（1，4），（2，4），（2，5），（3，6），（4，6）}的图所对应的邻接表，形参I和n的值分别为0和7，并且邻接表中每个单链表中的边结点都是按照adjvex域的值从大到小的次序链接的，则招待该算法时得到的输出结果为：
输出结果：
五、算法填空，在画有横线的地方填写合适的内容（10分）
//从HBT小根据堆中删除堆顶元素并将它返回
ElemType DeleteHeap(Heap&
HBT)
{
if(HBT.size==0){cerr<<”Heap
null!””<<endl;exit(1)}
Elem Type temp=HBT.heap[0
;
HBT.size--;
If(HBT.size==0)
;
ElemType x=HBT.heap[HBT.SIZE];
Int I=0;
Int j=2*I+1;
While(j<=HBT.Asize-1){//调整到孩子为空时止
If(j<HBT.size-1&&HBT.heap[j]>HBT.heap[j+1]
;
If(x<=HBT.heap[j])break;
HBT.heap[I]=
;
I=j;
;
}
return temp;
}
六、编写算法（10分）
编写一个从数组A[n]中进行二分查找的非递归算法。
Int Binsch (Elem Type A[],
int n, KeyType K)
//在A[0]~A[n-1]区间内二分查找关键字为K的元素，
//规定使用low和high保存待查区间的下限和上限
试题答案
一、1、C 2、B
3、A
4、C
二、填空题
1、(n+1)/2
2、HL==NULL
HL==NULL
3、 4
1
4、指针域
栈顶指针
5、（r-f+N）%N
6、10 11
2 7、64
127
8、 O（log2n） O(1)
9、N-1 N(N-1)/2
10、e 2e
11、3.7 12、1
0
3 13、
n/m
14、2 m 1
m-1
15、Olog2n） O(1)
16、O（n log2n）O(1)
三、运算题
1、先序：a,b,d,c,e,g,f,h
中序：d,b,a,e,g,c,f,h
后序：d,b,g,e,h,f,c,a
按层：a,b,c,d,e,f,g,
2、（2，4）10，（4，1）6，（1，0）3，（0，3）5，（4，6）8，（4，7）12，（3，5）15
3、拓扑序列：0,2,5,1,4,3,6,7,8
4、[25 16
34 38 40] 46
[80 56 68
79]
四、阅读算法，回答问题
1、47 15 18
9 5 85 30
2、0 5 2
1 4 3 6
五、算法填空
1）
return temp
2） j++
3）
3)HBT.heap[j]
4）
j=2*I+1或j=2*j+1
5）
HBT.heap[I]=x
六，编写算法
int Binsch(ElemType
A[],int n
,KeyType K)
{
int low =0,high=n-a;
while(low<=high)
{
int mid=(low+high)
if(K==A[mid].key)
high=mid-1;
else
low=mid+1;
}
return-1;
}
喜欢
加载中…