题目

算法设计题(1)试以单链表[1][1]为存储结构,实现简单选择排序[2][2]算法。void LinkedListSelectSort(LinkedList head)/本算法一趟找出一个关键字最小的结点[3][3],其数据和当前结点进行交换;若要交换指针,则须记下/当前结点和最小结点的前驱指针p=head->next;while(p!=null)(q=p->next; r=p; /设r是指向关键字最小的结点的指针while (q!=null){if(q->datadata) r=q;q:=q->next;)if(r!=p) r->data<-->p->data;p=p->next;}(2)有n个记录存储在带头结点的双向链表[4][4]中,现用双向冒泡排序[5][5]法对其按上升序进行排序,请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。typedef struct node( ElemType data;struct node *prior,*next;)node,*DLinkedList;void TwoWayBubbleSort(DLinkedList la)/对存储在带头结点的双向链表la中的元素进行双向起泡排序。(int exchange=1; / 设标记DLinkedList p,temp,tail;head=la /双向链表头,算法过程中是向下起泡的开始结点tail=null; /双向链表尾,算法过程中是向上起泡的开始结点while (exchange){p=head->next; /p是工作指针,指向当前结点exchange=0; /假定本趟无交换while (p->next!=tail) / 向下(右)起泡,一趟有一最大元素沉底if (p->data>p->next->data) /交换两结点指针,涉及6条链{temp=p->next; exchange=1;/有交换p->next=temp->next;temp->next->prior=p /先将结点从链表[6][6]上摘下temp->next=p; p->prior->next=temp; /将temp插到p结点前temp->prior=p->prior; p->prior=temp;)else p=p->next; /无交换,指针后移tail=p; /准备向上起泡p=tail->prior;while (exchange p->prior!=head) /向上(左)起泡,一趟有一最小元素冒出if (p->dataprior->data) /交换两结点指针,涉及6条链(temp=p->prior; exchange=1; /有交换p->prior=temp->prior;temp->prior->next=p; /先将temp结点从链表上摘下temp->prior=p; p->next->prior=temp; /将temp插到p结点后(右)temp->next=p->next; p->next=temp;)else p=p->prior; /无交换,指针前移head=p; /准备向下起泡}/ while (exchange)} /算法结束(3)设有顺序放置的n个桶,每个桶中装有一粒砾石,每粒砾石的颜色是红,白,蓝之一。要求重新安排这些砾石,使得所有红色砾石在前,所有白色砾石居中,所有蓝色砾石居后,重新安排时对每粒砾石的颜色只能看一次,并且只允许交换操作来调整砾石的位置。[题目分]利用快速排序[7][7]思想决。由于要求“对每粒砾石的颜色只能看一次”,设3个指针i,j和k,分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始,从右向左搜索,若该元素是兰色,则元素不动,指针左移(即k-1);若当前元素是红色砾石,分i>=j(这时尚没有白色砾石)和i为方便处理,将三种砾石的颜色用整数1、2和3表示。void QkSort(rectype r[],int n)/ r为含有n个元素的线性表[8][8],元素是具有红、白和兰色的砾石,用顺序存储[9][9]结构存储,/本算法对其排序,使所有红色砾石在前,白色居中,兰色在最后。(int i=1,j=1,k=n,temp;while (k!=j){while (r[k].key==3) k--;/ 当前元素是兰色砾石,指针左移if (r[k].key==1) / 当前元素是红色砾石if (i>=j){temp=r[k];r[k]=r[i];r[i]=temp; i++;)/左侧只有红色砾石,交换r[k]和r[i]else (temp=r[j];r[j]=r[i];r[i]=temp; j++;/左侧已有红色和白色砾石,先交换白色砾石到位temp=r[k];r[k]=r[i];r[i]=temp; i++;/白色砾石(i所指)和待定砾石(j所指)) /再交换r[k]和r[i],使红色砾石入位。if (r[k].key==2)if (i<=j) ( temp=r[k];r[k]=r[j];r[j]=temp; j++;)/ 左侧已有白色砾石,交换r[k]和r[j]else ( temp=r[k];r[k]=r[i];r[i]=temp; j=i+1;)/i、j分别指向红、白色砾石的后一位置}/whileif (r[k]==2) j++; /* 处理最后一粒砾石else if (r[k]==1) ( temp=r[j];r[j]=r[i];r[i]=temp; i++; j++; )/最后红、白、兰色砾石的个数分别为: i-1;j-i;n-j+1}/结束QkSor算法[算法讨论]若将j(上面指向白色)看作工作指针,将r[1..j-1]作为红色,r[j..k-1]为白色,r[k..n]为兰色。从j=1开始查看,若r[j]为白色,则j=j+1;若r[j]为红色,则交换r[j]与r[i],且j=j+1,i=i+1;若r[j]为兰色,则交换r[j]与r[k];k=k-1。算法进行到j>k为止。算法片段如下:int i=1,j=1,k=n;while(j<=k)if (r[j]==1) /当前元素是红色(temp=r[i]; r[i]=r[j]; r[j]=temp; i++;j++; )else if (r[j]==2) j++; /当前元素是白色else /(r[j]==3 当前元素是兰色(temp=r[j]; r[j]=r[k]; r[k]=temp; k--; )对比两种算法,可以看出,正确选择变量(指针)的重要性。(4)编写算法,对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前,要求:采用顺序存储结构,至多使用一个记录的辅助存储空间;② 算法的时间复杂度为O(n)。(5)借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..n]中。若查找成功,则输出该记录在r数组中的位置及其值,否则显示“not find”信息。请简要说明算法思想并编写算法。[题目分]把待查记录看作枢轴,先由后向前依次比较,若小于枢轴,则从前向后,直到查找成功返回其位置或失败返回0为止。int index (RecType R[],int l,h,datatype key)( int i=l,j=h;while (i{ while (i<=j R[j].key>key) j--;if (R[j].key==key) return j;while (i<=j R[i].keyif (R[i].key==key) return i;)printf(“Not find”) ; return 0;}/index(6)有一种简单的排序算法,叫做计数排序。这种排序算法对一个待排序的表进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。 给出适用于计数排序的顺序表定义;② 编写实现计数排序的算法; 对于有n个记录的表,关键字比较次数是多少? 与简单选择排序相比较,这种方法是否更好?为什么?typedef struct( int key; datatype info)RecTypevoid CountSort(RecType a[],b[],int n) /计数排序算法,将a中记录排序放入b中( for(i=0;i{ for(j=0,cnt=0;jif(a[j].keyb[cnt]=a[i];)}/Count_Sort(3) 对于有n个记录的表,关键码比较n次。(4) 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间;而这种方法比较次数是n,且需要另一数组空间。[算法讨论]因题目要求“针对表中的每个记录,扫描待排序的表一趟”,所以比较次数是n2次。若限制“对任意两个记录之间应该只进行一次比较”,则可把以上算法中的比较语句改为:for(i=0;ifor(i=0;ifor(j=i+1;jif(a[i].keyB.(100,120,110,130,80, 60, 90)C.(100,60, 80, 90, 120,110,130)D.(100,80, 60, 90, 120,130,110)(8)在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( )型调整以使其平衡。A. LL B.LR C.RL D.RR B. -树的说法错误的是( )。 C. 根结点至多有m棵子树 D. 所有叶子都在同一层次上 E. 非叶结点至少有m/2 (m为偶数)或m/2+1(m为奇数)棵子树 F. 根结点中的数据是有序的 G. -和B+树的叙述中,不正确的是( )。 B-树和B+树都是平衡的多叉树 B-树和B+树都可用于文件的索引结构 B-树和B+树都能有效地支持顺序检索 B-树和B+树都能有效地支持随机检索 -树是一棵( )。 m叉排序树 m叉平衡排序树 m-1叉平衡排序树 m+1叉平衡排序树 (12)下面关于哈希查找的说法,正确的是( )。 哈希函数构造的越复杂越好,因为这样随机性好,冲突小 除留余数法是所有哈希函数中最好的 不存在特别好与坏的哈希函数,要视情况而定 哈希表的平均查找长度有时也和记录总数有关 (13)下面关于哈希查找的说法,不正确的是( )。 采用链地址法处理冲突时,查找一个元素的时间是相同的 采用链地址法处理冲突时,若插入规定总是在链首,则插入任一个元素的时间是相同的 用链地址法处理冲突,不会引起二次聚集现象 用链地址法处理冲突,适合表长不确定的情况 H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的元素加到表中,用二次探测法决冲突,则放入的位置是( )。 8 3 5 9 (15)采用线性探测法处理冲突,可能要探测多个位置,在查找成功的情况下,所探测的这些位置上的关键字 ( )。 不一定都是同义词 一定都是同义词 一定都不是同义词 都相同

算法设计题

(1)试以单链表[1][1]为存储结构,实现简单选择排序[2][2]算法。

void LinkedListSelectSort(LinkedList head)

//本算法一趟找出一个关键字最小的结点[3][3],其数据和当前结点进行交换;若要交换指针,则须记下

//当前结点和最小结点的前驱指针

p=head->next;

while(p!=null)

{q=p->next; r=p; //设r是指向关键字最小的结点的指针

while (q!=null)

{if(q->datadata) r=q;

q:=q->next;

}

if(r!=p) r->data<-->p->data;

p=p->next;

}

(2)有n个记录存储在带头结点的双向链表[4][4]中,现用双向冒泡排序[5][5]法对其按上升序进行排序,请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。

typedef struct node

{ ElemType data;

struct node *prior,*next;

}node,*DLinkedList;

void TwoWayBubbleSort(DLinkedList la)

//对存储在带头结点的双向链表la中的元素进行双向起泡排序。

{int exchange=1; // 设标记

DLinkedList p,temp,tail;

head=la //双向链表头,算法过程中是向下起泡的开始结点

tail=null; //双向链表尾,算法过程中是向上起泡的开始结点

while (exchange)

{p=head->next; //p是工作指针,指向当前结点

exchange=0; //假定本趟无交换

while (p->next!=tail) // 向下(右)起泡,一趟有一最大元素沉底

if (p->data>p->next->data) //交换两结点指针,涉及6条链

{temp=p->next; exchange=1;//有交换

p->next=temp->next;temp->next->prior=p //先将结点从链表[6][6]上摘下

temp->next=p; p->prior->next=temp; //将temp插到p结点前

temp->prior=p->prior; p->prior=temp;

}

else p=p->next; //无交换,指针后移

tail=p; //准备向上起泡

p=tail->prior;

while (exchange p->prior!=head) //向上(左)起泡,一趟有一最小元素冒出

if (p->dataprior->data) //交换两结点指针,涉及6条链

{temp=p->prior; exchange=1; //有交换

p->prior=temp->prior;temp->prior->next=p; //先将temp结点从链表上摘下

temp->prior=p; p->next->prior=temp; //将temp插到p结点后(右)

temp->next=p->next; p->next=temp;

}

else p=p->prior; //无交换,指针前移

head=p; //准备向下起泡

}// while (exchange)

} //算法结束

(3)设有顺序放置的n个桶,每个桶中装有一粒砾石,每粒砾石的颜色是红,白,蓝之一。要求重新安排这些砾石,使得所有红色砾石在前,所有白色砾石居中,所有蓝色砾石居后,重新安排时对每粒砾石的颜色只能看一次,并且只允许交换操作来调整砾石的位置。

[题目分]利用快速排序[7][7]思想决。由于要求“对每粒砾石的颜色只能看一次”,设3个指针i,j和k,分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始,从右向左搜索,若该元素是兰色,则元素不动,指针左移(即k-1);若当前元素是红色砾石,分i>=j(这时尚没有白色砾石)和i

为方便处理,将三种砾石的颜色用整数1、2和3表示。

void QkSort(rectype r[],int n)

// r为含有n个元素的线性表[8][8],元素是具有红、白和兰色的砾石,用顺序存储[9][9]结构存储,

//本算法对其排序,使所有红色砾石在前,白色居中,兰色在最后。

{int i=1,j=1,k=n,temp;

while (k!=j)

{while (r[k].key==3) k--;// 当前元素是兰色砾石,指针左移

if (r[k].key==1) // 当前元素是红色砾石

if (i>=j){temp=r[k];r[k]=r[i];r[i]=temp; i++;}

//左侧只有红色砾石,交换r[k]和r[i]

else {temp=r[j];r[j]=r[i];r[i]=temp; j++;

//左侧已有红色和白色砾石,先交换白色砾石到位

temp=r[k];r[k]=r[i];r[i]=temp; i++;

//白色砾石(i所指)和待定砾石(j所指)

} //再交换r[k]和r[i],使红色砾石入位。

if (r[k].key==2)

if (i<=j) { temp=r[k];r[k]=r[j];r[j]=temp; j++;}

// 左侧已有白色砾石,交换r[k]和r[j]

else { temp=r[k];r[k]=r[i];r[i]=temp; j=i+1;}

//i、j分别指向红、白色砾石的后一位置

}//while

if (r[k]==2) j++; /* 处理最后一粒砾石

else if (r[k]==1) { temp=r[j];r[j]=r[i];r[i]=temp; i++; j++; }

//最后红、白、兰色砾石的个数分别为: i-1;j-i;n-j+1

}//结束QkSor算法

[算法讨论]若将j(上面指向白色)看作工作指针,将r[1..j-1]作为红色,r[j..k-1]为白色,r[k..n]为兰色。从j=1开始查看,若r[j]为白色,则j=j+1;若r[j]为红色,则交换r[j]与r[i],且j=j+1,i=i+1;若r[j]为兰色,则交换r[j]与r[k];k=k-1。算法进行到j>k为止。

算法片段如下:

int i=1,j=1,k=n;

while(j<=k)

if (r[j]==1) //当前元素是红色

{temp=r[i]; r[i]=r[j]; r[j]=temp; i++;j++; }

else if (r[j]==2) j++; //当前元素是白色

else //(r[j]==3 当前元素是兰色

{temp=r[j]; r[j]=r[k]; r[k]=temp; k--; }

对比两种算法,可以看出,正确选择变量(指针)的重要性。

(4)编写算法,对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前,要求:

采用顺序存储结构,至多使用一个记录的辅助存储空间;

② 算法的时间复杂度为O(n)。

(5)借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..n]中。若查找成功,则输出该记录在r数组中的位置及其值,否则显示“not find”信息。请简要说明算法思想并编写算法。

[题目分]把待查记录看作枢轴,先由后向前依次比较,若小于枢轴,则从前向后,直到查找成功返回其位置或失败返回0为止。

int index (RecType R[],int l,h,datatype key)

{ int i=l,j=h;

while (i

{ while (i<=j R[j].key>key) j--;

if (R[j].key==key) return j;

while (i<=j R[i].key

if (R[i].key==key) return i;

}

printf(“Not find”) ; return 0;

}//index

(6)有一种简单的排序算法,叫做计数排序。这种排序算法对一个待排序的表进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。

给出适用于计数排序的顺序表定义;

② 编写实现计数排序的算法;

对于有n个记录的表,关键字比较次数是多少?

与简单选择排序相比较,这种方法是否更好?为什么?

typedef struct

{ int key; datatype info}RecType

void CountSort(RecType a[],b[],int n) //计数排序算法,将a中记录排序放入b中

{ for(i=0;i

{ for(j=0,cnt=0;j

if(a[j].key

b[cnt]=a[i];

}

}//Count_Sort

(3) 对于有n个记录的表,关键码比较n次。

(4) 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间;而这种方法比较次数是n,且需要另一数组空间。

[算法讨论]因题目要求“针对表中的每个记录,扫描待排序的表一趟”,所以比较次数是n2次。若限制“对任意两个记录之间应该只进行一次比较”,则可把以上算法中的比较语句改为:

for(i=0;i

for(i=0;i

for(j=i+1;j

if(a[i].key

B.(100,120,110,130,80, 60, 90)

C.(100,60, 80, 90, 120,110,130)

D.(100,80, 60, 90, 120,130,110)

(8)在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( )型调整以使其平衡。

A. LL B.LR C.RL D.RR
B. -树的说法错误的是( )。
C. 根结点至多有m棵子树
D. 所有叶子都在同一层次上
E. 非叶结点至少有m/2 (m为偶数)或m/2+1(m为奇数)棵子树
F. 根结点中的数据是有序的
G. -和B+树的叙述中,不正确的是( )。
B-树和B+树都是平衡的多叉树
B-树和B+树都可用于文件的索引结构
B-树和B+树都能有效地支持顺序检索
B-树和B+树都能有效地支持随机检索
-树是一棵( )。
m叉排序树
m叉平衡排序树
m-1叉平衡排序树
m+1叉平衡排序树
(12)下面关于哈希查找的说法,正确的是( )。
哈希函数构造的越复杂越好,因为这样随机性好,冲突小
除留余数法是所有哈希函数中最好的
不存在特别好与坏的哈希函数,要视情况而定
哈希表的平均查找长度有时也和记录总数有关
(13)下面关于哈希查找的说法,不正确的是( )。
采用链地址法处理冲突时,查找一个元素的时间是相同的
采用链地址法处理冲突时,若插入规定总是在链首,则插入任一个元素的时间是相同的
用链地址法处理冲突,不会引起二次聚集现象
用链地址法处理冲突,适合表长不确定的情况
H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的元素加到表中,用二次探测法决冲突,则放入的位置是( )。
8
3
5
9
(15)采用线性探测法处理冲突,可能要探测多个位置,在查找成功的情况下,所探测的这些位置上的关键字 ( )。
不一定都是同义词
一定都是同义词
一定都不是同义词
都相同

题目解答

答案

C RL D 根结点中的数 和 B+ 树都能有效 m 叉平衡排序树 C ． 不存在特别好与坏的哈希 址法处理冲突时，查找一个元素的时 D ． 9 都是同义词