449#数据结构.docx
《449#数据结构.docx》由会员分享，可在线阅读，更多相关《449#数据结构.docx（16页珍藏版）》请在冰点文库上搜索。
449#数据结构
《数据结构》模拟卷
一、选择题
1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（a）。
a.O（n）b.O（n/2）C.O
（1）D.O（n2）
2.带头结点的单链表first为空的判定条件是：
（b）。
a.first==NULL;b.first->link==NULL;
C.first->link==first;D.first!
=NULL;
3.从逻辑上可以把数据结构分为（C）两大类。
a．动态结构、静态结构b．顺序结构、链式结构
C．线性结构、非线性结构D．初等结构、构造型结构
4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。
在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（D），在被调用程序中可直接操纵实际参数。
a.空间b.副本C.返回地址D.地址
5.以下数据结构中，哪一个是线性结构（D）。
a．广义表b.二叉树C.稀疏矩阵D.串
6.以下属于逻辑结构的是（C）。
a．顺序表b.哈希表C.有序表D.单链表
7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（C）的值除以9。
a.20b.18C.25D.22
8.在有向图中每个顶点的度等于该顶点的（C）。
a.入度b.出度
C.入度与出度之和D.入度与出度之差
9.在基于排序码比较的排序算法中，（C）算法的最坏情况下的时间复杂度不高于O（nlog2n）。
a.起泡排序b.希尔排序C.归并排序D.快速排序
10.当α的值较小时，散列存储通常比其他存储方式具有（b）的查找速度。
a.较慢b.较快C.相同D.不同
二、填空题
1.二维数组是一种非线性结构，其中的每一个数组元素最多有______2___个直接前驱（或直接后继）。
2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，a[0][0]存放于B[0]中。
对于任意给定数组元素B[K]，它应是A中第_ë（K+1）/3û_行的元素。
3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的__指针__域的值。
4.在一个链式栈中，若栈顶指针等于NULL则为__空栈_。
5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的__返回_地址。
6.在一棵树中，__叶子_结点没有后继结点。
7.一棵树的广义表表示为a（b（c,d（e,f）,g（h））,i（j,k（x,y））），结点f的层数为___3___。
假定根结点的层数为0。
8.在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过_____1___。
9.n（n﹥0）个顶点的无向图最多有__n（n-1）/2_条边，最少有___0_____条边。
10.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_稠密__索引，若对应数据对象表中的若干个表项，则称此索引为_稀疏___索引。
三、判断题
1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的（对）
2.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序（错）
3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针（对）
4.通常递归的算法简单、易懂、容易编写，而且执行的效率也高（错）
5.一个广义表的表尾总是一个广义表（对）
6.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止（对）
7.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）（错）
8.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关（错）
9.直接选择排序是一种稳定的排序方法（错）
10.闭散列法通常比开散列法时间效率更高（错）
四、运算题
1.设有一个1010的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，a[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。
2.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。
intcount（ListNode*Ha,ElemTypex）
{//Ha为不带头结点的单链表的头指针
intn=0;
while（Ha->link!
=NULL）{
Ha=Ha->link;
if（Ha->data==x）n++;
}
returnn;
}
3.已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。
前序序列：
a,b,C,D,E,F,G,H,I,J
中序序列：
C,b,a,E,F,D,I,H,J,G
后序序列：
4.已知一个有序表（15,26,34,39,45,56,58,63,74,76,83,94）顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34,56,58,63,94时的比较次数。
元素值
比较次数
5.设散列表为HT[17],待插入关键码序列为{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}，散列函数为H（key）=i2，其中，i是关键码第一个字母在字母表中的序号。
现采用线性探查法解决冲突。
字母
a
b
C
D
E
F
G
H
I
J
K
L
M
序号
1
2
3
4
5
6
7
8
9
10
11
12
13
字母
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
序号
14
15
16
17
18
19
20
21
22
23
24
25
26
（1）试画出相应的散列表；
（2）计算等概率下搜索成功的平均搜索长度；
参考正确的答案是：
1.根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I*（I+1）/2+J，因此，a[8][5]在数组B中位置为
8*（8+1）/2+5=41。
2.
while（Ha!
=NULL）{
if（Ha->data==x）n++;
Ha=Ha->link;
}
3.后序序列：
C,b,F,E,I,J,H,G,D,a
4.
判断结果
元素值
比较次数//对1个给1分，全对给8分
5.
H（Jan）=102=5，成功.H（Feb）=62=3，成功.
H（Mar）=132=6，成功.H（Apr）=12=0，成功.
H（May）=132=6，=7，成功，H（June）=102=5，=6，=7，=8，成功.
H（July）=102=5，=6，=7，=8，=9，成功.
H（Aug）=12=0，=1，成功.H（Sep）=192=9，=10，成功.
H（Oct）=152=7，=8，=9，=10，=11，成功.
H（Nov）=142=7，=8，=9，=10，=11，=12，成功.
H（Dec）=42=2，成功.
（1）相应的散列表（6分），错一个存储位置扣1分，最多扣6分。
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Apr
Aug
Dec
Feb
Jan
Mar
May
June
July
Sep
Oct
Nov
（1）
（2）
（1）
（1）
（1）
（1）
（2）
（4）
（5）
（2）
（5）
（6）
（2）搜索成功的平均搜索长度为
1/12*（1+2+1+1+1+1+2+4+5+2+5+6）=31/12（2分）
五、算法设计题
已知二叉树中的结点类型用BinTreeNode表示，被定义为:
structBTreeNode{chardata;BinTreeNode*leftChild,*rightChild;};其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。
假定参数BT初始指向这棵二叉树的根结点。
intBTreeCount（BinTreeNode*BT）;
《数据结构》模拟卷
一、单项选择题
1．以下与数据的存储结构无关的术语是（C）。
a．循环队列b.链表C.哈希表D.栈
2．以下数据结构中，哪一个是线性结构（D）。
a．广义表b.二叉树C.稀疏矩阵D.串
3．以下那一个术语与数据的存储结构无关？
（b）。
a．栈b.哈希表C.线索树D.双向链表
4．在下面的程序段中，对x的赋值语句的频度为（C）。
FORi:
=1TOnDO
FORj:
=1TOnDO
x:
=x+1;
a．O（2n）b．O（n）C．O（n2）D．O（log2n）
5.下面关于线性表的叙述中，错误的是哪一个（b）。
a．线性表采用顺序存储，必须占用一片连续的存储单元。
b．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
6．线性表是具有n个（C）的有限序列（n>0）。
a．表元素b．字符C．数据元素D．数据项E．信息项
7.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（a）存储方式最节省时间。
a．顺序表b．双链表C．带头结点的双循环链表D．单循环链表
8.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。
a．单链表b．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表
9.下面给出的四种排序法中（D）排序法是不稳定性排序法。
a.插入b.冒泡C.二路归并D.堆积
10.下列排序算法中，其中（D）是稳定的。
a.堆排序，冒泡排序b.快速排序，堆排序
C.直接选择排序，归并排序D.归并排序，冒泡排序
11.已知一算术表达式的中缀形式为a+b*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（D）。
a．-a+b*C/DEb.-a+b*CD/EC．-+*ABC/DED.-+a*BC/DE
12.算术表达式a+b*（c+d/e）转为后缀表达式后为（b）。
a．ab+cde/*b．abcde/+*+C．abcde/*++D．abcde*/++
二、填空题，在横线处填写合适内容
1.数据结构的存储结构包括顺序、____链接____、索引和散列等四种。
2.在程序运行过程中可以扩充的数组是_____动态_____分配的数组。
这种数组在声明它时需要使用数组指针。
3.在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。
4.栈是一种限定在表的一端进行插入和删除的线性表，又被称为_____后出先进______表。
5.如果一个对象部分地包含自己，或自己定义自己，则称这个对象是____递归_____的对象。
6.一棵树的广义表表示为a（b（c,d（e,f）,g（h））,i（j,k（x,y））），结点f的层数为____3_______。
假定树根结点的层数为0。
7.一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有____右____子女。
8.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的___左子树_____上。
9.设图G=（V,E），V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有_____2_____种。
10.每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做_____交换_____排序。
11.快速排序在平均情况下的空间复杂度为___O（log2n）___。
12.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为__500___。
三、判断题
1.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度（对）
2.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树（错）
3.对于AOE网络，加速任一关键活动都能使整个工程提前完成（错）
4.直接选择排序是一种稳定的排序方法（错）
5.闭散列法通常比开散列法时间效率更高（错）
6.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的（对）
7.顺序表和一维数组一样，都可以按下标随机（或直接）访问（对）
8.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置（错）
9.用非递归方法实现递归算法时一定要使用递归工作栈（错）
10.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果（对）
四、运算题
1.设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，a[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是多少。
a[6][2]的存储字地址：
2.已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1及度为0的结点个数。
中序序列：
c,b,d,e,a,g,i,h,j,f
后序序列：
c,e,d,b,i,j,h,g,f,a
求解一下问题：
高度：
度为2的结点数：
度为1的结点数：
度为0的结点数：
3.假定一组记录为（36,75,83,54,12,67,60,40），将按次序把每个结点插入到初始为空的一棵AVL树中，请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少？
左单旋转结点个数：
右单旋转结点个数：
先左后右双旋转结点个数：
先右后左双旋转结点个数：
不调整结点个数：
4.已知一个带权图的顶点集V和边集G分别为：
V={0,1,2,3,4,5,6};
E={（0,1）19,（0,2）10,（0,3）14,（1,2）6,（1,5）5,（2,3）26,（2,4）15,（3,4）18,
（4,5）6,（4,6）6,（5,6）12};
试根据迪克斯特拉（Dijkstra）算法求出从顶点0到其余各顶点的最短路径，在下面填写对应的路径长度。
顶点：
0123456
0
路径长度：
5.已知一个数据表为{36,25,25*,62,40,53}，请写出在进行快速排序的过程中每次划分后数据表的变化。
（0）[362525*624053]
（1）
（2）
（3）
参考正确的答案是：
1.a[6][2]的存储字地址：
322
正确的答案是说明：
按行存储时，计算A[i][j]地址的公式为
LOC（i,j）=LOC（0,0）+（i*n+j）*d
其中首地址LOC（0,0）=200,每个数组元素的存储占用数d=1,二维数组的列数n=20，根据题意，元素A[6][2]的存储地址为
LOC（6,2）=200+（6*20+2）*1=322
2.
高度：
4
度为2的结点数：
3
度为1的结点数：
3
度为0的结点数：
4
3.
左单旋转结点个数：
1
右单旋转结点个数：
0
先左后右双旋转结点个数：
1
先右后左双旋转结点个数：
0
不调整结点个数：
6
4.错1个数值扣2分，最多扣全部8分。
顶点：
0123456
0
16
10
14
25
21
31
路径长度：
5.
（0）[362525*624053]
（1）[25*25]36[624053]
（2）25*2536[5340]62
（3）25*2536405362
五、算法设计题
1．设有一个表头为first的单链表。
试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。
参考正确的答案是：
解答1
templatevoidList:
:
Tnerse（）{
if（first==NULL）return;
ListNode*p=first→link;,*pr=NULL;
While（p!
=NULL）{
First→link=pr;
Pr=first;first=p;p=p→link;
}
first->link=pr;
}
解答2
templatevoidList:
:
Tnerse（）{
ListNode*p,*head=newListNode（）;
While（first!
=NULL）{
P=first;first=first→link;
p→link=head→link;head→link=p;
}
first=head→link;deletehead;
}
《数据结构》模拟卷
一、单项选择题
1．数据结构是（ D ）。
a．一种数据类型
b．数据的存储结构
C．一组性质相同的数据元素的集合
D．相互之间存在一种或多种特定关系的数据元素的集合
2．算法分析的目的是（ b ）。
a．辨别数据结构的合理性
b．评价算法的效率
C．研究算法中输入与输出的关系
D．鉴别算法的可读性
3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ D ）。
a．插入b．删除
C．排序D．定位
4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ b ）。
a．3，2，6，1，4，5b．3，4，2，1，6，5
C．1，2，5，3，4，6D．5，6，4，2，3，1
5．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index（s1,s2）的值为（ D ）。
a．15b．16
C．17D．18
6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，a[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ a ）。
a．1207b．1209
C．1211D．1213
7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ a ）。
a．队列b．栈
C．线性表D．有序表
8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ b ）。
a．不一定相同b．都相同
C．都不相同D．互为逆序
9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ C ）。
a．层次遍历算法b．前序遍历算法
C．中序遍历算法D．后序遍历算法
10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ a ）。
a．图中每个顶点的入度b．图中每个顶点的出度
C．图中弧的条数D．图中连通分量的数目
11．图的邻接矩阵表示法适用于表示（ C ）。
a．无向图b．有向图
C．稠密图D．稀疏图
12．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（ D ）。
a．ib．i+1
C．n-iD．n-i+1
二、填空题
1．栈是___特殊____的线性表，其运算遵循___后进先出____的原则。
2．___栈____是限定仅在表尾进行插入或删除操作的线性表。
3.一个栈的输入序列是：
1，2，3则不可能的栈输出序列是__3，1，2_______。
4．二叉树由__根结点、左子树、右子树_三个基本单元组成。
5．在二叉树中，指针p所指结点为叶子结点的条件是___P->Lchild==NULL&&P->Rchild==NULL___。
6．具有256个结点的完全二叉树的深度为___9___。
7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12___个叶子结点。
8．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的___移动__。
9.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是___算法，最费时间的是_快速排序___算法。
10．不受待排序初始序列的影响，时间复杂度为O（N2）的排序算法是___选择排序__，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是___归并排序__。
三、解答题
1．某广义表的表头和表尾均为（a,（b,c）），画出该广义表的图形表示。
2．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。
（1）画出该二叉树；
（2）画出与
（1）求得的二叉树对应的森林。
3．已知带权图的邻接表如下所示，其中边表结点的结构为：
依此邻接表从顶点C出发进行深度优先遍历。
（1）
升级会员 