数据结构自考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)计算电文编码总长。

散列存储中,常用的解决冲突的方法有开放地址法和( )两大类。

对含n个元素的数据序列采用快速排序算法进行排序,平均时间复杂度是( )

将森林T转换为一棵二叉树T1,在T中结点A是结点B的右邻的兄弟(下一个兄弟),则在T1中,A是B的( )结点。

如果有向无环图G中仅有一个顶点的度为0若要求G的拓扑序列不唯一,则G中必须存在一个出度至少为( )的顶点。

已知二叉树的前序遍历序列和后序遍历序列,则对应的二叉树( )确定

递归算法设计中的最小子问题称为递归的( )

指针p和q分别指向单链表L中的两个相邻结点,即q- next=p若要在q所指结点后插入指针r所指结点,则执行的语句是r->next=p( )

广义表((a,b),(c,d),e,(f,(g,h))的表尾是( )

设散列表长m=16,散列函数H(key)=key表中已保存4个关键字:addr(18)=3addr(35)-5,addr(5)6,addr(22)-7,其余地址均为开放地址。存储关键字36时存在冲突,采用线性探测法来处理。则查找关键字36时的探查次数是【】

数据项是具有独立含义的( ) 标识单位。

一棵二叉排序树中,关键字n所在结点是关键字m所在结点的孩子,则【】

一组记录的关键字为(35,48,47,23,4488),利用堆排序算法进行降序排序,建立的初始堆【】

对数据序列(26,14,17,12,7,4,3)采用二路归并排序进行升序排序,两趟排序后,得到的排序结果为【】

下列选项中,不稳定的排序方法是【】

设有向图G含有n个顶点、e条边,使用邻接表存储。对G进行深度优先搜索遍历算法的时间复杂度是【】

有向图G中所有顶点的度数之和是24,则G中弧的数量是【】

有向图G有n个顶点和e条边,G保存在邻接矩阵M中,M中与1的个数差是【】

已知一棵完全二叉树T的第5层上共有5个叶结点,则T中叶结点个数最少是【】

已知广义表LS=(((a,b,c),d),(e,(f,),(h,i),ls的深度是【】                            

已知二叉树T的前序遍历序列为a,b,c,c,d,序遍历序列为c,e,b,d,a,则T的后序遍历序列为【】

设指针变量p指向非空单链表中的结点,ext是结点的指针域,则判断p所指结点为尾结点前一个结点的逻辑表达式中,正确的是【】

设栈的初始状态为空,元素1,2,3,4,5依次入栈,不能得到的出栈序列是【】

下列数据结构中,逻辑结构不同的是【】

将16个数据元素的线性表按顺序存储方式存储在数组中,若第一个元素的存储地址是1000,第6个元素的存储地址是1040,则最后一个元素的存储地址是【】