}
(A)Binsch(A,mid+1,low,K) (B)Binsch(A,mid-1,low,K) (C)Binsch(A,mid+1,high,K) (D)Binsch(A,mid-1,high,K) (E)Binsch(A,low,mid+1,K) (F)Binsch(A,low,mid-1,K) (G)Binsch(A,high,mid+1,K) (H)Binsch(A,high,mid-1,K)
6.下列程序采用单链表作为存储结构，实现直接插入排序。已知单链表第一个结点
为h。试在下列(A)~(T)选项中选择正确语句填入各空白处。 struct node { int key;
struct node *next; }; void stinsort(struct node *h) {
struct node *p,*q,*r,*s; int t;
if (h==NULL) return; (11) E ; while(p!=NULL) { q=h;
while((q!=p)&&( (12) T )) { (13) C ; q=q->next; } (14) P ; if(p!=q){ r->next=p; q->next=p->next; (15) M ; }
p=s; } }
(A)r=q->next (B)q=r->next (C)r=q (D)r=p->next (E)p=h->next (F)q=h->next (G)p=h (H)q=h (I)q->next=s (J)p->next=s (K)s=p (L)q->next=p (M)p->next=q (N)s=q->next (O)s=q (P)s=p->next
第 41 页 共 100 页
(Q)r->key>q->key (R)r->key
7.下列程序用来生成一个带头结点的单链表，并将字符串str中的每一个字符存放到
该单链表中去，要求单链表中每个结点存放4个字符。 struct node { char data[4];
struct node *next; };
void strqueue(char str[]) {
struct node *head,*p,*q; int i,j=0;
head=(struct node *)malloc(sizeof(struct node)); head->next=NULL; （1） =head; for (i=0; str[i]!=‘\\0‘; i++) { if(j==0) {
p=(struct node *)malloc(sizeof(struct node)); (2) =str[i]; j=1;
p->next=NULL; (3) ; q=p; } else {
(4) ; j++; if(j>3) j=0; } } }
q=head; p->data[0] q=>next=p
p->data[j]=str[i]
8.下列程序从哈希表中删除一个关键字为k的记录，假设所用哈希函数为HT，解决
第 42 页 共 100 页
冲突的方法为链地址法。 struct node {
int key;
struct node *next; }HT[m];
void deletehash(struct node HT[],int k) {
struct node *p,*q,*r; j= （5） ; if(HT(j).key==0)
printf(\ else if(HT(j).key==k) {
if(HT(j).next==NULL) （6） ;
else {
q=HT(j).next;
while( （7） ) {
r=q; q=q->next; }
if(q!=NULL) {
（8） ; printf(\ free(q); }
else printf(\
} } }
k%p
HT[j].key=0
(q!=NULL)&&(q->key!=k) r->next=q->next;
9.已知Q是一个非空队列，S是一个栈。下列程序算法，仅用以下队列和栈的ADT
函数和少量工作变量，将队列Q中的所有元素逆置。 栈的ADT函数有：
makeEmpty(s:stack); 置空栈
push(s:stack; value:datatype); 新元素value进栈 pop(s:stack):datatype; 出栈，返回栈顶值 isEmptyS(s:stack):boolean; 判栈空否
第 43 页 共 100 页
队列的ADT函数有
enQueue(q:queue;value:datatype); 元素value进队 deQueue(q:queue):datatype; 出队列，返回队头值 isEmptyQ(q:queue):boolean; 判队列空否
void SetReverse(queue s) {
datatype x; stack s;
makeEmpty(s);
while (not isEmptyQ(q)) { x= (9) ;
(10) ; }
while (not isEmptyS(s)) { (11) ; (12) ; } }
deQueue(q) push(s,x) x:=pop(s) deQueue(q,x)
10. 下列程序从哈希表中查找一个关键字为k的记录，若关键字为k的记录不存在，
则将其插入其中。假设所用哈希函数为HT，解决冲突的方法为链地址法。请在空格处填入正确合理的内容。 struct node { int key;
struct node *next; } HT[m];
void linkhash(struct node HT[], int k, int p) {
struct node *q,*r,*s; j=k%p;
if (HT[j].key= =0) { HT[j].key=k;
第 44 页 共 100 页
[1] ; }
else if (HT[j].key= =k) printf(―found! ], ]‖,j,k);
else {
q= [2] ; while(q!=NULL)&&(q->key!=k) { r=q;
[3] ; }
if ( [4] ) {
s=(struc node *)malloc(sizeof(struct node)); s->key=k; s->next=NULL; [5] ; }
else printf(―found! ], ]‖,j,k); } }
[1] HT[j].next=NULL [2] HT[j].next [3] q=q->next [4] q= =NULL [5] r->next=s
11. 已知二叉树中结点的数值域之值为整型，利用二叉树的中序非递归遍历算法，
要求经过一次遍历计算得到二叉树中结点数值域之值的最小值和次小值。请在空格处填入正确合理的内容。 struct nodex { char data,
struct nodex *lch,rch; } {
int x1,x2; x1=32767; x2=32767;
p=t; q=p; top=0; bool=1;
第 45 页 共 100 页