数据结构导论2012年10月真题及答案解析（02142）

设散列函数H(key)=key mod 11(mod表示求余运算)，给出键值序列为66，13，41，15，44，6，68，17，26，31，39，46，用链地址法解决冲突，试画出相应的散列表，并计算在等概率情况下查找成功时的平均查找长度。

带头结点的单链表的结点结构如下：

typedef struct node

{  int data;

   struct node *next;

}Node, *LinkList;

试编写单链表的删除运算算法void DeleteLinklist( LinkList head，int i)

写出直接选择排序算法。

题32图所示二叉排序树的各结点的值为1~10中的数，试标出各结点的数值。

题32图

已知含五个顶点A，B，C，D，E的连通带权图的邻接矩阵如题31图所示，试画出它所表示的连通带权图及该连通带权图的最小生成树。

          题31图

如题29图所示，在栈的输入端依次输入元素A，B，C，试写出在栈的输出端可以得到的所有输出序列，并给出每个序列的操作过程(用push(A)表示A进栈，pop(A)表示A出栈)。

题29图

将题30图所示的一棵树转换为对应的二叉树。

题30图

堆排序算法的时间复杂度为________。

如果要将序列{60，18，28，69，99，75，78}建成堆，则只需把60与________相互交换。

在顺序查找、二分查找、散列查找和索引顺序查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是________。

除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为________。

三个顶点v₁，v₂，v₃的图的邻接矩阵为，则该图中顶点v₂的出度为________。

具有64个结点的完全二叉树的深度为________。

C程序中，将对称矩阵A[n][n]的下三角元素压缩存储到n(n+1)/2个元素的一维数组M中，设a[i][j](i≥j)存放在数组M[k]中，则k的值(用i，j表示)为________。

某二叉树的先序遍历序列为AJKLMNO，中序遍历序列为JLKANMO，则根结点A的右子树中的结点个数为________。

在栈结构中，允许插入和删除的一端称为________。

在带有头结点的单链表head中，首结点的指针为________。

所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是________。

下面算法程序段的时间复杂度为________。

for (i=1; i<=n; i++)

      for (j=1; j<=n; j++)

           for (k=1;k<=n;k++)

                 x++;

单链表中指针p指向结点A，若要删除A之后的结点(存在且不释放存储空间)，则需要修改指针的操作为p->next=________。

快速排序属于(　　)

在一棵初始时为空的二叉树中，依次插入键值序列50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素60要进行的比较次数是(　　)

在带权有向图中求两个结点之间的最短路径可以采用的算法是(　　)

有10个顶点的无向完全图的边数是(　　)

二分查找(Binary Search)算法的时间复杂度是(　　)

二叉树的中序遍历序列中，结点P排在结点Q之前的条件是(　　)

m个叶结点的哈夫曼树中，其结点总数为(　　)

以行序为主序的二维数组a[3][5]中，第一个元素a[0][0]的存储地址是100，每个元素占2个存储单元，则a[1][2]的存储地址是(　　)

对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为(　　)

在链栈的运算中，不需要判断栈是否为空的是(　　)

一个队列的输入序列是A，B，C，D，则该队列的输出序列是(　　)

设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是(　　)

设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为(　　)

即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为(　　)

下面几种算法时间复杂度阶数中，值最大的是(　　)