Question

数据结构 题目 比较多 比较急 谢谢

下面程序的时间复杂为（ ）(2分)
for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}
(A)O(n) (B)
O(n2) (C)
O(n3) (D) O(n4)

设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。(2分)
(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；
(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；
(C) q=p->next；p->next=q->next；free(q)；
(D)q=p->next；p->data=q->data；free(q)；
设有n个待排序的记录关键字，则在堆排序中需要（ ）个辅助记录单元。(2分)
(A)1 (B) n (C) nlog2n (D)
n2

设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。(2分)
(A) 10，15，14，18，20，36，40，21
(B)10，15，14，18，20，40，36，21
(C)10，15，14，20，18，40，36，2l
(D)15，10，14，18，20，36，40，21
设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。(2分)
(A)O(1) (B) O(log2n) (C) (D)
O(n2)

设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。(2分)
(A)n，e (B) e，n (C)
2n，e (D)
n，2e

5、设一棵完全二叉树有700个结点，则共有 个叶子结点(2分)
6、在图形结构中，每个结点的前驱结点数和后续结点数可以 ( 2分)
7、每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫 做____________排序。(2分)
8、设一棵完全二叉树有128个结点，则该完全二叉树的深度为________。(2分)
对链表进行插入和删除操作时不必移动链表中结点。( ) (1分)
子串“ABC”在主串“AABCABCD”中的位置为2。( ) (1分)
若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( ) (1分)
希尔排序算法的时间复杂度为O(n2)。( ) (1分)
用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( ) (1分)
1、给出下列二叉树的先序序列。( 6分)

2、已知结点a,b,c,d及其权值写出哈夫曼树的构造过程。
a b c
d

7 5 2
4

将此森林转换为相应的二叉树

完成计算二叉树叶子结点的算法。

完成计算二叉树深度的算法。

Answer 1

1、B：f(n)=1+2+3+.....+n=n(n+1)/2为O(n2)
2、A：将下一个结点的数据置于结世哗知点P，同时删除下一点结点
3、A：堆排序是就地排序，只需一个辅助单元
4、A
5、B
6、D
5、350
6、任意多个
7、选择
8、7
对
错？（首次出现的位置是2）
错
错
错1、CABEFDHG

哈夫曼树的构造过程

森林转为二叉树

//-----求子结点
思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。
法一：核心部分为：
DLR(liuyu *root)     /*中序遍历   递归函数*/
{if(root!=NULL)
 {if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);}
  DLR(root->lchild);
  DLR(root->rchild); }
 芦纯return(0);
}
法二：
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 
{ 
  if(!T) return 0; //空树没有叶子 
  else if(!T->lchild&&!T->rchild) return 1; //叶子结点 
  else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加 
上右子树的叶子数 
}//LeafCount_BiTree 

注：上机时要先建树！

//-----------求深度--------------
int depth(liuyu*root)     /*统计层数*/
{int d,p;                   /*注意每一层的局部变量d,p都是各自独立的*/
p=0;
if(root==NULL)return(p);      /*找到叶子之后才开始统计*/
else{ 
d=depth(root->lchild);
if(d>p) p=d;              /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/
d=depth(root->rchild);
if(d>p)p=d;
}
p=p+1;
return(p);
}
法二：
int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 
{ 
  if(T->data==x) 
  { 
    printf("%d\n",Get_Depth(T)); //找到了值为x的结点,求其深度 
    exit 1; 
  } 
  } 
  else 
  { 
    if(T->lchild) Get_Sub_Depth(T->lchild,x); 
    if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 
  } 
}//Get_Sub_Depth 
int Get_Depth(Bitree T)//求子树深度的递归算法 搜消
{ 
  if(!T) return 0; 
  else 
  { 
    m=Get_Depth(T->lchild); 
    n=Get_Depth(T->rchild); 
    return (m>n?m:n)+1; 
  } 
}//Get_Depth 

Answer 2

选择题：BCCABD
填空：颤源困1、701 2、任意 3、插入排序 4、茄念log2（128）（=7）
判断题：对、错、对、错、错
问题补充：
1、CABFEDHG
2、图没裂册办法画
二叉树深度：log2 n