阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot时，采用从left、right和mid=[(left+right)/2]中取中间值，并交换到right位置的办法。数组a存放待排序的一组记录，数据类型为T，left和right是待排序子区间的最左端点和最右端点。void quicksort (int a[], int left, int right) {int temp;if (left＜right) {hat p

使用VC6打开考生文件夹下的工程test41_3。此工程包含一个test41_3.cpp，其中定义了类Rectangle，但该类的定义并不完整。请按要求完成下列操作，将程序补充完整。

(1)定义类Rectangle的私有数据成员left，top和fight，bottom，它们都是int型的数据。请在注释“//**1**”之后添加适当的语句。

(2)添加类Rectangle的带四个int型参数1、t、r、b的构造函数的声明，并使这四个参数的默认值均为0，请在注释“//**2**”之后添加适当的语句。

(3)添加类Rectangle的成员函数SetTop()参数为int型的t，作用为把t的值赋给类的数据成员top，添加类Rectangle的成员函数SetBottom()参数为int型的t，作用为把t的值赋给类的数据成员bottom，请在注释“//**3**”之后添加适当的语句。

(4)完成派生类Rectangle的成员函数Show()的定义，使其以格式“right-bottom point is(right，bottom)”输出，请在注释“//**4**”之后添加适当的语句。

源程序文件test41_3.cpp清单如下：

include ＜iostream.h＞

class Rectangle

{

// ** 1 **

int right, bottom;

public:

// ** 2 **

～ Rectangle(){};

void Assign(int 1, int t, int r, int b);

void SetLeft(int t){left = t;}

void SetRight(int t){right = t;}

// ** 3 **

void SetBottom(int t){bottom = t;}

void Show();

};

Rectangle::Rectangle(int 1, int t, int r, int b)

{

left = 1; top = t;

right = r; bottom = b;

}

void Rectangle::Assign(int 1, int t, int r, int b)

{

left = 1; top = t;

right = r; bottom = b;

}

void Rectangle::Show()

{

cout＜＜"left-top point is ("＜＜left＜＜","＜＜top＜＜")"＜＜'\n';

// ** 4 **

}

void main()

{

Rectangle rect;

rect.Show();

rect.Assign(100,200,300,400);

rect.Show();

}

阅读下列说明、流程图和算法，将应填(n)处的字句写在对应栏内。

[说明]

下面的流程图(如图3所示)用N - S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为 low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：

[流程图]

[算法说明]

将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int hieh)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。

[算法]

void sort(int A[]，int L，int H) {

if (L＜H) {

k=p(A，L，R)； //p()返回基准数在数组A中的下标

sort((4))； //小于基准敷的元素排序

sort((5))； //大于基准数的元素排序

}

}

从字符串S("abcdefg") 中返回子串B("cd") 的正确表达式是______。

A．Mid(S,3,2)

B． Right(Left(S,4) ,2)

C． Left(Right(S,5) ,2)

D． 以上都可以

从字符串S(“abcdefg”)中返回子串B(“cd”)的正确表达是( )。

A．Mid(S，3，2)

B．Right(Left(S，4)，2)

C．Left(Right(S，5)，2)

D．以上都可以

从字符串S（＂abcdefg＂）返回子串B（＂cd＂）的正确表达式为（ ）。A．Mid（S，3，2）B．Right（Left（S，4），2）C．Left（Right（S，5）2）D．以上都可以

阅读以下说明和C++程序，将应填入(n)处的字句写在对应栏内。

【说明】以下程序实现了二叉树的结点删除算法，若树中存在要删除的结点，则删除它，否则返回。 FindNode ()函数能够在二叉树中找到给定值的结点，并返回其地址和父结点。

【C++程序】

template ＜ class T ＞

void BinSTree ＜ T ＞: :Delete( const T& item)

{

TreeNode ＜ T ＞ * DelNodePtr, * ParNodePtr, * RepNodePtr;

if(( DelNodePtr = FindNode (item,ParNodePtr)) = = NULL)

(1)

if(DelNodePtr→right = = NULL) //被删除结点只有一个子结点的情况

RepNodePtr = DelNodePtr→left;

else if( DelNodePtr→left = = NULL)

(2);

else // 被删除结点有两个子结点的情况

{

TreeNode ＜ T ＞* PofRNodePtr = DelNodePtr;

RepNodePtr = DelNodePtr→left;

while(RepNodePtr→right ! = NULL)

{ //定位左子树的最右结点

PofRNodePtr =RepNodePtr;

RepNodePtr = RepNodePtr→right;

}

if(PofRNodePtr = = DelNodePtr) //左子树没有右子结点

(3);

else //用左子顷的最右结点替换删除的结点

{

(4)

RepNodePtr→left = DelNodePtr→left;

RepNodePtr→right = DelNodePtr→right;

}

}

if (5)//要删除结点是要结点的情况

root = RepNodePtr;

else if ( DelNodePtr→data ＜ ParNodePtr→Data)

ParNodePtr→left = RepNodePtr;

else

ParNodePtr→right =RepNodePtr;

FirstTreeNode ( DelNodePtr ) ;//释放内存资源

size→;

}

阅读下列说明和流程图，将应填入(n)的语句写在对应栏内。

【流程图说明】

下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data, left和right。其查找的方法是：首先与树的根节点的元素值进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。

【算法说明】

【流程图】

将上题的排序二叉树中查找元素的过程用递归的方法实现。其中NODE是自定义类型：

typedef struct node {

int data;

struct node * left;

struct node * right;

}NODE;

【算法】

NODE * SearchSortTree(NODE * tree, int e)

{

if(tree!=NULL)

{

if(tree-＞data＜e)

(4); //小于查找左子树

else if(tree-＞data＜e)

(5); //大于查找左子树

else return tree;

}

return tree;

}

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。 下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下： arr：待排序数组 p,q,r：一个子数组的位置从p到q，另一个子数组的位置从q+1到r begin,end：待排序数组的起止位置 left,right：临时存放待合并的两个子数组 n1,n2：两个子数组的长度 i,j,k：循环变量 mid：临时变量 【C代码】

inciude<stdio.h> inciude<stdlib.h> define MAX 65536 void merge(int arr[],int p,int q,int r) { int *left, *right; int n1,n2,i,j,k; n1=q-p+1; n2=r-q; if((left=(int*)malloc((n1+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } for(i=0;i<n1;i++){ left[i]=arr[p+i]； } left[i]=MAX； for(i=0; i<n2; i++){ right[i]=arr[q+i+1] } right[i]=MAX; i=0; j=0; for(k=p; （1） ; k++) { if(left[i]> right[j]) { （2） ; j++; }else { arr[k]=left[i]； i++； } } } void mergeSort(int arr[],int begin,int end){ int mid; if( （3） ){ mid=(begin+end)/2; mergeSort(arr,begin,mid); （4） ; merge(arr,begin,mid,end); } }

【问题1】 根据以上说明和C代码，填充1-4。 【问题2】 根据题干说明和以上C代码，算法采用了（5）算法设计策略。 分析时间复杂度时，列出其递归式位（6），解出渐进时间复杂度为（7）（用O符号表示）。空间复杂度为（8）（用O符号表示）。 【问题3】 两个长度分别为n1和n2的已经排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为（9）。

●试题二

阅读下列说明、流程图和算法，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

下面的流程图(如图3所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：

【流程图】

图3流程图

【算法说明】

将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。

【算法】

void sort (int A[]， int 1，int H){

if ( L<H){

k=p(A，L，R)；//p()返回基准数在数组A中的下标

sort( (4) )；//小于基准数的元素排序

sort( (5) )；//大于基准数的元素排序

}

}

阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。

【函数】

void QuickSort( int A[ ],int s,int t)

{ int i=s,j=t+1,temp;

int x=A[s];

do{

do i ++ ;while (1);

do j -- ;while(A[j]＞x);

if(i＜j){temp=A[i];(2);(3);}

}while(i＜j);

A[a] =A[j];A[j] =x;

if(s＜i-1) (4);

if(j+1＜t) (5);

}

用SQL语句进行表的查询操作，使用 ()语句。如果要进行分组查询，应使用 ()子句;如果要对查询结果进行排序，要使用 () 子句;查询使用连接操作时，可以使用的外连接方式主要有左连接() ，右连接() ，全连接 () 等几种。

A UPDATE ， ORDER BY， GROUP BY， LEFT JOIN， RIGHT JOIN， FULL JOIN

B SELECT ， GROUP BY， ORDER BY， LEFT JOIN，RIGHT JOIN， FULL JOIN

C SELECT ， ORDER BY ， GROUP BY ， LEFT JOIN， RIGHT JOIN，FULL JOIN

D SELECT ，GROUP BY ， ORDER BY ， RIGHT JOIN， LEFT JOIN， FULL JOIN

阅读以下说明和C语言函数，将应填入(n)处的语句写在对应栏内。

【说明】

本程序从正文文件text.in中读入一篇英文短文，统计该短文中不同单词及出现次数，并按词典编辑顺序将单词及出现次数输出到正文文件word.out中。

程序用一棵有序二叉树存储这些单词及其出现的次数，边读入边建立，然后中序遍历该二叉树，将遍历经过的二叉树上的结点内容输出。

【函数】

include ＜stdio.h＞

include ＜malloc.h＞

include ＜ctype.h＞

include ＜string.h＞

define INF "text.in"

define OUTF "word.our'

typedef struct treenode {

char *word;

int count;

struct treenode *left, *right;

} BNODE;

int getword(FILE *fpt, char *word)

{ char c;

c=fgetc(tpt);

if (c==EOF)

return 0;

while(!(tolower(c)＞= 'a' && tolower(c)＜= 'z'))

{ c=fgetc(fpt);

if (c==EOF)

return 0;

} /* 跳过单词间的所有非字母字符 */

while(tolower(c)＞= 'a' && tolower(c)＜= 'z')

{ *word++=c;

c=fgetc(fpt);

}

*word='\0';

return 1;

}

void binary_tree(BNODE **t, char *word)

{ BNODE *ptr, *p; int compres;

p=NULL;

(1);

while (ptr) /* 寻找插入位置 */

{ compres=strcmp(word, ptr-＞word);/* 保存当前比较结果 */

if (!compres)

{ (2); return;}

else

{ p=ptr;

ptr=compres＞0 ? ptr-＞right: ptr-＞left;

}

}

ptr=(BNODE *)malloc(sizeof(BNODE));

ptr-＞left=ptr-＞right=NULL;

ptr-＞word=(char *)malloc(strlen(word)+1);

strcpy(ptr-＞word, word);

(3);

if (p==NULL)

*t=ptr;

else if (compres＞0)

p-＞right=ptr;

else

p-＞left=ptr;

}

void midorder(FILE *fpt, BNODE *t)

{ if (t==NULL)

return;

midorder(fpt,(4));

fprintf(fpt, "%s %d\n", t-＞word, t-＞count);

midorder(fpt, t-＞right);

}

void main()

{ FILE *fpt; char word[40];

BNODE *root=NULL;

if ((fpt=fopen(INF, "r"))==NULL)

{ printf("Can't open file %s\n", INF);

return;

}

while(getword(fpt, word)==1)

binary_tree((5));

fclose(fpt);

fpt=fopen(OUTF, "w");

if (fpt==NULL)

{ printf("Can't open fife %s\n", OUTF);

return;

}

midorder(fpt, root);

fclose(fpt);

}

阅读下列程序说明和C程序，将应填入程序中(n)处的字句，写在对应栏内。

【程序说明】

本程序先从文件读人各考生的准考证号(设为整型数)及成绩，并将其存放在一棵检索二叉树上，二叉树结点的健值是成绩，每个结点带一链表，链表结点存放取得该成绩的考生的准考证号。然后，程序按中序遍历检索二叉树，从高分到低分输出结果，使每行输出成绩及其取得成绩的考生的准考证号。

【程序】

include ＜ stdio. h ＞

typedef struet idnode {

int id;

struct idnode * next;

} ldNode;

typedef struct marknode I

int mark;

ldNode * head;

struct marknode * left, * right;

} MarkNode;

char fname [ ] = "sp07.dat";

main( )

{ int id, mark;

MarkNode * root = null;

FILE * fp = fopen(fname," r" );

if(!fp) {

printf("file%s open error, \n" , fname);

exit(0);

}

while (!feop(fp)) {

fscanf(fp," %d%d", &id, &mark);

btree(&root, id, mark);

}

fclose(fp);

print(root);

}

btree(MarkNod * * mpptr, int id, int mark)

{ ldNode * ip;

MarkNode *mp = * mpptr;

if (1) {

if (mark==p-＞mark) addldNODE ((2), id);

else if ( mark ＞mp -＞ mark) btree (&top -＞ left, id, mark);

else btree(&mp-＞ right, id, mark);

} else

Imp = ( marknode * ) malloc(sizeo (marknode) );

mp -＞ mark = mark;

mp -＞ left =mp -＞ right = NULL;

(3)

addldNode(&mp -＞ head, id);

(4);

}

}

addldNode(ldNode * * ipp, int id)

{ ldNode * ip = * ipp;

if ((5))addldNode ((6)), id;

else {

ip = (ldNode * )malloc(sizeof(ldNode) );

sp - ＞ id = id;

ip -＞ next = NULL;

(7)

}

}

print(MarkNode * rap)

{ ldNode *ip, *ip0;

if (mp) {

print ( mp -＞ left);

printf(" %6d: \t" ,mp -＞ mark);

ip = mp -＞ head;

while(ip) {

printf(" %6d" ,ip -＞ id);

ip0 =ip;

ip = ip -＞ next;

free (ip0);

}

printf(" \n" ); printf( mp -＞ right); free(mp);

}

}

阅读下列说明、流程图和算法，将应填入(n)处的字句写在对应栏内。

【流程图说明】

下图所示的流程图5.3用N-S盒图形式描述了数组Array中的元素被划分的过程。其划分方法；以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于Array[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。

【算法说明】

将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int Array[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组Ar ray中的下标。递归函数void sort(int Array[]，int L，int H)的功能是实现数组Array中元素的递增排序。

【算法】

void sort(int Array[]，int L，int H){

if (L＜H) {

k=p(Array，L，H)；/*p()返回基准数在数组Array中的下标*/

sort((4))；/*小于基准数的元素排序*/

sort((5))；/*大于基准数的元素排序*/

}

}

阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。

【说明】本程序从正文文件text.in中读入一篇英文短文，统计该短文中不同单词及出现次数，并按词典编辑顺序将单词及出现次数输出到正文文件word．out中。

程序用一棵有序二叉树存储这些单词及其出现的次数，边读入边建立，然后中序遍历该二叉树，将遍历经过的二叉树上的结点的内容输出。

include ＜stdio.h＞

include ＜malloc.h＞

include ＜ctype.h＞

include ＜string.h＞

define INF "text.in"

define OUTF "wotd.out"

typedef struct treenode{

char *word；

int count；

struct treenode *left，*right；

}BNODE

int getword (FILE *fpt，char *word)

{ char c；

c=fgetc (fpt)；

if ( c＝EOF)

return 0；

while(!(tolower(c)＞='a' && tolower(c)＜='z'))

{ c=fgetc (fpt)；

if ( c==EOF)

return 0；

} /*跳过单词间的所有非字母字符*/

while (tolower (c)＞='a' && tolower (c)＜='z')

{ *word++=c；

c=fgetc (fpt)；

}

*word='\0'；

return 1;

}

void binary_tree(BNODE **t，char *word)

{ BNODE *ptr，*p；int compres；

P=NULL； (1)；

while (ptr) /*寻找插入位置*/

{ compres=strcmp (word， (2) )；/*保存当前比较结果*/

if (!compres)

{ (3)；return；}

else

{ (4)；

ptr=compres＞0? ptr-＞right：ptr-＞left；

}

}

ptr= (BNODE*) malloc (sizeof (BNODE)) ;

ptr-＞left = ptr-＞right = NULL;

ptr-＞word= (char*) malloc (strlen (word) +1) ;

strcpy (ptr-＞word, word);

ptr-＞count - 1;

if (p==NULL)

(5);

else if (compres ＞ 0)

p-＞right = ptr;

else

p-＞left = ptr;

}

void midorder (FILE **fpt, BNODE *t)

{ if (t==NULL)

return;

midorder (fpt, t-＞left);

fprintf (fpt, "%s %d\n", t-＞word, t-＞count)

midorder (fpt, t-＞right);

}

void main()

{ FILE *fpt; char word[40];

BNODE *root=NULL;

if ((fpt=fopen (INF,"r")) ==NULL)

{ printf ("Can't open file %s\n", INF )

return;

}

while (getword (fpt, word) ==1 )

binary_tree (&root, word );

fclose (fpt);

fpt = fopen (OUTF, "w");

if (fpt==NULL)

{ printf ("Can't open file %s\n", OUTF)

return;

}

midorder (fpt, root);

fclose(fpt)；

}

阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子序列)，然后再对左子序列和右子序列分别进行快速排序， 最终得到非递减的有序序列。 函数 quicksort(int a[]，int n)实现了快速排序，其中，n 个整数构成的待排序列保存在数组元素 a[0]-a[n-1]中。

【C 代码】 include < stdio.h> void quicksort(int a[] ，int n) { int i ，j; int pivot = a[0]; //设置基准值 i =0; j = n-l; while (i< j) { while (i<j &&（1）) j-- //大于基准值者保持在原位置 if (i<j) { a[i]=a[j]; i++;} while (i,j &&（2）) i++; //不大于基准值者保持在原位置 if (i<j) { a[j]=a[i]; j--;} } a[i] = pivot; //基准元素归位 if ( i>1) （3） ; //递归地对左子序列进行快速排序 if ( n-i-1>1 ) （4） ; //递归地对右子序列进行快速排序 } int main () { int i，arr[ ] = {23，56，9，75，18，42，11，67}; quicksort ( （5） ); //调用 quicksort 对数组 arr[ ]进行排序 for( i=0; i<sizeof(arr) /sizeof(int); i++ ) printf(" %d\t" ，arr[i]) ; return 0; }

●试题一

阅读下列说明和流程图，将应填入(n)的语句写在答题纸的对应栏内。

【流程图说明】

下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data，left和right。其查找的方法是：首先与树的根节点的元素值进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。

【算法说明】

【流程图】

将上题的排序二叉树中查找元素的过程用递归的方法实现。其中NODE是自定义类型：

typedef struct node{

int data；

struct node*left；

struct node*right；

}NODE；

【算法】

NODE*SearchSortTree(NODE*tree，int e)

{

if(tree!=NULL)

{

if(tree->data<e)

(4) ；∥小于查找左子树

else if(tree->data<e)

(5) ；∥大于查找左子树

else return tree；

}

return tree；

}