数据结构自考2015年4月真题及答案解析

存储二叉树的二叉链表定义如下：

ypedef struct node {

      char data;

      struct node *lchild, *rchild;

} BinTNode;

typedef BinTNode *BinTree;

请编写一个后序遍历二叉树的递归程序void PostOrder(BinTree root)，并输出遍历序列。其中root指向二叉树根结点。

下列函数的功能是：在带头结点的单链表上进行选择排序。请在空白处填上适当内容将函数补充完整，并说明该算法是否是稳定的。

阅读程序，并回答下列问题。

假设顺序表R的元素存放在下标为l～8的数组元素中，K=7，low=1，high=8。

(1)R的关键字依次为{1，2，3，4，5，6，7，8)，函数f33的返回值是多少?

(2)R的关键字依次为{7，7，7，7，7，7，7，7)，函数f33的返回值是多少?

(3)简述函数的功能。

设下列程序段中的数据皆为int型，请指出该程序段的功能是什么。

给定带权图G如题29图所示，使用迪杰斯特拉(Dijkstra)算法，求顶点vl到其他各顶点的最短路径，列出每条路径上的各顶点及路径长度。

下列函数的功能是在带头结点的单链表head中删除所有数据域值为X的结点，请在空白处填上适当的语句，使其完成指定功能。

已知散列函数为H(key)=key%11，现将关键字序列{23，27，34，56，58，10，18，120)散列到散列表HT(0…10)中，利用线性探查法解决冲突。回答下列问题。

(1)画出最后的散列表;

(2)求在等概率情况下查找成功时的平均查找长度。

已知广义表及结点类型结构如下：

typedef enum{ATOM, LIST}NodeTag;

      //ATOM=0,表示原子;LIST=1,表示子表

typedef struct GLNode

{ NodeTag tag;    //区分原子结点和表结点

    union

{    DataType data;     //存放原子结点的值

    GLNode *slink;      //指向子表的指针

};

GLNode *next;   //指向下一个表结点

}*Glist; //广义表类型

请回答下列问题。

(1)若广义表A为空表，应如何表示?

(2)若广义表A=(a，(b，c))，画出A的存储结构。

若待排序序列中的关键字基本有序，采用快速排序或直接插入排序时，效率较高的是_________。

顺序栈的类型定义如下：

typedef struct{

     DataType data[MaxSize];

        int top;

}SeqStack;

SeqStack S;

规定栈底位置在MaxSize-1，请回答下列问题。

(1)若要求栈空时条件为真，则判断栈空的条件表达式是什么?

(2)若要求栈满时条件为真，则判断栈满的条件表达式是什么?

(3)用语句表示将X入栈的操作。

希尔排序方法使用的增量序列中，最后一个增量必须是_________。

用矩阵作为图的存储结构，该矩阵称为图的_________。

普里姆(Prim)算法得到的是带权连通图的_________。

一棵右子树为空的二叉树在后序线索化后，其空指针域的个数为_________。

广义表A=(a，(b，C，(e，f，g，h)))，head(tail(A))= _________。

队列Q中已有元素l，3，5，数据序列2，4，6，8，10依次入队，再连续执行6次出队操作，得到的出队序列是_________。

采用大0表示法时，常数阶算法的时间复杂度记为_________。

一个线性表如果需要频繁地增删元素，则存储结构应该选择_________。

算法必须满足可行性等五个准则，其中_________的含义是：算法中每条指令的含义都必须明确，无二义性。

下列叙述中，不符合m阶B树定义的是(　　)

对含有16个元素的有序表进行二分查找，关键字比较次数最多是(　　)

下列排序方法中，效率较高且使用辅助空间最少的方法是(　　)

下列排序方法中，平均比较次数最少的方法是(　　)

下列关于有向无环图G的拓扑排序序列的叙述中，正确的是(　　)

对下图进行广度优先搜索遍历，不能得到的遍历序列是(　　)

构造一棵含n个叶结点的哈夫曼树，树中结点总数是(　　)

若图G的邻接表中有奇数个表结点，下列选项中，正确的是(　　)

以二叉链表作为二叉树的存储结构，在有n(n>0)个结点的二叉链表中，空指针域的个数是(　　)

二维数组a[10][20]按行优先顺序存放在连续的存储空间中，元素a[0] [0]的存储地址为200，若每个元素占1个存储空间，则元素a[6][2]的存储地址是(　　)

广义表A=(a(b，c，(e，f, g，h)))的深度是(　　)

设栈的进栈序列为a，b，c，d，e，经过合理的出入栈操作后， 不能得到的出栈序列是(　　)

使用大小为6的数组实现循环队列，若当前rear=0，front=3。当从队列中出队一个元素，再入队两个元素后，rear和front的值分别是(　　)

以下各阶时间复杂度中，性能最优的是(　　)

头指针head指向带头结点的单循环链表。链表为空时下列选项为真的是(　　)