数据结构试题-考研精选(9)

时间:2025-04-03

11. (5,16,71,23,72,94,73) 12. (1,4,3,2)

13. j+1,hashtable[j].key==k 14. return(t),t=t->rchild

第8小题分析:二分查找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。

三、算法设计题

1. 设计在单链表中删除值相同的多余结点的算法。 typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) {

lklist *p,*q,*s;

for(p=head;p!=0;p=p->next) {

for(q=p->next,s=q;q!=0; )

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} }

}

2. 设计一个求结点x在二叉树中的双亲结点算法。

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0;

void preorder(bitree *bt, char x) {

if (bt!=0 && flag==0)

if (bt->data==x) { flag=1; return;}

else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } }

void parent(bitree *bt,char x) {

int i;

preorder(bt,x);

for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf("not found x\n");

else if (i<=r) printf("%c",bt->data); else printf("not parent"); }

数据结构试卷(四)

一、选择题(30分)

1.设一维数组中有n个数组元素,则读取第i个数组元素的平均时间复杂度为( (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)

2.设一棵二叉树的深度为k,则该二叉树中最多有( )个结点。

(A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1

。 )

数据结构试题-考研精选(9).doc 将本文的Word文档下载到电脑

精彩图片

热门精选

大家正在看

× 游客快捷下载通道(下载后可以自由复制和排版)

限时特价:7 元/份 原价:20元

支付方式:

开通VIP包月会员 特价:29元/月

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219