数据结构填空选择

1．数据的物理结构包括 数据元素 的表示和 数据元素关系 的表示。

2. 对于给定的n个元素,可以构造出的逻辑结构有 集合 ， 线性结构 ， 树形结构 ，__图状结构或网状结构_四种。

3．数据的逻辑结构是指 数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系” 。

4．一个数据结构在计算机中的 表示（或称映像） 称为存储结构（又数据的物理结构）。

5．抽象数据类型的定义仅取决于它的一组__逻辑特性_，而与_在计算机内部如何表示和实现_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。 6．数据结构中评价算法的两个重要指标是 算法的时间复杂度和空间复杂度

7. 数据结构是研讨数据的_逻辑结构_和_物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_，设计出相应的_算法。

8． 一个算法具有5个特性: 有穷性 、 确定性 、 可行性 ，有零个或多个输入、有一个或多个输出 。

4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较____C____个元素结点。

A．n/2 B．n C．（n+1）/2 D．（n-1）/2 10. 线性表的顺序存储结构是一种___A____的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取 17. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行___B___。 A．hs->next=s; B．s->next=hs; hs=s;

C．s->next=hs->next;hs->next=s; D．s->next=hs; hs=hs->next;

1. 线性表是一种典型的___线性 _结构。 4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需___前移____一个位置，移动过程是从___前____向___后____依次移动每一个元素。

5. 在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过__链域的指针值_____决定的。

10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为____单链表_____和___双链表____；而根据指针的联接方式，链表又可分为___非循环链表_____和____循环链表_____。

11. 在单链表中设置头结点的作用是___使空表和非空表统一；算法处理一致

_____。

12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为__O(1)___，在给定值为x的结点后插入一个新结点的时间复杂度为___O(n)_____。

13. 对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别

栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。

栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇

1. 空串与空格字符组成的串的区别在于（ B ）。

A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2. 一个子串在包含它的主串中的位置是指（ D ）。

A.子串的最后那个字符在主串中的位置

B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置

D.子串的第一个字符在主串中首次出现的位置

7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ D ）。

A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing” C. “ShanghaiNanjing” D. “Shanghai＆Nanjing”

1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。

2. 两个字符串相等的充要条件是_____________________和___________________。 3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。

4. 串是指___________________。

5. 空串是指___________________，空格串是指___________________。 1. 固定长度，设置长度指针

2. 两个串的长度相等，对应位置的字符相等 3. “BCDEDE”

4. 含n个字符的有限序列 （n≥0）

5. 不含任何字符的串，仅含空格字符的字符串

10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( D )。

A. n B. n?e C. e D. 2?e

11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( C )。

A. n B. n?e C. e D. 2?e

14. 在一个无权图的邻接表表示中，每个边结点至少包含( B )域。

A. 1 B. 2 C. 3 D. 4

8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有___3_____个连通分量。

12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。12. O（n），O（e/n） 3. 假定一棵三叉树的结点数为50，则它的最小高度为（ C ）。

A. 3 B. 4 C. 5 D. 6 7. 线索二叉树是一种（ C ）结构。

A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 8. 线索二叉树中，结点p没有左子树的充要条件是（ B ）。 A. p->lc=NULL B. p->ltag=1 C. p->ltag=1 且p->lc=NULL D. 以上都不对

11. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（ A ）存储结构。

A. 三叉链表 B. 广义表 C. 二叉链表 D. 顺序 12. 下面叙述正确的是（ D ）。 A. 二叉树是特殊的树

B. 二叉树等价于度为2的树 C. 完全二叉树必为满二叉树 D. 二叉树的左右子树有次序之分

13. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ A ）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对

2. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。

5. 在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。

6. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。

11. 一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。 13. 对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于链接孩子结点，_____________个空闲着。

14. 哈夫曼树是指________________________________________________的二叉树。 15. 空树是指________________________，最小的树是指_______________________。 16. 二叉树的链式存储结构有______________和_______________两种。 17. 三叉链表比二叉链表多一个指向______________的指针域。 18. 线索是指___________________________________________。

19. 线索链表中的rtag域值为_____时，表示该结点无右孩子，此时______域为指向该结点后继线索的指针。

20. 本节中我们学习的树的存储结构有_____________、___________和___________。 2. n+1 5. 中序

6. 2n，n-1，n+1

11. 单支树，完全二叉树 13. 2n，n-1，n+1

14. 带权路径长度最小

15. 结点数为0，只有一个根结点的树

16. 二叉链表，三叉链表 17. 双亲结点

18. 指向结点前驱和后继信息的指针 19. 1，RChild

20. 孩子表示法，双亲表示法，长子兄弟表示法

本文来源：https://www.bwwdw.com/article/18it.html