数据结构试卷及答案

东华理工大学2022—2022学年第一学期考试摹

拟试卷A

一、填空题（50分）

1、数据结构是一门研究非数值计算的程序设计问题中的重据元盍_以及它们之间关系和

运算等的科学。（2分）

2、数据结构的类型通常分为：集合、线性结构、树形结构、图状结构或者网状结构：

从逻辑上可以把它们分成：线性结构和非线性结构。

3、数据的逻辑结构只抽象反映数据元素的逻辑关系；数据的存储（物理）

结构是数据的逻辑结构在计算机存储器中的实现。

4、算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是空I巫

复杂度和时间复杂度»

A

5、计算机算法是解决问题的有限运算序列，它必须具备输入、输出、确定性、有穷性

和稳定性等5个方面的特性。

6、线性结构中元素之间的关系存在•对一关系,树形结构中元素之间的关系存在;

对多关系，图形结构中元素之间的关系存在多对多关系。

7、试写出以下算法的时间复杂度

i=s=0

while（s<n）{

i++；

s+=i;

I

。而

7、试写出以下算法的时间复杂度

i=1

while(i<=n)

i=i*2

O(log2n)

8、抽象数据类型的定义由三元组来定义：(D,S,P)其中，D是数据对象，S是D上的

关系集，P是对D的基本操作集。

9、写出抽象数据类型线性表的定义

ADTList{

数据对象：D={ai|aiElemset,i=l,2,...,n,n0}

数据关系：R={<ai-1,ai>|ai-1,aiD,i=2,...,n}

基本操作：

InitList(&L)〃构造一个空的线性表L

DestroyList(&L)〃消毁线性表L

ListLength(L)//返回L中数据元素的个数

ListInsert(&L,i,e)//1<i<ListLength(L)+l,在L中第i个位置之前插入数据元素e,L长度

加1

ListDelete(&L,i,&e)//1<i<ListLength(L)删除L中的第i个元素，并用e返回

ListTraverse(L,visit())//挨次对L的每一个元素调用函数visit()

}ADTList

10、指出线性表顺序存储、链式存储结构的优缺点。

答：顺序存储优点：逻辑上相邻，物理位置也相邻，可以随机存取表中任一元素：缺点：插

入和删除元素时需要挪移大量元素。

链式存储结构优点：插入、删除元素时不需要挪移元素；缺点：逻辑上相邻，物理位置

不一定相邻，不能随机存取表中元素，需要挨次查找，求线性表的长度时不如顺序存储结构

方便，需要逐个结点搜索计算，或者设置带头结点的线性链表。

11、完成下列在单链表中删除元素算法

StatusListDelete_L(LinkLisl&L,inti,ElemType&e){〃删除第i个元素e

p=L;j=0;〃p指向头结点

while(p->next&&j<i-l)(

p=p->next;++j

}//寻觅第i个结点，并令P指向其前驱

if(!(p->next)||j>i-l)returnERROR;〃删除位置不正确

q=p->next;p->next=q->next;〃删除与释放结点e=q-

>data;

free(q);

returnOK;

)

12、在一个长度为n的线性链表中第i个元素(1in)之前插入一个元素时，需向后挪移n・i+l

个元素。

13、在一个长度为n的线性链表中删除第i个元素(1in)时，需向前挪移n-i个元素。

14、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=p->next和

p->next=s的操作。

15、在单链表中，插入或者删除一个结点元素时，仅需要修改指针而不需要挪移元素。

16、栈(Stack)是限定仅在表尾进行插入和删除操作的线性表，

17、栈链式存储结构中删除栈顶元素，并用e返回，完成下列算法

StatusPop(ListStack&S,SElemType&e){

if(S.top=NULL)returnERROR;〃栈无元素

p=S.top;

S.top=S.top->next;

e=p->data;

free(p);〃释放节点批p

S.len—;

returnOK;

)

17、设有一队列，(al,a2,…,an)则对头元素是al队尾元素是an。

18、假设队列以带头结点的链式表示，则删除一不元素并返回给e的算法如下:

StatusDeQueue(LinkQueue&Q,QElemType&e){

if(Q.front==Q.rear)returnEEROR;

p=Q.front->next;//p为需要删除的结点

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;〃队列中惟独一个元素被删除时，队尾等于队头

free(p);

returnOK;

}

19、循环队列中，假设少用一个元素，则插入元素到队尾的算法

StatusEnQueue(SqQueue&Q,QElemTypee){

if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;〃队满

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;//Q.rear前移

returnOK;

)

20、循环队列中，假设少用一个元素，则/删除队头元素并赋给e的算法如下

StatusDeQueue(SqQueue&Q,QElemType&e){

if(Q.front=Q.rear)returnERROR;〃队空

e=Q.base[Q.Oont];

Q.front=(Q.front+1)%MAXQSIZE;//Q.rear前移

returnOK;

)

21、判定一个队列QU(最多元素为MaxSize)为空的条件是：QU->front==QU->rear；为

满队列的条件是：QU->rear-QU->front==MaxSize。

22、SUABCDEFG's2=TQRST\假设con(x,y)为连接两字符串函数，subs(s,i,j)返回串s

中从第i个位置起的j个字符，len(s)返回串s的长度，则

con(subs(sl,2,len(s2)),subs(s1,len(s2),2))的结果串为：BCDEFEF

23、什么是稀疏矩阵？如何衡量？举例采用三元子顺序表示已稀疏矩阵。

答：当矩阵中的非零元素比较少，且分布没有一定的规律，称为稀疏矩阵。稀疏矩阵的衡量

标准，可以用稀疏因子表示，通常认为当W0.05是称为稀疏矩阵

t

mn

24、深度为5的二叉树最多有31个结点。

25、深度为k的彻底二叉树至少有2k-l个结点，至多有2k-l个结点，若自上而下，从

左到右次序给结点编号（从1开始），则编号最小的叶结点的编号是2k-1。

26、己知一棵二叉树的中序遍历序列为cbedahgijf,后序遍历序列为cedbjigfa,画出该二

叉树。

二、设有下列一棵树，回答下列问题：（15分）

1）该树的根结点是A:

2）这棵树的叶结点是G、E、F、I、J；

3）该树的非终端结点是A、C、B、D、H；

4）D结点的度是1；

5）该树的度是3；树深度是4；

6）将该树转换成二叉树。（5分）

7）假设对该树进行先根遍历、后根遍历，写出该树的先根序列、后根系列。（5分）

先根序列：ACGDHIJBEF

后根系列：GCIJHDEFBA

2、数据逻辑结构包括：线性结构、树形结构和图形结构三种类型，树形结构和图

形结构合称为非线性结构。（4分）

3、下列程序段的时间复杂度是0（n）。（2分）

i=s=0;

while（s<n）{

i++；

s+二i;

）

4^判断一个循环队列QU（最多元素为mO）为满队列的条件是QU->front==（QU->rear+1）%

mOo（2分）

5、带头结点的单链表head为空的判断条件是head->next==NULL。（2分）

6、假设线性表采用单链表存储结构,完成下列插入元素的算法（5分）

StatusListInsert_L（LinKLis&tL,inti,ElementTypee）

{/在带头结点的单链线性表L中第i个位置之前插入元素

P=L;j=0;

while(p&&j<i-1)p={p->next;++j}

if(!p||j>i-l)returnERRORs=(

LinkLismtaDloc(sizeof(LNode));s->data=

e；

s->next-p->next;一

p->next=s;returnOK

)

7、若x和y是两个采用顺序结构存储的串，编写并完成比较两个串是否相等的函数。(6分)int

Issame(orderstring*x,orderstring*y)

(

inti=0;tag=1;

if(x->len!=y->len)retum(O);

else

(

while(ivx->len&&tag)

(

if(x->vec[i]!=y->vec[i]t)ag=0;

i++;

)

return(tag);

)

)

8、已知二维数组A[m][n]采用行序为主方式存储，每一个元素占k个存储单元，并且第一个

元素的存储地址是LOC(A[0]⑼)，则用的地址是LOC(A⑼[0])+(n*i+j)*k。(2分)

10、下图所示的4棵二叉树，是平衡二叉树的树是B、D。(4分)

11、深度为k的彻底二叉树至少有2口个结点，至多有27个结点，若

从上而下，从左到右次序给结点编号（从1开始），则编号最小的叶结点的编号是

）2+1。（3分）.

12、有向彻底图：具有n（n-l）条边的有向图称为有向彻底图。（2分）

13、对线性表进行折半查找时，要求线性表必须以顺序方式存储，且结点按关键字有序排

列°（4分）

14、一组记录的排序码为（17,48,2435,69,8223,79,3）6,,其72中含有5个长度为2的有序表，按归并

排序的方法对该序列进行一趟归并排序后的结果为：

17,24,35,48,23,69,79,82,36,72。（6）

15、己知系列｛503,87,512,61,908,170,897,275,653,462）,以第一个记录为枢

轴（基准），写出采用快速排序法对该序列作升序排序时的第一趟的结果：（5分）[462,87,

275,61,170]503[89,7908,653,503]。

三、已直一棵二叉树的中序遍历系列为kbedohgijf,后序遍历系列为kedbhjigfb,画出该二叉

树。（5分）

四、稀疏矩阵有什么特点？假设用三元组顺序表来表示稀疏矩阵，试设计该方法的存储结构。

写出下列稀疏矩阵的三元组表示。（10分）

0020

3000

0015

0000

答：实际非零元素的个数远远小于矩阵元素的个数（0.05）。

三元组顺序表示存储结构可设计如下:

#MAXSIZE12500;

typedefstruct{

intij;

Elemtypee;

JTriple;

typedefstruct{

Tripledata[MAXSIZE+1]；

intmu,nu,tu;

JTSMatrix;

将下列树转换成二叉树

①

已知有5个字符(4b,cd)e,它们浮现的权值分别是｛12,4,5,2。，3｝试构建一

个赫夫曼树，并求它们的赫夫曼编码。

a(0),b(100),c(101),d(110),e(lll)

彻底图:对于有n顶点的无向图，边E的取值范围是0〜n(n-l)/,2当n个

顶点的无向图有n(n-l)/2条边时称为彻底图

有向彻底图:对于有n顶点的无向图，边E的取值范围是0〜n(n-l),当n

个顶点的有向图有n(n-l)条边时称为有向彻底图采用邻接表存

储图的深度优先遍历法算类似与二叉树的先序遍历，

而广度优先遍历算法类似与二叉树的层序遍历。

已知一个有向图用邻接矩阵表示，则计算第i结点入度的方法是求

矩阵第i列非0元素之和。

图的深度优先搜索序列和广度优先搜索序列是不惟一的。

三、图的存储结构有哪几种？请用邻接矩阵和邻接表两种存储结构表示下图。(10分)

参考答案:

（1）图的存储结构有有：数组表示法（邻接矩阵）、邻接表、十字链表和邻接多重表四种表

示方法。（2分）

（2）邻接矩阵储结构如下：（4分）

01000

10101

01011

00101

01110

（3）邻接表存储结构如下：（4分）

五、用Dijstra方法求下图中从V0点到各终点的最短路径，并在表格中填写求

解过程。（12分）

参考答案：

（1）在表格中填写算过程（8分）

从V0点到各终点的D值和最短路径的求解过程

线占

八、、

1=11=21=31=41=5

1

VI

(vO,vl)

2

V2

{v0,vl,v2}

553

V3

(v0,v3)(v0,v3)(v0,vl,v2,v3)

V4无

34

44

V5

(v0,v5)(v0,vl,v5)

(v0,vl,v5)(v0,vl,v5)

V1vz-

VJV3V5

IvOvl!IvOvlv?l

S{v0,vl,v2,v3,v5}

(2)阐述丫0到各点的路径(4分)

vO到vl点的最短路径为1,顶点为(vO,vl)

vO到v2点的最短路径为2,顶点为(v0,vl,v2)

vO到v3点的最短路径为3,顶点为(v0,vl,v2,v3)

vO到v4点之间无路径

vO到v5点的最短路径为4,顶点为(v0,vl,v5)

五、试找出下列有向无环网的关键路径。(10分)

顶点veV1边e11-e

VI00al099

V2413a2077

V3613