数据结构自考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入栈的操作。