数据结构网试题

数据结构试题第一章绪论、选择题:1在数据结构中，从逻辑上可以把数据结构分成（A、动态结构和静态结构

紧凑结构和非紧凑结构C、线性结构和非线性结构内部结构和外部结构2、算法分析的两个主要方面是（A、空间复杂性和时间复杂性正确性和简明性C、A、空间复杂性和时间复杂性正确性和简明性C、可读性和文档性数据复杂性和程序复杂性3、以下与数据的存储结构无关的术语是（循环队列 B、链表C3、4、以下数据结构中，哪一个是线性结构（A.广义表B、二叉树 C稀疏矩阵54、以下数据结构中，哪一个是线性结构（A.广义表B、二叉树 C稀疏矩阵5、在下面的程序段中，对x的赋值语句的频度为（FORi:=1TOnDOFORj:=1TOnDOx:=x+1;O(2n)B、O(n)2CO(2n)B、O(n)2C、O(n)D、O(log2n)6、以下哪个数据结构不是多型数据类型（C有向图C有向图字符串7、以下数据结构中，（

树 7、以下数据结构中，（

树 B字符串是非线性数据结构。以下属于逻辑结构的是（9、顺序表B.哈希表9、顺序表B.哈希表C有序表单链表F列程序段的时间复杂度为s=0;for(i=1;i<n;i++)for(j=1;j<n;j++)s+=ij;A、O(1)

B、O(n)

C、O(2n)

2D、O(n)AA、一种数据类型10、数据结构是（B、相互之间存在一种或多种特定关系的数据元素的集合C、一组性质相同的数据元素的集合D、数据的存储结构11、算法分析的目的是（B、评价算法的效率B、评价算法的效率D、鉴别算法的可读性）。C、研究算法中输入与输出的关系12、下面程序段的时间复杂度为（for（inti=0;i<m;i++）for（intj=0;j<n;j++）a[i][j]=ij；22A、O（m） B、O（n）C、O（mn） D、O（m+n）13、执行下面程序段时，执行 S语句的次数为（ ）。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A、n2 B、n2/2 C、n（n+1） D、n（n+1）/214、 算法的可读性是指（ ）。A、 算法所含语句数较少B、 算法较简单，计算机容易编译C、 算法较简单，人们很容易看出它的执行结果D、 算法结构清晰，容易被算法设计者及其同行看懂15、 算法分析的主要任务是分析（ ）。A、算法是否具有较好的可读性 B、算法中是否存在语法错误C、算法的功能是否符合设计要求 D、算法的执行时间和问题规模之间的关系二、填空题：1、在数据逻辑结构的二元组 S=（D，R）表示中，D是（），R是（）。TOC\o"1-5"\h\z2、 没有前驱的结点称为（ ），没有后继的结点称为（ ）。3、 数据的逻辑结构可以分为（ ）和（）两大类。4、 在树形结构中，每个结点最多只有一个（ ）。5、 为了实现随机访问，线性结构应该采用（ ）存储。6、 逻辑上相邻的结点在存储器中也相邻，这是（ ）存储结构的特点。7、数据的运算是在（ ）上定义的，运算的具体实现与（ ）结构有关。8、 用数量级形式表示的算法执行时间称为算法的（ ）。9、 算法的执行时间是（）的函数。10、在高级语言程序中，表示一组连续的存储单元，通常用（ ）。11、数据的物理结构包括（ ）的表示和（ ）的表示。12、 对于给定的n个元素，可以构造出的逻辑结构有（ ），（），（），（）四种。13、 一个算法具有5个特性：（）、（）、（）、有零个或多个输入、有一个或多个输出。14、一个算法的时间复杂度为 （3n2+2nlog2n+4n-7）/（5n），其数量级表示为（ ）。15、 在线性结构、树形结构和图形结构中，前驱和后继结点之间分另【J存在着（ ）、（）和（）的联系。三、判断题:TOC\o"1-5"\h\z1计算机程序处理的对象可分为数据和非数据两大类。 （）2、构成数据的最小单位是数据项。 （）3、数据元素和结点是同一个概念。 （）4、每个结点一般包含若干个字段。 （）5、同一个结点中的各个字段类型可以不相同。 （）6、数据是由一些类型相同的数据元素构成的。 （）7、数据的逻辑结构与各数据元素在计算机中如何存储有关。 （）8、如果数据元素值的大小改变了，则数据的逻辑结构也随之改变。 （）9、逻辑结构相同的数据，结点类型也一定相同。 （）10、逻辑结构相同的数据，可以有多种不同的存储方法。 （）11、逻辑结构不相同的数据，要采用不同的存储方法来存储。 （）12、线性结构的特征之一是：开始结点和终端结点都是唯一的。 （）13、在线性结构中，每个结点都有一个前驱、一个后继。 （）14、线性结构可以看成是树形结构的一个简单特例。 （）15、树型结构可以看成是图状结构的一个简单特例。 （）16、判断某个算法是否容易阅读是算法分析的任务之一。 （）17、算法容易阅读是好算法的主要标志之一。 （）18、算法必须用程序设计语言来书写。 （）19、为了实现随机访问，线性结构只能用顺序方法存储。 （）20、问题的规模越大，其算法也就越长。 （）21、数据元素是数据的最小单位。 （ ）22、记录是数据处理的最小单位。 （ ）23、数据的逻辑结构是指数据的各数据项之间的逻辑关系； （）24、算法的优劣与算法描述语言无关，但与所用计算机有关。 （ ）25、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 （ ）26、算法可以用不同的语言描述，如果用 C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。（ ）27、 程序一定是算法。（ ）28、数据的物理结构是指数据在计算机内的实际存储形式。 （）29、在顺序存储结构中，有时也存储数据结构中元素之间的关系。 （ ）30、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）四、应用题:1、评价一个好的算法，您是从哪几方面来考虑的?

2、若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构?3、在编制管理通讯录的程序时，什么样的数据结构合适 ？为什么？,、 3 2(3),、 3 2(3)T3(n)=3n+100n+n+1;账号、姓名、开户年月日、储蓄类型、存入累2(1)Ti(n)=1000; (2)T2(n)=n+1000n;分别写出相应的大O表示的运算时间。五、综合题:1、设计一数据结构，用来表示某一银行储户的基本信息:加数、利息、帐面总数。2、调用下列C函数f(n)或PASACAL函数f(n)，回答下列问题：试指出f(n)值的大小，并写出f(n)值的推导过程；假定n=5，试指出f(5)值的大小和执行f(5)时的输出结果。C函数：intf(int n){inti,j，k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--)for(k=1;k<j+1;k++)sum++;printf("sum=%d\n",sum);}return(sum);}

第二章线性表第二章线性表、选择题:1、一个顺序表所占存储空间的大小与（ ）无关。A、顺序表长度B、结点类型 C、结点中各字段的类型 DA、顺序表长度5个内存单元，则该25个内存单元，则该结点的地址，通常是指5个内存单元中（A、第3个单元的地址B、地址值最小的那个单元的地址C、地址的一个升序序列D、地址的一个降序序列。3、顺序表的长度与（ ）有关。A、线性表中有多少个结点 B、每个结点有多少个字段C、每个结点中各字段的类型 D、存储顺序表的数组类型TOC\o"1-5"\h\z4、与单向链表相比，双向链表的优点之一是（ ）。A、插入、删除操作更简单 B、可以进行随机访问C、可以省略表头指针或表尾指针 D、顺序访问相邻结点更灵活5、 动态链表所占用的内存单元地址一定是（ ）。A、无序的 B、连续的C、不连续的 D、部分连续的6、 与动态链表相比，静态链表的缺点之一是（ ）。A、插入、删除操作有时不方便 B、存储空间有时得不到充分利用C、要求各结点具有相同的类型 D、链表中各结点的值只能读取，不能更改7、如果对线性表的运算只有2种：删除第一个元素；在最后一个元素的后面插入新元素， 则最好使用（）。A、只有表头指针没有表尾指针的循环单向链表 B、只有表尾指针没有表头指针的循环单向链表C、非循环双向链表 D、循环双向链表8、设H是带表头结点循环单向链表的表头指针。当这种链表成为空链表时， （）。A、 表头结点指针字段的值为空B、 H的值为空C、 表头结点指针字段的值与H的值相等D、表头结点指针字段的值与 H的地址相等9•设H是带表头结点循环单向链表的表头指针， p是和H同类型的变量。当p指向链表的最后一个结点时，（）。A、 该结点指针字段的值为空B、 p为空C、 p的值与表头结点指针字段的值相等D、 该结点指针字段的值与H的值相等10•在长度为n的（）上，删除第一个元素，其算法的时间复杂度是 O（I）。A、只有表头指针的不带表头结点的循环单向链表B、 只有表尾指针的不带表头结点的循环单向链表C、 只有表尾指针的带表头结点的循环单向链表D、 只有表头指针的带表头结点的循环单向链表11•在长度为n的（）上，删除最后一个元素，其算法的时间复杂度是 O（n）。A、只有表头指针的循环双向链表 B、只有表头指针的非循环双向链表C、只有表尾指针的非循环双向链表 D、只有表尾指针的循环双向链表TOC\o"1-5"\h\z12、假设某个带头结点的单链表的头指针为 head，则判定该表为空表的条件是（ ）。A、head==NULL； B、head-〉next==NULL；C、head!=NULL； D、head->next==head；13、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针 s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。A、q->next=s->next；s->next=p； B、s->next=p；q->next=s->next；C、p->next=s->next；s->next=q； D、s->next=q；p->next=s->next；14、 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。A、插入B、删除 C、排序 D、定位15、 下列有关线性表的叙述中，正确的是（ ）。A、 一个线性表是n个数据元素的有限序列B、 线性表中任何一个元素有且仅有一个直接前驱C、 线性表中任何一个元素有且仅有一个直接后继D、 以上说法都不正确16、从一个长度为n的顺序表中删除第i个元素（1<i<n）时，需向前移动（）个元素。TOC\o"1-5"\h\zA、n-i B、n-i+1 C、n-i-1 D、i17、在一个单链表HL中，若要向表头插入一个由指针 p指向的结点，则执行（ ）。A、HL=p;p->next=HL; B、p->next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->next=p;18、下述哪一条是顺序存储结构的优点？（ ）A、存储密度大 B、插入运算方便 C、删除运算方便 D、可方便地用于各种逻辑结构的存储表示19、 关于线性表的叙述中，错误的是哪一个？（ ）A、 线性表采用顺序存储，必须占用一片连续的存储单元。B、 线性表采用顺序存储，便于进行插入和删除操作。C、 线性表采用链接存储，不必占用一片连续的存储单元。D、 线性表采用链接存储，便于插入和删除操作。20、 线性表是具有门个（）的有限序列（n>0）。A、表元素 B、字符 C、数据元素 D、数据项21•若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A、顺序表 B、双链表 C、带头结点的双循环链表 D、单循环链表

22、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（储方式最节省运算时间。A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表23、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。A、单链表 B、单循环链表 C、带尾指针的单循环链表 D、带头结点的双循环链表24、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）方式最节省运算时间。）存存储A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表）存存储B、数组下标 C、下一元素地址D、左、右孩子地址26B、数组下标 C、下一元素地址D、左、右孩子地址26、 链表不具有的特点是（A、插入、删除不需要移动元素C、不必事先估计存储空间 D、27、 下面的叙述不正确的是（A、 线性表在链式存储时，查找第B、 线性表在链式存储时，查找第C、 线性表在顺序存储时，查找第D、 线性表在顺序存储时，查找第）。B、可随机访问任一元素所需空间与线性长度成正比）。i个兀素的时间冋i的值成正比i个兀素的时间冋i的值无关i个兀素的时间冋i的值成反比i个兀素的时间冋i的值无关TOC\o"1-5"\h\z28、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为 （C.O(n)2D.O(n)(1<=i<=n+1)C.O(n)2D.O(n)A.0(0) B.0(1)29、 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。A、O（n）O（n） B、O（n）O（1） C、O（1）O（n） D、O（1）O（1）30、在单链表指针为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;二、填空题：1、顺序表是一种（ ）线性表。2、往长度为n的顺序表中插入一个元素，最多要移动（ ）个元素。3、在（）情况下，从顺序表中删除一个元素平均要移动近一半的元素。4、在程序中，实现动态链表要用到（ ）类型的变量。5、 用数组实现的链表，通常称为（ ）链表。6、若用带表头结点的单向链表来表示长度为 n的线性表，则需要为链表分配（ ）个结点的内存空间7、在循环单向链表中，可以用（ ）代替表头指针。8、在长度为n的顺序表上实现定位操作，其算法的时间复杂度是（ 数据结构7亠9、在长度为n的单向链表上实现定位操作，其算法的时间复杂度是（10、在顺序表（）后面插人新元素，不需要移动任何元素。11、在（）循环单向链表上，删除第一个结点，其算法的时间复杂度为 0（I）。12、 根据（）多少，线性链表可分为单向链表和双向链表两大类。13、在单向链表中，增加一个表头结点的目的是（ ）。14、 用数组实现单向链表时，通常将数组中那些空单元组织成一个（ ）。15、 往顺序表中插入新元素，除了要判断是否有空单元以外，还要判断（ ）是否正确。16、 在非循环的（）链表中，可以用表尾指针代替表头指针。17、在一个长度为100的顺序表中删除第10个元素时，需移动（ ）个元素。链表为空的条件分别为 （）和（）。18、在以HL为表头指针的带表头附加结点的单链表和循环单链表中,链表为空的条件分别为 （）和（）。19、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用（ ）存储结构。20、线性表L=（a1,a2,…3用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要TOC\o"1-5"\h\z移动元素的个数是（ ）。21、设单链表的结点结构为（data,next）,next为指针域，已知指针 px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：（）;（）。22、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动（ ）个元素。23•在单链表中设置头结点的作用是（ ）。24.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为（ ）,在给定值为x的结点后插入一个新结点的时间复杂度为（ ）。25•根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成（ ）和（）；而又根据指针的连接方式，链表又可分成（ ）和（）。26、在双向循环链表中，向p所指的结点之后插入指针 f所指的结点，其操作是（）、（）、（）、（）。27、链接存储的特点是利用（ ）来表示数据元素之间的逻辑关系。28、 顺序存储结构是通过（ ）表示元素之间的关系的；链式存储结构是通过（ ）表示元素之间的关系的。TOC\o"1-5"\h\z29、对于双向链表，在两个结点之间插入一个新结点需修改的指针共（ ）个，单链表为（ ）个。30、循环单链表的最大优点是： （）。31、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是： （）32、带头结点的双循环链表 L中只有一个元素结点的条件是： （）33、在单链表L中，指针p所指结点有后继结点的条件是： （）34、带头结点的双循环链表 L为空表的条件是：（）。35、 在单链表p结点之后插入s结点的操作是：（）。三、判断题:1、线性结构中的结点按前驱、后继关系可以排成一个线性序列。TOC\o"1-5"\h\z2、存储一个线性表所需的内存单元数与线性表的元素类型有关。 （）3、空线性表的一个特征是线性表中各结点尚未赋值。 （）4、顺序表是一种有序的线性表。 （）5、顺序表的长度等于元素个数与每个元素所占内存单元数之乘积。 （）6、分配给顺序表的内存单元地址必须是连续的。 （）7、用一维数组表示顺序表时，顺序表的第 i个元素必须放在下标为i的数组元素中。（）8、若表示顺序表的一维数组各元素尚未赋值， 则创建一个空顺序表的操作实际上不需要做任何事情。 （）9、 从长度为n的顺序表中删除一个元素，所需时间都是O（n）。（）10、往顺序表中插入一个元素，平均要移动大约一半的元素。 （）11、在动态单向链表中，每个结点总是占用一片连续的内存空间。 （）12、分配给单向链表的内存单元地址必须是连续的。 （）13、与顺序走相比；在链表上实现顺序访问，其算法的效率比较低。 （）14、单向链表中的结点只有后继，没有前驱。 （）15、在任何一种线性链表上都无法进行随机访问。 （）16、在循环单向链表中；每个结点都有一个后继。 （）17、在画单向链表示意图时，表示指针的箭头必须指向结点的第一个字段。 （）18、凡是空的单向链表都是不含任何结点的。 （）19、空的单向链表所表示的是长度为零的线性表。 （）20、允许进行插入、删除操作是动态链表的主要特征。 （）21、一个结点的指针字段为空，说明该字段中没有存放任何信息。 （）22、不带表头结点的空的单向链表不占用任何内存空间。 （）23、在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 （）24、如果单向链表带有表头结点，则线性表的插入操作永远不会改变表头指针的值。 （）25、在循环单向链表中，任何一个结点的指针字段值都不可能为空。 （）26、双向链表的表头指针要比单向链表的表头指针占用更多的内存空间。 （）27、在结点个数相同的情况下，双向链表所需的内存空间是单向链表的两倍。 （）28、双向链表的结点，数值字段、前驱指针字段和后继指针字段的排列顺序可以是任意的。 （）29、在双向链表中，每个结点一般至少有 3个字段。（）30、静态链表的表头指针是一个指针类型的变量。 （）31、链表中的头结点仅起到标识的作用。 （）32、顺序存储结构的主要缺点是不利于插入或删除操作。 （）33、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。 （ ）34、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。 （ ）35、对任何数据结构链式存储结构一定优于顺序存储结构。 （）36、顺序存储方式只能用于存储线性结构。 （ ）37、集合与线性表的区别在于是否按关键字排序。 （ ）38、所谓静态链表就是一直不发生变化的链表。 （ ）39、线性表的特点是每个元素都有一个前驱和一个后继。40、取线性表的第i个兀素的时间冋i的大小有关•（)41、循环链表不是线性表•（ ）42、线性表只能用顺序存储结构实现。()43、线性表就是顺序存储的表。 （)44、为了很方便的插入和删除数据，可以使用双向链表存放数据。 （ ）45、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）四、应用题：1线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构？为什么？2、说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。3、在单链表和双向链表中，能否从当前结点出发访问到任何一个结点4、设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作data,pre和next，试写出在指针p所指结点data,pre和next，试写出在指针p所指结点 数据结构 10 五、综合题:1、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。2、已知L1、L2分别为两循环单链表的头结点指针， m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。3、已知不带头结点的线性链表 list，链表中结点构造为（data、link），其中data为数据域，link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。voiddelete(Linklist&Lvoiddelete(Linklist&L)5、给定（已生成）一个带表头结点的单链表，设 head为头指针，结点的结构为（data,next），data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。 （要求；不允许使用数组作辅助空间 ） 数据结构 11 第三章栈和队列、选择题:1栈和队列的共同点在于（A、都对存储方法作了限制B、选择题:1栈和队列的共同点在于（A、都对存储方法作了限制B、都是只能进行插入、删除运算C、都对插入、删除的位置作了限制D、都对插入、删除两种操作的先后顺序作了限制2、栈的“先进后出”特性是指（最后插入栈中的元素总是最早被删除当同时进行插入、删除操作时，总是插人操作优先C、C、每当有删除操作时，总要先做一次插入操作每次从栈中删除的总是最早插入的元素3、栈是一种特殊的线性表，其特殊之处在于（A、栈具有普通线性表所没有的逻辑特性栈的存储方法比较特殊CA、栈具有普通线性表所没有的逻辑特性栈的存储方法比较特殊C、对线性表的使用方法作了限制栈比普通线性表更简单4、与顺序栈相比，链接栈（A、优点是存储管理较简单A、优点是存储管理较简单优点是插入、删除操作不需要移动其他元素C、C、缺点是不能顺序访问栈中元素缺点是插入、删除操作效率较低5、最适合用作链接栈的链表是（A、不带表头结点的非循环单向链表带表尾指针的循环单向链表CA、不带表头结点的非循环单向链表带表尾指针的循环单向链表C、带表头指针的循环单向链表D、循环双向链表6、最不适合用作链接栈的链表是（A、只有表头指针没有表尾指针的循环双向链表A、只有表头指针没有表尾指针的循环双向链表B、只有表尾指针没有表头指针的循环双向链表C、C、只有表尾指针没有表头指针的循环单向链表D、只有表头指针没有表尾指针的循环单向链表7、若7、若5个元素的进栈序列是 1,2,3,4,5，则不可能得到出栈序列（A、1，A、1，2，3，4，5B、3，4，2，5，1C、4，2，1，3，55,4,8、若8、若5个元素的出栈序列是1，2，3，4，5,则进栈序列可能是（A、3,1,2,5,4A、3,1,2,5,4B、2,3,1,5,4C、3，I，4，2，54，3,1,59、当4个元素的进栈序列给定以后，由这4个元素构成的可能的出栈序列共有）种。A、14B、16C、17D、2410、链接栈和链接队列都可以用只带表尾指针的循环单向链表来表示。此时的栈和队列（A、插入运算和删除运算都相同A、插入运算和删除运算都相同B、删除运算相同，插入运算不相同C、C、插入运算相同，删除运算不相同D、插人运算和删除运算都不相同11、设n11、设n个元素的进栈序列是 1,3，…，n,出栈序列是P1,P2，…，Pn。若P1=n，则Pi（I=i<n）的值（A、是iA、是iB、是n-iC、是n-i+1D、有多种可能12、设n个元素的进栈序列是1,2,3，…，n,出栈序列是pi,P2，…，Pn。若Pn=n，则Pi（I=i<n）的值（ ）。A、是i B、是n-iC、是n-i+1 D、有多种可能13.设n个元素的进栈序列是p1，P2，…，Pn，出栈序列是1,2，3,…，n,。若p3=|，则p1的值（ ））A、可能是2 B、一定是214、与顺序队列相比，链接队列的（A、可能是2 B、一定是214、与顺序队列相比，链接队列的（A、优点是可以实现无限长队列C、缺点是不能进行顺序访问）。B、优点是插人、删除操作较简单D、 缺点是不能根据队首指针和队尾指针计算队列的长度15、如果栈和队列都用只带表尾指针的循环单向链表来表示。则栈和队列的（A、删除算法相同，插入算法不相同 B、插人算法相同，删除算法不相同C、插入算法相同，删除算法也相同 D、插人算法不相同，删除算法也不相同16、循环顺序队列中是否可以插入下一个元素， （ ）。A、与队首指针和队尾指针的值有关B、只与队尾指针的值有关，与队首指针的值无关C、只与数组大小有关，与队首指针和队尾指针的值无关D、与曾经进行过多少次插入操作有关17、在顺序队列中，元素的排列顺序（ ）。A、由元素插入队列的先后顺序决定B、A、由元素插入队列的先后顺序决定B、与元素值的大小有关C、与队首指针和队尾指针的取值有关D、与数组大小有关18、假设以数组A[n]存放循环队列的元素,其头、尾指针分别为front和rear18、假设以数组A[n]存放循环队列的元素,A、（rear-front-1）%n B、（rear-front）%nC、（front-rear+1）%n D、（rear-front+n）%nTOC\o"1-5"\h\z19、在计算机内实现递归算法时所需的辅助数据结构是（ ）。A、栈 B、队列C、树 D、图20、假设以数组A[m]存放循环队列的元素。已知队列的长度为 length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为（ ）。A、（rear-length+m+1）%m B、（rear-length+m）%mC、（rear-length+m-1）%m D、（rear-length）%m21、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。D、n+1D、不分顺序A、n-2 BD、n+1D、不分顺序22、对于栈操作数据的原则是（ ）。A、先进先出 B、后进先出 C、后进后出23、某堆栈的输入序列为a,b,c,d23、某堆栈的输入序列为A、aA、a,c,b,dB、b,c,d,aC、c,d,b,aD、d,c,a,b24、设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 数据结构 13

A、线性表的顺序存储结构B、队列A、线性表的顺序存储结构B、队列C、线性表的链式存储结构D、栈TOC\o"1-5"\h\z25、 用链接方式存储的队列，在进行删除运算时（ ）。A、仅修改头指针 B、仅修改尾指针 C、头、尾指针都要修改 D、头、尾指针可能都要修改26、循环队列存储在数组 A[O..m]中，则入队时的操作为（ ）。A、rear=rear+1 B、rear=（rear+1）mod（m+1）C、rear=（rear+1）modm D、rear=（rear+1）mod（m-1）27、若用一个大小为6的数组来实现循环队列， 且当前rear和front的值分别为0和3,当从队列中删除一个元素，再加入两个元素后， rear和front的值分别为多少？（ ）。A、1和5 B、2和428、栈和队列的共同点是（ ）。B、都是先进后出DB、都是先进后出D、没有共同点C、只允许在端点处插入和删除元素29、 最大容量为n的循环队列，队尾指针是A、（rear+1）MODn=front29、 最大容量为n的循环队列，队尾指针是A、（rear+1）MODn=frontC、rear+1=front30、 设栈S和队列Q的初始状态为空，元素队列Q，若6个元素出队的序列是e2，e4,A、6 B、4 C、3二、填空题：1、 具有“先进先出”特性的线性表称为（2、栈是一种具有（ ）特性的线性表。3、 用算法语言描述顺序栈时，不但要用（B、rear=frontD、（rear-l）MODn=fronte1，e2，e3，e4,e5和e6依次通过栈S，—个元素出栈后即进e3,e6,e5,e1则栈S的容量至少应该是（ ）。D、2）。）表示其存储空间，而且还要用一个变量表示（ ）。4、即使知道队首指针和队尾指针的值，也无法计算出元素个数的队列，一定是（ 。队列。5、如果程序所要处理的数据元素是逐步产生的，而且要求处理数据元素的顺序和产生数据元素的顺序正好相反，则通常用（ 。暂存待处理的数据。6、顺序栈和链接钱的区别仅在于（ 。的不同。TOC\o"1-5"\h\z7、 在编写程序的时候，如果栈的最大长度难以估计，则最好使用（ ）。8、栈和队列的区别仅在于（ ）。9、若用Q[0]~Q[100]作为循环顺序队列的存储空间， Q[f]、Q[r]分别表示队首元素和下一个插人位置，则当f=70,r=20时，队列中共有（。个元素。10、顺序队列在实现的时候；通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生（ 。现象。11、若用只有队尾指针没有队首指针的循环单向链表来表示链接队列，则在进行删除操作的过程中，不仅需要判断（ 。，而且还要判断（ ）。12、若用Q[0]~Q[m]作为循环顺序队列的存储空间， Q[r]表示队尾元素，Q[f]表示队首元素的前一个位置,则可以用（ 。作队空的标志，与此相对应，可用（ 。作队满的标志。 数据结构 14 13、队列的队尾位置通常是随着（ ）操作而变化的。14、栈是（ ）的线性表，其运算遵循（ ）的原则。15、 （）是限定仅在表尾进行插入或删除操作的线性表。16、一个栈的输入序列是：1,2，3则不可能的栈输出序列是（ ）。17、 设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是（ ），而栈顶指针值是（ ）H。设栈为顺序栈，每个元素占4个字节。18、在作进栈运算时应先判别栈是否 （）；在作退栈运算时应先判别栈是否 （）；当栈中元素为n个，TOC\o"1-5"\h\z作进栈运算时发生上溢，则说明该栈的最大容量为（ ）。19、多个栈共存时，最好用（ ）作为存储结构。20、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为 1234，为了得到1342出栈顺序，相应的S和X的操作串为（ ）。21、顺序栈用data[1..n]存储数据，栈顶指针是 top,则值为x的元素入栈的操作是（ ）。22、表达式23+（（123-2）/4+345⑺+108/9的后缀表达式是（ ）。23、 循环队列的引入，目的是为了克服（ ）。24、 （ ）又称作先进先出表。25、 队列的特点是（ ）。26、已知链队列的头尾指针分别是 f和r，则将值x入队的操作序列是（ ）。27、区分循环队列的满与空，只有两种方法，它们是（ ）和（ ）。28、设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为 （），若用牺牲一个单元的办法来区分队满和队空（设队尾指针 sq.rear）,则队满的条件为（ ）。29、表达式求值是（ ）应用的一个典型例子。30、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是 front和rear，则当前队列的元素个数是（ ）。三、判断题：1、栈是一种存储方法比较特殊的线性表。 （）2、栈底元素是不能删除的元素。 （）3、顺序栈中元素值的大小是有序的。 （）4、进栈越早的元素，出栈越晚。 （）5、在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。 （）6、顺序栈的栈顶指针是一个指针类型的变量。 （）7、顺序栈是一种规定了元素进栈顺序的栈。 （）8、对于顺序栈来说，栈底元素的下标不能大于栈顶元素的下标。 （）9、对于顺序找来说，栈顶指针的类型必须和数组下标的类型相同。 （）10、栈顶元素和栈底元素有可能是同一个元素。（）11、对于非空的栈来说，栈顶元素和栈底元素都是唯一的。 （） 数据结构 15 TOC\o"1-5"\h\z12、对于顺序栈来说，栈顶指针的移动方向只与插人、删除操作有关。 （）13、若用s[1]~s[m]表示顺序栈的存储空间，则对栈的插人、删除操作最多只推进行 m次。（）14、对顺序栈进行插入、删除操作，不涉及元素的前、后移动问题。 （）15、栈是一种对插入、删除操作总次数作了限制的线性表。 （）16、栈是一种对插入、删除操作的次序作了限制的线性表。 （）17、插入、删除操作比较简单是链接栈的优点之一。 （）18、如果两个顺序栈有共同的元素，则可以共用同一个数组。 （）19、栈和队列都不适合用散列存储法存储。 （）20、栈和队列具有相同的逻辑特性。 （）21、空栈没有栈顶指针。（）22、空栈是指栈中兀素尚未赋值。 （）23、空栈是指栈项指针尚未赋值。 （）24、n个元素进队列的顺序和出队列的顺序总是一致的。 （）25、顺序队列中有多少元素，可以根据队首指针的值和队尾指针的值来计算。 （）26、循环队列中每个元素都有后继。 （）27、循环队列没有开始结点和终端结点。 （）28、 若用“队首指针的值和队尾指针的值相等”作为循环顺序队列为空的标志，则在设置一个空队列时，只需给队首指针和队尾指针赋同一个值，不管什么值都可以。 （）29、无论是顺序队列，还是链接队列，插人、删除运算的时间复杂度都是 0（1）。（）30、若用不带表头结点的非循环单向链表来表示链接队列， 则可以用“队首指针的值和队尾指针的位相等”作为队空的标志。（）四、应用题：1、什么是队列的假上溢现象，怎么解决？2、有5个元素，其入栈次序为：A,B,C,D,E,在各种可能的出栈次序中，以元素 C,D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？3、设输入序列为2,3,4,5,6，利用一个栈能得到序列2,5,3,4,6吗？栈可以用单链表实现吗? 数据结构 16 4、在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点？分别用多个顺序存储空间建立多个独立的堆栈;多个堆栈共享一个顺序存储空间；分别建立多个独立的链接堆栈。5、设一个双端队列，元素进入该队列的次序为 a,b，c,d。求既不能由输入受限的双端队列得到 ，又不能由输出受限的双端队列得到的输出序列。五、综合题:1、设从键盘输入一整数的序列： ai,a2,a3,…，a.,试编写算法实现：用栈结构存储输入的整数，当 a乂1时，将可进栈；当ai=-i时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。2、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。3、如果允许在循环队列的两端都可以进行插入和删除操作。要求:写出循环队列的类型定义；写出从队尾删除”和从队头插入”的算法。4、设计算法以求解从集合的所有组合的输出结果为：{1..n}中选取k(k<=n)个兀素的所有组合。例如，从集合 {1..4}中选取2个兀素1 2,1 3,1 4,23, 24,3 4。 数据结构 17

第四章串第四章串、选择题:TOC\o"1-5"\h\z1判断两个串大小的基本准则是（ ）。A、两个串长度的大小 B、两个串中首字符的大小C、两个串中大写字母的多少 D、对应的第一个不等字符的大小2、通常将链串的结点大小设置为大于 1是为了（ ）。A、提高串匹配效率 B、提高存储密度C、便于插入操作 D、便于删除操作3、设串sl="DataStructureswithJava",s2="it"，则子串定位函数 index（s1,s2）的值为（ ）。A、 15 B、16 C、17 D、184、下面关于串的的叙述中，哪一个是不正确的？（ ）。A、串是字符的有限序列 B、空串是由空格构成的串C、C、模式匹配是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储5、设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）。A、求子串 B、联接 C、匹配 D、求串长6、若串S=6、若串S='software其子串的数目是（C、36A、8 B、377、串的长度是指（ ）。A、串中所含不同字母的个数C、串中所含不同字符的个数）。D、9B、串中所含字符的个数D、串中所含非空格字符的个数、填空题:TOC\o"1-5"\h\z1、 设S='lamateacher',则其长度为（ ）。2、设s1='goods2='',s3='bye!',贝Us1,s2,s3连接后的结果是（ ）。3、 空格串是指（ 。，其长度等于（ 。。4、 组成串的数据元素只能是（ ）。5、 一个字符串中（。称为该串的子串。6、INDEX（'DTASTRUCTURE, 'STR'=（ 。。7、设正文串长度为n,模式串长度为m,则串匹配的KMP算法的时间复杂度为（ ）。8、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为（ 。，又称P为（）。9、串是一种特殊的线性表，其特殊性表现在（ ）;串的两种最基本的存储方式是（ ）、（ ）。10、 两个字符串相等的充分必要条件是（ ）。三、判断题:1、KMP算法的特点是在模式匹配时指示主串的指针不会变小（ ）。 数据结构 18

2、设模式串的长度为m,目标串的长度为n,当n~m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省（ ）。3、 串是一种数据对象和操作都特殊的线性表（ ）。四、 应用题：1简述空格串与空串的区别。2、如果两个串含有相等的字符，能否说它们相等？五、 综合题：1、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。第五章数组和广义表）。B）。B、节省存储空间D、便于增加或减少矩阵中的非零元素字链表表示，其优点在于（1、 用三元组顺序表表示稀疏矩阵，目的是为了（A、对非零元素进行随机访问C、便于插人或删除矩阵元素2、 与三元组顺序表相比，稀疏矩阵用A、 便于实现增加或减少矩阵中非零元素的操作B、 便于实现增加或减少矩阵元素的操作C、 可以节省存储空间）。B、无法根据行列号查找某个矩阵元素）。B、无法根据行列号查找某个矩阵元素D、使矩阵元素之间的逻辑关系更加复杂数据结构193、 对稀疏矩阵采用压缩存储，其缺点之一是（A、无法判断矩阵有多少行多少列C、无法根据行列号计算矩阵元素的存储地址

4、特殊矩阵用行优先顺序表表示， （）。A、简化了矩阵元素之间的逻辑关系 B、便于按行处理矩阵元素C、无法根据行列号计算矩阵元素的存储地址 D、可以节省存储空间5、 所谓特殊矩阵是指（ ）比较特殊。A、矩阵元素之间的关系 B、矩阵的处理方法C、矩阵元素的取值 D、矩阵的存储方法6、特殊矩阵不同于一般的稀疏矩阵，是因为（ ）。A、特殊矩阵中值相同的元素分布有规律 B、特殊矩阵中值相同的元素分布比较密集C、特殊矩阵中值相同的元素较少 D、特殊矩阵有特殊的用途7、所谓稀疏矩阵是指（ ）的矩阵。A、零元素较多且分布无规律 B、非零元素较少C、元素较少 D、不适合用二维数组表示8、10阶3对角矩阵用行优先顺序表表示，矩阵中第 7行第8列元素在顺序表中（ ）。A、是第20个元素 B、是第21个元素C、是第22个兀素 D、不存在A、减少矩阵的存储空间需求量。CA、减少矩阵的存储空间需求量。C、减少非零元素的存储空间需求量10、矩阵用行优先顺序表表示以后，A、减少了存储空间的需求量C、只能按行优先顺序访问矩阵元素B、减少访问非零元素所需时间D、降低非零元素间逻辑关系的复杂程度（）°B、增加了存储空间的需求量D、存取矩阵元素所需时间保持不变2个单元，按行优先顺序存储，起始地址为1000，第4行第5列的那个2个单元，按行优先顺序存储，起始地址为1000，第4行第5列的那个A、 A、 1046 B、1044C、 1048 D、102312、8阶方阵，每个元素占1个单元，按行优先顺序存储，起始地址为 100,存储地址为135的那个元素是矩阵中第5行第（ ）列元素。A、2B、3 C、4D、513、对于一个非空的广义表来说， （）°A、可能不含任何原子元素 B、至少含一个原子元素C、其长度不小于其中任何一个子表的长度 D、至少含一个非空的子表元素14、在表示丿义表L=（（））的链接存储结构中，有（ ）个结点。A、0 B、1C、2 D、315、在一个长度为n,含m个原子的广义表中，()°A、m和n相等B、m不大于nC、m不小于nD、m和n无关16、下列4个广义表中，长度为1，深度为4的广义表是（ ）°A、（（），（（a））） B、（（（（a）,b））,c） C、（（（a,b）,（c））） D、（（（a,（b）,c）））17、空的广义表，是指广义表（ ）° 数据结构 20

A、深度为0 B、尚未赋值 C、不含任何原子TOC\o"1-5"\h\z18、对于广义表((a,b),(()),(a,(b)))来说，其( )。A、长度为4 B、深度为4C、有3个元素19、 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储,1,每个元素占一个地址空间，则 a85的地址为( )。D、不含任何元素D、有2个元素an为第—「元素,其存储地址为A、 13 B、D、不含任何元素D、有2个元素an为第—「元素,其存储地址为20、假设以行序为主序存储二维数组 A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10」LOC[5，5]=( )。A、 808 B、818 C、1010 D、10201000的内存单元中，则21、数组A[0..5,0..6]1000的内存单元中，则A、1175 B、1180C、1205D、A、1175 B、1180C、1205D、1210i=0,1,…列下标j=1,2,…,10右A按行先)的起始地址相同。设每个字符占一个字22、二维数组i=0,1,…列下标j=1,2,…,10右A按行先)的起始地址相同。设每个字符占一个字A、A[8,5] B、A[3,10] C、A[5,8] D、A[0,9]23、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+1D、j(i-1)/2+124、有一个10090的稀疏矩阵，非 0元素有10个，设每个整型数占 2字节，则用三元组表示该矩阵时，TOC\o"1-5"\h\z所需的字节数是( )。A、60 B、66 C、18000 D、3325、 数组A[0..4,-1..-3,5..7]中含有元素的个数( )。A、55 B、45 C、36 D、1626、已知广义表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)))))27、已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。A、A、head(tail(LS))B、tail(head(LS))C、C、head(tail(head(tail(LS)))D、head(tail(tail(head(LS)))))。Head(Tail(Head(Tail(Tail(A)))))28、广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为)。Head(Tail(Head(Tail(Tail(A)))))TOC\o"1-5"\h\zA、(g) B、(d) C、c D、d29、 广义表运算式Tail(((a,b),(c,d)))的操作结果是( )。A、(c,d) B、c,d C、((c,d)) D、d30、 广义表(a,(b,c),d,e)的表头为()。A、a B、a,(b,c) C、(a,(b,c)) D、(a)31、设广义表L=((a,b,c))，贝UL的长度和深度分别为( )。 数据结构 21

A、1和1 B、1和332、下面说法不正确的是（B、广义表的表尾总是一个广义表DB、广义表的表尾总是一个广义表D、广义表可以是一个多层次的结构C、广义表难以用顺序存储结构、填空题:1、矩阵用一维数组表示时，有行优先顺序和（ ）两种实现方法。2、m行n列矩阵可以看成是长度为（ ）的线性表，表中的每个元素是长度为 m的线性表。3、10行20列矩阵若用行优先顺序表来表示，则矩阵中第 8行第7列元素是顺序表中的第（ ）个元素。4、10行20列矩阵若用列优先顺序表来表示，则矩阵中第 7行第8列元素是顺序表中的第（ ）个元素。5、10阶三对角矩阵若用行优先顺序表来表示， 则矩阵中第6行第7列元素是顺序表中的第（）个元素。6、用行优先顺序表表示10阶对称矩阵，若存储主对角线上的元素，则顺序表的长度为（ ）；若不存储TOC\o"1-5"\h\z主对角线上的元素，则顺序表的长度为（ ）。7、 用顺序方法存储三元组线性表，通常有两种实现方法，即（ ）。8、（）是一种常用的表示三元组线性表的链接存储结构。9、 广义表中的每个兀素可以是（ ），也可以是（ ）。10、 可以将广义表看成是（）的推广。11、 广义表通常用（ ）方法存储。12、广义表（（（a,b,（）,c）,d）,e,（（f）,g））的长度是（ ），深度是（ ）。三、判断题：矩阵每一行的元素个数都是相等的。 （）矩阵的行数和列数可以不相等。 （）用一维数组表示矩阵，可以简化对矩阵的存取操作。 （）矩阵一般用二维数组表示。（）对称矩阵的行数和列数一定是相同的。 （）具有特殊用途的矩阵称为特殊矩阵。 （）对角矩阵的特点是非零元素只出现在矩阵的两条对角钱上。 （）&在n阶三对角矩阵中，每一列都有 3个非零元素。（）9.在n阶三对角矩阵中，每一行都有 n个元素。（）10.若用列优先顺序表来表示 n阶三对角矩阵，则该顺序表的长度为 3n。（）稀疏矩阵的特点是矩阵中元素较少。 （）12•在表示矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小有关。 （）13•十字链表是三元组线性表的一种链接存储结构。 （）14•非零元素较少的特殊矩阵最好用三元组顺序表或十字链表表示。 （）15•在按行优先顺序存储的三元组线性表中，各元素的排列顺序只与每个元素的行下标有关，与每个元素的列下标无关。（） 数据结构 22 16•用三元组顺序表表示稀疏矩阵，其优点之一是可以随机访问矩阵中每个非零元素。TOC\o"1-5"\h\z17.用一维数组表示特殊矩阵，其目的是为了节省存储空间。 （）18•矩阵作为一种特殊的线性表，其长度通常不能为零。 （）19•矩阵用一维数组表示，可以节省存储空间。 （）矩阵作为一种特殊的线性表，其长度通常是固定不变的（ ）广义表的长度与广义表中含有多少个原子元素有关。 （）广义表的深度与广义表中含有多少个子表元素有关。 （）在广义表中，每个原子的类型都是相同的。 （）在广义表中，每个子表的结构都是相同的。 （）在广义表中，每个原子必须是单个字符。 （）“空的广义表”是指广义表中不包含原子元素。 （）广义表的长度不小于其中任何一个子表的长度。 （）若用链接方法存储广义表，则所需存储空间大小与广义表的长度成正比。 （）四、应用题：1、数组A[1..8,-2..6,0..6]以行为主序存储，设第一个元素的首地址是 78,每个元素的长度为4，试求元素A[4,2,3]的存储首地址。2、假设按低下标优先存储整型数组 A（-3:8,3:5,-4:0,0:7）时，第一个元素的字节存储地址是100,每个整数占4个字节，问A（0,4,-2,5）的存储地址是什么？3、三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是 100,试求元素A[5,0,7]的存贮首地址。五、综合题:1、编写一个过程，对一个nXi矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。2、给定有m个整数的递增有序数组 a[1..m]和有n个整数的递减有序数组 b[1..n]，试写出算法：将数组a和b归并为递增有序数组 c[l..m+n]。要求：算法的时间复杂度为 0（m+n）） 数据结构 23

第六章树和二叉树、选择题:对于一棵具有n个结点、度为4的树来说，（）。A、树的高度至多是 n-3 B、树的高度至多是 n-4C、第i层上至多有4（i-1）个结点 D、至少在某一层上正好有 4个结点2、对于一棵具有n个结点、度为4的树来说，树的高度至少是（ ）。A、「logA、「log42n」B、rlog4(3n-1)」C、「log4(3n+1)」D、「log4(2n+1)J3、 度为43、 度为4、高度为h的树，（A、至少有h+3个结点C、至多有4h个结点4、 用双亲数组表示树，其优点之A、找指定结点的双亲C、找指定结点的兄弟5、 用孩子链表表示树，其优点之A、判断两个指定结点是不是兄弟C、判断指定结点在第几层6、 如果用孩子链表来表示树，则（A、树的高度等于各链表长度的最大值C、树的度数等于各链表长度的最大值A、每个结点都有一个或两个孩子结点C、至少有一个度为2的结点10、 “二叉树为空”意味着二叉树（A、由一些没有赋值的空结点构成C、不存在11、 在高度为h的完全二叉树中，（A、度为0的结点都在第h层上）。B、至多有4h-l个结点D、至少有h+4个结点

•是（ ）比较方便。B、找指定结点的孩子D、判断某结点是不是树叶）比较方便。B、找指定结点的双亲D、计算指定结点的度数）°B、树叶的数目和链表的数目成反比

D、结点的数目等于各链表长度之和7、如果在表示树的二叉链表中有 6个空的左指针域，7个空的右指针域，5个结点左、右指针域都为空,TOC\o"1-5"\h\z则该树中树叶的个数（ ）°A、有7个B、有6个 C、有5个 D、不能确定8、如果用二叉链表来表示一棵具有 n（n>1）个结点的树，则在二叉链表中（ ）°A、至多有n-1个非空的右指针域B、至少有2个空的右指针域C、至少有2个非空的左指针域 D、至多有n-1个空的右指针域9、二叉树和度为2的树的相同之处包括（ ）°B、至少有一个根结点D、每个结点至多只有一个双亲结点）°B、根结点没有子树D、没有结点）°B、第i（1wi<n）层上的结点都是度为 2的结点 数据结构 24

C、第i（1Wi<n）层上有2i1个结点 D、不存在度为1的结点12、每个结点的度或者为 0或者为2的二叉树称为正则二叉树，对于 n个结点的正则二叉树来说，它的最大高度是（ ）。D、(n+1)/2A、「log2n」B、(n-1)/2C、「log2D、(n+1)/213、若树中结点的前序序列是 abcdef,后序序列是bdecfa,则（）。A、结点c有两个孩子 B、树有两个度为0的结点C、树的高度为5 D、不能唯一确定该树的结构14、若树中结点的前序序列是 abcdefg，后序序列前面3个结点是bde，则后序序列的后面4个结点有可能是（）。A、gcfaB、gacfC、afgcD、cfgaTOC\o"1-5"\h\z15、 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树（ ）。A、只有一个结点 B、每个结点都没有左孩子C、每个结点都没有右孩子 D、不存在16、 若某棵二叉树结点的后序序列和层次序序列正好相反，则该二叉树（ ）。A、每个结点都没有右孩子 B、不存在度为2的结点C、每个结点都没有左孩子 D、不存在17、 若某棵二叉树结点的前序序列和后序序列相同，则该二叉树（ ）。A、度为1 B、只有一个结点C、每个结点都没有左孩子 D、每个结点都没有右孩子18、在一棵高度小于4的二叉树中，若结点的前序序列是 abcdef，则结点的中序序列有可能是（ ）。A、dcebafBA、dcebafB、bcdafeC、cbdafeD、fcadbe19、若二叉树中结点的中序序列是19、若二叉树中结点的中序序列是abcdef，则结点的前序序列不可能是（A、dbacefBA、dbacefB、 acbedfC、efbacdD、bafdce20、在一棵高度小于5的二叉树中，若结点的中序序列是 abcdef；则结点的后序序列有可能是（ ）。A、bdfecaBA、bdfecaB、befdcaC、bdefcaD、fedcba21、在任何一棵二叉树中，如果结点中，（）。21、在任何一棵二叉树中，如果结点中，（）。a有左孩子b、右孩子c,则在结点的前序序列、中序序列、后序序列A、结点b一定在结点a的前面B、结点a一定在结点c的前面C、结点b一定在结点c的前面D、结点a一定在结点b的前面22、若二叉树结点的前序序列是 abcd，后序序列是dcba，则该二叉树（ ）。A、每个分支结点都没有左孩子 B、每个分支结点都只有一个孩子C、每个分支结点都没有右孩子 D、高度可能为323、如果二叉树中结点的前序序列是… a…b…中序序列是…b…a…则（ ）。A.结点a和结点b分别在某结点的左子树和右子树中B、结点b在结点a的右子树中C、结点b在结点a的左子树中 数据结构 25

D、结点a和结点b分别在某结点的两棵非空子树中中序序列和后序序列中，结点a、b的位置都是a在前、b中序序列和后序序列中，结点a、b的位置都是a在前、b在后（即形a、a、b可能是兄弟a可能是b的双亲C、a可能是b的孩子不存在这样的二叉树25C、a可能是b的孩子不存在这样的二叉树25、如果二叉树结点的前序序列和中序序列分别是定是cbfgehdaC、不存在abcdefgh和bcafegdh，则后序序列B、可能是cbgefhdaD、有多种可能2626、如果完全二叉树结点的后序序列是 abcdefgh，则结点的前序序列（A、不能唯一确定A、不能唯一确定B、是hgfedcbaC、C、是abdchegfD、是hdbacgef27二叉树若用顺序方法存储，则下列四种运算中的（27二叉树若用顺序方法存储，则下列四种运算中的（）最容易实现。A、前序遍历二叉树B、判断两个指定结点是不是在同一层上C、A、前序遍历二叉树B、判断两个指定结点是不是在同一层上C、层次遍历二叉树D、根据结点的位查找其存储位置28.对含有n个结点、高度为h的二叉树进行非递归后序遍历，所需栈容量（A、大于hB、等于h C、等于nD、小于n29、29、根据使用频率为五个字符设计的哈夫曼编码不可能是（110110,10,01,00B、000,001,010,011,lC、100,11,10,D、001C、100,11,10,D、001,000,01,11,1030、用整数1,2,3,4,5作为五个树叶的权值，可构造一棵带权路径长度值为（）的哈夫曼树。33B、15C、34D、54填空题:填空题:1、在树形结构中，如果某结点（如果某棵树（ ），则称该树为度为）,则称该结点为根结点；如果某结点（n1、在树形结构中，如果某结点（如果某棵树（ ），则称该树为度为）,则称该结点为根结点；如果某结点（n的树；如果某棵树（）,则称该树为高度为则称该结点为树叶;n的树。2、高度为h，度为k的树中至少有（）个结点，至多有（个结点。3、树的存储方法主要有（）和（ ）三种。4、在高度为h（h仝0）的二叉树中至多有（）个结点,至少有（）个结点。5、n个结点的二叉树最大高度是（）,最小高度是（62、高度为h，度为k的树中至少有（）个结点，至多有（个结点。3、树的存储方法主要有（）和（ ）三种。4、在高度为h（h仝0）的二叉树中至多有（）个结点,至少有（）个结点。5、n个结点的二叉树最大高度是（）,最小高度是（6、n个结点的二叉树中如果有 m个树叶，则一定有（）个度为1的结点，（）个度为2的结点。7、高度为h的满二叉树中有（ ）个结点。高度为h的完全二叉树中至少有（）个结点，至多有（个结点。9、3个结点可以构成（ ）种不同形状的树，可以构成（）种不同形状的二叉树。10、若用二叉链表来存储具有 m个树叶、n个分支结点的树。则二叉链表中有（）个左指针域为空的结点，有（ ）个右指针域为空的结点。

结点，有（ ）个右指针域为空的结点。11、在具有11、在具有n个结点的二叉链表中共有（）个空指针域。12、 二叉树的存储方法主要有（ ）和（ ）两种。13、在有n个结点的顺序存储的完全二叉树中， 若某结点在数组中的下标是 i，且ivn/2,则该结点的双亲、左孩子和右孩子在数组中的下标分别是（ ）、（）和（ ）。14、 二叉树中结点的前序序列是通过对二叉树进行（ ）遍历得到的。15、在任何一棵二叉树中， 若结点a有左孩子b、右孩子c,则在结点的前序序列、 中序序列、后序序列中,结点（ ）一定在结点（ ）前面。16•根据二叉树的中序序列和（ ）序列，可以唯一地确定其逻辑结构。17.如果二叉树A和B共有相同形式的二叉链表存储结构，则 A的（）序列和B的（）序列相同。18•在对二叉树进行非递归前序遍历过程中，需要用（ ）来暂存所访问结点的地址。在对二叉树进行层次遍历过程中，需要用（ ）来暂存所访问结点的地址。在（）线索二叉树中。有可能每个结点的右孩子指针域都不为空。在（ ）线索二叉树中，有可能每个结点的左孩子指针域都不为空。具有（ ）值的二叉树称为哈夫曼树。用整数1,2,3,4,5作为5个树叶的权值，可以构造出（ ）棵最优二叉树，每棵最优二叉树TOC\o"1-5"\h\z的带权路径长度值都是（ ）。24、具有256个结点的完全二叉树的深度为（ ）。25、 已知二叉树有50个叶子结点，则该二叉树的总结点数至少是（ ）。26、 8层完全二叉树至少有（ ）个结点，拥有100个结点的完全二叉树的最大层数为（ ）。27、有一份电文中共使用 6个字符：a,b,c,d,e,f,它们的出现频率依次为 2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为（），字符c的编码是（）。28、 如果结点A有3个兄弟，而且B是A的双亲，贝UB的度是（ ）。29、高度为8的完全二叉树至少有（）个叶子结点。30、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有（)个叶子结点。三、判断题：1、树形结构中的每个结点都有一个前驱。()TOC\o"1-5"\h\z2、树形结构中的每个结点至多只有一个前驱。 （）3、度为k的树中至少有一个度为k的结点。（）4、在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （）5、 度为k的树中，每个结点至多有k-1个兄弟。（）6、在用图示法表示树形结构时，每一条边必须画成一样长。 （）7、如果树中有m个分支结点，n个终端结点，则在表示这棵树的孩子链表中共有 m个链表。（）8、如果树用双亲数组表示，则判断某个结点是不是其他结点的双亲是很方便的。 （）9、如果树用双亲数组表示，则判断某个结点是不是其他结点的孩子是很方便的。 （）10、如果树用左孩子右兄弟链表表示，则找任何一个结点的孩子都是很方便的。 （） 数据结构 27

11、如果树用左孩子右兄弟链表表示，则找任何一个结点的兄弟都是很方便的。 （）12、如果树用二叉链表表示，则某个结点是不是树叶的条件是该结点左、 右两个指针域的值都为空。（）13、 二叉树是度为2的树。（）14、 度为2的树是二叉树。（）15、n（n>2）个结点的二叉树中至少有一个度为 2的结点。（）TOC\o"1-5"\h\z16、二叉树中结点之间的相互关系可用二元组来表示。 （）17、不存在这样的二叉树：它有 n个度为0的结点，n-l个度为1的结点，n-2个度为2的结点。（）18、在任何一棵完全二叉树中，终端结点或者和分支结点一样多，或者只比分支结点多一个。 （）19、完全二叉树中的每个结点或者没有孩子或者有 2个孩子。（）20、在所有高度相同的二叉树中，满二叉树总是含有最多的结点数。 （）21、满二叉树中不存在度为1的结点。（）22、若用顺序方法存储满二叉树，则具有前驱、后继关系的结点将占据相邻的存储单元。 （）23、n个结点的二叉链表中总是有n+1个空的指针域。（）24、n个结点的二叉链表中总是有「n/2」个含有空指针域的结点。 （）25、当树中结点数多于1个时，不可能根据结点的前序序列和后序序列唯一地确定该树的逻辑结构。 （）26、当二叉树中结点数多于1个时，不能根据结点的前序和后序序列唯一地确定该二叉树的逻辑结构。 （）27、只要知道完全二叉树中结点的前序序列，就可以唯一地确定它的逻辑结构。 （）28、哈夫曼树中不存在度为1的结点。（）29、在哈夫曼树中，权值相同的树叶结点都在同一层上。 （）30、在哈夫曼树中，权值较大的树叶结点一般离根结点较远。 （）四、应用题：1、已知完全二叉树的第七层有 10个叶子结点，则整个二叉树的结点数最多是多少？2、将下列由三棵树组成的森林转换为二叉树。PP