智慧树知到《算法与数据结构》章节测试答案文档格式.docx

1、8、描述非数值计算问题的数学模型不再是数学方程，而是数据结构（ ）。表树图集合表,树,图,集合9、 数据结构是一门研究（ ）程序设计问题中计算机的（ ）以及它们之间的（ ）和（ ）等的学科。非数值计算操作对象操作非数值计算,操作对象,关系,操作10、 顺序存储结构: 借助元素在存储器中的（ ）来表示数据元素间的逻辑关系。地址相对位置数值第一章1、（）是一种最简单的线性结构。线性表2、（ ）线性表的数据元素可以由所描述对象的各种特征的数据项组成。有序存储散列存储链式存储顺序存储3、已知单向链表中指针p指向结点A，（ ）表示删除A的后继结点（若存在）的链操作（不考虑回收）。p-next=pp=p-

2、nextnext-next=p-4、已知last指向单向简单链表的尾结点，将s所指结点加在表尾，不正确的操作是。s-next=NULL, last-next=s,last=s;next=s, s=last;last-next=s,s-next=NULL,last=s;next=s,last=s,last-next=NULL;5、已知h是指向单向加头链表的首指针，删除表头结点的操作是_。p=h-next;free（p）;h=h-free（h-next）;p=h,h=p-next,h-6、有N个元素组成的线性表，我们说此线性表的长度为（ ）nn+1n-17、对线性表中的数据元素进行（ ）和（ ）等

3、操作，实现表的长度的增长或缩短。插入遍历访问删除插入,删除8、线性表的抽象数据类型定义数据对象函数关系数据关系基本操作数据对象,数据关系,基本操作9、我们使用（ ），实现线性表的顺序存储。函数数组10、线性表的基本操作是用C语言中的（ ）对其进行表示的。循环语句结构体条件语句11、 在链表中第i 个结点之前插入新的元素 e ，表的逻辑结构不变。12、在单链表中插入结点只需要（）。但同时，若要在第（ ）个结点之前插入元素，修改的是第 （ ）个结点的指针。 i修改指针i+1i-1i ,修改指针,i-113、单链表和线性表中所有基本操作相同，且编程实现方法相同。14、数字钟程序中使用的时间，可以是系

4、统时间。15、和单链表的差别仅在于，判别链表中最后一个结点的条件不再是（ ），而是（ ）。后继是否为头结点前继是否为头结点前继是否为空后继是否为空,16、双向链表的删除 时需要同时修改两个方向上的指针,改变结点之间的逻辑关系。17、双向链表的插入 时不需要同时修改两个方向上的指针,改变结点之间的逻辑关系。18、 双向链表中，当指针p指向非空表中的非头尾结点时，以下哪个式子是正确的（）prior=pnext =p-priorprior-prior=p ,p=p-19、 双向链表中，当指针p指向非空表中的非头尾结点时，以下哪个式子是正确的（）next=p -prior=p-20、 双向链表需要在结

5、点中设两个指针域（ ）parent指针域prior指针域数据域next指针域prior指针域,next指针域第二章1、队列是一种（ ）的线性表。先进先出先进后出只能插入只能删除2、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。 front-next=s；front=s； s-next=rear；rear=s； rear-next=front；rear-3、栈操作数据的原则是（ ）。后进先出后进后出不分顺序4、栈与队列是一种特殊操作的线性表（ ）5、和链栈类似，用单链表来实现链队。根据队的先入先出

6、（FIFO）原则，为了操作上的方便，使用一个（ ）和（ ）。头指针尾指针指针域头指针,尾指针6、队列的顺序存储结构用C语言中（ ）数据类型实现。一维数组实现二维数组实现枚举型7、栈和队列不能进行再分配了。8、队列允许在表的一端进行插入操作和删除操作。9、入栈需要修改地址指针。10、 链栈主要的运算，如插入、删除是在栈顶执行的。 链表的头部作栈顶是最方便的，需要像单链表那样为了运算方便附加一个头结点。11、链栈的结点结构与单链表的结点结构相同，由（）和（）组成。指针域 双亲域数据域 指针域孩子域 指针域双亲域12、 构造一个空栈S 时，不需要用动态存储空间分配函数。13、顺序栈中数据元素与栈顶指

7、针的变化：非空栈中的栈顶指针top始终在的 （）下一个位置栈中任意元素栈顶元素栈底元素栈中元素14、在初始化空顺序栈时一般不限定栈的最大容量，因为，栈在使用过程中所需最大空间的大小很难估计。15、利用（）的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈称为顺序栈。一组地址相同一组地址不连续一组地址连续一组地址断开第三章1、串（即字符串）是一种特殊的线性表，它的数据元素是（ ）。数字单个字符B2、包含零个字符（n=0）的串称为空串，通常记为，其长度为零；空串是任意串的子串。A3、空串与空格串相同4、串比较是按字符的ASCII值比较的，而不是按串的长度比较的。 StrCompare（data

8、, structures） _ 0；大于等于小于小于等于C5、SubString（ sub, commander, 1, 9） 求得 sub = _；commanrcoandercommandercomander C6、串的基本操作中，操作对象大多为串的整体。7、在串的表示和实现过程中，用一组地址不连续的存储单元存储串值中的字符序列，称为串的定长顺序存储方式。8、在顺序串中，用一个指针来指向最后一个字符，C语言的表示如下：typedef struct char dataMAXSIZE; int curlen; SeqString;请定义一个串变量： structg stypedef struc

9、t s；SqString s；SeqString s；D9、在C语言中，存在一个称为堆的自由存储区，并由C语言的动态分配函数_来管理。malloc（ ）malloc（ ）和free（ ）free（ ）main（）10、堆分配存储结构的串有顺序存储结构的特点，在操作中对串长又没有任何限制，因而在串处理的应用程序中常被选用。第四章1、设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。 2i+1 2i i/22i-12、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。空或只有一个结点高度等于其结点数任一结点无左孩子任

10、一结点无右孩子3、二叉树的第k层的结点数最多为（ ）2的k次幂-12K+12K-12的k-1次幂4、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。BADCBCDACDABCBDA5、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）6、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。7、深度为k的完全二叉树中最少有（ ）个结点。 2k-1-1 2k-1+1 2k-18、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。N0=N1+1N0=Nl+N2N0=N

11、2+1N0=2N1+l9、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。 任一结点无左孩子10、 树的带权路径长度定义为，树中所有叶子结点的带权路径长度之和（对所有叶子结点）。（）第五章1、设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。2nn/2 n（n-1）2、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。第i行非0或非元素的个数之和第i列非0或非元素的个数之和第i行0元素的个数之和 第i列0元素的个数之和3、设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边n（n-1）/2n（n-1）n的2次幂n的2次幂-14、

12、 子串ABC在主串AABCABCD中的位置为2。5、 对链表进行插入和删除操作时不必移动链表中结点。6、深度为k的完全二叉树中最少有（ ）个结点。 2k-1-17、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。8、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。第i列0元素的个数之和9、简单回路就是回路。10、图中任两点有路径相通，该图称为连通图（）第六章1、时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（ ）。 堆排序 冒泡排序 希尔排序快速排序2、设一组权值集合W=2，3，4，5，6，则由该

13、权值集合构造的哈夫曼树中带权路径长度之和为（ ）。203040453、设一组权值集合W=2，3，4，5，6，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）4、 连通图的最小生成树的边上的权值之和是唯一的。5、设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。6、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。7、以数据集1，3，5，7为叶结点的权值，构造一棵哈夫曼树，求出带权路径长度WPL（）。2628298、设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边9、查找表可分为两类（）动态查找表顺序查找表静态查找表起泡查找表AC10、使用折半方法

14、进行查找的表是一个有序表。第七章1、执行一趟快速排序能够得到的序列是（ ）。 41，12，34，45，27 55 72，6345，34，12，41 55 72，63，27 63，12，34，45，27 55 41，7212，27，45，41 55 34，63，722、排序分稳定排序和不稳定排序。4、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。5、设一组初始记录关键字序列为（45，80，55，40，42，85），则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ ）。40，42，45，55，80，8342，40，45，80，85，8842，40，45，55，80，8542，

15、40，45，85，55，806、设一组初始记录关键字序列为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。15，25，35，50，20，40，80，85，36，7015，25，35，50，80，20，85，40，70，3615，25，35，50，80，85，20，36，40，7015，25，35，50，80，20，36，40，70，857、设一组初始记录关键字序列为（50，40，95，20，15，70，60，45），则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。 40，50，20，9515，40，60，2015，20，40，4545，40，15，208、执行一趟快速排序能够得到的序列是（ ）。41，12，34，45，27 55 72，6363，12，34，45，27 55 41，729、队列的顺序存储结构用C语言中（ ）数据类型实现。10、时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（ ）。