数据结构试题-考研精选(9)
时间:2025-04-03
时间: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
。 )