数 据 结 构 习 题
计算机学院专业基础教研室
2012年12月
1
前 言
数据结构是计算机相关专业教学计划中的一门核心课程，是有志从事计算机与技术工作的人员的一门重要的专业基础课程。计算机相关学科各领域都要用到各种数据结构，要从事这些领域的工作，尤其是计算机应用领域的开发研制工作，必须具备良好的数据结构基础。
数据结构课程的教学要求是学会分析研究计算机加工的数据对象的特征，以便在实际应用中选择适当的数据结构、存储结构和相应的算法，初步掌握算法的时间与空间性能分析技巧，得到复杂程序设计的训练。
我们在认真总结多年教学经验和体会的基础上，结合新时期大学生的学习特点和要求，编写了这本《数据结构习题》，作为数据结构课程学习的配套教材，以希望通过习题的求解，使学生更好地学习和掌握课程内容，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。
由于时间仓促和编者水平所限，本书一定还存在着许多问题，敬请广大读者批评指正。
2
目 录
第一章 绪论????????????????????????????? 1 第二章 线性表???????????????????????????? 6 第三章 栈和队列???????????????????????????12 第四章 串?????????????????????????????‥19 第五章 数组和广义表????????????????????????‥22 第六章 树和二叉树????????????????????????‥‥28 第七章 图?????????????????????????????‥33 第九章 查找????????????????????????????‥38 第十章 内部排序???????????????????????????41
3
第一章 绪论
一、选择题
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．以下那一个术语与数据的存储结构无关？（ ）
1
A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．线性表若采用链式存储结构时，要求内存中可用存储单元的地址（①）。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续或不连续都可以 12．在以下的叙述中，正确的是（①）。
A．线性表的线性存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出
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. 单链表 18.一个数据对象是（ ）的集合。
A.相同类型的数据项 B.相同类型的数据元素
C.不同类型的数据项 D.不同类型的数据元素 19. ( )是数据的基本单位。
A.数据项 B.关键字 C.数据元素 D.数据类型 20.数据结构在计算机中的表示称为数据( )。 A.对象 B.的存储结构 C.类型 D.元素 21.下列程序段的时间复杂度为( )。 { for(i=0；i<5；i++) for(j=0；j A.O(5) B.O(5+n) C.O(n5 ) D.O(n) 22．数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间 2 的（②）和运算等的学科。 ①A．操作对象 B．计算方法 C．逻辑存储 D．数据映象 ②A．结构 B．关系 C．运算 D．算法 23．数据结构被形式地定义为（K，R），其中K是（①）的有限集合，R是K上的（②） 的有限集合。 ①A．算法 B．数据元素 C．数据操作 D．逻辑结构 ②A．操作 B．映象 C．存储 D．关系 24．在数据结构中，从逻辑上可以把数据结构分成（①）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 25．线性表的顺序存储结构是一种（①）的存储结构，线性表的链式存储结构是一种 （②）的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 26．算法分析的目的是（①），算法分析的两个主要方面是（②）。 ①A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 27．计算机算法指的是（①），它必具备输入、输出和（②）等五个特性。 ①A．计算方法 B．排序方法 C．解决问题的有限运算序列 D．调度方法 ②A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性 C．确定性、有穷性和稳定性 D．易读性、稳定性和安全性 28．线性表的逻辑顺序与存储顺序总是一致的，这种说法（①）。 A．正确 B．不正确 二、填空题 1．数据的物理结构包括 的表示和 的表示。 3 2. 对于给定的n个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） ， __（4）四种。 3．数据的逻辑结构是指 。 4．一个数据结构在计算机中 称为存储结构。 5．抽象数据类型的定义仅取决于它的一组__（1）_，而与_（2）_无关，即不论其内 部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。 6．数据结构中评价算法的两个重要指标是 7. 数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这 种结构定义相应的_（3）_，设计出相应的（4）_。 8． 一个算法具有5个特性: （1） 、 （2） 、 （3） ，有零个或多个输入、有一 个或多个输出。 9． 下面程序段的时间复杂度为________。(n>1) sum=1； for (i=0;sum 10．计算机执行下面的语句时，语句s的执行次数为 _______ 。 FOR(i=l；i 11.下面程序段中带下划线的语句的执行次数的数量级是： i：=1； WHILE i 三、基础知识题 1．数据结构是一门研究什么内容的学科？ 2．数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 3．数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类 型的主要特点是什么？使用抽象数据类型的主要好处是什么？ 4．回答问题（每题2分） （1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存 在着怎样的关系？ （2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？ 举例说明之。 （3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同 的数据结构。这样说法对吗？举例说明之。 （4）评价各种不同数据结构的标准是什么？ 4 5．评价一个好的算法，您是从哪几方面来考虑的？ 6．解释和比较以下各组概念 抽象数据类型及数据类型 数据结构、逻辑结构、存储结构 抽象数据类型 算法的时间复杂性（5） 算法（6）频度 7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？ 8．对于一个数据结构，一般包括哪三个方面的讨论？ 9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？ 10. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？ 11．数据结构与数据类型有什么区别？ 12．数据的存储结构由哪四种基本的存储方法实现？ 13．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最 方便，写出这些结构？ 14. 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存 储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。 15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么? 16. 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运 算效率不同。 17. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2)，A2的 时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。 18．设计一数据结构，用来表示某一银行储户的基本信息： 账号、姓名、开户年月 日、储蓄类型、存入累加数、利息、帐面总数。 5 n 第二章 线性表 一 、 选择题 1．下述哪一条是顺序存储结构的优点？（ ） A． 存储密度大 B．插入运算方便 B． C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运 算，则利用（ ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省 时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。 A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ ）. A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 6 9. 链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 11． 双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链 表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点） A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p); B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink; C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink; D．以上A，B，C都不对。 12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ ） A．（1），（2） B．（1） C．（1），（2）,(3) D.（2） 13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法 的时间复杂度为（ ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 14. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 15．线性表（ a1,a2,?,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1） 16．非空的循环单链表head的尾结点p↑满足（ ）。 A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head 17．循环链表H的尾结点P的特点是（ ）。 A．P^.NEXT:=H B．P^.NEXT:= H^.NEXT C．P:=H D．P:=H^.NEXT 7 18．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（） A. p＾.next=h B. p＾.next=NIL C. p＾.next.＾next=h D. p＾.data=-1 19．完成在双循环链表结点p之后插入s的操作是（ ）； A． p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next; B． p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.next:=p^.next; C． s^.priou:=p; s^.next:=p^.next; p^.next:=s; p^.next^.priou:=s ; D． s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ; p^.next:=s; 20．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。 注:双向链表的结点结构为(llink,data,rlink)。 供选择的答案： A． p↑.llink：=q； q↑.rlink：=p； p↑.llink↑.rlink：=q；q↑.llink：=q； B． p↑.llink：=q； p↑.llink↑.rlink：=q ； q↑.rlink：= p； q↑.llink:=p↑.llink； C． q↑.rlink：=p； q↑.llink：=p↑.llink； p↑.llink↑.rlink：=q; p↑.llink：=q; D． q↑.llink:=p↑.llink；q↑.rlink:=p； p↑.llink：=q；p↑.llink：=q； 21．在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为: rlink(p) ← q; llink(p) ← llink(q); llink(q) ← p; （ ） A．rlink(q) ← p B．rlink(llink(q)) ← p C．rlink(llink(p)) ← p D．rlink(rlink(p)) ← p 22． 双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ） A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink; B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink; C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p; D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q; 23．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。 A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink; C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; 8 24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 26. 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 A． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink; B． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p; C． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink D． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink; 二、填空题 1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。 2．线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。 3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______; 4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。 5．在单链表中设置头结点的作用是________。 6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。 7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。 8．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、 _______、_______、________。 9．在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句： s^ .next:=p； s^ .prior:= ________；p^ .prior:=s；________:=s； 10.链接存储的特点是利用________来表示数据元素之间的逻辑关系。 11.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过 9 ________表示元素之间的关系的。 12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链 表为_______个。 13. 循环单链表的最大优点是：________。 14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________ 15. 带头结点的双循环链表L中只有一个元素结点的条件是：________ 16. 在单链表L中，指针p所指结点有后继结点的条件是：__ 17.带头结点的双循环链表L为空表的条件是：________。 18. 在单链表p结点之后插入s结点的操作是：_______。 三、解答题 1．线性表有两种存储结构：一是顺序表，二是链表。试问： （1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性 表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取 线性表中的元素，那么应采用哪种存储结构？为什么？ 2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大 量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。 3．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？ 为什么？ 4．线性结构包括______、______、_______和_______。线性表的存储结构分成______ 和______。请用类PASCＡL语言描述这两种结构。 5．线性表（a1，a2，?，an）用顺序映射表示时，ai和ai+1（1<=i 6. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首 元结点的关系。 7. 试述头结点,首元结点,头指针这三个概念的区别. 8．有线性表(a1,a2,?,an),采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。 （1）线性表中元素无序。（2）线性表中元素按递增有序。 （3）线性表中元素按递减有序。 10 9. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? 10. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链 表？ 11. 设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C 语言语句。 12. 设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next， 请写出在p结点之前插入s结点的操作（PASCAL语句）。 四、算法设计题 1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法 将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 2. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点 个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。 3．在带头结点的单链表上，给出求表长Length(L)的算法，并加入简要的注释或说 明。 4．设单链表具有头结点，且表中元素各不相同，试给出在单链表中查找值为\的结 点的算法，并加入简要的注释或说明。 5．设单链表具有头结点，且表中元素各不相同，试给出在单链表中删除值为\的结点的算法。 11 第三章 栈和队列 一、 选择题 1. 对于栈操作数据的原则是（ ）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ③ , ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3，?，pN,若pN是n，则pi是( )。 A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 12 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列 的是（ ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的 序列为（ ）。 A．fedcba B. bcafed C. dcefba D. cabdef 12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排 列是( )。 A．XYZ B. YZX C. ZXY D. ZYX 13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ） A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 14. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确 操作是( )。 A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1 C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1 15. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 16. 栈在（ ）中应用。 A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 17. 一个递归算法必须包括（ ）。 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 18. 执行完下列语句段后，i值为：（ ） int f(int x) { return ((x>0) ? x* f(x-1):2);} 13 int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 19. 表达式a*(b+c)-d的后缀表达式是( )。 A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 20. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ）， 其中^为乘幂 。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构 最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 22. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 D. 头、尾指针可能都要修改 C. 头、尾指针都要修改 23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向 队尾结点，则在进行删除操作时( )。 A．仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改 24. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结 构。 A．队列 B．多维数组 C．栈 D. 线性表 25. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前 队列中的元素个数为（ ）。 A．(rear-front+m)%m C．(front-rear+m)%m B．rear-front+1 D．(rear-front)%m 26. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则 当前队列中的元素数是( )。 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 27. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) 14 C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 28. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 29. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对 30. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也 不能由输出受限的双端队列得到的输出序列是( )。 A. 1234 B. 4132 C. 4231 D. 4213 31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 C．rear+1=front D. (rear-l) MOD n=front 32. 栈和队列的共同点是（ ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 33. 栈的特点是（ ① ）,队列的特点是（ ② ）,栈和队列都是（ ③ ）。若 进栈序列为1,2,3,4 则（ ④ ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ ⑤ ）是一个出队列序列。 ①, ②: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 ③: A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构 ④, ⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4 34. 栈和队都是（ ） A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构 35. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S， 一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 15 A. (rear+1) MOD n=front B. rear=front A． 6 B. 4 C. 3 D. 2 36. 用单链表表示的链式队列的队头在链表的（ ）位置。 A．链头 B．链尾 C．链中 37. 依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进一个元素，机器可要求 下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？ A．{d ，e，c，f，b，g，a} B. {f，e，g，d，a，c，b} C. {e，f，d，g，b，c，a} D. {c，d，b，e，f，a，g} 二、填空题 1．栈是_______的线性表，其运算遵循_______的原则。 2．_______是限定仅在表尾进行插入或删除操作的线性表。 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。 4. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5， 经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。 5. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_______，栈2空时 ，top[2]为_______，栈满时为_______。 6．两个栈共享空间时栈满的条件_______。 7．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。 8. 多个栈共存时，最好用_______作为存储结构。 9．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342 出栈顺序，相应的S和X的操作串为_______。 10. 顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是 _______。 11．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。 12. 循环队列的引入，目的是为了克服_______。 13．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效 下标范围内循环， M= _______。 14．________又称作先进先出表。 16 15. 队列的特点是_______。 16．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 _______。 17. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 18．区分循环队列的满与空，只有两种方法，它们是______和______。 19．设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队 满的条件为_______。 20. 设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的 出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。 三、基础知识题 1．名词解释：栈。 2．名词解释：队列 3．什么是循环队列？ 4．假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。 （1）试指出判别给定序列是否合法的一般规则。 （2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得 到，请举列说明。 5. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？ 6.如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。 7. 若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E、D 和D、B、A、C、E？为什么？ 8. 设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。 9. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？ 10. 试证明：若借助栈由输入序列1,2,?,n得到输出序列为P1,P2,?,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i 11. 设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈 17 和出栈操作，试问通过入出栈操作的合法序列。 能否得到输出顺序为325641的序列。 能否得到输出顺序为154623的序列。 12.（1） 什么是递归程序？ （2） 递归程序的优、缺点是什么？ （3） 递归程序在执行时，应借助于什么来完成？ （4） 递归程序的入口语句、出口语句一般用什么语句实现？ 13. 在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点？ （1）分别用多个顺序存储空间建立多个独立的堆栈； （2）多个堆栈共享一个顺序存储空间； （3）分别建立多个独立的链接堆栈。 14．在某程序中，有两个栈共享一个一维数组空间SPACE[N]、SPACE[0]、SPACE[N-1] 分别是两个栈的栈底。 （1）对栈1、栈2，试分别写出（元素x）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2，试分别写出栈满、栈空的条件。 15. 简述顺序存储队列的假溢出的避免方法及队列满和空的条件。 16. 举例说明顺序队的“假溢出”现象，并给出解决方案。 17. 怎样判定循环队列的空和满？ 18. 简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队首指 针与队尾指针的值。 四、算法设计 1．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的初始化队列、入队列和出队列算法。 2．借助栈(可用栈的基本运算)来实现单链表的逆置运算。 3．假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如（.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .)。试利用栈的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。 18 第四章 串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的？（ ） A． 串是字符的有限序列 B．空串是由空格构成的串 C． 模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 .若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（ ） A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ） A．求子串 B．联接 C．匹配 D．求串长 4．已知串S=‘aaab’,其Next数组值为（ ）。 A．0123 B．1123 C．1231 D．1211 5．串 ‘ababaaababaa’ 的next数组为（ ）。 A．012345678999 B．012121111212 C．011234223456 D．0123012322345 6．字符串‘ababaabab’ 的nextval 为（ ） A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1) C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 ) 7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ ），nextval数组的值为 （ ）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 19 8．若串S=’software’,其子串的数目是（ ）。 A．8 B．37 C．36 D．9 9．设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。 A．2n-1 B．n2 C．(n2/2)+(n/2) D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况 10．串的长度是指（ ） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 二、填空题 1.空格串是指__(1)__，其长度等于___(2)__。 2.组成串的数据元素只能是________。 3.一个字符串中________称为该串的子串 。 4.INDEX（‘DATASTRUCTURE’， ‘STR’）=________。 5．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。 6．模式串P=‘abaabcac’的next函数值序列为________。 7．字符串’ababaaab’的nextval函数值为________。 8．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为__(1)__，又称P 为__(2)__。 9．串是一种特殊的线性表，其特殊性表现在__(1)__；串的两种最基本的存储方式是__(2)__、__(3)__；两个串相等的充分必要条件是__(4)__。 10．两个字符串相等的充分必要条件是_______。 11．知U=‘xyxyxyxxyxy’；t=‘xxy’； ASSIGN（S，U）； ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））； ASSIGN（m，‘ww’） 求REPLACE（S，V，m）= ________。 12．实现字符串拷贝的函数 strcpy为： void strcpy(char *s , char *t) /*copy t to s*/ { while (________) } 13．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(\返 20 回1，f(\返回0； int f((1)________) {int i=0,j=0; while (s[j])(2)________; for(j--; i 三、基础知识题 1．名词解释：串 2．描述以下概念的区别：空格串与空串。 3．两个字符串S1和S2的长度分别为m和n。求这两个字符串最大共同子串算法的时间复杂度为T(m,n)。估算最优的T(m,n)，并简要说明理由。 4．设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？ 5．KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进? 6．已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和 nextval函数值。 7．给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。 8．令t=‘abcabaa’,求其next 函数值和nextval函数值。 9．已知字符串‘cddcdececdea’，计算每个字符的next和nextval函数的值。 四、算法设计 1．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。（注：用程序实现） 2．输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入ａ［０］,456放入ａ［１］，? ? 。编程统计其共有多少个整数，并输出这些数。 3． 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。 4．编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。 5．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。 21 第 五 章 数组和广义表 一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案： ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤：A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组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 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（ ① ）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（ ② ） 和（ ③ ）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（ ④ ）和（ ⑤ ）。 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 22 7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中， A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ ）。供选择的答案： A. 198 B. 195 C. 197 8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（ ）内的正确答案。 （1）存放A至少需要（ ）个字节； （2）A的第8列和第5行共占（ ）个字节； （3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（ ）的起始地址一致。 供选择的答案： （1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150 （3）A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9] 9. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,?,8,列下标j=1,2,?,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。 A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9] 10. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所 有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i 11. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( )。 A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1 12. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1） /2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 13. 设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。 A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-1 14. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三 23 元组表示该矩阵时，所需的字节数是（ ）。 A. 60 B. 66 C. 18000 D. 33 15. 数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。【中山大学 1998 二、5 （2分）】 A. 55 B. 45 C. 36 D. 16 16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点， 使j 沿链移动的操作为( )。 A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 17. 对稀疏矩阵进行压缩存储目的是（ ）。 A.便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 18. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ ）。 A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail（L）））)） 19. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的 运算是( )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 20. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。 Head(Tail(Head(Tail(TailA)))) A. (g) B. D C. c D. d 21. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tailC)) =( )。 A.（a） B. A C. a D. B E. b F. (A) 22. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）。 A. (c,d) B. c,d C. ((c,d)) D. d 23. 广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ ）。 A. c B. b，c C.（b，c） D.（（b，c）） 24. 广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 25. 广义表（a,(b,c),d,e）的表头为（ ）。 A. a B. a,(b,c) C. (a,(b,c)) D. A 26. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 24 27. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、 填空题 1.数组的存储结构采用_______存储方式。 2.设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为__（1）_；如按列优先顺序存储,则元素A[-18,-25]的存储地址为__（2）_。 3.设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）_。 4.将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。 5.二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储) 6.设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为_______。 7.已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。 8.已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：_______。 9.用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_（1）_行，第_（2）_列的元素。 10.设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （l） 存放该数组至少需要的单元数是_______; （2） 存放数组的第8列的所有元素至少需要的单元数是_______; （3） 数组按列存储时，元素A[5,8]的起始地址是_______。 11. 当广义表中的每个元素都是原子时，广义表便成了_______。 12. 广义表的表尾是指除第一个元素之外，_______。 13. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅 在于 (1)____。为了区分原子和表，一般用 (2)____表示表，用 (3)_____ 25 表示原子。一个表的长度是指 (4)__，而表的深度是指__(5)__ 14. 广义表的_______ 定义为广义表中括弧的重数。 15．设广义表L=((),()), 则head(L)是(1)___；tail(L)是(2)____；L的长度是 (3)___；深度是 (4)__。 16. 已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和 Tail( )将原子元素99从A中取出来 。 17. 广义表的深度是_______。 三、基础知识题 1. 数组A[1..8，-2..6，0..6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4,2,3]的存储首地址。 2. 已知b对角矩阵（aij）n*n，以行主序将b条对角线上的非零元存储在一维数组中，每个数据元素占Ｌ个存储单元，存储基地址为Ｓ，请用i，j 表示出 aij的存储位置。 3. 数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从 1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： （1）存放该数组所需多少单元？ （2）存放数组第4列所有元素至少需多少单元？ （3）数组按行存放时，元素A[7,4]的起始地址是多少？ （4）数组按列存放时，元素A[4,7]的起始地址是多少？ 4．假设按低下标优先存储整型数组A（-3:8,3:5,-4:0,0:7）时，第一个元素的字节存储地址是100，每个整数占4个字节，问A（0，4，-2，5）的存储地址是什么？ 5．设有三维数组A[-2:4,0:3,-5:1]按列序存放，数组的起始地址为1210，试求 A(1,3,-2)所在的地址。 6. 三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100，试求元素A[5,0,7] 的存贮首地址。 四、 算法设计题 1. 设有大小不等的n 个数据组（n个数据组中数据的总数为m），顺序存放在空间区 D内,每个数据占一个存储单元，数据组的首地址由数组S给出，（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。 2. 数组 H[ 1：1000] 中存放着1000个大小不同的正整数; 26 （1） 选择一分类算法使能最快地得到其中10个最大的数，简要说明理由； （2） 编写一程序seek() ，执行该程序时，在命令行中提供二个参数； seek a n seek I n 27 第六章 树和二叉树 一、选择题 1．树最适合用来表示（ ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 2．深度为5的二叉树至多有（ ）个结点。 A． 16 B． 32 C． 31 D． 10 3．有32个结点的完全二叉树的深度为（ ）（根的层次为1）。 A．8 B．7 C．6 D．5 4．若二叉树中度为2的结点有15个，度为1的结点有10个，则有（ ）个叶结 点。 A．25 B．15 C．16 D．41 5．在有n个结点的二叉链表中值为非空的链域的个数为（ ）。 A． n-1 B 2n-1 C n+1 D 2n+1 6．有64个结点的完全二叉树的深度为（ ）（根的层次为1）。 A．8 B．7 C．6 D．5 7．对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列 均相同。 A． 3 B． 1 C． 2 D． 不存在 8．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）二叉树。 A． 空或只有一个结点 B． 高度等于其结点数 C． 任一结点无左孩子 D． 任一结点无右孩子 9．前序遍历与中序遍历结果相同的二叉树为（ ）；前序遍历和后序遍历结果相同的二叉树为（ ）。 A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树 10．设n, m为一棵二叉树上的两个结点，在中序遍历时n在m前的条件是（ ）。 A． n在m右方 B． n在m左方 C． n是m祖先 D． n是m子孙 11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。 A． 不发生改变 B． 发生改变 28 C． 不能确定 D． 以上都不对 12．线索二叉树是一种（ ）结构。 A． 逻辑 B． 逻辑和存储 C． 物理 D． 线性 13. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先 序遍历、中序遍历和后序遍历。如把由树转化得到的二叉树叫做这棵树对应的二叉树，则结论（ ）是正确的。 A． 树的先根遍历序列与对应的二叉树的先序遍历序列相同 B． 树的后根遍历序列与对应的二叉树的后序遍历序列相同 C． 树的先根遍历序列与对应的二叉树的中序遍历序列相同 D． 以上都不对 14．设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所含的结点数 至少为（ ）。 A． 2h B． 2h-1 C． 2h+1 D． h+1 15. 设bt是某树的二叉树表示的根结点指针，则bt满足（ ）。 A． bt->lchild==bt->rchild B． bt->rchild==NULL C． bt->lchild==NULL D． bt==NULL 16．设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（ ）。 A．2n+2 B． 2n+1 C． 2n D． 2n-1 17．设哈夫曼树的叶子结点数为n，则它的结点总数为（ ）。 A． 2n-1 B． 2n C． 2n+1 D． 不确定 18．由带权9、1、3、5、6的5个叶子结点生成的哈夫曼树的带权路径长度为（ ）。 A． 50 B． 60 C. 52 D. 65 19．二叉树的先序遍历序列和中序遍历序列分别为：EFHIGJK和HFIFJKG,该二叉树根 的右子树的根是（ ）。 A． E B． F C. G D. H 20．下列有关二叉树的叙述中正确的是（ ）。 A． 二叉树的度为2 B． 任何一棵二叉树中至少有一个结点的度为2 C. 度为0的树是一棵二叉树 D. 二叉树中任何一个结点的度为2 21．二叉树上叶结点数等于（ ）。 A． 分支结点数加１ B． 单分支结点数加１ C. 双分支结点数加１ D. 双分支结点数减１ 22．判断线索二叉树中p所指结点由左孩子的条件是（ ）。 29 A． p!=UNLL B． p->lchild!=NULL C. p->ltag==0 D. p->ltag==1 二、填空题 1. 具有n个结点的完全二叉树的深度为 。 2. 二叉树第i层上最多有 个结点。 3. 深度为k的二叉树最多有 个结点。 4．具有n个结点的二叉树的最小深度为 ，最大深度为 ；具有具有n个结点的度为2的树的最小深度为 ，最大深度为 。 5．具有m个叶结点的huffman树共有 个结点。 6．完全二叉树T按顺序存放，编号依次为1,2,...,n,则编号为i的结点左孩子如果存在的话，其编号为 。 7．在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。 8．三个结点a,b,C．组成二叉树，共有 种不同的结构。 9. 一颗树T中，包括1个度为1的结点，2个度为2的结点，3个度为3的结点，则T的叶子结点数为 。 10．已知某完全二叉树采用顺序存储结构，结点的存放顺序为（A,B,C,D,E,F,G,H,I,J），该完全二叉树的后根遍历序列为 。 11．前序遍历序列是abc且后序遍历序列为cba的二叉树共有 棵。 12. F是由T1, T2, T3三棵树组成的森林，T1, T2, T3 的结点数分别为n1,n2,n3,则F对应的二叉树B(F)的根的左子树中结点数为 ，根的右子树中的结点数为 。 三、基础知识题 1．已知一棵树遍的集合为{ (7) 哪些是结点e的兄弟？哪些是结点f的兄弟？ (8) 结点b和n的层次号分别是什么？ 30 (9) 树的深度是多少？ (10) 以结点c为根的子树的深度是多少？ (11) 树的度数是多少？ 2．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，?，nk个度为k 的结点，问该树中有多少个叶子结点？ 4．对题2所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 5．现有按先序遍历二叉树的结点序列为abc，试写出能得到这一遍历结果的各种二 叉树。 6．一棵非空的二叉树其先序序列和后序序列正好相反，说明这棵二叉树的形状。 7．分别画出和下列树对应的二叉树。 A B 8．画出和下列二叉树相应的森林。 A B 9．以数据集{4，5，6，7，10，12，18}为结点权值构造的Huffman树，并求其带权 路径长度。 10．假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出 31 该树并给出其后序序列。 12. 已知某二叉树按后序遍历序列为CEDBHJIGFA，按中序遍历序列为CBEDAHGIJF, 试画出该二叉树形状（要求写出中间过程）， 并写出它的先序遍历序列。 13. 设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,试为这六个字母设 计huffman编码并画出对应huffman树。 14. 对给出的数据序列4,5,6,7,10,12,15,18,23，构造一棵huffman树，并求其带 权路径长度。 15．设a,b,c,d,e,f,g,h,i九个字母出现的次数分别为4,5,6,7,10,12,15, 18,23， 构造一棵huffman树，并给出每个字符的huffman编码。 16. 设一棵二叉树的先序、中序遍历序列分别为EBADCFHGIKJ和ABCDEFGHIJK，要求： (1) 画出该二叉树(要求写出中间步骤); (2)将这棵二叉树转换成对应的树(或森林)。 17.设一份电文中a,b,c,d,e,f,g,h八个字母出现的次数分别为7,19,2,6,32,3,21, 10, 要求： (1) 为每个字母设计huffman编码, (2) 给出八个字母二进制表示的等长编码并比较两方案的优缺点。 18．证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。 19. 证明一棵二叉树无论进行先序、中序或后序遍历，其叶结点的相对次序不发生改 变。 四、算法设计题 1．试给出二叉树先序遍历的非递归形式的算法。 2．试写出按层次遍历二叉树的算法。 3．以二叉链表作存储结构，试编写求二叉树深度的算法。 4．设一棵二叉树以二叉链表存储，试设计算法求此二叉树上叶子结点个数。 5．设一棵二叉树以二叉链表存储，试设计算法求此二叉树上度为2的结点个数。 6．试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子结点个数。 7．设计一个算法，统计二叉树中 等于给定值x的结点个数。 8．设计一个算法，从一棵二叉树中查找出所有结点的最大值。 9．编写递归算法，将二叉树中所有结点的左、右子树相互交换。 10．编写求任意二叉树中一条最长的路径的算法，要求输出此路径上各结点的值及路径的长度。 11．设一棵树以孩子-兄弟表示法存储，试编写计算树的深度的算法。 32 第七章 图 一、选择题 1．具有4个顶点的无向完全图有（ ）条边。 A． 6 B．12 C. 16 D． 20 2．对于具有n个顶点的连通无向图，其边的个数至少为（ ）。 A． n-1 B．n C． n+1 D． nlogn 3．G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A． 6 B．7 C． 8 D． 9 4．对于具有n个顶点的强连通图，其弧条数的最小值为（ ）。 A． n+1 B．n C． n-1 D． n-2 5. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍；在一个有向图中， 所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 A． 1/2 B． 2 C． 1 D． 4 6．图的深度、广度优先遍历算法分别类似于二叉树的（ ）。 A． 先序遍历和中序遍历 C． 后序遍历和中序遍历 B． 先序遍历和层序遍历 D． 层序遍历和先序遍历 7. 有n个顶点e条边的无向图G,它的邻接表中的表结点总数是( ) A． 2n B．n C． 2e D． e 8. 连通图G中有n个顶点,G的生成树是( )连通子图. A． 包含G的所有顶点 B． 不必包含G的所有顶点 C． 包含G的所有边 D． 包含G的所有顶点和所有边 9. 下面关于图的存储的叙述中正确的是（ ） A．用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边 数无关 B．用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个 数无关 C．用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数 无关 D．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数 无关 10．对一个具有n个顶点和e条边的无向图，若采用邻接表存储，则表结点数是( ⒀ )。 A． n+e B． 2e C． e D． n 11．设图G用邻接表存储，则拓扑排序的时间复杂度为（ ）。 33 A． O(n) B． O(n+e) C． O(n2) D． O(n×e) 12．可以进行拓扑排序的图一定是（ ）。 A． 连通图 B． 带权连通图 C． 无回路的图 D． 无回路的有向图 13．下面（ ）可以判断出一个有向图中是否有环（回路）？ A． 求关键路径 B． 拓扑排序 C． 求最短路径 D． 前面都不正确 14．关键路径是事件结点网络中的（ ）。 A． 从源点到汇点的最长路径 B． 从源点到汇点的最短路径 C． 最长的回路 D． 最短的回路 15．下列说法错误的是（ ）。 A． 一个图的邻接矩阵表示是唯一的 B． 一个图的邻接表表示是唯一的 C． 一个图的生成树必为该图的极小连通子图 D． 一个无环有向图的拓扑排序序列必唯一 16．导致图的遍历序列不唯一的因素有（ ）。 A． 出发点不同、遍历方法不同 B． 出发点不同、存储结构不同 C． 遍历方法不同、存储结构不同 D． 出发点不同、存储结构不同、遍历方法不同 17．已知某有向图 （ ）。 A． V3,V1,V4,V5,V2,V6 B． V3,V4,V1,V5,V2,V6 C． V1,V3,V4,V5,V2,V6 D． V1,V4,V3,V5,V2,V6 18. 若一个有向图具有拓扑排序序列，并且顶点按拓扑排序序列编号，那么它的邻 接矩阵必定为（ ）。 A． 对称矩阵 B． 稀疏矩阵 C． 三角矩阵 D． 一般矩阵 二、填空题 1．图的主要存储结构有两种，分别为 和 。 2．对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为 。 3.已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是 。 34 G=(V,E),其中V={V1,V2,V3,V4,V5,V6}, E={ 4．已知无向图的结点个数为n，边的个数为e，则在其邻接表的存储结构中，表结点 与头结点共有 个。 5．若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的 ，它所用到的 数据结构为 。 6．若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的 ，它所用到的 数据结构为 。 7. G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的 每个顶点，则该图一定是 图。 8 n个顶点的连通图的生成树有 条边。 9. AOV-网以结点和有向边分别代表 。 10. AOE-网以结点和有向边分别代表 。 三、基础知识题 1．有如下数据结构的形式定义，试画出此结构的图形表示。 DS={D, S}, 其中：D={1, 2, 3, 4}, S={R}, R={<1,2>,<1,3>,<2,3>,<2,4>,<3,4>}。 2．已知如下图所示的有向图，请给出该图的 （1）每个顶点的入/出度； （2）邻接矩阵； （3）邻接表。 3．什么是无向图的连通分量和生成树？ 4．如果含n个顶点的图形成一个环，则它有多少棵生成树？ 5．对于n顶点的无向图G，采用邻接矩阵A表示，如何判断下列问题： (1) 图中有多少条边？ (2) 任意两个顶点i和j是否有边相连？ 35 (3) 任意一个顶点的度是多少？ 6．求网的最小生成树有哪些算法？各适用于何种情况？为什么？ 7．给出下列无向图的邻接表存储结构，并由邻接表写出由E出发的广度优先搜索序 列和深度优先搜索序列。 8．下图为一无向连通网络，分别根据普里姆(Prim)算法和克鲁斯卡尔(Kruscal)算法从顶点１出发构造出它的最小生成树。 9. 对如下带权图，请： (1) 给出结点的一个拓扑序列；（2）找出一条从v1 到v7 的最短路径（要求写出求解步骤）。 36 10．对下图所示的AOE网络，给出其关键路径。 四、算法设计题 1．编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建 立有向图的邻接表。 2. 假设图采用邻接表存储，编写利用深度优先搜索方法和广度优先搜索方法遍历图 的算法。 3．试基于图的深度优先搜索方法和广度优先搜索方法编写算法，判断以邻接表方式 存储的有向图中是否存在由顶点到顶点vj的路径(i≠j)。 4．采用邻接表存储结构，编写一个判断无向图中任意给定的两各顶点之间是否存在 一条长度为k的简单路径的算法。 37 第九章 查找 一、选择题 1．顺序查找法适合于存储结构为（ ）的线性表。 A．散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 2．二分查找法要求查找表中各元素的关键字必须是（ ）排列。 A．递增或递减 B.递增 C. 递减 D.无序 3．在长度为n的线性表中使用顺序查找法的平均查找长度是( )。 A． O(1) B． O(n) C.O(log2n) D．O(n) 4．在长度为n的有序表中使用二分查找法的平均查找长度是( )。 A． O(1) B． O(n) C．O(log2n) D．O(n2) 5．对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标依次为 ( )。 A． 1，2，3 B． 9，5，2，3 C． 9，5，3 D． 9，4，2，3 6．有一个有序表为{3，9，12，32，41，45，62，75，77，82，99} ，用二分查找法 查找82成功时的查找次数是( )。 A． 1 B． 2 C． 3 D． 4 7．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（ ） 查找方法。 A． 分块 B． 顺序 C． 二分 D． 散列 8．在下列查找方法中，平均查找速度最快的是（ ）。 A． 分块查找 C． 二分查找 量级相当。 A． 分块查找 C． 二分查找 B． 顺序查找 D． 前面都不正确 B． 顺序查找 D． 二叉排序树查找 2 9．在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与（ ） 10．在二分查找中，第i次查找成功的记录个数最多为（ ）。 A． 2i B． 2i+1 C． 2i-1 D． 2i-1 11．用n个关键字构造一棵二叉排序树，最低高度为（ ）。 A． n/2 A． 奇数 B． n C． nlog2n D． log2n +1 D． 充分大的数 12. 在散列函数H(k)=k MOD m 中，一般来讲，m应取（ ）。 B． 偶数 C． 素数 38 二、填空题 1．顺序查找法的平均查找长度为 ；二分查找法的平均查找长度为 。 2．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。 3．以二分查找方法从长度为50的有序表中查找一个元素时，其查找长度不超 过 。 4．在具有20个元素的有序表中进行二分查找，则比较一次查找成功的结点数 为 ，比较两次查找成功的结点数为 ，比较3次查找成功的结点数为 ，比较4次查找成功的结点数为 ，比较5次查找成功的结点数为 。总的平均查找长度为 。 5．在随机情况下，含有个结点的二叉排序树的平均查找长度为 。当二叉排序树退化为一棵单支树时，平均查找长度为 。 6．对一棵二叉排序树，若以 遍历该树，将得到一个以关键字递增顺序排列的有序序列。 7. 平衡二叉树上结点的平衡因子是指 。 8. Hash技术解决冲突的方法主要有 两种。 9. Hash技术关键是 两个方面。 10．散列函数的构造方法通常是 、 、 、 和 五种。 11．若待散列的序列为（18，25，63，50，42，32，9），散列函数为H(key)=key mod 9，与18发生冲突的元素有 个。 12．在散列存储中，装填因子α的值越大，则存储元素时发生冲突的可能性 就 。 三、基础知识题 1．简述顺序查找法和二分查找法的区别。 2．若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三 种情况下分别讨论两者在等概率时的平均查找长度是否相同？ （1）查找不成功，即表中没有关键字等于给定值K的记录； (2) 查找成功，且表中只有一个关键字等于给定值K的记录； (3) 查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出 所有记录。此时的平均查找长度考虑找到所有记录时所用的比较次数。 3．画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平 均查找长度。 39 4．已知一组元素为(37,70,29,46,25,78,62,12)，画出按元素排列输入生成的一棵二叉排序树，并求其在等概率情况下查找成功的平均查找长度（要求写出每插入一个元素时二叉排序树形状）。 5. 取适当Hash函数及处理冲突的方法，试在0--12散列地址空间中对关键字序列(2,41,53,46,30,13,01,67)构造Hash表，并求出等概率下查找成功的平均查找长度。 6．已知长度为12的表{Jan,Feb,Mar,Apr,May,June,July, Aug,Sep,Oct,Nov, Dec},（1）试按表中元素顺序建立一棵二叉排序树，并求其在等概率情况下查找成功的 平均查找长度； （2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度；(3) 按表中元素顺序建立一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。 7．试推导含12个结点的平衡二叉树的最大深度，并画出一棵这样的树。 8． 从空树开始，画出按下列次序向2-3树即3阶B-树中插入关键字的建树过程： 20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。 9．已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个 哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。 四、算法设计题 1．假设顺序表按关键字自大至小有序，改写顺序查找算法，将监视哨设在高下标端。 然后画出描述此查找过程的判定树，分别求出等概率情况下查找成功和不成功时的平均查找长度。 2．编写递归算法，从大到小输出给定二叉排序树中所有关键字不小于x的数据元素。 3．编写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表为存 储结构且树中结点的关键字均不同。 4．假设哈希表长为m，哈希函数为H(x)，用链地址法处理冲突。试编写输入一组关 键字并建造哈希表的算法。 40 第十章 内部排序 一、选择题 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． 快速排序 B 选择排序 C 插入排序 D． 归并排序 7．快速排序执行一遍之后，已经到位的元素个数是（ ）。 A． 1 B 3 C n/2 D． n/4 8．数据表中有1000个元素，如果仅需求出其中最大的10个元素，则采用（ ） 排序方法最节省时间。 A． 快速排序 B 希尔排序 C 堆排序 D． 直接选择排序 9．在下列排序方法中，所需辅助存储量最多的是（ ）。 A． 快速排序 B 归并排序 C 堆排序 D． 链式基数排序 10．下列排序方法中，一趟结束后未必能选出一个元素放在其最终位置上的算法是 （ ）。 A． 快速排序 B 冒泡排序 C 树型选择排序 D． 归并排序 11．若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择 的排序方法是（ ）。 A． 快速排序 B 归并排序 C 堆排序 D． 直接插入排序 12．快速排序方法在（ ）情况下最不利于发挥其长处。 A． 要排序的数据量太大 B 要排序的数据中含有多个相同值 C 要排序的数据量已基本有序 D． 要排序的数据个数为奇数 13．下列排序方法中不稳定的是（ ）。 A． 简单选择 B 冒泡排序 C 直接插入排序 D． 归并排序 41 14．下列序列中，（ ）才可能是执行第一趟快速排序后得到的序列。 A． {8,6,18}19{16,10,50} B {6,4,8}18{81,19,36,18} C {81,1,2}36{99,81,69} D． {2,3,4}89{78,98,68} 15．对于关键字序列{72,73,71,23,94,16,5,68,76,103}，用筛选法建堆，必须从 关键字为（ ）的结点开始。 A． 103 B 72 C 94 D． 23 16．以下序列中，（ ）不是堆。 A． {15,26,38,49,27,51,39,62} B {15,23,26,72,94,71,68,73} C {15,23,71,94,72,68,26,73} D． {15,23,26,68,94,72,71,73} 二、填空题 1．对于n个记录的序列进行冒泡排序，在最坏情况下的时间复杂度是 ；在 最好情况下的时间复杂度是 。 2．最简单的交换排序方法是 。 3．在插入和选择排序中，若初始数据基本正序或反序，则选用 ；若初始 数据无序，则选用 。 4．在堆和快速排序中，若初始数据基本有序，则选用 ；若初始数据基本 反序，则选用 。 5. 归并排序的时间复杂度为 。 6. 快速排序是一种 类型的排序；对含有n个元素的序列进行排序时，快速 排序的时间复杂度是 。 7．对具有n个记录的序列进行快速排序，在最坏情况下的时间复杂度是 ； 在最好情况下的时间复杂度是 。 8．对具有n个元素的序列采用堆排序法进行排序，排序趟数为 。 9．在时间复杂度为O(logn)的所有排序方法中， 排序方法是稳定的。 10．在时间复杂度为O(n2)的所有排序方法中， 排序方法是不稳定的。 三、基础知识题 1．以关键字序列（25,84,21,47,15,27,68,35,20）为例，手工执行各种排序算法，写出每一趟排序结束时的关键字状态。 2. 对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。 (1) n=7时在最好情况下需进行多少次比较？请说明理由。 (2) 对n=7给出一个最好情况的初始排列实例。 42 3．试按堆的构造方法，写出对应于序列(26,5,77,1,61,11,59,15,48,19)的初始堆（大根堆、小根堆均可，要求给出调整过程）。 4．判别以下序列是否为堆（小根堆或大根堆）。如果不是，则把它调整为堆（要求记录交换次数最少）。 (1) (100,86,48,73,35,39,42,58,66,22); (2) (12,70,33,65,24,56,46,90,86,33)。 5. 对初始关键字序列(E,D,X,K,H,L,M,C,P)，请画出筛选法建堆的过程。 6．请回答下列关于堆的一些问题： (1) 堆的存储表示是顺序的，还是链式的？ (2) 设有一个小根堆，则具有最大值的元素可能在什么地方？ (3) 对n个元素进行初始建堆的过程中，最多做多少此数据比较（不用大O表示 法）？ 7．分别利用折半插入排序法和2-路归并排序法对含4个记录的序列进行排序，画出描述该排序过程的判定树，并比较它们所需进行的关键字间的比较次数的最大值。 8．对一个由n个关键字不同的记录构成的序列，你能否用比2n-3少的次数选出这n个记录中关键字取最大值和关键字取最小值的记录？若能，请说明如何实现？在最坏情况下至少进行多少次比较？ 四、算法设计题 1．以带头结点的单链表为存储结构实现简单选择排序，排序的结果是单链表按关键字的值升序排列，试编写此算法。 2．编写算法，对n个关键字去整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求： (1) 采用顺序存储结构，至多使用一个记录的辅助存储空间； (2) 算法的时间复杂度为O(n)； (3) 讨论算法中记录的最大移动次数。 3．编写一个双向冒泡的排序算法，即相邻两遍向相反方向冒泡。 4．输入若干国家名称，请编写算法按字典顺序将这些国家进行排序（设所有的名称均用大写或小写表示）。 5．荷兰国旗问题：设有一个仅有红、白、蓝3种颜色的条块组成的条块序列。请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排列，即排成荷兰国旗图案。 43