考研资料数据结构练习题1Word格式文档下载.docx
《考研资料数据结构练习题1Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《考研资料数据结构练习题1Word格式文档下载.docx（17页珍藏版）》请在冰点文库上搜索。
28、从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_______。
对于关键字序列（22，13，11，18，50，15，7，28，35，120），用筛选法建堆，则开始调整结点的键值必须为_______。
29、线性结构中的一个结点代表一个（）。
若线性表中最常用的操作是取第i个元素和查找该元素的前驱，则采用的存储方式最能节省时间的是（）。
若最常用的操作是插入和删除第i个元素，则采用的存储方式最能节省时间的是（）。
30、设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；
当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针R指向当前队尾元素的位置）。
31、如果以链栈为存储结构，则出栈操作时（），与顺序栈相比，链栈有一个明显的优势是（）。
32、循环队列采用数组data[1．．n]来存储元素的值，并用front和rear分别作为其头尾指针。
为区分队列的满和空，约定：
队中能够存放的元素个数最大为n-l，也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是（）；
入队时，可用语句（）求出新元素在数组data中的下标。
33、已知栈的输入序列为1，2，3…．，n，输出序列为a1，a2，…，an，a2=n的输出序列共有（）种输出序列。
34、稀疏矩阵一般的压缩存储方法有两种，它们是用（）。
对矩阵压缩存储是为了（）。
35、将下三角矩阵A[l..8，1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址为（）。
二、选择题
1、从逻辑上可以把数据结构分为（）两大类。
A．动态结构、静态结构B．顺序结构、链式结构
C．线性结构、非线性结构D．初等结构、构造型结构
2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）（1<
=i<
=n+1）。
A.O（0）B.O
（1）C.O（n）D.O（n2）
3、若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是（）。
A.iB.n-iC.n-i+1D.不确定
4、设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（）个叶子结点。
A.
B.
C.
D.
5、下列陈述中正确的是（）。
A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分
6、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）。
A．m-nB．m-n-1C．n+1D．条件不足，无法确定
7、．算术表达式a+b*（c+d/e）转为后缀表达式后为（）。
A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++
8、关键路径是事件结点网络中（）。
A．从源点到终点的最长路径B．从源点到终点的最短路径
C．最长回路D．最短回路
9、具有12个关键字的有序表，二分查找的平均查找长度（）。
A.2.5B.4C.3.1D.5
10、AVL树是一种平衡的二叉排序树，树中任一结点的（）
A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1
C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度
11、线性表采用链接存储时，其地址（）。
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续与否均可以
12、栈和队列是两种特殊的线性表，只能在它们的（）处添加或删除结点。
Ａ．中间点
Ｂ．端点
Ｃ．随机存取点
Ｄ．结点
13、输入序列为ABC，可以变为BAC时，经过的栈操作为（）。
A.push,pop,push,pop,push,popB.push,push,push,pop,pop,pop
C.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop
14、下面（）不是算法所具有的特性。
Ａ．有穷性Ｂ．确切性Ｃ．高效性
Ｄ．可行性
15、下面关于串的的叙述中，（）是不正确的？
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算
D．串既可以采用顺序存储，也可以采用链式存储
16、数组A[6][7]的每个元素占五个字节，将其按行优先次序存储在起始地址为2000的内存单元中，则元素A[3][5]的地址是（）。
A.2130B.2180C.2205D.2210
17、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。
A．nB．（n-1）2 C．n-1D．n2
18、设无向图G中的边的集合E={（a，b），（a，e），（a，c），（b，e），（e，d），（d，f），（f，c）}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。
A.aedfcbB.acfebdC.aebcfdD.aedfbc
19、堆的形状是一棵（）。
A.二叉排序树B.满二叉树C.完全二叉树D.判定树
20、若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（）A．s->
next=p->
next；
p->
next=s；
B．p->
s->
C．p->
next=s->
next=p；
D．s->
21、链表不具有的特点是（）。
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
22、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。
A.23415B.54132C.23145D.15432
23、递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。
A．队列B．多维数组C．栈D.线性表
24、设给定权值总数有n个，其哈夫曼树的结点总数为（）。
A．不确定B．2nC．2n+1D．2n-1
25、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）。
A．m-nB．m-n-1C．n+1D．条件不足，无法确
26、某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是（）。
A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子
27、下列说法正确的是（）。
（1）二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索
（2）二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前
（3）二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值
A．
（1）
（2）（3）B．
（1）
（2）C．
（1）（3）D．前面的可选答案都不对
28、设一组初始记录关键字序列为（60，80，55，40，42，85），则以第一个关键字60为基准而得到的一趟快速排序结果是（）。
A．40，42，60，55，80，85B.42，45，55，60，85，80
C.42，40，55，60，80，85D.42，40，60，85，55，80
29、树有先根遍历和后根遍历，树可以转化为对应的二叉树。
下面的说法正确的是（）。
A．树的后根遍历与其对应的二叉树的后根遍历相同
B．树的后根遍历与其对应的二叉树的中根遍历相同
C．树的先根遍历与其对应的二叉树的中根遍历相同
D．以上都不对
30、.下图的邻接表中，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是（）。
A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V2
31、以下说法不正确的是（）。
A．无向图中的极大连通子图称为连通分量
B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D．有向图的遍历不可采用广度优先搜索
32、设哈希表长为14，哈希函数H（key）=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。
A．8B．3C．5D．9
33、栈和队列是两种特殊的线性表，只能在它们的（）处添加或删除结点。
Ａ．中间点
Ｂ．端点
Ｃ．随机存取点
34、二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。
设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是（）。
A．A[8，5]B．A[3，10]C．A[5，8]D．A[0，9]
35、.在n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。
A.O（n）B.O（log2n）C.O（nlog2n）D.O（n2）
三、判断题
1．如果两个串含有相同的字符，则这两个串相等。
（ ）
2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。
（ ）
3．二叉树是度为2的树。
4．在顺序表中取出第i个元素所花费的时间与i成正比。
5．在栈满情况下不能作进栈运算，否则产生“上溢”。
（ ）
6．图G的生成树是该图的一个极小连通子图。
7．所谓数据的逻辑结构指的是数据之间的逻辑关系。
8．二叉排序树的查找和折半查找的时间性能相同。
9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。
10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等。
11、双向链表中至多只有一个结点的后继指针为空。
（）
12、在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。
13、对链表进行插入和删除操作时，不必移动结点。
14、栈可以作为实现程序设计语言过程调用时的一种数据结构。
15、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧<
a,b>
（）。
16、对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。
17、“顺序查找法”是指在顺序表上进行查找的方法。
18、向二叉排序树插入一个新结点时，新结点可以为分支结点。
19、二分查找要求序列顺序存储且关键字序列有序。
20、二路归并时，被归并的两个子序列中的关键字个数一定要相等。
21、调用一次深度优先遍历可以访问到图中的所有顶点。
（）
22、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
（）
23、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。
24、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
25、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。
26、层次遍历初始堆可以得到一个有序的序列。
27、设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。
28、线性表的顺序存储结构比链式存储结构更好。
（）
29、中序遍历二叉排序树可以得到一个有序的序列。
30、快速排序是排序算法中平均性能最好的一种排序。
31、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。
32、当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。
33、设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O（log2n）。
34、完全二叉树中的叶子结点只可能在最后两层中出现。
35、哈夫曼树中没有度数为1的结点。
36、对连通图进行深度优先遍历可以访问到该图中的所有顶点。
37、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
38、由树转化成二叉树，该二叉树的右子树不一定为空。
39、线性表中的所有元素都有一个前驱元素和后继元素。
40、带权无向图的最小生成树是唯一的。
四、应用题
1、已知一棵二叉树的先根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树，并给出其后序序列。
2、将下列由三棵树组成的森林转换为二叉树。
（只要求给出转换结果）
类似例题：
画出与下列二叉树对应的森林。
3、已知无向图如下所示：
（1）．给出从V1开始的广度优先搜索序列；
（2）．画出它的邻接表；
（3）．画出从V1开始深度优先搜索生成树。
4、假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，请先构建一棵哈夫曼树，计算其WPL值，并为这8个字母设计相应的哈夫曼编码。
5、已知一表为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中顺序依次插入初始为空的二叉排序树，要求：
（1）画出建立的二叉排序树（值的大小以字母顺序为准）。
（2）对该二叉排序树作中序遍历，试写出遍历序列。
（3）求出在等概率情况下查找成功的平均查找长度。
6、已知一个图的顶点集V和边集G分别为：
V={0,1,2,3,4,5,6,7};
E={（0,1）8,（0,2）5,（0,3）2,（1,5）6,（2,3）25,（2,4）13,（3,5）9,（3,6）10,
（4,6）4,（5,7）20};
按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
________,________,________,________,________,________,________。
7、已知散列函数为H（K）=Kmod11,健值序列为{57，14，29，11，16，82，42，16，3}哈希表长为11，采用线性探测法处理冲突，试构造闭散列表，并计算查找成功的平均查找长度。
8、已知待排序的序列为（503，87，542，41，900，170，827，275，603，422），试完成下列各题。
（1）根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。
（2）输出最小值后，如何得到次小值。
（并画出相应结果图）。
9、下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。
怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出一个方案。
10、已知图G=（V,E），其中V={v1,v2,v3,v4,v5},E={<
v1,v2>
<
v1,v4>
v2,v3>
v2,v5>
v4,v5>
）,<
v5,v3>
}；
画出这个图的图形并写出所有的拓扑序列。
11、设有关键码序列{20，35，40，15，30，25，38}，请给出平衡二叉树的构造过程（只需要给出不平衡时到平衡的过程即可）。
12、已知散列函数为H（K）=Kmod13,健值序列为11，31，15，44，06，78，12，25，38，84，19，49，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。
13、对于下列一组关键字47，56，15，45，80，19，9，61，试写出快速排序每一趟的排序结果。
14、对下面的关键字集（30，15，21，40，25，26，36，37），若查找表的装填因子为0.8，采用线性探测再散列解决冲突：
（1）设计哈希函数；
（2）画出哈希表；
（3）求查找成功的平均查找长度。
15、按顺序输入下列顶点对:
（V1,V2）、（V1,V6）、（V2,V6）、（V1,V4）、（V6,V4）、（V1,V3）、（V3,V4）、（V6,V5）、（V4,V5）、（V1,V5）、（V3,V5）。
（顶点序列为：
V1，V2，V3，V4，V5，V6）
（1）画出相应的邻接表。
（2）写出在邻接表上，从顶点3开始（表下标从0开始）的DFS序列和DFS生成树。
五、算法与程序设计
1、阅读算法完成题目要求：
（1）说出下列算法的功能。
template<
classT>
structBinnode
{Tdata;
Binnode<
T>
*prior,*next;
};
boolUnknown（Binnode<
*first）
{Binnode<
*p,*q;
p=first->
next;
q=first->
prior;
while（p!
=q&
&
prior!
=q）
if（p->
data==q->
data）
{
p=p->
q=q->
}
elsereturn0;
return1;
}
（2）根据下列算法和输入的数据画出生成的链表形式。
template<
LinkList<
:
LinkList（intn）
{first=newNode<
;
Node<
*s;
Tx;
first->
next=NULL;
for（inti=0;
i<
n;
i++）
{cin>
>
x;
s=newNode<
data=x;
s->
next=first->
first->
next=s;
}
输入数据为：
1098765
（3）说出下列算法的功能，它是采用什么结构实现的。
voidBiTree<
Unknown（BiNode<
*root）
{constintMaxSize=100;
intfront=0;
intrear=0;
BiNode<
*Q[MaxSize];
BiNode<
*q;
if（root==NULL）return;
else{
Q[rear++]=root;
while（front!
=rear）
{
q=Q[front++];
cout<
<
q->
data<
"
"
if（q->
lchild!
=NULL）Q[rear++]=q->
lchild;
rchild!
rchild;
（4）阅读下列算法求出调用该算法后输出结果。
voidAE（Stack&
S）
{
InitStack（S）;
Push（S,10）;
Push（S,20）;
Push（S,30）;
intx=Pop（S）+2*Pop（S）;
Push（S,x）;
inti,a[4]={7,9,15,18};
for（i=0;
i<
4;
i++）Push（S,a[i]）;
while（!
StackEmpty（S））
升级会员 