文档介绍：该【数据结构模拟题及答案】是由【玥玥】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【数据结构模拟题及答案】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。.
数据构造试题(A05)
一、选择题(共10小题,每题1分,共10分)
()
m=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
m=m+1;
(n2)(m+n+1)(m+n)(n)
,指针p指向元素为x的结点,实现“删除x的后继”的语句是
()
=p->next;->next=p->next->next;
->next=p;=p->next->next;
,当在任何地点上删除一个元素的概率相等时,删除一个
元素需要挪动的元素的均匀个数为()
.(n-1)/2C.(n+1)/2D.(n+2)/2
,则以下序列中不行能是栈的输出序列的是
()

~n,其头尾指针分别为f和r,则其元素个
数为()
--f+1
C.(r-f)modn+1D.(r-f+n)modn
()。
可编写
.
A.(100,85,98,77,80,60,82,40,20,10,66)
B.(100,98,85,82,80,77,66,60,40,20,10)
C.(100,85,40,77,80,60,66,98,82,10,20)
D.(10,20,40,60,66,77,80,82,85,98,100)
(12,24,36,48,60,72,84)中折半查找重点字72时所需
进行的重点字比较次数为()。

,效率最高的排序方法是()。

二、填空题(共
20小题,每题1分,共20
分)
1、在单链表中,删除指针P所指结点的后继结点的语句
是
。
2、线性表的两种储存构造分别是
和
。
3、己知完整二叉树的第4层有5
个结点,则其叶子结点数
是
。
4、将下三角矩阵
A[,]的下三角部分逐行地储存到开端地点为1000
的内存单元中,已知每个元素占4个单元,则A[7,5]的地点
是
。
5、有n个结点的强连通有向图G起码有
条弧。
7、在有序表A[]中,采纳二分查找算法查找元素值等于
A[12]的元素,所
比较的元素的下标挨次为
。
可编写
.
8、直接选择排序算法所履行的元素互换次数最多为。
9、在带有头结点的单链表L中,第一个元素结点的指针
是。
10、拥有100个结点的完整二叉树的深度是。
11、在一个长度为n的次序表中第i个元素(1≤i≤n)以前插入一个元素时,需向
后挪动个元素。
12、在行列中,同意进行插入操作的一端称为,同意进行删除操作的一
端称为
。
13
、在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点
的指针head可用p表示为head=
。
15
、关于一棵拥有n个结点的树,该树中全部结点的度数之和为
。
16
、8
层完整二叉树起码有
个结点,拥有300
个结点的完整二
叉树的最大层数为。
17、有n个结点的有向连通图,其边数最多为
____条,最罕有____条。
18
、设n0为赫夫曼树的叶子结点数量,则该赫夫曼树共有
_____个结点。
19
、次序查找n个元素的次序表,若查找成功,则比较重点字的次数最多为____
次。
三、判断题(共10小题,每题1分,共10分)
判断以下各题能否正确,若正确,在(
)内打“√”,不然打“╳”。
1、(
)若某二叉树的叶子结点数为
1,则其先序序列和后序序列必定相反。
2、(
)线性表采纳链表方式温次序表方式储存,履行插入和删除运算的时间
复杂度都是O(n),因此两种储存方式的插入、删除运算所花销的时间同样。
可编写
.
3、()在栈为空的状况下,不可以作出栈操作,不然产生下溢。
5、()在一个有向图的毗邻表中,假如某个极点的链表为空,则该极点的度
必定为0。
6、()假如有向图G=(V,E)的拓扑序列独一,则图中必然仅有一个顶
点的入度为0,一个极点的出度为0。
8、(
)广义表的长度是指广义表中原子的个数。
9、(
)在迅速排序算法中,以待排序的
n个记录中的第一个记录的键值
为基准,将全部记录分为两组,该记录就在这两组的中间,这也是该记录的最后
地点。
10、()在一个大根堆中,最小元素不必定在最后。
四、解答题(共30分,此中第1、2小题各占7分,第3、4小题各占8分)
1、已知二叉树T的先序遍历序列为ABCDEFGHIJKLMN,中序遍历序列为
DCFEGBAIHKJMLN。请画出该二叉树T,并写出它的后序遍历序列。
2、已知一个无向图的极点集为{a,b,c,d,e},其毗邻矩阵
以下所示
01001
10010
c
d

00011
01101
10110
(1)画出该图的图形;
2)依据毗邻矩阵从极点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列。
可编写
.
3、已知线性表的重点字会合{87,25,310,08,27,132,68,95,187,123,70,63,
47},已知哈希函数为H(k)=kMOD13,采纳拉链法办理矛盾,设计出该哈希
表的构造。
4、输入以下整数序列,画出成立的二叉排序树,最后分别图示将此中50,86
删除后的二叉排序树。(86,50,78,90,64,55,23,100,40,80,45)。
五、算法题(共30分,此中第1、2小题各占6分,第3、4小题各占9分)
1、假定一个单循环链表L的数据域为整型,设计一个算法,求该表中全部结点
的数据之和。
2、设某二叉树以二叉链表为储存构造,请写出求其高度的递归算法。
3、假定有两个按元素值递加有序摆列的线性表A和B,均以单链表作储存构造,
请编写算法将表A和表B合并成一个按元素非递减有序(同意值同样)摆列的
线性表C。
4、试写出二叉链表表示的二叉树的先序遍历的非递归算法。
数据构造试题(A05参照答案)
一、选择题1~5:ABBBB6~9:DCDD
二、填空题
1、p->next=p->next->next;
、次序,链接
、6
、1132
可编写
.
5、n
6、O(n2)
7、10,15,12
8、n-1
9、L->next
、7
、n-i+1
、队尾,队头
、p->next->next
14、s->prior->next=s,(或p->prior->prior->next=s)
、n-1
、128,9
、n(n-1),n
、2n0-1
、n
三、判断题
1、√2、╳3、√5、╳
6、√8、╳9、√10、√
四、简答题
、二叉树以以下图:
可编写
.
后来序遍历序列是:DFGECBIKMNLJHA
2、(1)该图的图形以以下图:
2)依据毗邻矩阵从极点a出发进行深度优先遍历和广度优先遍历,其深度优先遍历序列是abdce,广度优先遍历序列是abedc。
、获得的哈希表以以下图所示:
可编写
.
、成立的二叉排序树以以下图:
删除50后的二叉排序树以以下图:
可编写
.
再次删除86后的的二叉排序树以下:
五、算法题
可编写
.
1、解:设储存构造以下:
typedefstructnode
{intdata;
structnode*next;
}Lnode,*CLinkList;
且设单循环链表是带头结点的,算法以下:
intsumOfLinkList(CLinkListL)
{intsum=0;Lnode*p=L->next;
while(p!=L){sum+=p->data;p=p->next;}
returnsum;
}
2、解:设储存构造以下:
typedefstructnode
{ElemTypedata;
structnode*lchild,*rchild;
}Tnode,*BinTree;
算法以下:
intdepth(BinTreeT)
{if(!T)return0;else
{intDL,DR;DL=depth(T->lchild);
可编写