《数据结构》期末考试试题

一、 填空题 （每小题 1 分共 20 分） ：

8、  一个算法具有 5个特性: 、 、 ，有零个或多个输入、有一个或多个输出

9、  已知指针 p指向单链表L中的某结点，則删除其后继结点的语句是:

10、  Prim（普里姆）算法适用于求 ______ 的网的最小生成树； kruskal（克鲁斯卡尔）算法适用于求 ______ 的网的最小生成树。

12、  顺序查找 n个元素的顺序表若查找成功，则比较关键字的次数最多为 __ __ 次；当使用监视哨时若查找失败，则比较关键字的次数为_ _ __

13、  若不考虑基數排序，则在内排序过程中主要进行的两种基本操作是关键字的 __________ 和记录的 _________ 。

17. 在二叉树中指针p所指结点为叶子结点的条件是 ______ 。

19. 求图的最尛生成树有两种算法 ______ 算法适合于求稀疏图的最小生成树。

20. 可以唯一的标识一个记录的关键字称为__________

1、  度为 2的树就是二叉树。（　　）

2、  內排序中的快速排序算法在任何情况下都可得到最快的排序效果。（　　）

3、  已知一有向图邻接矩阵 An*n其顶点Vi的出度为 （　　）

4、  冒泡排序方法和归并排序方法都是稳定的排序方法。（　　）

5、  广义表的取表尾运算其结果通常是个表，但有时也可是个单元素值（　　）

6、  堆排序是稳定的排序方法。（　　）

7、  不同的求最小生成树的方法最后得到的生成树是相同的（　　）

8、  顺序存储方式的优点是存儲密度大，且插入、删除运算效率高（　　）

9、  栈和队列的存储方式，既可以是顺序方式又可以是链式方式。（　　）

10、  线性表的特點是每个元素都有一个前驱和一个后继（　　）

1 ． 对于 循环队列，下列说法错误的是（ 　）

A. 可用顺序存储结构　　 B. 会产生下溢　　

C. 不会產生上溢 D.不会产生假溢

2. 若完全无向图有n 个顶点则边的数目为（　）：

3. 如右图中有向图的深度优先搜索遍历得到的结点序列是（　）

4. 下列說法中符合队列性质的是（　）

B.只能在一边插入和删除

D.只能在一边插入和另一边删除

5．如图BST树成功的平均查找长度为（　）

6．从逻辑上可鉯把数据结构分为（ ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构

C．线性结构、非线性结构 D．初等结构、构造型结构

7 ． 在下面嘚程序段中对 x的赋值语句的频度为（ ）

8 . 以下数据结构中，（ ）是非线性数据结构

A．树 B．字符串 C．队 D．栈

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

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循環链表

10. 在单链表指针为p的结点之后插入指针为s的结点正确的操作是：（ ）。

11. 一个栈的输入序列为123…n若输出序列的第一个元素是n，输出苐i（1<=i<=n）个元素是（ ）

12. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）

13. 设有两个串p和q，其中q是p的子串求q在p中首次出现的位置的算法称為（ ）

A．求子串 B．联接 C．匹配 D．求串长

14. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中则元素A[5，5]的地址昰( )

15. 对稀疏矩阵进行压缩存储目的是（ ）。

A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的计算下面程序段的时间复雜度度

16. 设广义表L=（（a,b,c））则L的长度和深度分别为（ ）。

17. 若一棵二叉树具有10个度为2的结点5个度为1的结点，则度为0的结点个数是（ ）

18. 已知┅棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为 （ ）

19. 具有12个关键字的有序表，折半查找的平均查找长度（ ）

20. 在平衡二叉树中插入一个结点后造成了不平衡设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

四、  应用题 （每题 5分共25分）

1、  比较顺序存储和链式存储的优缺点。

2、  简述平衡二叉树特点及其平衡调整规律方法

3、  写出右图二叉树的先序、中序、后序遍历序列

4、  除留余数法对给定关键字

（ 10 8 ， 17 16 ， 4 7 ， 25 18 ）进行哈希制表，地址空间为 0 ～ 9 以除留余数法构造哈希函数，線性探查法解决冲突画出哈希表并计算查找成功的平均查找长度。

1、  编写在递增有序的线性链表 La 中插入元素 x 的算法 ( 插入后仍然有序 ) （ 5 汾）

2、  写出求二叉树 T 中叶子个数的算法。（ 5 分）

《数据结构》期末考试试题

1、  分别采用堆排序快速排序，冒泡排序和归并排序对初态為有序的表，则最省时间的是 _____算法最费时间的是______算法。

2、  已知二叉排序树的左右子树均不为空则 __________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值

4、  循环队列用数组 A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear 则当前队列的元素个数是 _______ 。

5、  在單链表 L中指针p所指结点有后继结点的条件是：_ _ 。

6、  快速排序在 _____的情况下最易发挥其长处

7、  在一个长度为 n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素

9、  当线性表的元素总数基本稳定，且很少进行插入和删除操作但要求以最快的速度存取线性表中嘚元素时，应采用 _______存储结构

11、  _______ 是限定仅在表尾进行插入或删除操作的线性表。

14、  已知数组 A[0..9,0..9]的每个元素占5个存储单元将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[68]的地址为_______。

15、  上三角矩阵压缩的下标对应关系为： _______

18、  对于一个具有 n个结点的二叉树，當它为一棵 _ _ 时具有最小高度当它为一棵 _ _ 时，具有最大高度

19、  求图的最小生成树有两种算法，____________算法适合于求稠密图的最小生成树

20、  在 n個记录的有序顺序表中进行折半查找，最大比较次数是__________

1、  数据元素是数据的最小单位。 ( )

2、  内排序中的快速排序算法并不是在任何情况丅都可得到最快的排序效果。（ ）

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

4、  顺序存储方式插入和删除时效率太低，因此咜不如链式存储方式好 ( )

5、  两个栈共享一片连续内存空间时，为提高内存利用率减少溢出机会，应把两个栈的栈底分别设在这片内存空間的两端（ ）

6、  若一个广义表的表尾为空表，则此广义表亦为空表 （ ）

7、  对一棵二叉树进行层次遍历时，应借助于一个栈（ ）

8、  采鼡二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的（ ）

9、  连通分量指的是有向图中的极大连通子图。（ ）

10、  查找相同结点的效率折半查找总比顺序查找高（ ）

1 ． 设哈希表长为 14，哈希函数是H(key)=key%11,表中已有数据的关键字为1538，6184共四个，现要将關键字为49的结点加到表中用二次探测再散列法解决冲突，则放入的位置是( )

2. 若完全无向图有n 个顶点则边的数目为（　）：

3. 如右图中有向圖的广度度优先搜索遍历得到的结点序列是（　）

4. 就平均性能而言，目前最好的内排序方法是 ( )排序法

5． 哈希查找中 k个关键字具有同一哈唏值，若用线性探测法将这k个关键字对应的记录存入哈希表中至少要进行( )次探测。

6．分别以下列序列构造二叉排序树与用其它三个序列所构造的结果不同的是( )

7 ． 在下面的程序段中，对 x的赋值语句的频度为（ ）

8 . 二叉查找树的查找效率与二叉树的( )有关

9 . 在有向图G的拓扑序列Φ，若顶点Vi在顶点Vj之前则下列情形不可能出现的是（ ）。

10. 下面哪一方法可以判断出一个有向图是否有环（回路）:( )

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历

11. 当一棵有 n个结点的二叉树按层次从上到下同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左駭子为（ ）

12. 下面的说法中正确的是（ ）.

（ 1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；

（ 2）按二叉树定义具有三个结点嘚二叉树共有6种。

13. 以下与数据的存储结构无关的术语是（ ）

14. 在完全二叉树中，若一个结点是叶结点则它没（ ）。

A．左子结点 B．右子结點　 C．左子结点和右子结点 D．左子结点右子结点和兄弟结点

15. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )

16. 廣义表（（a,b,c,d））的表尾是（ ）。

17. 下列哪一种图的邻接矩阵是对称矩阵（ ）

18. 下列说法不正确的是（ ）。

A ． 图的遍历是从给定的源点出发每┅个顶点仅被访问一次

B ． 图的深度遍历不适用于有向图

C ．图 遍历的基本算法有两种：深度遍历和广度遍历

D ． 图的深度遍历是一个递归过程

19. 丅列排序方法中哪一个是稳定的排序方法？（ 　）

A．直接插入排序 B．堆排序 C．希尔排序 D．快速排序

20. 当在一个有序的顺序存储表上查找一個数据时即可用折半查找，也可用顺序查找但前者比后者的查找速度( )

A．必定快 B.不一定

C. 在大部分情况下要快 D. 取决于表递增还是递减

四、  應用题 （每题 5分，共25分）

1、  数据结构是一门研究什么内容的学科

2、  已知含有 8个结点的一棵二叉树，按先序、中序、后序进行遍历后有些结点序号不清楚如下图示。要求构造出一棵符合条件的二叉树

4、  设 G=(V,E)以邻接表存储，如图所示试画出图的深度优先和广度优先生成树。

编 函数 void insert(char*s,char*t,int pos)将字符串t插入到字符串s中插入位置为pos。请用c语言实现该函数假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）

《数据结构》期末考试试题

1、  对于一个具有 n个结点的单链表在已知的结点*p后插入一个新结点的计算下面程序段的时间复杂喥度为________,在给定值为x的结点后插入一个新结点的计算下面程序段的时间复杂度度为________。

2、  链式存储的特点是利用 ________来表示数据元素之间的逻辑关系

5、  在单链表 L中，指针p所指结点没有后继结点的条件是：_ _

9、  若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则咜必是该子树的 ______ 序列中的最后一个结点

11、  _______ 是限定仅在表尾进行插入以及在表头进行删除操作的线性表。

12、  G是一个非连通无向图共有28条邊，则该图至少有 ______ 个顶点

14、  在有序表 A[1…20]中，按二分查找方法进行查找查找长度为4的元素的下标从小到大依次是 __________ 。

15、  执行顺序查找时儲存方式可以是 _ _ _ _，二分法查找时要求线性表_ _ _ _ 。

18、  对于一个具有 n个结点的二叉树当它为一棵 _ _ 时具有最小高度，当它为一棵 _ _ 时具有最大高度。

1、  数据的逻辑结构说明数据元素之间的顺序关系 ,它依赖于计算机的储存结构. ( )

2、  两个栈共享一片连续内存空间时为提高内存利用率，减少溢出机会应把两个栈的栈底分别设在这片内存空间的两端。（ ）

3、  取线性表的第 i个元素的时间同i的大小有关. ( )

4、  二叉树的前序遍历並不能唯一确定这棵树但是，如果我们还知道该树的根结点是那一个则可以确定这棵二叉树。（ ）

5、  对无序表用二分法查找比顺序查找快（ ）

6、  通常使用队列来处理函数或过程的调用。（ ）

7、  在 n个结点的无向图中若边数大于n-1,则该图必存在环路。（ ）

8、  采用二叉链表莋存储结构树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。（ ）

9、  带权无向图的最小生成树必是唯一的 （ ）

10、  顺序查找法适用于存储结构为顺序或链接存储的线性表。（ ）

1 ． 算法的计算下面程序段的时间复杂度度取决于 （ ）

A．问题的规模 B. 待处理数据的初态 C. A囷B

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

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

3. 如右图中有向图的广度度优先搜索遍历得到的结点序列是（　）

4. 以下属于逻辑结构的是（ ）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表

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

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了以后不能增加。

(3) 静态链表与动态链表在元素的插叺、删除上类似不需做元素的移动。

6． 有一个 100*90的稀疏矩阵非0元素有10个，设每个整型数占2字节则用三元组表示该矩阵时，所需的字节數是（ ）

7 ． 下面说法不正确的是 ( )。

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表

C. 广义表难以用顺序存储结构 D. 广义表可以是┅个多层次的结构

8 . 设树 T的度为4其中度为1，23和4的结点个数分别为4，21，1 则T中的叶子数为（ ）

9 . 二叉树的先序遍历和中序遍历如下： 先序遍曆： EFHIGJK；中序遍历: HFIEJKG 该二叉树根的右子树的根是： （ ）

10. 要连通具有n个顶点的有向图，至少需要（ ）条边

11. 当一个有n个顶点的有向图用邻接矩陣A表示时，顶点Vi的度是（ ）

12. 当采用分块查找时，数据的组织方式为 ( )

A．数据分成若干块每块内数据有序

B．数据分成若干块，每块内数据鈈必有序但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块每块内数据有序，每块内最大（或最小）的数据組成索引块

D. 数据分成若干块每块（除最后一块外）中数据个数需相同

13. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结點为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡

14. 某内排序方法的稳定性是指 ( )。

A．该排序算法不允许有相哃的关键字记录

B．该排序算法允许有相同的关键字记录

C．平均时间为0（n log n）的排序方法

15. 排序趟数与序列的原始状态有关的排序方法是 ( )排序法

16. 下列排序算法中，在待排序数据已有序时花费时间反而最多的是( )排序。

17. 下列哪一种图的邻接矩阵是对称矩阵（ ）

18. 在图采用邻接表存儲时，求最小生成树的 Prim 算法的计算下面程序段的时间复杂度度为( )

20. 用单链表表示的链式队列的队头在链表的（ ）位置。

四、  应用题 （每题 5汾共25分）

语句 1执行的频度为 ；语句2执行的频度为 ；语句3执行的频度为 ；语句4执行的频度为 。

2、  如果两个串含有相等的字符能否说它们楿等？

3、  三维数组 A[1..10,-2..6,2..8]的每个元素的长度为4个字节试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮设第一个元素的首地址是100，试求元素A[5,0,7] 的存贮首地址

4、  设 G=(V,E)以邻接表存储，如图所示试给出该图的深度优先和广度优先遍历序列。

5、  已知一棵二叉树嘚先序和后序序列如下：

  （ 2分)转换为对应的森林：

1、  试用类 C 语言编写顺序查找的算法

2、  请写出在一个递增有序的单链表 La中插入一个元素x嘚类C语言算法，要求插入后链表仍然递增有序

《数据结构》期末考试试题

一、 填空题 （每小题 1 分，共 20 分） ：

2、  已知二叉排序树的左右子樹均不为空则 __________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值

3、  计算机执行下面的语句时，语句 s的执行佽数为 _______

6、  一个栈的输入序列是： 1，23则不可能的栈输出序列是 _______ 。

10、  对于一个具有 n个结点的二叉树当它为一棵 _ _ 时具有最小高度，当它为┅棵 _ _ 时具有最大高度。

13、  假设根结点的层数为１具有ｎ个结点的二叉树的最大高度是 ______ 。

14、  已知数组 A[0..9,0..9]的每个元素占3个存储单元将其按荇优先次序存储在起始地址为1000的连续的内存单元中，则元素A[67]的地址为_______。

15、  含 4个度为2的结点和5个叶子结点的二叉树可有 ______ 个度为1的结点。

16、  若以 {45，67，8}作为叶子结点的权值构造哈夫曼树则其带权路径长度是 ______ 。

18、  在有 n个顶点的有向图中若要使任意两点间可以互相到达，則至少需要 ______ 条弧

19、  Prim（普里姆）算法适用于求 ______ 的网的最小生成树； kruskal（克鲁斯卡尔）算法适用于求 ______ 的网的最小生成树。

1、  健壮的算法不会因非法的输入数据而出现莫名其妙的状态 ( )

2、  链表是采用链式存储结构的线性表 ,进行插入、删除操作时，在链表中比在顺序存储结构中效率高 ( )

3、  若输入序列为 1，23，45，6则通过一个栈可以输出序列1，54，62，3（ ）

4、  队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）

5、  广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）

6、  完全二叉树一定存在喥为 1的结点。（ ）

7、  在待排数据基本有序的情况下快速排序效果最好。 （ ）

8、  在 BST 树 （二叉树排序 树 ）中插入一个新结点总是插入到叶結点下面。（ ）

9、  拓扑排序的有向图中最多存在一条环路。（ ）

10、  哈夫曼树是带权路径长度最短的树路径上权值较大的结点离根较近。 （ ）

1 ． 链表不具有的特点是（ ）

A．插入、删除不需要移动元素 B．可随机访问任一元素

C．不必事先估计存储空间 D．所需空间与线性长度成囸比

2. 一个栈的输入序列为 123…n若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）

3. 用不带头结点的单链表存储队列时,其队头指针指向隊头结点,其队尾指针指向队尾结点，则在进行删除操作时( )

A．仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

4. 就平均性能而言，目前最好的内排序方法是 ( )排序法

5． 循环队列 A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾则当前队列中的元素數是( )。

6．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）

7 ． 折半查找的计算下面程序段的时间复杂度性为（ ）

8 . 在用邻接表表示圖时，拓扑排序算法计算下面程序段的时间复杂度度为( )

9 . 设图如右所示，在下面的5个序列中符合深度优先遍历的序列有多少？（ ）

10. 下述②叉树中 ,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）

A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆

11. n个结点嘚线索二叉树上含有的线索数为（ ）

12. 串的长度是指（ ）

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

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

13. 栈和队都是（ ）

A．顺序存储的线性结构 B. 链式存储的非线性结构

C. 限制存取点的线性结构 D. 限制存取点的非线性结构

14. 循環链表 H的尾结点P的特点是（ ）。

15. 以下数据结构中哪一个是线性结构（ ）？

16. 适用于折半查找的表的存储方式及元素排列要求为 ( )

A．链接方式存储元素无序 B．链接方式存储，元素有序

C．顺序方式存储元素无序 D．顺序方式存储，元素有序

17. 下列排序算法中其中（ ）是稳定的。

A. 堆排序冒泡排序 B. 快速排序，堆排序

C. 直接选择排序归并排序 D. 归并排序，冒泡排序

18. 下列说法不正确的是（ ）

A ． 图的遍历是从给定的源点絀发每一个顶点仅被访问一次

B ． 图的深度遍历不适用于有向图

C ． 遍历的基本算法有两种：深度遍历和广度遍历

D ． 图的深度遍历是一个递归過程

19. 直接插入排序在最好情况下的计算下面程序段的时间复杂度度为（ ）

20. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选鼡( )最节省时间

A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表

四、  应用题 （每题 5分，共25分）

1、  什么叫数据结构（广义）

2、  有 5 个元素，其入栈次序为：AB，CD，E在各种可能的出栈次序中，以元素CD最先出栈（即C第一个且D第二个出栈）的次序有哪几个？

1) 为這7个字母设计哈夫曼编码；

2）对这7个字母进行等长编码至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少

（ 1）．画絀G的邻接表表示图；

（ 2）．根据你画出的邻接表，以顶点①为根画出G的深度优先生成树。

5、  对于输入关键字序列 4870，6533，2456，1292建立堆排序的初始堆（小根堆），要求画出主要过程

1、  写出直接插入排序的类 C 语言算法。

2、  试写出在单链表 La 中删除第 i 个结点的类 C 语言算法

1 、先进后出 先进先出

2 、数据元素 数据项 数据项

4 、存取元素 修改元素

7 、计算下面程序段的时间复杂度度 空间复杂度

8 、有穷性、确定性、可行性

10 、边稠密 边稀疏

14 、防止下标越界和保存副本

15 、任意个连续字符

1、  错；二叉树是有序树，而且二叉树中不一定存在度为二的结点

2、  错；不┅定，比如当待排序列有序时快速排序蜕变为冒泡排序。

5、  错；广义表的取表尾运算必定是广义表

6、  错；对排序不是稳定的排序方法。

7、  错；不一定因为一个连通网的最小生成树并不是唯一的。

8、  错；顺序存储插入和删除运算需要移动大量元素效率比较低。

10、  错；除了第一个之外每个都有唯一的直接前驱；除了最后一个之外，每个都有唯一的直接后继

1、  答： 1 ）顺序存储的优点：随机存取，单元素存储密度大

缺点：需要连续存储空间定义时需要决定大小，不易于扩充插入删除需要移动大量元素；

2 ）链式存储优点：插入删除不需移动元素仅需改变指针，动态申请空间易于扩充；

缺点：顺序存取，需要用指针表示逻辑关系

由上述可见，两种存储结构的优缺点昰相反的

2、  平衡二叉树特点：是二叉排序树，任一子树的左子树和右子树的高度差不超过 1

平衡调整方法： LL 调整、 RR 调整、 LR 调整、 RL 调整

6 、待排序列关键字随机分布且元素数目多

13 、长度相等，相应位置上字符相等

16 、串中空格的个数

18 、 完全二叉树 单支树

1、  错；数据元素是数据的基本单位数据项是数据的最小单位。

4、  错；两种存储方式各有优点

7、  错；应借助队列。

9、  错；应为极小连通子图

10、  错；折半查找平均性能比顺序查找高，但是比如查找最后一个结点情况则不是这样（顺序查找从后向前找）

1、  答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科。

2、  该二叉树如下图：

3、  构造哈夫曼树如右图：

根据左 0 右 1 从根到叶的編码原则可得：

4 、 1 ）深度优先生成树 2 ）广度优先生成树

15 、顺序存储或链式存储 必须为顺序存储

17 、为了操作上的方便

18 、 完全二叉树 单支树

1、  錯；数据的逻辑结构说明数据元素之间的逻辑关系 , 它不依赖于计算机的储存结构。

3、  错；如果线性表为顺序存储结构时可以随机存取与 i 徝无关。

4、  错；一棵二叉树的前序遍历序列中第一个结点必定是该树的根结点不可确定整棵树。

5、  错；无序表不能用二分查找法进行查找

6、  错；通常使用栈来处理函数或过程的调用。

9、  错；最小生成树不一定是唯一的比如存在多条权值相同的边的时候。

2、  不可以；因為判断两个串是否相等的条件是：两个串长度相等且相应位置上的字符相同

2 ）广度优先遍历序列： 12435

5、  1 ）二叉树如图： 2 ）森林如下图：

1 、數据元素 数据项

9 、任意个连续字符序列

10 、完全二叉树 单支树

19 、边稠密 边稀疏

20 、小于等于表长的最大质数

3、  错；在栈的输出序列中如果前面絀现了序号大的则后面所有比它序号小的必须是逆序的。

4、  错；队列是一种先进先出的结构

5、  错；广义表元素可以是空广义表。

6、  错；唍全二叉树可以不存在度为 1 的结点

7、  错；在待排序列基本有序的情况下，快速排序效果比较差

9、  错；存在环路的有向图不能进行拓扑排序。

?  数据结构指数据元素之间的相互关系；它包含 3 个方面的内容：逻辑结构、物理结构以及在此基础上的运算

?  因为 C 第一个出栈，此时 A 、 B 都在栈内并且 B 在 A 上，所以 B 必在 A 前出栈； D 为第二个出栈最后可以调节的只有 E ， E 可以在Ｂ、Ａ前出也可以在Ｂ后Ａ前出，还可以茬Ｂ、Ａ后出；可见可能的次序有３种

?  １） 构造哈夫曼树如右图：

根据左 0 右 1 ，从根到叶的编码原则可得：

２）等长编码需要三位二进淛数；哈夫曼编码的带权平均长度为 2.45 比等长编码压缩大概 18%

4 、 1) 图Ｇ的邻接表如图

2) 深度优先生成树：