数据结构课件题目（附答案） - 图文

… 第一章

1.算法的计算量的大小称为计算的（ B ）。 A. 效率 B. 复杂性 C. 现实性 D. 难度 2.一个算法应该是（ B ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 3．下面说法错误的是（ A ）

(1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 4.在数据结构中，从逻辑上可以将之分为( D )。

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 5.计算算法的时间复杂度是属于一种( B )。

A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6.可以用( D )定义一个完整的数据结构:

A. 数据元素 B. 数据对象 C. 数据关系 D. 抽象数据类型 7.算法分析的目的是___C____。

A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 8.设计一个―好‖的算法应考虑达到的目标有___BCD___。

A. 是可行的 B. 是健壮的 C. 无二义性 D. 可读性好

第二章

1.线性表是具有n个（ C ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

2.若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式( A )。

A.单链表 B.双向链表 C.单循环链表 D.顺序表

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

A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表 4.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( A )最节省时间。 A. 带头结点的双循环链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 单链表 5.静态链表中指针表示的是( C )

A.下一元素的地址 B.内存储器的地址

C.下一元素在数组中的位置 D.左链或右链指向的元素的地址 6.下述哪一条是顺序存储结构的优点？（ C ）

A．插入运算方便 B．可方便地用于各种逻辑结构的存储表示

…

C．存储密度大 D．删除运算方便

7.下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链接存储，不必占用一片连续的存储单元 D．线性表采用链接存储，便于插入和删除操作。

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

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 9.链表不具有的特点是（ B ）

A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比

10.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ B ）

A.(1),(2) B.(1) C.(1),(2),(3) D.(2)

11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。 A. O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 12.单链表中，增加一个头结点的目的是为了( C ）。

A．使单链表至少有一个结点 B．标识表结点中首结点的位置 C．方便运算的实现 D．说明单链表是线性表的链式存储

13.对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（ D ）。 A． p->right=s ; s->left=p; p->right->left=s ; s->right=p->right; B． p->right=s ; p->right->left=s ; s->left=p; s->right=p->right; C． s->left=p; s->right=p->right; p->right=s ; p->right->left=s ; ; D． s->left=p; s->right=p->right; p->right->left=s ; p->right=s ;

14.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL

第三章 无 第四章

1.下面关于串的的叙述中，哪一个是不正确的？（B）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2.串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？（A） A. 数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 3.串的长度是指（ B ）

A．串中所含不同字母的个数 B．串中所含字符的个数

…

C．串中所含不同字符的个数 D．串中所含非空格字符的个数

4.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ C ）。 A．2n-1 B．n C．(n/2)+(n/2) D．(n/2)+(n/2)-1 E. (n/2)-(n/2)-1 F. 其他情况

2222第五章

1.数组是同类型值的集合。（F ）

2.从逻辑结构上看，n维数组的每个元素均属于n个向量。（ T ）

3.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ F ）

第六章

1.n(n>0)个结点的树的高度:最低是多少？(2)最高是多少？(n) 2.n(n>0)个结点的二叉树的高度:最低是多少？最高是多少？ 3.有关二叉树下列说法正确的是（ B ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 4.一棵124个叶结点的完全二叉树，最多有( C )个结点。 A.247 B.248 C.249; D.250; E.251

5.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( C )。 A. 311 B. 312 C. 313 D. 314 E. 其它 6.一个具有1025个结点的二叉树的高h为（ C ）

A．11 B．10 C．11至1025之间 D．10至1024之间 7.一棵树高为K的完全二叉树至少有（ C ）个结点

A. 2 –1 B. 2 –1 C. 2-1 D. 2

8.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12___个叶子结点。

9.已知二叉树的 先序序列ABDFCEHG中序序列DBFAHECG请构造该二叉树。

10.已知二叉树的后序序列DMFBHELGCA 中序序列DBMFAHECGL请构造该二叉树。 11.一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。 先序序列为：_ _ C D E _ G H I _ K 中序序列为：C B _ _ F A _ J K I G

后序序列为： _ E F D B _ J I H _ A 12.试找出满足下列条件的二叉树 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同

4）中序序列与层次遍历序列相同

13.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ）。

A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEGB

KK?1KK

…

14.一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( C )。 A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶子结点 D. 其中度为2的结点最多为一个

15.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( B )的二叉树 A．空或只有一个结点 B. 高度等于其结点数 C．任一结点无左孩子 D. 任一结点无右孩子 16.二叉树在线索化后，仍不能有效求解的问题是（D ）。

A. 先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继 17.引入二叉线索树的目的是（ A ）

A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一

18.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( C ) A. X的双亲 B. X的右子树中最左的结点 C. X的左子树中最右结点 D. X的左子树中最右叶结点

19.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( B )。 A. 0 B. 1 C. 2 D. 不确定 20.将树转换成二叉树 AA

B C D B C E F GHI J

EG D F K L AH J K 树转换成的二叉树其右子树一定为空 L I GB21.森林转为二叉树

JCHA G J K B C D H I DIEK F L M N E LF 22.已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO M后序序列：CDEBFHIJGAMLONK 解：森林的前序序列和后序序列对应其转换的二叉树的前序序列和中序序列，应先据此构造N二叉树，再构造出森林

23.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别

…

为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是 （ D )。

A．M1 B．M1+M2 C．M3 D．M2+M3

24.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ C ）个。

A．n-1 B．n C．n+1 D．n+2 25.设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是( D )。

A. 在树T中，X是其双亲的第一个孩子 B. 在树T中，X一定无右边兄弟 C. 在树T中，X一定是叶子结点 D. 在树T中，X一定有左边兄弟 26.设树形T在后根次序下的结点排列和各结点相应的次数如： 后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ 次 数：００００３０００２０２４ 请画出Ｔ的树形结构图。

27.给定权值7，6，3，32，5，26，12，9，构造相应的哈夫曼树，并计算其带权路径长度。为使结果答案唯一，请用左结点的值小于等于右结点的值来构造哈夫曼树。

第七章

1.图中有关路径的定义是（ A ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2.设无向图的顶点个数为n，则该图最多有（ B ）条边。

A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n

3.一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A．0 B．1 C．n-1 D．n 4.要连通具有n个顶点的有向图，至少需要（b）条边。

A．n-l B．n C．n+l D．2n

5.G是一个非连通无向图，共有28条边，则该图至少有____9__个顶点。

6.用邻接表存储图所用的空间大小 A 。

A.与图的顶点数和边数都有关 B.只与图的边数有关 C.只与图的顶点数有关 D.与边数的平方有关 7.图G是n个顶点的无向完全图，则下列说法正确的有：BCD A. G的邻接多重表需要n(n-1)个边结点和n个顶点结点； B. G的连通分量个数最少； C. G为连通图； D. G所有顶点的度的总和为n(n-1);

8.在有向图的邻接表存储结构中，顶点v在链表中出现的次数是( B )。

A. 顶点v的度 B. 顶点v的出度 C. 顶点v的入度 D. 依附于顶点v的边数 8.图的遍历举例

(1)假定以邻接表存储，邻接点按编号升序排列。遍历序列如下：

2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构课件题目（附答案） - 图文在线全文阅读。