第1章绪论
一、选择题
1. 算法的计算量的大小称为计算的（）。
A．效率 B. 复杂性 C. 现实性 D. 难度
2. 算法的时间复杂度取决于（）
A．问题的规模 B. 待处理数据的初态 C. A和B
3.计算机算法指的是（1），它必须具备（2）这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法
(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性
D. 易读性、稳定性、安全性
4．一个算法应该是（）。
A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.
5. 下面关于算法说法错误的是（）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
6. 下面说法错误的是（）
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A．(1) B.(1),(2) C.(1),(4) D.(3)
7．从逻辑上可以把数据结构分为（）两大类。
A．动态结构、静态结构B．顺序结构、链式结构
C．线性结构、非线性结构D．初等结构、构造型结构
8．以下与数据的存储结构无关的术语是（）。
A．循环队列 B. 链表 C. 哈希表 D. 栈
9．以下数据结构中，哪一个是线性结构（）？
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串
10．以下那一个术语与数据的存储结构无关？（）
A．栈 B. 哈希表 C. 线索树 D. 双向链表
11．在下面的程序段中，对x的赋值语句的频度为（）
FOR i:=1 TO n DO
FOR j:=1 TO n DO
x:=x+1;
A．O(2n) B．O(n) C．O(n2) D．O(log2n)
12．程序段FOR i:=n-1 DOWNTO 1 DO
FOR j:=1 TO 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)
13．以下哪个数据结构不是多型数据类型（）
A．栈B．广义表C．有向图D．字符串
14．以下数据结构中，（）是非线性数据结构
A．树B．字符串C．队D．栈
15. 下列数据中，（）是非线性数据结构。
A．栈 B. 队列 C. 完全二叉树 D. 堆
16．连续存储设计时，存储单元的地址（）。
A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续
17．以下属于逻辑结构的是（）。
A 顺序表 B. 哈希表 C.有序表 D. 单链表
二、判断题
1. 数据元素是数据的最小单位。( )
2. 记录是数据处理的最小单位。( )
3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( )
4．算法的优劣与算法描述语言无关，但与所用计算机有关。( )
5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )
6．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( )
7．程序一定是算法。( )
8．数据的物理结构是指数据在计算机内的实际存储形式。( )
9. 数据结构的抽象操作的定义与具体实现有关。( )
10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )
11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )
12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( )
13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( )
三、填空
1．数据的物理结构包括的表示和的表示。
2. 对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），__（4）_四种。
3．数据的逻辑结构是指。
4．一个数据结构在计算机中称为存储结构。
5．抽象数据类型的定义仅取决于它的一组__（1）_，而与_（2）_无关，即不论其内部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。
6．数据结构中评价算法的两个重要指标是.
7. 数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_（3）_，设计出相应的（4）_。
8．一个算法具有5个特性: （1）、（2）、（3），有零个或多个输入、有一个或多个输出。
9．已知如下程序段
FOR i:= n DOWNTO 1 DO {语句1}
BEGIN
x:=x+1；{语句2}
FOR j:=n DOWNTO i DO {语句3}
y:=y+1; {语句4}
END；
语句1执行的频度为（1）；语句2执行的频度为（2）；语句3执行的频度为（3）；
语句4执行的频度为（4）。
10．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）FOR i：＝１TO n DO
FOR j：＝１TO i DO
FOR k：＝1TO j DO
ｘ：＝ｘ＋delta；
11.下面程序段中带下划线的语句的执行次数的数量级是：.
i：=1；WHILE i 12. 下面程序段中带下划线的语句的执行次数的数量级是( )。 i:=1; WHILE i 13. 下面程序段中带有下划线的语句的执行次数的数量级是( ) i：=n*n WHILE i<>1 DO i:=i div 2; 14. 计算机执行下面的语句时，语句s的执行次数为_______ 。 FOR(i=l；i FOR(j=n;j>=i;j--) s; 15. 下面程序段的时间复杂度为________。(n>1) sum=1； for (i=0;sum 16．设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。 ①以下是该函数的程序段，请将未完成的部分填入，使之完整 int f(m,n) int m,n; { if(m==1) return (1) ; if(n==1){ return (2) ;} if(m {return f(m,m);} if (m==n) {return 1+ (3) ;} return f(m.n-1)+f(m-n, (4) ); } ②执行程序，f(6,4)= 。 17. 在有n个选手参加的单循环赛中，总共将进行______场比赛。 四、应用题 1. 数据结构是一门研究什么内容的学科？ 2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？ 4. 回答问题（每题2分） （1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？ （2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。 （3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。 （4）评价各种不同数据结构的标准是什么？ 5．评价一个好的算法，您是从哪几方面来考虑的？ 6．解释和比较以下各组概念【华南师范大学2000 一（10分）】 （1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构 （3）抽象数据类型（4）算法的时间复杂性（5）算法（6）频度 7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？ 8．对于一个数据结构，一般包括哪三个方面的讨论？ 9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？ 10. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？ 11．数据结构与数据类型有什么区别？ 12．数据的存储结构由哪四种基本的存储方法实现？ 13．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？ 14. 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。 15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么? 16. 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。 17. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。 18．设计一数据结构，用来表示某一银行储户的基本信息：账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。 19. 写出下面算法中带标号语句的频度。 TYPE ar=ARRAY[1..n] OF datatype; PROCEDURE perm ( a: ar; k, n: integer); V AR x: datatype; i:integer; BEGIN （1）IF k=n THEN BEGIN （2）FOR i:=1 TO n DO （3）write (a[i]); writeln; END ELSE BEGIN （4）FOR i:=k TO n DO （5）a[i]:=a[i]+i*i; （6）perm (a, k+1, n); END; 设k的初值等于1。 20. 分析下面程序段中循环语句的执行次数。 i:=0;s:=0;n:=100; REPEAT i:=i+1; s:=s+10*i; UNTIL NOT((i 21．下列算法对一n位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。 TYPE num=ARRAY [1..n] of [0..1]； PROCEDURE Inc （V AR a：num）； V AR i：integer； BEGIN i：=n； WHILE A[i]=1 DO BEGIN A[i]：=0；i：=i-1；END； END； A[i]：=1； END Inc； 22. 阅读下列算法，指出算法A的功能和时间复杂性 PROCEDURE A (h,g:pointer); (h,g分别为单循环链表（single linked circular list）中两个结点指针) PROCEDURE B(s,q:pointer)； V AR p:pointer; BEGIN p:=s; WHILE p^.next<>q DO p:=p^.next; p^.next:=s; END;(of B) BEGIN B(h,g); B(g,h); END;（of A） 23. 调用下列C函数f(n)或PASACAL函数f(n) 回答下列问题: （1）试指出f(n)值的大小，并写出f(n) 值的推导过程; （2）假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。 C函数：int f(int n) { int i,j，k,sum= 0; for(i=l; i {for(j=n;j>i-1; j--) for(k=1;k sum++; printf("sum=%d\n",sum)； } } 24．设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 m:=0; FOR i:=1 TO n DO FOR j:=2*i TO n DO m:=m+1; 25．有下列运行时间函数： （1）T1 (n)=1000; （2）T2(n)=n2+1000n; （3）T3(n)=3n3+100n2+n+1; 分别写出相应的大O表示的运算时间。 26. 试给出下面两个算法的运算时间。 （1）for i←1 to n do x ←x+1 END （2）for i← 1 to n do for j←1 to n do x←x+1 end end 27. 斐波那契数列Fn定义如下 F0=0，Fl=1，Fn=Fn-1+Fn-2, n=2,3... 请就此斐波那契数列，回答下列问题。 (1) (7分) 在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，…, Fl, F0精确计算多少次? (2) (5分) 如果用大O表示法，试给出递归计算Fn时递归函数的时间复杂度录多少? 28．将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。 n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+logn 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.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。() 1．由３个结点所构成的二叉树有种形态。 2. 一棵深度为6的满二叉树有个分支结点和个叶子。 3. 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。 4. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R 次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。 5. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。 6. 一棵度为2的树与一棵二叉树有何区别？ 7. 设如下图所示的二叉树B的存储结构为二叉链表，root为根指 针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别 为指向左右孩子的指针，data为字符型，root为根指针，试回答 下列问题： 对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；C的结点类型定义如下： struct node {char data; struct node *lchild, rchild; }; C算法如下： void traversal(struct node *root) {if (root) {printf(“%c”, root->data); traversal(root->lchild); printf(“%c”, root->data); 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 《数据结构-C语言版》 第一章绪论 单项选择题 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．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL 数据结构试题及答案 数据结构试题(,)参考答案班别学号姓名成绩一、单项选择(每小题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、下图所示的4棵二叉树中，不是完全二叉树的是（） 2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。 A 、正确 B 、错误 C 、不一定 3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。 A 、acbed B 、decab C 、deabc D 、cedba 4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。 A 、前序 B 、中序 C 、后序 D 、层次序 5、深度为5的二叉树至多有（）个结点。 A 、16 B 、32 C 、31 D 、10 6、在一个非空二叉树的中序遍历序列中，根结点的右边（）。 A 、只有右子树上的所有结点 B 、只有右子树上的部分结点 C 、只有左子树上的部分结点 D 、只有左子树上的所有结点 7、树最适合用来表示（）。 A 、有序数据元素 B 、无序数据元素 C 、元素之间具有分支层次关系的数据 D 、元素之间无联系的数据。 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A 、不发生改变 B 、发生改变 C 、不能确定 D 、以上都不对 9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。 A 、二叉链表 B 、广义表存储结构 C 、三叉链表 D 、顺序存储结构 10、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则（）。 A 、n=m+h B 、h+m=2n C 、m=h-1 D 、n=2h -1 11、设n ，m 为二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（）。 A 、n 在m 右方 B 、n 是m 祖先 C 、n 在m 左方 D 、n 是m 子孙 12．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/- ， A B C D 第一章概论 一、选择题 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. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 数据结构课程作业_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 解析第六章第六节二叉树的性质 知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序 101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式B．数据的存储形式C．数据的表示形式D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项B．数据类型C．数据元素D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大B．小C．相同D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间B．在顺序结构中查找元素的速度比在链接结构中查找要快C．与链接结构相比，顺序结构便于安排数据元素D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；i 数据结构习题(,,章) ————————————————————————————————作者：————————————————————————————————日期： 第四章串 一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。 第五章数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（） 第1章绪论 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。 （6）在一般情况下，一个算法的时间复杂度是（）的函数。 （7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链式存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 ⑶算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 ⑷下面（）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 ⑸算法分析的目的是（），算法分析的两个主要方面是（）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性H 数据复杂性和程序复杂性 3. 判断题 （1）算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。 （2）每种数据结构都具备三个基本操作：插入、删除和查找。 （3）逻辑结构与数据元素本身的内容和形式无关。 （4）基于某种逻辑结构之上的基本操作，其实现是唯一的。 4. 分析以下各程序段，并用大O记号表示其执行时间。 排序算法（19） 1.以单链表为存储结构，写一个直接选择排序算法。 2.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关 键字之前。请分析算法的时间复杂度。 3.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。 4. 4.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进 行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。 void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=n-1; while (i>0) lastExchange=0; for(j=0;j if([j+1] 交换A[j]和A[j+1]; lastExchange=j; } i=lastExchange;//将i置为最后交换的位置 }//endwhile }//BubbleSort 5.改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。 6.对给定的j(1 ≤ j ≤ n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。 7.以单链表为存储结构，写一个直接选择排序算法。 8.写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度域)；将key先插入R 中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。 9.写一个建堆算法：从空堆开始，依次读入元素调用上题中堆其中。 10.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。 第六章树和二叉树试题 一、单项选择题 1.树中所有结点的度等于所有结点数加（）。 A. 0 B. 1 C. -1 D. 2 2.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点 3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. -1 4.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。 A. n B. n-1 C. n+1 D. 2*n 5.在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等 于0而小于等于树的高度），最多具有（）个结点。 A. 2i B. 2i+1 C. 2i-1 D. 2n 6.在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不 小于（）。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h 7.在一棵具有35个结点的完全二叉树中，该树的高度为（）。假定空树 的高度为-1。 A. 5 B. 6 C. 7 D. 8 8.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。假 定树根结点的编号为0。 A. ?(n-1)/2? B. ?n/2? C. ?n/2? D. ?n/2? -1 9.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号 为（）。假定根结点的编号为0 A. 2i B. 2i-1 C. 2i+1 D. 2i+2 10.在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结 点，其双亲结点的编号为（）。 A. ?(i+1)/2? B. ?(i-1)/2? C. ?i/2? D. ?i/2? -1 11.在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（） 结点。 A. 兄弟 B. 子女 C. 祖先 D. 子孙 12.在一棵树的静态双亲表示中，每个存储结点包含（）个域。 A. 1 B. 2 C. 3 D. 4 13.已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则 该二叉树的高度为（）。假定根结点的高度为0。 A. 3 B. 4 C. 5 D. 6 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 第一章绪论 一、选择题 1.D 2.C 3.C 4.B 5.D 6.C 7.D 8.C 9.A 10.D 11.D 12.B 二、填空题 1. 逻辑结构存储结构运算 2. 集合结构线性结构树形结构图状结构 3. 有穷性. 确定性. 可行性. 输入. 输出 4. 顺序存储. 链式存储 5. 数据元素 6. 线性结构非线性结构 三、简答题 1. 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满 有穷性，因为它不是一个算法。其次，程序中的指令必须是计算机可以执行的，而 算法中的指令却无此限制。如果一个算法采用机器可执行的语言来书写，那么它就 是一个程序。 2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元 素的组织形式）。例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中 既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元 素. 判断是否为空队列，以及队列置空等操作。 3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互 关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理 结构。 4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表 示一个或者多个操作。此外，一个算法还具有下列5个特性： （1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完 成。 （2）确定性：算法中每一步必须有明确的含义，不会产生二义性。并且，在任何 条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基 本运算执行有限次得以实现。 （4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始 量。 （5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量 5. 举例说明四种基本结构的区别: 集合: 数据元素之间无任何关系,如集合A={x,5,t,&}; 线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）； 树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理； 图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。 四. 算法设计题 数据结构习题集含答案 目录 选择题 第一章绪论 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; void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 { InitStack(S); Push(S,T); //根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p); if(!StackEmpty(S)) { pop(S,p); push(S,p->rchild); //向右一步 } }//while }//PreOrder_Nonrecursive 一、下面是有关二叉树的叙述，请判断正误 1.二叉树中每个结点的两棵子树的高度差等于1。（） 2.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（） 3.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i —1个结点。（） 4.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（） 5.具有12个结点的完全二叉树有5个度为2的结点。（） 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 6．二叉树是度为2的有序树（） 7．完全二叉树一定存在度为1的结点（） 8．深度为K的二叉树中结点总数≤2k-1（） 9．由一棵二叉树的先序序列和后序序列可以惟一确定它（） 10．完全二叉树中，若一个结点没有左孩子，则它必是树叶（） 11．用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（）12．完全二叉树的存储结构通常采用顺序存储结构（） 13．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（）14．在中序线索二叉树中，每一非空的线索均指向其祖先结点（） 二、填空 1. 一棵具有２５７个结点的完全二叉树，它的深度为。 2. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 3．深度为H 的完全二叉树至少有_____________个结点；至多有_____________个结点4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_____________。 5. n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_____________。它共有_____________个叶子结点和_____________个非叶子结点，其中深度最大的那棵树的深度是_____________，它共有_____________个叶子结点和_____________个非叶子结点。 三、单项选择题 1．有关二叉树下列说法正确的是（） A）二叉树的度为2 B）一棵二叉树的度可以小于2 C）二叉树中至少有一个结点的度为2 D）二叉树中任何一个结点的度都为2 2．二叉树的第I层上最多含有结点数为（） A）2I B）2I-1-1 C）2I-1D）2I-1 3．具有10个叶结点的二叉树中有（）个度为2的结点 A）8 B）9 C）10 D）11 4．在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0； ②二叉树的度为2； ③二叉树的左右子树可任意交换； ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A）①②③B）②③④C）②④D）①④ 5．由3 个结点可以构造出多少种不同的二叉树？（） A）2 B）3 C）4 D）5 6．引入二叉线索树的目的是（）数据结构第一章试题
数据结构第6章习题集
数据结构第1章作业
数据结构复习题目和答案
数据结构试题及答案
数据结构第六章习题课
数据结构试题答案
数据结构-第六章-图-练习题及答案详细解析(精华版)
数据结构课程作业
数据结构习题库汇总
数据结构习题(,,章)
数据结构作业第1章
数据结构习题
《数据结构》习题汇编06第六章树和二叉树试题
数据结构第一章课后习题与答案
数据结构1-4章习题答案
数据结构考试题库含答案
数据结构第6章树练习
相关主题
文本预览