全国自考(数据结构)模拟试卷8
-
36. 3DELLEFT(BT,X).
-
35. 3CREATE(X,LBT,RBT);
-
33. 写出下列程序段的输出结果。(假设此栈中元素的类型是char)
voide main( )
{stack s;
char x,y;
InitStack(s)
x=‘1’,y=‘0’
push(s,x);
push(s,x);
push(s,y);
push(s,x);
push(s,‘e’);
push(s,x);
pop(s,x);
push(s,‘h’);
while(!stackEmpty(s))
{pop(s,y);
printf(y);
}
prinft(x)
}
-
以二叉链表为存储结构,分别实现二叉树的下列运算:
PARENT(BT,X);
-
31. 简述一下算法的功能:
status A (1inkedlist L)
{//L是无表头结点的单链表
if (L&&L—>next)
{Q=L;L=L—>next;P=L;
while(P—>next)P=P—>next;
P—>next=Q;Q—>next=NULL;
}
return ok;
)//A
-
30. 请将下面的程序改成递归的过程。
voide ditui(int n)
{int i;
i=n;
while(i>1)
prinft(i--);
}
-
32. 求下面算法中变量count的值:(假设n为2的乘幂,并且n>2)
int Time
{int n
count=0;x=2;
while(x<n/2)
{x*=2;count++;
}
return(count)
}
-
29. 已知有一组长度为9的关键字序列为{22,63,72,54,97,17,37,80,92},现在假设散列表的地址空间为T[0..10],请用除余法构造散列函数,如果存在冲突问题,请用线性探查法解决冲突,并给出相应的散列表。
-
28. 已知有如下一个关键字序列{96,47,104,32,73,136,15,38,90,180},按照上述插入顺序构造一棵二叉排序树,则请给出二叉排序树的构造过程,说明其深度,并在等概率的条件下求出平均查找长度。
-
26. 已知一棵具有2个结点的二叉树的前序遍历序列和后序遍历序列是AB和BA,请问:这棵二叉树是惟一的吗?如果树是不惟一的,请画出满足此条件的不同的二叉树,并简单分析一下。
-
27. 对于下面的3个广义表,请画出其图形表示式,并说明它们各属于什么类型的广义表。 (1)B(A(x,l(a,b)),y) (2)C(A(x,l(a,b)),B(A(x,l(a,b)),y)) (3)D(a,D(a,D(…)))
-
25. 一棵树中非叶子结点的个数为n,与树对应的二叉树中右子树为空的结点的个数为m,则m=______。
-
23. 设有一元多项式A(x)=7+3x+10x30-4X100+13x101,用单链表给出A(x)的存储表示为______。
-
24. 在顺序表中,插入或者删除一个元素,需要平均移动______个元素,具体移动的元素个数与______有关。
-
21. 就文件而言,按用户的观点所确定的基本存储单元称为______。按外设的观点所确定的基本存储单元称为______。
-
22. 对于一个具有n条边和e个顶点的图来说,如果采用邻接表表示,则其空间复杂度为______,若采用邻接矩阵表示,则其空间复杂度为______。
-
19. 对带有头结点的链队列lq,判定队列中具有一个数据元素的条件是______。
-
20. 判断一个没有头结点的单链表head为空的条件是______。
-
18. 已知无向图G的结点数为n,边数为e,其邻接表表示中的表结点数与表头结点数之和为______。
-
17. ______与数据元素本身的内容和形式无关。
-
16. 设线性表(a1,a2,…,a500)元素的值由小到大排列。对一个给定的k值,用二分法检索查找表中与k相等的元素,在检索不成功的情况下,至多需比较______次。
-
14. 在有向图中,所有顶点的入度之和是所有顶点出度之和的( )倍。
- A.0.5
- B.1
- C.2
- D.4
-
15. 从一个长度为n的顺序表中删除第i个元素(1≤i≤n)8寸,需要向前移动( )
- A. n-i
- B.n-i+1
- C.n-i-1
- D.i
-
11. 森林T中有4棵树,第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后,其根结点的左孩子上有( )个结点。
- A.n1-1
- B.n1
- C.n1+n2+n3
- D.n2+n3+n4
-
12. 倒排文件的主要优点是( )
- A.便于进行插入和删除运算
- B.便于进行文件的合并
- C.能大大提高基于非关键码数据项的查找速度
- D.能大大节省存储空间
-
13. 一个队列的输入序列是1,2,3,4,则队列的输出序列是( )
- A.4,3,2,1
- B.1,2,3,4
- C.1,4,3,2
- D.3,2,4,1
-
10. 在一个链队中,假设f和r分别为队首和队尾指针,则删除一个结点的运算是( )
- A.r=f—>next
- B.r=r—>next
- C.f=f—>next
- D.f=r—>next
-
9. 任何一个带权的无向连通图的最小生成树( )
- A.只有一棵
- B.有一棵或多棵
- C.一定有多棵
- D.可能不存在
-
7. 在一棵完全二叉树的顺序存储方式中,若编号为t的结点有右孩子,则此结点右孩子的编号为( )
- A.2t
- B.2t-1
- C.2t+1
- D.t/2
-
8. 对于一个具有N个结点和E条边的无向图,若采用邻接表示,则表头向量的大小是( )
- A.N
- B.N+1
- C.N-E
- D.N-1
-
4. 如果以链表作为栈的存储结构,则退栈操作时( )
- A.必须判别栈是否满
- B.判别栈元素的类型
- C.必须判别栈是否空
- D.对栈不作任何判别
-
6. 对采用二分查找法进行查找运算的查找表,要求按( )方式进行存储。
- A.顺序存储
- B.链式存储
- C.顺序存储且结点按关键字有序
- D.链式存储且结点按关键字有序
-
5. 在一个具有n个单元的顺序栈中,假设栈底是存储地址的高端,现在我们以top作为栈顶指针,则作退栈操作时,top的变化是( )
- A.top=top-1
- B.top=top+1
- C.top不变
- D.top不确定
-
3. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是bgbaechf,则其后序遍历的结点访问顺序是( )
- A.bdgcefha
- B.gdbecfha
- C.bdgechfa
- D.gdbehfca
-
2. C语言数组Data[m+1]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作的语句为( )
- A.front=front+1
- B.front=(front+1)%m
- C.rear=(rear+1)%m
- D.front=(front+1)%(m+1)
-
1. 在桶排序中,其平均时间复杂度是( )
- A.O(1)
- B.O(n)
- C.O(n2)
- D.O(1gn)