18春西南大学0012《数据结构》作业答案.docx

1-5 DACAD
6-10 DCCBA
11-15 BCCAD
16-20 BBCBD
21-25 ADBBD
26-27 BD
28-30 ACD ACD CD
31-35 BBBAB
36、 中序遍历二叉排序树所得到的序列是___________序列(填有序或无序)。
有序
37、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用( )存储方式最节省时间.
顺序表
38、 设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=_______。
d/2
39、 快速排序的最坏时间复杂度为___________,平均时间复杂度为__________。
O(n*n),O(nlog2n)
40、 设一棵完全二叉树中有500个结点,则该二叉树的深度为__________;若用二叉链表作为该完全二叉树的存储结构,则共有___________个空指针域。
9,501
41、 为了能有效地应用HASH查找技术,必须解决的两个问题是____________________和__________________________。
构造一个好的HASH函数,确定解决冲突的方法
42、 设有向图G用邻接矩阵A[n][n]作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点i的________,第i列上所有元素之和等于顶点i的________。
出度,入度
43在一个长度为n的顺序表中删除第i个元素,需要向前移动( )个元素.
n-1
44、 1、已知栈的基本操作函数:
int InitStack(SqStack *S); //构造空栈
int StackEmpty(SqStack *S);//判断栈空
int Push(SqStack*S,ElemType e);//入栈
int Pop(SqStack *S,ElemType *e);//出栈
函数conversion实现十进制数转换为八进制数,请将函数补充完整。
void conversion(){
InitStack(S);
scanf(“%d”,&N);
while(N){
(1) ;
N=N/8;
}
while( (2) ){
Pop(S,&e);
printf(“%d”,e);
}
}//conversion
(1)Push(S,N%8) (2)!StackEmpty(S)
45、带头结点的单链表head为空的判定条件是( )。
head->next==NULL
46、 下面程序段的功能实现数据x进栈,要求在下划线处填上正确的语句。
typedef struct {int s[100]; int top;} sqstack;
void push(sqstack &stack,int x)
{
if (==m-1) printf(“overflow”);
else {____________________;_________________;}
}
stac