当前位置：文档之家 › 数据结构练习题

数据结构练习题

  • 格式：doc
  • 大小：213.00 KB
  • 文档页数：21

数据结构练习题一、单项选择1、组成数据的基本单位是（）。

A. 数据项B. 数据类型C. 数据元素D.数据变量2、线性表的链接实现有利于（）运算。

A. 插入B. 读表元素C. 查找D. 定位3、串的逻辑结构与（）的逻辑结构不同。

A. 线性表B. 栈C. 队列D. 树4、二叉树第i（i>=1）层上至多有（）结点。

A. 2iB. 2iC. 2i-1D. 2i-15、设单链表中指针P指着结点A ，若要删除A之后结点（若存在），则需要修改指针的操作为（）。

A. p->next=p->next->nextB. p=p->nextC. p=p->next->nextD. P->next=p6、设一数组的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（）。

A. 3,2,5,6,4,1B. 1,5,4,6,2,3C. 2,4,3,5,1,6D. 4,5,3,6,2,17、设字符串S1=‘ABCDEFG’，S2=‘PQRST’，则运算S=CONCAT（SUB（S1，2，LENGTH （S2），SUB（S1，LENGTH（S2），2））后结果为（）。

A. ’BCQR’B. ’BCDEF’C. ’BCDEFG’D. ’BCDEFEF’8、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（）。

A. 13B. 33C. 18D. 409、如果结点A有3个兄弟，而且B为A的双亲，则B的度为( )。

A. 3B. 4C. 5D. 110、线索化二叉树中某结点D，没有左孩子的主要条件是（）。

A. D->Lchild=NullB. D->ltag=lC. D->Rchild=NullD. D->ltag=011、下列数据结构中，( )不都是线性结构。

A.栈和队列B.队列和数组C.数组和串D.文件和队列12、为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。

A.顺序存储B.链式存储C.索引存储D.散列存储13、设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为( )A.s->t1->r1=s->t1;s->r1->t1=s->r1;B.s->t1->r1=s->r1;s->r1->t1=s->t1;C.s->r1=s->t1->r1;s->t1=s->r->t1;D.s->t1=s->t1->r1;s->r1=s->r->t1;14、假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( )A.q->right=s; s->left=q; q->right->left=s; s->right=q->right;B.s->left=q; q->right=s; q->right->left=s; s->right=q->right;C.s->left=q; s->right=q->right; q->right->left=s; q->right=s;D.以上都不对15、由下列三棵树组成转的森林换成一棵二叉树为( )16、具有100个结点的完全二叉树的深度为( )A.6B.7C.8D.917、已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)，则其转置矩阵的三元组表中第3个三元组为( ) A.(2，1，3) B.(3，1，5)C.(3，2，-1)D.(2，3，-1)18、无向图的邻接矩阵是一个( )A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵19、索引非顺序文件中的索引表是( )A.非稠密索引B.稠密索引C.主索引D.多级索引20、对n个记录的文件进行堆排序，最坏情况下的执行时间为( )A.O(log2n)B.O(nlog2n)C.O(n)D.O(n2)21、数据结构是研究数据的( )以及它们之间的相互关系。

A. 理想结构，物理结构B. 理想结构，抽象结构C. 物理结构，逻辑结构D. 抽象结构，逻辑结构22、线性表采用链式存储时，其地址( )。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续与否均可以23、串的逻辑结构与( )的逻辑结构不相同。

A. 线性表B. 栈C. 队列D. 查找表(集合)24、完成堆排序的全过程需要( )个纪录大小的辅助空间。

A. 1B. nC. nlog2nD. |nlog2n|25若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。

A. 10，15，14，18，20，36，40，21B. 10，15，14，18，20，40，36，21C. 10，15，14，20，18，40，36，21D. 15，10，14，18，20，36，40，2126、有一棵二叉树如下图，该树是( )。

A. 二叉平衡树B. 二叉排序树C. 堆的形状D. 以上都不是27、对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )，利用Kruskal时间复杂度为( )。

A. O(log2n)B. O(n2)C. O(ne)D. O(elog2e)28、n个顶点的强连通图至少有( )边。

A. nB. n+1C. n-1D. n(n-1)29、设有100个元素，用二分法查找时，最大比较次数是（），最小比较次数为（）。

A. 25B. 7C. 10D. 130、在内部排序中，排序时不稳定的是( )。

A. 插入排序B. 冒泡排序C. 快速排序D. 归并排序31、下列数据组织形式中，（）的结点按逻辑关系依次排列形成一个“锁链”。

A.集合B.树形结构C.线性结构D.图状结构32、数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（）A.S上的算法B.S的存储结构C.在S上的一个基本运算集D.在S上的所有数据元素33、下列说法正确的是（）A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算34、设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（）A.s->next=p->next;p->next=s；B.p->next=s;s->next=p->next；C.s->next=p->next;p->next=s;交换p->data和s->data；D.p=s;s->next=p；35、．稀疏矩阵一般采用（）方法压缩存储。

A.三维数组B.单链表C.三元组表D.散列表36、树若用双亲链表表示，则（）A.可容易地实现求双亲及子孙的运算B.求双亲及子孙的运算均较困难C.可容易地实现求双亲运算，但求子孙运算较困难D.可容易地实现求子孙运算，但求双亲运算较困难37、将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（）A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子38、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）A.完全图B.连通图C.有回路D.一棵树39、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。

这种方式主要适合于（）A.静态查找表B.动态查找表C.静态查找表与动态查找表D.两种表都不适合40、文件存储的基本单位是( )。

A.记录B.数据项C.属性D.关键字41、ADT表的数组实现的读表元算法的平均时间复杂度量级为( )。

A. O(n)B. O(nlog2n)C. O(1)D. O(n2)42、深度为k且为( )个结点的二叉树称为满二叉树(设根结点处于第1层)。

A. 2k-lB. 2kC. 2k-1D. 2k-143、对于下图V1的度为( )A. 1B. 2C. 3D. 444、中根遍历一棵二叉排序树所得到的结点访问序列是键值的( )序列。

A. 递增或递减B. 递减C. 递增D. 无序45、已知某图的邻接表如下：此邻接表所对应的无向图为( )。

A. B.C.46、 快速排序在( )情况下最不利于发挥其长处。

A. 被排序的数据量太大B. 被排序数据中含有多个相同的关键字C. 被排序的数据完全无序D. 被排序的数据已基本有序47、下列哪种排序需要的附加存储开销最大( )。

A. 快速排序B. 堆排序C. 插入排序D. 冒泡排序48、对任何一棵二叉树T ，设n 0，n 1，n 2分别是度数为0，1，2的结点数，则n 0=( )。

A. n 0=n 1+1B. n 0=-n 1+n 2C. n 0=n 2+lD. n 0=2n 1+149、折半查找过程可以用二叉树形象地说明，实际上这种方法是从二叉树的根结点开始到叶子的查找过程。

假设结点数为n ，深度为d ，则比较的次数不超过二叉树的深度d=( )A. |log 2n 」+1B. 「log 2n|-1C. |log 2n 」D. 「log 2n|50、组成数据的基本单位是( )。

A. 数据项B. 数据类型C. 数据元素D. 数据变量51、线性表的链接实现有利于( )运算。

A. 插入B. 读表元素C. 查找D. 定位52、串的逻辑结构与( )的逻辑结构不中。

A. 线性表B. 栈C. 队列D. 查找表53、Substr(‘DATASTRUCTURE’，5，9)=（）A. ‘STRUCTURE’B. ‘DATA’C. ‘ASTRUCTUR’D. ‘DATASTRUCTURE’54、下列哪种排序需要的附加存储开销最大。

( )A. 快速排序B. 堆排序C. 归并排序D.插入排序55、下列哪种排序算法是不稳定的。

( )A. 快速排序B. 冒泡排序C. 归并排序D. 直接插入排序56、设有1000个元素，用二分查找时，最大比较次数是（）。

合集下载

数据结构练习题

数据结构练习题

. . . . .一、单选题第1章绪论1、在数据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构C、线性结构和非线性结构2、算法分析的两个主要方面是A、空间复杂性和时间复杂性C、可读性和文档性3、数据的不可分割的最小单位是B、紧凑结构和非紧凑结构D、内部结构和外部结构B、正确性和简明性D、数据复杂性和程序复杂性A、结点B、数据元素C、数据项D、数据对象4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为A、规则B、集合C、结构D、运算5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是A、问题的规模C、机器执行速度二、判断题1、数据结构是带有结构的数据元素的集合。

2、程序越短，运行的时间就越少。

3、处理同一问题的算法是唯一的。

B、机器代码质量的优劣D、语句的执行次数4、一个完整算法可以没有输入，但必须有输出。

三、填空题1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

2、______________结构的数据元素之间存在一对多的关系。

3、数据结构的形式化定义为(D，S)，其中D 是______________的有限集，S 是 D 上关系的有限集。

4、数据结构在计算机中的______________称为存储结构。

5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此- 1 -得到两种不同的存储结构是______________存储结构和______________存储结构。

6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。

7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。

四、解答题1、设n 为正整数。

数据结构 练习题

数据结构 练习题

A）10 B）110 C）1110 D）1111
6. 已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是
A）E B）F C）G D）J
7. 设结点A有左孩子结点B，右孩子结点C，则在先序遍历、中序遍历、后序遍历这三种基本遍历序列中B一定是C的
图6-2 例6.3附图
6 自测习题
1. 简答题
1. *根据权值（1，2，3，4，5，6），构造哈夫曼树，并计算二叉树的带权路径长度。
2. 请
将下图6-1所示的森林转换成二叉树。
图6-1 简答题2的附图森林
3. *已知一棵二叉树的中序遍历序列为DHBEAIFCGJK，该二叉树的后序遍历序列是HDEBIFJKGCA，现请画出这棵二叉树。
第1章 概述
一、简答题
1．简述以下术语的含义并说明它们之间的关系。
数据类型、数据结构、逻辑结构、存储结构
2．简述算法时间效率和空间效率的概念。
3．简述数据结构课程的目的和意义。
二、选择题
1．以下数据结构中，逻辑结构属于线性结构的是
A）有向图 B）链式栈 C）二叉树 D）二叉排序树
四、算法及分析
1．写出交换两个整型变量值的算法，并分析算法的时间复杂度。
2．写出求n的阶乘 的算法，并分析算法的时间复杂度。
第2章 线性表
一、简答题
1．在处理某个问题时，需要存储的数据总量不能确定，并经常需要进行数据的添加和删除操作，此时应选用哪种存储结构？为什么？
3．设有结点定义
struct node
{ int data;
struct node *next;
数据结构练习题

数据结构练习题

一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它 们之间的 关系 和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D 上的 关系 有限集合。 3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方 面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构 。 5. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 系 ，图形结构中元素之间存在 多对多 关系。 6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前 驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点 。 7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱 结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以 任意多个 。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。 9．数据的存储结构可用2种基本的存储方法表示，它们分别是 顺序存储结构 和连式存储结构 。 10. 数据的运算最常用的有5种，它们分别是 检索、排序、插入、删除、修改 。 11. 一个算法的效率可分为 时间 效率和 空间 效率。
（ × ）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两 个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （ × ）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的 示意图有序。 （ × ）3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元 向前移动。错，链表的结点不会移动，只是指针内容改变。 （ × ）4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （ × ）5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （ × ）6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低， 在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （ × ）7.线性表在物理存储空间中也一定是连续的。 错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （ × ）8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相 邻。 （ × ）9.顺序存储方式只能用于存储线性结构。 错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于 非线性结构，但其最佳存储方式是顺序存储方式。 （ × ）10.线性表的逻辑顺序与存储顺序总是一致的。 错，理由同7。链式存储就无需一致。
数据结构练习附答案

数据结构练习附答案

一、单项选择题1.逻辑关系是指数据元素间的（）A．类型B．存储方式C．结构D．数据项2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A．顺序表 B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front=(front+1)%(m-1)C．front=(front-1)%m D．front=(front+1)%m4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。

A．rear％n==front B．(front+l)％n==rearC．rear％n-1==front D．(rear+l)％n==front5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。

A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。

( )A. 90B. 91C. 92D. 937.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。

A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。

A. nB. 2nC. n/2D. n*n9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。

A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法10.对线性表进行二分查找时，要求线性表必须( )。