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

单链表类型定义如下：

typedef struct node {

      int data;

      struct node *next;

 } ListNode;

typedef ListNode *LinkList;

设计算法在带头结点的单链表L中删除数据值最小的结点(设链表中各结点数据值均不相同)。函数的原型为：void f34(LinkList L)

实现二分查找的递归算法如下,在答题纸相应位置填写适当的内容使算法完整。

单链表类型定义如下：

typedef struct node {

    int data;

    struct node *next;

} ListNode;

typedef ListNode *LinkList;

用不带头结点的单链表存储待排数据,链表头指针为head。下列直接选择排序算法对链表按升序进行排序,请在答题纸相应位置填写适当内容使算法完整。

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

typedef struct node {

     DataType data;

      struct node *lchild, *rchild;

} BinNode;

typedef BinNode *BinTree;

阅读下列算法,并回答问题：

阅读下列算法,并回答问题：

void f30(SeqStack S)

{    int k=0;

     CirQueue Q;

     SeqStack T;

     InitQueue(&Q); //初始化队列Q

       InitStack(&T); //初始化栈T

       while (!StackEmpty(&S))

    {      k++;

        if (k%2!=0) Push(&T, Pop(&S));

        else EnQueue(&Q, Pop(&S)); 

  } //第一个循环

     while (!QueueEmpty(&Q)) //第二个循环

      Push(&S, DeQueue(&Q));

       while(!StackEmpty(&T)) //第三个循环

        Push(&S,Pop(&T));

 }

设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。调用函数f30(S)后,

(1)第一个循环结束后,栈T和队列Q中的内容各是什么?

(2)第三个循环语句结束后,栈S中的内容是什么?

设图以邻接表存储,如题28图所示。

(1)写出从顶点v1出发图的深度优先搜索遍历序列。

(2)写出从顶点v1出发图的广度优先搜索遍历序列。

(1)一个排序方法稳定的含义是什么?

(2)快速排序是稳定的吗?举例说明。

假定电文字符集为{A,B,C,D,E,F,G,H},它们在电文中出现的次数分别为{19,6,12,5,38,3,13,4),为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树的过程中,权值较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1。

顺序查找算法的平均时间复杂度为________。

用X代表进栈操作,S代表出栈操作。给出利用栈将字符串"a*b-c"改变为"ab*c-"的操作步骤。例如：将"ABC"改变为"BCA",则其操作步骤为XXSXSS。

在直接插入排序、冒泡排序和快速排序中,平均时间性能最佳的是________。

假设m个关键字互为同义词,若用线性探查法把这m个关键字存入散列表中,至少要进行的探查次数是________。

若无向图中任意两个不同的顶点间都有路径,则称该图为________。

二叉树的线索链表利用________存放遍历时得到的前趋或后继结点的指针。

采用邻接矩阵存储n个顶点e条边的无向图,其邻接矩阵的大小为________。

普里姆(Prim)算法完成的功能是求图的________。

若三维数组a[4][5][6]的基地址是100,每个元素占用2个存储单元,则数组a中最后一个元素的存储地址是________。

头指针为L的带头结点的双循环链表,结点的前趋指针域为prior,后继指针域为next,判断该链表为空的条件是________。

数据结构研究的内容包括数据的逻辑结构、________和数据的运算。

下列关于m阶B树的叙述中,错误的是(　　)

在散列查找中处理冲突时,可以采用开放定址法。下列不是开放定址法的是(　　)

比较次数与待排序列初始状态无关的排序方法是(　　)

对序列(15,9,7,8,20,-1,4)进行排序，若一趟排序后的结果为(-1,15,9,7,8,20,4),则采用的排序方法是(　　)

查找较快，且插入和删除操作也比较方便的查找方法是(　　)

无向图中所有顶点的度数之和与所有边数之比是(　　)

采用邻接矩阵存储图时，广度优先搜索遍历算法的时间复杂度为(　　)

用邻接表表示n个顶点e条边的无向图,其边表结点的总数是(　　)

下列选项为完全二叉树的是(　　)

对稀疏矩阵进行压缩存储的目的是(　　)

一棵二叉树的第7层上最多含有的结点数为(　　)

下列关于队列的叙述中,错误的是(　　)

设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是(2,4,3,6,5,1),则栈的容量至少是(　　)

顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是(　　)

与数据存储结构无关的概念是(　　)