数据结构题库

1、C、确定性、有穷性和稳定性 D、易读性、稳定性和安全性 第一章 绪论 答案：1、A，B 2、D，B 3、C 4、C，A 5、C，B 二、名词解释： 一、选择题 1、数据 1、数据结构是一门研究非数值计算的程序设计问题中 4、数据结构 计算机的 以及它们之间的 和运算等的 2、数据元素 5、数据类型 3、数据对象 6、算法 答案：1、数据是对客观事物的符号表示，在计算机科 学科。 A、数据元素 B、计算方法 C、逻辑存储 D、数据映象 A、结构 B、关系 C、运算 D、算法 2、 数据结构被形式地定义为(K,R),其中K是 的 有限集，R是K上的 有限集。 A、 算法 B、数据元素 C、数据操作

2、 D 、 逻辑结构 A、 操作 B、映象 C、存储 D、 关系 3 、 在 数据结 构 中 ， 从逻 辑 上 可 以把 数 据 结 构分 成 _。 A、动态结构和静态结构 B、紧凑结构和非紧凑 结构 C、线性结构和非线性结构 D、内部结构和外部结 构 4、算法分析的目的是 ，算法分析的两个 主要方面是 。 A、找出数据结构的合理性 B、研究算法中的 输入和输出的关系 C、分析算法的效率以求改进 D、分析算法 的易懂性和文档性 A、空间复杂度和时间复杂度 B、正确性和 简单性 C、可读性和文档性 D、数据复杂性和 程序复杂性 5、计算机算法指的是 ，它必须具备输入、输 出和 等 5 个特性。 A

3、、计算方法 B、排序方法 C、解决问题的有限运算序列 D、调度方法 A、可执行性、可移植性和可扩充性 B、可行性、确定性和有穷性 学中是指所有能输入到计算机中被计算机程序处理的符号 的总称。 2、数据元素数据的基本单位，在计算机程序中通常做 为一个整体进行考虑和处理。 3、数据对象：性质相同的数据元素的集合。 4、数据结构：相互具有一种或多种关系的数据元素的集合。 5、数据类型：是具有相同性质的计算机数据的集合及在这 个数据上的一组运算，是和数据结构密切相关的概念。 6、算法：对特定问题求解步骤的一种描述，是有限指令的 集合。 三、填空题 1、下面程序段的时间复杂度是_。 for (i=0;i

4、<n;i+) for (j=0;j<m;j+) aij=0; 2、下面程序段的时间复杂度是_。 i=s=0 while(s<n) i+; /* i=i+1 */ s+=i; /* s=s+i */ 3、下面程序段的时间复杂度是_。 s=0; for (i=0;i<n;i+) for (j=0;j<n;j+) s+=bij; sum=s; 4、下面程序段的时间复杂度是_。 i=1; wile (i<=n) 1 i=i*3; 5、数据元素可以由若干_组成，_是数据的基 本单位，_是数据的最小单位。 6、数据结构分为两部分，即_结构和_结构。 7、数据的存储方式分

5、为_存储和_存储。 8、顺序存储是一种_的存储方式，是用一组_ 的存储空间存储数据，而链式存储是用一组_的存储空间 存储数据。 3、 n2) n) 答案： O(m*n) 2、 1、 O(O( 4、 O(lo g3n) 5、数据项 数据元素 数据项 6、逻辑 物理 7、顺 序 链式 8、随机存取 连续 任意 四、简答题： 1、什么是算法，其基本性质是什么？ 2、算法的要求是什么？ 3、结构共分几类？其各自的性质是什么？ 答案：1、算法是对特定问题求解步骤的一种描述，是有限 指令的集合。其基本性质如下： 1)有穷性：算法对任意合法的输入均能在有限时间、有限步 骤后完成。 2)确定性：算法的每一步骤

6、的含义都是唯一、确定的，对于 相同的输入均能得到相同的输出。 3)可行性： 算法的每一个步骤和指令都应在已实现的算法的 基础上完成。 4)输入：任一个算法必须有 0 个或多个输入。 5)输出：任一个算法必须有 1 个或多个输出。 2、算法的要求是： 1)正确性：算法能正确描述待求解问题的需求，没有逻辑错 误，据此算法书写的程序，对于任何合法的输入，都有得到 正确的、说明需求的结果。 2)可读性：算法应简洁、明晰，易于阅读和理解，便于算法 的移植和交流，有利于增加算法的生命力。 3)健壮性： 当输入的数据非法时， 算法要能作出适当的处理， 不会产生难以预料的结果。 4)高效率性：一般来说，对同一

7、问题的多种算法，首先选择 执行时间相对较短、存储空间相对较少的算法，然后考虑易 于实现的算法。 3、结构共分为四类，分别为： 1)集合：所有元素除共在同一集合外，没有其他关系。 2)线性结构：元素间是一对一的关系。 3)树型结构：元素间是一对多的关系。 4)图型结构：元素间是多对多的关系。 五、算法设计题： 1、试写一算法，求随机输入的三个整数的最大值。 2、随机从键盘上输入三个整数求其平均值输出。 第二章 线性结构 一、 判断题 1、线性表的逻辑顺序与存储顺序总是一致的。 2、顺序存储的线性表可以按序号随机存取。 3、顺序表的插入和删除一个数据元素，每次操作平均 只有近一半的元素需要移动。

8、4、线性表中的元素可以是各种各样的，但同一线性表 中的数据元素具有相同的特性，因此是属于同一数据对象。 5、在线性表的顺序存储结构中，逻辑上相邻的两个元 素在物理位置上并不一定紧邻。 6、在线性表的链式存储结构中，逻辑上相邻的元素在 物理位置上不一定相邻。 7、线性表的链式存储结构优于顺序存储结构。 8、在线性表的顺序存储结构中，插入和删除时，移动 元素的个数与该元素的位置有关。 9、线性表的链式存储结构是用一组任意的存储单元来 存储线性表中数据元素的。 10、在单链表中，要取得某个元素，只要知道该元素的 指针即可，因此，单链表是随机存取的存储结构。 11、线性表中，每一个元素均存在前驱。 1

9、2、线性表中，每一个元素均存在后继。 13、线性表中，存在唯一一个被称为第一元素的元素。 14、线性表中，存在唯一一个被称为最后一个元素的元 素。 15、线性结构是一种一对一的结构。 答案：1-5 ×× 6-10 ×× 11-15 × × 2 8、 单链表中，增加一个头结点的目的是为了（ 二、 选择题： ） 。 A、使单链表至少有一个结点 点的位置 1、线性表是( ) 。 C、方便运算的实现 A、一个有限序列，可以为空； B、一个有限序列， 表的链式存储 不能为空； B、标识表结点中首结 D、说明单链表是线性 9、 若某线性表中最常用

10、的操作是在最后一个元素之后 C、一个无限序列，可以为空； 不能为空。 D、一个无序序列， 插入一个元素和删除第一个元素，则采用（ ）存储方式最 节省运算时间。 2、对顺序存储的线性表，设其长度为 n，在任何位置 A、单链表 上插入或删除操作都是等概率的。 插入一个元素时平均要移 C、双链表 动表中的（ ）个元素。 B、仅有头指针的单循环链表 D、仅有尾指针的单循环链表 10、 若某线性表中最常用的操作是取第 i 个元素和找 A、 第 i 个元素的前趋元素，则采用（ ）存储方式最节省运算 n 时间。 3、线性表采用链式存储时，其地址( ) 。 A、单链表 B、顺序表 A、必须是连续的； C、一定

11、是不连续的； B、部分地址必须是连续的； C、双链表 D、单循环链表 D、连续与否均可以。 11、 一个向量(一种顺序表)第一个元素的存储地址是 4、用链表表示线性表的优点是 （ ） 100， A、便于随机存取 A、110 B、花费的存储空间较顺序存储少 B、108 C、100 D、120 12、 不带头结点的单链表 head 为空的判定条件是 C、便于插入和删除 _。 D、数据元素的物理顺序与逻辑顺序相同 A、head = = NULL; 5、 某链表中最常用的操作是在最后一个元素之后插入 C、head.next = = head; 一个元素和删除最后一个元素， 则采用( )存储方式最节省

12、B、head.next = = NULL; D、head! = NULL; 13 、 带 头 结 点 的 单 链 表 head 为 空 的 判 定 条 件 是 运算时间。 _。 A、单链表 A、head = = NULL; B、双链表 C、head.next = = head; C、单循环链表 B、head.next = = NULL; D、head! = NULL; 14、 在一个单链表中，若 p 所指结点不是最后结点， D、带头结点的双循环链表 在 p 之后插入 s 所指结点，则执行_。 6、 循环链表的主要优点是( A、不再需要头指针了 ) 。 A、s.next=p; p.next=s;

13、 B、s.next=p.next; p.next=s; B、已知某个结点的位置后，能够容易找到他的直接前 C 、 s.next=p.next; 趋 s.next=p; C、在进行插入、删除运算时，能更好的保证链表不断 p=s; D 、 p.next=s; 15、 在一个单链表中，已知 q 所指结点是 p 所指结点 开 的前驱结点，若在 q 和 p 之间插入 s 结点，则执行_。 D、从表中的任意结点出发都能扫描到整个链表 A、 7、 下面关于线性表的叙述错误的是( )。 s.next=p; A、线性表采用顺序存储，必须占用一片地址连续的单 C、q.next=s; s.next=p; 元； s.

14、next=q; B、 线性表采用顺序存储， 不便于进行插入和删除操作； D、p.next=s; 16、 从一个具有 n 个结点的单链表中查找其值等于 x C、线性表采用链式存储，不必占用一片地址连续的单 结点时，在查找成功的情况下，需平均比较_个结点。 元； A、 D、线性表采用链式存储，便于进行插入和删除操作； 3 17、 给定有 n 个结点的向量，建立一个有序单链表的 时间复杂度_。 2 A、 O(1); B、 O(n); C、 O(n ); D、 O(nlog 2n); 18、顺序存储结构是一种_ _的存储结构。 A、随机存取 B、索引存取 C、顺序存取 D、 散列存取 19、在以下的叙

15、述中，正确的是_ _。 A、线性表的顺序存储结构优于链表存储结构 B、线性表的顺序存储结构适用于频繁插入/删除数据 元素的情况 C、线性表的链表存储结构适用于频繁插入/删除数据 元素的情况 D、线性表的链表存储结构优于顺序存储结构 20、非空的循环单链表 head 的尾结点（由 p 所指向） 满足_。 A、 p.next= =NULL B、 p= =NULL C、 p.next= =head D、 p= =head 21、在一个单链表中，若删除 p 所指结点的后续结点， 则执行_。 A、p.next= p.next.next； B、 p= p.next; p.next= p.next.next

16、； C、p.next= p.next; D、p= p.next.next； 答案：1-5 AADCD 6-10 DBCDB 11-15 BABBC 16-20 DCACC 21 A 三、 填空题 1 在一个长度为 n 的向量中的第 i 个元素(1in)之 前插入一个元素时，需向后移动_个元素。 2、 在一个长度为 n 的向量中删除第 i 个元素(1i n)时，需向前移动_个元素。 3、在一个单链表中 p 所指结点之前插入一个由指针 s 所指结点，可执行以下操作： s.next=_(1)_; p.next=s; t=p.data; p.data=_(2)_; s.data=_(3)_; 4、在线

17、性表 L=(a1,a2,an)中，L 称为线性表的 _，n 称为线性表的_。 5、在线性表中有(ai,aj)，称 ai 为 aj 的_，称 aj 为 ai 的_。 6、在顺序表中，若第一个元素所在的地址为 Loc(a1)， 每个元素在内存中占有 L 个存储单元，则元素 ai 在内存中 的地址 Loc(ai)=_。 7、顺序表是一种_存取的存储结构，其元素的逻辑 位置与物理位置一一对应。 8、系统在内存中为顺序表提供一组_的存储空间， 为单链表提供一组_的存储空间。 9、在单链表中，一个结点包含两部分内容，分别为 _和_。 10、在单链表中，若指针 p 已指向最后一个结点，则 p 应满足的条件是

18、_。 11、在单链表中，若结点 p 是结点 q 的前驱，应满足的 条件是_。 12 、 在 单 链 表 中 ， 申 请 一 个 结 点 空 间 的 命 令 是 _，释放一个空间的命令是_。 13、在双向链表中，每个结点有两个指针域，一个为 _，指向_ _；另一个为_，指向_ _ _。 14、 在一个单链表中p所指结点之后插入一个s所指结点 时，应执行s.next=_ _和p.next=_的操作。 15、在双向链表中，若结点 p 是结点 q 的前驱，现要删 除结点 q，需要完成的操作是_；_； 16、 在双向链表中， 若在结点 p 之前插入一个新结点 s， 需要完成的操作有_；_；_；_； 答案

19、：1、n-i+1 2、n-i 3、(1) p.next (2) s.data (3) t 4、名字 长度 5、直接前驱元素 直接后继元素 6、Loc(ai)=Loc(a1)+(i-1)*L 7、随机 8、连续 任 意 9、指针域 数据域 10 、 p.next=null 11 、 p.next=q 12 、 malloc() free() 13、前驱指针域 prior 后继指针域 next 14、p.next s 15、p.next=q.next; q.next.prior=q.prior; 16 、 s.prior=p.prior; s.next=p; p.prior.next=s; p.p

20、rior=s; 四、算法设计题： 1、在一顺序表 L 的第 i 个元素前，插入一新元素 x。 2、现有一顺序表 L，其值非递增有序排列，现插入一4 新元素 x，要求插入后，L 仍保持非递增有序排列，试写其 算法。 3、在带头结点的单链表 H 中的 p 结点前插入一个新元 素 x。 4、已知单链表 LA、LA 中的元素按值非递减有序排列， 现将 LA、LB 归并成一个新表 LC，并要求 LC 中的元素亦非 递减有序排列。 五、编程题： 1、百钱百鸡问题。 2、猎人与狗的问题：一队猎人一队狗，两队并成一队 走， 数头一共三百六， 数脚一共八百九， 问多少猎人多少狗。 第三章 栈和队列 一、判断题：

21、 1、栈和队列都是限制存取点的线性结构 2、栈和队列是两种重要的线性结构。 3、带头结点的单链表形式的队列，头指针 F 指向队列的头结点，尾指针 R 指向队列的最后一个结点 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。 答案：1-4 ×× 二、选择题： 1、一个栈的入栈序列 a，b，c，d，e，则栈的不可能的输出序列是_。 D、 abcde A、 edcba B、 decba C、 dceab 2、若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p1，p2，p3，pn，若 p1=n，则 pi 为_。 i B、 n=i C、 n-i+1D、 不确定 3

22、、栈结构通常采用的两种存储结构是_。 A、顺序存储结构和链式存储结构 C、链表存储结构和数组 B、散列方式和索引方式 D、线性存储结构和非线性存储结构 4、 判定一个顺序栈 ST（最多元素为 m0）为空的条件是_。A、top !=0 B、top= =0 C、top !=m0 top= =m0-1 5、 判定一个顺序栈 ST（最多元素为 m0）为栈满的条件是_。A、top！=0 B、top= =0 C、top！=m0 top= =m0-1 6、 队列操作的原则是( ) A、 先进先出 B、 后进先出 C、 只能进行插入 D、 只能进行删除 7、 向一个栈顶指针为HS的链栈中插入一个s所指结点时，

23、则执行_ _。(不带空的头结点) A、HSnext=s; C、snext= HS; HS=s; B、snext= HSnext; HSnext=s; D、snext= HS; HS= HSnext; 8、从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行_ _。(不带空的头结点) A、x=HS; HS= HSnext; B、x=HSdata; C、HS= HSnext; x=HSdata; D、x=HSdata; HS= HSnext; 9、 一个队列的数据入列序列是 1，2，3，4，则队列的出队时输出序列是_ 。 A、4，3，2，1 B、1，2，3，4 A、 D、 D、

24、 5 C、1，4，3，2 D、3，2，4，1 10、判定一个循环队列 QU（最多元素为 m）为空的条件是_。 A、rear - front= =m C、front= = rear B、rear-front-1= =m D、front= = rear+1 11、 判定一个循环队列 QU（最多元素为 m, m= =Maxsize-1）为满队列的条件是_。 A、(rear- front)+ Maxsize)% Maxsize = =m B、rear-front-1= =m 12、 循环队列用数组 A0， C、front= =rear D、front= = rear+1 已知其头尾指针分别是 fron

25、t 和 rear， 则当前队列中的元素个数是_。 A、 (rear-front+m)%m C、 rear-front-1 B、 rear-front+1 D、 rear-front 13、 栈和队列的共同点是_。A、 都是先进后出 没有共同点 14、栈操作的原则是( ) B、 都是先进先出 C、 只允许在端点处插入和删除元素 D、 A、 先进先出 B、 后进先出 C、 只能进行插入 D、 只能进行删除 15、在顺序栈中，判断栈 s 为空的条件是( A、t.base = NULL C、st.top-st.base>= st.stacksize 16、在顺序栈中，判断栈 s 满的条件是( )

26、 B、st.top = st.stacksize D、st.top = st.base ) A、 C、 st.base = NULL st.top-st.base>= st.stacksize B、 st.top = st.stacksize D、 st.top = st.base 答案：1-5 CCABD 三、填空题： 6-10 ACBCC 11-15 AACBD 16 C 1、栈和队列都是_结构，对于栈只能在_插入和删除元素；对于队列只能在_插入元素和_删除元素。 2、向一个长度为 n 的顺序表的第 i 个元素（1in+1）之前插入一个元素时，需向后移动_个元素。 3、向一个长度为

27、n 的顺序表中删除第 i 个元素（1in）时，需向前移动_个元素。 4、向栈中压入元素的操作是_。 5、对栈进行退栈时的操作是_。 6、在一个循环队列中，队首指针指向队首元素的_。 7、从循环队列中删除一个元素时，其操作是_。 8、在具有 n 个单元的循环队列中，队满时共有_个元素。 9、一个栈的输入序列是 12345，则栈的输出序列 43512 是_。 10、一个栈的输入序列是 12345，则栈的输出序列 12345 是_。 11、队列的基本性质是_；栈的基本性质是_。 12、在一个链栈中，若栈顶指针等于 NULL 则为_，在一个链队中，若队首指针与队尾指针的值相同， 则表示该队列为_或该队

28、列_。 13、向一个栈顶指针为 top 的链栈中插入一个新结点*P，应执行 和 操作。 14、栈的顺序存储结构即顺序栈，是利用 栈顶指针 top 始终指向 。 15、从数据结构的角度看，栈和队列是 来依次存放自栈底至栈顶的数据元素；当栈为非空时， 两类线性表。 6 答案：1. 线性、栈顶、队尾、队首 2. n-i+1 3. n-i 4.先移动栈顶指针，后存入元素 6.前一个位置 8. n-1 9. 不可能的 12、栈空 空队 只有一个元素 14、一组地址连续的存储单元 四、算法题： 5. 先取出元素，后移动栈顶指针 7. 先移动队首元素，后取出元素 10. 可能的 11、FIFO LIFO 1

29、3、p.next=top top=p 栈顶元素的下一位置 15、受限的线性表 1、输入一个任意的非负十进制整数,输出与其等值的八进值数。 答案：void conversion() InitStack(s); scanf(“%d”,&N); while(N) push(s,N%d); N=n/8; while(!empty(s) pop(s,e); printf(“%d”,e); 第四章 串和广义表 一、判断题： 1、空串是由空白字符组成的串 2、串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分 配一个固定长度的存储区。 3、串的堆分配

30、存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动 态分配得到的。 4、如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。 5、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。 6、广义表的表头一定是列表。 7、广义表的表尾一定是列表。 8、空串的长度为零。 9、广义表的元素即可以是原子，也可以是子表。 10、广义表中的子表与串中的子串的含义一样。 11、广义表 A=()，为空表，其长度为 0。 12、由于广义表的元素可以是列表，所以可以将广义表转化为一个树型结构 答案：1-5 ×

31、15;× 6-10 ×× 11-12 7 二、选择题： 1、以下叙述中正确的是 A、串是一种特殊的线性表 C、串中无素只能是字母 。 B、串的长度必须大于零 D、空串就是空白串 2、空串与空格串是相同的，这种说法_。 A、 正确 B、 不正确 3、串是一中特殊的线性表，其特殊性体现在_。 A、 可以顺序存储 C、 可以链接存储 B、 数据元素是一个字符 D、 数据元素可以是多个字符 4、设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作_。 A、连接 B、模式匹配 C、求子串 D、求串长 5、设串 s1=ABCDEFG，s2=PQRST，函数 co

32、n (x,y)返回 x 和 y 串的连接串，subs(s,i,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串，len(s)返回串 s 的长度，则 con (subs (s1,2,len (s2), subs (s1,len (s2),2)的 结果串是_。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 6、设串的长度为 n，则它的子串个数为 A、n B、n(n+1) C、n(n+1)/2 7、下列那些为空串（ ） A、S=“ ” B、S=“” C、S=“” 。 D、n(n+1)/2+1 D、S=“” 8、S1=“ABCD” A、1 B、2 C、3 D

33、、4 9、串是一种特殊的线性表，其特殊性体现在( )。 A、可以顺序存储 C、可以链接存储 10、串是( )。 A、少于一个字母的序列 C、不少于一个字符的序列 11、 串的长度是( )。 A、串中不同字母的个数 C、串中所含的字符的个数 B、 数据元素是一个字符 D、 数据元素可以是多个字符 B、 任意个字母的序列 D、 有限个字符的序列 B、 串中不同字符的个数 D、 串中所含字符的个数，且大于 0 12、若某串的长度小于一个常数，则采用( )存储方式最为节省空间。 A、链式 答案：1-5 ABBBD B、 堆结构 6-10 CBCBD C、 顺序表 11-12 CC 三、填空题： 1、串

34、的两种最基本的存储方式是_。 2、两个串相等的充分必要条件是_。 3、空串是_，其长度等于_。 4、空格串是_，其长度等于_。 8 5、设 s=IAMATEACHER,其长度是_。 6、串 s=abcdef,s1=cde，s1 在 s 中的位置为_。 7、广义表 A=(a,(b,c d)；其表头为_，表尾为_。 8、广义表 A=(a,A)；其表头为_，表尾为_。 9、串是每个结点仅由一个字符组成的（ 答案：1顺序存储方式和链接存储方式 ） 。 2两个串的长度相等且对应位置的字符相同 3零个字符的串、零 4由一个或多个空格字符组成的串、其包含的空格个数 514 6、3 7、a (b,c,d) 8

35、、a (A) 9、线性表 四、简答题： 1、请写出下列广义表的表长、表头、表尾。 (1) A=( ) (2) B=(e) (3) C=(a,b,(c,d,e) (4) D=(a,D) 答案：(1) 表长为 0，表头为( )，表尾为（） (2) 表长为 1，表头为 e，表尾为（） (3) 表长为 3，表头为 a，表尾为（b,(c,d,e)） (4) 表长为 2，表头为 a，表尾为（D） 五、编程题： 1编写一个程序，要求有键盘输入三个数，计算以这三个数为边长的三角形的面积(假定输入的边长是有效的)。 2. 有一函数，其函数关系如下，试编程求对应于每一自变量的函数值。 1 y = 0 -1 (x&

36、lt;0) (x=0) (x>0) 9 第五章 一、名词解释： 1、压缩存储 2、特殊矩阵 3、稀疏矩阵 数组 答案：1、压缩存储：为多个值相同的元分配一个存储空间，对零元不分配存储空间。 2、特殊矩阵：值相同的元素或者是零元素分布的有规律则称为特殊矩阵。 3、稀疏矩阵：在一个 m*n 的矩阵中，有 t 个非 0 元，其稀疏因子为 t/(m*n)，如果稀疏因子小于 0.05 就称为稀疏矩阵。 二、选择题： 1、 _。 A、1058 B、1056 C、1098 D、答案 A,B,C 都不对 2、 二维数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j

37、从 0 到 9，从首地址 SA 开始连续存 放在存储器内，该数组按列存放时，元素 A47的起始地址为_。 A、 SA+141 B、 SA+180 C、 SA+222 D、 SA+225 3、二维数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA 开始连续存放在 存储器内，存放该数组至少需要的字节数是_。 A、 80 B、 100 C、240 D、 270 4、 二维数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA 开始连续存 放在存储器内，该数组按行存放时，数

38、组元素 A74的起始地址为_。 A、 SA+141 答案：1-4 BBCC B、 SA+144 C、 SA+222 D、 SA+225 三、填空题： 1、 已知二维数组 Amn采用行序为主方式存储，每个元素占 k 个存储单元，并且第一个元素的存储地址是 LOC(A00)，则 Aij的地址是_。 2、 二维数组 A1020采用列序为主方式存储， 的地址是_。 3、 二维数组 A1020510采用行序为主方式存储， 则 A189的地址是_。 4、现有一个 n 阶的对称矩阵 ann，现将其压缩存储在一个一维数组 sm中，则 m=_，若以行序为主序进行 存储，则元素 aij(i>=j)在 s 中

39、的下标 k=_。 5、在一个 m*n 的矩阵中，若 a00是第一个元素，则 aij是第_个元素。 答案：1、LOC (A00)+(n*i+j)*k 2.、326 3、1208 10 4、n(n+1)/2 四、编程题： i(i-1)/2+j-1 5、i*n+j 1、编写一程序，求 1+2+3+4+100 的值（中） 2、菱形的输出(前 5 行) （中） 第六章 树 一、选择题： 1、由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树，这种说法_。 A、 正确 B、 错误 2、假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30 个，则叶子结点数为 A、15 B、16 C、17

40、 D、47 3、按照二叉树的定义，具有 3 个结点的不同形状的二叉树有_种。 A、3 B、 4 C、 5 D、 6 4、按照二叉树的定义，具有 3 个不同数据结点的不同的二叉树有_种。 A、5 B、 6 C、 30 D、 32 5、深度为 5 的二叉树至多有_个结点。 A、16 B、32 C、31 D、10 6、设高度为h的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为_ A、 2h B、 2h-1 C、 2h+1 D、 h+1 7、 对一个满二叉树，m 个树叶，n 个结点，深度为 h，则_ 。 h A、 n=h+m B、 h+m=2n C、 m=h-1 D、 n

41、=2 -1 8、 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_。 A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 个。 _。 9、 如果某二叉树的前根次序遍历结果为 stuwv，中序遍历为 uwtvs，那么该二叉树的后序为_。 A、 uwvts B、 vwuts C、 wuvts D、 wutsv 10、 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_。 A、 正确 B、 错误 11、 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访 问顺序是_。 A、 bdgcefha

42、B、 gdbecfha C、 bdgaechf D、 gdbehfca 12、 在一非空二叉树的中序遍历序列中，根结点的右边_。 A、 只有右子树上的所有结点 a C、 只有左子树上的部分结点 b c B、 只有右子树上的部分结点 D、 只有左子树上的所有结点 13、 如图 6、1 所示二叉树的中序遍历序列是_。 d e f g A、 abcdgef B、 dfebagc C、 dbaefcg D、 defbagc 11a b d e g 图6.2 图 6、1 c f h 14、 一棵二叉树如图 6、2 所示，其中序遍历的序列为_ _ A、 abdgcefh B、 dgbaechf C、 gd

43、behfca D、 abcdefgh 15、设 a,b 为一棵二叉树上的两个结点，在中序遍历时，a 在 b 前的条件是 A、a 在 b 的右方 B、a 在 b 的左方 C、a 是 b 的祖先 D、a 是 b 的子孙 。 16、 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是_。 A、 acbed B、 decab C、 deabc D、 cedba 17、 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用_存储结构。 A、 二叉链表 B、 广义表存储结构 C、 三叉链表 D、 顺序存储结构 18、 如图 6、3 所示的 4 棵二

44、叉树，_不是完全二叉树。 (A) (B) 图6.3 (C) (D) 19、 如图 6、4 所示的 4 棵二叉树，_是平衡二叉树。 20、在线索化二叉树中，t 所指结点没有左子树的充要条件是_。 A、 t.left=NULL C、 t.ltag=1 且 tleft=NULL B、 t.ltag=1 D、 以上都不对 21、 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_。 A、 正确 B、 错误 22、 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 A、 正确 B、 错误 23、 具有五层结点的二叉平衡树至少有_个结点。 A、 10 B、 12

45、C、 15 D、 17 24、 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。12 这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论_是正确的。 A、树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B、树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C、树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D、以上都不对 25、 树最适合用来表示_。 A、 有序数据元素 C、 元素之间具有分支层次关系的数据 26、下列有关二叉树的说法正确的是( )。 B、 无序数据元素 D、 元素之间无联系的数据 A、二叉树的度为 2 C、

46、二叉树中至少有一个结点的度为 2 27、以下说法错误的是( )。 A、二叉树可以是空集 B、 一棵二叉树度可以小于 2 D、 二叉树中任一个结点的度都为 2 B、 二叉树的任一结点都可以有两棵子树 C、二叉树与树具有相同的树形结构 D、 二叉树中任一结点的两棵子树有次序之分 28、假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30 个，则叶子结点数为( A、15 B、 16 C、 17 D、47 29、由带权为 9,2,5,7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为( )。 A、 23 B、 37 C、 46 D、 44 30.在一棵具有 n 个结点的二叉树第 i 层

47、上，最多具有( )个结点。 i i+1 i-1 n A、2 B、 2 C、 2 D、 2 答案：1-5 BBCCC 6-10 ADACA 11-15 DABBB 16-20 DCCBB 21-25 BBBAC 26-30 BCBDC 二、填空题： 1、 有一棵树如图 6、5 所示，回答下面的问题： 这棵树的根结点是_； 这棵树的叶子结点是_； 结点 D 的度是_； 这棵树的度是_； 这棵树的深度是_； 结点 H 的子女是_； 图6.5 一棵树 结点 H 的双亲结点是_； (8)结点 N 的祖先是_。 )个。 2、 深度为 k 的完全二叉树至少有_个结点。至多有_ 右次序给结点编号（从 1 开始） ，则编号最小的叶子结点的编号是 3、 在一棵二叉树中，度为零的结点的个数为n 2的 0，度为 4、 一棵二叉树的第 i（i1）层最多有_个结点，最少含 个结点，若按自上而下，从左到 _。 结点的个数为 n 2， 则有n0=_。 有_个结点；一棵有 n（n>0） 13个结点的满二叉树共有_个叶子和_个非终端结点。 5、高度为 k 的二叉树最多有_个结点，最少有_个结点。 6、 由如图 6、7 所示的二叉树，回答以下问题： 其中序遍历序列为_； 其前序遍历序列为_； 其后序遍历序列为_； 7、对于一个具有 n 个结点的二叉树，当它为一棵 具有 高度，即