数据结构自考2014年10月真题及答案解析

已知二叉树的二叉链表类型定义如下：

typedef struct node {

       char data;

       struct node *lchild, *rchild;

}BinTNode;

typedef BinTNode * BinTree;

函数f33的功能是将二叉树Bt变换为它的镜像。镜像的含义如题33图所示

请将空白处(1)~(4)填写适当内容,使其完成指定功能,请在答题卡上作答。

已知带头结点的单链表类型定义如下：

typedef struct node {

       int data;

        struct node *next;

} ListNode;

typedef ListNode *List_ptr;

请编写函数InvertList实现单链表的原地逆转。要求在原链表上进行逆转，不允许申请新的表结点空间。函数原型如下

List_ptr InvertList( List_ptr head); //原地逆转单链表head

带头结点的单链表定义如下，其中freq域记录本结点被访问的次数，初值为0，单链表始终以freq值从大到小有序。函数f31完成的功能是：查找给定关键字所在结点，若查找成功，则该结点的freq域加1，并按freq值调整结r旨位置。请将空白处(1)～(3)补充完整。在答题卡上作答。

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

若顺序表R的元素个数n=6，关键字依次为{41，82，75，24，8，16}，则：

(1)写出函数f32执行后的输出结果：

(2)函数f32的功能是什么?

给定有向无环图G如题29图所示，写出G的5种不同的拓扑排序序列。

请写出下列程序段的输出结果。

Seqstack S; //初始化栈

Schar x, y;

X='L'; y='O';

Push(s, x); Push(S,x);

Push(s, y); x=Pop(S);

Push(S, 'E'); Push(s,x);

x=Pop( S ); Push(S,'H');

while(! StackEmpty (s)) {

y=Pop(S);

putchar( y );

}

putchar( x );

输出结果

将百分制成绩分成五个等级，已知成绩的对应关系及分布情况如下表所示：

请根据最优二叉树的基本原理，采用类C语言，描述你所设计的成绩判定过程。

26.设Q是有N个存储空间的循环队列，初始状态front=rear=0，约定指针rear指向的单元始终为空，回答下列问题。

(1)写出数据元素X入队的语句序列;

(2)写出队首元素出队并保存到变量Y的语句序列;

(3)给出计算队列长度L的表达式。

已知稀疏矩阵M如下，采用三元组表存储。

请回答下列问题。

(1)给出三元组表的类型定义。

(2)画出矩阵M按行优先的三元组表。

DFS算法的中文名称是_________。

若构造一颗具有n个结点的二叉排序树，在最坏情况下，其深度为_________。

除邻接表外，图的另一种链式存储方式是_________。

含n个顶点e条边的带权连通图G，采用迪杰斯特拉算法得到的某个给定顶点到其余各顶点最短路径的条数是_________。

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

栈和队列是操作受限的线性表，其中只能在表的一端进行插入或删除操作的是_________。

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

描述算法占内存空间效率的术语是_________。

设顺序表第1个元素的存储地址是2000，每个数据元素占4个字节，则第41个元素的存储地址是_________。

假设散列表长m=11，散列函数H(key)=key%11。表中已有4个结点：H(39)=6，H(41)=8，H(53)=9，H(76)=10，占了4个位置，其余位置为空。现采用线性探查法处理冲突，存储关键字85时需要探查的次数是(　　)

著名计算机科学家沃思曾指出：算法+_________=程序。

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

下列排序方法中，时间复杂度与数据初始状态相关的是(　　)

下列排序方法中，效率较高且稳定的方法是(　　)

设带权连通图G中含有n(n>1)个顶点e条边。下列关于G的最小生成树的叙述中， 正确的是(　　)

下列关于无向图广度优先搜索序列的叙述中，正确的是(　　)

下列关于无向连通图特性的叙述中，正确的是(　　)

下列选项中，可以唯一确定一棵二叉树的两种遍历序列是(　　)

设深度为k(k≥1)的二叉树中只有度为0和度为2的结点，则该二叉树中所包含的结点数至少是(　　)

广义表A=(a，(b，e，(e，f，g，h)))的表长是(　　)

在二维数组a[8][10]中，每个数组元素a[i][j]占用3个存储空间，所有数组元素存放在一个连续的存储空间中，则该数组需要的存储空间个数是(　　)

下列关于算法输出的叙述中，正确的是(　　)

针对线性表逻辑上相邻的两个元素，下列叙述中，正确的是(　　)

队列和栈的特征分别是(　　)

下列选项中，属于逻辑结构的是(　　)