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

已知n个单链表的表头指针保存在数组A中,单链表中的结点类型及数组类型定义如下,存储形式如题图所示

#define MAXSIZE 100

typedef int DataType,

typedef struct node

(DataType data,∥data是数据域

struct node next;∥指向下一结点的指针

}Node;

typedef Node SeqList[MAXSIZE];

试设计算法,在多个链表中查找值为key的数据元素,查找成功返回1,查找失败返回0函数原型为intf34(SeqList,intn, int key

二叉树的存储结构类型定义如下

typedef int DataType;

typedef struct node

{

DataType key;∥data是数据域

struct nodelchild, rchild;//分别指向左右孩子

}BinTNode;

Typed*BinTree;

阅读下列程序并回答问题

,void f33 (BinTree root, int left,intright)

{

if(root==NULL) return;

f33(root->Ichild, left,right);

if(root->key>-left &.8root->keykey);

f33(root->rchild,left,right);

}

(1)设二叉树T如题图所示,bt是指向根结点的指针给出执行f33(bt,14,30)的输出结果

(2)给出该函数的功能

二叉树的存储结构类型定义如下:

typedef char DataType;

typedef struct node

{DataType data;  ∥data是数据域

struct node Ichild, rchild;//分别指向左右孩子

}BinTNode;

typedef BinTNode BinTree;

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

void f31(Bin Tree T)

{if(T! =NULL){

f31(T->rchild);

寸

printf("%c", T->data);

f31(T->lchild);

}

return;

}

(1)设二叉树T如题31图所示,给出执行f31(T)的输出结果

(2)给出该算法的时间复杂度。

?待排序记录的数据类型定义如下

define MAXSIZE 100

typedef int KeyType;

typedef struct{

KeyType key;

}RecType;

typedef RecType SeqList[MAXSIZE];

要下列函数实现顺序表的直接插入排序,请在空白处填上适当内容使算法完整。

void f32(SeqList R, int n)

{

int i,j;

RecType temp;

for(i=; i<=   ①   ;i++){

temp=R[i]:

j=i;

while(j>0&& temp. key

]=RLj-1];

②   ;

   ③   ;

}

}

顺序表类型定义如下:

#define ListSize 10

typedef struct{

int data[ListSize];

int length;

}SeqList;

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

int partmin(SeqList SL1, SeqList SL2)

{ intminlength, minvalue, k=0;

minlength=SL2->length;

minvalue=SL2->data=0];

while(k

if(SL1->data[k]data[k]&&SL1->data[k]minvalue)

minvalue=SL1->data[k];

else if(SL2->datak]

minvalue=SL2->datak];

k++;

}

return minvalue;

}

int f30(SeqList SL1, SeqList *SL2)

{

if(SL1->length>SL2->length) returnpartmin(SL1, SL2);

else return partmin(SL2,SL1);

}

(1)若SL1->data中的数据为(15,14,25,8,-28,3,126,56,34),SL2->data中的数据为(12,7,-33,15,39,24,42,13),则调用函数f30(&sl1,&sL2)后的返回值是什么?

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

设有二叉排序树T如题图所示。现需在中删除结点e,请回答下列问题。

(1)画出删除后的二叉排序树(仅需画出一棵)

(2)在你实现的删除过程中,指针域更新的次数是多少?

有数据序列(12,17,05,10,20,24,45,11,10,1),

(1)使用希尔排序方法将其排成升序序列请回答下列问题量为3和1的希尔排序结果。

(2)计算第一趟希尔排序中数据元素之间的总交换次数(两个元素之间的交换记1次)

已知图G采用邻接矩阵存储,邻接矩阵如题图所示。

(1)根据邻接矩阵画出图G

(2)根据图G写出从顶点A开始图G的1个深度优先搜索遍历序列

(3)根据图G写出从顶点A开始图G的1个广度优先搜索遍历序列。

假设顺序存储的有序表R含有8个关键字,行二分查找时,平均查找长度为( )

设电文字符集是ee2,,e,es},各字符出现的次数分别为36,13,26,18,23}。现要为

(1)给出构造的哈夫曼树

(2)给出各字符的哈夫曼编码。

(3)计算电文编码总长。