没有合适的资源?快使用搜索试试~ 我知道了~
东南大学十套数据结构试题及答案.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 164 浏览量
2023-03-06
20:10:32
上传
评论
收藏 365KB DOCX 举报
温馨提示
试读
23页
。
资源推荐
资源详情
资源评论
A
0
1
3
4
5
6
7
34
4
40
1
3
5
2
0
2. 请画出以下列图的邻接矩阵和邻接表。
S1:
S2:
while(p->next) p=p->next;
p->next=q;q->next=NULL;
}
}
请答复以下问题:
〔1〕说明语句S1 的功能;
〔2〕说明语句组S2 的功能;
1
2
n
表。
2. void ABC(BTNode * BT)
{
{
if (BST==NULL)
return false; //查找失败
else {
if (item==BST->data){
item=BST->data;//查找成功
return ___________;}
else if(item<BST->data)
return Find(______________,item);
else return Find(_______________,item);
}//if
}
六、编写算法〔共8 分〕
统计出单链表HL 中结点的值等于给定值X 的结点数。
int CountX(LNode* HL,ElemType x)
三、应用题(36 分)
四、算法设计题(16 分)
1
2
i
数据构造试卷〔三〕
二.填空题
1. 以下算法实如今顺序散列表中查找值为 x 的关键字,请在下划线处填上正确的语句。
struct record{int key; int others;};
int hashsqsearch(struct record hashtable[ ],int k)
{
int i,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}
if (_______________________ ) return(j); else return(-1);
}
2. 以下算法实如今二叉排序树上查找关键值 k,请在下划线处填上正确的语句。
typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;
bitree *bstsearch(bitree *t, int k)
{
if (t==0 ) return(0);else while (t!=0)
if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;
}
三、计算题(每题 10 分,共 30 分)
1.二叉树的前序遍历序列是 AEFBGCDHIKJ,中序遍历序列是 EFAGBCHKIJD,画出此二叉
树,并画出它的后序线索二叉树。
2.待散列的线性表为〔36,15,40,63,22〕,散列用的一维地址空间为[0..6],假定选用
的散列函数是 H〔K〕= K mod 7,假设发生冲突采用线性探查法处理,试:
〔1〕计算出每一个元素的散列地址并在以下列图中填写出散列表:
`
0
1
2
3
4
5
6
〔2〕求出在查找每一个元素概率相等情况下的平均查找长度。
3.序列〔10,18,4,3,6,12,1,9,18,8〕请用快速排序写出每一趟排序的结果。
四、算法设计题(每题 15 分,共 30 分)
1. 设计在单链表中删除值一样的多余结点的算法。
2. 设计一个求结点 x 在二叉树中的双亲结点算法。
数据构造试卷〔四〕
1. 设一组初始记录关键字序列为(20,18,22,16,30,19),那么以 20 为中轴的一趟快
速排序结果为______________________________。
2. 设一组初始记录关键字序列为(20,18,22,16,30,19),那么根据这些初始关键字序
列建成的初始堆为________________________。
3. 设某无向图G 中有n 个顶点,用邻接矩阵A 作为该图的存储构造,那么顶点i 和顶点j
互为邻接点的条件是______________________。
4. 设无向图对应的邻接矩阵为A,那么A 中第i 上非0 元素的个数_________第 i 列上非0
元素的个数〔填等于,大于或小于〕。
5. 设前序遍历某二叉树的序列为ABCD,中序遍历该二叉树的序列为BADC,那么后序遍
历该二叉树的序列为_____________。
6. 设散列函数H(k)=k mod p,解决冲突的方法为链地址法。要求在以下算法划线处填上正
确的语句完成在散列表hashtalbe 中查找关键字值等于k 的结点,成功时返回指向关键
字的指针,不成功时返回标志0。
typedef struct node {int key; struct node *next;} lklist;
void createlkhash(lklist *hashtable[ ])
{
int i,k; lklist *s;
for(i=0;i<m;i++)_____________________;
for(i=0;i<n;i++)
{
s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];
k=a[i] % p; s->next=hashtable[k];_______________________;
}
}
三、计算题(每题 10 分,共 30 分)
1、画出广义表 LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储构造。
2、以下列图所示的森林:
(1) 求树〔a〕的先根序列和后根序列;
(2) 求森林先序序列和中序序列;
〔3〕将此森林转换为相应的二叉树;
A
B
C
F
I
D E
(a)
J
K
(b)
3、设散列表的地址范围是[ 0..9 ],散列函数为 H〔key〕= 〔key 2+2〕MOD 9,并采用链
表处理冲突,请画出元素 7、4、5、3、6、2、8、9 依次插入散列表的存储构造。
四、算法设计题(每题 10 分,共 30 分)
1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表
中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。
2. 设计在链式存储构造上交换二叉树中所有结点左右子树的算法。
3. 在链式存储构造上建立一棵二叉排序树。
剩余22页未读,继续阅读
资源评论
若♡
- 粉丝: 6174
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功