文档文库
手机版
投诉建议
热门搜索： 心得体会 演讲稿 思想汇报
首页 > 数据结构考试

数据结构考试

发布时间：   来源：文档文库   
小 中 大
字号：
手机查看

题型：
填空题（10题，每空1分，10分）
判断+改错(5-10题，每题1-2分，10-20分
选择题（15-20题，每题1分，15-20分）综合题（5-7个大题，共35-40分）
程序题（2-3题，共10-15分）
综合题
二叉树的顺序存储，前、中、后、层序遍历方法已知二叉树的前(后序+中序遍历，画二叉树给定一个权值集合，画哈夫曼树，求哈夫曼编码图的邻接矩阵和邻接表存储、广度和深度遍历方法Prim算法和Kruskal算法求无向带权图的最小生成树
给定待排序的数据序列，写出直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序的排序过程二叉排序树的建立哈希表的建立
程序题
求带头结点的单链表长的算法(显示单链表所有元素在单链表中查找内容为x的结点的算法
在带头结点head的单链表的结点a之后插入新元素x删除单链表的第i个结点直接插入排序直接选择排序冒泡排序二分查找


单元测验1
一．判断题（ㄨ）（1）数据的逻辑结构和数据的存储结构是相同的。（ㄨ）（2）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（√）（3）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√）（4）数据的存储结构是数据的逻辑结构的存储映像。（ㄨ）（5）数据的逻辑结构是依赖于计算机的。（√）（6）算法是对解题方法和步骤的描述。二．填空题
1．数据有逻辑结构和存储结构两种结构。
2.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。3．树形结构和图形结构合称为非线性结构。4．数据的存储结构又叫物理结构。
5．数据的存储结构形式包括：顺序存储和链式存储6．线性结构中的元素之间存在一对一的关系。7．树形结构中的元素之间存在一对多的关系。8．图形结构的元素之间存在多对多的关系。
9．数据结构主要研究数据的逻辑结构、存储结构和二者之间的相互运算三个方面的内容。10．一个算法的时间复杂度是问题规模的函数。
时间复杂度：Ο(1＜Ο(log2＜Ο(n＜Ο(nlog2＜Ο(n＜Ο(n＜…＜Ο(2＜Ο(n!
11．若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n）。12．若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为O（n2）。三．选择题
1．数据结构通常是研究数据的（D）及它们之间的相互联系。
A.联系与逻辑B.存储和抽象C.联系和抽象D.存储结构和逻辑结构2．数据在计算机内存储时，数据元素在存储器内相对位置可以表示元素之间的逻辑关系，称为（D）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3．链接存储的存储结构所占存储空间（A）。
A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点值，另一部分存放结点所占单元数4．在数据结构中，与所使用的计算机无关的是（B）
A.物理结构B.逻辑结构(不用进行计算C.存储结构D.逻辑和存储结构5．算法能正确的实现预定功能的特性称为（A）
A.正确性B.易读性C.健壮性D.高效性
6．算法在发生非法操作时可以作出处理的特性称为（B）
A.正确性B.健壮性C.易读性D.高效性7．下列时间复杂度中最坏的是（A）
A.O（n2）B.O（log2n）C.O（n）D.O（1）8.算法分析的两个主要方面是（C）。
A.可读性和文档性B.正确性和简明性C.空间复杂性和时间复杂性D.数据复杂性和程序复杂性
n
n
2
3
n


四．分析下面各程序段的时间复杂度
（1）s=0;
for(i=0;iO（n）
for(j=0;jO（n）s=s+B[i][j];
（2）for(i=0;i<n;i++O（n）
for(j=0;i<n;j++
c[i][j]=i+j;O（n）

22
单元测验2
一．判断题（√）（1）在线性表的链式存取结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（×）（3）顺序存储方式的优点是存储密度大，插入、删除效率高→链式存储。（×）（4）链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（√）（5）线性表采用顺序存储，必须占用一片连续的存储单元。（×）（6）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。二．填空题
1．顺序表相对于链表的优点是：节省存储和随机存取。
2．链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。3．在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。
4．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储结构
5．在线性表的链接存储中，元素之间的逻辑关系是通过指针决定的。
6．对一个需要经常进行插入和删除操作的线性表，采用链接存储结构为宜。三．选择题
1．单链表的存储密度（C）。
存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）
A．大于1B．等于1C．小于1D．不能确定
2．已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（A）。
A．B+(i-1*mB．B+i*mC．B-i*mD．B+(i+1*m3．在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（B）。
A．O（1）B．O（n）C．O（n2）D．O（log2n）4．下面关于线性表的叙述中，错误的是（B）关系。
A．顺序表必须占一片地址连续的存储单元B．链表可以随机存取任一元素C．链表不必占用一片地址连续的存储单元D．顺序表可以随机存取任一元素5．链表不具备的特点是（C）。
A．插入删除时不需移动元素B．不必事先估计存储空间C．随机访问D．所需空间与线性表成正比6．用链式存储结构存储的线性表，其优点是（B）。
A．便于随机存取B．便于插入和删除
C．花费的存储空间比顺序表少D．数据元素的物理顺序与逻辑顺序相同



四．程序填空
1、求带头结点的单链表长的算法：
intf(linknode*head,intn{P=head;n=0;While(P->next!=NULL{P=P->next;++n;
}
returnn;}2、在单链表中查找内容为x的结点的算法：
Node*Lsearch(linknode*head,charx
{
P=head;
while(P->next!=NULL&&P->data!=x
P=P->next;
if(P->next==NULL
printf("没有找到!\n";
else
returnP;/*找到，返回结点指针*/
}
3、在带头结点head的单链表的结点a之后插入新元素x：
structNode{
Chardata;Node*next;};
voidListInsert(Node*head,Charx{
node*p,*s;p=head->next;
while(p!=NULL&&(p->data!=aP=P->next;if(p==NULL
printf("不存在结点a，无法插入!\n";


else{
s=(node*malloc(sizeof(node;;//让指针s指向x的地址s->data=x;
s->next=p->next;p->next=s;}}
单元测验3
一．判断题（√）（1）栈是运算受限制的线性表。（√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。（ㄨ）（3）栈一定是顺序存储的线性结构。（√）（4）栈的特点是“后进先出”。（√）（5）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。（ㄨ）（6）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。二．填空题
1．在栈结构中，允许插入、删除的一端称为栈顶。
2．在一个链栈中，若栈顶指针等于NULL，则表示栈空。
3．已知顺序栈S，在对S进行出栈操作之前首先要判断栈是否空。4．从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。
5.顺序栈用data[n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_data[top]=x；top++；
三．选择题1．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，下列不可能的出站顺序为(B
A．1234B．1423C．1324D．12432．顺序栈存储空间的实现使用（B）存储栈元素。
A．链表B．数组C．循环链表D．变量3．如果以链表作为栈的存储结构，则出栈操作时（B）
A．必须判别栈是否满B．必须判别栈是否空C．必须判别栈元素类型D．队栈可不做任何判别
4．一个栈的入栈次序ABCDE，则栈的不可能的输出序列是(D。
A．EDCBAB．DECBAC．ABCDED．DCEAB5、栈与一般线性表的区别在于(C。
A．数据元素的类型不同B．数据元素的个数不同C．操作是否受限制D．逻辑结构不同
6．带头结点的链栈LS的示意图如下，栈顶元素是（A）
Head
C/\ABD
A．AB．BC．CD．D



单元测验4
一．判断题（√）（1）队列是限制在两端进行操作的线性表。（√）（2）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。（×）（3）在循环链队列中无溢出现象。（×）（4）栈和队列都是顺序存储的线性结构。（×）（5）在队列中允许删除的一端称为队尾。（×）（6）顺序队列和顺序循环队列的队满和队空的判断条件是一样的。二．填空题
1．在队列中存取数据应遵从的原则是先进先出。2．在队列中，允许插入的一端称为队尾。3．对于队列，只能在队首删除元素。
4．解决顺序队列“假溢出”的方法是采用循环队列。
5．顺序队列的队头指针为front，队尾指针为rear，则队空的条件为front==rear。6．在一个链队列中，若队头指针与队尾指针的值相同，则表示该队列为空。
7．区分循环队列的满与空，有三种方法，它们是_设计数器_____、_设标志位_____和__少用一个存储空间____。
8.循环队列存储在数组A[m]中，则入队时的操作为rear=(rear+1%m
9．设顺序循环队列的队头指示器front指向队头元素，队尾指示器rear指向队尾元素后的一个空闲元素，队列的最大空间为M，则用牺牲一个存储单元区分队列满与空时，队列为空的标志为front=rear
队满标志为front==(rear+1%M。
10.已知链队列的头尾指针分别是Q->front和Q->rear，则将值x入队的操作序列是p=(LQNode*malloc(sizeof(LQNode；p->data=x;p->next=NULL；Q->rear->next=p(进行连接；Q->rear=p（指针后移）；
三．选择题
1．同一队列内各元素的类型(A。
A．必须一致B．不能一致C．不限制D．可以不一致2．队列是一个(D线性表结构。
A．不加限制的B．推广了的C．非D．加了限制的3．四个元素按：A，B，C，D顺序连续进队Q，执行一次出队操作后，队头元素是（先进先出）（C）。
A．DB．CC．BD．A
4．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为(B。出队一个元素front+1入队一个元素rear+1
A．5和1B．4和2C．2和4D．1和55．以下属于队列的操作有(D。
A．在队首插入元素B．删除值最小的元素
C．按元素的大小排序D．判断是否还有元素
6.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是(C。
A．6B.4C.3D.2


单元测验5

一、选择题
1.若对n阶对称矩阵A(行下标和列下标范围均为1…n，将其下三角形的元素(包括主对角线上所有元素依次存放于一维数组B［0..(n(n+1/2-1］中，则在B中确定aij（i）的位置k的关系为(B。A.i*(i-1/2+j-1B.j*(j-1/2+i-1C.i*(i+1/2+jD.j*(j+1/2+i
注意：1.下标从1开始2.对称矩阵3.i同时满足这三个条件答案为B1.下标从1开始2.对称矩阵3.i>=j同时满足这三个条件答案为A1.下标从0开始2.对称矩阵3.i同时满足这三个条件答案为D1.下标从0开始2.对称矩阵3.i>=j同时满足这三个条件答案为C
2.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（B）
（注意该题下标从1开始：计算10+（4*100+4）*2=818若下标从0开始则结果为1020注意列主序算法的不同）
A.808B.818C.1010D.1020
3.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(B。同下题8行10列填完一列再填下一列到A[4,8]一共60个元素
A.BA+141B.BA+180C.BA+222D.BA+225
4.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,„,8,列下标j=1,2,„,10。若A按行优先存储，元素A[8,5]的起始地址与当A按列优先存储时的元素（B）的起始地址相同。设每个字符占一个字节。
计算方法：该2维数组一共是9行10列即每行10个元素，每列9个元素
行主序（也就是填满一行再填下一行）A[8,5]相当于第（8*10+5）=85个元素当为列主序（即填满一列再填下一列）的时候85/9=9。。。4即可以填满9列还剩4个元素即A[3,10]A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]
5.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储下标序号为1，则a85的下标序号为（B）。
a11a21a22a31a32a33……（若为列主序就是a11a12…a110a21）以此类推。那么a11到a77一共有(1+7*7/2=28个。a81到a85是5个，所以就是33。A.13B.33C.18D.40
6.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（B）。
a(i,j,k其中i是非0元素的行，j是非0元素的列，k是值。在用三元组表示稀疏矩阵，还要三个成员来记住，矩阵的行数列数，总的元素数，所以所需的字节数是10*（1+1+1）*2+3*2=66A.60B.66C.18000D.33

单元测验6



一．判断题（√）（1）二叉树的前序遍历中，任意一个结点均处于其孩子结点的前面。（√）（2）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（√）（3）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。（√）（4）具有n个叶子结点的哈夫曼树共有2n-1个结点。二．填空题
1．在树中，一个结点所拥有的子树数称为该结点的度。2．度为零的结点称为叶结点。
3．由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。4．哈夫曼树是带权路径长度最小的二叉树。
5．已知完全二叉树的第8层有8个结点（根结点计为第1层），则其叶结点数是68。（画图）6．三个结点可以组成2种不同形态的树。
7．将一棵完全二叉树按层次从0开始编号，对于为5的结点，该结点左孩子的编号为：11。左孩子2n+1
8．结点最少的二叉树是空二叉树。
9．对于二叉树来说，第5层上至多有16个结点。2
k+1
10．深度为5的二叉树至多有31个结点。最多→满二叉树2-1最少→单支树k+1
k-1
具有n个结点的满二叉树层数log2(n+1下取整
叶结点数为n0，度为2的结点为n2，则有关系n0=n2+1
三．选择题
1．树最适合用来表示（B）。
A．有序数据元素B．元素之间有分支层次的关系C．元素之间无联系的数据D．无序数据元素2．前序为A，B，C的二叉树共有（A）种。
A．5B．4C．3D．23．根据二叉树的定义，具有3个结点的二叉树有（C）种树型。
A．3B．4C．5D．6
4．将一棵有80个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为0，则编号为38的结点的右孩子编号为（C）。右孩子2n+2
A．76B．77C．78D．795．用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是（B）。（画图）
Ａ．32Ｂ．33Ｃ．34Ｄ．15WPL=4*2+5*2+3*2+2*1+1*1=336．在树结构中，若结点B有3个兄弟，A是B的父亲结点，则A的度为为（B）。
A．3B．4C．5D．67．下列陈述正确的是（C）。
A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分
C．二叉树中最多只有两棵子树，且有左右子树之分D．二叉树中必有度为2的结点8．某二叉树的前序遍历序列为：DABCEFG，中序遍历序列为：BACDFGE，则层次遍历序列为（C）。
A．BCAGFEDB．ABCDEFGC．DAEBCFGD．BCAEFGD


四．应用题
1、某二叉树的结点数据采用顺序存储，其结构如下（其中，“/\”表示结点为空）：
0A
123456789BC/\DEF/\/\G

请画出该二叉树，并分别写出按前序、中序、后序、层序遍历的结点序列。解法：按照满二叉树写出编号，然后依次填充。
2、已知一棵二叉树的中序遍历结点序列为BFDGAEHC，后序遍历结点序列为FGDBHECA。
请画出此二叉树，并写出该树的前序遍历结点序列。
ABDFGCEH
3．已知一棵二叉树的后序遍历和中序遍历的序列分别为：
A，C，D，B，G，I，H，F，E和A，B，C，D，E，F，G，H，I。请画出该二叉树，并写出它的前序遍历的序列。答：恢复的二叉树为：EBFHAD
CGI

其前序遍历的序列为：EBADCFHGI4．已知一棵二叉树的前序遍历和中序遍历的序列分别为：
A，B，D，G，H，C，E，F，I和G，D，H，B，A，E，C，I，F。请画出此二叉树，并写出它的后序遍历的序列。。
答：恢复的二叉树为：
A

BC

FDE
GHI
其后序遍历的序列为：GHDBEIFCA
5．已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF，请画出该二叉树，并写出它的后序遍历的序列。解：后序遍历的序列：DGJHEBIFCA
A
BCDFE
G
H
IJ


6、某二叉树的结点数据采用顺序存储，其结构如下：
1234567891011121314151617181920EAF
D
H

C



G
I




B
（1）画出该二叉树（3分）
（2）写出按层次遍历的结点序列（2分）解：
E（1）
A

lchilddatarchild
10J0
DCB
GF
H
I
（2）层次遍历的结点序列：EAFDHCGIB
7、某二叉树的存储如下：
20H0
32F0
43D9
57B4
65A0
78C0
80E0
910G0
101I0
其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为数据域。（1）画出该二叉树（3分）
A
（2）写出该树的前序遍历的结点序列（2分）（1）解：（2）前序遍历的结点序列：ABCEDFHGIJ
B

CD

EF

G

H
J
I


哈夫曼树的构造方法：依次选择权值最小和次小的数的数分别作为二叉树的左右孩子WPL的计算以及哈弗曼编码
3．给定一个权集W={4，5，7，8，6，12，18}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。
解：456781218
60

913
2535

17
12131718
25
9678
35
54
60
WPL=(12+18*2+(6+7+8*3+(4+5*4=159
4．给定一个权集W={3，15，17，14，6，16，9，2}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。解
82236914151617

3349
52933
29161720
11
9111415
20
65
49

82
WPL=(16+17*2+(9+14+15*3+6*4+(2+3*5=229
5．假设用于通信的电文仅由A、B、C、D、E、F、G、H8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树：100
01

字母编号
40A60011
0B
2119C2832
01D
E1117
100F1
2
3
对应编码1010001000010011110001011011
出现频率
719263232110

0
51
2
3
6710

GH




单元测验7
一．判断题（ㄨ）（1）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。（ㄨ）（2）邻接表只能用于有向图的存储。（√）（3）一个图的邻接矩阵表示是唯一的。（ㄨ）（4）有向图不能进行广度优先遍历。（√）（5）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。二．填空题
1．图有：邻接矩阵和邻接表等常用存储方式。
2．图的遍历有：深度优先搜索和广度优先搜索等方法。
3．图的邻接矩阵表示法是表示__顶点____之间相邻关系的矩阵。
4．有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的__出度____。5．有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点i的入度。6．设有一稀疏图G，则G采用_邻接表____存储比较节省空间。7．设有一稠密图G，则G采用_邻接矩阵____存储比较节省空间。
8．n个顶点的有向完全图有n（n-1）条边。若为无向图则有n（n-1/2条边9．对于具有n个顶点的图，其生成树有且仅有n-1条边。10．无向图的邻接矩阵一定是对称矩阵。三．选择题
1．在下列表示方法中，（D）是有向图边的表示方法。
A．（1，2）B．（1，2>C．<1，2）D．<1，2>
2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(B倍。
A．1/2B.1C.2D.4
3．对于一个具有n个顶点的无向图的边数最多有（B）。
A．nB．n（n-1）/2C．n（n-1）D．2n
4．在一个具有n个顶点的无向图中，要连通全部顶点至少需要（B）条边。
A．nB．n-1C．n+1D．n/25．有8个结点的有向完全图有(C条边。n（n-1）
A．14B.28C.56D.1126．无向图顶点v的度是关联于该顶点（B）的数目。
A．顶点B．边C．序号D．下标7．有n个顶点的无向图的邻接矩阵是用（B）数组存储。
A．一维B．n行n列C．任意行n列D．n行任意列8．在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（C）。举例得出结论即可
A．eB．nC．2eD．2n


四．应用题1．根据如下无向图
（1）画出该图的邻接矩阵和邻接表
（2）并分别给出该图邻接矩阵下的深度优先搜索遍历和广度优先搜索遍历的结点序列。

邻接矩阵






邻接表表示方法



ABCDEFG
A→B→CB→A→DC→A→D
A0110000B1011000C1001000D0110110E0001001F0001001G0000110深度优先遍历ABDCEGF广度优先遍历ABCDEFG
D→B→C→E→FE→D→GF
→D→G




G→E→F

2．分别用普里姆(Prim算法和克鲁斯卡尔(Kruskal算法画出构造该无向带权图最小生成树的过程。





单元测验8
一．判断题（ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实际应用价值。（√）（2）对n个记录的进行快速排序，所需要的平均时间是O（nlog2n）。（ㄨ）（3）堆排序所需的时间与待排序的记录个数无关。（√）（4）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。（√）（5）对快速排序来说，初始序列为递增有序或递减有序都是最坏情况。（√）（6）采用希尔方法排序时，若关键字的排列杂乱无序，则效率较高。二．填空题
1．大多数排序算法都有两个基本的操作：比较和移动。2．对n个关键字进行冒泡排序，时间复杂度为O（n2）。3．快速排序在最坏情况下的时间复杂度是O（n2）。
4．在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定的排序方法。
5．当增量为1时，该趟希尔排序与直接插入排序基本一致。
6．第一趟排序后，序列中键值最大的记录交换到最后的排序算法是冒泡排序。
7．依次将待排序的每个记录插入到一个有序已排序序列中的排序方法称为插入排序。
8．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较3次。
有序区[152338547296]无序区[604583]待插入元素60先和96比较再和72比较最后和54比较9．两个序列分别为：L1={25，57，48，37，92，86，12，33}交换15次
L2={25，37，33，12，48，57，86，92}交换4次
用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：L2。
10．对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是54，72，60，96，80。第一次有序区[12]无序区[3596215472604480]第二次有序区[1221]无序区[96355472604480]第三次有序区[122135]无序区[965472604480]第四次有序区[12213544]无序区[5472609680]

三．选择题
1．排序是根据（A）的大小重新安排各元素的顺序。
A．关键字B．数组C．元素件D．结点
2．排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为(B。
A．插入排序B．选择排序C．希尔排序D.快速排序
3．每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（D）。
A．冒泡排序B．堆排序C．希尔排序D.快速排序4．快速排序在（C）情况下最易发挥其长处。
A．待排序的数据中含有多个相同的关键字B．待排序的数据已基本有序
C．待排序的数据完全无序D．待排序的数据中最大值与最小值相差悬殊5．直接插入排序的方法是从第（B）个元素开始，插入到前边适当位置的排序方法。
A．1B．2C．3D．n第一个元素初始时已经选定为a[0]6．堆的形状是一棵（C）。


A．二叉排序树B．满二叉树C．完全二叉树D．任意二叉树
7．内排序是指在排序的整个过程中，全部数据都在计算机的（A）中完成的排序。
A．内存B．外存C．内存和外存D．寄存器外排序则是将数据部分导入内存依次排序
8．下述几种排序方法中，平均时间复杂度最小的是（A）。
A．希尔排序O(nB．直接插入排序C．冒泡排序D．直接选择排序9．对n个数据进行快速排序，在最坏情况下，算法的时间复杂度是（B）。
A．O(nB．O(n2C．O(nlog2nD．O(n3
10．冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（C）次。
A．1B．2C．n-1D．n
11．用直接插入排序法对下面的四个序列进行由小到大的排序，元素比较次数最少的是（B）。
A，94，32，40，90，80，46，21，69B．21，32，46，40，80，69，90，94C．32，40，21，46，69，94，90，80D．90，69，80，46，21，32，94，4012．一个数据序列的关键字为：（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：（C）以46(Low为基准进行第一次快速排序(递归→先右后左
A．（38，40，46，56，79，84）B．（40，38，46，79，56，84）C．（40，38，46，56，79，84）D．（40，38，46，79，56，84）四．应用题
1．已知数据序列{80，18，9，90，27，75，42，69}，试写出采用冒泡排序（从小到大）算法排序时，每一趟排序的结果。第一次189802775426990第二次918277542698090第三次918274269758090
2．已知数据序列{40，63，11，84，35，93，58，39}，试写出采用直接选择排序（从小到大）每一趟排序结果。
第一次1163408435935839第二次1135408463935839第三次1135398463935840第四次1135394084639358第五次1135394058639384第六次1135394058639384第七次1135394058638493第八次1135394058638493
3．已知数据序列{12，2，16，30，28，10，17，20}，写出希尔排序（从小到大）每一趟（设d=4,2,1）的排序结果。
第一次122162028101730第二次122161017202830第三次212101617202830
4．已知数据序列{10，1，15a，18，7，15b}(ab为了区别两个15，试写出采用快速排序（从小到大）每一趟排序的结果。第一次17101815a15b第二次171015b15a18
1.3


5．已知数据序列{18，17，60，40，07，32，73，65}，试写出采用直接插入排序（从小到大）每一趟排序结果。
第一次1817604007327365
第二次1718604007327365
第三次1718604007327365
第四次1718406007327365
第五次0717184060327365
第六次0717183240607365
第七次0717183240607365
第八次0717183240606573
五．程序填空
1．直接选择排序
VoidSelectSort(DataTypea[],intn
{
inti,j,small;
DataTypetemp;
for(i=0;i
{
Small=i;
for(j=i+1;j
if(a[j].key
small=j;if(small!=i{temp=a[i];a[i]=a[small];a[small=temp;}}}

2、直接插入排序VoidInsertSort(DataTypea[],intn{inti,j;DataTypetemp;for(i=0;i{temp=a[i+1];j=i;while(j>-1&&temp.key{a[j+1]=a[i];j--;}a[j+1]=temp;}}3、冒泡排序VoidBubbleSort(DataTypea[],intn{inti,j,flag=1;DataTypetemp;for(i=0;i{
flag=0;for(j=0;j{if(a[j].key>a[j+1].key{flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}


单元测验9
一．判断题（√）（1）二分查找法要求待查表的关键字值必须有序。（ㄨ）（2）对有序表而言采用二分查找总比采用顺序查找法速度快。慢（ㄨ）（3）在二叉排序树中，根结点的值都小于孩子结点的值。小于右孩子结点的值（√）（4）哈希表是一种将关键字转换为存储地址的存储方法。（√）（5）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。（ㄨ）（6）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。二．填空题
1．在分块查找方法中，首先查找索引表，然后再查找相应的块。2．顺序查找、二分查找、分块查找都属于静态查找。
3．对于长度为n的线性表，若进行顺序查找，则时间复杂度为O（n）。
4．对于长度为n的线性表，若采用二分查找，则时间复杂度为：O（log2n）。
5．在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较
4次才找到。
第一次mid=（low+high）/2=3查找a[3]=18,low=mid+1=4第二次mid=（low+high）/2=5查找a[5]=36,low=mid+1=6第三次mid=（low+high）/2=6查找a[6]=45,low=mid+1=7第四次mid=（low+high）/2=7查找a[7]=92.
6．对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点小，则继续在左子树中查找。
7．二叉排序树是一种动态查找表。
8．哈希法既是一种存储方法，又是一种查找方法。
9．设哈希函数H(k和键值k1，k2，若k1≠k2，且H（k1）=H（k2），则称这种现象为哈希冲突。10．处理冲突的两类主要方法是开放定址法和链表法。
11．在哈希函数H(key=key%P中，P一般应取质数。为了最大情况避免哈希冲突12．在查找过程中有插入元素或删除元素操作的，称为动态查找。三．选择题
1．对线性表进行二分查找时，要求线性表必须（B）。
A．以顺序方式存储B．以顺序方式存储，且结点按关键字有序排序C．以链接方式存储D．以链接方式存储，且结点按关键字有序排序2．衡量查找算法效率的主要标准是（C）。
A．元素个数B.所需的存储量C．平均查找长度D．算法难易程度
3．有一个有序顺序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为
82的结点时，(C次比较后查找成功。解法同填空5A．2B．3C．4D．5
4．下列（D）不是利用查找表中数据元素的关系进行查找的方法。
A．顺序表的查找B．有序顺序表的查找C.二叉排序树的查找D．哈希查找
5．在查找过程中，若同时还要做增加、删除工作，这种查找称为（C）。
A．静态查找B.内查找C．动态查找D．外查找
6．已知8个元素为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一棵二叉排序树，最后两层上结点的总数为（B）。生成二叉排序树的过程
A．1B．2C.3D．4


7．下列那种查找方法不属于静态查找（D）。
A．顺序查找B.二分查找
C．分块查找D．二叉排序树8．设哈希表长n=14，哈希函数H（k）=k％11。表中已有4个结点：H(15=4,H(38=5,H(61=6,H(84=7,其余地址为空。如用线性探查法处理哈希冲突，关键字为49的结点的地址是（A）。
A．8B．3C．5D．9(49+1+1+1%11=8四．应用题
1．在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4。
（1）画出此二叉排序树
（2）写出此二叉排序树的中序遍历序列将该数组从小到大排列即可2．给定结点的关键字序列为：42，18，9，4，8，20，14，97。
设哈希表的长度为12，哈希函数为：H（K）=K%12，冲突采用线性探查法，请写出最终的哈希地址表。
解：最终的哈希地址表如下所示：
01234567891011

9714
4
42188920

2．给定结点的关键字序列为：87，25，11，8，27，28，68，95，70，6，83，63，47，设哈希函
数为：H（K）=K%13，试画出链表法解决冲突时所构造的哈希表
下标DataLinkDataLink0123456789101112

272868706958871125
∧∧∧∧∧→∧∧→∧∧→∧
834763
∧∧∧



五．程序填空
1、在顺序表L[n]中查找数据x，找到则返回元素位置，没找到则返回-1#include"SeqList.h"
intSeqList(SeqlistSDataTypex{inti=0;while(i<S.size&&S.[list].key!=x.keyi++;if(S.list[i].key==x.keyreturni;elsereturn-1;}
2、在长度为n的、升序排列的有序表R中，二分查找内容为x的结点。#include"SeqList.h"
intBinarySrarch(SeqlistSDataTypex{intlow=0,high=n-1;intmid;while(low{mid=(low+high/2;//确定查找位置if(S.list[mid].key==x.keyreturnmid;elseif(S.list[mid].keylow=mid+1;elseif(S.list[mid].key>x.keyhigh=mid-1;}return-1;//查找失败}

本文来源：https://www.2haoxitong.net/k/doc/6759eae4b9f3f90f76c61b8f.html

《数据结构考试.doc》
将本文的Word文档下载到电脑，方便收藏和打印
推荐度：
点击下载文档

文档为doc格式
相
关
案
例

相关推荐

推荐内容

社区出生缺陷工作计划 工程合同财务审核 标准考勤制度 2022年给女朋友的道歉信(集锦15篇)【多篇】 幼儿园大班诗歌教案五篇 采购申请审批流程 新高考2022届物理备考专题：万有引力解题中的“一模、两路、三角”【权威预测,冲刺985精品】 人体内脏结构人体全息示意图 钢材买卖合同范本 轻度抑郁可以治好吗 [“金庸”治好我的轻度抑郁]
网站内容来自网络，如有侵权请联系我们，立即删除！ Copyright © 范文写作网京ICP备16605803号