《数据结构》复习题

一、填空题1、数据结构就是一门研究数据的逻辑结构和物理结构，以及它们之间的关系和所定义的算法如何运行的学科。2、四种基本逻辑结构分别是集合、线性结构、树形结构和图状结构。3、算法的质量可从以下几个方面来评价：正确性、易读性、健壮性和高效率。4、线性表的最基本操作有插入、删除和定位（查找）三种。5、设每个数据元素占用K个存储单元，若a1的地址为Loc(a1)，则ai的地址为Loc(a1)+(i-1)*k。6、栈是一种操作在栈顶一端进行的线性表。7、栈的结构特征是后进先出。8、在队列中，允许进队的一端称为队尾，允许出队的一端称为队首。9、队列的结构特征是先进先出。10、若串的长度为0时，该串称之为空串。11、树中度数为0的结点称为叶结点。12、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第1个元素的地址为address,则第i个结点的地址是address+(i-1)*m。13、线性表有两种存储结构：顺序存储结构和链式存储结构，就两种存储结构完成下列填空： 顺序存储结构存储密度较大，链式存储结构 存储利用率较高，顺序存储结构可以随机存取， 链式存储结构不可以随机存取，链式存储结构插入和删除操作比较方便。14、顺序表中逻辑上相邻的元素在物理位置上也相邻，在链表中逻辑上相邻的元素的物理位置不一定相邻。15、在顺序表la的第i个元素前插入一个新元素，则有效的i值范围是1 =i=length；在顺序表lb的第j个元素之后插入一个新元素，则j的有效范围是1 = j=length；要删除顺序表lc的第k个元素，则k的有效范围是 1 =k=length。16、设有一个空栈，现有输入序列为1，2，3，4，5，经过操作序列 push , pop , push , push , pop, push ,push ,pop 后，现在已出栈的序列是1,3,5 ，栈顶元素的值是 4 。17、设有栈 S ，若线性表元素入栈顺序为1，2，3，4，得到的出栈序列为1，3，4，2，则用栈的基本运算Push, Pop描述的操作序列为push , pop, push, push , pop, push , pop, pop。18、在一个链队列中，若队首指针为 front,队尾指针为 rear，则判断该队列只有一个结点的条件front!=NULL&front=rear。19、设循环队列的头指针 front 指向队头元素，尾指针 rear 指向队尾元素后的一个空闲元素，队列的最大空间为 MAX ，则队空的标志为front=rear，队满的标志为 (rear+1)%MAX=front)，当rearfront 时队列长度是rear-front+MAX20、已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。其后序遍历次序为edcgbfa。层次遍历次序为afbcgde。21、设有二维数组A (5 x 7) ,每一元素用相邻的4个字节存储，存储器按字节编址。已知A00的存储地址为100。则按行存储时，元素A14的第一个字节的地址是144；按列存储时，元素A14的第一个字节的地址是184。22、队列的插入操作是在队列的队尾进行，删除操作是在队列的队首进行。23、当用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件是top=0。24、设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用128个字节。W中第6 行的元素和第4 列的元素共占用44个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W6，3的起始地址为208。25、二叉树是指度为2的有序树。一棵结点数为N的二叉树，其所有结点的度的总和是n-1。26、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的前一个位置，该循环队列的最大长度为n-1。27、一棵高度为5的二叉树中最少含有5个结点，最多含有31个结点；28、在串S=“structure”中，以t为首字符的子串有12个。29、假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B0存储矩阵中第1个元素a1,1,则B31中存放的元素是 a4,8。30、设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是4，编号为8的左孩子结点的编号是16。31、在一个长度为n的顺序表中第i个元素（1=irnext=p-rnext、p-rnext-lnext=f、p-rnext=f、f-lnext=p。35、链接存储的特点是利用指针来表示数据元素之间的逻辑关系。36、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：p-next=p-next-next37、对于栈操作数据的原则是后进先出。38、栈是限定仅在表尾进行插入或删除操作的线性表。39、在作进栈运算时应先判别栈是否栈满;在作退栈运算时应先判别栈是否栈空；40、循环队列的引入，目的是为了克服假溢出41、队列的特点是先进先出。42、数组的存储结构采用顺序存储方式。43、设有二维数组A0.9,0.19,其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A6,6存储地址为232。44、二叉树由根结点，左子树，右子树三个基本单元组成。45、在二叉树中，指针p所指结点为叶子结点的条件是p-lnext=NULL &p-rnext=NULL。46、深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点。二、算法填空题1、顺序表的定位算法struct nodeint data20;int length;int loc(struct node *l,int item)int i,j;j=l-length;if(j=0) return 0;for(i=0;idatai=item) return i;printf(“找不到！”);return 0;2、顺序表的插入算法struct nodeint data20;int length;int ins(struct node *l,int i,int x)int j;if(il-length+1) return 0;for(j=l-length;j=i;j-)l-dataj=l-dataj-1;l-dataj-1=x;l-length+;return 1;3、顺序表删除算法struct nodeint data20;int length;int del(struct node *l,int i;)int j;if(il-length)return 0;for(j=i-1;jlength-2;j+)l-dataj=l-dataj+1;l-length-;return 1;4、单链表的定位算法struct nodeint data;struct node *next;int loc(struct node*l,int item)int i;struct node *temp;temp=l-next;while(temp!=NULL&temp-data!=item)i+;temp=temp-next;if(temp=NULL) return 0;else return i;5、单链表的插入算法(后插法)struct nodeint data;struct node *next;int ins(struct node *l,int i,int item)int j=1;struct node *node,*temp;node=(struct node*)malloc(sizeof(struct node);node-data=item;temp=l-next;if(temp=NULL)if(i=0)l-next=node;node-next=NULL;return 1;elsereturn 0;while(jnext;j+;if(temp=NULL) return 0;node-next=temp-next;temp-next=node;return 1;6、单链表的删除算法struct nodeint data;struct node *next;int del(struct node *l,int i)struct node *temp,*p;int j=0;temp=l;if(temp-next=NULL)return 0;while(jnext!=NULL)j+;temp=temp-next;if(temp-next=NULL)return 0;p=temp-next;temp-next=p-next;free(p);return 1;7、双向链表的插入算法Struct nodeint data;struct node *lnext;struct node *rnext;int insertdlist(struct node *l,int i,int item) int j=1;struct node *node,*temp;node=(struct node*)malloc(sizeof(struct node);node-data=item;temp=l-rnext;if(temp=NULL)if(i=0)l-rnext=node;node-rnext=NULL;node-lnext=l;return 1;elsereturn 0;while(jrnext;j+;if(temp=NULL) return 0;node-rnext=temp-rnext;node-lnext=temp;temp-rnext-lnext=node;temp-rnext=node;return 1;8、双向链表的删除算法Struct nodeint data;struct node *lnext;struct node *rnext;int deldlist(struct node *head,int i)struct node *temp,*p;int j=0;temp=head;if(temp-rnext=NULL)return 0;while(jrnext!=NULL)j+;temp=temp-rnext;if(jrnext=NULL)return 0;temp-lnext-rnext=temp-rnext;if(temp-rnext!=NULL)temp-rnext-lnext=temp-lnext;free(temp);return 1;9、顺序栈的入栈算法Struct nodeint stack20;Int top;struct node *push(struct node *s,int x) if(s-top=20)return NULL;elses-stacks-top=x;s-top+;return s;10、顺序栈的出栈算法Struct nodeint stack20;Int top;int pop(struct node *S)if(S-top=0)printf(n顺序栈是空栈!);return 0;S-top-;return S-stackS-top;11、链栈的入栈算法struct nodeint data;struct node *next;struct node *push(struct node *top,int item)struct node *p;p=(struct node*)malloc(sizeof(struct node);p-data=item;p-next=top;top=p;return top;12、链栈的出栈算法struct nodeint data;struct node *next;struct node *pop(struct node *top)struct node *p;if(!top)printf(链栈是空栈！);return NULL;p=top;top=top-next;free(p);return top;13、链队的进队算法struct nodeint data;struct node *next;struct linkstruct node *front;struct node *rear;void addq(struct link *head,int item)struct node *p;p=(struct node*)malloc(sizeof(struct node);p-data=item;p-next=NULL;head-rear-next=p;head-rear=p;return;14、链队的出队算法struct nodeint data;struct node *next;struct linkstruct node *front;struct node *rear;void delq(struct link *head)struct node *p;p=head-front;if(!p)printf(空队不能做出队操作！);return;head-front=head-front-next;free(p);return;三、判断题（T）1、栈和队列都是限制存取点的线性结构。（F）2、设栈的输入序列是1，2，n，若输出序列的第一个元素是n，则第i个输出元素是n-i+1。（T）3、若一个栈的输入序列是1，2，3n，输出序列的第一个元素是i，则第i个输出元素不确定。（F）4、循环队列不会发生溢出。（T）5、链队列与循环队列相比，前者不会发生溢出。（T）6、直接或间接调用自身的算法就是递归算法。（F）7、数据元素是数据的最小单位。（T）8、数据结构是带有结构的数据元素的集合。（F）9、算法的时间复杂度是算法执行时间的绝对度量。（F）10、算法的正确性是指算法不存在错误。（F）11、线性表的逻辑顺序与物理顺序总是一致的。（F）12、线性表的顺序存储表示优于链式存储表示。（T）13、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（F）14、二维数组是其数组元素为线性表的线性表。（T）15、每种数据结构都应具备三种基本运算：插入、删除和搜索。（F）16、线性表的链式存储结构优于顺序存储结构。（F）17、栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。（T）18、字符串是数据对象特定的线性表。（F）19、在单链表P指针所指结点之后插入S结点的操作是：P-next= S ; S- next = P-next; （T）20、一个无向图的连通分量是其极大的连通子图。（T）21、邻接表可以表示有向图，也可以表示无向图。（T）22、假设B是一棵树，B是对应的二叉树。则B的后根遍历相当于B的中序遍历。 （F）23、通常，二叉树的第i层上有2i-1个结点。（F）24、数据元素是数据的最小单位。（F）25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（F）26、算法的优劣与算法描述语言无关，但与所用计算机有关。（T）27、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（F）28、程序一定是算法。（F）29、链表中的头结点仅起到标识的作用。（T）30、顺序存储结构的主要缺点是不利于插入或删除操作。（T）31、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（F）32、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（F）33、线性表的特点是每个元素都有一个前驱和一个后继。（F）34、循环链表不是线性表。（F）35、线性表只能用顺序存储结构实现。（F）36、线性表就是顺序存储的表。（F）37、即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（T）38、栈与队列是一种特殊操作的线性表。（T）39、若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。（F）40、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（T）41、循环队列也存在空间溢出问题。（F）42、二叉树是度为2的有序树。（T）43、完全二叉树中，若一个结点没有左孩子，则它必是树叶。（F）44、数组是同类型值的集合。（F）45、二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。（F）46、一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i n)，右儿子是2i+1（2i+1data); head=p; p=malloc(); Scanf(%d,&p-data); if(head-data=p-data) head-next=p; p-next=NULL; else p-next=head; head-next=NULL; head=p; 2、 设head是链表入口，请计算该链表中结点个数。写出实现算法。compute(head,p) p=0;i=head; while(i!=NULL) p+; i=i-next; printf(%dn,p);3、 设head是链表入口，请计算该链表中数据域为偶数的结点个数。写出实现算法。compute(head,p) p=0;i=head; while(i!=NULL) if(i%2=0) p+; i=i-next; printf(%dn,p);4、 设head是链表入口，在结点p之后插入一个值为i的结点。写出实现算法。ins(head,p,i) x=malloc(size); x-data=i; if(head=NULL) head=x; x-next=NULL; else x-next=p-next; p-next=x; 5、 设head是链表入口，查找数据域为key的结点，若找到，请删除该结点。写出实现算法。lgsearch(head,key)w=head;p=head;while(p!=NULL)&(p-data!=key)w=p;p=p-next;if(p=NULL) puts(NO!);elseif(head=p)head=p-next;elsew-next=p-next;五、队或栈算法题1、有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？2、画出对算术表达式A-B*C/D-E求值时操作数栈和运算符栈的变化过程。3、设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。4、设输入序列为1，2，3，4，5,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。5、简述顺序存储队列的假溢出的避免方法及队列满和空的条件。六、数组地址计算题设有一数组A（1：5，1：8