马昱春数据结构作业【华工数据结构作业】
一、程序阅读填空
1. 在顺序表中第 i 个位置插入新元素 x
template int SeqList::Insert (Type & x, int i){
if (ilast+1||last==MaxSize-1) return 0; //插入不成功
else {
last++;
for( _____ int j=MaxSize-1___________________;j>i;j--)
__________ data[j+1]=data[j]__________________;
data[i] = x;
return 1; //插入成功
}
}
2. 直接选择排序的算法
template void SelectSort(datalist & list)
{ for(int i=0; i
template viod SelectExchange(datalist & list, const int i){
int k = i;
for(int j=i+1;j
if(list.Vector[j].getKey()
___ k=i __________________;//当前具有最小关键码的对象
if(k!=i) Swap(list.Vector[i], list.Vector[k]); //交换
}
3、 删去链表中除表头结点外的所有其他结点
template void List :: MakeEmpty ( ) {
ListNode *q;
while (first→link!=NULL){
_________ q=first->link _________________;
________ first->link=q->link __________________;
//将表头结点后第一个结点从链中摘下
delete q; //释放它
}
last = first; //修改表尾指针
}
4、基于有序顺序表的折半搜索递归算法（Element 为有序顺序表）
template int orderedList ::
BinarySearch(const Type & x, const int low, const int high)const
{
int mid = -1;
if ( low
______ mid=(low+high)/2____________________;
if ( Element[mid].getKey( )
mid = BinarySearch (___x,mid+1,high________________________);
else if ( Element[mid].getKey( ) > x )
mid = BinarySearch ( x, low, mid -1 );
}
return mid;
}
5、在顺序表中第 i 个位置插入新元素 x 。
int insert(sqlist *L, datatype x, int i)
{ int j;
if (L->n==maxsize) {cout
if( ) {coutn;j>=i;j--)
L->data[j]=L->data[j-1]; //节点后移
//插入x
L->n++; //修改表长
Return 1; //插入成功
}
6、直接选择排序的算法
void SelectSort( list R, int n )
{ int i, j, k;
for (i=1; i
;
for(j=i+1;j
if(R[j].key
if(k!=i) {R[0]=R[i]; R[i]=R[k]; R[k]=R[0];}
}
}
二、简答题
1. 线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点？
答：顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标) 直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序(没有规定元素进栈顺序) ，平均需要移动一半(或近一半) 元素，修改效率不高。 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。
2. 设有一个输入数据的序列是{46,25,78, 62, 12, 37, 70, 29}，试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
答：按顺序逐个输入
46
/ \
25 78
/ \ /
12 37 62
/ \
29 70
3. 用广义表的带表头结点的存储表示法表示下列集合。
A = ( )
B = (6, 2)
C = (‘a ’,( 5, 3, ‘
x ’))
D = (B, C, A)
E = (B, D)
答：
4. 上图所示为一有向图，请给出该图的下述要求：
（1）给出每个顶点的入度和出度；
（2）以结点3为起始结点，分别画出该图的一个深度优先生成树和一个宽度优先生成树；
（3）给出该图的邻接矩阵；
（4）给出该图的邻接表；
答：（1）顶点 入度 出度
1 3 0
2 2 2
3 1 2
4 1 3
5 2 1
6 2 3
（2）
（3）邻接矩阵
（4）邻接表
5. 对于如上图所示的有向图，试写出：
(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树；
(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；
答：(1) 以顶点①为根的深度优先生成树（不唯一）：② ③ ④ ⑤ ⑥
或
(2) 以顶点②为根的广度优先生成树：
②
⑤
6. 已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。
先序序列 _BC_EF__
中序序列 BDE_AG_H
后序序列 _DC_GH_A
答：后序最后一个是A ，所以A 是先序的第一个得到：
先序序列 ABC_EF__
中序序列 BDE_AG_H
后序序列 _DC_GH_A
_____________(A)____________
____________/___\___________
________(BDE_)_(G_H)________
先序的第二个元素是B ，所以B 是A 的左子树根节点
由中序B 在最前，知道其他元素都在B 的右子树上
所以，后序序列为(DE_)B(G_H)A，对比已有的后序序列_DC_GH_A
得后序序列为：EDCBGHFA ，中序序列为：BDECAGFH
先序序列 ABC_EF__
中序序列 BDECAGFH
后序序列 EDCBGHFA
所以，二叉树为：
_____________(A)_____________
____________/___\____________
__________(B)____(F)_________
___________\_____/_\_________
___________(C)_(G)_(H)_______
___________/_________________
_________(D)_________________
__________\__________________
__________(E)________________
7．分析下列两个程序段的运行时间（时间复杂度）。
void mystery (int n)
{ int i, j, k;
for (i =1; i
for (j = i+1; j
for (k = 1; k
}
答：O(n3)
void odd (int n)
{ int i, j, x = 0, y = 0;
for (i =1; i
if odd(i)
{ for(j = i; j
for( j = 1; j
}
}
答：O(n2)
8. 有一组数据：25，50，70，21，4，18，100，43，7，12。现采用汽泡排序算法进行排序，写出每趟排序的结果，并标明第一趟数据的移动情况。
答：第一趟： 25，50，70，21，4，18，100，43，7，12
25，50，70，21，4，18，100，43，7，12
25，50，21，70，4，18，100，43，7，12
25，50，21，4，70，18，100，43，7，12
25，50，21，4，18，70，100，43，7，12
25，50，21，4，18，70，100，43，7，12
25，50，21，4，18，70，43，100，7，12
25，50，21，4，18，70，43，7，100，12
25，50，21，4，18，70，43，7，12，100
第二趟 25，21，4，18，50，43，7，12，70，100
第三趟 21，4，18，25，43，7，12，50，70，100
第四趟 4，18，21，25，7，12，43，50，70，100
第五趟 4，18，21，7，12，25，43，50，70，100
第六趟 4，18，7，12，21，25，43，50，70，100
第七趟 4，7，12，18，21，25，43，50，70，100