本科-数据结构(本)期末综合练习

数据结构（本）期末综合练习2013年6月期末综合练习一1. 在数据结构和算法中，与所使用的计算机有关的是（）。

A．数据元数间的抽象关系B．数据的存储结构C．算法的时间复杂度 D．数据的逻辑结构2. 一种逻辑结构在存储时（）。

A．只要存储数据元素间的关系 B．只能采用一种存储结构C．可采用不同的存储结构 D．只要存储数据元素的值3 .对顺序表,以下叙述中正确的是 ( )。

A．用一组地址连续的存储单元依次存放线性表的数据元素B．各个数据元素的首地址是连续的C．数据元素不能随机访问D．插入操作不需要移动元素4 .对链表, 以下叙述中正确的是（）。

A．不能随机访问任一结点 B．结点占用的存储空间是连续的C．插入删除元素的操作一定要要移动结点 D．可以通过下标对链表进行直接访问5．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为（）。

A．9 B．10 C．15 D．166．线性表在存储后,如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结点，则采用（）存储方式是不可行的。

A．单链表 B．双链表 C．单循环链表 D．顺序表7. 设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( )。

A.p->next=p->next->next;B.p=p->next;C.p=p->next->next;D.p->next=p ;8．栈和队列的共同特点是（）。

A．都是先进后出 B．元素都可以随机进出C．只容许在端点处插入和删除元素 D．都是先进先出9．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（）。

（进栈出栈可以交替进行）。

A．7，5，3，1 B．7，3，1,5C．7，5，1，3 D．5,1，3，710．元素2，4，6，8按顺序依次进栈，按该栈的的可能输出序列依次入队列，该队列的可能输出序列是（）（进栈出栈可以交替进行）。

数据结构（本）期末综合练习（2022年6月）期末综合练习一一、单项选择题1．深度为5的完全二叉树共有20个结点，则第5层上有（）个结点(根所在结点为第一层)。

A．3B．8C．5D．62．同一种逻辑结构（）。

A．只能有唯一的存储结构B．可以有不同的存储结构C．只能表示某一种数据元素之间的关系D．以上三种说法均不正确3．已知一个图的边数为m，则该图的所有顶点的度数之和为（）。

A．2mB．mC．2m+1D．m/24．链表所具备的特点是（）。

A．可以随机访问任一结点B．占用连续的存储空间C．插入删除元素的操作不需要移动元素结点D．可以通过下标对链表进行直接访问5．数据结构中，与所使用的计算机无关的是数据的（）结构。

A．物理B．存储C．逻辑与物理D．逻辑6．数据的物理结构（）。

A．与数据的逻辑结构无关B．仅仅包括数据元素的表示C．只包括数据元素间关系的表示D．包括数据元素的表示和关系的表示7．链表所具备的特点是（）。

A．可以随机访问任一结点B．占用连续的存储空间C．插入删除不需要移动元素结点D．可以通过下标对链表进行直接访问8．线性结构中数据元素的位置之间存在（）的关系。

A．一对一B．一对多C．多对多D．每一个元素都有一个直接前驱和一个直接后继9．线性表只要以（）方式存储就能进行折半查找。

A．链接B．顺序C．关键字有序的顺序D．二叉树10．以下表中可以随机访问的是（）。

A．单向链表B．双向链表C．单向循环链表D．顺序表11．散列查找的原理是（）。

A．在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系B．按待查记录的关键字有序的顺序方式存储C．按关键字值的比较进行查找D．基于二分查找的方法12．算法的时间复杂度与（）有关。

A．所使用的计算机B．与计算机的操作系统C．与算法本身D．与数据结构13．对n个元素进行冒泡排序若某趟冒泡中只进行了（）次元素间的交换，则表明序列已经排好序。

A．1B．2C．0D．n-114．设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（）。

国家开放大学最新《数据结构（本）》期末综合练习（填空题）测验答案解析试题1满分1.00未标记标记试题试题正文对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。

该矩阵A有回答列。

反馈正确答案是：10试题2满分1.00未标记标记试题试题正文结构中的数据元素存在多对多的关系称为回答结构。

反馈正确答案是：图状试题3满分1.00未标记标记试题试题正文在单向链表中，q指向p所指结点的直接后继结点，要删除q所指结点，可以用操作回答= q->next;。

反馈正确答案是：p->next;试题4满分1.00未标记标记试题试题正文n个元素进行冒泡法排序，第j趟冒泡要进行回答次元素间的比较。

反馈正确答案是：n-j试题5满分1.00未标记标记试题试题正文对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和回答三项信息。

反馈正确答案是：数组元素试题6未标记标记试题试题正文中序遍历回答树可得到一个有序序列。

反馈正确答案是：二叉排序树试题7满分1.00未标记标记试题试题正文队列的操作特点是后进回答。

反馈正确答案是：后出试题8满分1.00未标记标记试题试题正文待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后，结果序列为回答。

反馈正确答案是：1，2，4，8，3，5，9满分1.00未标记标记试题试题正文n个元素进行冒泡法排序，通常需要进行回答趟冒泡。

反馈正确答案是：n-1试题10满分1.00未标记标记试题试题正文广义表（（a，b），d，e（（i，j），k））的长度是回答。

反馈正确答案是：4试题11满分1.00未标记标记试题试题正文中序遍历二叉排序树可得到一个回答的序列。

反馈正确答案是：有序试题12满分1.00未标记标记试题试题正文广义表的（c，a，（a，b），d，e，（（i，j），k））深度是回答。

数据结构（本）期末综合练习综合练习一一、单项选择题1．设有头指针为head的带有头结点的非空单向循环链表, 指针p指向其尾结点, 要删除头结点,并使其仍为单向循环链表,则可利用下述语句head =head->next ;（）。

A．p =head; B．p=NULL; C．p->next =head; D．head=p;2．在一个单链表中p指向结点a, q指向结点a的直接后继结点b，要删除结点b，可执行（）。

A．p->next=q->next ; B．p=q->next;C．p->next=q; D．p->next=q;3. 以下说法不正确的是A. 线性表的链式存储结构不必占用连续的存储空间B．一种逻辑结构只能有唯一的存储结构C. 一种逻辑结构可以有不同的存储结构D．线性表的顺序存储结构必须占用连续的存储空间4．在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行（）;和p->next=s;A．p= s; B． p->next=s->next;C．p=s->next; D． s->next=p->next;5．把数据存储到计算机中，并具体体现( )称为物理结构。

A. 数据元素间的逻辑关系B．数据的处理方法C．数据的性质D．数据的运算6．设有一个长度为23的顺序表，要删除第8个元素需移动元素的个数为（）。

A．16 B．14 C．15 D．137．链表所具备的特点之一是（）。

A．可以随机访问任一结点 B．需要占用连续的存储空间C．插入元素的操作不需要移动元素 D．删除元素的操作需要移动元素8．设一棵有8个叶结点的二叉树，度数为1的结点有3个,则该树共有（）个结点。

A．20 B．18 C．17 D．169．图状结构中数据元素的位置之间存在（）的关系。

A．一对一 B．多对多C．一对多 D．每一个元素都有一个直接前驱和一个直接后继10．一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。

数据结构（本科）期末综合练习一（单选题）单选题1.一个数组元素a[i] 与( )的表示等价。

A.*(a+i)B.a+iC.*a+iD.&a+i2.若需要利用形参直接访问实参，则应把形参变量说明为( )参数。

A.指针B.引用C.传值D.常值3.下面程序段的时间复杂度为( )。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)4.执行下面程序段时，执行S语句的次数为( )。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++) S;A.n2B.n2/2C.n(n+1)D.n(n+1)/25.下面算法的时间复杂度为( )。

int f(unsigned int n) {if(n==0 || n==1) return 1;else return n*f (n-1);}A.O(1)B.O(n)C.O(n2)D.O(n!)6.一种抽象数据类型包括数据和( )两个部分。

A.数据类型B.操作C.数据抽象D.类型说明7.当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( )，以节省参数值的传输时间和存储参数的空间。

A.基本类型B.引用型C.指针型D.常值引用型8.当需要进行标准I/O操作时，则应在程序文件中包含iostream.h头文件，当需要进行文件I/O 操作时，则应在程序文件中包含( )头文件。

A.fstream.hB.stdlib.hC.iomanip.hD.string.h9.一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为( )。

A.所有域长度之和B.最大域所占字节长度C.任意一个域长度D.sizeof(r)的值10.输出一个二维数组b[m][n]中所有元素值的时间复杂度为( )。

1.数据的物理结构（D ）。

A •与数据的逻辑结构无关C.只包括数据元素间关系的表示B .仅仅包括数据元素的表示D .包括数据元素的表示和关系的表示D•至少有一个数据项为指针类型3.从n个数中选取最大元素，（CA •基本操作是数据元素间的交换C •算法的时间复杂度是0（n）4.线性表的顺序结构中，（C ））。

B •算法的时间复杂度是0（n2）D .需要进行（n+1）次数据元素间的比较D .顺序表B ）（设头指针为head）oB. head->next= =NULLD . head!=NULL数据结构（本）期末综合练习期末综合练习一、单项选择题2•数据元素是数据的基本单位，它（ C ）A•只能有一个数据项组成B•至少有二个数据项组成C•可以是一个数据项也可以由若干个数据项组成A •逻辑上相邻的元素在物理位置上不一定相邻B •数据元素是不能随机访问的C .逻辑上相邻的元素在物理位置上也相邻D •进行数据元素的插入、删除效率较高5 •以下表中可以随机访问的是（ D ）oA .单向链表B .双向链表C •单向循环链表6.带头结点的单向链表为空的判断条件是（A . head = =NULLC. head->next= =head7.设顺序存储的线性表长度为n,对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（A ）A . （n+1）/2B . n C. 2n D . n-i8.线性结构中数据元素的位置之间存在（ A ）的关系。

A . 一对一B . 一对多C .多对多D .每一个元素都有一个直接前驱和一个直接后继9.设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收栈顶元素，则岀栈操作为（A ）oA . x=top->data;top=top->next;B . top=top->next;x=top->data;C . x=top-> next;top=top-> data;D . top->next =top; x=top->data;10 .设顺序存储的线性表长度为n,要删除第i个元素，按课本的算法，当i= （ C ）时，移动元素的次数为3A . 3B . n/2C . n-3D . 411.以下说法正确的是（ C ）oA .队列是后进先出B .栈的特点是后进后岀C .栈的删除和插入操作都只能在栈顶进行14 . 一个栈的进栈序列是 a ，b ，c ，d ,则栈的不可能的出栈序列是（ AA. adbc B . bead C . ebadD . deba15 .设有一个12阶的对称矩阵（矩阵A 的第一个元素为 A ，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组印,1，数组b 的下标从1开始）,则矩阵b 中A 中第4行的元素在数组b 中的下A . 7< i < 10B . 11< i < 15C . 9< i < 14A . 2mC . 2m+1D . m/217 .设有一个带头结点的链队列，队列中每个结点由一个数据域data 和指针域next 组成，front 和rear 分别为链队列的头指针和尾指针，要执行出队操作，用 x 保存出队元素的值，p 为指向结点类型的指针，可执行如下操作： p=front->next;x=p->data;然后执行（B18.A . front=p->next; C front=p;以下说法不正确的是( D )°B . front->next=p->next; D . front->next =p; 19. 20. A .连通图 B .连通图C .连通图 G 一定存在生成树 G 的生成树中一定包含 G 的所有顶点G 的生成树中不一定包含 G 的所有边 G 的生成树可以是不连通的D .连通图散列查找的原理是（AA .在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系B .按待查记录的关键字有序的顺序方式存储C .按关键字值的比较进行查找D .基于二分查找的方法 空串的长度为（ A ）°B . 1C . 221 .排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序 列的适当位置，直到全部排好序为止，该排序算法是 （D ） °A .选择排序 C .冒泡排序B .快速排序 D .直接插入排序22 .采用顺序查找法对长度为 n 的线性表进行查找（不采用表尾设监视哨的方法），最坏的情况下要进行（B ）次元素间的比较。

国家开放大学电大本科《数据结构》期末试题及答案
_1252数据结构电大
本科
一、单项选择题（每题10分，共70分）
1.下列以十进制表示的数值中，最高位为符号位的是（A）
A.-256
B.+256
C.-1024
D.+1024
2.下列关于基本排序法的描述中正确的是（D）
A.插入排序法是一种稳定排序法
B.选择排序法最坏的情况下时间复杂度为O（n2）
C.冒泡排序法最坏的情况下可以达到线性排序的时间复杂度
D.冒泡排序法和快速排序法均是不稳定的排序法
3.一个二叉树中，若结点的右孩子为空，则（C）
A.该结点一定是叶结点
B.该结点一定是树根
C.该结点的左孩子一定不为空
D.该结点的父结点一定不为空
4.已知关键字序列5，2，7，8，4，1，采用二叉树构造技术，构造出的二叉排序树中，根结点关键字为（A）
A.5
B.2
C.4
D.6
5.二叉树若当前结点的右孩子为空，则（B）
A.其后继结点为当前结点的父结点
B.其后继结点为当前结点的左孩子
C.其后继结点为当前结点的右孩子
D.其后继结点不存在
6.关于顺序存储结构，下列描述中不正确的是（B）。

数据结构（本科）期末综合练习（算法设计题）DOC1.设有一个线性表(e0,e1,,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。

请编写一个函数将这个线性表原地逆置，即将数组的前n个元素内容置换为(en-1,en-2,,e1,e0)。

函数的原型为：templatevoidinvere(TypeA[],intn);2.试编写一个函数，在一个顺序表A中找出具有最大值和最小值的整数。

函数的原型如下所示，原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Ma某中得到表中的最大整数，Min中得到表中的最小整数。

注意，函数中可使用顺序表的两个公有函数：Length()求表的长度；getData(intk)提取第k个元素的值。

#include“SeqLit.h”templatevoidFindMa某Min(SeqLit&A,int&Ma某,int&Min);3.设有两个整数类型的顺序表A（有m个元素）和B（有n个元素），其元素均以升序排列。

试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以升序排列（表中允许元素重复）。

函数的原型如下所示。

原型中的参数表给出参加运算的三个顺序表A、B与C。

从C中得到执行结果。

函数中用到顺序表的4个公有函数：Length()求表的当前长度；ma某Length()求表的最大允许长度；getData(intk)提取第k个元素的值；etData(intk,intval)修改第k个元素的值为val。

templatevoidmerge(SeqLit&A,SeqLit&B,SeqLit&C);4.编写一个函数frequency，统计在一个输入字符串中各个不同字符出现的频度。

函数返回两个数组：A[]记录字符串中有多少种不同的字符，C[]记录每一种字符的出现次数。

此外，还要通过整数k返回不同字符数。