更新国家开放大学电大本科《数据结构》期末题库和答案Word下载.docx

更新国家开放大学电大本科《数据结构》期末题库和答案Word下载.docx

《更新国家开放大学电大本科《数据结构》期末题库和答案Word下载.docx》由会员分享，可在线阅读，更多相关《更新国家开放大学电大本科《数据结构》期末题库和答案Word下载.docx（50页珍藏版）》请在冰点文库上搜索。

7．向具有n个结点的堆中插入一个新元素的时间复杂度为（）。

A．O

（1）B．0（n）

C．O（log2n）D．O（nlog2n）

8．在一棵AVL树中，每个结点的平衡因子的取值范围是（）。

A．一l～1B．一2～2

C．1～2D．O～1

9．一个有n个顶点和n条边的无向图一定是（）的。

A．连通B．不连通

C．无回路D．有回路

二、填空题，在横线处填写合适的内容（每小题2分，共l4分）

1．数据结构包括（）、存储结构和对数据的运算这三个方面。

2．一维数组所占用的空间是连续的。

但数组元素不一定顺序存取，通常是按元素的（）存取的。

3．将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该一

维数组需要至少具有（）个元素。

4．对于一棵具有n个结点的树，该树中所有结点的度数之和为（）。

5．在一棵高度为3的理想平衡二叉树中，最少含有（）个结点，假定树根结点的高度为0。

6．假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底层的结点数为（）个。

7．用邻接矩阵存储图，占用的存储空间与图中的（）数有关。

三、判断题。

在每小题前面打对号表示正确或打叉号表示错误（每小题2分。

共14分）

（）1．算法和程序都应具有下面一些特征：

有输入，有输出，确定性，有穷性，有效性。

（）2．用字符数组存储长度为n的字符串，数组长度至少为n+1。

（）3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

（）4．邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。

（）5．对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。

（）6．在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。

（）7．图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。

四、运算题（每小题6分，共30分）

1．假定一棵二叉树广义表表示为a（b（c），d（e，f）），分别写出对它进行中序、后序、按层遍历的结果。

中序：

后序：

按层：

2．一个一维数组all2]中存储着有序表（15，26，34，39，45，56，58，63，74，76，80，86），根据折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成功搜索时的平均搜索长度。

度为l的结点个数：

平均搜索长度：

3．假定一个线性序列为（38，42，55，15，23，44，30，74，48，26），根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。

左子树为空的所有单支结点：

右子树为空的所有单支结点：

所有叶子结点：

4．已知一个图的顶点集V和边集G分别为：

V={1，2，3，4，5，6}；

E={<

1，2>

，<

1，3>

2，4>

2，5>

3，4>

4，5>

4，6>

5，1>

，

<

5，3>

6，5>

}；

假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次

序链接的，试写出：

（1）从顶点l出发进行深度优先搜索所得到的顶点序列；

（2）9,N点1出发进行广度优先搜索所得到的顶点序列。

（1）：

（2）：

5．已知一个数据序列为{16，45，27，23，41，15，56，64}，请把它调整为一个最大堆。

最大堆：

五、算法分析题（每小题6分。

共12分）

1·

下面算法的功能为：

将两个有序单链表合并成一个有序单链表并返回其表头指针。

阅

读算法，在划有横线的上面填写合适的内容。

ListNode*Mergel（ListNode*．&

pl，ListNode*&

p2）

{

ListNode*p=newListNode，*f=p；

while（p1!

=NULL&

&

p2!

=NULL）

if（pl-->

data<

=p2-->

data）{

p-->

link=pl；

;

}

else{p->

link=p2；

p2=p2一>

if（pl!

=NULL）p-->

elsep～>

1ink=p2；

pl==p2==NULL；

returnf一>

link：

2．已知二叉树中的结点类型BinTreeNode定义为：

structBinTreeNode{ElemTypedata；

BinTreeNode*left，*right；

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。

根据下面算法的定义指出其功能。

算法中参数BT指向一棵二叉树。

BinTreeNode*BTreeSwopX（BinTreeNode*BT）

{

if（BT==NULL）returnNULL；

else{

BinTreeNode*pt=newBinTreeNode；

pt一>

data—BT一>

data；

right—BTreeSwopX（BT一>

left）；

left=BTreeSwopX（BT-->

right）；

returnpt；

算法功能：

六、算法设计题（每小题6分，共12分）

1．已知f为单链表的表头指针，单链表中的结点结构为（data，link），并假定每个结点的值均为大于0的整数。

根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值0。

intMax（LinkNode*f）；

2．设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明

写出从此队列中删除一个元素的算法。

／／循环队列定义

structCyclicQueue

ElemTypeelemEM]；

／／M为已定义过的整型常量

intrear；

／／rear指向队尾元素的后一个位置

intlength：

／／length指示队列中元素个数

}5

／／若队列非空则删除队头元素并由引用参数x带回，同时返回true；

否则若队列为空则返回false。

boolDelCQueue（CyclicQueueQ，ElemType&

x）；

试题答案及评分标准

一、单项选择题，翟括号内填写所选择的标号（每小题2分，共18分）

1．C2．C3．B4．B5．C6．A7．C8．A9．b

二、填空题。

在横线处填写合适内容（每小题2分，共14分）

1．逻辑结构2．下标（或顺序号）3．n（n+1）／24．n一15．86．197．顶点

三、判断题，在每小题前面打对号表示正确或打叉号表示错误（毒小题2分。

1．错2．对3．对4．错

5．对6．错7．对7．对

1．中序：

C，b，a，e，d，f

C，b，e，f，d，a

a，b，d，C，e，f

2．度为1的结点个数：

5

37/12

3．左子树为空的所有单支结点：

l5，23，42，44

30

26，48，74

4．（I）1，2，4，5，3，6／／3分

（2）1，2，3，4，5，6／／3分

5．最大堆：

{64，45，56，23，41，15，27，16}

1．pl2p1一>

link、p=p一>

link／／每空3分

2．生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右

子树（或左、右孩子的值）交换的结果。

六、算法设计题（每小题6分。

1．评分标准：

按注释酌情给分。

intMax（LinkNode*f）

{

if（f==NULL）return0：

if（f一>

link==NULL）returnf一>

inttemp=Max（f-->

link）；

data>

temp）returnf一>

elsereturntemp；

2．评分标准：

按注释酌情给分：

boolDelCQueue（CyelieQueueQ，ElemType&

x）

if（Q．1ength==O）returnfalse；

x—Q．elem[（Q．rear—Q．1ength-t-M）％M]；

Q．1ength一一；

returntrue；

《数据结构》题库及答案二

一、单项选择题（每小题2分。

共30分）

1．链表所具备的特点是（）。

A．可以随机访问任一结点

B．占用连续的存储空间

C．插入删除元素的操作不需要移动元素结点

D．可以通过下标对链表进行直接访问

2．线性结构中数据元素的位置之间存在（）的关系。

A．一对一

B．一对多

C．多对多

D。

每一个元素都有一个直接前驱和一个直接后继

3．算法的时间复杂度与（）有关。

7

A．所使用的计算机B．与计算机的操作系统

C．与算法本身D．与数据结构

4．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后继，现要删除q所指结点，可用的语句是（）。

A．p=q->

nextB．p->

next=q

C．p->

next=q->

nextD．q->

next=NULL

5．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。

A．r=f->

next：

B．r=r->

C．f=f一>

next；

D．f=r一>

6．元素3，6，9按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。

A．9，6，3

B．9，3，6

C．6，3，9

D．3，9，6

7．设有一个l0阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组8中（数组下标从1开始），则矩阵中元素氏，。

在一维数组B中的下标是（．）。

A．33B．32

C．85D．41

8．在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。

A．4B．3

C．6D．12

9．一棵有n个结点采用链式存储的二叉树中，共有（）个指针域为空。

A．n+1B．n

C．n一1D．n--2

10．设一棵哈夫曼树共有n个叶结点，则该树有（）个非叶结点。

A．n—lB．n

C．n+1D．2n

11．在一个无向图中，所有顶点的度数之和等于边数的（）倍。

A．3B．2．5

C．1．5D．2

12．已知如图1所示的一个图，若从顶点V。

出发，按广度优先进行遍历，则可能得到的一种顶点序列为（）。

13．在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120）中，用折半查找法查找值80时，经（）次比较后查找成功。

A．4B．2

C．3D．5

14．排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）。

A．冒泡

B．直接插入

C．折半插人

D．选择排序

15．排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（）排序。

A．归并B．插入

C．快速D．选择

二、填空题（每小题2分。

共24分）

结构中的数据元素存在多对多的关系称为——结构。

2.要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。

则比较的

次数和算法的时间复杂度分别为---------和---------

3·

设有一个头指针为head的单向循环链表，p指向链表中的结点，若p一>

next==

——，则P所指结点为尾结点。

4·

向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s一>

next=h；

和---------

5·

在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为------

和r=s；

（结点的指针域为next）

6.设有n阶对称矩阵A，用数组s进行压缩存储，当i<

j时，A的数组元素aij相应于数组s的数组元素的下标为-----------。

（数组元素的下标从l弃始）

7·

一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为---------,---------

8·

一棵有2n--1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有-------

个叶结点。

9．—-----—遍历二叉排序树可得到一个有序序列。

10．如图2所示的二叉树，其前序遍历序列为---------

11二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。

这种说法是——的。

（回答正确或不正确）一“

12.按某关键字对记录序列排序，若——一———在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。

三、综合题（每小题10分。

1．一组记录的关键字序列为（46．79，56，38，40，84）

（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果。

（给出逐次交

换元素的过程，要求以升序排列）

（2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。

2．设查找表为（16，15，20，53，64，7）

（1）用冒泡法对该表进行排序（要求升序排列），要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡?

第j趟要进行多少次元素间的比较?

（2）在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。

（要求以数据

元素作为树结点）

（3）求在等概率条件下，对上述有序表成功查找的平均查找长度。

3．

（1）“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。

该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由?

（2）设有查找表（7，16，4，8，20，9，6，18，5），依次取表中数据构造一棵二叉排序树。

对上述二叉树给出后序遍历的结果。

四、程序填空题（每空2分。

共16分）

1．以下是用头插法建立带头结点且有n个结点的单向链表的程序，要求结点中的数据域从前向后依次为n，n--1，……，l，完成程序中空格部分。

NODE*create2（n）

{NODE*head，*P，*q；

inti；

D=（NODE*）malloc（sizeof（NODE））；

P一>

next=NULL；

head=

（1）——；

（2）——；

for（i=1；

=n；

{P2（3）———————————————；

p一>

data=i；

if（i==1）

p->

else

next2（4）——；

q一>

next2（5）——；

return（head）；

2．以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right，数据域data为字符型；

BT指向根结点）。

voidPostorder（structBTreeNode*BT）

{if（BT!

=NULL）{·

（1）---------------------------------；

（2）---------------------------------；

（3）--------------------------------；

一、单项选择题（每小题2分，共30分）

1．C2．A3．C4．C5．C

6．B7．A8．A9．Al0．A

11．Dl2．Cl3．Al4．Cl5．D

二、填空题（每小题2分。

共24分）’

1-图状（网状）‘

2．n一1，0（n）

3．head

4．H=s；

5．r一>

next=S；

6．i（i一1）／2+j

7．2i和2i+1

8．n

9．中序

10．abdefeg

11．不正确

12．关键字相等的记录

共30分）

1．

（1）初始序列46，79，56，38，40，84

40，79，56，38，回，84

40，回，56,38，79，84

40，38，56，围，79，84．

40，38，回，56，79，84

40，38，46，56，79，84，

（2）

2．

（1）原序列16152053647

15162053764n一1耥

15162075364n—j次

15167205364

15716205364

71516205364

（2）

（3）平均查找长度一（1*1+2*2+3*3）／6—14／6

3．

（1）不正确，二叉排序树要求其子树也是二又排序树。

（2）·

后续遍历5，6，4，9，8，18，20，16，7

1．

（1）P

（2）q=P

（3）（NODE*）malloc（sizeof（NODE））

（4）q->

next

（5）p

2．

（1）Postorder（BT一>

left）

（2）Postorder（BT一>

right）

（3）printf（“c”，BT一>

data）

《数据结构》题库及答案三

共18分）

1．若需要利用形参直接访问实参，则应把形参变量说明为（）参数。

A．指针B．引用

C．传值D．常值

A．OB．1

C．2D．n

3．已知单链表A长度为m，单链表8长度为n，它们分别由表头指针所指向，若将B整体连接到A的末尾，其时间复杂度应为（）。

A．O

（1）B．O（m）

C．O（n）D．O（m十n）

4．假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）

A．iront==rearB．front!

=NULL

C．rear!

=NULLD．front==NULL

5．若让元素l，2，3依次进栈，则出栈次序不可能出现（）种情况。

A．3，2，1B．2，1，3

C．3，1，2D．1，3，2

6．在一棵高度为5（假定树根结点的高度为0）的完全二叉树中，所含结点个数至少等于（）

A．16B．64

C．31D．32

7．向具有n个结点的二叉搜索树中插入一个结点的时间复杂度大致为（）。

A．O

（1）B．O（1og2n）

C．O（n）D．O（nlog2n）

8．具有n个顶点的有向图最多可包含有（）条有向边。

A．n—1B．n

C．n（n一1）／2D．n（n一1）

9．图的广度优先搜索类似于树的（）遍历。

A．先根B．中根

C．后根D．层次

在横线处填写合适的内容（每小题2分，共14分）

1．链表只适用于（）查找。

2．设双向循环链表中每个结点的结构为（data，llink，rlink），则结点*P的前驱结点的地址为（）。

3．在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有（）个结点。

4．假定一棵树的广义表表示为a（b，c，d（e，f），g（h）），则结点f的层数为（）。

假定树根结点的层数为0。

5．从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的（）继续搜索。

6．每次从第i至第n个元素中顺序挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做（）排序。

7．快速排序在最坏情况下的时间复杂度为（）。

三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分。

（）1．数据的逻辑结构与数据元素本身的内容和形式无关。

（）2．使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

（）3．在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历和按层遍历时具有相同的结果。

（）4．能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上

相同。

（）5．邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

（）6．在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

（）7．向一棵8树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高

度减少1。

四、运算题（每小题6分。

1．假定一棵二叉树广义表表示为a（b（c（，g）），d（e，f）），分别写出对它进行先序、中序和后序遍历的结果。

先序：

中序：

后序：

2．有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度。

带权路径长度：

3．已知图G=（V，E），其中

V={a，b，c，d，e}，

E={<

a，b>

b，a>

c，b>

c，d>

d，e>

e，a>