当前位置:
文档之家› 《数据结构》期中试题(有答案)
《数据结构》期中试题(有答案)
5.写出下述算法A的功能:
其中BiTree定义如下:
Typedef struct BiTNode{
TElemType data;
struct BiTNode *LChild, *RChild;
}BiTNode, *BiTree;
Status A(BiTree T)
{
Queue Q;
InitQueue(Q);
得分
评卷人
四、阅读算法(每小题5分,共25分)
1.void AE(Stack& S){
InitStack(S);
Push(S,3);
Push(S,4);
int x=Pop(S)+2*Pop(S);
Push(S,x);
int i,a[5]={1,5,8,12,15};
for(i=0;i<5;i++) Push(S,2*a[i]);
weight
Parent
Lchild
Rchild
weight
Parent
Lchild
Rchild
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5
0
0
0
29
0
0
0
7
0
0
0
8
0
0
0
14
0
0
0
23
0
0
0
3
0
0
0
11
0
0
0
--
0
0
0
--
0
0
0
--
0
0
0
--
0
0
0
--
0
0
0
--
0
0
0
--
0
0
0
1
2
3
4
5
6
7
8
9
10
(1)InitList(La);
Int a[]={100,26,57,34,79};(1)79 34 57 26 100
For (i=0;i<5;i++)
ListInsert(La,1,a[i]);//逆序;
(2)ListDelete(La,1,e);//e=79;(2)34 57 26 100 79
11
12
13
14
15
5
9
0ቤተ መጻሕፍቲ ባይዱ
0
29
14
0
0
7
10
0
0
8
10
0
0
14
12
0
0
23
13
0
0
3
9
0
0
11
11
0
0
8
11
1
7
15
12
3
4
19
13
8
9
29
14
5
10
42
15
6
11
58
15
2
12
100
0
13
14
3、内存中一片连续空间(不妨假设地址从1到m)提供给两个栈s1和s2使用,怎样分配这部分存储空间,使得对任一栈,仅当这部分空间全满时才发生上溢。如何判断栈满,栈空,并对两个栈的容量进行分析。(7分)
ENQueue(Q,T);
While(not QueueEmpty(Q))
{ DeQueue(Q,e);
If(e==NULL) break;
Else
{ Print(e.data);
ENQueue(Q,e.LChild);
ENQueue(Q.e.RChild);
}
}
}
答:层次遍历二叉树的非递归算法
得分
答:选择顺序存储。因为顺序存储可以通过下标随意访问线性表中的元素,效率较高。而链式存储要访问某个元素是,需要遍历链表来找到这个元素,效率比较低。
选择顺序存储结构;理由有两点(1)主要从插入删除操作在移动元素的个数上分析,(2)顺序存储定位块,可直接定位。
2、哈夫曼树在构造时,首先进行初始化存储空间,结果如左下图,当构造完成后,请填写最后状态表,如右下图。(6分)(见课本P148)
{
cerr<<"Memory allocation failare!"<<endl;
exit(1);
}
________newptr->data=item;_______
newptr->next=NULL;
if (HL==NULL)
HL=__newptr___________;
else{
LNode* P=HL;
2.编写算法计算给定二叉树中叶结点的个数。
其中树节点定义如下
typedef struct BiTNode{
DataType data;
Struct BiTNode *LChild, * RChild;
typedefstruct LNode
{
ElemType data;
Struct LNode* next;
}*List, LNode;
函数定义:voidinvert(List& L)
voidinvert(List& L)//链表的就地逆置;带头结点的单链表;
{
p=L->next; q=p->next; s=q->next; p->next=NULL;
return(1);
}
2.向单链表的末尾添加一个元素的算法。
LNode是一个包含(data,Next)的结构体
Void InsertRear(LNode*& HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
If (____newptr==NULL__________)
B线性表是具有n(n>=0)个元素的一个有限序列
C线性表就是顺序存储的表(可以是链式存储结构)
D线性表只能用顺序存储结构实现(可以是链式存储结构)
2、表长为n的顺序存储的线性表,当在任何一个位置上插入或者删除一个元素的概率相等时,删除一个元素需要移动元素的平均个数为(A)
A (n-1)/2B n/2 Cn D n-1
评卷人
五、算法填空(每空1分,共9分)
1.堆分配存储方式下,串连接函数。
typedef struct
{
char * ch;
int len;
} HString;
HString *s,t;
StatusStrCat(s,t) /*将串t连接在串s的后面*/
{
int i;
char *temp;
temp=(char*)malloc(s->len+t.len);
初始条件:线性表L已存在,
1≤i≤ListLength ( L )+1。
操作结果:在L中第i个位置之前插入新的
数据元素e , L的长度加1。
ListDelete( &L , i , &e ) //删除
初始条件:线性表L已存在且非空,
1≤i≤ListLength( L )。
操作结果:删除L的第i个数据元素,并
while(!StackEmpty(S)) cout<<Pop(S)<<' ';
}
该算法被调用后得到的输出结果为:
答:30、24、16、10、2、10
2.void ABC (BTNode *BT,int &c1,int &c2) {
if (BT !=NULL ) {
ABC(BT->left,c1,c2);
容量分析:
从低地址向高地址增长时,容量为栈顶top的值;
从高地址往低地址存放时,容量为m+1-(栈顶top的值)。
4、设某二叉树的前序遍历序列为:ABCDEFGHI,中序遍历序列为:BCAEDGHFI。(1)试画出该二叉树;(2)画出该二叉树后序线索化图。(3)试画出该二叉树对应的森林。(10分)
(1)(3)(四棵树)
c1++;
if (BT->left==NULL&&BT->right==NULL) c2++;
ABC(BT->right,c1,c2);
}//if
}
该函数执行的功能是什么?
答:该函数的功能是统计,二叉树结点总数,和叶子结点总数。
c1为二叉树结点数,c2为二叉树中叶子结点数
3.在下面的每个程序段中,假定线性表La的类型为List,e的类型为ElemType,元素类型ElemType为int,并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。
s->LLink=p;s->RLink=p->RLink;
Cs->LLink=p; s->RLink=p->RLink;
p->RLink=s;p->RLink->LLink=s;
Ds->LLink=p; s->RLink=p->RLink;
p->RLink->LLink=s; p->RLink=s;
else return 0;//为合数;
}
(1)指出该算法的功能;
(2)该算法的时间复杂度是多少?