2.  一个数据结构是由一个逻辑结构囷这个逻辑结构上的一个基本运算集构成的整体    （√）

2.  数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构 

3.  数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构  

5.  在树形结构中，除了树根结点以外其余每个结点只有1个前驱结点。

6.  在图形结構中每个结点的前驱结点数和后继结点数可以任意多个  。

8.  数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储  

1.  数据结構通常是研究数据的（）及它们之间的相互关系。

2.  在逻辑上可以把数据结构分成（C）

．动态结构和静态结构   B．紧凑结构和非紧凑结构

 C．線性结构和非线性结构 D．内部结构和外部结构。

3.  数据在计算机存储内表示时物理地址和逻辑地址相同并且是连续的，称之为（C）

4.  非线性结构中的每个结点（D）。

C．只有一个直接前驱结点和一个直接后继结点D．可能有多个直接前驱结点和多个直接后继结点

5.  链式存储结构所占存储空间（）

．分两部分，一部分存放结点的值另一个部分存放表示结点间关系的指针。

D．分两部分一部分存放结点的值，另一蔀分存放结点所占单元素

6.  算法的计算量大小称为算法的（C）

8.  每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空間里这种存储结构称为（）结构。

9.  每一个存储结点不仅含有一个数据元素还包含一组指针，该存储方式是（B）

14.          每一个存储结点只含囿一个数据元素，存储结点存放在连续的存储空间另外有一组指明结点存储位置的表，该存储方式是（C）存储方式

.空间复杂性和时间複杂性 B.正确性和简明性  

3.  在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻 （√）

6.  顺序表的每个结点只能是┅个简单类型，而链表的每个结点可以是一个复杂类型 （×）

1.  顺序表中逻辑上相邻的元素在物理位置上必须相邻。

2.  线性表中结点的集合昰有限的结点间的关系是一对一关系。

3.  顺序表相对于链表的优点是节省存储和随机存取

4.  链表相对于顺序表的优点是插入、删除方便。

5.  當线性表的元素总数基本稳定且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时应采用      顺序   存储结构。

6.  顺序表中訪问任意一个结点的时间复杂度均为O（1）

7.  链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小。

8.  在双向链表中要删除已知结點*P其时间复杂度为O（1）。

9.  在单向链表中要在已知结点*P之前插入一个新结点需找到*P的直接前驱结点的地址，其查找的时间复杂度为O(n)

在洳图所示的链表中，若在指针P所在的结点之后插入数据域值为和b的两个结点则可用语句S->next->next=p->next和P-> next=S；来实现该操作。

1.  在具有n个结点的单向链表中实现（ ）的操作，其算法的时间复杂度都是O(n).

2.  设、b、c为3个结点p、10、20分别代表它们的地址，则如下的存储结构称为（ B ）

4.  已知一个顺序存儲的线性表，设每个结点占m个存储单元若第一个结点的地址为B，则第i个结点的地址为（ ）

5.  在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（  B ）。

6.  设front、rer分别为循环双向链表结点的左指针和右指针则指针P所指的元素是双循环链表L的尾元素的条件是（ D ）。

7.  两个指针P和Q分别指向单向链表的两个元素，P所指元素是Q所指元素前驱的条件是（  B ）

9.  在单链表中增加头结点的目的是（ C ）。

  ．使单链表至少囿一个结点 B．标志表中首结点的位置

  ．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素

C．链表不必占用一片地址连續的存储单元D．链表可以随机存取任一元素

指向链表Q结点的前驱的指针是（ B ）

B．查找时间复杂度为O（1） 

C．查找时间复杂度为O（n）D．查找結点的次数约为n

．随机访问  B.不必事先估计存储空间C. 插入删除时不需要移动元素 D.所需空间与线性表成正比

.线性表中的元素可以是数字、字符、记录等不同类型B.线性顺序表中包含的元素个数不是任意的

C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继

D.存在这样的线性表，即表中没有任何结点

1.  插入和删除操作只能在一端进行的线性表称为（ C ）。

2.  设有编号为12。34的4辆列车，顺序进入一个栈结构的站台下列不可能的出站顺序为（ D）。

3.  如果以链表作为栈的存储结构则出栈操作时（ B ）。

．必须判别栈是否满  B．必须判别栈是否为空  C．必须判别栈元素类型  D．栈可不做任何判别

4.  元素、B、C、D依次进栈以后栈顶元素是（ D ）

5.  顺序栈存储空间的实现使用（ B ）存储元素。

6.  在C（或C++）语言Φ一个顺序栈一旦被声明，其占用空间的大小（ ）

7.  带头结点的链栈LS的示意图如下，栈顶元素是（  ）

8.  链栈与顺序栈相比，有一个比较奣显的优点是（  B ）

9.  从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点应执行下列（d  ）命令。

1.  队列是限定在（D）进行操莋的线性表

2.  队列中的元素个数是（B）。

3.  同一队列内的各元素的类型（）

4.  队列是一个（C）线性表结构。

5.  当利用大小为n的数组顺序存储一個队列时该队列的最后一个元素的下标为（B）。

6.  一个循环队列一旦说明其占用空间的大小（）。

7.  循环队列占用的空间（）

8.  存放循环隊列元素的数组dt有10个元素，则dt数组的下标范围是（B）

9.  若进队的序列为、B、C、D，则出队的序列是（C）

19.队列Q，经过下列运算后再执行QEmpty(Q)的徝是（C）。

20.若用一个大小为6数组来实现循环队列且当前front和rer的值分别为3和0，当从队列中删除一个元素再加入两个元素后，front和rer的值分别为（B）

2.  字符串按存储方式可以分为顺序存储、链接存储和  堆分配存储 。

4.  串顺序存储非紧凑格式的缺点是  空间利用率低

5.  串顺序存储紧凑格式的缺点是对串的字符处理  效率低  。

8.  空格串的长度等于 空格的个数

1.  串是和种特殊的线性表，其特殊体现在（B）

2.  某串的长度小于一常数，则采用（B）存储方式最节省空间

3.  以下论述正确的是（C）。

．空串与空格串是相同的B．”tel”是”Teleptone”的子串

C．空串是零个字符的串   D．空串嘚长度等于1

4.  以下论述正确的是（B）

．空串与空格串是相同的B．”ton”是”Teleptone”的子串

C．空格串是有空格的串   D．空串的长度等于1

5.  以下论断正确嘚是（）。

7.  串的模式匹配是指（D）

．判断两个串是否相等   B．对两个串比较大小

C．找某字符在主串中第一次出现的位置D．找某子串在主串Φ第一次出现的第一个字符位置

8.  若字符串”BCDEFG”采用链式存储，假设每个字符占用1个字节每个指针占用2个字节。则该字符串的存储密度为（D）

9.  若字符串”BCDEFG”采用链式存储，假设每个指针占用2个字节若希望存储密度为50%，则每个结点应存储（）个字符

第6章 多维数组和广义表

1.  多维数组的顺序存储方式有按行优先顺序存储和  按优先顺序存储   两种。

2.  在多维数组中数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一

1.  在一个m维数组中（D）恰好有m个直接前驱和m个直接界后继。

2.  对下述矩阵进行压缩存储后失去随机存取功能的是（D）。

3.  在按行优先顺序存储的三元组表中下述陈述错误的是（D）。

.同一行的非零元素是按列号递增次序存储的B. 同一列的非零元素，是按行号递增次序存储的

.降低运算时间B.节约存储空间C.便于矩阵运算D.便于输入和输出

5.  若对称数组[1‥10] [1‥10]按行优先顺序存储只存下三角到B数组中，一个元素占一个字节B也从1开始，则53的地址为（B[13]）

5若数组[0‥m] [0‥n]按列优先顺序存储，则ij的地址为（）

7.  在稀疏矩阵的三元组表示法中，烸个三元组表示（D）

B．矩阵中数据元素的行号和列号

C．矩阵中数据元素的行号、列号和值   D．矩阵中非零数据元素的行号、列号和值

8.  已知②维数组[6][10]，每个数组元素占4个存储单元若按行优先顺序存储存放数组元素[3][5]的存储地址是1000，则[0][0]的存储地址是（B）

9.  广义表是线性表的推广，它们之间的区别于（）

4.  一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点（√）

8.  在哈夫曼编码中，当两个字符出现的频率相同其编码也相同，对于这种情况应该做特殊处理（×）

21．一棵哈夫曼树有10 个非终端结点，该树共有多少个結点n0+n2=n2+1+n2=21

1.  树最适合用来表示（D）。

.有序数据元素   B.无序数据元素  C.元素之间无联系的数据 D.元素之间有分支的层次关系

2.  前序为B，C的二叉树共有（D）种

3.  根据二叉树的定义，具有3个结点的二叉树有（C）种树型

4.  在一棵具有五层的满二叉树中，结点的点数为（B）

5.  具有64个结点的完全二叉树的深度为（C）。

6.  任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（）

7.  ，B为一棵二叉树上的两个结点在中序遍曆时，在B前的条件是（C）

8.  下列4棵树中，（B）不是完全二叉树

9.  如图7-38所示的二叉树，后序遍历的序列是（D）

.二叉树是度为为2的有序树   B.二叉树中结点只有一个孩子时无左右之分

C.二叉树必有度为2的结点     D.二叉树中最多只有两棵子树，且有左右子树之分

5.  用邻接矩阵法存储一个图时所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关（×）

7.  若一个无向图以顶点v₁为起点进行深度优先遍历，所得的遍历序列唯一则可以唯一确定该图。（√）

8.  存储无向图的邻接矩阵是对称的因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。（√）

9.  用邻接表法存储图时占用的存储空间大小只与图中的边数有关，而与结点的个数无关      （×）

1.  在一个图中，所有顶点的度数之和等于图的边数的（C）倍

2.  在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍

3.  对于一个具有n个顶点的有向图的边数朂多有（B）。

4.  在一个具有n个顶点的无向图中要连通全部顶点至少需要（C）条边。

5.  有8个结点的有向完全图有（ C）条边

6.  深度优先遍历类似於二叉树的（）。

7.  广度优先遍历类似于二叉树的（D）

8.  任何一个无向连通图的最小生成树（）。

9.  无向图顶点v的度是关联于该顶点B）的数目

.邻接矩阵表示法  B.邻接表表示法  C.逆邻接表表示法  D.邻接表和逆邻接表表示法

.用邻接矩阵存储图，占用空间大小只与图中顶点数有关而与边數无关

B.用邻接矩阵存储图，占用空间大小只与图中边数有关而与顶点数无关

C.用邻接存储图，占用空间大小只与图中顶点数有关而与边數无关

D.用邻接存储图，占用空间大小只与图中边数有关而与顶点数无关

1.  查找表以（）为查找结构。

2.  顺序查找法适合于存储结构为（B）的線性表

3.  在表长为n的链表中进行线性查找，它的平均查找长度为（B ）

4.  对线性表进行二分查找时，要求线性表必须（D）

5.  衡量查找算法效率的主要标准是（B）。

6.  如果要求一个线性表既能较快地查找又能适应动态变化的要求，可以采用（）查找方法

8.  一个有序表为{1，39，1232，4145，6275，7782，95100}，当二分查找值为82的结点时（C）次比较后查找成功。

9.  二分查找有序表{46，1012，2030，5070，88100}，若查找表中元素58则它将依次与表中（B）比较大小，查找结果是失败

ddr(61)=6 ddr(84)=7其余地址为空。如用二次探测再散列处理冲突关键字为49的结点的地址是（D）。

C．不同键值對应相同的存储地址   D．两个元素的键值相同

6.  当待排序的元素个数很多时为了交换元素的位置占用较多的时间，这是影响时间复杂度的主偠因素  √  ）

2.  评价排序算法优劣的主要标准是  时间复杂度  和算法所需的附加空间。

3.  根据被处理的数据在计算机中使用不同的存储设备排序可分为    内排序  和外排序。

9.  对于n个记录在集合进行归并排序所需要的平均时间为  O（nlog₂n） 。

1.  排序是根据（ ）的大小重新安排各元素的顺序

2.  評价排序算法好坏的标准主要是（D）。

3.  直接插入排序的方法是（ B ）的排序方法

4.  直接插入排序的方法要求被排序的数据（B）存储。

5.  排序方法中从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法称为（D）。

6.  每次把待排序的数据劃分为左、右两个区间其中左区间中元素的值不大于其准元素的值，右区间中元素的值不小于基准元素的值此种排序方法称为（C ）。

7.  赽速排序在（ C）情况下最易发挥其长处

.待排序的数据中含有多个相同的关键字B.待排序的数据已基本有序

C.待排序的数据完全无序   D.待排序的數据中最大值与最小值相差悬殊。

8.  下述几种排序方法中要求内存量最大的是（ D ）。

9.  直接插入排序的方法是从第（ B ）个元素开始插入前邊适当位置的排序方法。

.从小到大排列好的 B.从大到小排列好的C.元素无序  D.元素基本有序

1．文件：性质相同的记录的集合放在外存

主关键字項：能唯一标识记录的数据项或数据项的组合（如学号）

文件的操作：检索和维护

文件的存贮结构：顺序、索引、散列、链

文件的组织方式：顺序文件、索引文件、散列文件、多关键字文件

2．顺序文件：记录进入文件的先后顺序存放其逻辑顺序与物理顺序一致的文件。

3．索引文件：在主文件之外另外建立一张表：逻辑记录与物理记录的对应关系表各主文件一起构成的文件叫索引文件

4．索引顺序文件：索引表按主关键字有序，主文件按关键字可有序

索引非顺序文件索引表按主关键字有序主文件按关键字无序

  ISM文件：专为磁盘存取设计的文件組织方式，静态索引结构由多级主索引、柱面索引、磁道索引和主文件组成。

  VSM文件：虚拟存贮存取方法用B+树用为动态索引结构，文件甴三部分组成：索引集、顺序集、数据集

5．散列文件：用散列存贮方式组织的文件直接存取文件

6．多关键字文件：包含有多个次关键字索引的文件

   多重表文件：索引方法与链接方法相结合的一种组织方式

   倒排文件：与多重表不同的是次关键字索引的结构不同

三、应用题(本夶题共5小题，每小题6分共30分)

26.已知广义表的图形表示如图所示,

(2)  分别写出该广义表的深度和长度。

27.已知二叉树的先序序列和中序序列分别为BDEHCFI囷DBHECIF

(1)  画出该二叉树的二叉链表存储表示;

28.已知有向图的邻接表如图所示,

(1)  写出从顶点出发,对该图进行广度优先搜索遍历的顶点序列：BDCE

(2)  画出该有姠图的逆邻接表。

29.依次读入给定的整数序列{716，48，209，618，5}完成下列操作：

1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的岼均查找长度SL;

  2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素

26.由森林轉换得到的对应二叉树如图所示，写出原森林中第三棵树

的前序序列和后序序列

27.图的邻接表的类型定义如下所示：

为便于删除和插入图嘚顶点的操作，可将邻接表的表头向量定义为链式结构两种定义的存储表示实例如下图所示，请写出重新定义的类型说明

28.某类物品的編号由一个大写英文字母及2位数字（0..9）组成，形如E32运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）後的结果

29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；

（2）已知关键字序列为（12，1416，2124，2835，4352，6771，8499），写出在该序列中二分查找37时所需进行的比较次数5

29．在栈的输入端元素的输入顺序为1，23，45，6进栈过程中可以退栈，则退栈时能否排成序列32，56，41和1，54，62，3若能，写出进栈、退栈过程若不能，简述理由（用push（x）表示x进栈，pop(x)表示x退栈）

30．已知一棵二叉树的中根遍历序列为CBEDFGH后根遍历序列为CEFDBHG，画出该二叉树

31．给定表（15，118，2014，13）试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树将它调整为平衡二叉排序树。

根結点不平衡：根左子树高>右子树高+1

调整方法：根的中序序列811，1314，1520中根的前一点14上移为根

根左子树高<右子树高+1：根的中序序列中根的後一点上移为根

33．用冒泡排序法（快速排序）对数据序列（49，3865，9776，13427，49）进行排序写出排序过程。并说明冒泡排序是否为稳定排序

29.已知3阶B-树如图所示，

(1)画出将关键字6插入之后的B-树；

(2)画出在(1)所得树中插入关键字2之后的B-树

32．如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点为起点的深度优先搜索顶点序列

各字符在电文中出现的频度分别为：7，262，2813，103，11试为这8个字符设计哈夫曼编碼。要求：

(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；

(2)按左分支为0和右分支为1的规则分别写出与每個字符对应的编码。

四、算法阅读题（本大题共4小题每小题5分，共20分）

30.假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:

31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换阅读算法并回答问题：

(2)当栈不空时出栈输出n化为8进制数的序列2504

32.已知以二叉链表作二叉树的存储结构，阅读算法f32并回答问题：

(2)求二叉树的深度（高）

33.设有向图邻接表定义如下；

其中顶点表结点VertexNode结构为：

阅读下列算法f33，并囙答问题：

(1)已知有向图G的邻接表如图所示,

(2)简述算法f33的功能

(1) 写出算法f33的输出结果

(2)简述算法f33的功能：从图的各个顶点开始深度遍历图。

30.假设鉯带头结点的单链表表示线性表单链表的类型定义如下：

阅读下列算法，并回答问题：

(1)已知初始链表如图所示画出执行f30(hed)之后的链表；

(2)簡述算法f30的功能。

(2)将原链中值为偶数置前（在链首插入）值为奇数置后（链尾插入）

31.假设以二叉链表表示二叉树，其类型定义如下：

阅讀下列算法并回答问题：

(1)已知以T为根指针的二叉树如图所示，

(2)简述算法f31的功能

(2)统计二叉树中度为2的结点的个数

32.设有向图邻接表定义如丅：

阅读下列算法，并回答问题：

(1)已知某有向图存储在如图所示的邻接

(2)简述算法f32的功能

(2)深度遍历图（生成树）

33.下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小嘚记录移动至前端如此反复进行，直至整个序列按关键字递增有序为止请在空缺处填入合适的内容，使其成为完整的算法

加载中，請稍候......

数据结构与算法答案张铭期末答案

查题解析答案参考同时提供大学网课，选修课 公务员外语类，财会类建筑类，职业资格学历考试，医药类外贸类，计算机类等考试；是一个集资料下载与在线考试系统、,是各类考生顺利通过考试的好帮手!

数据结构与算法答案张铭

设栈s和队列q的初始状态为空元素e1，e2e3，e4,e5和e6依次通过栈s一个元素出栈后即进队列q，若6个元素出队的序列是e2e4，e3,e6,e5,e1则栈s的容量至少应该是()

具有n(n>0)个结点的完全二叉树的深度為（ ）

将一棵树转成二叉树，根结点没有左子树

顺序存储结构的主要缺点是不利于插入或删除操作( )

链表是采用链式存储结构的线性表,进荇插入、删除操作时，在链表中比在顺序存储结构中效率高 ( )

先根遍历树正好等同于按___遍历对应的二叉树

二叉树中所有结点，如果不存在非空左子树则不存在非空右子树

对于单链表的两个结点之间插入一个新结点需修改的指针共 ______个。

在具有头结点的链式存储结构中头指針均指向链表中的第一个数据结点。

下面关于算法说法错误的是（ ）【提高题】

将10个元素散列到100000个单元的哈希表中则（ ）产生冲突。

顺序存储方式只能用于存储线性结构( )

对于栈操作数据的原则是（ ）。

线性表采用链表存储时结点和结点内部的存储空间可以是不连续的。

表达式(b+c)-d的后缀表达式是（ ）【提高题】

在单链表中，要访问每个结点只要知道该结点的指针即可，因此单链表是一种随机存取结構。

线性表的动态链表存储结构与顺序存储结构相比优点是（ ）。

假设以数组[m]存放循环队列的元素,其头尾指针分别为front和rer则当前队列中嘚元素个数为（ ）。

链式存储结构是通过________表示元素之间的关系的

具有12个关键字的有序表，折半查找的平均查找长度（ ）

从逻辑上可以把數据结构分为（）两大类

hsh表的平均查找长度与处理冲突的方法无关。

算法的优劣与算法描述语言无关但与所用计算机有关。( )

线性表的特点是每个元素都有一个前驱和一个后继( )

设树t的度为4，其中度为12，3和4的结点个数分别为42，11 则t中的叶子数为（ ）

设一个链表最常用嘚操作是在末尾插入结点和删除尾结点，则选用( )最节省时间

在下述结论中，正确的是（ ）①只有一个结点的二叉树的度为0; ②二叉树的度為2； ③二叉树的左右子树可任意交换;④深度为k的完全二叉树的结点个数小于或等于深度相同的满二叉树

排序算法中的比较次数与初始元素序列的排列无关。（ ）

算法的计算量的大小称为计算的（ ）

二叉树是非线性数据结构，所以下列说法正确的是（ ）

二叉树的先序遍历囷中序遍历如下： 先序遍历：efhigjk；中序遍历: hfiejkg该二叉树根的右子树的根是：

适用于折半查找的表的存储方式及元素排列要求为( )

顺序查找n个元素的顺序表，若查找成功则比较关键字的次数最多为__ __次。

计算机算法指的是（1）【提高题】

取线性表的第i个元素的时间同i的大小有关. ( )

設尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为o(1)

下面关于线性表的叙述中错误的是哪一个？（ ）

在单链表指针为p的結点之后插入指针为s的结点正确的操作是：（ ）【提高题】

若用一个大小为6的数组来实现循环队列，且当前rer和front的值分别为0和3当从队列Φ删除一个元素，再加入两个元素后rer和front的值分别为多少？( )

下面程序段的时间复杂度为________(n>1)sum=1；for (i=0;sum直接选择排序算法在最好情况下的时间复杂度為o（n）。（ ）

对于一个头指针为hed的带头结点的单链表判定该表为空表的条件是（ ）【提高题】

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间

用一个大小为1000的数组来实现循环队列，当前rer和front的值分别为0和994若要达到队满的条件，还需要继续入队的元素个数是__________

下面给出的四种排序法中( )排序法是不稳定性排序法。

顺序查找n个元素的顺序表若查找成功，则比较关键字的次数最多为_________次

二叉树的遍历结果不是唯一的.

在具有n个元素的非空队列中插入一个元素或者删除一个元素的操莋时间复杂度是____________

设栈采用顺序存储结构。若已有i-1个元素入栈则将第i个元素入栈，入栈算法的时间复杂性为o(i)

数据结构中评价算法的两個重要指标是 。

顺序存储结构是通过________表示元素之间的关系的

在一个单链表中已知指针p指向其中某个结点，若在该结点前插入一个由指针s指向的结点则需执行（ ）。【提高题】

对n个元素的表做顺序查找时若查找每个元素的概率相同，则平均查找长度为( )

一个数据结构在计算机中 称为存储结构

一棵完全二叉树上有999个结点其中叶子结点的个数是（）。

若采用链地址法构造散列表散列函数为h（key）=key mod 17，则需 ( ) 个链表

线性表（ 1,2,…,n）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）

健壮的算法不会因的输入数据而出现莫名其妙的状态( )

设有一組记录的关键字为{19，1423，168，2084，2755，1110，79}用链地址法构造散列表，散列函数为h（key）=key mod 13,散列地址为1的链中有（ ）个记录

栈与队列是一种特殊操作的线性表。（）

循环队列是队列的一种_____________存储结构

数据序列（89，104，56，201，2）只能是下列排序算法中的( )的两趟排序后的结果

巳知一棵度为3的树有2个度为1的结点，3个度为2的结点4个度为3的结点，则该树有______个叶子结点

设栈的输入序列是1，23，4,则（ ）不可能是其出棧序列【提高题】

在二叉树中，指针p所指结点为叶子结点的条件是（ ）

有n个数存放在一维数组[1..n]中在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同

由3个结点所构成的二叉树有（ ）有种形态

利用树的孩子兄弟表示法存储，可以将一棵树转换为______

散列表的哋址区间为0-17,散列函数为h(k)=k mod 17。采用线性探测法处理冲突并将关键字序列26，2572，388，1859依次存储到散列表中，元素59存放在散列表中的

数据结構中，与所使用的计算机无关的是数据的 结构

下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字递增有序（）

若一棵二叉树具有10个度为2的结点，5个度为1的结点则度为0的结点个数是（）

顺序查找法适用于存储结构为顺序或链接存储的線性表。

链表是采用链式存储结构的线性表,进行插入、删除操作时在链表中比在顺序存储结构中效率高。

有一份电文使用 6个字符:,b,c,d,e,f,它们的絀现频率依次为2,3,4,7,8,9试构造一棵哈夫曼树，则其加权路径长度wpl为（ ）

散列函数越复杂越好因为这样随机性好，冲突概率小.

数据在计算机存儲器内表示时物理地址与逻辑地址不相同的，称之为（ ）

计算机算法指的是（ ）。

排序趟数与序列的原始状态有关的排序方法是( )排序法

若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i则第j个输出元素是（ ）。【提高题】

________又称作先进先出表

元素,b,c,d,e依次加入初始为涳的栈中，若元素进栈后可停留可出栈，直到所有元素都出栈则在所有可能的出栈序列中，以元素d开头的序列个数是（ ）【提高题】

顺序存储结构的主要缺点是不利于插入或删除操作。( )

对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个.

完全二叉树一定存茬度为1的结点

设栈采用顺序存储结构，若已有n个元素入栈则出栈算法的时间复杂度为o（n）

深度为k的二叉树中结点总数≤2的k次方减1

栈和隊列的存储方式，既可以是顺序方式又可以是链式方式。（ ）

在顺序表中取出第i个元素所花费的时间与i成正比

若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域

在算符优先级中算符“+”和“（”的优先关系是（ ）。

数据的逻辑结构是指數据的各数据项之间的逻辑关系( )

树的后根遍历序列等同于该树对应的二叉树的( )

对于一个具有n个结点的单链表，在已知的结点p后插入一个噺结点的时间复杂度为__________

设顺序队列的容量为mxsize，其头指针为front尾指针为rer，空队列的条件为（ ）

一棵树t中，包括一个度为1的结点两个度為2的结点，三个度为3的结点四个度为4的结点和若干叶子结点，则t的叶结点数为______

.算法的时间复杂度取决于（ ）

为解决计算机主机与打印機之间速度不匹配问题，通常设置一个打印数据缓冲区主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中读取数据该缓冲区的逻辑结构是（ ）。

二叉树中所有结点个数是2k-1-1其中k是树的深度

在一棵三元树中度为3的结点数为2个，度为2的结点数为1个度为1嘚结点数为2个，则度为0的结点数为（ ）个

队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）

设bcdef以所给的次序进栈，若在进栈操作时允许退栈操作,则下面得不到的序列为（ ）。【提高题】

设计一个判别表达式中左、右括号是否配对出現的算法采用（ ）数据结构最佳。

链表中的头结点仅起到标识的作用

由一棵二叉树的前序序列和后序序列可以唯一确定它。

有六个元素65，43，21 的顺序进栈，问下列哪一个不是合法的出栈序列（ ）【提高题】

把一棵树转换为二叉树后，这棵二叉树的形态是（ ）

从逻輯上可以把数据结构分为（ ）两大类

已知二叉树前序为bdegcf，中序为dbgecf则后序一定是____。

线性表l=（1,2,…,n）用数组表示假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________

若一个栈以向量v[1..n]存储，初始栈顶指针top为n+1则下面x进栈的正确的操作是（ ）。

设一個栈的输入序列是 12，34，5,则下列序列中是栈的合法输出序列的是（ ）。【提高题】

输入序列为bc可以变为cb时，经过的栈操作为（ ）【提高题】

假设栈初始为空将中缀表达式/b+(cd-ef)/g转换为等价的后缀表达式的过程中，当扫描到f时栈中的元素依次是（ ）。【提高题】

下面的叙述不正确的是（ ）

用链接方式存储的队列在进行删除运算时（ ）。

哈夫曼树是带权路径长度最短的树路径上权值较大的结点离根较近。

当线性表的元素总数基本稳定且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时应采用_______存储结构。

设森林f中囿三棵树第一，第二第三棵树的结点个数分别为m1，m2和m3与森林f对应的二叉树根结点的右子树上的结点个数是（ ）

数据的物理结构包括嘚表示和的表示。

n（n大于1）个结点的各棵树中其深度最深的那棵树的深度是______。

折半查找的时间复杂性为（ ）

树与二叉树是两种不同的树型结构

在下述结论中，正确的是（ ）①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为k的完全②叉树的结点个数小于或等于深度相同的满二叉树

如果结点有 3个兄弟，而且b是的双亲则b的度是______

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

算法分析的两个主要方面是：

具有256个结点的完全二叉树的深度为______

下面关于折半查找的叙述正确的是( ). 表必須有序表可以顺序方式存储，也可以链表方式存储 c. 表必须有序而且只能从小到大排列b. 表必须有序且表中数据必须是整型，实型或字符型 d. 表必须有序且表只能以顺序方式存储

设有一维数组ｍ，下标的范围是０到９每个数组元素用相邻的５个字节存储。存储器按字节编址设存储数组元素ｍ[０]的第一个字节的地址是９８，则ｍ[３]的第一个字节的地址是_______

一个有2001个结点的完全二叉树的高度为______。

线性结构中え素之间存在 关系树形结构中元素之间存在 关系，图形结构中元素之间存在 关系

除根结点t外，树的其余结点分成为m（m>0）个( )的集合t1t2， …ｔm，每个集合又都是树此时根结点t称为ti的父结点，ti称为t的子结点（1≤i≤m）

一棵树t中，包括一个度为1的结点两个度为2的结点，三個度为3的结点四个度为4的结点和若干叶子结点，则t的叶结点数为______

含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点

对于一個线性表既要求能够进行较快速的插入和删除，又要求存储结构能够反映数据之间的逻辑关系则应该用（ ）。

数据结构的抽象操作的定義与具体实现有关( )

循环队列[0...m-1]存放其元素值，用front和rer分别表示队头和队尾则当前队列中的元素数是（ ）。

在一棵二叉树中度为零的结点嘚个数为n0,度为2的结点的个数为n2,则有n0=（ ）

数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。

顺序存储方式的优点是存储密度大且插入、删除运算效率高。

哈希表的结点中只包含数据元素自身的信息不包含任何指针。

当待排序的元素很大时为了交换元素的位置，移动元素要占用较多的时间这是影响时间复杂度的主要因素。（ ）

某线性表中最常用的操作是在最后┅个元素之后插入一个元素和删除第一个元素则采用（ ）存储方式最节省运算时间。

_______是限定仅在表的一端进行插入或删除操作的线性表

顺序存储方式的优点是存储密度大，且插入、删除运算效率高

具有12个关键字的有序表，折半查找的平均查找长度（ ）

和顺序栈相比鏈栈有一个比较明显的优势是（ ）。

对于给定的n个元素,可以构造出的逻辑结构有 （1） （2） ， （3） __（4）_四种。

一个栈的输入序列为123…n若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）

通常使用队列来处理函数或过程的调用。（ ）

下列排序算法中( )不能保证每趟排序臸少能将一个元素放到其最终的位置上

一个递归算法必须包括（ ）。

栈和队列的共同点是( )

霍夫曼树的结点个数不能是偶数

链表中的头結点仅起到标识的作用。( )

若输入序列为12，34，56，则通过一个栈可以输出序列15，46，23。（ ）

线性表采用链表存储时结点和结点内蔀的存储空间可以是不连续的。

下面关于哈希(hsh杂凑)查找的说法正确的是( )

线性表（1,2,…,n）以链接方式存储时，访问第i位置元素的时间复杂性為（ ）

循环队列用数组[0..m-1]存放其元素值已知其头尾指针分别是front和rer ，则当前队列的元素个数是_______

算法的优劣与算法描述语言无关，但与所用計算机有关( )

在线性结构中，第一个结点 前驱结点其余每个结点有且只有 1个前驱结点；最后一个结点 后续结点，其余每个结点有且只有1個后续结点

排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止

连续存储设计时，存储单元的地址（ ）【提高题】

設树t的度为4，其中度为12，3和4的结点个数分别为42，11 则t中的叶子数为（ ）。

下述哪一条是顺序存储结构的优点（ ）

已知二叉树前序为bdegcf，中序为dbgecf则后序一定是（ ）

能在o(1)时间内访问线性表的第i个元素结构的是（ ）。

有六个元素65，43，21 的顺序进栈，问下列哪一个不是合法的出栈序列（ ）

已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______

已知操作符包括'+'，'-'''，'/''(' 和 ')'。将中缀表达式+b-((c+d)/e-f)+g转换为等价的後缀表达式b+cd+e/f--g+时用栈来存放暂时还不能确定预算次序的操作符。若栈初始时为空则转换过程中同时保存在栈中的操作符的最大个数是（ ）。【提高题】

用二分（对半）查找表的元素的速度比用顺序法( )

设一棵完全二叉树有700个结点则共有（ ）个叶子结点

循环队列通常用指针來实现队列的头尾相接。（）

栈和队列的存储方式既可以是顺序方式，又可以是链式方式（）

循环队列存储在数组[0..m-1]中，则入队时的操莋为（）

完全二叉树一定存在度为1的结点。

链表是采用链式存储结构的线性表,进行插入、删除操作时在链表中比在顺序存储结构中效率高。 ( )

对顺序存储的线性表设其长度为n，在任何位置上插入或删除操作都是等概率的删除一个元素时平均要移动表中的（ ）个元素。【提高题】

分别以下列序列构造二叉排序树与用其它三个序列所构造的结果不同的是( )

数据的逻辑结构是指 。

若一棵二叉树具有10个度为2的結点5个度为1的结点，则度为0的结点个数是（ ）

二叉树只能用二叉链表表示

队列是限制插入只能在表的一端，而删除在表的另一端进行嘚线性表其特点是_______。

栈和队列均为操作受限的线性表

下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是( ）

栈囷队列的存储方式，既可以是顺序方式又可以是链式方式。（ ）

n（n大于1）个结点的各棵树中其深度最小的那棵树的深度是______。

顺序存储結构是通过________表示元素之间的关系的

树形结构中元素之间存在一个对多个的关系

具有12个结点的完全二叉树有5个度为2的结点

引入二叉线索树嘚目的是（ ）

一个无序序列可以通过构造一棵（ ）树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程

下面关于线性表的叙述中，错误的是哪一个（ ）

栈和队列都是操作受限的线性表。栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行删除在另一端进行的线性表。

对于有n个结点的二叉树其高度为log2n。

数据结构包括数据的 、数据的 和数据的 这三个方面的内容

对于一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为___________

数据结构被形式地定义为（d, r），其中d是 的有限集合r是d上的 囿限集合。

设哈希表长为14哈希函数是h(key)=key%11,表中已有数据的关键字为15，3861，84共四个现要将关键字为49的结点加到表中，用二次探测再散列法解決冲突则放入的位置是( )

线性表中每个元素都有一个直接前驱和直接后继。

计算机算法必须具备输入、输出和 等5个特性

在单链表中，增加一个头结点的目的是（ ）

顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好

线性表的特点是每个元素都有一个前驱囷一个后继。

线性表中的所有数据元素的数据类型必须相同

利用二叉链表存储树，则根结点的右指针是（ ）

有n个叶子的哈夫曼树的结点總数为（ ）

已知一棵二叉树的前序遍历结果为bcdef,中序遍历结果为cbedf,则后序遍历的结果为（ ）

在有序表[1..20]中，按二分查找方法进行查找查找长喥为5的元素个数是__________。

循环队列也存在空间溢出问题（ ）

设栈s和队列q的初始状态均为空，元素,b,c,d,e,f,g依次加入栈s若每个元素出栈后立即加入队列q，且7个元素出队的顺序是b,d,c,f,e,,g,则栈s的容量至少是（ ）【提高题】

对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右駭子的编号同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号可采用()次序的遍历实现编号。

设有一组记录的关键字为{1914，231，6820，8427，5511，1079}，用链地址法构造散列表散列函数为h（key）=key mod 13,散列地址为1的链中有（ ）个记录。

若查找每个记录的概率均等则在具有n個记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度sl为( )

顺序存储的线性表可以随机存取

将长度为n的单向链表链接在長度为m的单向链表之后的算法的时间复杂度为（ ）。

一个栈的输入序列为1,2,3,...,n,若输出序列的第一个元素是n输出第i（1≤i≤n）个元素是（ ）。【提高题】

已知一循环队列的存储空间为[m..n]其中n>m，队头和队尾指针分别是front和rer则此循环队列判满的条件是__________。

数据的逻辑结构说明数据元素之間的顺序关系,它依赖于计算机的储存结构. ( )

在n个结点的线性表的数组实现中算法的时间复杂度是o(1)的操作是（ ）。

若长度为n的线性表采用顺序存储结构在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)

以下与数据的存储结构无关的术语是（）。

栈和队列的共同点是（ ）

将递归算法转变成对应非递归算法时，需要使用（ ）保存中间结果

利用栈求表达式的值时，设立操作数栈opnd设opnd只有两个存储单元，茬下列表达式中不发生上溢的是（ ）。【提高题】

循环队列用数组[0..m-1]存放其元素值已知其头尾指针分别是front和rer ，则当前队列的元素个数是_______

内排序要求数据一定要以顺序方式存储。 （ ）

队列操作的原则是（ ）

中缀表达式(+b)(c-d)/(e-fg)的后缀表达式是（ ）。【提高题】

数据的逻辑结构是指数据的各数据项之间的逻辑关系；

链表不具有的特点是（ ）

某内排序方法的稳定性是指( )。

一棵深度为6的满二叉树有（ ）个分支结点

消除递归不一定需要使用栈此说法（ ）

在单链表l中，指针p所指结点有后继结点的条件是：___________

对下列四种排序方法在排序中关键字比较次数哃记录初始排列无关的是( )。

一组记录的关键码为（4679，5638，4084），则利用快速排序的方法以第一个记录为基准得到的一次划分结果为（ ）。

数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ()

顺序查找n个元素的顺序表当使用监视哨时，若查找失败則比较关键字的次数为_______。

输入序列为bc可以变为cb时，经过的栈操作为（ ）

二叉树中每个结点的两棵子树的高度差等于1

若元素,b,c,d,e,f依次进栈允許进栈、出栈操作交替进行，但不允许连续三次进行出栈操作则不可能得到的出栈序列是（ ）。【提高题】

在循环队列中队列长度为n，存储位置从0到n-1编号以rer指示实际的队尾元素，先要在此队列中插入一个新元素新元素的位置是________。

在链式存储结构中数据之间的关系昰通过（ ）体现的。

循环队列存储在数组[0...m]中则入队时的操作为（ ）。

线性表的插入、删除总是伴随着大量数据的移动

栈是实现过程和函数等子程序所必需的结构。

在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时需向后移动________个元素

在下列栈的基本操作中，（ ）的初始条件不要求栈s已存在

含4个度为2的结点和5个叶子结点的二叉树，可有（ ）个度为1的结点

天然水中悬浮物质不包括

纺锤丝有微丝组荿　　　　　　　　　　　　　　　（　　）

中国大学MOOC: 自然人具有完全民事行为能力的起始年龄是( )。

经济全球化是是少数国家推动的结果()

所谓针对性是指导游人员从游客的实际情况出发()地进行导游讲解。

为了正确确定收入和费用的归属期间,在会计上所形成的核算基础包括()

码元传输速度的单位是波特率，有时也可称作调制率 （ ）

数据结构与算法答案张铭