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

什么是堆?写出对应于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆顶元素取最小值)。

二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。

试写出直接插入排序算法。

题31图中二叉排序树的各结点的值为32～40，标出各结点的值。

             题31图

下述矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。

有一字符串的次序为-3*y+a/y!2，试利用栈将输出次序改变为3y*-ay!2/+，试写出进栈和退栈的操作步骤。(用push(x)表示x进栈，pop(x)表示x退栈)

已知一棵二叉树的先根遍历序列为ABCDEGHF，中根遍历序列为CBEDAGFH，画出该二叉树。

堆排序需________个记录大小的辅助存储空间。

在图中，第一个顶点和最后一个顶点相同的路径称为________。

动态查找中两个元素X，Y存入同一个散列表时，X、Y键值相同，则这种情况称为________。

对于一棵满二叉树，若有m个叶子，则树中结点数为________。

含有n个顶点和n-1条边的连通图G采用________存储结构较省空间。

一个10阶对称矩阵A，采用行优先顺序压缩存储上三角元素，为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则的地址为________。

一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为________。

循环队列被定义为结构类型，含有三个域：data、front和rear，则循环队列sq为空的条件是________。

在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点________的。

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

从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动________个元素。

下列程序段的时间复杂度为________。

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

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

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

               s=i+j+k;

在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为________。

对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)/2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为(　　)

循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为(　　)

关于串的的叙述，不正确的是(　　)

有关树的叙述正确的是(　　)

有关插入排序的叙述，错误的是(　　)

对线性表进行二分查找时，要求线性表必须(　　)

在表长为n的顺序表上做删除运算，其平均时间复杂度为(　　)

当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为(　　)

对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为(　　)

下述几种排序方法中，要求内存量最大的是(　　)

在一个图中，所有顶点的度数之和与图的边数的比是(　　)

长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为(　　)

含有n个结点的二叉树用二叉链表表示时，空指针域个数为(　　)

下述文件中适合于磁带存储的是(　　)

某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为(　　)