读书破万卷下笔如有神
第一章练习
一、选择题
1. 算法的计算量的大小称为计算的（）。
A．效率 B. 复杂性 C. 现实性 D. 难度
2.计算机算法指的是（），它必须具备（）这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法
(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性
D. 易读性、稳定性、安全性
3．从逻辑上可以把数据结构分为（）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
选择题答案：1.B 2.（1）C （2）B 3.C
二、判断题
1. 数据元素是数据的最小单位。( )
2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( )
3．算法的优劣与算法描述语言无关，但与所用计算机有关。( )
4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )
5．程序一定是算法。( )
6．数据的物理结构是指数据在计算机内的实际存储形式。( )
7. 数据结构的抽象操作的定义与具体实现有关。( )
判断题答案：1.F 2.F 3.F 4.T 5.F 6.T 7.F
三、填空
1. 对于给定的n个元素,可以构造出的逻辑结构有，，，_ _四种。
2．数据的逻辑结构是指。
3．一个数据结构在计算机中称为存储结构。
4．数据结构中评价算法的两个重要指标是和
5. 数据结构是研讨数据的_ _ 和 _ _，并对与这种结构定义相应的_ _，设
计出相应的_ 。
6．一个算法具有5个特性: 、、，有零个或多个输入、
有一个或多个输出。
填空题答案：1.集合线性结构树形结构图状结构
2. 数据及相互之间的联系
3.的存储方式
4.时间复杂度空间复杂度
5.逻辑结构存储结构运算（操作）算法
可行性确定性有穷性6.
读书破万卷下笔如有神
第二章练习
一选择题
1．下述哪一条是顺序存储结构的优点？（）
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
2．下面关于线性表的叙述中，错误的是哪一个？（）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n个（）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项 E．信息项
4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A. 单链表
B.单循环链表
C. 带尾指针的单循环链表
D.带头结点的双循环链表
7. 静态链表中指针表示的是（）.
A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址
8. 链表不具有的特点是（）
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
9. 下面的叙述不正确的是（）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
10.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表无关。i个元素的时间与i中第
读书破万卷下笔如有神
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（）
A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）
11. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。
2) A. O(0) B. O(1) C. O(n) D. O(n12. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
13．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）
A．O（i） B．O（1） C．O（n） D．O（i-1）
14．非空的循环单链表head的尾结点p满足（）。
A．p->link=head B．p->link=NIL C．p=NIL D．p= head 15．在双向链表指针p的结点前插入一个指针q的结点操作是（）
A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
16．在单链表指针为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;
17．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）
A．head==NULL B．head→next==NULL C．head→next==head
D．head!=NULL
三、填空
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快
的速度存取线性表中的元素时，应采用_______存储结构。
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;
）之前插入一个元素时，需1<=i<=n个元素（i的顺序表中第n．在一个长度为4．
读书破万卷下笔如有神
向后移动________个元素。
5．在单链表中设置头结点的作用是________。
6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为
________。
7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和
________。
8．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。
10．链接存储的特点是利用________来表示数据元素之间的逻辑关系。
11.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过
________表示元素之间的关系的。
12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。
13. 循环单链表的最大优点是：________。
14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________
15. 带头结点的双循环链表L中只有一个元素结点的条件是：________
16. 在单链表L中，指针p所指结点有后继结点的条件是：__
填空答案：
1．顺序
2．（n-1）/2
3．py->next=px->next; px->next=py
4 ．n-i+1
5．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。
6．O(1)，O(n)
7．单链表，多重链表，（动态）链表，静态链表
8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;
9．p^.prior s^.prior^.next
10．指针
11．物理上相邻指针
12．4 2
13．从任一结点出发都可访问到链表中每一个元素。
14．u=p->next; p->next=u->next; free(u);
15．L->next->next==L
16．p->next!=null
二、判断
1. 链表中的头结点仅起到标识的作用。( )
2. 顺序存储结构的主要缺点是不利于插入或删除操作。( )
( )
结点和结点内部的存储空间可以是不连续的。线性表采用链表存储时，．3．
读书破万卷下笔如有神
4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 5. 对任何数据结构链式存储结构一定优于顺序存储结构。( )
6．顺序存储方式只能用于存储线性结构。( )
7．集合与线性表的区别在于是否按关键字排序。( )
8. 所谓静态链表就是一直不发生变化的链表。( )
9. 线性表的特点是每个元素都有一个前驱和一个后继。( )
10. 取线性表的第i个元素的时间同i的大小有关. ( )
11. 循环链表不是线性表. ( )
12. 线性表只能用顺序存储结构实现。( )
13. 线性表就是顺序存储的表。( )
14．为了很方便的插入和删除数据，可以使用双向链表存放数据。( )
15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )
16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( )
部分答案解释如下。
1、头结点并不“仅起”标识作用，并且使操作统一。另外，头结点数据域可写入链表长度，或作监视哨。
4．两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪一个好。7．集合中元素无逻辑关系。
9．非空线性表第一个元素无前驱，最后一个元素无后继。
13．线性表是逻辑结构，可以顺序存储，也可链式存储。
第三章练习
一选择题
1. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A. 60
B. 66
C. 18000
D. 33
2. 对稀疏矩阵进行压缩存储目的是（）。
A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度
3. 广义表（（a,b,c,d））的表头是（），表尾是（）。
）b,c,d（ D.）a,b,c,d（ C.（）A. a B.
读书破万卷下笔如有神
4. 广义表（a,(b,c),d,e）的表头为（）。
A. a
B. a,(b,c)
C. (a,(b,c))
D.
(a)
5. 设广义表L=（（a,b,c）），则L的长度和深度分别为（）。
A. 1和1
B. 1和3
C. 1和2
D. 2和3
6. 下面说法不正确的是( )。
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构
D. 广义表可以是一个多层次的结构
选择题答案
1.B
2.C
3.C
4.A
5.C
6.A
三、填空
1. 所谓稀疏矩阵指的是_______。
2. 当广义表中的每个元素都是原子时，广义表便成了_______。
3. 广义表的表尾是指除第一个元素之外，_______。
4. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 (1)____。为了区分原子和表，一般用 (2)____表示表，用
(3)_____表示原子。一个表的长度是指 (4)__，而表的深度是指__(5)__ 5. 广义表的_______ 定义为广义表中括弧的重数。
填空答案：
1. 非零元很少(t< 2. 线性表 3. 其余元素组成的表 4. （1）原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而 表带结构，本质就是广义表，因作为广义表的元素故称为子表。 （2）大写字母（3）小写字母（4）表中元素的个数（5）表展开后所含括号的层数 5. 深度 二、判断 1. 稀疏矩阵压缩存储后，必会失去随机存取功能。（） 2. 一个稀疏矩阵A采用三元组形式表示，若把三元组中有关行下标与列下m*n 标的值互换，并把m和n的值互换，则就完成了A的转置运算。（）m*n3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（） 4. 若一个广义表的表头为空表，则此广义表亦为空表。（） 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。5. 读书破万卷下笔如有神 （） 6. 所谓取广义表的表尾就是返回广义表中最后一个元素。（） 7. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（） 8. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（） 9. 一个广义表可以为其它广义表所共享。（） 判断题答案 1.√ 2. × 3.× 4.× 5.× 6.× 7.√ 8.√ 9.√ 部分答案解释如下。 6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转 置后在新三元组中的位置。 8. 错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。 9. 错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。 10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表）。 11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。 第四章练习 一、填空 1．栈是_______的线性表，其运算遵循_______的原则。 2．_______是限定仅在表尾进行插入或删除操作的线性表。 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。 4．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。 5. 顺序栈用data[n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。 6．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。 7. 循环队列的引入，目的是为了克服_______。 8．________又称作先进先出表。 9．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。 10．设循环队列用数组A[M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为_______。 11．表达式求值是_______应用的一个典型例子。 12．循环队列用数组A[m]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。 填空题答案： 、3 栈、2 后进先出（或限定仅在表尾进行插入和删除操作）操作受限、1． 读书破万卷下笔如有神 3 1 2 4、S×SS×S×× 5、data[++top]=x； 6、 23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3是三个数） 7、假溢出时大量移动数据元素。 8、队列 9、先进先出 10、（TAIL+1）MOD M=FRONT 12、栈 13、（rear-front+m）% m； 二、判断 1. 栈是实现过程和函数等子程序所必需的结构。（） 2. 栈与队列是一种特殊操作的线性表。（） 3. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（） 4. 通常使用队列来处理函数或过程的调用。（） 5. 循环队列也存在空间溢出问题。（） 6. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（） 判断题答案：1.√， 2.√， 3. ×，4.×， 5.√，6. √ 第五、六章练习 一、选择题 1. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）（提示：结点总数=度总数+1） A．5 B．6 C．7 D．8 2. 在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树 可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 3. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数 为n,森林F中第一棵树的结点个数是（） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 4．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点 个数是（） A．9 B．11 C．15 D．不确定 5．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和 M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 6．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 501 C．254 D．505 7. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 8. 有n个叶子的哈夫曼树的结点总数为（）。 2n-1 ．2n+1 D．2n C． B．不确定A． 读书破万卷下笔如有神 9. 有关二叉树下列说法正确的是（） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 10．二叉树的第I层上最多含有结点数为（） I I-1I-1I -1 2 D 2．-1 C 2A．2． B．11. 一个具 有1025个结点的二叉树的高h为（） A．11 B．10 C．11至1025之间 D．10至1024之间 12．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( ) 结点 A．2h B．2h-1 C．2h+1 D．h+1 13．对于有n 个结点的二叉树, 其高度为（） A．nlogn B．logn C．?logn?|+1 D．不确定22214. 一棵 具有 n个结点的完全二叉树的树高度（深度）是（） A．?logn?+1 B．logn+1 C．?logn? D．logn-1 222215．深度 为h的满m叉树的第k层有（）个结点。(1= k-1 kh-1h-1 m D．m．-1 C．mA．m B16．在一棵高度为k 的满二叉树中，结点总数为（） k-1 k kk?+1 ?2C．log2A．2-1 DB．2．17．高度为 K的二叉树最 大的结点数为（）。 kk-1kk-1-1 ．22 D2 -1 B．2 C．A．18. 一棵树高为K的完全二 叉树至少有（）个结点 kk-1k-1k D. 21 C. 2 –A．2 –1 B. 2 19．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 20．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 21．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： A、 E B、 F C、 G D、 H 22．在下列情况中，可称为二叉树的是（） A．每个结点至多有两棵子树的树 B. 哈夫曼树 C．每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E．以上答案都不对 23．由3 个结点可以构造出多少种不同的二叉树？（） A．2 B．3 C．4 D．5 读书破万卷下笔如有神 二、判断题. 的有序树1. 二叉树是度为2 的结点。2. 完全二叉树一定存在度为1 。3. 对于有N个结点的二叉树，其高度为logn2k -1。．深度为K的二叉树中结点总数≤24 5．对一棵二叉树进行层次遍历时，应借助于一个栈。 6．用树的前序遍历和中序遍历可以导出树的后序遍历。7．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列8．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 9. 二叉树只能用二叉链表表示。 i-1 (i>=1)。层上至少有2个结点10．在二叉树的第i 11．完全二叉树的存储结构通常采用顺序存储结构。 12．度为二的树就是二叉树。 13．霍夫曼树的结点个数不能是偶数。一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。14. ．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。15 答案二、判断题 8.√6. 5.×× 7.√×1. 2.× 3.×4. √ 15.√ 14.×√ 10.9.×× 11.√ 12.×13. 三、填空题 _(1)__，__(2)_，_(3)__三个基本单元组成。1．二叉树由 ，d=4，c=3，__(1)_2．中缀式a+b*3+4*（c-d）对应的前缀式为，若a=1，b=2的运算结果为_(2)__。则后缀式db/cc*a-b*+ ______。3．具有256个结点的完全二叉树的深度为3个度为1的结点，32的结点，4个度为个度为．已知一棵度为43的树有2的结点，则该树有______个叶子结点。至多有___(2)____个结点。个结点，深度为5．k的完全二叉树至少有___(1)____ ______。6．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是则有在一棵二叉树中，．度为零的结点的个数为N0,度为的结点的个数为N2,27N0 =______ 个叶子结点。的完全二叉树至少有．高度为88______。______个叶子结点，则该二叉树的总结点数至少是50．已知二叉树有9 读书破万卷下笔如有神 10．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。 11．具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。 12．哈夫曼树是______。 13．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 14．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为 2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c 的编码是_(2)__。 15．设n为哈夫曼树的叶子结点数目，则该哈夫曼树共有______个结点。0 三.填空题答案 1.(1)根结点(2)左子树(3)右子树 2.(1) ++a*b3*4-cd (2)18 3. 9 4. 12 k-1k-1 5.(1)2 (2)26.n 7. N2+1 8. 64 9. 99 10. ?n/2? 11.N+1 12.带权路径长度最小的二叉树，又称最优二叉树 13.69 14.(1)80 (2)001（不唯一） 15.2n-1 0 第七章练习 一、选择题 1．设无向图的顶点个数为n，则该图最多有（）条边。 2n．0 E．．A．n-1 B．n(n-1)/2 C n(n+1)/2 D2．一 个n个顶点的连通无向图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn； 3．要连通具有n个顶点的有向图，至少需要（）条边。 A．n-l B．n C．n+l D．2n 4．n个结点的完全有向图含有边的数目（）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 5．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通 分量。 A．0 B．1 C．n-1 D．n ）倍，在一个有．在一个无向图中，所有顶点的度数之和等于所有边数（6． 读书破万卷下笔如有神 向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。 A．1/2 B．2 C．1 D．4 7．无向图G=(V,E),其中： V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图 进行深度优先遍历，得到的顶点序列正确的是（）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 8．已知有向图G=(V,E)，其中V={V,V,V,V,V,V,V}， 7416253E={ 3的拓扑序列是（）。 A．V,V,V,V,V,V,V B．V,V,V,V,V,V,V 71134436625275C．V,V,V,V,V,V,V D．V,V,V,V,V,V,V 74252463175631 9．一个有向无环图的拓扑排序序列（）是唯一的。 A．一定 B．不一定 10. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出 现的是（）。 A．G中有弧 C．G中没有弧 三、填空题 1.判断一个无向图是一棵树的条件是______。 2．有向图G的强连通分量是指______。 3．一个连通图的______是一个极小连通子图。 4．具有10个顶点的无向图，边的总数最多为______。 5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。 6. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 ______条弧。 7．在有n个顶点的有向图中，每个顶点的度最大可达______。 8．设G为具有N个顶点的无向连通图，则G中至少有______条边。 9．N个顶点的连通图的生成树含有______条边。 10．有N个顶点的有向图，至少需要量______条弧 才能保证是连通的。 11．右图中的强连通分量的个数为（）个。 12．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。 13. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。 14. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。 } V={a,b,c,d,e 中其，）E，V（G=图向无一知已15. 读书破万卷下笔如有神 E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。 16. 一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G'(V，E'）,V（G'）=V（G），E（G'）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是______。 17. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。 18．构造连通网最小生成树的两个典型算法是______。 19. 有一个用于n个顶点连通带权无向图的算法描述如下： （1）．设集合T1与T2，初始均为空； （2）．在连通图上任选一点加入T1； （3）．以下步骤重复n-1次： a.在i属于T1，j不属于T1的边中选最小权的边； b.该边加入T2。 上述算法完成后，T2中共有______条边，该算法称______算法，T2中的边构成图的______。 20．AOV网中,结点表示______,边表示______。 21. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为______的顶点，并进栈； （2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对 Vk入度处理，处理方法是______； （3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。 二、判断题 1．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（） 2. 有e条边的无向图，在邻接表中有e个结点。（） 3．强连通图的各顶点间均可达。（） 4．强连通分量是无向图的极大强连通子图。（） 5．连通分量指的是有向图中的极大连通子图。（） 6. 十字链表是无向图的一种存储结构。（） 7．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）8．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（） 9. 有向图的邻接矩阵是对称的。（） 10．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（） 11. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（） 12．任何无向图都存在生成树。（） 13. 不同的求最小生成树的方法最后得到的生成树是相同的.（） 14．带权无向图的最小生成树必是唯一的。（） ）（．连通图上各边权值均不相同，则该图的最小生成树是唯一的。15． 读书破万卷下笔如有神 16. 最小生成树问题是构造连通网的最小代价生成树。（） 17．拓扑排序算法把一个无向图中的顶点排成一个有序序列。（） 18. 无环有向图才能进行拓扑排序。（） 19. 有环图也能进行拓扑排序。（） 20．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（）21．AOV网的含义是以边表示活动的网。（） 一.选择题答案 1.B 2.A 3.B 4.D 5.1B 5.2D 6.1B 6.2C 7.D 8.A 9.B 10.D 部分答案解释如下。 1. 不一定是连通图，可能有若干连通分量 12. 只有无向连通图才有生成树 13. 最小生成树不唯一，但最小生成树上权值之和相等 21. AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。 三．填空题答案 1.有n个顶点，n-1条边的无向连通图 2.有向图的极大强连通子图 3. 生成树 4. 45 5. n(n-1)/2 6. n 7. 2(n-1) 8. N-1 9. N-1 10. N 11. 3 12. 度出度 13. 第I列非零元素个数 14.n 2e 15. 深度优先 16.宽度优先遍历 17.队列 18.普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法 19.(1)n-1 (2)普里姆 (3)最小生成树 ）活动间的优先关系2（）活动20.(1． 读书破万卷下笔如有神 21.（1）零（2）V度减1，若V入度己减到零，则V顶点入栈（3）环kkk Chap1 一、选择题 1.算法的计算量的大小称为计算的（）。 A．效率 B.复杂性 C.现实性 D.难度 2.计算机算法指的是（1），它必须具备（2）这三个特性。 (1)A．计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法 (2)A．可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 3.下面关于算法说法错误的是（）。 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 4．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 5．以下数据结构中，哪一个是线性结构（）？ A．广义表 B.二叉树 C.稀疏矩阵 D.串 6．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1TO n DO FOR j:=1TO n DO x:=x+1; n) A．O(2n)B．O(n)C．O(n2)D．O(log 2 7．程序段FOR i:=n-1DOWNTO1DO FOR j:=1TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中n为正整数，则最后一行的语句频度在最坏情况下是（）。 A.O（n） B.O(nlogn) C.O(n3) D.O(n2) 8．以下哪个数据结构不是多型数据类型（） A．栈B．广义表C．有向图D．字符串 9．以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 二、判断题 1．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 2．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。() 3．程序一定是算法。() 4．数据的物理结构是指数据在计算机内的实际存储形式。() 5.数据结构的抽象操作的定义与具体实现有关。() 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。() 第2章线性表 一、选择题 1. 链表不具备的特点是（）。 A．可随机访问任意结点 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件是（）。 ==NULL B. head->next==NULL >next==head !=NULL 3.带头结点的单链表head为空的判定条件是（）。 ==NULL B. head->next==NULL >next==head !=NULL 4．带头结点的双循环链表L为空表的条件是（）。 A．L==NULL B．L->next->==NULL C．L->prior==NULL >next==L 5.非空的循环链表head的尾结点（由P所指向）满足（）。 A．p->next==NULL B．p==NULL C．p->next==head ==head 6.在循环双链表的p所指结点之前插入s所指结点的操作是（）。 A．p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior; B．p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior; C．s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s; D. s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。 A．单链表 B．给出表头指针的单循环链表 C．双链表 D. 带头结点的双循环链表 8.某线性表最常用的操作是在最后一个结点之后插入一个节点或删除第一个结点，故采用（）存储方式最节省运算时间。 A．单链表 B．仅有头结点的单循环链表 C．双链表 D. 仅有尾指针的单循环链表 9.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（）。 A．单链表 B．静态链表 C．线性链表 D. 顺序存储结构 10.如果最常用的操作是取第i个结点及前驱，则采用（）存储方式最节省时间。 A．单链表 B．双链表 C.单循环链表 D.顺序表 11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。 A．O(1) B．O(n) C．O(n*n) D. O(nlog2n) 12.在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行()操作与链表的长度有关。A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 13.设线性表有n个元素，以下算法中，()在顺序表上实现比在链表上实现效率更高。A．输出第i(0<=i<=n-1)个元素值 B．交换第0个元素与第1个元素的值 C. 顺序输出这n个元素的值 D.输出与给定值x相等的元素在线性表中的序号 14.设线性表有2n个元素，算法()，在单链表上实现比在顺序表上实现效率更高。 A．删除所有值为x的元素 B．在最后一个元素的后面插入一个新元素 C. 顺序输出前k个元素 D.交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1) 习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说 法_B__ o A.正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec，中序遍历序 列是debac，它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 数据结构试题及答案 数据结构试题(,)参考答案班别学号姓名成绩一、单项选择(每小题2分，共24分) 1.若某线性表的常用操作是取第i个元素及其前趋元素，则采用( A )存储方式最节省时间 A.顺序表 B.单链表 C.双链表 D.单向循环 B ) 2.串是任意有限个( A.符号构成的序列 B.字符构成的序列 C.符号构成的集合 D.字符构成的集合 3.设矩阵A(aij,1<=i,j<=10)的元素满足: aij<>0(i>=j,1<=i,j<=10),aij =0 (i A.64 B.63 C.31 D.32 7.将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。编号为47的结点X的双亲的编号为( C ) A.24 B.25 C.23 D.2无法确定 8.设有一个无向图G=(V,E)和G'=(V',E')，如果G'为G的生成树，则下面不正确的说法是( D ) A.G'为G的子图 B.G'为G的一个无环子图 C.G'为G的极小连通子图且V'=V D.G'为G的连通分量 1 9.用线性探测法查找闭散列上，可能要探测多个散列地址，这些位置上的键值( D ) A.一定都是同义词 B.一定都不是同义词 C.都相同 D.不一定都是同义词 10.二分查找要求被查找的表是( C ) A.键值有序的链接表 B.链接表但键值不一定有序表 C.键值有序的顺序表 D.顺序表但键值不一定有序表 11.当初始序列已经按键值有序，用直接插入法对其进行排序，需要比较的次数为( B ) 2 A. n B. n-1 C. logn D. nlogn 22 12.堆是一个键值序列{K1,K2,...,Ki,...,Kn},对i=1,2,...,n/2 ，满足 ( A ) ? ? A. Ki<=K2i且Ki<=K2i+1(2i+1<=n) B.Ki 第二章线性表 1、描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。 2、对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i 个结点a i ； (2)定位到第i 个结点的前驱a i-1； (3)定位到尾结点； (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点；(2)在P 结点前插入S 结点；(3)在表首插入S 结点；(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && j 4、设计算法：在顺序表中删除值为e 的元素，删除成功，返回1；否则，返回0。 5、设计一个算法，将一个带头节点的数据域依次为a 1，a 2，…，a n （n ≥3）的单链表的所有节点逆置，即第一个节点的数据域变为a n ，…，最后一个节点的数据域为a 1。（注意：先用自然语言描述算法基本思想，然后用类C++语言描述） int Sqlist 2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i] } } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 第二章习题 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。× 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。× 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。×9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。× 11.线性表中每个元素都有一个直接前驱和一个直接后继。（×） 12.线性表中所有元素的排列顺序必须由小到大或由小到小。（×） 13.静态链表的存储空间在可以改变大小。（×） 14.静态链表既有顺序存储结构的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 15.静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。（） 16.静态链表与动态链表的插入、删除操作类似，不需要做元素的移动。（） 17.线性表的顺序存储结构优于链式结构。（×） 18.在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。（×） 19.在单链表中，可以从头结点开始查找任何一个结点。（） 20.在双链表中，可以从任何一结点开始沿同一方向查找到任何其他结点。（×） 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 ，在任何位置上插入或删除操作都是等概率的。插n．对顺序存储的线性表，设其长度为2． 入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) （n -1）/2 (D) n 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 一、单选题（每题2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？(B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（ D ）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（A）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（D ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为____O(1)_____，在表尾插入元素的时间复杂度为____O n________。 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 《数据结构》第二章练习题 1.单项选择题 2.1链表不具备的特点是（） A 可随机访问任一结点 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与其长度成正比 2.2 不带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.3带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.4 带头结点的双循环链表L为空的条件是（） A L==NULL B l->next->==NULL C L->prior==NULL D L->next==L 2.5 非空的循环单链表head尾结点（由P所指向）满足（) A P->next==NULL B P==NULL C P->next==head D P==head 2.6在双循环链表中的P所指结点之前插入s所指结点的操作是（） A p->prior=s;s->next=p;p->prior>next=s;s->prior=p->prior; B p->prior=s;p->prior>next=s;s->next=p;s->prior=p->prior; C s->next=p;s->prior=p->prior; p->prior=s;p->right->next=s; D s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 2.7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间 A 单链表 B 给出表头指针的单循环链表 C 双链表 D 带头结点的双循环链表 2.8某线性表最常用的操作时在最后一个结点之后插入一个结点或删除第一个结点，故采用（）存储方式最节省运算时间 A 单链表B仅有头结点的单循环链表 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 试卷一 一、单选题（每题 2 分，共20分） 1. 对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 7. 若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 二、填空题（每空1分，共28分） 1. 数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。 2. 队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0_____________。 4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 7. 二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为数据结构第一章试题
数据结构第二章试题
数据结构书面作业练习题
数据结构试题及答案(免费)
数据结构试题及答案
数据结构第二章线性表测试题
数据结构第二章课后习题题解
数据结构试题答案
数据结构第2章基础习题 作业
数据结构习题与答案
数据结构第一章考试题库(含答案)
数据结构试题及答案
(完整版)数据结构课后习题及解析第二章
数据结构考试题库含答案
数据结构第二章练习题 - 副本
数据结构课程作业
数据结构试题及答案修2
相关主题
文本预览