数据结构试题和答案解析（).doc

文档介绍：...wd...
...wd...
N的二叉树，其所有结点的度的总和是_n-1__。
8.        对一棵二叉搜索树进展中序遍历时，得到的结点序列是一个有序序列_。对一棵由算术表达式组成的二叉语法树进展后序遍历得到的结点序列是该算术表达式的___后缀表达式_。
9.        对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_2n_个，其中n-1_个用于指向孩子_n+1个指针是空闲的。
10.    假设对一棵完全二叉树从0开场进展结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，那么A[ i ]元素的左孩子元素为2i+1_,右孩子元素为_2i+2__，双亲元素为___(i-1)/2。
11.    在线性表的散列存储中，处理冲突的常用方法有____开放定址法____和_链接法_两种。
12.    当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。
 
三、                   运算题〔每题6分，共24分〕
1.        一个6´5稀疏矩阵如下所示，
 
 
 
试：
〔1〕        写出它的三元组线性表；
〔2〕        给出三元组线性表的顺序存储表示。
2.        设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
...wd...
...wd...
...wd...
四、                   阅读算法〔每题7分，共14分〕
1.                     int Prime(int n)
{
int i=1;
int x=(int) sqrt(n);
while (++i<=x)
if (n%i==0) break;
if (i>x) return 1;
else return 0;
}
(1)     指出该算法的功能；
(2)     该算法的时间复杂度是多少？
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])
{
cout<<j<<' ';
visited[j]=true;
QInsert(Q,j);
}
p=p->next;
}
}
}
 
...wd...
...wd...