数据结构历年试题及答案

本文格式为Word版，下载可任意编辑——数据结构历年试题及答案试卷：1252

中央广播电视大学2023-2023学年度其次学期“开放本科〞期末考试

一、单项选择题（每题2分，共30分）1．在C语言中，顺序存储长度为3的字符串，需要占用()个字节。A．4B．3C．6D．122。串函数StrCat(a，b)的功能是进行串()。A．比较B．复制C．赋值D．连接3．-棵有n个结点采用链式存储的二叉树中，共有()个指针域为空。A．n+lB．nC．n-lD．n-24．设一棵哈夫曼树共有n个非叶结点，则该树有()个叶结点。A．nB．n+lC．n-lD．2n5．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行()。A.x=top->data;top=top->nextB.x=top->data

C.top=top->next;x=top->dataD.top=top->next;x=data

6．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有()个结点。A．30B．20C．21D．23

7．在一个无向图中，所有顶点的度数之和等于边数的()倍。^A．O上；．B．3C．1.5D．28．已知如图1所示的一个图，若从顶点V，出发，按深度优先探寻法进行遍历，则可能得到的一种顶点序列为()。

9．已知如图2所示的一个图，若从顶点a出发，按广度优先探寻法进行遍历，则可能得到的一种顶点序列为()。A.abcedfB.abcefdC.aebcfdD.acfdeb10.对二叉排序树进行()遍历，可以使遍历所得到的序列是有序序列。

A．按层次B．后序C．中序D．前序

11．在有序表(2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80时，经()次比较后查找成功。A．4B．2C．3D．5

12．有一个长度为9的有序表，按折半查找对该表进行查找，在等概率状况下查找成功的平均比较次数为()。A．25/10B．25/9C．20/9D．17/9

13.排序算法中，从未排序序列中依次取出元素与已排序序殂（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是()。A．冒泡B。直接插入C．折半插入D．选择排序

14．一组记录的关键字序列为(46，79，56，38，40，84)，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为()。A．40,38946,79956,84B．40,38946,56,79,84C．40，38,46,84,56,79D．38，40,46956,79,84

15.排序方法中，从尚未排序序列中挑拣元素，并将其依次放人已排序序列（初始为空）的一端的方法，称为()排序。A．归并B．插入C．快速D．选择

1．A2．D3．A4．B5.A6．C7．D8．A9．B10.C11．B2．B13．C14．B15.D二、填空题（每题2分。共20分）

16.在二叉树的链式存储结构中，寻常每个结点中设置三个域，它们是(值域)(左指针)(右指针)。17.一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为(2i、2i+l)。

18.串的两种最基本的存储方式是(顺序存储)和(链式存储)。

19.-棵有2n-l个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有(n)个叶结点。20.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有（n+1）个指针域为空。21（中序）遍历二叉排序树可得到一个有序序列。

22.图的深度优先探寻和广度优先探寻序列不一定是唯一的。此断言是（正确）的。

23.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是（不正确）的。（回复正确或不正确）

24.对记录序列排序是指按记录的某个关键字排序，记录序列按（主关键字）排序结果是唯一的。25.按某关键字对记录序列排序，若（关键字相等的记录）在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题（每题10分。共30分）

26．设查找表为(16，15，20，53，64，7)，(1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，寻常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据元素作为树结点）。27．(1)设有查找表{5，14，2，6，18，7，4，16，3），依次取表中数据，构造一棵二叉排序树。(2)说明如何由序列的二叉排序树得到相应序列的排序结果。

38．(1)对给定权值2，1，3，3，4，5，构造哈夫曼树（要求每个结点的左子树根结点的权小于等于右子树根结点的权）。(2)给出各权值的哈夫曼编码。

四、程序填空题【每空2分。共16分）

30.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为1eft和right，数据域data为字符型，BT指向根结点）。voidPostorder(structBTreeNode*BT)

{if(BT!=NULL){(1)[](2)[](3)[]}}

试卷：1252

中央广播电视大学2023-2023学年度第一学期“开放本科〞期末考试

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

1．同一种规律结构()。A.只能有唯一的存储结构B．可以有不同的存储结构C．只能表示某一种数据元素之间的关系n以上三种说法均不正确

2．链表所具备的特点是()。A可以随机访问任一结点B占用连续的存储空间C插入删除元素的操作不需要移动元素结点D可以通过下标对链表进行直接访问3．数据的物理结构()。A与数据的规律结构无关B仅仅包括数据元素的表示C只包括数据元素间关系的表示n包括数据元素的表示和关系的表示4.线性结构中数据元素的位置之间存在()的关系。

A-对一B一对多C多对多D.每一个元素都有一个直接前驱和一个直接后继

14.设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B中（数组下标从1开始），则矩阵中元素氏。在一维数组B中的下标是．()。A．33B．32C．85D．41

15．在一个无向图中，所有顶点的度数之和等于边数的()倍。A3＆2.5C1.5D．21．B2．C3．D4．A5．D6．C7．B8．C9．A10．C11．A12．B13．C14．A15．D

二、填空题（每题2分，共24分）

16.栈和队列的操作特点分别是（后进先出）和（先进先出）。17.结构中的数据元素存在多对多的关系称为（网状）结构。18.根据数据元素间关系的不同特性，寻常可分为集合、线性、（树形）、（图形）、四类基本结构。

19.要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间繁杂度分别为（n-1）和(O(n))。

20.在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行(s->next=s)和(p->next=s)的操作。21．在二叉树的链式存储结构中，寻常每个结点中设置三个域，它们是值域、(左指针)、（右指针）。22．一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左右孩子的编号分别为（2i）、（2i+1）23．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行(s->next=h)；和(n=s)。24.在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为（r->next=s）和r=s；(结点的指针域为next)。

25.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有(12)个结点。（根所在结点为第1层）26.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的（行下标）、（列下标）和非零元素值三项信息。

27.在对一组记录(55，39，97，22，16，73，65，47，88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻觅插入位置，需比较（3）次。三、综合题（每题10分，共30分）

28．(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树（要求每个结点的左子树根结点的权小于等于右子树根结点的权），给出相应权重值叶结点的哈夫曼编码。(2)-棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由。29．一组记录的关键字序列为(46，79，56，38，40，84)

(1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）。(2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。30．设查找表为(50，60，75，85，96，98，105，110，120，130)

(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？

(3)画出对上述有序表进行折半查找所对应的判定树（要求以数据元素作为树结点）。

四、程序填空题（每空2分，共16分）

试卷：1252

中央广播电视大学2023--2023学年度第一学期“开放本科〞期末考试

一、单项选择题(每题2分。共30分)

1．链表所具备的特点是()。A．可以随机访问任一结点B．占用连续的存储空间C．插入删除元素的操作不需要移动元素结点D．可以通过下标对链表进行直接访问2．线性结构中数据元素的位置之间存在()的关系。A．一对一B．一对多C．多对多

D。每一个元素都有一个直接前驱和一个直接后继3．算法的时间繁杂度与()有关。7A．所使用的计算机B．与计算机的操作系统C．与算法本身D．与数据结构

4．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后继，现要删除q所指结点，可用的语句是()。A．p=q->nextB．p->next=qC．p->next=q->nextD．q->next=NULL

5．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为()。A．r=f->next：B．r=r->next：C．f=f一>next；D．f=r一>next：

6．元素3，6，9按顺序依次进栈，则该栈的不可能输出序列是()(进栈出栈可以交替进行)。A．9，6，3B．9，3，6C．6，3，9D．3，9，6

7．设有一个l0阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组8中(数组下标从1开始)，则矩阵中元素氏，。在一维数组B中的下标是(．)。A．33B．32C．85D．41

8．在C语言中，顺序存储长度为3的字符串，需要占用()个字节。A．4B．3C．6D．12

9．一棵有n个结点采用链式存储的二叉树中，共有()个指针域为空。A．n+1B．nC．n一1D．n--2

10．设一棵哈夫曼树共有n个叶结点，则该树有()个非叶结点。A．n—lB．nC．n+1D．2n

11．在一个无向图中，所有顶点的度数之和等于边数的()倍。A．3B．2．5C．1．5D．2

12．已知如图1所示的一个图，若从顶点V。出发，按广度优先进行遍历，则可能得到的一种顶点序列为()。

13．在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80时，经()次比较后查找成功。A．4B．2C．3D．5

14．排序算法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比

较次数尽量少)，然后将其放入已排序序列的正确位置的方法是()。A．冒泡B．直接插入C．折半插人D．选择排序

15．排序方法中，从尚未排序序列中挑拣元素，并将其依次放入已排序序列(初始为空)的一端的方法，称为()排序。A．归并B．插入C．快速D．选择

二、填空题(每题2分。共24分)

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

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进行压缩存储，当inext=NULL；head=(1)——；(2)——；

for(i=1；idata=i；if(i==1)p->next=NULL；else

p->next2(4)——；q一>next2(5)——；}

return(head)；}

2．以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右指针域分别为left和right，数据域data为字符型；BT指向根结点)。voidPostorder(structBTreeNode*BT){if(BT!=NULL){·

(1)；(2)；(3)；

()

A．iront==rearB．front!=NULLC．rear!=NULL

D．front==NULL

5．若让元素l，2，3依次进栈，则出栈次序不可能出现()种状况。A．3，2，1

B．2，1，3

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

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

B．64

C．31D．32

7．向具有n个结点的二叉探寻树中插入一个结点的时间繁杂度大致为()。

A．O(1)B．O(1og2n)C．O(n)

D．O(nlog2n)

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

A．n—1

B．n

C．n(n一1)／2D．n(n一1)

9．图的广度优先探寻类似于树的()遍历。A．先根

C．后根

B．中根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分。共14分)

()1．数据的规律结构与数据元素本身的内容和形式无关。()2．使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

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

()4．能够在链接存储的有序表上进行折半探寻，其时间繁杂度与在顺序存储的有序表上一致。

()5．邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。()6．在索引顺序结构上实施分块探寻，在等概率状况下，其平均探寻长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

()7．向一棵8树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。

四、运算题(每题6分。共30分)

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={，，，，，，}在该图的邻接表表示中，每个顶点单链表各有多少个边结点。顶点：abcde边结点数：

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

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

E={，，，，，，，，，}