计算机专业基础综合数据结构(集合)历年真题试卷汇编6

计算机专业基础综合数据结构（集合）历年真题试卷汇编6(总分：58.00，做题时间：90分钟)一、填空题(总题数：7，分数：14.00)1.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分(折半)查找方法统计成绩大于或等于x分的学生人数，请填空使之完善。

#define N／*学生人数*／intuprx(int a[N]，int x) ／*函数返回大于等于x分的学生人数*／ {int head=1，mid，rear=N; do{mid=(head+rear)／2；if(x<=a[mid]) (1) else(2); }while((3))； if(a[head]（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)head=mid+1 (2)rear=mid-1 (3)head≤rear／／编者注：参数应为a[N+1])解析：2.下列程序段search(a，n，k)在数组a的前n(n≥1)个元素中找出第k(1≤k≤n)小的值。

这里假设数组a 中各元素的值都不相同，请填上适当的语句使得整个程序完整。

define NAXN 100 int a[MAXN]，n，k；int search(int a[]，int n，int k) {intlow，high，i，j，m，t；k--，low=0；j=high；do(t=a[ltow]；i=low j=high； do{while(i<j＆&t<j&&t>=a[j])i++； if(i（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)il=k (2)i+1 (3)i一1 (4)il=k)解析：3.下列算法是利用折半查找算法在一个有序表中插入一个元素X，并保持表的有序性。

请将程序中空白处填上适当的语句完成功能。

int bininsert(sqlist r，int x，int n)／／将x插入到r[1．-n]中并保持其有序性 {int low：1，high=13．，mid，flag=l，pos，i；／／插入的位置为pos while( (1) &&flag) (mid=(log+high)／2；if(xr[mid]．key) (3) ；else flag=0；if(!flag)pos=mid；else pos=low；for(i=n；i>=pos；i一一) (4)； r[pos]．key=x； } 【北京交通大学2005七、1(8分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)low<=high (3)high=mid-1 (3)low=mid+1 (4)r[i+1]=r[i])解析：4.假设root是一棵给定的非空查找树，对于下面给出的子程序，当执行注释中给出的调用语句时，就可以实现如下的操作：在非空查找树root中查找值为k的结点；若值为k的结点在树中，且是一个叶子结点，则删除此叶子结点，同时置Success为“真”；若值为k的结点不在树中，或者虽然在树中，但不是叶子结点，则不进行删除，仅置success为“假”。

应注意到非空查找树只包含一个结点情况，此时树中的唯一结点，既是根结点，也是叶子结点。

#include typedef struct、node{ int key；struct node*left，*right ；}node；node*root；int kt success；void del—leaf(node**t，int k，int。

sn) (node*P，*pf；p=。

t；*sn=0；while( (1) ＆＆!*sn) if(k==p一>key)。

sn=1；else { (2) ；if (kkey)p=p->left ；else p=p->right； } if (*sn&&P一>Ieft==NULL&&P一>right==null) { if( (3) ) if(pf一>left==p)pf 一>left=null； else pf一>right=null； else (4) ； free(p)； } else*sn=0； }／*call form：del—leaf(&root，k，&success)；*／【上海大学1999一、2(8分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)p!=null (2)pf=p (3)p!=*t (4)*t=null)解析：5.已知二叉查找树采用链式存储结构，结点结构为(1ch，data，rch)，若令root指向二叉查找树的树根，P指向树中的某个非叶子结点，请编写算法删除p所指结点并保持该树为二叉查找树。

voiddeletep(BSTree&root，BSTree p) {／*在root指向的二叉查找树中删除结点非叶子结点p*／ if(p一>ich){s=p->ich；pre=p； while ( (1) ) { (2) ；s=s一>rch；) P一>data=s一>data； if(pre==p)(3) ；else (4) } else{s=p一>rch：pre=p：while( (5) ) ( (6) ；S=S一>Ich；) P一>data=s一>data；if(pre==p) (7) ；else (8) ； } free(S)； }／*deletep*／【西安电子科技大学2004二、2(8分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)s一>rch (2)pre=s (3)p一>lch=s一>lch (4)pre一>rch=s一>lch(5) s一>lch (6)pre=s (7)p一>rch=s一>rch (8)pre一>lch=s一>rch)解析：6.设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。

在下面的算法中，free tree(T)在对二叉排序树T进行后序遍历时释放二叉排序树T的所有结点；delete_subtree(T,A)，首先在二叉排序树T中查找值为A的结点，根据查找情况分别进行如下处理：(1)若找不到值为A的结点，则返回根结点的地址。

(2)若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二又树，则返回null／NIL；否则返回根结点的地址。

typedef struct node{int data， struct node*ichild， *rchild)node； void free—tree(node*T){if(T!=null){free—tree(T一>ichild)；free—tree iT一>rchild)； (1) ；} }node*delete—subtree(node*T，int A) {node*p=null，*q=T；while( (2) ) {p=q；if(Adata)q=q一>Ichild；else (3) ；) if(q!=null) {free—tree(q)；if(p==null) T=null；else if(Adata) (4) ；else (5) ；} return(T)： } 【东华大学2003六(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)delete(T) (2)q&&q一>data!=A (3)q=q一>rchild (4)p一>lchild=null (5)p 一>rchild=null)解析：7.阅读下列程序，指出其功能，并写出空格处应填上的语句。

void testl(element item，list_pointer ht[]) {int hash—value=hash(item．key)； list_pointer ptr l trail=NULL。

lead=ht[hash value]； for(；lead；trail=lead，lead=lead->1ink) (if{!strcmp(1ead->item．key，item．key)) (fprintf(stderr，“The key is in the table＼n”)；exit(1)；) } ptr=(1ist_pointer)malloc(sizeof(1ist))；if(IS—FULL(ptr)) (fprintf(stderr，“The memoty is full＼n”)；exit(1)；) ptr一>item=item；ptr一>1ink=NULL； if(trail) (1) ；else (2) ； }【浙江大学2002六(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：本题是在哈希表ht[]中插入值为item的元素，如该元素已在哈希表中，报告出错。

(1)trai一>link=ptr (2)ht[1rash—value]=ptr)解析：二、综合题(总题数：8，分数：20.00)8.在一棵表示有序集S的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。