第6章树和二叉树
一、选择题（每小题1分，共10分）
1.以下数据结构中，（ A ）是非线性数据结构。
A.树
B.线性表
C.队列
D.栈
2.在一棵二叉树中第五层上的结点数最多为（ B ）。
A.8
B.15
C.16
D.32
3. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。
A. CBEFDA
B. FEDCBA
C. CBEDFA
D. 不定
4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( B ）。
A.9
B.11
C.15
D.不确定
5.给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（D ）。
A. LRN
B. NRL
C. RLN
D. RNL
6.在下列存储形式中，哪一个不是树的存储形式？（ D ）
A.双亲表示法
B.孩子表示法
C.孩子兄弟表示法
D.顺序存储表示法
7.有n个叶子的哈夫曼树的结点总数为（D ）。
A．不确定B．2n C．2n+1 D．2n-1
8.设i为n个结点的完全二叉树结点编号，i=1，2，3...n；若i≤（n-1）/2时，结点i的右孩子为（ B ）
A.2i
B.2i+1
C.2i-1
D.i+1
9. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ C ）。
A.23
B.37
C.44
D.46
10.一棵具有n个结点的完全二叉树的树高度（深度）是（ A ）。
A. +1
B. log2n+1
C.
D. log2n-1
11.由权值分别为7，9，4，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。
A.36
B.60
C.48
D.53
12.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。
A. 24
B. 71
C. 48
D. 53
13.具有35个结点的完全二叉树的深度为( B )。
A. 5
B. 6
C. 7
D. 8
14.由权值分别为３,８,６,２,５的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）．
A．24 B．55 C．72 D．53
15.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序( A )。
A．不发生改变 B．发生改变 C．不能确定 D．以上都不对
16.具有10个叶子结点的二叉树中有( B )个度为2的结点。
A．8 B．9 C．10 D．11
二、判断题（每小题1分，共10分）
1.完全二叉树中，若一个结点没有左孩子，则它必是树叶。（对）
2.二叉树的遍历结果不是唯一的。（对）
3.二叉树中序线索化后，不存在空指针域。（对）
4.在二叉树的第i层上至少有2i-1个结点(i>=1)。（错）
5.设T为哈夫曼树，具有5个叶结点，树T的高度最高可以是4。(错)
6.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。（错）
7.有n个叶子结点的哈夫曼树所具有的结点数为2n。（错）。
8.用树的前序遍历和中序遍历可以导出树的后序遍历。( 错)
9．二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。（√）
10．度为2 的有序树是二叉树。（×）
11．二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（√）
12．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（×）
13．若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。（×）14．在哈夫曼树中，权值最小的结点离根结点最近。( ×)
三、填空题（每空1分，共10分）
1.具有n个结点的完全二叉树的深度为。+1
2.设只含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为，最小结点数为。2k-1、k
3.将一棵树转化为二叉树时，此二叉树的根节点的右子树为。空树
四、简答题（共10分）
1.满二叉树和完全二叉树有什么区别？
答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个叶子结点，满二叉树是完全二叉树的一个特例。
2.画出二叉树的五种基本形态。
答：二叉树的五种基本形态为：
3.在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。
4.什么是哈夫曼（Huffman）树？
答：设有n个权值{w1,w2,……w n}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为w i,则带权路径长度WPL最小的二叉树叫哈夫曼树或最优二叉树。
或者：又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。
五、应用题（共40分）
1.（8分）已知一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G),
(D,H),(D,I),(D,J),(A,B),(A,C),(A,D))画出这棵树，并回答下列问题：
(1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？
(2)树的度是多少？各个结点的度是多少？
(3)树的深度是多少？各个结点的层数是多少？以结点Ｇ为根的子树的深度是多少？
2.
写出先序、中序、后序、层次遍历该二叉树时访问结点的顺序。
3.（5分）对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，证明：n0=n2+1。
4.叙述并证明二叉树的性质3。
5.（8分）已知一棵二叉树如下，
（1）请分别写出按前序、中序、后序和层次遍历时得到的结点序列。
（2）如果此二叉树由森林转换得到，请画出原森林中的各棵树。
6.（8分）画出由下列序列得到的二叉树以及由此二叉树转化的森林：先序：EBADCFHGIKJ；中序：ABCDEFGHIJK。
7.有二叉树中序序列为：ABCEFGHD，后序序列为：ABFHGEDC，请画出此二叉树，并写出二叉树的先序遍历序列和层次遍历序列。
8.（8分）二叉树T的前序遍历序列和中次遍历序列分别是ABCDEFG和CBEDAFG，试画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。
9.（6分）二叉树的先序序列为EBADCFHGIKJ；二叉树的中序序列为ABCDEFGHIJK，请画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。
10.（8分）设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C
请画出该二叉树，并将这棵二叉树转换成对应的树（或森林）。
11.（8分）设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。并写出后序和层次遍历序列。
12.（6分）设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。
13.（8分）假设字符a,b,c,d,e,f,g,h的使用频度分别是0.15,0.19,0.07,0.08,0.04,0.23，0.13，0.11画出哈夫曼树并写出a,b,c,d,e,f,g,h的Huffman（哈夫曼）编码。
14.（8分）假设字符a,b,c,d,e,f的使用频度分0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。
15.（8分）假设字符a,b,c,d,e,f的使用频度分别是0.07,0.10,0.12,0.16,0.25,0.30，构造哈夫曼树并写出a,b,c,d,e,f的哈夫曼编码。
16.（6分）试分别画出具有三个结点的树和三个结点的二叉树的不同形态。
17.请画出下图所示的树所对应的二叉树。
答案：
18.（6分）请画出与下列二叉树对应的森林。
19.已知一棵树边的集合为{
（1）哪个是根结点？（2）哪些是叶子结点？哪些是分支结点？（3）哪个是结点G的双亲结点？（4）哪些是结点G的祖先？（5）哪些是结点G的孩子？
（6）哪些是结点E的子孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？
（8）结点B和N的层次号分别是多少？（9）树的深度是多少？
（10）以结点C为根的子树的深度是多少？
20.假设在树中，结点x是结点y的双亲时，用（x，y）来表示树边。已知一棵树边的集合为：{（i，m），（i，n），（e，i），（b，e），（b，d），（a，b），（g，j），（g，k），（c，g），（c，f），（h，l），（c，h），（a，c）}。用树形表示法画出此树，并回答下列问题：
（1）哪个是根结点：（2）哪些是叶结点？（3）哪个是g的双亲？
（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？
（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次各是多少？
（9）树的深度是多少？（10）以结点c为根的子树的深度是多少？
（11）树的度数是多少？
21.已知一棵树边的结点为（I,M），(I，N),(E，I),(B，E)，(B，D),(C，B),(G，L)，(G，K)，(A，G)，(A，F),(H，J)，(A，H)，(C，A)}，试画出这棵树，并回答下列问题：
(1)哪个是根结点？
(2)哪些是叶子结点？
(3)树的深度是多少？
六、算法题（共12分）
1.编写计算二叉树深度的算法(二叉树的深度也叫二叉树的高度)。
答：int Depth (BiTree T )
{ // 返回二叉树的深度
if (T ) {
depthLeft = Depth( T->lchild );//求左子树的深度
depthRight= Depth( T->rchild ); //求右子树的深度
depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight);
//深度的最大值+1
}
else depthval = 0;
return depthval;
}
2.编写算法：统计一个二叉树中所有叶子结点的数目。
答：void CountLeaf (BiTree T, int& count)
{//在实际使用时，count作为全局变量，其初始值为0
if ( T ) {
if ((!T->lchild)&& (!T->rchild))
count++; // 对叶子结点计数
CountLeaf( T->lchild, count);
CountLeaf( T->rchild, count);
} // if
} // CountLeaf
参考题：
3. 编写算法先序、中序、后序递归遍历二叉树的算法
4. 编写中序非递归遍历二叉树的算法。
5. 试以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法。
一、单选题（每题 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章线性表 一、选择题 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)
第二章线性表 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
第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】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(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为
一、单选题（每题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.数据结构这门学科是针对什么问题而产生的（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. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)
《数据结构》第二章练习题 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仅有头结点的单循环链表
第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 试卷一 一、单选题（每题 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 ]元素的左孩子元素为________,右孩子元素为 一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 数据结构试题及答案 一、选择题（每小题2分，共20分），每个题的备选答案中，只有一个是正确的，请将答案填写在试题的括号中。 1、对顺序存储的线性表，设其长度为20，在任何位置上插入或删除操作都是 等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 A．10 B．9 C．11 D．12 2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 3、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（ B ）语句修改top指针。 A．top++ B．top-- C．top = 0 D．top 4、设入栈顺序为A，B，C，D，E，则出栈序列不可能是（ C ）。A．EDCBA B．ABCDE C．ADEBC D．ABDEC 5、已知关键字序列（46, 79, 56, 38, 40, 84），采用快速排序（以位于最左位 置的关键字为基准）得到的第一次划分结果为：（ A ） A．{ 40, 38, 46, 56, 79, 84 } B．{ 38, 46, 79, 56, 40, 84 } C．{ 38, 46, 56, 79, 40, 84 } D．{ 40, 38, 46, 79, 56, 84 } 6、一个有n个顶点和n条边的无向图一定是（ C ）。 A．不连通的 B．连通的 C．有环的 D．无环的 7、在一棵具有n个结点的二叉树的第i层上，最多具有（ B ）个结点。 A．2i B．2i-1 C．2i+1 D．2n 8、对线性表采用折半查找法，该线性表必须（ B ）。 A．采用顺序存储结构B．采用顺序存储结构，且元素按值有序 C．采用链式存储结构 D．采用链式存储结构，且元素按值有序 9、在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ C ）。A．?(n-1)/2? B．?n/2? C．?n/2? D．?n/2? -1 10、在一个无向图中，所有顶点的度数之和等于所有边数的 ( D ) 倍。 A．3 B．1/2 C．1 D．2 二、填空题（每小题2分，共20分），请将正确的结果，填写在试题的横线上。 1、带头结点的循环链表L为空的条件是。 2、序列A={12, 70, 33, 65, 24, 56}给出对应于序列A的大顶堆HA（以线性数 组表示）。 3、每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________ 排序。 4、设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front = = Q.rear，则队列的长度 为。 5、已知数组A[0..11][0..8]按行优先存储，每个元素占有5个存储单元，且 A[0][0]的地址为1000（十进制），则A[6][7]的地址为________________。 6、已知广义表A=(a，()，(b，(c)))，则其深度为。 7、在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6 个，则叶子结点数为__ ____个。 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三） （四） （五） （六） （七 ）（八 ） （九 ） （十 ） 9 12 15 17 19 21 24 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三 ） （四 ） （五 ） （六） （七） （八） （九） （十 ） 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题 栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 用链接方式存储的队列，在进行插入运算时 (C ). 头、尾指针都要修改 头、尾指针可能都要修改 (D ) 线性表 2分，共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n]，假设 个空间，问 676(10)，每个元素占 制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置？脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ） 。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素 乙间无联系的数 据 元素之 f k-1 D. 2 A[19]中，第一个元素放 A[1]中，现进行二 分查找，则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，若选用 H (K ) =K %9作为散列函数，则散列地址为 1的元素有(D )个， A . 1 B . 2 C . 3 10. 设有6个结点的无向图，该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分，共26分) 1.通常从四个方面评价算法的质量： _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个，树的深度为 ____________ ，树的度为 ___________ 。 .4 条边才能确保是一个连通图。 正确性 易读性 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。 1.1. 一元稀疏多项式的求导算法 写出一元稀疏多项式的求导算法，用带表头结点的单链表存储该一元稀疏多项式，Lb为头指针，用类C语言描述该求导算法，不另行开辟存储空间，删除无用结点，并分析算法的时间复杂度。该链表的数据结构如下： typedef struct LNode{ float coe; //系数 int exp; //指数 struct LNode *next; //指针 } LNode , *LinkList ; 求导算法如下： void Differential(LinkList &Lb) { //求导算法 pre=Lb; p=pre->next; while ( p ) { if ( p->exp != 0 )//指数不等于零 { p->coe = p->coe * p->exp ; p->exp = p->exp – 1 ; pre = pre->next ; } else//指数等于零 { pre->next = p->next ; free ( p ); } p = pre->next ; } } 时间复杂度为: O(n) 1.2. 单链表存储结构的排序算法 排序算法：将一组整数排序成非递减有序序列。用带头结点的单链表存储，L为头指针，用类C语言写出该排序算法，不另行开辟存储空间，并分析算法的时间复杂度。该单链表的数据结构如下： typedef struct LNode{ int data; //数据域 struct LNode *next; //指针域 } LNode , *LinkList ; void Sort(LinkList &L) { //排序算法如下：将L排序成非递减单链表 q=L; p=q->next->next; q->next->next=NULL; while(p) { While(q->next && p->data >= q->next->data) q=q->next; s=p->next; p->next=q->next; q->next=p; p=s; q=L; } }//sort 好风光好感动1、线性表的逻辑顺序与物理顺序总是一致的。( x ) 2、线性表的顺序存储表示优于链式存储表示。( X ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( v ) 4、二维数组是其数组元素为线性表的线性表。( v ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( x ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( v ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（x ） 8、线性的数据结构可以顺序存储，也可以存储。非线性的数据结构只能存储。（x ） 9、栈和队列逻辑上都是线性表。（v ） 10、单链表从任何一个结点出发，都能访问到所有结点（v ） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（x ） 12、快速排序是排序算法中最快的一种。（x ） 13、多维数组是向量的推广。（x） 14、一般树和二叉树的结点数目都可以为0。（v） 15、直接选择排序是一种不稳定的排序方法。（x ） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（v ） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（x ） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（x ） 19、堆栈在数据中的存储原则是先进先出。（x ） 20、队列在数据中的存储原则是后进先出。（x ） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（x ） 22、哈夫曼树一定是满二叉树。（x ） 23、程序是用计算机语言表述的算法。（v） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（v ） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（v ） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（v ） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（x ） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（v ） 29、希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。（v ）数据结构试题及答案修2
数据结构试题及答案
数据结构试题及答案.docx
十套数据结构试题与答案
数据结构试卷及答案压缩版
数据结构第2章 链表 练习题
数据结构试题及答案
相关主题
文本预览