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

试写出判断带头结点的单链表head中的元素值是否是递减的算法。

试写出在有序表T中用二分查找法查找键值为key的元素的算法。

给定表(27，19，50，1，75，12，40，90，66，32，22)，试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。

对初始关键字序列48，39，68，95，88，12，27，48的记录进行冒泡排序(升序)，给出排序过程。

设有编号为A，B，C，D的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出站台的所有可能的顺序。

已知一棵二叉树的先序遍历序列为ABCDEFGHK，中序遍历序列为CBEDFAGKH，试建立该二叉树并写出它的后序遍历序列。

利用克鲁斯卡尔(Kruskal)算法构造题31图的最小生成树，画出它的构造过程。

                              题31图

设记录数为n，则冒泡排序算法在最好情况下所作的比较次数为________。

二路归并排序算法的时间复杂度为________。

用n个值构造一棵二叉排序树，它的最大深度为________。

设有向图G的邻接矩阵为A，如果i，V_j>是图中的一条弧，则A[i][j]的值为_______。

一个有序表A含有15个数据元素，且第一个元素的下标为1，按二分查找算法查找元素A[14]，所比较的元素下标依次是________。

在一棵度为3的树中，度为3的结点数为1个，度为2的结点数为2个，度为1的结点数为3个，则度为0的结点数为________个。

某二叉树的中序遍历序列为BACDEFGH，后序遍历序列为BCAEDGHF，则根结点F的左子树上共有________个结点。

含有n个顶点的连通图中的任意一条简单路径，其最大长度为________。

队列操作的原则是________。

向一个长度为100的顺序表中第50个元素之前插入一个元素时，需向后移动的元素个数为________。

设p指向单链表的最后一个结点，要在最后一个结点之后插入q所指的结点，需执行的语句序列是①p->next=q;②________;③p->next=NULL。

一个带头结点的链栈LS，现将一个新结点入栈，指向该结点的指针为p，入栈操作为p->next=LS->next和________。

下列算法中，不稳定的排序算法是(　　)

• A.冒泡排序
• B.快速排序
• C.直接插入排序
• D.二路归并排序

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

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

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

    {   x=a[i][j];

          a[i][j]=a[j][i];

         a[j][i]=x;

}

要解决散列引起的冲突问题，最常用的方法是(　　)

• A.数字分析法、除留余数法、平方取中法
• B.除留余数法、线性探测法、平方取中法
• C.线性探测法、二次探测法、链地址法
• D.除留余数法、线性探测法、二次探测法

图的广度优先搜索遍历的过程类似于树的(　　)

• A.前序遍历
• B.中序遍历
• C.后序遍历
• D.按层次遍历

下列表述中，正确的是(　　)

• A.序列(102，81，55，62，50，40，58，35，20)是堆
• B.序列(102，81，55，62，50，40，35，58，20)是堆
• C.序列(102，81，55，58，50，40，35，62，20)是堆
• D.序列(102，71，55，40，50，62，35，58，20)是堆

无向图的邻接矩阵是(　　)

• A.对称矩阵
• B.稀疏矩阵
• C.对角矩阵
• D.上三角矩阵

将题10图所示的一棵树转换为二叉树，结点D是(　　)

题10图

• A.A的右孩子
• B.B的右孩子
• C.C的右孩子
• D.E的右孩子

元素的进栈次序为A，B，C，D，E，则出栈中不可能的序列是(　　)

• A.A，B，C，D，E
• B.B，C，D，E，A
• C.E，A，B，C，D
• D.E，D，C，B，A

将含有80个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1。则关于编号40的结点的左右孩子的说法正确的是(　　)

• A.左孩子编号为79，右孩子编号为80
• B.左孩子不存在，右孩子编号为80
• C.左孩子编号为80，右孩子不存在
• D.左孩子不存在，右孩子不存在

具有63个结点的完全二叉树是(　　)

• A.满二叉树
• B.二叉排序树
• C.哈夫曼树
• D.空树

判断链栈LS是否为空的条件是(　　)

• A.LS->next= =LS
• B.LS->next= =NULL
• C.LS! =NULL
• D.LS= =NULL

关于链队列的运算说法正确的是(　　)

• A.入队列需要判断队列是否满
• B.出队列需要判断队列是否空
• C.入队列需要判断队列是否空
• D.出队列需要判断队列是否满

若线性表最常用的操作是存取第i个元素及其后继的值，则最节省操作时间的存储结构是(　　)

• A.单链表
• B.双链表
• C.单循环链表
• D.顺序表

从一个长度为100的顺序表中删除第30个元素，需向前移动的元素个数为(　　)

• A.29
• B.30
• C.70
• D.71

算法的空间复杂度是指(　　)

• A.算法中输入数据所占用的存储空间的大小
• B.算法本身所占用的存储空间的大小
• C.算法中所占用的所有存储空间的大小
• D.算法中需要的辅助变量所占用存储空间的大小

数据的基本单位是(　　)

• A.数据元素
• B.数据项
• C.字段
• D.域