当前位置：文档之家 › 数据结构 练习题

数据结构 练习题

  • 格式：pdf
  • 大小：93.12 KB
  • 文档页数：7

下载文档原格式

  / 7

合集下载

数据结构练习题

数据结构练习题

. . . . .一、单选题第1章绪论1、在数据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构C、线性结构和非线性结构2、算法分析的两个主要方面是A、空间复杂性和时间复杂性C、可读性和文档性3、数据的不可分割的最小单位是B、紧凑结构和非紧凑结构D、内部结构和外部结构B、正确性和简明性D、数据复杂性和程序复杂性A、结点B、数据元素C、数据项D、数据对象4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为A、规则B、集合C、结构D、运算5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是A、问题的规模C、机器执行速度二、判断题1、数据结构是带有结构的数据元素的集合。

2、程序越短，运行的时间就越少。

3、处理同一问题的算法是唯一的。

B、机器代码质量的优劣D、语句的执行次数4、一个完整算法可以没有输入，但必须有输出。

三、填空题1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

2、______________结构的数据元素之间存在一对多的关系。

3、数据结构的形式化定义为(D，S)，其中D 是______________的有限集，S 是 D 上关系的有限集。

4、数据结构在计算机中的______________称为存储结构。

5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此- 1 -得到两种不同的存储结构是______________存储结构和______________存储结构。

6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。

7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。

四、解答题1、设n 为正整数。

数据结构 练习题

数据结构 练习题
A）10 B）110 C）1110 D）1111
6. 已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是
A）E B）F C）G D）J
7. 设结点A有左孩子结点B，右孩子结点C，则在先序遍历、中序遍历、后序遍历这三种基本遍历序列中B一定是C的
图6-2 例6.3附图
6 自测习题
1. 简答题
1. *根据权值（1，2，3，4，5，6），构造哈夫曼树，并计算二叉树的带权路径长度。
2. 请
将下图6-1所示的森林转换成二叉树。
图6-1 简答题2的附图森林
3. *已知一棵二叉树的中序遍历序列为DHBEAIFCGJK，该二叉树的后序遍历序列是HDEBIFJKGCA，现请画出这棵二叉树。
第1章 概述
一、简答题
1．简述以下术语的含义并说明它们之间的关系。
数据类型、数据结构、逻辑结构、存储结构
2．简述算法时间效率和空间效率的概念。
3．简述数据结构课程的目的和意义。
二、选择题
1．以下数据结构中，逻辑结构属于线性结构的是
A）有向图 B）链式栈 C）二叉树 D）二叉排序树
四、算法及分析
1．写出交换两个整型变量值的算法，并分析算法的时间复杂度。
2．写出求n的阶乘 的算法，并分析算法的时间复杂度。
第2章 线性表
一、简答题
1．在处理某个问题时，需要存储的数据总量不能确定，并经常需要进行数据的添加和删除操作，此时应选用哪种存储结构？为什么？
3．设有结点定义
struct node
{ int data;
struct node *next;

数据结构练习题

数据结构练习题
一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它 们之间的 关系 和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D 上的 关系 有限集合。 3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方 面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构 。 5. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 系 ，图形结构中元素之间存在 多对多 关系。 6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前 驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点 。 7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱 结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以 任意多个 。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。 9．数据的存储结构可用2种基本的存储方法表示，它们分别是 顺序存储结构 和连式存储结构 。 10. 数据的运算最常用的有5种，它们分别是 检索、排序、插入、删除、修改 。 11. 一个算法的效率可分为 时间 效率和 空间 效率。
（ × ）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两 个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （ × ）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的 示意图有序。 （ × ）3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元 向前移动。错，链表的结点不会移动，只是指针内容改变。 （ × ）4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （ × ）5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （ × ）6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低， 在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （ × ）7.线性表在物理存储空间中也一定是连续的。 错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （ × ）8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相 邻。 （ × ）9.顺序存储方式只能用于存储线性结构。 错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于 非线性结构，但其最佳存储方式是顺序存储方式。 （ × ）10.线性表的逻辑顺序与存储顺序总是一致的。 错，理由同7。链式存储就无需一致。

数据结构练习附答案

数据结构练习附答案

一、单项选择题1.逻辑关系是指数据元素间的（）A．类型B．存储方式C．结构D．数据项2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A．顺序表 B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front=(front+1)%(m-1)C．front=(front-1)%m D．front=(front+1)%m4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。

A．rear％n==front B．(front+l)％n==rearC．rear％n-1==front D．(rear+l)％n==front5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。

A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。

( )A. 90B. 91C. 92D. 937.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。

A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。

A. nB. 2nC. n/2D. n*n9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。

A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法10.对线性表进行二分查找时，要求线性表必须( )。

数据结构练习题及答案

数据结构练习题及答案

数据结构练习题（一）一、单选题1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( )。

A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中( )是非线性结构。

A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组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．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( )。

A．2k-1 +1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。

A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。

A．1 B．2 C．3 D．49.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。

数据结构练习题

数据结构练习题

后， rear 的值为 ， front 的值 为 ，当前队列的 长 度 为 。 14.设循环队列的容量为 40(序号从 0 到 39)， 现经过一系列的入队和出队运算后， 有: ① front=11，rear=19; ② front=19，rear=11； 问在这两种情况下，循环队列中各有元素多少个？ 15.写出下列程序段的输出结果(队列中的元素类型 QElem Type 为 char)。 void main( ){ Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y); printf(y); }; printf(x); } 16.简述以下算法的功能(栈和队列的元素类型均为 int) void algo3(Queue &Q){ Stack S; int d; InitStack(S); while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } }
第一章 绪论
1.数据结构是研究数据的( )以及它们之间的相互关系。 A.物理结构，逻辑结构 B.理想结构，抽象结构 C.理想结构，物理结构 D.抽象结构，逻辑结构 2.从逻辑上可以把数据结构分为( )两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 3.以下不属于算法要素的是( ) A. 有穷性 B. 可行性 C. 可读性 D. 输入 4.算法的时间复杂度与( )有关。 A.问题规模 B.计算机硬件性能 C.编译程序质 D.程序设计语言 2 5.某算法的时间复杂度为 O(n )，表明该算法的( ) 2 A.问题规模是 n B.执行时间等于 n2 C.执行时间与 n2 成正比 D.问题规模与 n2 成正比 6.假设某算法语句总的执行次数为 T(n)=2n³ +n² ,那么该算法的时间复杂性量级为 ( ) A.O(2) B.O(n³ ) C.O(n² ) D.O(1) 7.设 n 为正整数，下面程序段中标号为①的语句频度为 。 int i = 1; k = 0; while ( i <= n-1 ){ k += 10*i; ① i++; } 8.程序段 for( i=0; i<n; i++ ) for( j=0; j<i; j++ ) k++; 中，语句 k++的执行次数为 。 9.在下面的程序段中，对 x 的赋值语句的渐进时间复杂度为 。 for(k=1;k<=n;k++) for(j=1;j<=n;j++) x=x+1; 10.下面程序段的时间复杂度为 。 void fun(int n) { int y=1; while (y <=n) y=2*y; }

数据结构练习题

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B3. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)4. 以下数据结构中，哪一个是线性结构（）A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串5. 在下面的程序段中，对x的赋值语句的频度为（）for (int i=1; i<=n; i++)for (int j=1; i<=n;j++)x+=1;A．2n B．n C．n2D．log2n二、判断题1. 数据元素是数据的最小单位。

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

( )3. 数据的物理结构是指数据在计算机内的实际存储形式。

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

( )5. 数据结构的抽象操作的定义与具体实现有关。

( )三、填空1．数据的物理结构包括的表示和的表示2. 数据结构中的逻辑结构有（1），（2），（3），__（4）_四种。

3. 一个数据结构在计算机中称为存储结构4. 数据结构中评价算法的两个重要指标是5. 一个算法具有5个特性: （1）、（2）、（3），有零个或多个输入、有一个或多个输出。

6. 已知如下程序段, 语句1执行的频度为（1）；语句2执行的频度为（2）；for (int i=n; i>=1; i--) {x = x+1; //语句1for (int j = n; j>=1; j--)y = y+1; //语句2}7. 下面程序段中带下划线的语句的执行次数的渐进时间复杂度为int i=1; while (i<n) i = i*2;四、应用题1. 解释和比较以下各组概念（1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型（4）算法的时间复杂性（5）算法（6）频度2. 若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？3. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好.4. 下列算法对一n位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。

《数据结构》练习题库

二、填空题1. 线性表是一种典型的___线性______结构。

2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移__n-i+1__个元素。

3. 顺序表中逻辑上相邻的元素的物理位置__相邻______。

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

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

6. 在双向链表中，每个结点含有两个指针域，一个指向___前趋____结点，另一个指向____后继___结点。

7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用___顺序__存储结构为宜。

相反，当经常进行的是插入和删除操作时，则采用__链接___存储结构为宜。

8. 顺序表中逻辑上相邻的元素，物理位置__一定_____相邻，单链表中逻辑上相邻的元素，物理位置___不一定____相邻。

9. 线性表、栈和队列都是__线性_____结构，可以在线性表的___任何___位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在___队尾____位置插入元素和在___队头____位置删除元素。

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

11. 在单链表中设置头结点的作用是__使空表和非空表统一______。

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

13. 对于一个栈作进栈运算时，应先判别栈是否为__栈满_____，作退栈运算时，应先判别栈是否为_栈空______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为___m____。

数据结构练习题及参考答案

《数据结构》练习题一、解答题（共50分）1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所示。

请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算WPL 。

2. （8分）若一棵二叉树中序遍历和后序遍历序列分别为：DBEHGAFIC 和DHGEBIFCA 。

试画出这棵二叉树，并写出其先序遍历和层序遍历序列。

3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的顶点表按字母a 、b 、c 、d 、e 、f 、g 、h 的顺序依次存储，邻接表的边表结点按顶点的下标由小到大链接）。

请画出其邻接表，并写出从顶点f 出发，分别进行深度和广度优先遍历的序列，写出用Prime 方法从顶点c开始产生最小生成树的边的序列。

4.（8分）已知键值序列为(44，39，67，25， 52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。

⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（ ）。

⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81) ，用堆（大根堆）排序方法进行排序，第一趟的排序结果是（ ）。

二、完善程序（共20分，每空2分）1.假设一组递减有序的原始数据存储在数组r 中，存放元素的下标下限为low,下标上字符 出现频率 a 0.05 b 0.03 c 0.24 d 0.16 e 0.08 f 0.24 g 0.18 h0.02限为high,以下是在数组中查找数值为k的折半查找算法。

请填空完善程序。

int BinSearch(int r[ ], int low,int high,int k){ int l,h,m;l= low; h= high;while ( ⑴){m= ⑵;if (k < r[m]) ⑶;else if (k > r[m]) ⑷;else return m;}return 0;}2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。

《数据结构》练习题一、选择题a是...

《数据结构》练习题一、选择题1．一个数组元素a[i]与（ A ）的表示等价。

A ．*（a+i ） B ．a+i C ．*a+i D ．&a+ia 是存储的是数组首地址，*a 指向的就是数组第一个元素a[0],所以*（a+i ）的地址和a[i]的地址一样。

数组和指针在一定程度上本质是一样的。

2．当利用大小为N 的数组顺序存储一个栈时，假定用top==N 表示栈空，则退栈时，修改top 指针的语句是（ A ）。

A ．top++;B ．top=0;C ．top--;D ．top=N; 3．队列的删除操作是在（ A ）进行。

A ．队首B ．队尾C ．队前D ．队后队列删除元素是在队首进行，队列是进先先出，相对来说，队首元素是最先进入队列的，因此出队应该是在队首进行。

队列其实就和我们平时排队一样的4．二叉树上叶子结点数等于（ C ）。

A ．分支结点数加1B ．单分支结点数加1C ．双分支结点数加1D ．双分支结点数减15．哈希冲突是指（ D ）。

A ．两个元素具有相同的序号B ．两个元素的键值不同，而其他属性相同C ．数据元素太多D ．不同键值的元素对应于相同的存储地址6．由权值分别为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ A ）。

A ．51B ．23C ．53D ．742310 135 56 72 3(2+3)*3+5*2+(6+7)*2=517．某程序的时间复杂度为)log log 1003(22n n n n +⨯+，其数量级表示为（ B ）。

A ．O(n)B ．)log (2n n OC ．O(100)D ．)(log 2n O8．从二叉搜索树中查找一个元素时，其时间复杂度大致为（ C ）。

A ．O(n)B ．O(1)C ．)(log 2n OD ．)(2n O9．在线性表的散列存储中，若用m 表示散列表的长度，n 表示待散列存储的元素的个数，则装填因子α等于（ A ）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
4. 填空题 1. 采用二叉链式存储结构，具有n个结点的二叉树中，一共有 [1] 个指针域，其中 [2] 个指针域为空。
2. 一棵非空的二叉树，其第i层上最多有＿＿＿＿＿个结点。 3. 满二叉树是一棵深度为k的且恰好有＿＿＿＿＿个结点的二叉树。 4. 将一棵完全二叉树按层次编号，对任一编号为i的结点有：如该结点有左孩子，则其编 号为 [1] ；如该结点有右孩子，则其编号为 [2] 。 5. 设一棵二叉树中只有叶子结点和左、右子树都非空的结点，如果叶子结点的个数是m， 则左、右子树都非空的结点个数是＿＿＿＿＿ 6. 设有一棵树（如图6-3所示），请回答下列问题： 根结点是＿[1]＿；叶子结点有＿＿[2] ＿＿；Ｅ的双亲是＿[3]＿；Ｆ的祖先是＿[4] ＿；Ｇ的孩子是＿[5]＿；Ｄ的孩子是＿[6]＿；Ｅ的子孙有＿＿[7]＿＿；Ｄ的兄弟是 ＿[8]＿；Ｂ的兄弟是＿[9]＿；结点Ｈ的层数是＿[10]＿；树的深度是＿[11]＿；Ｅ为根 的子树深度是＿[12]＿；这棵树的度是＿[13]＿。
A）O(1)
B）O(n)
C）
O(n2)
D）O(log2n)
4．在长度为n的顺序表中，若要删除第i（1≤i≤n）个元素，则需要向前移动的元素的次
数为
A）i
B）n-i
C）n-i+1
D）n-i-1
5．在长度为n的顺序表中第i（1≤i≤n）个位置上插入一个元素时，为留出插入位置所需
移动元素的次数为
A）n-i
图6-2 例6.3附图
6 自测习题 1. 简答题 1. *根据权值（1，2，3，4，5，6），构造哈夫曼树，并计算二叉树的带权路径长度。 2. 请 将下图6-1所示的森林转换成二叉树。
图6-1 简答题2的附图森林
3. *已知一棵二叉树的中序遍历序列为DHBEAIFCGJK，该二叉树的后序遍历序列是 HDEBIFJKGCA，现请画出这棵二叉树。 4. *给出图6-2所示的一棵二叉树的顺序存储结构、二叉链表和三叉链表存储结构。
7. 在单链表p结点之后插入s结点的操作是：_______。
四、算法设计
*1．有序顺序表、单链表的插入算法。
设线性表有序（按由小到大的顺序排列），分别编写顺序表、带有头结点的单链表的插入
算法，使插入值为x的元素后线性表仍保持有序的算法。
*2．单链表的输出算法：输出带有头结点的单向链表中各结点的值。
*3．顺序表、单链表的删除算法：分别编写顺序表、带有头结点的单链表中删除所有值为
图6-3 填空题6的附图
第6章树 例题分析与解答 例6.1 设有一棵树的度为3，其中度为1、2、3的结点个数分别为5、2、1、，则这棵树中 叶子结点的个数为 A）4 B）5 C）6 D）7 【解答】 设这棵树中叶子结点的个数为n0，根据已知，在这棵树中结点的总数n=5+2+1+ n0=8+ n0；此外，从树的性质又可知，度为1的结点有1个分?В 任?2的结点有2个分支，度为 3的结点则有3个分支，因此这棵树的总的分支数为：1*5+2*2+3*1=12，而一棵有n个结点 的树，只允许有n-1个分支存在，所以又有：n-1=12，即n=13，将n代入上式，则n0=5。所 以，选项B是正确的。
9. 已知线性表（a1 a2 a3 ...an）按顺序存于内存中，每个元素都是整数，试设计用最
少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x .
..x）变为（-x,-x,-x...x,x,x），其中x>0。
第三章 请设计算法： 利用栈结构和栈的基本运算将一个十进制数转换成指定的k（k=2~9）进制数。
A）数据元素是有独立含义的数据最小单位 B）数据元素是描述数据的基本单位
C）数据元素可以称做结点
D）数据元素可以称做记录
3．设问题的规模为n，分析以下程序段：
a=10; b=100;
while (b>0)
{ a++;
b- -;
}
以上程序段的算法时间复杂度是
A）O(1)
B）O(n)
C）O(n2)
D）O( )
2、简述头指针、头结点的区别，以及头指针和头结点的作用。
二、选择题
1．以下链表结构中，从当前结点出发能够访问到任一结点的是
A）单向链表和双向链表
B）双向链表和循环链表
C）单向链表和循环链表
D）单向链表、双向链表
和循环链表
2．线性表是具有n个
的有限序列。
A）数据项
B）数据元素
C）表元素
D）字符
3．若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为
图2-2 填空题3附图
函数sum的功能是：计算非空的链表中各结点数据域之和，并用函数值返回该结果。请填
Hale Waihona Puke 空。int sum(struct node *head)
{ int s=0;
struct node *p;
p=head->next;
do
7．有序顺序表、有序单链表的归并算法。
分别编写将两个有序顺序表、两个带有头结点的单链表归并成一个有序线性表（按由小到
大的顺序排列）的归并算法，要求尽量利用原来的存储空间。
8. 设L为单链表的头结点地址，单链表中数据结点的数据都是正整数且无相同的，试设计
利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。
x的结点的算法。
4．顺序表、单链表的逆置算法：分别实现顺序表、带有头结点的单链表的逆置操作。即
将线性表（a1,a2,...an）逆置为（an,...a2,a1）。
5．顺序表、单链表的查找算法：分别实现顺序表、带有头结点的单链表中查找最后一个
值为x的结点位置的算法。
6．写出求单链表、循环单链表表长的算法。
B）i
C）n-i+1
D）n-i-1
6．下述哪一条是顺序存储结构的优点？
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结
构的存储表示
7．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，
则利用（ ）存储方式最节省时间。
A．顺序表
B．双链表
C．带头结点的双循环链表 D．单循环链表
2．线性表L=( a1,a2,...an)用数组存储。假定删除表中任一元素的概率相同，则删除一
个元素平均需要移动的元素个数是
。
3．设有结点定义
struct node
{ int data;
struct node *next;
}; 且已建立如图2-2所示的带有头结点的单向链表：
例6.3 假设已知某二叉树的前序遍历序列和后序遍历序列，则根据已知条件一定能唯一地 确定出一棵二叉树。请问这句话对吗？ 【解答】错。 例如某二叉树的前序遍历序列为：AB；后序遍历序列为BA；根据条件可以画出如图 6-2所示的两棵不同的二叉树。因此已知前序和后序遍历序列，并不能唯一地确定出一棵 二叉树。
例6.2 一棵权值为1，2，3，4，5，6的哈夫曼树，如图6-1所示，其中方框为带权的叶子 结点，圆圈为非叶子结点。则该哈夫曼树的带权路径长度WPL，及权值为1的叶子结点的高 度分别为 A）51；5 B）72；5 C）51；4 D）72；4
图6-1 例6.2附图哈夫曼树 【解答】 其 中n表示叶子结点的数目，wi表示叶结点的权值，li表示根到叶结点之间的路径长度。因 此有： WPL= (1+2)*4+3*3+ (4+5+6)*2=51。权值为1的叶结点的高度很明显为5。所以，本题的答 案为选项A。
三、填空题
1．数据结构包括的三方面内容分别是：数据的 [1] 、数据的 [2] 和数据的运算。
2．数据元素是数据的基本单位，在某些情况下也可以称为 [1] 、 [2] 和 [3] 。
3．数据逻辑结构的4种基本形态包括集合结构、 [1] 结构、 [2] 结构和 [3] 结
构。
4．一个正确的算法应该具有5个特性：[1] 、 [2] 、[3] 、 [4] 和 [5] 。
{ s=s+ [1] ;
p=p->next;
}
while ( p!= [2] );
return s;
}
4. 带头结点的双循环链表L中只有一个数据结点的判定条件是：________。
5. 在单链表L中，指针p所指结点有后继结点的判定条件是：__ 。
6. 带头结点的单循环链表L为空表的条件是：________。
图6-2 简答题4的附图二叉树 2. 判断题 1. 由树转化为二叉树，其根结点的右子树总是空的。 （ ） 2. 若有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树 的中序遍历序列中的第一个结点。 （ ） 3. 若一个树叶是某二叉树的前序遍历序列中的最后一个结点，则它也一定是这棵二叉树 的中序遍历序列中的最后一个结点。 （ ） 4. 若一个树叶是某二叉树的中序遍历序列中的最后一个结点，则它也一定是这棵二叉树 的前序遍历序列中的最后一个结点。 （ ） 5. 在二叉树中，具有一个子女的父结点，在中序遍历序列中没有后继结点。而具有两个 子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。（ ） 6. 虽然已知二叉树的前序遍历和中序遍历序列，但还不能唯一确定出这棵二叉树，因为 并不知道二叉树的根结点是哪一个。 （ ） 7. 在满二叉树中，存在度为1的结点。 （ ） 8. 在任意一棵二叉树中，终端结点的个数等于度为２的结点个数加１。 （ ） 9. 前序遍历序列与中序遍历序列完全相同的二叉树有：空二叉树或任一结点均无左子树 的非空二叉树。 （ ） 3.选择题 1. 如果结点A是结点B的双亲，而且结点Ｂ有４个兄弟，则结点A的度是 A）2 B）3 C）4 D）5 2. 设有一棵二叉树，其１度结点有m个，２度结点有n个，则该二叉树的结点总数为 A）m+n B）2*m+n C）m+2*n D）m+2*n+1 3. 设有一棵二叉树，其先序遍历序列是：ABCDEFG，中序遍历序列是：CBDAFEG，则该二 叉树的后序遍历序列是 A）CDBFGEA B）CDFGBEA C）CDBAFGE D）CDBFEGA 4. 设有13个值，由它们组成一棵哈夫曼树，则该哈夫曼树中结点个数共有。 A）13 B）12 C）26 D）25 5. 设电文中出现的字母为A、B、C、D和E，每个字母在电文中出现的次数分别为：6， 23，3，5和12，按哈夫曼编码，则字母C的编码应是 A）10 B）110 C）1110 D）1111 6. 已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根 的右子树的根是 A）E B）F C）G D）J 7. 设结点A有左孩子结点B，右孩子结点C，则在先序遍历、中序遍历、后序遍历这三种基 本遍历序列中B一定是C的 A） 前驱 B）后继 C）相邻结点 D）不相邻结点