数据结构》复习题

一、填空题1、数据结构就是一门研究数据的逻辑结构和物理结构，以及它们之间的关系和所定义的算法如何运行的学科。

2、四种基本逻辑结构分别是集合、线性结构、树形结构和图状结构。

3、算法的质量可从以下几个方面来评价：正确性、易读性、健壮性和高效率。

4、线性表的最基本操作有插入、删除和定位（查找）三种。

5、设每个数据元素占用K个存储单元，若a[1]的地址为Loc(a1)，则a[i]的地址为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)，当rear<front 时队列长度是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，则二维数组元素W[6，3]的起始地址为208。

25、二叉树是指度为2的有序树。

一棵结点数为N的二叉树，其所有结点的度的总和是n-1。

26、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的前一个位置，该循环队列的最大长度为n-1。

27、一棵高度为5的二叉树中最少含有5个结点，最多含有31个结点；28、在串S=“structure”中，以t为首字符的子串有12个。

29、假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B[0]存储矩阵中第1个元素a1,1,则B[31]中存放的元素是a4,8。

30、设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是4，编号为8的左孩子结点的编号是16。

31、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动n-i+1个元素。

32、在单链表中设置头结点的作用是简化插入、删除操作。

33、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和多重链表；34、在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是f->rnext=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、设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为232。

44、二叉树由根结点，左子树，右子树三个基本单元组成。

45、在二叉树中，指针p所指结点为叶子结点的条件是p->lnext=NULL &&p->rnext=NULL。

46、深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点。

二、算法填空题1、顺序表的定位算法struct node{int data[20];int length;};int loc(struct node *l,int item){int i,j;j=l->length;if(j==0) return 0;for(i=0;i<j;i++)if(l->data[i]==item) return i;printf(“找不到！”);return 0;}2、顺序表的插入算法struct node{int data[20];int length;};int ins(struct node *l,int i,int x) {int j;if(i<1||i>l->length+1) return 0;for(j=l->length;j>=i;j--)l->data[j]=l->data[j-1];l->data[j-1]=x;l->length++;return 1;}3、顺序表删除算法struct node{int data[20];int length;};int del(struct node *l,int i;){int j;if(i<1||i>l->length)return 0;for(j=i-1;j<l->length-2;j++)l->data[j]=l->data[j+1];l->length--;return 1;}4、单链表的定位算法struct node{int 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 node{int 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(j<i&&temp!=NULL){ temp=temp->next;j++;}if(temp==NULL) return 0;node->next=temp->next;temp->next=node;return 1;}6、单链表的删除算法struct node{int 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(j<i-1&&temp->next!=NULL){ j++;temp=temp->next;}if(temp->next==NULL)return 0;p=temp->next;temp->next=p->next;free(p);return 1;}7、双向链表的插入算法Struct node{int 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(j<i&&temp!=NULL){ temp=temp->rnext;j++;}if(temp==NULL) return 0;node->rnext=temp->rnext;node->lnext==temp;temp->rnext->lnext=node;temp->rnext=node;return 1;}8、双向链表的删除算法Struct node{int 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(j<i&&temp->rnext!=NULL){ j++;temp=temp->rnext;}if(j<i&&temp->rnext==NULL)return 0;temp->lnext->rnext=temp->rnext;if(temp->rnext!=NULL)temp->rnext->lnext=temp->lnext;free(temp);return 1;}9、顺序栈的入栈算法Struct node{int stack[20];Int top;};struct node *push(struct node *s,int x){if(s->top==20)return NULL;else{s->stack[s->top]=x;s->top++;return s;}}10、顺序栈的出栈算法Struct node{int stack[20];Int top;};int pop(struct node *S){if(S->top==0){printf("\n顺序栈是空栈!");return 0;}S->top--;return S->stack[S->top];}11、链栈的入栈算法struct node{int 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 node{int 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 node{int data;struct node *next;};struct link{struct 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 node{int data;struct node *next;};struct link{struct 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、栈和队列都是限制存取点的线性结构。