华工数据结构作业

一、程序阅读填空

1. 在顺序表中第 i 个位置插入新元素 x

template int SeqList::Insert (Type & x, int i){ if (i<0||i>last+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< list.CurrentSize;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 <= high ) {

______ mid=(low+high)/2____________________; if ( Element[mid].getKey( ) < x )

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<<”表满，不能插入！（上溢）\\n”; return –1; }

if( i<0||i>=maxsize ) {cout<<”非法插入位置！\\n”; return 0;} for(j=L->n;j>=i;j--)

L->data[j]=L->data[j-1]; //节点后移 L->data[j]=x ; //插入x L->n++; //修改表长 Return 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++) //在当前无序区中找键值最小的记录R[k] if(R[j].key

二、简答题

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