数据结构作业题目答案.docx
《数据结构作业题目答案.docx》由会员分享，可在线阅读，更多相关《数据结构作业题目答案.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构作业题目答案
一、单择题
1.栈和队列的共同特点是（A）。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
2.二叉树的第k层的结点数最多为（2k-1）。
A.2k-1B.2K+1C.2K-1D.2k-1
3.数据结构中，从逻辑上可以把数据结构分成（C）。
A.动态结构和静态结构B.进凑结构和非进凑结构
C.线性结构和非线性结构D.内部结构和外部结构
4.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二树满足的条件是（b）。
相同的话则选a.
A.空或只有一个结点B.高度等于其结点数
C.任一结点无左孩子D.任一结点无右孩子
5.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（A）个元素。
A.n-iB.n+l-iC.n-1-iD.i
6.判定一个栈ST（最多元素为m0）为空的条件是（B）。
A.ST→TOP!
=0B.ST→TOP==0
C.ST→TOP!
=m0D.ST→TOP==m0
7.非空的循环单链表head的尾结点（由P所指向）满足（C）。
A.p->next=NULLB.p=NULLC.p->next=headD.p=head
8.在线性结构中，所有结点都有（B）个直接后继。
A.0B.0或1C.1D.不确定
9.设数组A[m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作时修改指针的语句是C。
A、sq.front=（sq.front+1）%m
B、sq.front=（sq.front+1）%（m+1）
C、sq.rear=（sq.rear+1）%m
D、sq.rear=（sq.rear+1）%（m+1）
二、填空题
1.已知一棵二叉树的中序序列和后序序列分别为：
DBGEACHF和DGEBHFCA，则该二叉树的前序序列是（ABDEGCFH）。
2.在（循环）链表中，从任何一结点出发都能访问到表中的所有结点。
3.以下函数的时间复杂度为（O（n））。
fact（intn）
{
if（n<=1）
return1;
else
return（n*fact（n-1））;
}
4.在线索化二叉树中，t所指结点没有左子树的充要条件是t->Ltag==（1或true）。
5.现有按中序遍历二叉树的结果为abc，问有（5）种不同形态的二叉树可以得到这一遍历结果。
6.如图所示，删除元素b的语句为（q->next=q->next->next）．
三、应用题
1.给出下面森林对应的二叉树及二叉树的后序序列。
2.已知二叉树的先序、中序和后序序列如下:
前序序列：
*BC***G*
中序序列：
CB*EAGH*
后序序列：
*EDB**FA
，其中有一些看不清的字母用*表示。
（1）请先补充*处的字母.
（2）再构造一棵符合条件的二叉树
（3）最后画出带头结点的中序线索链表。
答案：
3.有一个含头结点的单链表，头指针为A,另有一个不含头结点的单链表，头指针为B。
（1）分别写出判断A为空和B为空的条件。
（2）假设S指向一个新结点，分别写出在A的表头插入S，和在B的表头插入S的语句。
4.设A～H8个字符出现的概率为:
W={0.10,0.16,0.01,0.02,0.29,0.10,0.07,0.25}。
设计最优二进制编码（用0,1编码）
（1）画出最优二叉树
（2）计算平均码长（二叉树的带权路径长度）。
5.线性表有两种存储结构一是顺序表，二是链表。
试问
（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。
在此情况下，应选用哪种存储结构？
为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？
为什么？
答：
（1）选链式存储结构。
它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O
（1）。
（2）选顺序存储结构。
顺序表可以随机存取，时间复杂度为O
（1）。
6.循环队列的优点是什么？
如何判别它的空和满？
答：
优点：
循环队列克服了“假上溢”现象。
判别空和满：
设有循环队列sq，以（sq->rear+1）%MaxSize=＝sq->front或sq->count=＝MaxSize来判别队满；以sq->rear=＝sq->front来判别队空
四、编程题
1、已知顺序表结构体定义如下：
#defineMAXLEN100
typedefstruct{
intdata[MAXLEN];
intlast;
}SeqList;
在顺序表L的第i个位置上插入值为x的元素的函数定义如下：
intInsList（SeqList*L,inti,intx）{
……//
（1）函数代码空缺部分
}
要求：
将“
（1）函数代码空缺部分”的内容，在下面空白处填写完整，其中顺序表满，返回-1；插入位置错误，返回0；正常完成数据插入返回1。
2、已知链队列元素的结构体定义如下：
typedefstructNode{
intdata;
structNode*next;
}QNode;
链队列头结点定义为：
typedefstruct{
QNode*front,*rear;
}LQueue;
在队列中，完成入队操作的函数定义如下：
voidIn_LQueue（LQueue*q,intx）{
……//
（2）函数代码空缺部分
}
依据题目条件，将“
（2）函数代码空缺部分”的内容，在下面空白处填写完整。
3、已知线性单链表结构体定义如下：
typedefstructNode{
intdata;
structNode*next;
}LNode,*LinkList;
在单链表L的第i个位置上插入值为x的元素的函数定义如下：
intInsert_LinkList（LinkListL,inti,intx）{
…………//
（1）函数代码空缺部分
}
假设LNode*Get_LinkList（LinkListL,inti）函数已经定义完成，该函数的功能为“在单链表L中查找第i个元素结点，找到后返回其指针；否则返回空指针”。
要求：
将“
（1）函数代码空缺部分”的内容，在下面空白处填写完整，其中插入位置错误，返回值为0；正常完成数据插入返回值为1。
4、已知栈的结构体定义如下：
#defineMAXLEN100
typedefstruct{
chardata[MAXLEN];
inttop;
}SeqStack;
在栈中，完成“出栈”操作的函数定义如下：
intPop_SeqStack（SeqStack*s,char*x）{
//
（2）函数代码空缺部分
}
要求：
将“
（2）函数代码空缺部分”的内容，在下面填写完整，因空栈导致无法正常出栈，返回值为0；正常出栈返回值为1。
升级会员 