数据结构第一次至第四次作业答案.pdfVIP

第一次作业答案

填空题：

1、已知栈的基本操作函数：

intInitStack(SqStack*S);//构造空栈

intStackEmpty(SqStack*S);//判断栈空

intPush(SqStack*S,ElemTypee);//入栈

intPop(SqStack*S,ElemType*e);//出栈

函数conversion实现十进制数转换为八进制数，请将函数补充完整。

voidconversion(){

InitStack(S);

N);

while(N){

Push(S,N%8);

N=N/8;

}

while(!StackEmpty(S)){

Pop(S,e);

}

}//conversion

2.设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为

11，则队列中元素的个数为(615)。

3.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q=p-next;

p-next=(q-next)

4.一个算法的效率可分为(时间)效率和（空间）效率。

5.数据结构被形式地定义为（D,R），其中D是（数据元素）的有限集合，R是D上的（关

系）有限集合。

6.下面程序段的时间复杂度是（0（m*n））

for(i=0;im;i++)

for(j=0;jn;j++)

a[i][j]=i*j;

选择题：B判断题：错误正确错误

单选题：ADB多选题：ACDACDCD

第二次作业答案

选择题：ADBBCB判断题：错误错误

主观题：

3、广义表A=((a),a)的表头是（a）

()

4、稀疏矩阵一般的压缩存储方法有三元组和（十字链表）两种。

5、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序

存放在一维数组R[1..N]中，若结点R有右孩子，则其右孩子是R[2i+1]。

6、如果从无向图的任一顶点出发进行一次深度优先有哪些信誉好的足球投注网站即可访问所有顶点，

则该图一定是连通图。

7、n个顶点的连通图至少有n-1条边。

8、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半

查找55需要比较（1）次

9、对一棵二叉排序树按（中序）遍历，可得到结点值从小到大的排列序列。

10、一个序列中有10000个元素，若只想得到其中前10个最小元素，则最

好采用（堆排序）方法。

第三次作业答案

BCC

论述题：

1.

答：共计14种，分别是：1234，1243，1324，1342，1432，2134，2143，

2341，2314，2431，3214，3241，3421，4321。

主观题答案：

答：

1、①全进之后再出情况，只有1种：4，3，2，1

②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4

③进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,4

2,1,4,32,1,3,4

④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,

2,3,41,2,4,3

2、先序遍历：BEFCGDH中序遍历：FEBGCHD后序遍历:FEHGDCB

3、DLR(liuyu*root)/*中序遍历递归函数*/

{if(root!=NULL)

{if((root-lchild==NULL)(root-rchild==NULL)){sum++;{if((root-lchil