数据结构试卷（A）
一、 填空题（每空1分，1*20）
1、在二叉树的第i层上至多有( )个结点，深度为k的二叉树至多有( )个结点，任何一棵二叉树中，度为2的结点个数为n则叶子结点个数为( )。
2、队列是一种限定( )的线性表，它只允许在表的一端插入，在另一端删除，允许插入的一端叫( )，允许删除的一端叫做( )。
3、N个结点的连通图至多有( )条边，至少有( )条边。
4、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 ，所有顶点邻接表中的结点总数为( )。
5 、若一个广义表为（a，（a，b），d，e，（（i，j），k）），则该表深度为（），而表长度为（）。
6、锦标赛排序的时间复杂度为( )从稳定性上讲是一个( )的排序方法。堆排序的时间复杂度为( )
是一个( )（稳定或不稳定）的排序方法。
7、在结点为N的各棵树中，高度最小的树的高度为( )，它有( )个叶结点，高度最大的树的高度是( )，它有( )个叶子结点。
二、 判断题（正确为T，错误为F，每小题2分，共10分）
1、数据结构、数据元素和数据项在计算机中的映像分别为存储结构、结点和数据域。
（ ）
2、顺序表和单链表都是随机存取的线性存储结构。 （ ）
3、两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历得到的序列顺序是相同的。 （ ）
4、在任何情况下归并排序都比直接插入排序快。 （ ）
5、拓扑排序就是从某个集合的偏序得到该集合的一个全序。 （ ）
三、 选择题（每题2分，共10分）
1、若循环链表的结点具有数据域data和指针域next，H指向其头结点，该表具有一个元素结点的条件是（ ）为真值。
A. H= =H->next B. H= =H->next->next C. H->next D. !(H->next)
2、折半查算法的时间复杂度是（ ）。
A. O(n2) B. O(n) C. O(nlog2n) D. O(log2n)
3、m阶B树中的m是指（ ）。
A. 每个结点至少有m棵子树 B. 非终端结点中关键字的个数
C. 每个结点至多有m棵子树 D. m阶B树的深度（或高度）
4、三个结点的二叉树的形态有（ ）种
A. 3 B. 4 C. 5 D. 6
5、采用链表方式表示一个栈，栈顶结点的插入与删除能在链表的（ ）进行
A. 任意位置 B. 一端 C. 两端 D. 中间进行
四、 画图及填空（每题5分，共15分）
1、 将下列二叉树在顺序存储结构A[0..15]中存放。
2、已知一棵二叉树的前序遍历的结果是ABCEDFGHIJ，中序遍历结果是BECADFHIGJ，试画出这棵二叉树，并写出它的后序遍历结果。
3、画出广义表L=((( )),a,((b,c),( ),d),(((e))))的存储结构图。
五、应用题（45分）
下面的算法是将整形数组-1]中的元素划分为两部分，使得左边元素均为奇数，右边元素均为偶数，请在＿＿中填入恰当的语句，完成本算法。（10分）
void Partition(int A[ ])
    { i=0; j=n-1;
    while＿＿＿＿
        { while (i<j&&＿＿＿＿) i++;
        while(i<j&&＿＿＿＿)j++;
        if(i<j)＿＿＿＿;
        }
    }
2、从一棵空的平衡二叉树开始，把关键字（5，17，6，21，14，13，28，3，40）按出现
的先后次序逐个插入，从而构造一棵平衡二叉排序树。请画出每插入一个关键字后得到的树型结构，若需要进行平衡旋转，则表明旋转类型及旋转后的结果。（15分）
3、对下图所示的AOE网络回答下列问题。（20分）
1）这个工程最早可能在什么时候结束？
2）求每个活动的最早开始时间e( )和最迟开始时间l( )。
3）确定那些活动是关键活动？
数据结构试卷（B）
一、 填空题（每空1分，1*20）
1、在二叉树的第i层上至多有( )个结点，深度为k的二叉树至多有( )个结点，任何一棵二叉树中，度为2的结点个数为n则叶子结点个数为( )。
2、队列是一种限定( )的线性表，它只允许在表的一端插入，在另一端删除，允许插入的一端叫 ，允许删除的一端叫做( )。
3、N个结点的连通图至多有( )条边，至少有( )条边。
4、 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为( ) ，所有顶点邻接表中的结点总数为( )。
5、若一个广义表为（a，（a，b），d，（（i，j，（）），k），e），则该表深度为( ) ，而表长度为( )。
6、锦标赛排序的时间复杂度为( )从稳定性上讲是一个( )的排序方法。堆排序的时间复杂度为( )是一个( )（稳定或不稳定）的排序方法。
7、在结点为N的各棵树中，高度最小的树的高度为( )，它有( )个叶结点，高度最大的树的高度是( )，它有( )个叶子结点。
二、 判断题（正确为T，错误为F，每小题2分，共10分）
1、据结构、数据元素和数据项在计算机中的映像分别为存储结构、结点和数据域。
（ ）
2、顺序表和单链表都是随机存取的线性存储结构。 （ ）
3、两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历得到的序列顺序是相同的。 （ ）
4、在任何情况下归并排序都比直接插入排序快。 （ ）
5、拓扑排序就是从某个集合的偏序得到该集合的一个全序。 （ ）
三、 选择题（每题2分，共10分）
1、若循环链表的结点具有数据域data和指针域next，H指向其头结点，该表具有一个元素结点的条件是（ ）为真值。
A. H= =H->next B. H= =H->next->next C. H->next D. !(H->next)
2、折半查算法的时间复杂度是（ ）。
A. O(n2) B. O(n) C. O(nlog2n) D. O(log2n)
3、m阶B树中的m是指（ ）。
A. 每个结点至少有m棵子树 B. 非终端结点中关键字的个数
C. 每个结点至多有m棵子树 D. m阶B树的深度（或高度）
4、三个结点的二叉树的形态有（ ）种
A. 3 B. 4 C. 5 D. 6
5、采用链表方式表示一个栈，栈顶结点的插入与删除能在链表的（ ）进行
A. 任意位置 B. 一端 C. 两端 D. 中间进行
四 、 应用题（共60分）
1、已知一棵二叉树的前序遍历的结果是ABCEDFGHIJ，中序遍历结果是BECADFHIGJ，试画出这棵二叉树，并写出它的后序遍历结果。（10分）
2、对无向带权图，根据它的邻接矩阵，按普里姆算法求其最小生成树；写明求解过程。（12分）
先序中序后序遍历二叉树
3、以关键码序列{503, 087, 512, 061, 908,170, 897, 275, 653, 426}为例，手工执行以下排序算法，写出每一趟排序结果时的关键码状态。(18分)
希尔排序 基数排序
4、对下图所示的AOE网络回答下列问题。（20分）
1）这个工程最早可能在什么时候结束？
2）求每个活动的最早开始时间e( )和最迟开始时间l( )。
3）确定那些活动是关键活动？
数据结构试卷（C）
一、 填空题（每空1分，1*20）
1、抽象数据类型ADT是指（）以及 （）。
2 、 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有顶点邻接表中的结点总数为（）。
3 、在具有n个结点的有序单链表中，插入一个新结点并依然有序的时间复杂度为（）。
4 、双端队列是（）的线性表。
5 、设数组-1]为循环队列的存储空间，其队头、队尾指针分别为front和rear，则在队列非满时元素x入队的时指针变化情况为（)。
6 、基数排序法是（）排序法，它与插入交换和选择排序法的排序策略均不同。
7 、已知一棵二叉树的前序遍历结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，则它的后序遍历结果是（）。
8 、一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行
编号，则n层结点个数是( ),编号为i的结点的父结点的编号为（），编号为i的第m个孩子结点若存在，编号是（），编号为i的结点有右兄弟的条件为（），其所有右兄弟结点编号为（）。
9 、若单链表的结点具有数据域data和指针域next，frist为链表的头指针，该表为空的条件是（）。
10 、设有一空栈，栈顶指针为1000H（），现有输入序列为1，2，3，4，5，经过PUSH、PUSH、POP、PUSH、POP、PUSH、PUSH之后，输出序列是（），而栈顶指针值是（）H， 设栈为顺序栈，每个元素占4个字节。
11、若一个广义表为（a，（a，b），d，（（i，j，（）），k），e），则该表深度为（），而表长度为（）。
二、 选择题（每题2分，2*10）
1、就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是（）。
A 堆排序< 快速排序< 归并排序
B 堆排序< 归并排序< 快速排序

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。