数据结构期末考试试卷1.pdf

《数据结构期末考试试卷1.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试试卷1.pdf（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题1一、单项选择题1.数 据 结 构 是 指()oA.数 据 元 素 的 组 织 形 式B.数据类型C.数据存储结构 D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称 之 为()oA.存储结构 B.逻辑结构C.链式存储结构 D.顺序存储结构3.树 形 结 构 是 数 据 元 素 之 间 存 在 一 种()。A.一对一关系 B.多对多关系C.多对一关系 D.一对多关系4.设 语 句x+的时间是单位时间，则以下语句的时间复杂度为()ofor(i=1;i=n;i+)for(j=i;j=n;j+)x+;A.0(1)B.0()C.O(n)D.0()5.算 法 分 析 的 目

2、的 是(1),算 法 分 析 的 两 个 主 要 方 面 是(2)。(1)A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进 D.分析算法的易懂性和文档性(2)A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性6.计 算 机 算 法 指 的 是（1）,它具备输入，输 出 和（2）等五个特性。（1）A.计算方法 B.排序方法C.解决问题的有限运算序列 D.调度方法（2）A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，

3、在存储空间使用的灵活性上，链 式 存 储 比 顺 序 存 储 要（）oA.低 B.高 C.相同 D.不好说8.数 据 结 构 作 为一门独立的课程出现是在（）年。A.1946 B.1953 C.1964 D.19689.数据结构只是研究数据的逻辑结构和物理结构，这 种 观 点（）。A.正确 B.错误C.前半句对，后半句错 D.前半句错，后半句对10.计 算 机 内 部 数 据 处 理 的 基 本 单 位 是（）。A.数据 B.数 据 元 素C.数 据 项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是?_ 和2.数据的逻辑结构有四种基本形态，分别是、和3.线性结构反映结点间的逻辑

4、关系是 的，非线性结构反映结点间的逻辑关系是 的。4.一个算法的效率可分为 效率和_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _效率。5.在树型结构中，树根结点没有 结点，其余每个结点的有且只有 个前趋驱结点；叶子结点没有 结点；其余每个结点的后续结点可以6.在图型结构中，每个结点的前趋结点数和后续结点数可以7.线性结构中元素之间存在 关系；树型结构中元素之间存在 关系；图型结构中元素之间存在 关系O8.下面程序段的时间复杂度是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ofor(i=0;in;i+)for(j=0;jn;j

5、+)AiU=O;9.下面程序段的时间复杂度是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _oi=s=O;while(sn)i+；s+=i;10.下面程序段的时间复杂度是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=B 皿 ;sum=s;11.下面程序段的时间复杂度是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ i=1；while(i=n)i=i*3;12.衡量算法正确性的标准通常是13.算法时间复杂度的分析通常有两种方法，即 和

6、的方法，通常我们对算法求时间复杂度时，采用后一种方法。三、求下列程序段的时间复杂度。1.x=0;for(i=1;in;i+)for(j=i+1;j=n;j+)x+;2.x=0;for(i=1;in;i+)for(j=1;j=n-i;j+)x+;3.int i,j,k;for(i=0;in;i+)for(j=0;j=n;j+)cij=O;for(k=0;k=O)&Ai!=k)return(i);5.fact(n)if(n=1)return(1);elsereturn(n*fact(n-1);习题1参考答案一、单项选择题1.A 2.C 3.D 4.B 5.C、A 6.C、B 7.B 8.D 9.B

7、 10.B二、填空题1.线性结构，非线性结构2.集合，线性，树，图3.一 对 一,一对多或多对多4.时 间，空间5.前趋，一，后继，多6.有多个7.一对一，一对多，多对多8.0()9.0()10.0()11.O(log n)12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。13.事后统计，事前估计三、算法设计题1.0()2.0()3.0(n)4.0(n)5.0(n)习题2一、单项选择题1.线性表是 OA.一个有限序列，可以为空 B.一个有限序列，不可以为空C.一个无限序列，可以为空 D.一个无限序列，不可以为空2.在一个长度为n的顺序表中删除第i个元素(0=inext=s;s-pr

8、ior=p;p-next-prior=s;s-next=p-next;B.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;C.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;6.设单链表中指针p指向结点m,若要删除m之后的结点(若存在)，则需修改指针的操作为 OA.p-next=p-next-next;B.p=p-next;C.p=p-next-next;D.p-next=p;7.在一个长度为n的顺序

9、表中向第i个元素(0 inext=p-next;p-next=sB.q-next=s;s-next=pC.p-next=s-next;s-next=pD.p-next=s;s-next=q9.以下关于线性表的说法不正确的是 oA.线性表中的数据元素可以是数字、字符、记录等不同类型。B.线性表中包含的数据元素个数不是任意的。C.线性表中的每个结点都有且只有一个直接前趋和直接后继。D.存在这样的线性表：表中各结点都没有直接前趋和直接后继。10.线性表的顺序存储结构是一种 的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取11.在顺序表中，只要知道,就可在相同时间内求出任一结点的存储

10、地址。A.基地址B.结点大小C.向量大小 D.基地址和结点大小12.在等概率情况下，顺序表的插入操作要移动 结点。A.全部 B.一半C.三分之一 D.四分之一13.在 运算 中，使用顺序表比链表好。A.插入 B.删除C.根据序号查找 D.根据元素值查找14.在 一 个 具 有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_ _ _ _ _ _ _ _OA.0(1)B.0(n)C.0(n2)D.O(log2n)15.设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列。A.A,B,C,D,E B.B,C,D,E,AC.E,A,B,C,D D.E,D,C,B,A

11、16.在 一 个 具 有n个单元的顺序栈中，假 定 以 地 址 低 端(即0单元)作 为 栈 底，以top作为栈顶指针，当做出栈处理时，top变化为_OA.top 不变 B.top=0 C.top-D.top+1 7.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行A.hs-next=s;B.s-next=hs;hs=s;C.s-next=hs-next;hs-next=s;D.s-next=hs;hs=hs-next;18.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为 OA.rear%n=front B.(front+l)%n

12、=rearC.rear%n-1=front D.(rear+l)%n=front19.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为 OA.rear%n=front B.front+l=rearC.rear=front D.(rear+l)%n=front2 0.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为 OA.front=front-next B.rear=rear-nextC.rear=front-next D.front=rear-next二、填空题1.线性表是一种典型的 结构。2.在一

13、个长度为n的顺序表的第i个元素之前插入一个元素，需要后移 个元素。3.顺序表中逻辑上相邻的元素的物理位置 o4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需 一个位置，移动过程是从 向 依次移动每一个元素。5.在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过决定的。6.在双向链表中，每个结点含有两个指针域，一个指向 结点，另一个指向 结点。7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用 存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 存储结构为宜。8.顺序表中逻辑上相邻的元素，物理位置 相邻

14、，单链表中逻辑上相邻的元素，物理位置 相邻。9.线性表、栈和队列都是 结构，可以在线性表的 位置插入和删除元素；对于栈只能在 位置插入和删除元素；对于队列只能在 位置插入元素和在 位置删除元素。10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为 和_ _ _ _ _ _ _ _;而根据指针的联接方式，链表又可分为和 O11.在单链表中设置头结点的作用是 O12.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结 点 的 时 间 复 杂 度 为,在给定值为x的结点后插入一个新结点的时间复杂度为 o1 3.对于一个栈作进栈运算时，应 先 判 别 栈 是 否 为,作退栈运算时

15、，应 先 判 别 栈 是 否 为,当栈中元素为m时，作进栈运算时发生上溢，则 说 明 栈 的 可 用 最 大 容 量 为。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 分别设在这片内存空间的两端，这样只有当_ _ _ _ _ _ _ _ 时才产生上溢。14.设有一空栈,现有输入序列1,2,3,4,5,经过push,push,pop,push,pop,push,push 后，输出序列是_ _ _ _ _ _ _ _ _ _。15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为 O三、简答题1.描述以下三个概念的区

16、别：头指针，头结点，表头结点。2.线性表的两种存储结构各有哪些优缺点？3.对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4.对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。5.在单循环链表中设置尾指针比设置头指针好吗？为什么？6.假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。7.什么是队列的上溢现象？一般有几种解决方法，试简述之。8.下述算法的功

17、能是什么？LinkList*Demo(LinkList*L)L是无头结点的单链表LinkList*q,*p;if(L&L-next)q=L;L=L-next;p=L;while(p-next)p=p-next;p-next=q;q-next=NULL;)return(L);)四、算法设计题1.设计在无头结点的单链表中删除第i个结点的算法。2.在单链表上实现线性表的求表长ListLength(L)运算。3.设计将带表头的链表逆置算法。4.假设有一个带表头结点 的链表，表 头 指 针 为head,每个结点含三个 域：data,next和priorQ其 中data为 整 型 数 域,next和pri

18、or均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域(此 域 初 值 为NULL)把所有结点按照其值从小到大的顺序链接起来。5.已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素(若表中存在这样的元素)的算法。6.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。7.假定用一个单循环链表来表示队列(也称为循环队列)，该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：(1)向循环链队列插入一个元素值为x的结点；(2)从

19、循环链队列中删除一个结点。8.设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。习题2参考答案一、单项选择题1.A 2.A 3.D 4.C 5.D 6.A 7.B 8.B 9.C10.A 11.D 12.B 13.C 14.B 15.C 16.C 17.B18.D 19.C20.A二、填空题1.线性2.n-i+13.相邻4.前移，前，后5.物理存储位置，链域的指针值6.前 趋，后继7.顺 序，链接8.一 定，不一定9.线 性，任 何，栈 顶，队尾，队头10.单链表，双链表，非循环链表，循环链表11.使空表和非空表统一；算法处理一致12.0(1),O(n)13.栈 满，栈 空

20、，m,栈 底，两个栈的栈顶在栈空间的某一位置相遇14.2、315.0(1)三、简答题1.头 指 针 是 指 向 链 表 中 第 一 个 结 点(即 表 头 结 点)的 指 针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2.线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指

21、针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3.应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4.应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。5.设尾指针比设头指针好。尾指

22、针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其 尾 指 针 为rear,则开始结点和终端结点 的 位置分别是rear-next-next和rear,查找时间都是0(1)。若用头指针来表示该链表，则查找终端结点的时间为0(n)。6.共有14种可能的出栈序列，即为：ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA7.在队列的顺序存储结构中，设队头指针为front,队 尾 指 针 为rear,队 列 的 容 量(即 存 储 的 空 间 大

23、小)为maxnum。当有元素要加入队列(即 入 队)时，若rear=maxnum,则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“炭溢出”现 象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。一般地，要解决队列的上溢现象可有以下几种方法：(1)可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。(2)要避免出现 假溢出 现象可用以下方法解决：第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。第二种：每当删去一个队头元

24、素，则可依次移动队列中的元素总是 使front指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出 的原则。8.该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指 针。四、算法设计题1.算法思想为：(1)应判断删除位置的合法性，当in-1时，不允许进行删除操 作；(2)当i=0时,删 除 第 一 个 结 点：(3)当0in时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：d

25、elete(LinkList*q,int i)在无头结点的单链表中删除第i 个结点LinkList*p,*s;int j;if(inext;free(s);)else j=0;s=q;while(0next;j+；)if(s=NULL)printf(Cantt delete);elsep-next=s-next;free(s);2.由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：int ListLength(LinkList*L)求带头结点的单链表的表长int len=O;ListList*p;P=L；while(p-next!=NULL)p=p-n

26、ext;len+;)return(len);)3.设单循环链表的头指针为head,类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q-next=s;操作即可，算法描述如下：void invert(LinkList*head)逆置head指针所指向的单循环链表linklist*p,*q,*s;q=head;p=head-next;while(p!=head)当表不为空时，逐个结点逆置 s=q;q=p;p=p-next;q-next=s;)p-next=q;)4.定 义 类 型Lin

27、kList如 下：typedef struct node int data;struct node*next,*prior;LinkList;此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：insert(LinkList*head)LinkList*p,*s,*q;p=head-next;p指向待插入的结点，初始时指向第一个结点while(p!=NULL)s=head;s指 向q结点的前趋结点q=head-prior;q指 向 由prior域构成的链表中待比较的结点while(q!=NULL)&(p-dataq-dat

28、a)查找插入结点 p的合适的插入位置 s=q;q=q-prior;)s-prior=p;p-prior=q;结点p插 入 到 结 点s和 结 点q之间p=p-next;)5.算法描述如下：delete(LinkList*head,int max,int min)linklist*p,*q;if(headkNULL)q=head;p=head-next;while(p!=NULL)&(p-datanext;while(p!=NULL)&(p-datanext;q-next=p;)6.算法描述如下：delete(LinkList*head,int max,int min)LinkList*p,*q

29、;q=head;p=head-next;while(p!=NULL)if(p-datadata=max)q=p;p=p-next;)else q-next=p-next;free(p);p=q-next;7.本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：(1)插 入(即 入 队)算 法：insert(LinkList*rear,elemtype x)设循环链队列的队尾指针为rear,x为待插入的元素LinkList*p;p=(LinkList*)malloc(sizeof(LinkList);if(rear=NULL)如为空队，建立循环链队列

30、的第一个结点 rear=p;rear-next=p;链接成循环链表)else 否则在队尾插入p结点 p-next=rear-next;rear-next=p;rear=p;)(2)删 除(即 出 队)算 法：delete(LinkList*rear)设循环链队列的队尾指针为rearif(rear=NULL)空队printf(underflown);if(rear-next=rear)队中只有一个结点rear=NULL;elserear-next=rear-next-next;/rear-next 指向的结点为循环链队列的队头结点)8.只要从终端结点开始往前找到第一个比x大(或相等)的结点数据,

31、在这个位置插入就可以了。算法描述如下：int lnsertDecreaseList(SqList*L,elemtype x)int i;if(*L).len=maxlen)printf(tcoverflow);return(O);)for(i=(*L).len;i0&(*L).elem i-1 0 B.inC.1in D.1in+19.字符串采用结点大小为1的链表作为其存储结构，是 指()oA.链表的长度为1B.链表中只存放1个字符C.链表的每个链结点的数据域中不仅只存放了 一个字符D.链表的每个链结点的数据域中只存放了一个字符二、填空题1.计算机软件系统中，有两种处理字符串长度的方法：一种是

32、,第二种是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _O2.两个字符串相等的充要条件是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _和3.设字符串 S1=ABCDEF，S2=PQRS”，则运算 S=CONCAT(SUB(S1,2,LEN(S2),SUB(S1,LEN(S2),2)后的串值为 o4.串是指 o5.空串是指,空格串是指三、算法设计题1.设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，ms,t（s-m

33、）,并将删除后的结果复制在该数组的第s单元以后的单元中，试设计此删除算法。2.设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。习题3参考答案一、单项选择题1.B2.D3.C4.D5.B6.C7.D8.C9.D二、填空题1.固定长度，设置长度指针2.两个串的长度相等，对应位置的字符相等3.“BCDEDE”4.含n个字符的有限序列(后0)5.不含任何字符的串，仅含空格字符的字符串三、算法设计题1.算法描述为：int delete(r,s,t,m)从串的第m个字符以后删除长度为t的子串char r;int s,t,m;int ij;fo

34、r(i=1;i=m;i+)rs+i=ri;for(j=m+t-i；jdata!=pt-data)pt=pt-next;if(pt=NULL)ps=NULL;else ps=ps-next;s=ps;)return s;/find习题4一、单项选择题1.设二维数组A0n-1按行优先顺序存储在内存中，第一个元素的地址为p,每个元素占k 个字节，则元素a ij的地址为()。A.p+i*n+j-1*k B.p+(i-1)*n+j-1*kC.p+(j-1)*n+i-1*k D.p+0*n+i-1*k2.已知二维数组A10 x10中，元素a20的地址为5 6 0,每个元素占4个字节，则元素a10的 地 址

35、 为()。A.520 B.522 C.524 D.5183.若数组A0按列优先顺序存储，则 a ij地 址 为()。A.LOC(aOO)+m+i B.LOC(aOO)+j*n+iC.LOC(aOO)+(j-1)*n+i-1 D.LOC(aOO)+(j-1)*m+i-14.若下三角矩阵A n x n,按列顺序压缩存储在数组Sa0.(n+1)n/2中，则非零元素a ij的 地 址 为()(设每个元素占d 个字节)A.G-1)*n-+i-1*dB.0-1)*n-+i*dC.(j-1)*n-+i+1*dD.(j-1)*n-+i-2*d5.设有广义表D=(a,b,D),其 长 度 为(),深 度 为()

36、oA.无穷大 B.3 C.2 D.56.广义表A=(a),则 表 尾 为()oA.a B.()C.空表 D.(a)7.广义表 A=(x,(a,B),(x,(a,B),y),则运算 head(head(tail(A)的结果 为()oA.xB.(a,B)C.(x,(a,B)D.A8.下列广义表用图来表示时，分支结点最多的是()。A.L=(x,(a,B),(x,(a,B),y)B.A=(s,(a,B)C.B=(x,(a,B),y)D.D=(a,B),(c,(a,B),D)9.通常对数组进行的两种基本操作是()。A.建立与删除 B.索引和修改C.查找和修改 D.查找与索引10.假定在数组A中，每个元素

37、的长度为3个字节，行下标i从1到8,列下标j从1到1 0,从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为()oA.80 B.100 C.240 D.27011.数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1到1 0,从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A网 5的起始地址为()。A.SA+141 B.SA+144 C.SA+222 D.SA+22512.稀疏矩阵一般的压缩存储方法有两种，即()。A.二维数组和三维数组 B.三元组和散列C.三元组和十字链表 D.散列和十字链表13.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和

38、列下标互换，就完成了对该矩阵的转置运算，这 种 观 点()。A.正确 B.不正确14.一个广义表的表头总是一个()。A.广义表 B.元素 C.空表 D.元素或广义表15.一个广义表的表尾总是一个()。A.广义表 B.元素 C.空表 D.元素或广义表16.数组就是矩阵，矩阵就是数组，这 种 说 法()。A.正确 B.错误C.前句对，后句错 D.后句对二、填空题1.一维数组的逻辑结构是,存储结构是;对于二维或多维数组，分为 和两种不同的存储方式。2.对 于 一 个 二 维 数 组 若 按 行 序 为 主 序 存 储，则任一元素相对于A00的地址为 o3.一个广义表为(a,(a,b),d,e,(i,

39、j),k),则 该 广 义 表 的 长 度 为,深度为 O4.一个稀疏矩阵为，则对应的三元组线性表为5.一个nxn的对称矩阵，如果以行为主序或以列为主序存入内存,则其容量为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _6.已知广义表A=(a,b,c),(d,e,f),则运算h e a d(t a i l(t a i l(A)=。7.设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主序存储，a为第一个元素，其存储地址为0,每个元素占有1个存储地址空间，则a的地址为 o8.已知广义表Ls=（a,（b,c,d）,e）,运 用head和tail函数取出Ls中的原 子b的运算是。9.

40、三维数组 Rc 1.d 1 ,c2.d2,c3.d3共含有 个元素。（其中：c1d1,c2d2,c3lc=NULL B.p-ltag=1C.p-ltag=1 且 p-lc=NULL D.以上都不对9.设n,m为一棵二叉树上的两个结点，在中序遍 历 序 列 中n在m前 的 条 件 是（）。A.n在m右方 B.n在m左方C.n是m的祖先 D.n是m的子孙10.如 果F是由有序树丁转换而来的二叉树，那 么T中结点的前序就 是F中 结 点 的（）。A.中序 B.前序 C.后序 D.层次序11.欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方 案 是 二 叉 树 采 用（）存储结构。A.三 叉

41、 链 表B.广义表 C.二叉链表 D.顺序12.下 面 叙 述 正 确 的 是（）。A.二叉树是特殊的树B.二叉树等价于度为2的树C.完全二叉树必为满二叉树D.二叉树的左右子树有次序之分13.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对 次 序（）。A.不发生改变 B.发生改变C.不能确定 D.以上都不对14.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。A.1 B.2 C.3 D.415.根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二 叉 树（）。A.是完全二叉树 B.不是完全二叉树C.是满二叉树 D.不是满二叉树二、判断题1.二叉树中每个结点的度

42、不能超过2,所以二叉树是一种特殊的树。（）2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（）3.线索二叉树是一种逻辑结构。（）4.哈夫曼树的总结点个数（多于1时）不能为偶数。（）5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（）6.树的后序遍历与其对应的二叉树的后序遍历序列相同。（）7.根据任意一种遍历序列即可唯一确定对应的二叉树。（）8.满二叉树也是完全二叉树。（）9.哈夫曼树一定是完全二叉树。（）10.树的子树是无序的。（）三、填空题1.假定一棵树的广义表表示为A（B（E）,C（F（H,I,J）,G）,D),则 该 树 的 度 为,树 的 深 度 为,终端结点的个数为,单

43、分支结点的个数为,双 分 支 结 点 的 个 数 为,三 分 支 结 点 的 个 数 为,C结 点 的 双 亲 结 点 为,其孩子结点为 和 结点。2.设F是一个森林，B是 由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有 个。3.对于一个有n个结点的二叉树，当它为一棵 二叉树时具有最小高度，即为,当它为一棵单支树具有 高度，即为 O4.由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为 O5.在一棵二叉排序树上按 遍历得到的结点序列是一个有序序列。6.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 个，其中 个用于链

44、接孩子结点，个空闲着。7.在一棵二叉树中，度为0的结点个数为nO,度为2的结点个数为n2,则 n0=o8.一棵深度为k的 满 二 叉 树 的 结 点 总 数 为,一棵深度为k的 完 全 二 叉 树 的 结 点 总 数 的 最 小 值 为,最大值为 O9.由三个结点构成的二叉树，共有 种不同的形态。10.设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 O11.一棵含有n个结点的k叉树，形态达到最大深度，形态达到最小深度。12.对于一棵具有n个结点的二叉树，若一个结点的编号为i(lSKn),则 它 的 左 孩 子 结 点 的 编 号 为,右孩子结点的编号为,双亲结

45、点的编号为 O13.对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为 个，其中 个用于链接孩子结点，个空闲着。14.哈夫曼树是指_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 的二叉树。15.空树是指,最小的树是指16.二叉树的链式存储结构有 和_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 两种。17.三叉链表比二叉链表多一个指向 的指针域。18.线索是指19.线索链表

46、中的rtag域值为 时，表示该结点无右孩子，此时域为指向该结点后继线索的指针。20.本 节 中 我 们 学 习 的 树 的 存 储 结 构 有、和_ _ _ _ _ _ _ _ _ _ _ _ _。四、应用题1.已知一棵树边的集合为,请画出这棵树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶子结点？(3)哪个是结点g的双亲？(4)哪些是结点g的祖先？(5)哪些是结点g的孩子？(6)哪些是结点e的孩子？(7)哪些是结点e的兄弟？哪些是结点f的兄弟？(8)结点b和n的层次号分别是什么？(9)树的深度是多少？(1 0)以结点c为根的子树深度是多少？2.一棵度为2的树与一棵二叉树有何区别。3.试

47、分别画出具有3个结点的树和二叉树的所有不同形态？4.已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL,写出该二叉树的先序、中序和后序遍历序列。5.一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题：(1)各层的结点数目是多少？(2)编号为n的结点的父结点如果存在，编号是多少？(3)编号为n的结点的第i个孩子结点如果存在，编号是多少？(4)编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？6.找出所有满足下列条件的二叉树：(1)它们在先序遍历和中序遍历时，得到的

48、遍历序列相同；(2)它们在后序遍历和中序遍历时，得到的遍历序列相同；(3)它们在先序遍历和后序遍历时，得到的遍历序列相同；7.假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请写出该二叉树的后序遍历序列。8.假设一棵二叉树的后序序列为DCEGBFHKJIA,中序序列为DCBGEAHFIJK,请写出该二叉树的后序遍历序列。9.给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。10.给定一组权值(5,9,11,2,7,1 6),试设计相应的哈夫曼树。五、算法设计题1.一 棵 具 有n个结点的完全二叉树以一维数组作为存储结构，试设计一

49、个对该完全二叉树进行先序遍历的算法。2.给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。3.写出在中序线索二叉树中结点P的右子树中插入一个结点s的算法。4.给定一棵二叉树，用二叉链表表示，其根指针为t,试写出求该二叉 树 中 结 点n的双亲结点的算法。若 没 有 结 点n或者该结点没有双亲结 点，分别输出相应的信息；若 结 点n有双亲，输出其双亲的值。习题5参考答案一、单项选择题1.C 2.B 3.C 4.D 5.B 6.D 7.C 8.B 9.B 10.B 11.A 12.D 13.A 14.B 15.A二、判断

50、题1.x 2.7 3.x 4.4 5.x 6.4 7.4 8 J 9.x 10.x三、填空题1.3,4,6,1,1,2,A,F,G2.n+13.完全，,最大，n4.555.中序6.2n,n-1,n+17.n2+18.2k-1,2k-1,2k-19.510.2h-111.单支树，完全二叉树12.2i,2i+1,i/2（或？i/2?）13.2n,n-1,n+11 4.带权路径长度最小15.结点数为0,只有一个根结点的树1 6.二叉链表，三叉链表1 7.双亲结点18.指向结点前驱和后继信息的指针19.1,RChild2 0.孩子表示法，双亲表示法，长子兄弟表示法四、应用题1.解 答：根据给定的边确定