数据结构复习题(The most important)
第一章绪论
一、选择题
1、数据结构是一门研究非数值计算的程序设计问题中计算机的 A 以及它们之间的 B 和运算等的学科。(易)
① A、数据元素 B、计算方法 C、逻辑存储D、数据映象
② A、结构 B、关系 C、运算D、算法
2、数据结构被形式地定义为(K,R),其中K是 B 的有限集，R是K上的 D 有限集。(易)
① A、算法 B、数据元素C、数据操作D、逻辑结构
② A、操作 B、映象C、存储D、关系
3、在数据结构中，从逻辑上可以把数据结构分成__C______。(易)
A、动态结构和静态结构
B、紧凑结构和非紧凑结构
C、线性结构和非线性结构
D、内部结构和外部结构
4、算法分析的目的是 C ，算法分析的两个主要方面是 A 。(中)
① A、找出数据结构的合理性B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进
D、分析算法的易懂性和文档性
② A、空间复杂度和时间复杂度B、正确性和简单性
C、可读性和文档性
D、数据复杂性和程序复杂性
5、计算机算法指的是 C ，它必须具备输入、输出和 B 等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、数据——是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中被计算机程序处理的符号的总称。
2、数据元素——数据的基本单位，在计算机程序中通常做为一个整体进行考虑和处理。
3、数据对象：性质相同的数据元素的集合。
4、数据结构：相互具有一种或多种关系的数据元素的集合。
5、数据类型：是具有相同性质的计算机数据的集合及在这个数据上的一组运算，是和数据结构密切相关的概念。
6、算法：对特定问题求解步骤的一种描述，是有限指令的集合。
三、填空题
1、下面程序段的时间复杂度是__O(m*n)_____。(易)
for (i=0;i for (j=0;j a[i][j]=0; 2、下面程序段的时间复杂度是__O(根号n)_____。(中)(n 的值每次等差数列增长） i=s=0 while(s { i++; /* i=i+1 */ s+=i; /* s=s+i */ } 3、下面程序段的时间复杂度是___O(n^2)____。(易) s=0; for (i=0;i for (j=0;j s+=b[i][j]; sum=s; 4、下面程序段的时间复杂度是___O(Log3 n)____。(难) i=1; wile (i<=n) i=i*3; 5、数据元素可以由若干_数据项_____组成，__数据元素___是数据的基本单位，数据项____是数据的最小单位。(易) 6、数据结构分为两部分，即__逻辑___结构和_物理___结构。(易) 7、数据的存储方式分为__顺序___存储和___链式__存储。(易) 8、顺序存储是一种__随机___的存储方式，是用一组__连续___的存储空间存储数据，而链式存储是用一组_不连续__的存储空间存储数据。(易) 答案：1、O(m*n) 2、O(n) 3、O(2n) 4、O(lo3g n) 5、数据项数据元素数据项 6、逻辑物理 7、顺序链式 8、随机存取连续任意 四、简答题： 1、什么是算法，其基本性质是什么？(易) 2、算法的要求是什么？(中) 3、结构共分几类？其各自的性质是什么？(易) 答案：1、算法是对特定问题求解步骤的一种描述，是有限指令的集合。其基本性质如下： 1)有穷性：算法对任意合法的输入均能在有限时间、有限步骤后完成。 2)确定性：算法的每一步骤的含义都是唯一、确定的，对于相同的输入均能得到相同的输出。 3)可行性：算法的每一个步骤和指令都应在已实现的算法的基础上完成。 4)输入：任一个算法必须有0个或多个输入。 5)输出：任一个算法必须有1个或多个输出。 2、算法的要求是： 1)正确性：算法能正确描述待求解问题的需求，没有逻辑错误，据此算法书写的程序，对于任何合法的输入，都有得到正确的、说明需求的结果。 2)可读性：算法应简洁、明晰，易于阅读和理解，便于算法的移植和交流，有利于增加算法的生命力。 3)健壮性：当输入的数据非法时，算法要能作出适当的处理，不会产生难以预料的结果。 4)高效率性：一般来说，对同一问题的多种算法，首先选择执行时间相对较短、存储空间相对较少的算法，然后考虑易于实现的算法。 3、结构共分为四类，分别为： 1)集合：所有元素除共在同一集合外，没有其他关系。 2)线性结构：元素间是一对一的关系。 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(“%.2f\n”,ave); } 第二章线性结构 一、判断题 1、线性表的逻辑顺序与存储顺序总是一致的。(易) 错 2、顺序存储的线性表可以按序号随机存取。(易) 对 3、顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。(易) 对 4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。(易) 对 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(易) 错 6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。(易) 对 7、线性表的链式存储结构优于顺序存储结构。(易) 错 8、在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。(易) 对 9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。(易) 对 10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(易) 错 11、线性表中，每一个元素均存在前驱。(易) 错 12、线性表中，每一个元素均存在后继。(易) 错 13、线性表中，存在唯一一个被称为第一元素的元素。(易) 对 14、线性表中，存在唯一一个被称为最后一个元素的元素。(易) 对 15、线性结构是一种一对一的结构。(易) 对 答案：1-5 ×√√√× 6-10 √×√√× 11-15 ××√√√ 二、选择题： 1、线性表是( A ) 。(易) A、一个有限序列，可以为空； B、一个有限序列，不能为空； C、一个无限序列，可以为空； D、一个无序序列，不能为空。 2、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A）个元素。(易) A、n/2 B、(n+1)/2 C、(n –1)/2 D、n 3、线性表采用链式存储时，其地址( D ) 。(易) A、必须是连续的； B、部分地址必须是连续的； C、一定是不连续的； D、连续与否均可以。 4、用链表表示线性表的优点是（ C ）。(易) A、便于随机存取 B、花费的存储空间较顺序存储少 C、便于插入和删除 D、数据元素的物理顺序与逻辑顺序相同 5、某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。(易) A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表 6、循环链表的主要优点是( D ) 。(易) A、不再需要头指针了 B、已知某个结点的位置后，能够容易找到他的直接前趋 C、在进行插入、删除运算时，能更好的保证链表不断开 D、从表中的任意结点出发都能扫描到整个链表 7、下面关于线性表的叙述错误的是( B )。(易) A、线性表采用顺序存储，必须占用一片地址连续的单元； B、线性表采用顺序存储，不便于进行插入和删除操作； C、线性表采用链式存储，不必占用一片地址连续的单元； D、线性表采用链式存储，便于进行插入和删除操作； 8、单链表中，增加一个头结点的目的是为了（C）。(易) A、使单链表至少有一个结点 B、标识表结点中首结点的位置 C、方便运算的实现 D、说明单链表是线性表的链式存储 9、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。(易) A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 10、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ B）存储方式最节省运算时间。(易) A、单链表 B、顺序表 C、双链表 D、单循环链表 11、一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是___B____。(易) A、110 B、108 C、100 D、120 12、不带头结点的单链表head为空的判定条件是__A____。(易) A、head = = NULL; B、head->next = = NULL; C、head->next = = head; D、head! = NULL; 13、带头结点的单链表head为空的判定条件是__B____。(易) A、head = = NULL; B、head->next = = NULL; C、head->next = = head; D、head! = NULL; 14、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_B_。(易) 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结点，则执行___C___。(易) 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->next=s; s->next=q; 16、从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_D___个结点。(易) A、n; B、n/2; C、(n-1)/2; D、(n+1)/2; 17、给定有n个结点的向量，建立一个有序单链表的时间复杂度__C___。(易) A、 O(1); B、 O(n); C、 O(n 2 ); D、 O(nlog2n); 18、顺序存储结构是一种__A _的存储结构。(易) A、随机存取 B、索引存取 C、顺序存取 D、散列存取 19、在以下的叙述中，正确的是__C_。(易) A、线性表的顺序存储结构优于链表存储结构 B、线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C、线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D、线性表的链表存储结构优于顺序存储结构 20、非空的循环单链表head的尾结点（由p所指向）满足_C___。(易) A、 p->next= =NULL B、 p= =NULL C、 p->next= =head D、 p= =head 21、在一个单链表中，若删除p所指结点的后续结点，则执行__A__。(易) A、p->next= p->next->next； B、 p= p->next; p->next= p->next->next； C、p->next= p->next; D、p= p->next->next； 答案：1-5 AADCD 6-10 DBCDB 11-15 BABBC 16-20 DCACC 21 A 三、填空题 1 在一个长度为n的向量中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动___n-i+1__个元素。(易) 2、在一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动___n-i__个元素。(易) 3、在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作：(易) s->next=_p____; p->next=s; t=p->data; p->data=___(2)________; s->data=___(3)_______; 4、在线性表L=(a1,a2,……,an)中，L称为线性表的___名字____，n称为线性表的_长度_____。(易) 5、在线性表中有(ai,aj)，称ai为aj的_直接前驱_____，称aj为ai的_直接后继____。(易) 6、在顺序表中，若第一个元素所在的地址为Loc(a1)，每个元素在内存中占有L个存储单元，则元素ai在内存中的地址Loc(ai)=__Loc(a1)+(i-1)L______。(易) 7、顺序表是一种__随机___存取的存储结构，其元素的逻辑位置与物理位置一一对应。(易) 8、系统在内存中为顺序表提供一组__连续___的存储空间，为单链表提供一组_任意____的存储空间。(易) 9、在单链表中，一个结点包含两部分内容，分别为__数据域_____和___指针域____。(易) 10、在单链表中，若指针p已指向最后一个结点，则p应满足的条件是__p-> next=NULL_____。(易) 11、在单链表中，若结点p是结点q的前驱，应满足的条件是___P->next = q____。(易) 12、在单链表中，申请一个结点空间的命令是__malloc ( )_______，释放一个空间的命令是__free( )______。(易) 13、在双向链表中，每个结点有两个指针域，一个为_前驱指针域____，指向___前驱节点_ __；另一个为_后继指针域_____，指向___后续结点 _ _。(易) 14、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=__p->next __和p->next=_s___的操作。(易) 15、在双向链表中，若结点p是结点q的前驱，现要删除结点q，需要完成的操作是__p->next=q->next__________；__q->next->prior=p_________；(易) 16、在双向链表中，若在结点p之前插入一个新结点s，需要完成的操作有__s->prior=p->prior_____；__s->next=p_____；__p->prior->next=s_____；_p->prior=s_______；(易) 答案：1、n-i+1 2、n-i 3、(1) p->next (2) s->data (3) t 4、名字长度 5、直接前驱元素直接后继元素 6、Loc(ai)=Loc(a1)+(i-1)*L 7、随机 8、连续任意 9、指针域数据域 10、p.next==null 11、p.next=q 12、malloc() free() 13、前驱指针域 prior 后继指针域 next 14、p.next s 15、p.next=q.next; q.next.prior=q.prior; 16、s.prior=p.prior; s.next=p; p.prior.next=s; p.prior=s; 四、算法设计题： 1、在一顺序表L的第i个元素前，插入一新元素x。(中) 2、现有一顺序表L，其值非递增有序排列，现插入一新元素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(L.len==maxsize) return -1; for(j=L.len;j>=i;j--) L.elem[j+1]=L.elem[j]; L.elem[i]=x; L.len++; return 1; } 2、int Insert(SqList L,elemtp x) {if(L.len==maxsize) return -1; for(p=&L.elem[L.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.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; 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,%d\n”,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、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 错 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是__C__。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是__B__。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是__D__。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1(相当于数组编号） 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__C __。(不带空的头结点) (易) A、HS—＞next=s; B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next; 8、从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__B __。(不带空的头结点) (中) A、x=HS; HS= HS—＞next; B、x=HS—＞data; C、HS= HS—＞next; x=HS—＞data; D、x=HS—＞data; HS= HS—＞next; 9、一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是__C_ 。(易) A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 10、判定一个循环队列QU（最多元素为m）为空的条件是_C_。(中) A、rear - front= =m B、rear-front-1= =m C、front= = rear D、front= = rear+1 11、判定一个循环队列QU（最多元素为m, m= =Maxsize-1）为满队列的条件是_A__。(易) A、((rear- front)+ Maxsize)% Maxsize = =m B、rear-front-1= =m C、front= =rear D、front= = rear+1 12、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是__A。(中) A、 (rear-front+m)%m B、 rear-front+1 C、 rear-front-1 D、 rear-front 13、栈和队列的共同点是_C___。A、都是先进后出 B、都是先进先出C、只允许在端点处插入和删除元素 D、没有共同点 14、栈操作的原则是( B ) (易) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 15、在顺序栈中，判断栈s为空的条件是( D ) (中) A、t.base == NULL B、st.top == st.stacksize C、st.top-st.base>=st.stacksize D、st.top == st.base 16、在顺序栈中，判断栈s满的条件是( C ) (易) A、 st.base == NULL B、 st.top == st.stacksize C、 st.top-st.base>=st.stacksize D、 st.top == st.base 答案：1-5 CCABD 6-10 ACBCC 11-15 AACBD 16 C 三、填空题： 1、栈和队列都是_线性___结构，对于栈只能在_栈顶___插入和删除元素；对于队列只能在_队尾___插入元素和_队头___删除元素。(易) 2、向一个长度为n的顺序表的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动__n-i+1__个元素。(易) 3、向一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动__n-i__个元素。(易) 4、向栈中压入元素的操作是_push(i)___。(易) 5、对栈进行退栈时的操作是_pop(i)___。(易) 6、在一个循环队列中，队首指针指向队首元素的_位置___。(易) 7、从循环队列中删除一个元素时，其操作是__dequeue（i)__。(易) 8、在具有n个单元的循环队列中，队满时共有_n-1___个元素。(易) 9、一个栈的输入序列是12345，则栈的输出序列43512是错误的___。(易) 10、一个栈的输入序列是12345，则栈的输出序列12345是_可能的___。(易) 11、队列的基本性质是__先进先出_____；栈的基本性质是___后进先出______。(易) 12、在一个链栈中，若栈顶指针等于NULL则为___空栈____________，在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为__空队列__________或该队列______________。(易) 13、向一个栈顶指针为top的链栈中插入一个新结点*P，应执行p->next=top 和 top=p操作。(易) 14、栈的顺序存储结构即顺序栈，是利用一片连续的存储单元来依次存放自栈底至栈顶的数据元素；当栈为非空时，栈顶指针top始终指向栈顶元素。 15、从数据结构的角度看，栈和队列是受限两类线性表。(易) 答案：1. 线性、栈顶、队尾、队首 2. n-i+1 3. n-i 4.先移动栈顶指针，后存入元素 5. 先取出元素，后移动栈顶指针 6.前一个位置 7. 先移动队首元素，后取出元素 8. n-1 9. 不可能的 10. 可能的 11、FIFO LIFO 12、栈空空队只有一个元素 13、p->next=top top=p 14、一组地址连续的存储单元栈顶元素的下一位置 15、受限的线性表 四、算法题：1、输入一个任意的非负十进制整数,输出与其等值的八进值数。(中) 答案：void conversion() {InitStack(s); scanf(“%d”,&N); while(N) {push(s,N%d); N=n/8;} while(!empty(s)) {pop(s,e); printf(“%d\n”,e);} } 五、编程题： 1、从键盘上输入一个大写字母，要求改用小写字母输出。（中） 2、输入一个圆的半径，求其周长及面积并输出。 答案： 1、main() {char c; scanf(“%c”,&c); c=c+32; printf(“%c\n”,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=%.2f\n”,s,c); } 第四章串和广义表 一、判断题： 1、空串是由空白字符组成的串(易) 2、串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。(易) 3、串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。(易) 4、如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。(易) 5、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。(易) 6、广义表的表头一定是列表。(易) 7、广义表的表尾一定是列表。(易) 8、空串的长度为零。(易) 9、广义表的元素即可以是原子，也可以是子表。(易) 10、广义表中的子表与串中的子串的含义一样。(易) 11、广义表A=()，为空表，其长度为0。(易) 12、由于广义表的元素可以是列表，所以可以将广义表转化为一个树型结构 答案：1-5 ×√√×× 6-10 ×√√√× 11-12 √√ 二、选择题： 1、以下叙述中正确的是。(易) A、串是一种特殊的线性表 B、串的长度必须大于零 C、串中无素只能是字母 D、空串就是空白串 2、空串与空格串是相同的，这种说法____。(易) A、正确 B、不正确 3、串是一中特殊的线性表，其特殊性体现在____。(易) A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 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、BCDEFEF 6、设串的长度为n，则它的子串个数为。(易) A、n B、n(n+1) C、n(n+1)/2 D、n(n+1)/2+1 7、下列那些为空串（）(易) A、S=“” B、S=“” C、S=“φ” D、S=“θ” 8、S1=“ABCD”，S2=“CD”则S2在S3中的位置是（）(易) A、1 B、2 C、3 D、4 9、串是一种特殊的线性表，其特殊性体现在( )。(易) A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符 10、串是( )。(易) A、少于一个字母的序列 B、任意个字母的序列 C、不少于一个字符的序列 D、有限个字符的序列 11、串的长度是( )。(易) A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含的字符的个数 D、串中所含字符的个数，且大于0 12、若某串的长度小于一个常数，则采用( )存储方式最为节省空间。(易) A、链式 B、堆结构 C、顺序表 答案：1-5 ABBBD 6-10 CBCBD 11-12 CC 三、填空题： 1、串的两种最基本的存储方式是____。(易) 2、两个串相等的充分必要条件是____。(易) 3、空串是____，其长度等于____。(易) 4、空格串是____，其长度等于____。(易) 5、设s=’I︺AM︺A︺TEACHER’,其长度是____。(易) 6、串s=’abcdef’,s1=’cde’，s1在s中的位置为_____。(易) 7、广义表A=(a,(b,c d))；其表头为______，表尾为______。(中) 8、广义表A=(a,A)；其表头为______，表尾为______。(易) 9、串是每个结点仅由一个字符组成的（）。(易) 答案：1．顺序存储方式和链接存储方式 2．两个串的长度相等且对应位置的字符相同 3．零个字符的串、零 4．由一个或多个空格字符组成的串、其包含的空格个数 5．14 6、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） 五、编程题： 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(“%.2f\n”,s); } 2、main() {int x,y; scanf(“%d”,&x); if(x<0) y=1; if(x=0) y=0; if(x>0) y=-1; prinft(“%d\n”,y); } 第五章数组 一、名词解释： 1、压缩存储(易) 2、特殊矩阵(易) 3、稀疏矩阵(易) 答案：1、压缩存储：为多个值相同的元分配一个存储空间，对零元不分配存储空间。 2、特殊矩阵：值相同的元素或者是零元素分布的有规律则称为特殊矩阵。 3、稀疏矩阵：在一个m*n的矩阵中，有t个非0元，其稀疏因子为t/(m*n)，如果稀疏因子小于0.05就称为稀疏矩阵。 二、选择题： 1、设数组a[7][6]的基地址为1024,每个元素占2个存储单元,若以行序为主序顺序存储,则元素a[2][4]的存储地址是__。(中) A、1058 B、1056 C、1098 D、答案A,B,C都不对 2、二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为____。(中) A、 SA+141 B、 SA+180 C、 SA+222 D、 SA+225 3、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是____。(中) A、 80 B、 100 C、240 D、 270 4、二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为____。(中) A、 SA+141 B、 SA+144 C、 SA+222 D、 SA+225 答案：1-4 BBCC 三、填空题： 1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_______。(中) 2、二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。(中) 3、二维数组A[10…20][5…10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。(中) 4、现有一个n阶的对称矩阵a[n][n]，现将其压缩存储在一个一维数组s[m]中，则m=_______，若以行序为主序进行存储，则元素a[i][j](i>=j)在s中的下标k=______。(中) 5、在一个m*n的矩阵中，若a[0][0]是第一个元素，则a[i][j]是第______个元素。(中) 答案：1、LOC (A[0][0])+(n*i+j)*k 2.、326 3、1208 4、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\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、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。 (易) A、15 B、16 C、17 D、47 3、按照二叉树的定义，具有3个结点的不同形状的二叉树有____种。(易) A、3 B、 4 C、 5 D、 6 4、按照二叉树的定义，具有3个不同数据结点的不同的二叉树有____种。(易) A、5 B、 6 C、 30 D、 32 5、深度为5的二叉树至多有____个结点。(易) A、16 B、32 C、31 D、10 6、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ ___。(易) A、 2h B、 2h-1 C、 2h+1 D、 h+1 7、对一个满二叉树，m个树叶，n个结点，深度为h，则____ 。(易) A、 n=h+m B、 h+m=2n C、 m=h-1 D、 n=2 h-1 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。(易) A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 9、如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为____。(易) A、 uwvts B、 vwuts C、 wuvts D、 wutsv 10、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。(易) A、正确 B、错误 11、某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是____。(易) A、 bdgcefha B、 gdbecfha C、 bdgaechf D、 gdbehfca 12、在一非空二叉树的中序遍历序列中，根结点的右边____。(易) A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的部分结点 D、只有左子树上的所有结点 13、如图6、1所示二叉树的中序遍历序列是____。(易) A 、 abcdgef B 、 dfebagc C 、 dbaefcg D 、 defbagc 图6、1 14、 一棵二叉树如图6、2所示，其中序遍历的序列为__ __(易) A 、 abdgcefh B 、 dgbaechf C 、 gdbehfca D 、 abcdefgh 15、设a,b 为一棵二叉树上的两个结点，在中序遍历时，a 在b 前的条件是 。(易) A 、a 在b 的右方B 、a 在b 的左方 C 、a 是b 的祖先 D 、a 是b 的子孙 16、 已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是____。 (易) A 、 acbed B 、 decab C 、 deabc D 、 cedba 17、 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用____存储结构。(易) A 、 二叉链表 B 、 广义表存储结构 C 、 三叉链表 D 、 顺序存储结构 18、 如图6、3所示的4棵二叉树，____不是完全二叉树。(易) 19、 如图6、4所示的4棵二叉树，____是平衡二叉树。( 易) 20、在线索化二叉树中，t 所指结点没有左子树的充要条件是____。(易) A 、 t.left=NULL B 、 t.ltag=1 C 、 t.ltag=1且t —＞left=NULL D 、 以上都不对 21、 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。 (易) A 、 正确 B 、 错误 22、 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法____。 (易) A 、 正确 B 、 错误 23、 具有五层结点的二叉平衡树至少有____个结点。(易) g c e f d b a a g e d b c h f 图 6.2 (A) (B) (C) (D) 图6.3 图6.5 一棵树 A 、 10 B 、 12 C 、 15 D 、 17 24、 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。(易) A 、树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B 、树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C 、树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D 、以上都不对 25、 树最适合用来表示____。(易) A 、 有序数据元素 B 、 无序数据元素 C 、 元素之间具有分支层次关系的数据 D 、 元素之间无联系的数据 26、下列有关二叉树的说法正确的是( )。(中) A 、二叉树的度为2 B 、 一棵二叉树度可以小于2 C 、二叉树中至少有一个结点的度为2 D 、 二叉树中任一个结点的度都为2 27、以下说法错误的是( )。(中) A 、二叉树可以是空集 B 、 二叉树的任一结点都可以有两棵子树 C 、二叉树与树具有相同的树形结构 D 、 二叉树中任一结点的两棵子树有次序之分 28、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。(中) A 、15 B 、 16 C 、 17 D 、47 29、由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为( )。(中) A 、 23 B 、 37 C 、 46 D 、 44 30.在一棵具有n 个结点的二叉树第i 层上，最多具有( )个结点。(中) A 、2i B 、 2i+1 C 、 2i-1 D 、 2n 答案：1-5 BBCCC 6-10 ADACA 11-15 DABBB 16-20 DCCBB 21-25 BBBAC 26-30 BCBDC 二、填空题： 1、 有一棵树如图6、5所示，回答下面的问题：(易) ⑴ 这棵树的根结点是____； ⑵ 这棵树的叶子结点是____； ⑶ 结点D 的度是____； ⑷ 这棵树的度是____； ⑸ 这棵树的深度是____； ⑹ 结点H 的子女是____； ⑺ 结点H 的双亲结点是____； (8)结点N 的祖先是________。 2、 深度为k 的完全二叉树至少有____个结点。至多有____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则 编号最小的叶子结点的编号是____。(易) 3、 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n 0=____。(易) 4、 一棵二叉树的第i （i ≥1）层最多有____个结点，最少含有____个结点；一棵 有n （n>0）个结点的满二叉树共有____ 个 叶子和____个非终端结点。(易) 5、高度为k的二叉树最多有____个结点，最少有______个结点。(易) 6、由如图6、7所示的二叉树，回答以下问题：(易) ⑴其中序遍历序列为____； ⑵其前序遍历序列为____； ⑶其后序遍历序列为____； 7、对于一个具有n个结点的二叉树，当它为一棵二叉树时具有最小高度，即为，当它为一棵单支树具有高度，即为。(中) 8、8层完全二叉树至少有个结点，拥有100个结点的完全二叉树的最大层数为。(中) 9、二叉树通常有存储结构和存储结构。(易) 10、二叉树有不同的链式存储结构，其中最常用的是与。(中) 11、线索二叉树的左线索指向其，右线索指向其。(易) 12、遍历一棵二叉树包括访问、遍历和遍历三个方面。(易) 13、在二叉树中，某一结点x在第L层，x若有双亲，其双亲应在______层；若有孩子，其孩子应在______层。(中) 14、在二叉树中，某一结点x的编号为i，x若有双亲，其双亲编号应为_____；x若有左孩子，其左孩子编号应为______；x若有右孩子，其右孩子应为___________。答案：1、(1) A (2) EFGIJKLN (3) 2 (4) 4 (5) 5 (6) LMN (7) C (8) ACHM 2、2 k-1 2 k-1 2 k-2+1 3、n2+1 4、2 i-1 1 2[log2n+1]-1 2[log2n+1]–1 5、2 k-1 k 6、(1)dgbaechif (2)abdgcefhi (3)gdbeihfca log+1 最大 n 8、128 7 9、顺序链式 7、完全??n2 10、二叉链表三叉链表 11、某种遍历序列的直接前驱结点某种遍历序列的直接后继结点 12、根结点左子树右子树 13、L-1 L+1 14、i/2 2*i 2*i+1 三、判断题： 1、二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。(易) 2、二叉树就是结点度为2的树。(易) 3、二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。(易) 4、当k≥1时，高度为k的二叉树至多有2k-1个结点。(中) 5、完全二叉树的某结点若无左孩子，则它必是叶结点。(易) 6、用一维数组存放二叉树时，总是以前序遍历顺序存储结点。(易) 7、若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。(易) 8、存在这样的二叉树，对它采用任何次序的遍历，结果相同。(中) 9、中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。(易) 10、将一棵树转换成二叉树后，根结点没有左子树，(易) 11、由树转换成二叉树，其根结点的右子树总是空的。(易) 12、前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。(易) 13、在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。(易) 14、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。(易) 15、霍夫曼树一定是满二叉树。(易) 16、树的度是树内各结点的度之和。(易) 17、由二叉树的结点构成的集合可以是空集合。(易) 18、一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数(易) 答案：1-5 ××××√ 6-10 ××√√× 11-15 √×××× 16-18 ×√× 四、简答题： 1、具有3个结点的二叉树有几种形态，分别为什么？(易) 2、将左图中的森林转化成二叉树(中) 3、设有一段正文是由字符集{A,B,C,D,E,F}组成的，其中每个字符要正文中出现的次数分别为17,12,5,28,35,3。请构建哈夫曼树，并求出其WPL值，并给出每个字母的哈夫曼编码。(中) 4、已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ, 中序遍历的结果序列是EBCDAFHIGJ, 试画出这棵二叉树。(中) 答案：1、具有3个结点的二叉树有五种形态，如图所示： 2、转化成的二叉树如图： 3、构建的哈夫曼树为： 哈夫曼编码为： A：00 B：011 C：0101 D：10 E：11 F：0100 4、构建的二叉树为： 第七章图 一、选择题： 1、在一个图中，所有顶点的度数之和等于所有边数的____倍。(易) A 、 1/2 B 、 1 C 、 2 D 、 4 2、任何一个无向连通图的最小生成树 。(易) A 、只有一棵 B 、有一棵或多棵 C 、一定有多棵 D 、可能不存在 3、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。(易) A 、 1/2 B 、 1 C 、 2 D 、 4 4、一个有n 个顶点的无向图最多有____条边。(中) A 、 n B 、 n(n-1) C 、 n(n-1)/2 D 、 2n 5、具有4个顶点的无向完全图有____条边。(中) A 、 6 B 、 12 C 、 16 D 、 20 6、具有6个顶点的无向图至少应有____条边才能确保是一个连通图。(中) A 、 5 B 、 6 C 、 7 D 、 8 7、在一个具有n 个顶点的无向图中，要连通全部顶点至少需要____条边。(中) A 、 n B 、 n+1 C 、 n-1 D 、 n/2 8、对于一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。(中) A 、 n B 、 (n-1)2 C 、 n-1 D 、 n 2 9、对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示，则表头向量的大小为____。(易) A 、 n B 、 n+1 C 、 n-1 D 、 n+e 10、已知一个图如图7、1所示，若从顶点a 出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。(中) ① A 、a,b,e,c,d,f B 、e,c,f,e,b,d C 、a,e,b,c,f,d D 、a,e,d,f,c,b ② A 、a,b,c,e,d,f B 、a,b,c,e,f,d C 、a,e,b,c,f,d D 、a,c,f,d,e,b 11、已知一有向图的邻接表存储结构如图7、2所示。 ⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。(易) A 、 v1,v2,v3,v5,v4 B 、 v1,v2,v3,v4,v5 C 、 v1,v3,v4,v5,v2 D 、 v1,v4,v3,v5,v2 图7.2 一个有向图的邻接表存储结构 图 7.1 一个无向图 b a e c d f 1 2 3 4 5 3 2 4 5 2 4 ^ ^ ^ ^ ^ ⑵根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。(易) A、 v1,v2,v3,v4,v5 B、 v1,v3,v2,v4,v5 C、 v1,v2,v3,v5,v4 D、 v1,v4,v3,v5,v2 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。(易) A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。(中) A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 14、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。(易) A、求关键路径的方法 B、求最短路径的Dijkstra方法 C、宽度优先遍历算法 D、深度优先遍历算法 15、关键路径是事件结点网络中。(中) A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最长的回路 D、最短的回路 16、下面不正确的说法是。(易) （1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小； （2）AOE网工程工期为关键活动上的权之和； （3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。 A、（1） B、（2） C、（3） D、（1）、（2） 17、用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是。(易) A、逆拓朴有序的 B、拓朴有序的 C、无序的 18、在图7、3所示的拓朴排列的结果序列为。(易) A、125634 B、516234 C、123456 D 、521634 19、一个有n个顶点的无向连通图，它所包含的连通分量个数为。(中) A、0 B、1 C、n D、n+1 20．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为。(易) A、k1 B、k2 C、k1-k2 D、k1+k2 21、对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为。(中) A、k1 B、k2 C、k1-k2 D、k1+k2 22、具有n个顶点的有向图最多有( )条边。(中) A、n B、 n(n-1) C、 n(n+1) D、 2 n 23、 n个顶点的强连通图至少有( )条边。(中) A、 n B、 n-1 C、 n+1 D、 n(n-1) 24、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为( )。(中) A、s B、 s-1 C、 s+1 D、 n 25、在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为( )。(易) 图7.3有向图 A、k B、 k+1 C、 k+2 D、 2k 26、下面的叙述中不正确的是( )。(易) A、关键活动不按期完成就会影响整个工程的完成时间 B、任何一个关键活动提前完成，将使整个工程提前完成 C、所有关键活动都提前完成，则整个工程将提前完成 D、某些关键活动若提前完成，将使整个工程提前完成 27、一个图中包含k个连通分量，若按深度优先(DFS)搜索方法访问所有结点，则必须调用( )次深度优先遍历算法。(易) A、k B、 1 C、 k-1 D、 k+1 28、以下说法正确的是( )。(易) A、连通分量是无向图中的极小连通子图 B、强连通分量是有向图中的极大强连通子图 C、在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧 D、对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图 29、设G1=(V1,E1)和G2=(V2,E2)为两个图， V1?V2,E1?E2,则称（）(中) A、G1是G2的子图 B、G2是G1的子图 C、G1是G2的连通分量 D、G2是G1的连通分量 30.带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）(中) A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 答案：1-5 CBBCA 6-10 ACDAD（B） 11-15 C（B）ADDA 16-20 AABBB 21-25 ABAAB 26-30 BABAD 二、判断题： 1、在n个结点的无向图中，若边数 > n-1，则该图必是连通图。（）(易) 2、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。（）(易) 3、图的深度优先搜索序列和广度优先搜索序列不一定是唯一的。() (易) 4、有回路的图不能进行拓扑排序。( ) (易) 5、任何AOV网拓扑排序的结果都是唯一的。( ) (易) 6、在AOV-网中，如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径。( ) (易) 7、图的邻接矩阵中矩阵元素的行数只与顶点个数有关(易) 8、图的邻接矩阵中矩阵中非零元素个数与边数有关(易) 9、在拓扑排序序列中，任意两个相继结点V i和Vj都存在从V i到Vj的路径(易) 10、若一个图的邻接矩阵为对称矩阵，则该图必为无向图。(易) 11、任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条(易) 12、在有向图中，入度为0的结点称为叶子结点（或叶子）(易) 答案：1-5 ××√√× 6-10 √√√×× 11-15 √× 三、填空题 1、n个顶点的连通图至少____条边。(易) 2、在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。(易) 3、在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于____。(易) 4、已知图G的邻接表如图7、4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。(中) 图7、4 图G 的邻接表 5、已知一个有向图的邻接矩阵表示，计算第i 个结点的入度的方法是____。(易) 6、已知一个图的邻接矩阵表示，删除所有从第i 个结点出发的边的方法是____。(易) 7、如果含n 个顶点的图形成一个环，则它有 棵生成树。(易) 8、一个非连通无向图，共有28条边，则该图至少有 个顶点。(易) 9、一个无向图有n 个顶点和e 条边，则所有顶点的度的和即 ∑=n i i d 1 (i d 表示顶点i 的度)= 。(中) 10、一个图的 表示法是唯一的，而 表示法是不唯一的。(易) 11、有向图中的结点前驱后继关系的特征是 。(易) 12、若无向图G 的顶点度数最小值大于等于 时，G 至少有一条回路。(易) 13、根据图的存储结构进行某种次序的遍历，得到的顶点序列是 的。(易) 14、设无向图G 的顶点数为n ，图G 最少有 条边，最多有 条边。若G 为有向图，有n 个顶点，则图G 最少有 条边，最多有 条边。具有n 个顶点的无向完全图，边的总数为 条；而具有n 个顶点的有向完全图中，边的总数有 条。(中) 15、在有n 个顶点的有向图中，每个顶点的度最大可达 。(易) 16在一个图G 的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的 ；而对于无向图而言等于该顶点的 。(易) 17、对无向图，若它有n 个顶点e 条边，则其邻接表中需要 个结点。其中， 个结点构成邻接表， 个结点构成顶点表。(易) 答案：1.n-1 2. 1;0 3. 1 4.v1,v2,v3,v6,v5, v4；v1,v2,v5,v4,v3, v6 5.求矩阵第i 列非零元素之和 6. 将矩阵第i 行全部置为零 7.n 8.9 9、 2e 10．邻接矩阵 邻接表 11．一个结点可能有若干个前驱，也可能有若干个后继 12．2 13．唯一 14、0 n(n-1)/2 0 n(n-1) n(n-1)/2 n(n-1) 15．2(n-1) 16、出度数 度数 17、2e+n 2e n 四、简答题： 1、请用克鲁斯卡尔算法为图7、6构造最小生成树：(中) 图7-6 2、请用普里姆算法为图7、7构造最小生成树(中) v1 v3 v2 v4 v5 v6 v2 v5 v4 v3 v5 ^ ^ v6 v4 v6 v3 一、填空。 1．顺序存储结构的特点是（静态存储的物理次序和逻辑次序一致），链式存储结构的特点式（动态存储的物理次序和逻辑次序不一定一致）。 2．算法在遇到非法操作时可以作出合理处理的特性为（健壮性）。 3．常见的算法时间复杂度用大O记号表示为：常数阶（ O(1) ），对数阶（ O(log2n ) ），线性阶（O(n) ），平方阶( O(n2) )和指数阶（ O(2n) ）。 4．在单链表中，除了头结点以外，任一结点的存储位置由（其直接前驱的指针域）指示。 5．当线性表采用顺序存储结构时，其主要特点是（静态存储物理次序和逻辑次序一致）。6．在双链表中，每个结点设置了两个指针域，其中一个指向（直接前驱）结点，另一个指向（直接后继）结点。 7．设有一个空栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是（ 2,3 ），栈顶指针是（ 1003 H ）。8．栈S通常采用的两种存储结构是（顺序存储和链序存储）；其判定栈空的条件分别是（ s->top==-1 top->next==NULL ）, 判定栈满的条件分别是（ s->top==stack_size-1 ）。 9．（栈）可作为实现递归函数调用的一种数据结构。 10．栈和队列是两种特殊的线性表，栈的操作特性是（先进后出），队列的操作特性是（先进先出），栈和队列的主要区别是（栈是在表的一端进行操作，队列是在表的两端进行操作）。 11．循环队列的引入是为了克服（假溢出）。 12．数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为 ( (front-rear+n）mod n ）。 13．用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为（ O(1) ）和（ O(n) ）。 14．串是一种特殊的线性表，其特殊性体现在（串的数据限定为字符集）。 15．两个串相等的充分必要条件是（两个串的长度相等并且每个对应位置的字符都相等）。 16．（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。17．从逻辑关系上讲，数据结构主要分为（集合结构）、（线性结构）、（树形结构）、（图状结构或网状结构）。 18．数据的存储结构主要有（顺序）和（非顺序）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据的表示）和（关系的表示）。 19．算法具有5个特性，分别是（可行性，有限性，确定性，输入和输出） 20．顺序表中第一个元素的地址是100，每个元素的长度为2，则第五个元素的存储地址是（ 108 ）。 21．单链表中设置头指针的作用是（标识链表在内存中的位置）。 22、设单链表中指针P指向结点A，若要删除A的后继结点（假设A存在后继结点），则修改指针的操作为（ p->next=p->next->next; ）。 23．设S=”I AM A TEACHER”,其长度为（ 14 ）。 24．对于栈和队列，无论它们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是（ O(1) ）。 25．数组通常有两种运算：（获得特定位置的元素值）和（修改特定元素的值），这决定了数组通常采用（顺序）结构来存储。 1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2) 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 0一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示（D，S，P）。其中：D是数据对象，S 是D上的关系，P是对 D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表（头指针为L）中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取?表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(顺序弄反了)(f) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。栈和队列是操作上受限制的线性表(f) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。对列不是(f) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的 特殊情形。(f) 15 二叉树是一棵结点的度最大为二的树二叉树和树相互独立。(f) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历后根遍历相当于中序遍历。(f) 19. 通常，二叉树的第i层上有2i-1个结点。应该为1~2i-1个(f) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。 (t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。只能表示无向图，有向图用十字链表(f) 24 可从任意有向图中得到关于所有顶点的拓扑次序带环图没有。(f) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 26 关键路径是AOE网中源点到汇点的最短路径。(f) 27 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。(f) 28 一个无向图的连通分量是其极大的连通子图。(t) 29 十字链表可以表示无向图，也可用以表示有向图。(f) 30 邻接表可以表示有向图，也可以表示无向图。（t ） 31. 二叉排序树的平均查找长度为O(logｎ)。(t) 32. 二叉排序树的最大查找长度与（LOG2N）同阶。(f) 33 选用好的HASH函数可避免冲突。哈希函数有几种处理冲突的方法(f) 34 折半查找不适用于有序链表的查找。(t) 35. 对于目前所知的排序方法，快速排序具有最好的平均性能。(t) 36 对于任何待排序序列来说，快速排序均快于冒泡排序。(f) 数据结构考试复习题集团档案编码：[YTTR-YTPT28-YTNTL98-UYTYNN08] 复习题集 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机内部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据]（×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的内存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 数据结构期中练习 学号姓名 一、选择题 1.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 参考答案：C 2.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 参考答案：A B 3.判定一个栈ST(最多元素为m0)为空的条件是（）。 （A） ST-〉top!=0 （B）ST-〉top==0 （C）ST-〉top!=m0 （D）ST-〉top=m0 参考答案：B 4.判定一个栈ST(最多元素为m0)为栈满的条件是（）。 （A）ST->top!=0 （B）ST->top==0 （C）ST->top!=m0-1（D）ST->top==m0 参考答案：D 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 参考答案：C 6.稀疏矩阵一般的压缩存储方法有两种,即（）。 （A）二维数组和三维数组（B）三元组和散列 （C）三元组和十字链表（D）散列和十字链表 参考答案：C 7. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 （A）64（B）63 （C）63.5 （D）7 参考答案：C 8. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（） （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; 参考答案：B 9.在一个单链表中，若删除p所指结点的后续结点，则执行（） （A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next; （C）p->next=p->next; （D）p =p->next->next; 参考答案：A 10.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（）。 （A）SA+141（B）SA+180（C）SA+222（D）SA+225 参考答案：B 11. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。 （A） edcba（B）decba（C）dceab （D）abcde 参考答案：C 12.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素( ) 的起始地址相同。 （A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4] 参考答案：B 13.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（）。 （A）80（B）100（C）240（D）270 参考答案：C 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 第1章绪论 1 自测习题 二、选择题 1．以下数据结构中，属于线性结构的是 ( B ) A）有向图B）串C）线索二叉树D）B树 2．下列与数据元素有关的叙述中错误的是 (A) A）数据元素是有独立含义的数据最小单位 B）数据元素是描述数据的基本单位 C）数据元素可以称做结点 D）数据元素可以称做记录 3．以下术语中与数据的存储结构无关的是 (A) A）栈B）散列表C）顺序表D）双链表 4．以下数据结构中，属于线性结构的是 (B) A）有向图B）串C）线索二叉树D）B树 三、填空题 1．数据结构包括的三方面内容分别是：数据的逻辑结构、数据的存储结构和数据的运算。 2．数据元素是数据的基本单位，在某些情况下也可以称为结点、记录和顶点。 3．数据逻辑结构的4种基本形态包括集合结构、线性结构、树型结构和图（网）结构。 4．一个正确的算法应该具有5个特性：输入、输出、确定性、可行性和有穷性。 5．数据的存储结构包括顺序、链式、索引和散列四种。6．一个数据结构在计算机中的映象称为存储结构。 7．一个算法的效率主要是指该算法的时间效率和空间效率。 8．以下程序段的时间复杂度T（n）=_) O_____。 (2n sum=0; for(i=0 ; i 环链表 2．线性表是具有n 个 (B) 的有限序列。 A ）数据项 B ）数据元素 C ）表元素 D ）字符 3．若长度为n 的线性表采用链式存储结构，访问其第i 个元素的算 法时间复杂度为 (B) A ）O(1) B ）O(n) C ） O(n 2) D ）O(log 2n) 4．在长度为n 的顺序表中，若要删除第i （1≤i ≤n ）个元素，则 需要向前移动的元素的次数为 (B) A ）i B ）n-i C ）n-i+1 D ）n-i-1 5．在长度为n 的顺序表中第i （1≤i ≤n ）个位置上插入一个元素时， 为留出插入位置所需移动元素的次数为 (C) A ）n-i B ）i C ）n-i+1 D ）n-i-1 三、填空题 1．有一单链表结构如下： 图2-1 填空题1附图 若要删除值为c 的结点，应做的操作是 p->link=p->link->link 。 2．线性表L=( a 1,a 2,…a n )用数组存储。假定删除表中任一元素的概 … … data link 2005年－2006学年第二学期“数据结构”考试试题（A）姓名学号(序号)_答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清晰姓名、班号和学号），需写清晰题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2.链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3.在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是d 。 A.不带头结点的单链表 B.带头结点的单链表 C.循环双链表 D.顺序表 解D。 5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。A.edcba B.decba C.dceab D.abcde 答：C。 6.循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7.两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是 c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90,80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40 答：C。 9.以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80,77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80,60,66,98,82,10,20} 第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．部结构和外部结构。 3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点．B．无直接后继结点． 数据结构复习题答案 一、选择题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时 ( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、 尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？ ( ) A. 队列 B. 栈 C. 线 性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放 位置在644 ，A[2][2]存放位置在676(10)，每个 (10) 元素占一个空间，问A[3][3](10)存放在（）位 置，脚注 表示用10进制表示。 (10) A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B. 无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19] 中，第一个元素放A[1]中，现进行二分查找，则 查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2， 3 C. 9，5，3 D. 9，4，2， 3 8.对n个记录的文件进行快速排序，所需要的辅 助存储空间大致为( ) A. O（1） B. O（n） C. O n） D. O（n2） （1og 2 9.对于线性表（7，34，55，25，64，46，20，10） 进行散列存储时，若选用H（K）=K %9作为散列 函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 一、选择题 1、一个n个顶点的无向连通图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn 2、以下数据结构中，（）是非线性数据结构。 A．树B．字符串C．队列D．栈 3、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。 A．n –i+1 B．n –i C．i D．i-1 4、与线性表的链接存贮不相符合的特性是（）。 A．便于插、删运算B．需要连续的存贮空间 C．只能顺序查找D．存贮空间动态分配 5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数 为（）。 A．(rear-front+m)%m B．rear-front+1 C．(front+rear+m)%m D．(rear-front)%m 6、一个有n个顶点的无向图最多有( )条边。 A．n(n-1)/2 B．n (n-1) C．n-1 D．n+1 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， 8、从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．初等结构、构造型结构 C．线性结构、非线性结构D．树型结构、图型结构 9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（） A．空或只有一个根结点B．高度等于其结点数 C．任一结点无左孩子D．任一结点无右孩子 10、已知一个有向图用邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。 A．将邻接矩阵的第i 行删除B．将邻接矩阵的第i 行元素全部置零 C．将邻接矩阵的第i 列删除D．将邻接矩阵的第i 列元素全部置零 11、算法分析的两个主要方面是（） A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 13、具有6个顶点的无向连通图的生成树应有（）条边。 A．5 B．6 C．7 D．8 14、设栈的输入序列是A、B、C，则（）不可能是其出栈序列。 A．CBA B．CAB C．BCA D．ACB 15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（）。 A．head==NULL B．head->next==NULL C．head->next== head D．head ！=NULL 16、栈和队都是（） A．顺序存储的线性结构B．链式存储的非线性结构 C．限制存取点的线性结构D．限制存取点的非线性结构 17、在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。 A．①②③B．②③④C．②④D．①④ 18、以下数据结构中，（）是非线性数据结构。 《数据结构》课程复习资料 一、填空题: 1.设需要对5个不同的记录关键字进行排序，则至少需要比较________次，至多需要比较__________次。 2.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。 3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查 找成功有结点数有_________个。 4.数据结构从逻辑上划分为三种基本类型：___________、__________和___________。 5.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中， 包含有________条边。 6.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。 7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复 杂度为________。 8.在快速排序、堆排序、归并排序中，_________排序是稳定的。 9.在有n个叶子结点的哈夫曼树中，总结点数是_______。 10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定 _______。 11.3.已知数组A［10］［10］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存 储在起始地址为1000的连续的内存单元中，则元素A［5，6］对应的地址是_______。 12.在有n个结点的无向图中，其边数最多为_______。 13.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。 14.对矩阵采用压缩存储是为了___ ____。 15.带头结点的双循环链表L为空表的条件是_______。 16.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是。 17.对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运 算时，可能发生栈的下溢。 18.在双向链表中，每个结点有两个指针域，一个指向，另一个指向。 19.由一棵二叉树的前序序列和可唯一确定这棵二叉树。 20.折半查找的存储结构仅限于___ _，且是_ ___。 21.对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复 杂度为________________。 22.在稀疏距阵所对应的三元组线形表中，每个三元组元素按____________为主序，__________为辅序的 次序排列。 23.中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为______________。 24.在一棵高度为h的3叉树中，最多含有_______结点。 25.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i数据结构复习题答案 2
数据结构复习题(附答案)
数据结构复习题附答案
数据结构 期末考试复习题及答案
必看!!!!!数据结构期末复习题及部分答案解析
数据结构考试复习题
数据结构期末考试试题及答案
数据结构习题及答案 (9)
数据结构考试题库含答案
2015年数据结构期末考试题及答案
数据结构基本复习题答案
数据结构期末考试试题含复习资料
数据结构练习试题和答案解析
数据结构复习题答案
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
数据结构复习题及答案
数据结构复习题及参考答案