《数据结构》（戴敏）期末复习题库

1、第一章 绪论一、选择题1、数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。(易) A、数据元素 B、计算方法 C、逻辑存储D、数据映象 A、结构 B、关系 C、运算 D、算法2、数据结构被形式地定义为(K,R),其中K是 的有限集，R是K上的 有限集。(易) A、算法 B、数据元素C、数据操作D、逻辑结构 A、操作 B、映象C、存储D、关系3、在数据结构中，从逻辑上可以把数据结构分成_。(易)A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构 D、内部结构和外部结构4、算法分析的目的是 ，算法分析的两个主要方面是 。(中) A、找出数据

2、结构的合理性B、研究算法中的输入和输出的关系 C、分析算法的效率以求改进D、分析算法的易懂性和文档性 A、空间复杂度和时间复杂度B、正确性和简单性C、可读性和文档性D、数据复杂性和程序复杂性5、计算机算法指的是 ，它必须具备输入、输出和 等5个特性。(易) A、计算方法B、排序方法 C、解决问题的有限运算序列D、调度方法 A、可执行性、可移植性和可扩充性 B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性答案：1、A，B 2、D，B 3、C 4、C，A 5、C，B二、名词解释：(易)1、数据 2、数据元素 3、数据对象 4、数据结构 5、数据类型 6、算法答案：1、

3、数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中被计算机程序处理的符号的总称。2、数据元素数据的基本单位，在计算机程序中通常做为一个整体进行考虑和处理。3、数据对象：性质相同的数据元素的集合。4、数据结构：相互具有一种或多种关系的数据元素的集合。5、数据类型：是具有相同性质的计算机数据的集合及在这个数据上的一组运算，是和数据结构密切相关的概念。6、算法：对特定问题求解步骤的一种描述，是有限指令的集合。三、填空题1、下面程序段的时间复杂度是_。(易)for (i=0;i<n;i+)for (j=0;j<m;j+)aij=0;2、下面程序段的时间复杂度是_。(中)i=

4、s=0while(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)i=i*3;5、数据元素可以由若干_组成，_是数据的基本单位，_是数据的最小单位。(易)6、数据结构分为两部分，即_结构和_结构。(易)7、数据的存储方式分为_存储和_存储。(易)8、顺序存储是一种_的存储方式，是用一组_的存储空间存储数据，而链式存储是用一组_的存储空间存储数据

5、。(易)答案：1、O(m*n) 2、O() 3、O() 4、O(lon) 5、数据项 数据元素 数据项 6、逻辑 物理 7、顺序 链式 8、随机存取 连续 任意四、简答题：1、什么是算法，其基本性质是什么？(易)2、算法的要求是什么？(中)3、结构共分几类？其各自的性质是什么？(易)答案：1、算法是对特定问题求解步骤的一种描述，是有限指令的集合。其基本性质如下：1)有穷性：算法对任意合法的输入均能在有限时间、有限步骤后完成。2)确定性：算法的每一步骤的含义都是唯一、确定的，对于相同的输入均能得到相同的输出。3)可行性：算法的每一个步骤和指令都应在已实现的算法的基础上完成。4)输入：任一个算法必

6、须有0个或多个输入。5)输出：任一个算法必须有1个或多个输出。2、算法的要求是：1)正确性：算法能正确描述待求解问题的需求，没有逻辑错误，据此算法书写的程序，对于任何合法的输入，都有得到正确的、说明需求的结果。2)可读性：算法应简洁、明晰，易于阅读和理解，便于算法的移植和交流，有利于增加算法的生命力。3)健壮性：当输入的数据非法时，算法要能作出适当的处理，不会产生难以预料的结果。4)高效率性：一般来说，对同一问题的多种算法，首先选择执行时间相对较短、存储空间相对较少的算法，然后考虑易于实现的算法。3、结构共分为四类，分别为：1)集合：所有元素除共在同一集合外，没有其他关系。2)线性结构：元素间

7、是一对一的关系。3)树型结构：元素间是一对多的关系。4)图型结构：元素间是多对多的关系。五、算法设计题：1、试写一算法，求随机输入的三个整数的最大值。(中)2、随机从键盘上输入三个整数求其平均值输出。(易)答案：1、int max(int x,int y,int z) int t;t=x>y?x:y;t=t>z?t:z;return t;2、main() int a,b,c; float sum=0,ave; scanf(“%d%d%d”,&a,&b,&c); sum=a+b+c; ave=sum/3;printf(“%.2fn”,ave);第二章 线性结构

8、一、 判断题1、线性表的逻辑顺序与存储顺序总是一致的。(易)2、顺序存储的线性表可以按序号随机存取。(易)3、顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。(易)4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。(易)5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(易)6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。(易)7、线性表的链式存储结构优于顺序存储结构。(易)8、在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。(易)9、线性表的链式存

9、储结构是用一组任意的存储单元来存储线性表中数据元素的。(易)10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(易)11、线性表中，每一个元素均存在前驱。(易)12、线性表中，每一个元素均存在后继。(易)13、线性表中，存在唯一一个被称为第一元素的元素。(易)14、线性表中，存在唯一一个被称为最后一个元素的元素。(易)15、线性结构是一种一对一的结构。(易)答案：1-5 ×× 6-10 ×× 11-15 ××二、 选择题：1、线性表是( ) 。(易)A、一个有限序列，可以为空； B、一个有限

10、序列，不能为空； C、一个无限序列，可以为空； D、一个无序序列，不能为空。 2、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。(易) A、n/2 B、(n+1)/2 C、(n 1)/2 D、n3、线性表采用链式存储时，其地址( ) 。(易)A、必须是连续的； B、部分地址必须是连续的； C、一定是不连续的； D、连续与否均可以。4、用链表表示线性表的优点是 （ ）。(易)A、便于随机存取B、花费的存储空间较顺序存储少C、便于插入和删除D、数据元素的物理顺序与逻辑顺序相同5、 某链表中最常用的操作是在最后一个元素之后插入一

11、个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。(易)A、单链表B、双链表C、单循环链表D、带头结点的双循环链表6、 循环链表的主要优点是( ) 。(易)A、不再需要头指针了B、已知某个结点的位置后，能够容易找到他的直接前趋C、在进行插入、删除运算时，能更好的保证链表不断开D、从表中的任意结点出发都能扫描到整个链表7、 下面关于线性表的叙述错误的是( )。(易) A、线性表采用顺序存储，必须占用一片地址连续的单元；B、线性表采用顺序存储，不便于进行插入和删除操作；C、线性表采用链式存储，不必占用一片地址连续的单元；D、线性表采用链式存储，便于进行插入和删除操作；8、 单链表中，增

12、加一个头结点的目的是为了（）。(易)A、使单链表至少有一个结点 B、标识表结点中首结点的位置C、方便运算的实现 D、说明单链表是线性表的链式存储9、 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。(易)A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表10、 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间。(易)A、单链表 B、顺序表 C、双链表 D、单循环链表11、 一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素

13、的地址是_。(易)A、110 B、108 C、100 D、12012、 不带头结点的单链表head为空的判定条件是_。(易)A、head = = NULL; B、head->next = = NULL;C、head->next = = head; D、head! = NULL;13、 带头结点的单链表head为空的判定条件是_。(易)A、head = = NULL; B、head->next = = NULL;C、head->next = = head; D、head! = NULL;14、 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。(

14、易)A、s->next=p; p->next=s; B、s->next=p->next; p->next=s;C、s->next=p->next; p=s; D、p->next=s; s->next=p; 15、 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。(易)A、s->next=p->next; p->next=s; B、p->next=s->next; s->next=p;C、q->next=s; s->next=p; D、p->nex

15、t=s; s->next=q;16、 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。(易)A、n; B、n/2; C、(n-1)/2; D、(n+1)/2;17、 给定有n个结点的向量，建立一个有序单链表的时间复杂度_。(易)A、 O(1); B、 O(n); C、 O(n); D、 O(nlogn);18、顺序存储结构是一种_ _的存储结构。(易)A、随机存取 B、索引存取 C、顺序存取 D、散列存取19、在以下的叙述中，正确的是_ _。(易)A、线性表的顺序存储结构优于链表存储结构B、线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C

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

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

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

19、_。(易)12、在单链表中，申请一个结点空间的命令是_，释放一个空间的命令是_。(易)13、在双向链表中，每个结点有两个指针域，一个为_，指向_ _；另一个为_，指向_ _ _。(易)14、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_ _和p->next=_的操作。(易)15、在双向链表中，若结点p是结点q的前驱，现要删除结点q，需要完成的操作是_；_；(易)16、在双向链表中，若在结点p之前插入一个新结点s，需要完成的操作有_；_；_；_；(易)答案：1、n-i+1 2、n-i 3、(1) p->next (2) s->data (3)

20、t4、名字 长度 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.prior=s;四、算法设计题：1、在一顺序表L的第i个元素前，插入一新元素x。(中)2、现有一顺序表L，其值非递

21、增有序排列，现插入一新元素x，要求插入后，L仍保持非递增有序排列，试写其算法。(中)3、在带头结点的单链表H中的p结点前插入一个新元素x。(中)4、已知单链表LA、LA中的元素按值非递减有序排列，现将LA、LB归并成一个新表LC，并要求LC中的元素亦非递减有序排列。(中)五、编程题：1、百钱百鸡问题。(中)2、猎人与狗的问题：一队猎人一队狗，两队并成一队走，数头一共三百六，数脚一共八百九，问多少猎人多少狗。(中)四、五题答案：四、算法题：1、int Insert_Sq(SqList L,int i,elemtp x) if(i<1 | i>L.len+1) return 0;if(

22、L.len=maxsize) return -1;for(j=L.len;j>=i;j-) L.elemj+1=L.elemj;L.elemi=x;L.len+;return 1; 2、int Insert(SqList L,elemtp x)if(L.len=maxsize) return -1; for(p=&L.elemL.len-1;*p<=x;p-) *(p+1)=*p; *(p+1)=x; return 1; 3、int Insert_L(LNode *H,LNode *p,elemtp x) s=(LNode *) malloc(sizeof(LNode);s

23、.data=x;q=H;while(q.next!=p) q=q.next;s.next=p;q.next=s;return 1;4、void Merge_L(LNode La,LNode Lb,LNode Lc) pa=La.next;pb=Lb.next;Lc=pc=La;while(pa && pb)if(pa.data<=pb.data) pc.next=pa;pc=pa;pa=pa.next; else pc.next=pb;pc=pb;pb=pb.next; pc.next=pa?pa:pb;free(Lb);五、编程题：1、main()int x,y,z;

24、for(x=1;x<20;x+) for(y=1;y<33;y+) z=100-x-y; if(100=5*x+3*y+z/3.0) printf(“%d,%d,%dn”,x,y,z); 2、main() int x,y;for(x=1;x<360;x+) y=360-x; if(2*x+4*y=890) printf(“%d,%d n”,x,y); 第三章栈和队列一、判断题：1、栈和队列都是限制存取点的线性结构(易)2、栈和队列是两种重要的线性结构。(易)3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易)4、在对不带头结点的链队列

25、作出队操作时，不会改变头指针的值。(易)答案：1-4 ××二、选择题：1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是_。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为_。 A、 i B、 n=i C、 n-i+1 D、 不确定3、栈结构通常采用的两种存储结构是_。A、顺序存储结构和链式存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存储结构和非线性存储结构4、 判定一个顺序栈ST（最多元素为m0）为空的条件是_。A、t

26、op !=0 B、top= =0 C、top !=m0 D、top= =m0-15、 判定一个顺序栈ST（最多元素为m0）为栈满的条件是_。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-16、 队列操作的原则是( ) A、 先进先出 B、 后进先出 C、 只能进行插入 D、 只能进行删除7、 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行_ _。(不带空的头结点) (易)A、HSnext=s;B、snext= HSnext; HSnext=s;C、snext= HS; HS=s;D、snext= HS; HS= HSnext;8、从一个栈顶指针为HS

27、的链栈中删除一个结点时，用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 C、1，4，3，2 D、3，2，4，110、判定一个循环队列QU（最多元素为m）为空的条件是_。(中)A、rear - front= =m B、rear-front-1= =mC、front= = rear D、front= = re

28、ar+111、 判定一个循环队列QU（最多元素为m, m= =Maxsize-1）为满队列的条件是_。(易)A、(rear- front)+ Maxsize)% Maxsize = =mB、rear-front-1= =m C、front= =rear D、front= = rear+112、 循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_。(中)A、 (rear-front+m)%m B、 rear-front+1C、 rear-front-1 D、 rear-front13、 栈和队列的共同点是_。A、 都是先进后出 B、 都是

29、先进先出C、 只允许在端点处插入和删除元素 D、 没有共同点14、栈操作的原则是( ) (易)A、 先进先出 B、 后进先出 C、 只能进行插入 D、 只能进行删除15、在顺序栈中，判断栈s为空的条件是( ) (中)A、t.base = NULL B、st.top = st.stacksizeC、st.top-st.base>= st.stacksize D、st.top = st.base16、在顺序栈中，判断栈s满的条件是( ) (易)A、 st.base = NULL B、 st.top = st.stacksizeC、 st.top-st.base>= st.stacksi

30、ze D、 st.top = st.base答案：1-5 CCABD 6-10 ACBCC 11-15 AACBD 16 C三、填空题：1、栈和队列都是_结构，对于栈只能在_插入和删除元素；对于队列只能在_插入元素和_删除元素。(易)2、向一个长度为n的顺序表的第i个元素（1in+1）之前插入一个元素时，需向后移动_个元素。(易)3、向一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动_个元素。(易)4、向栈中压入元素的操作是_。(易)5、对栈进行退栈时的操作是_。(易)6、在一个循环队列中，队首指针指向队首元素的_。(易)7、从循环队列中删除一个元素时，其操作是_。(易)8、在具有

31、n个单元的循环队列中，队满时共有_个元素。(易)9、一个栈的输入序列是12345，则栈的输出序列43512是_。(易)10、一个栈的输入序列是12345，则栈的输出序列12345是_。(易)11、队列的基本性质是_；栈的基本性质是_。(易)12、在一个链栈中，若栈顶指针等于NULL则为_，在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为_或该队列_。(易)13、向一个栈顶指针为top的链栈中插入一个新结点*P，应执行 和 操作。(易)14、栈的顺序存储结构即顺序栈，是利用 来依次存放自栈底至栈顶的数据元素；当栈为非空时，栈顶指针top始终指向 。15、从数据结构的角度看，栈和队列是

32、两类线性表。(易)答案：1. 线性、栈顶、队尾、队首 2. n-i+1 3. n-i4.先移动栈顶指针，后存入元素 5. 先取出元素，后移动栈顶指针6.前一个位置 7. 先移动队首元素，后取出元素8. n-1 9. 不可能的 10. 可能的 11、FIFO LIFO12、栈空 空队 只有一个元素 13、p->next=top top=p14、一组地址连续的存储单元 栈顶元素的下一位置 15、受限的线性表四、算法题：1、输入一个任意的非负十进制整数,输出与其等值的八进值数。(中)答案：void conversion() InitStack(s);scanf(“%d”,&N);whi

33、le(N)push(s,N%d); N=n/8;while(!empty(s) pop(s,e); printf(“%dn”,e);五、编程题：1、从键盘上输入一个大写字母，要求改用小写字母输出。（中）2、输入一个圆的半径，求其周长及面积并输出。答案：1、main()char c; scanf(“%c”,&c); c=c+32; printf(“%cn”,c); 2、#definet PI 3.14 main() float r,s,c;scanf(“%f”,&r);s=PI*r*r;c=2*PI*r;printf(“s=%.2f,c=%.2fn”,s,c);第四章 串和广义表

34、一、判断题：1、空串是由空白字符组成的串(易)2、串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。(易)3、串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。(易)4、如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。(易)5、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。(易)6、广义表的表头一定是列表。(易)7、广义表的表尾一定是列表。(易)8、空串的长度为零。(易)9、广义表的元素即可以是原

35、子，也可以是子表。(易)10、广义表中的子表与串中的子串的含义一样。(易)11、广义表A=()，为空表，其长度为0。(易)12、由于广义表的元素可以是列表，所以可以将广义表转化为一个树型结构答案：1-5 ××× 6-10 ×× 11-12 二、选择题：1、以下叙述中正确的是 。(易)A、串是一种特殊的线性表B、串的长度必须大于零C、串中无素只能是字母D、空串就是空白串2、空串与空格串是相同的，这种说法_。(易)A、 正确 B、 不正确3、串是一中特殊的线性表，其特殊性体现在_。(易)A、 可以顺序存储 B、 数据元素是一个字符C、 可以链接存储

36、 D、 数据元素可以是多个字符4、设有两个串p和q，求q在p中首次出现的位置的运算称作_。(易)A、连接 B、模式匹配 C、求子串 D、求串长5、设串s1=ABCDEFG，s2=PQRST，函数con (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、BCDEFEF6、设串的长度为n，则它的子串个数为 。(易)A、nB、n(n+1)C、n(n+

37、1)/2 D、n(n+1)/2+17、下列那些为空串（ ）(易)A、S=“ ” B、S=“” C、S=“” D、S=“”8、S1=“ABCD”，S2=“CD”则S2在S3中的位置是（ ）(易)A、1 B、2 C、3 D、49、串是一种特殊的线性表，其特殊性体现在( )。(易)A、可以顺序存储 B、 数据元素是一个字符C、可以链接存储 D、 数据元素可以是多个字符10、串是( )。(易)A、少于一个字母的序列 B、 任意个字母的序列C、不少于一个字符的序列 D、 有限个字符的序列11、 串的长度是( )。(易)A、串中不同字母的个数 B、 串中不同字符的个数 C、串中所含的字符的个数 D、 串中

38、所含字符的个数，且大于012、若某串的长度小于一个常数，则采用( )存储方式最为节省空间。(易)A、链式 B、 堆结构 C、 顺序表答案：1-5 ABBBD 6-10 CBCBD 11-12 CC三、填空题：1、串的两种最基本的存储方式是_。(易)2、两个串相等的充分必要条件是_。(易)3、空串是_，其长度等于_。(易)4、空格串是_，其长度等于_。(易)5、设s=IAMATEACHER,其长度是_。(易)6、串s=abcdef,s1=cde，s1在s中的位置为_。(易)7、广义表A=(a,(b,c d)；其表头为_，表尾为_。(中)8、广义表A=(a,A)；其表头为_，表尾为_。(易)9、串

39、是每个结点仅由一个字符组成的（ ）。(易)答案：1顺序存储方式和链接存储方式2两个串的长度相等且对应位置的字符相同3零个字符的串、零4由一个或多个空格字符组成的串、其包含的空格个数5146、3 7、a (b,c,d) 8、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）五、编程题

40、：1编写一个程序，要求有键盘输入三个数，计算以这三个数为边长的三角形的面积(假定输入的边长是有效的)。（中）2. 有一函数，其函数关系如下，试编程求对应于每一自变量的函数值。（中） 1 (x<0) y = 0 (x=0) -1 (x>0)答案：1、#include “math.h” main() float a,b,c,p,s;scanf(“%f%f%f”,&a,&b,&c);p=(a+b+c)/2;s=sqrt(p*(p-a)*(p-b)*(p-c);printf(“%.2fn”,s);2、main() int x,y;scanf(“%d”,&x)

41、;if(x<0) y=1;if(x=0) y=0;if(x>0) y=-1;prinft(“%dn”,y);第五章数组一、名词解释：1、压缩存储(易)2、特殊矩阵(易)3、稀疏矩阵(易)答案：1、压缩存储：为多个值相同的元分配一个存储空间，对零元不分配存储空间。2、特殊矩阵：值相同的元素或者是零元素分布的有规律则称为特殊矩阵。3、稀疏矩阵：在一个m*n的矩阵中，有t个非0元，其稀疏因子为t/(m*n)，如果稀疏因子小于0.05就称为稀疏矩阵。二、选择题：1、设数组a76的基地址为1024,每个元素占2个存储单元,若以行序为主序顺序存储,则元素a24的存储地址是_。(中)A、1058

42、 B、1056 C、1098 D、答案A,B,C都不对2、 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A47的起始地址为_。(中)A、 SA+141 B、 SA+180 C、 SA+222 D、 SA+2253、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是_。(中)A、 80 B、 100 C、240 D、 2704、 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址S

43、A开始连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为_。(中)A、 SA+141 B、 SA+144 C、 SA+222 D、 SA+225答案：1-4 BBCC三、填空题：1、 已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00)，则Aij的地址是_。(中)2、 二维数组A1020采用列序为主方式存储，每个元素占一个存储单元并且A00的存储地址是200，则A612的地址是_。(中)3、 二维数组A1020510采用行序为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000，则A189的地址是_。(中)4、

44、现有一个n阶的对称矩阵ann，现将其压缩存储在一个一维数组sm中，则m=_，若以行序为主序进行存储，则元素aij(i>=j)在s中的下标k=_。(中)5、在一个m*n的矩阵中，若a00是第一个元素，则aij是第_个元素。(中)答案：1、LOC (A00)+(n*i+j)*k 2.、326 3、12084、n(n+1)/2 i(i-1)/2+j-1 5、i*n+j四、编程题：1、编写一程序，求1+2+3+4+100的值（中）2、菱形的输出(前5行) （中）答案：1、main()int i,sum=0; for(i=1;i<=100;i+) sum+=i; printf(“sum=%d

45、n”,sum); 2、main()int i,j; for(i=1;i<=3;i+) for(j=1;j<=3-i;j+) printf(“ “); for(j=1;j<=2*i-1;j+) printf(“*”); printf(“n”); for(i=1;i<=2;i+) for(j=1;j<=i;j+) printf(“ “); for(j=1;j<=5-2*i;j+) printf(“*”); printf(“n”); 第六章 树一、选择题：1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_。(易)A、 正确 B、 错误2、假

46、定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 (易)A、15 B、16 C、17 D、473、按照二叉树的定义，具有3个结点的不同形状的二叉树有_种。(易)A、3 B、 4 C、 5 D、 64、按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_种。(易)A、5 B、 6 C、 30 D、 325、深度为5的二叉树至多有_个结点。(易)A、16 B、32 C、31 D、106、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ _。(易)A、 2h B、 2h-1 C、 2h+1 D、 h+17、 对一个满二叉树，m个树

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

48、结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。(易)A、 bdgcefha B、 gdbecfha C、 bdgaechf D、 gdbehfca12、 在一非空二叉树的中序遍历序列中，根结点的右边_。(易)A、 只有右子树上的所有结点 B、 只有右子树上的部分结点C、 只有左子树上的部分结点 D、 只有左子树上的所有结点13、 如图6、1所示二叉树的中序遍历序列是_。(易)A、 abcdgef B、 dfebagc C、 dbaefcg D、 defbagcgcefdbaagedbchf图6.2 图6、1 14、 一棵二叉树如图6、2所示，其中序遍历的序列为_ _(易)A、 abdgcefh B、 dgbaechf C、 gdbehfca D、 abcdefgh15、设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、 cedba17、 实现任意二叉树的后序遍历的非递