简述数据的四种逻辑结构及其特点

1、简述数据的四种逻辑结构及其特点。

答案

数据的逻辑结构通常有集合结构、线性结构、树型结构、图形结构这4种基本结构。

集合结构，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。

线性结构，该结构的数据元素之间存在一对一的关系。

树型结构，该结构的数据元素之间存在一对多的关系。

图形结构，该结构的数据元素之间存在多对多的关系，图形结构也称为网状结构。

2、简述数据的四种存储结构及其特点。

答案

数据结构一般用四种基本的存储结构来表示数据之间的关系。

1、顺序存储结构，把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，可以实

现随机存取，但要使用一整块存储单元，可能产生较多的外部碎片。

2、链式存储结构，该方法不要求逻辑上相信邻的数据元素在物理位置上也相邻，不会出现

碎片现象,可以充分利用所有存储单元。缺点是每个元素因存储指针而占用额外的存储空间，

只能实现顺序存取。

3、索引存储结构，该方法在存储数据元素信息的同时，还建立附加的索引表。优点是检索

速度快。缺点是增加附加的索引表占用较多的存储空间。在增加和删除数据时要修改索引表,

因而花费较多的时间。

4、哈希(散列)存储结构，该方法的基本思想是根据数据元素的关键字直接计算出该数据

元素的存储地址。优点是检索、增加、删除结点的操作都很快。缺点是如果散列函数不好,

可能出现数据元素存储地址的冲突，而解决冲突会增加时间和空间开销。

3、设线性表中数据元素递增有序。试设计一个算法，将x插入到线性表的适当位置上，以

保持线性表的有序性，并分析算法的时间复杂度。

intinsertElem(Seqlist*L,inti,ElemTypex)

{intnewsize,i;

ElemType*newbase;

if(L->length>=L->listsize)

{newsize=(L->listsize+LISTINCREAMENT)*sizeof(ElemType);

newbase=(ElemType*)realloc(L->elem,newsize);

if(!(newbase))

returnERROR;

L->elem=newbase;

L->listsize+=LISTINCREAMENT;

)

for(i=L->length-1;L->elem[i]>x&&i>=0;i—)

L->elem[i+l]=L->elem[i];

L->elem[i+l]=x;

L->length++;

returnOK;

)

4、有顺序表A和B,其元素均按从小到大的顺序排列，编写一个算法将它们合并成一个顺

序表C,要求C中的元素也是按从小到大排列的。

voidMergeList(Seqlist*lc,Seqlistla,Seqlistlb)

{inti,j,lnea,lenb;

ElemTypeel,e2;

InitList(lc);

lena=ListLength(la);

lenb=ListLength(lb);

i=l；j=l；

while(i<lena&&j<lenb)

{GetElem(laJ,&e1);

GetElem(lb,j,&e2);

if(el<e2){

InsertElem(lc,ListLenth(*lc)+1,e1);i++;}

else{

InsetElem(lc,ListLenth(*lc)+1,e2);j++;}

)

while(i<=lena){

GetElem(la,I,&el);i++;

InsertElem(lc,ListLength(*lc)+l,el);}

while(i<=lenb){

GetElem(lb,j,&e2);j++；

InsertElem(lc,ListLength(*lc)+l,e2);}

)

4、若对n阶下三角矩阵A,以行序为主序方式将其元素(包括主对角线上所有元素)依次存

放于一维数组B[l...n*(n+l))/2+l]中，请推导出在B中确定a.的位置k的映射函数。

答案

对于下三角中的元素a.,其特点是：i5且IWiWn,存储到向量B中后，根据存储原则，它

前面有i-1行,共有l+2+3+...+i-l=i(i-l)/2个元素,而aij又是它所在的行中的第j个元素，

所以在存储中aij是第i(i-l)/2+j个元素。

在存储完下三角中的元素之后，紧接着存储主对角线上方的常量，因为是同一个常数，所以

存储一个即可。

综上所述，若下三角矩阵A经过压缩存储后，对于矩阵中的任意元素a.存储在B中下标为

k的单元，则k与i,j之间的关系为：

Ki-1).

i>J

k=

+1)।]

i<j

5、若对n阶上三角矩阵A,以列序为主序方式将其元素(包括主对角线上所有元素)依次放

于一维数组BLl...n*(n+l))/2+l］中，请推导出在B中确定a.的位置k的映射函数。

答案

对于上三角中的元素a”，其特点是：i<=j且iWjWn,存储到向量B中后，根据存储原则，它

前面有j-1列,共有1+2+3+…+j-l=j(j-D/2个元素，而aij又是它所在的行中的第i个元素,

所以在存储中a.是第j(j-l)/2+i个元素。

在存储完上三角中的元素之后，紧接着存储主对角线下方的常量，因为是同一个常数，所以

存储一个即可。

综上所述，若下三角矩阵A经过压缩存储后，对于矩阵中的任意元素ag存储在B中下标为

k的单元，则k与i,j之间的关系为：

70-1)「

j>i

k=

n(n+1)

、—一+1J<i

6、设输入序列为a,b,c,d,借助一个栈，写出可以得到的两个输出序列和不能得到的两个序

列。

答案

能得到的输出序列：d,c,b,aa,b,c,d不能得到的输出序列：a,c,d,ba,d,b,c

7、请定义单链表存储结构，并写出用头插法创建带头结点的单链表的算法。

typedefstructnode

{ElemTypedata;

structnode*next;

JLinkList;

单链表的创建-头插法

LinkList*CreateList_nx(intn)

{intI;

LinkList*head,*p;

head=(LinkList*)malloc(sizeof(LinkList));

head->next=NULL;

for(i=l;i<=n;i++)

{p=(LinkList*)malloc(sizeof(LinkList));

Scanf(u%d,,,&(p->data));

p->next=head->next;

head->next=p;}

returnhead;

)

8、请定义单链表存储结构，并写出用尾插法创建带头结点的单链表的算法。

typedefstructnode

{ElemTypedata;

structnode*next;

JLinkList;

单链表的创建■尾插法(7分)

LinkList*CreateList(intn)

{intI;

LinkList*head,*p,*r;

head=(LinkList*)malloc(sizeof(LinkList));

r=head;

for(i=l;i<=n;i++)

{p=(LinkList*)malloc(sizeof(LinkList));

Scanf(u%d,,,&(p->data));

r->next=p;

r=P；}

—next=NULL;

returnhead;

)

10、对于给定的权值(15,3,14,2,6,9,16,17)。

(1)请构造哈夫曼树。(2)计算该哈夫曼树的带权路径长度WPL值。(3)写出它的哈夫

曼编码。规定：哈夫曼树构造中左子树权值小于右子树。

哈夫曼树

哈夫曼编码：

15:1113:1010114:110

2:101006:10119:100

16:0017:01

23

哈夫曼树的带权路径长度WPL值

WPL=((16+17)*2+(9+14+15)*3+6*4+(2+3)*5)=229

11、已知一棵二叉树的先序、中序遍历序列分别为ABCDEFGHI和BCAEDGHFI。请画出

这棵二叉树和它的中序线索树。

二叉树中序线索树

13、设二叉树采用二叉链表存储结构，请编写二叉树的先序遍历的非递归算法。

voidPreOrder_Nonrecursive(BiTree*t)

{BiTree

inttop=0;

if(t!=NULL){

P=t；

do{

while(p!=NULL){

print，%c>\p->data);

s[top]=p;top++;

p=p->left;}

lf(top>0){

top-;p=s[top];

p=p->right;)

}while(p!=NULL||top>0);

14、设二叉树采用二叉链表存储结构，请编写二叉树的中序遍历的非递归算法。

VoidinOrder_Nonrecursive(BiTree*t)

{BiTree*s[MJ,*p;

inttop=0;

if(t!=NULL){

P二t；

do{

while(p!=NULL){

s[top]=p;top++;

p=p->left;}

lf(top>0){

top-;p=s[top];

print，'%c”,p->data);

p=p->right;}

}while(p!=NULL||top>0);

}

)

15、已知一棵二叉树的先序、中序遍历序歹U分别为ABDFCEGH和BFDAGEHC。

请画出这棵二叉树并将其转换成对应的树（或森林）。

17、已知某图的邻接表如图所示。

（1）写出此邻接表对应的邻接矩阵。

（2）写出由vi开始的深度优先遍历的序列。

（3）写出由w开始的深度优先的生成树。

（4）写出由vi开始的广度优先遍历的序列。

（5）写出由W开始的广度优先的生成树。

（1）邻接矩阵存储结构

123456

VIV2V3V4VSV6

1011100一

2100010

3100010

4100001

5011000

6000100

(2)由VI开始的深度优先遍历的序列：VIV2V5V3V4V6

(4)由vi开始的广度优先遍历的序列：VIV2V3V4V5V6

(3)由vi开始的深度优先的生成树(5)由vi开始的广度优先的生成树

17、已知某图的邻接表如图所示。

(1)画出该图。

(2)画出该图的邻接矩阵存储结构。

(3)写出以顶点VI为出发点的深度优先遍历序列。

(4)写出以顶点VI为出发点的广度优先遍历序列。

答案

(1)画出该图

（2）邻接矩阵存储结构

123456

V6|

VIV2V3V4V5Vexnum10arcnum2kind

1一011100-

2000011

3000010

4001011

5000001

6000000

（3）以顶点VI为出发点的深度优先遍历序列：VIV2V5V6V3V4

（4）以顶点VI为出发点的广度优先遍历序列：VIV2V3V4V5V6

18、已知一个有向无环图如下图所示，写出它的一个拓扑序列。

拓扑序歹U为VIV2V3V5V4V6

19＞已知一个无向网如下图所示，要求分别用Prim和Kruskal算法生成最小树。

Prim算法最小生成树Kruskal算法最小生成树

20、下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的

代价，如何选择能沟通每个城市且总代价最省的n-l条线路，画出所有可能的选择。(10分)

21、设有一组关键字{9,1,23,14,55,20,84,27},采用哈希函数Hash(key)=keymod

7,表长为10,用开放地址法的二次探测法Hi=(Hash(key)+&)mod10(4=12,22,32,...)解

决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

构造哈希表

关键码14192384275520

散列地址0123456789

平均查找长度ASL=(4*1+2*2+1*3+1*4)/8=15/8

22、已知一组关键码{28,16,32,12,60,2,5,72,},请写出以第一个记录为基准对其进行快速排序

(升序)的过程。

原始序列28163212602572

第一次划分51621228603272

第二次划分2F寸16122832回72

21

第三次划分5)12国2832回72

23使用散列函数Hash(x)=xmod11,把一个整数值转换成散列表下标，现要把数据

{1,13,12,34,38,33,27,22}插入到散列表中。

(1)使用线性探查再散列法来构造散列表。

(2)使用链地址法构造散列表。

24、编写折半插入排序算法并分析其性能。

voidBinSort(SeqList*L)

{inti,j,low,high,mi