《数据结构》第06章在线测试

数据结构章节测验数据结构第一章测验一、单选题 (共100.00分)1.在数据结构概念中, 数据的基本单位是（）A.数据段B.数据项C.数据表D.数据元素正确答案:D2.在数据结构概念中, 结构是描述（）A.数据项的类型B.数据元素之间的关系C.数据成员的先后顺序D.数据对象的取值范围正确答案:B3.在算法设计中, 要求算法便于理解和修改是属于算法要求的（）A.正确性B.可读性C.健壮性D.效率高正确答案:B4.抽象数据类型ADT通过三方面描述, 包括数据对象、数据操作和（）A.数据范围B.数据判断C.数据关系D.数据来源正确答案:C5.以下关于算法的描述, 哪个是正确的（）A.算法可以没有输入B.算法可以包含无限个执行步骤C.算法可以没有输出D.算法的每个步骤允许带有歧义的正确答案:A6.在算法设计中, 要求算法满足具体问题的需求是属于算法要求的（）A.正确性B.可读性C.健壮性D.效率高正确答案:A7.抽象数据类型ADT通过三方面描述, 包括数据关系、数据操作和（）A.数据对象B.数据来源C.数据范围D.数据判断正确答案:A8.以下关于数据结构的描述, 哪一个是正确的（）A.数据原子是数据的最小独立单位B.数据元素是数据的最小独立单位C.一个数据项可以包含若干个数据元素D.不能被计算机程序识别和处理的信息集合，不能称为数据正确答案:D9.设n为问题规模, 以下程序的时间复杂度为（...fo. (i=1.i<=10000.i++...fo.(j=1.j<=n.j++.........1;A.O(1)B.O(n)C.O(10000n)D.O(n2)正确答案:B10.设n为问题规模, 以下程序的时间复杂度为（.. fo.(i=1.i.POW（2.n）.i++.//POW(x.y)函数表示x的y次...a+100;A.O(n)B.O(2n)C.O(n!)D.O(2n)正确答案:D数据结构第二章测验一、单选题 (共100.00分)1.以下结构中, 哪一个是属于逻辑结构（）A.线性表B.顺序表C.单链表D.循环链表正确答案:A2.已知顺序表包含1000个数据, 现在第88号位置插入新的数据, 需要移动的数据个数为（）A.88B.87C.912D.913正确答案:D3.若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是（）A.单链表B.双链表C.单循环链表D.顺序表正确答案:D4.以下结构中, 哪一个是属于物理结构（）A.线性表B. 栈C.单链表D.队列正确答案:C5.已知顺序表包含100个数据, 现在要删除第99号位置的数据, 需要移动的数据个数为（）A.99B.100C. 1D. 2正确答案:C6.已知指针p指向单链表L的某个结点, 判断p指向的结点是尾结点的条件是（）A.i.(p->next>p)B.i.(p->next==NULL)C.i.(p->nextD.i.(p->data==0)正确答案:B7.以下描述哪个是正确的（）A.线性表的数据元素的存储位置一定是连续的B.顺序表的数据元素的存储位置一定是连续的C.链表的数据元素的存储位置一定不是连续的D.线性表的数据元素的存储位置一定不是连续的正确答案:B8.已知顺序表包含100个数据, 先在第15号位置插入1个新数据, 接着删除第3号位置的数据, 需要移动的数据总个数为（）A.18B.84C.184D.188正确答案:C9.设某单链表包含10个结点, 已知指针p指向第3个结点, 指针q指向第4个结点, 删除第4个结点的语句为（）A.p->nex..q->next.free(q);B.q->nex..p.free(p);C...q->next.free(p);D...p->next.free(q);正确答案:A10.设某单链表包含10个结点, 已知指针s指向一个新结点, 指针p指向第4个结点, 现在第4个结点之后插入这个新结点的两个语句为（）A.p->nex..s.s->nex..p->next;B.s->nex..p->next.p->nex..s;C.p->nex..s->next.s->nex..p;D.s->nex..p.p->nex..s->next;正确答案:B数据结构第三章测验一、单选题 (共100.00分)1.以下结构中, 哪一个是属于逻辑结构（）A.顺序栈B.链栈C.队列D.循环队列正确答案:C2.已知栈S为空, 数据1.2.3.4依次逐个进入栈S, 则栈顶数据为（）A. 1B. 2C. 3D. 4正确答案:D3.已知队列为空, 数据1.2.3.4依次逐个进入队列, 则出队的数据顺序为（）A.1234B.4321C.1324D.2413正确答案:A4.栈的最大特点是（）A.先进先出B.后进先出C.无限递归D.有限递归正确答案:B5.队列的最大特点是（）A.先进先出B.后进先出C.无限递归D.有限递归正确答案:A6.已知栈包含10元素, 其中存放在栈底是第1号元素, 则第10号元素可以通过（）进行访问A.栈底B.栈中C.栈尾D.栈顶正确答案:D7.以下描述正确的是（）A.顺序栈可以直接访问栈内任意位置的元素, 而链栈不可以B.链栈可以直接访问栈内任意位置的元素, 而顺序栈不可以C.通过栈可以实现程序的递归算法D.通过队列可以实现程序的递归算法正确答案:C8.以下结构中, 哪一个是属于物理结构（）A. 栈B.队列C.链队列D.线性表正确答案:C9.使用长度为10的数组实现循环队列, 则该队列最多存储数据个数为（）A. 1B. 9C.11.D.5正确答案:B10.在队列中, 允许插入的一端称为（）A.队头B.队中C.队指针D.队尾正确答案:D数据结构第四章测验一、单选题 (共100.00分)1.以下结构中, 哪一个是属于逻辑结构（）A.顺序表B.链栈C.循环队列D. 串正确答案:D2.以下哪一种是串在计算机中的常见表示方式（）A.定长顺序B.堆分配C.块链D.前三种都是正确答案:D3.在数据结构中, 串可以等同于（）的处理A.整数串B.浮点数串C.字符串D.多种类型的数组正确答案:C4.以下哪一种是串匹配的常用算法（）A.普里姆算法B.克鲁斯卡尔算法C.KMP算法D.关键路径算法正确答案:C5.已知主串为abcbcaddabc, 模式串为cad, 假设串位置从1开始, 则串匹配位置是（）A. 3B. 5C. 7D.不存在正确答案:B6.已知模式串为abaab, 则next数组为（）A.1122B.22312C.1212D.1112正确答案:A7.已知串S的内容为1+2+3, 以下描述哪一个是正确的（）A.串S的长度是6B.串S的运算结果是6C.整数1是串S的子串D.符号+是串S的子串正确答案:D8.以下描述哪一个是正确的（）A.串是字符有限序列B.串是整数、浮点数、字符等多种数据的有限序列C.只包含空格的串称为空串D.串只能使用顺序表存储正确答案:A9.串的长度是指（）A.串中包含不同字母的个数B.串中所含字符的个数C.串中包含不同字符的个数D.串中包含非空格的字符的个数正确答案:B10.串函数Sub(S.x.y)表示在串S中, 从x位置开始, 取出y个字符, 串位置从1开始计算。

自测题（6-10章）一、填空题1、二叉树第i(i>=1)层上至多有______个结点，深度为k(k>=1)的二叉树至多有______个结点。

2、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

3、满二叉树上各层的节点数已达到了二叉树可以容纳的______，满二叉树也是______二叉树，但反之不然。

4、具有n个结点的完全二叉树的深度为______。

5、具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。

6、二叉树有不同的链式存储结构，其中最常用的是________与________。

7、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。

8、由________转换成二叉树时，其根结点的右子树总是空的。

9、哈夫曼树是带权路径长度________的树，通常权值较大的结点离根________。

10、有m个叶子结点的哈夫曼树，其结点总数为________。

11、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有________个叶子结点。

12、具有10个顶点的无向图，边的总数最多为________。

13、N个顶点的连通图的生成树含有________条边。

14、无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。

15、一个具有n个顶点的完全无向图的边数为________，一个具有n个顶点的完全有向图的弧数为________。

16、遍历图的基本方法有________优先搜索和________优先搜索两种。

17、在有向图的邻接矩阵上，由第i行可得到第________个结点的________，而由第j列可得到第________个结点的________。

18、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素________比较大小。

删除40 删除70 删除60struct node { int data;struct node *lchild, *rchild;};typedef struct node NODE;NODE *create_tree(a,i,j)int a[ ],i,j;{NODE *p;int k;if(i>j) return(NULL);k=(i+j)/2;p=(NODE *)malloc(sizeof(NODE));p->data=a[k];p->lchild=create_tree(a,i,k-1);p->rchild=create_tree(a,k+1,j);return(p);}6. 3int check(root)NODE *root;{int x;if(root==NULL)return(0);if(root->data<root->rchild->data&&root->data>root->lchild->data) {x=check(root->rchild);if(!x) return(check(root->lchild));}return(1);}6. 4int height(root)NODE *root;{int h,k;if(root==NULL)return(-1);else if(root->lchild==NULL&&root->rchild==NULL)return(0);elseh=height(root->lchild);k=height(root->rchild);if(h>k)return(h+1);elsereturn(k+1);}}6. 5#include “math.h”int check_beltree(root)NODE *root;{int a;if(root==NULL)return(1);if(check_beltree(root->lchild)==0||check_beltree(root->rchild)==0) return(0);a=abs(height(root->rchild)-height(root->lchild)); //上题函数if(a<=1)return(1);}6．76．8结点k1 k2 k3 k4 k5结点值10 30 50 70 90相对使用频率（pi）p1 p2 p3 p4 p55 6 3 7 4外部结点使用频率(qi) q0 q1 q2 q3 q4 q54 2 1 2 3 4 本题的分析与计算，请参考“习题6.8”（Excel表），最后结果为：。

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。

表示该遗传关系最适合的数据结构为( )。

A.向量B.树 C图 D.二叉树2．树最合适用来表示( )。

A.有序数据元素 B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。

A. la (2b (3d,3e),2c)B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。

A. 2h_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。

A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。

A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。

A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。

A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。

..专业知识编辑整理..10.在题图6-2所示的二叉树中：(1)A结点是A.叶结点 B根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点 B．根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.4..专业知识编辑整理..11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。

数据结构第六章图练习题及答案详细解析（精华版）第一篇：数据结构第六章图练习题及答案详细解析(精华版) 图1.填空题⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵ 任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶ 图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

数据结构答案第6章第6章数据结构答案1. 栈的应用栈是一种常见的数据结构，其特点是先进后出。

下面是一些关于栈的应用场景。

1.1 函数调用栈在程序中，每当一个函数被调用时，相关的变量和状态信息会被存储在一个称为函数调用栈的栈中。

1.2 表达式求值栈也常用于表达式求值，特别是中缀表达式转后缀表达式的过程中。

通过使用栈，我们可以很方便地进行算术运算。

1.3 逆序输出如果我们需要逆序输出一段文本、字符串或者其他数据，可以使用栈来实现。

将数据依次压入栈中，然后再逐个弹出即可。

2. 队列的实现与应用队列是另一种常见的数据结构，其特点是先进先出。

下面是一些关于队列的实现和应用。

2.1 数组实现队列队列可以使用数组来实现。

我们可以使用两个指针分别指向队列的前端和后端，通过移动指针来实现入队和出队的操作。

2.2 链表实现队列队列还可以使用链表来实现。

我们可以使用一个指针指向队列的头部，并在尾部添加新元素。

通过移动指针来实现出队操作。

2.3 广度优先搜索（BFS）队列常用于广度优先搜索算法。

在BFS中，我们需要按照层级来访问节点。

使用队列可以帮助我们按照顺序存储和访问节点。

3. 树的遍历和应用树是一种非常重要的数据结构，在计算机科学中应用广泛。

下面是一些关于树的遍历和应用的介绍。

3.1 深度优先搜索（DFS）深度优先搜索是树的一种遍历方式。

通过递归或者使用栈的方式，可以按照深度优先的顺序遍历树的所有节点。

3.2 广度优先搜索（BFS）广度优先搜索也可以用于树的遍历。

通过使用队列来保存要访问的节点，可以按照层级的顺序遍历树。

3.3 二叉搜索树二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于左子树中的值，小于右子树中的值。

这种结构可以用于高效地进行数据查找。

4. 图的表示与遍历图是由节点和边组成的一种数据结构。

下面是一些关于图的表示和遍历的说明。

4.1 邻接矩阵表示法邻接矩阵是一种常见的图的表示方法。

使用一个二维数组来表示节点之间的连接关系。

《数据结构》在线测试题、单选题（共40 道试题，共80 分。

）1. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。

A. O(n) O(n)B. O(n) O(1)C. O(1) O(n)D. O(1) O(1)满分：2 分2. n个结点的线索二叉树上含有的线索数为（）A. 2nB. n－lC. n＋lD. n满分：2 分3. 下面关于算法说法错误的是（）A. 算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的满分：2 分4. 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。

A. 直接插入B. 直接选择C. 堆D. 快速满分：2 分5. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。

Head(Tail(Head(Tail(Tail(A)))))A. （a）B. AC. aD.d满分：2 分6. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

A. p->next=s;s->next=p->next;B. s->next=p->next;p->next=s;C. p->next=s;p->next=s->next;D. p->next=s->next;p->next=s;满分：2 分7. 关键路径是事件结点网络中（）。

A. 从源点到汇点的最长路径B. 从源点到汇点的最短路径C. 最长回路D. 最短回路满分：2 分8. 具有10个叶结点的二叉树中有（）个度为2的结点，A. 8B. 9C. 10D. ll满分：2 分9. 下列排序算法中，占用辅助空间最多的是：( )A. 归并排序B. 快速排序C. 希尔排序D. 堆排序满分：2 分10. 下述文件中适合于磁带存储的是（）。

数据结构第六章测验一、单选题 (共100.00分)1. 树的存储结构不包括（）A. 祖先表示法B. 双亲表示法C. 孩子表示法D. 孩子兄弟表示法正确答案：A2. 二叉树的深度为8，则该二叉树最多有（）个结点A. 15B. 16C. 255D. 256正确答案：C3. 已知二叉树有11个结点，其中4个结点是有一个孩子，叶子有（）个A. 4B. 5C. 6D. 3正确答案：A4. 已知A是二叉树根结点，B、C分别是A的左右孩子，D是B的左孩子，E是C的右孩子，F是D的右孩子，则该二叉树的中序遍历序列是（）A. FDBECAB. DFBACEC. ABDFCED. ABCDEF正确答案：B5. 赫夫曼树是指（）A. 路径长度最大的树B. 路径长度和最小的树C. 带权路径长度和最大的二叉树D. 带权路径长度和最小的二叉树正确答案：D6. 为了避免重复遍历在二叉树中保存前驱后继信息，这种二叉树称为（）A. 遍历二叉树B. 完全二叉树C. 满二叉树D. 线索二叉树正确答案：D7. 已知一棵完全二叉树有20个结点，从1开始按层次遍历编号，则结点8的孩子编号是（）A. 左孩子编号4，右孩子编号5B. 左孩子编号9，右孩子编号10C. 左孩子编号16，右孩子编号17D. 左孩子编号20，右孩子不存在正确答案：C8. 在二叉树中C是D的右孩子，在先序遍历序列中C在D的（）A. 前面B. 后面C. 不好说D. 并列正确答案：B9. 二叉树的第4层最多有（）个结点A. 4B. 6C. 8D. 16正确答案：C10. 二叉树的中序遍历序列中，结点P排在结点Q之前的条件是（）A. 在二叉树中P在Q的左边B. 在二叉树中P在Q的右边C. 在二叉树中P是Q的祖先D. 在二叉树中P是Q的子孙正确答案：A。