2017 数据结构作业

1、一、程序阅读填空 (数据结构)1. 在顺序表中第 i 个位置插入新元素 xtemplate int SeqList:Insert (Type & x, int i) if (ilast+1|last=MaxSize-1) return 0; /插入不成功 else last+; for( _ int j=MaxSize-1_;ji;j-) _ dataj+1=dataj_; datai = x; return 1; /插入成功 2. 直接选择排序的算法 template void SelectSort(datalist & list) for(int i=0; ilist.CurrentSiz

2、e-1; i+) _ SelectExchange(list, i)_; template viod SelectExchange(datalist & list, const int i)int k = i; for(int j=i+1;j list.CurrentSize;j+)if(list.Vectorj.getKey()list.Vectork.getKey()_ k=j_;/当前具有最小关键码的对象 if(k!=i) Swap(list.Vectori, list.Vectork); /交换3、 删去链表中除表头结点外的所有其他结点template void List : Make

3、Empty ( ) ListNode *q; while (firstlink!=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 = high ) _ m

4、id=(low+high)/2_; if ( Elementmid.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”表满，不能插入！（上溢）n”; return 1; if( i=maxsize ) coutn;j=i;j-)L-dataj=L-dataj-1; /节点后移 L-dataj=x ; /插入xL-n+; /修改表长Re

5、turn 1; /插入成功6、直接选择排序的算法void SelectSort( list R, int n ) int i, j, k; for (i=1; i=n-1;i+) /n-1趟排序 k=i ; for(j=i+1;j=n,j+) /在当前无序区中找键值最小的记录Rk if(Rj.keyRk.key) k=j ;if(k!=i) R0=Ri; Ri=Rk; Rk=R0;二、简答题1. 线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点？答：顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下 标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定

6、义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序(没有规定元素进栈顺序)，平均需要移动一半(或近一半)元素，修改效率不高。 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。2. 设有一个输入数据的序列是46,25,78, 62, 12, 37, 70, 29，试画出从空树起，逐个输入各个数据而生成的

7、二叉搜索树。答： 按顺序逐个输入 3.用广义表的带表头结点的存储表示法表示下列集合。A = ( )B = (6, 2)C = (a,( 5, 3, x)D = (B, C, A)E = (B, D)答：4.上图所示为一有向图，请给出该图的下述要求： （1）给出每个顶点的入度和出度；（2）以结点3为起始结点，分别画出该图的一个深度优先生成树和一个宽度优先生成树；（3）给出该图的邻接矩阵；（4）给出该图的邻接表；答：（1）顶点 入度 出度（2）如下图（3）邻接矩阵如下：（4）邻接表如下：5. 对于如上图所示的有向图，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点出

8、发进行广度优先搜索所得到的广度优先生成树； 答：(1) 以顶点为根的深度优先生成树（不唯一）： （2）以顶点 为根的广度优先生成树：6.已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。先序序列_BC_EF_中序序列BDE_AG_H后序序列_DC_GH_A答：后序最后一个是A，所以A是先序的第一个得到： 先序序列 ABC_EF_中序序列 BDE_AG_H 后序序列 _DC_GH_A先序的第二个元素是B，所以B是A的左子树根节点 由中序B在最前，知道其他元素都在B的右子树上 所以，后序序列为(DE_)B(G_H)A，对比已有的后序序列_DC_GH_A 得后序序列

9、为：EDCBGHFA，中序序列为：BDECAGFH 先序序列 ABC_EF_ 中序序列 BDECAGFH 后序序列 EDCBGHFA 所以，二叉树为：7分析下列两个程序段的运行时间（时间复杂度）。void mystery (int n) int i, j, k; for (i =1; i n; i+) for (j = i+1; j = n; j+) for (k = 1; k= j; k+);void odd (int n) int i, j, x = 0, y = 0; for (i =1; i = n; i+) if odd(i) for(j = i; j = n; j+) x+; fo

10、r( j = 1; j = i; j+) y+; 答：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 第