album 精选学习资源，大学生必学！

数据结构与算法试题及答案

preview
试读
15页
数据结构
需积分: 0 1 下载量 194 浏览量 更新于2024-08-09 收藏 231KB DOC 举报
数据结构与算法试题及答案
0
数据结构试卷（一）
阅读算法（每题 7 分，共 14 分）
1. LinkList mynote(LinkList L)
{//L 是不带头结点的单链表的头指针
if(L&&L->next){
q=L；L=L－>next；p=L；
S1： while(p－>next) p=p－>next；
S2： p－>next=q；q－>next=NULL；
}
return L；
}
请回答下列问题：
（1）说明语句 S1 的功能；
（2）说明语句组 S2 的功能；
（3）设链表表示的线性表为（a
1
,a
2
, …,a
n
）,写出算法执行后的返回值所表示的线性
表。
（1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点
（3）返回的线性表为（a
2
,a
3
,…,a
n
,a
1
）
2. void ABC(BTNode * BT)
{
if BT {
ABC (BT->left);
ABC (BT->right);
cout<<BT->data<<' ';
}
}
该算法的功能是：递归地后序遍历链式存储的二叉树。
算法填空（共 8 分）
二叉搜索树的查找——递归算法:
bool Find(BTreeNode* BST,ElemType& item)
{
if (BST==NULL)
return false; //查找失败
else {
if (item==BST->data){
item=BST->data;//查找成功
return __true__
_______;}
else if(item<BST->data)
return Find(__BST->left ___,item);
else return Find(__BST->right ___,item);
}//if
}
编写算法（共 8 分）
统计出单链表 HL 中结点的值等于给定值 X 的结点数。
1
int CountX(LNode* HL,ElemType x)
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i 为计数器
while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while, 出循环时 i 中的值即为 x 结点个数
return i;
}//CountX
1． 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给
出构造过程。
算法设计题
1. 设有一组初始记录关键字序列（K
1
，K
2
，…，K
n
），要求设计一个算法能够在 O(n)的时
间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于 K
i
，右半部分的
每个关键字均大于等于 K
i
。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(i<j){
while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}
while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}
}
r[i]=x;
}
2. 设有两个集合 A 和集合 B，要求设计生成集合 C=A∩B 的算法，其中集合 A、B 和 C 用
链式存储结构表示。
typedef struct node {int data; struct node *next;}lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *p,*q,*t;
for(p=ha,hc=0;p!=0;p=p->next)
{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;}
}
}
计算题(每题 10 分，共 30 分)
1.已知二叉树的前序遍历序列是 AEFBGCDHIKJ，中序遍历序列是 EFAGBCHKIJD，画出此
二叉树，并画出它的后序线索二叉树。
2
A
E
B
F
G
C
D
H
F
K
J
NULL
2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定
选用的散列函数是 H（K）= K mod 7，若发生冲突采用线性探查法处理，试：
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
` 0 1 2 3 4 5 6
（2）求出在查找每一个元素概率相等情况下的平均查找长度。
H(36)=36 mod 7=1; H
１
(22)=(1+1) mod 7=2; ….冲突
H(15)=15 mod 7=1;….冲突 H
2
(22)=(2+1) mod 7=3;
H
１
(15)=(1+1) mod 7=2;
H(40)=40 mod 7=5;
H(63)=63 mod 7=0;
H(22)=22 mod 7=1; ….冲突
（1） 0 1 2 3 4 5 6
63
36
15
22
40
（2）ASL=
6.1
5
31121
�
����
3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。
(8,9,4,3,6,1),10,(12,18,18)
(1,6,4,3),8,(9),10,12,(18,18)
1,(3,4,6),8,9,10,12,18,(18)
1,3,(4,6),8,9,10,12,18,18
1,3, 4,6,8,9,10,12,18,18
算法设计题(每题 15 分，共 30 分)
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;}

剩余14页未读，继续阅读

身份认证 购VIP最低享 7 折!
30元优惠券
资源推荐
资源评论
Hymannnn
  • 粉丝: 36
上传资源 快速赚钱
voice
center-task 前往需求广场，查看用户热搜

最新资源