华工数据结构作业

一、程序阅读填空

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

一、程序阅读填空

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


相关内容

  • 2015华工网络教育-[建设法规]作业题-答案
  • 2015华工网络教育-<建设法规>作业题-答案 <建设法规>作业题 一.选择题 1. ( B )是工程建设活动的起点,也是工程建设得以进行的必备条件 A.项目建议书 B.投资意向 C.可行性研究 D.审批立项 2. 项目建议书是投资机会分析结果文字化后的( A ),以方便投资 ...

  • 经济学原理随堂作业答案(2015华工)
  • 经济学原理 第二章 生产什么? 1. 10.某种商品的边际效用( ). A.是消费该商品产生的总效用与消费其他商品的总效用之比 B.等于该商品的价格 C.是消费该商品产生的总效用与该商品的数量之比 D.是每增加一单位某种商品的消费所带来的效用增量 参考答案:D 2. 11. 边际效用递减意味着:( ...

  • 华工科技股票筹资案例分析
  • 内容摘要作为财务管理最重要的的两大任务,筹资和投资是相互依存,相互关联的. 华工科技产业股份有限公司是华中地区第一家由高校产业重组上市的高科技公 司.作为一家高新技术企业,其经营风险是很大的,一旦决策失误,就会全盘皆 输,因此决策性的制定必须慎之又慎.在 2000 年的筹资决策投资决策中,华中 科技 ...

  • 6.1企业研究开发活动说明书-参考4
  • 深圳市XXXXX有限公司 研究开发情况介绍 第一部分 公司简介 深圳市XXXXX有限公司成立于2008年12月1日,是一家民营企业,地址位于深圳市XXXXXX,建筑面积1780 平方米,其中净化生产车间面积900 平方米,化库房面积300平方米,办公区域为400平方米.公司注册资金为800万元,其中 ...

  • 讽刺打油诗
  • 社会百态 说法大翻 如今的同志称"哥们" ,如今的官员叫"老板" : 满城的女子称"小姐" ,满街的商贩叫"大款" : 冲澡就叫"洗桑那&qu ...

  • 华人与拉丁美洲
  • 华人与拉丁美洲 中国人民和拉丁美洲人民之间的友谊源远流长.在中国 和拉丁美洲国家关系史中,华侨和华人占有重要地位,拉美 华侨和华人对于促进中国和拉美国家之间的友好往来.增进 相互了解起了桥梁和纽带作用. 拉美华侨的先驱--"马尼拉华人" 中国人自何时起进入拉美?中外学者对此一直有 ...

  • 华工微机8255实验代码
  • 一.实验目的 掌握8255方式0的工作原理及使用方法. 二.实验内容 1.实验电路如图20,8255C口接逻辑电平开关K0-K7,A口接LED显示电路L0-L7. 2. 编程从8255C口输入数据,再从A口输出. 三.编程提示 1.8255控制寄存器端口地址 A口的地址 C口的地址 288H 28A ...

  • 关于举行2013年秋季田径运动会的通知
  • 广州华夏职业学院 关于举办2013年秋季田径运动会的通知 各系: 为进一步加强学院体育工作,增强大学生的体质,提高学生的运动水平,引导学生全面发展,培养团结协作精神,增强凝聚力,展现我院大学生的精神面貌,根据我院实际情况,经学院研究决定,于2013年11月14日--11月15日在学院田径场举行华夏职 ...

  • 2011文化节闭幕式晚会策划书最终版
  • 第十六届"金秋木棉"研究生文化节-- "欢庆中国,激情华园" 第十六届文化节闭幕式晚会 活动策划书 主办单位:华南理工大学研究生团委.研究生会 承办单位:工商管理学院团总支.研分会 轻工与食品学院团总支.研分会 电力学院团总支.研分会 2009年10月17日 ...