数据结构全国2014年4月高等教育自学考试

1、全国2014年4月高等教育自学考试一、单项选择题(本大题共15小题，每小题2分，共30分)1.下列几种算法时间复杂度中，最小的是A.O(log2n)B.O(n)C.O(n2)D.O(1)2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有A.索引存储方式和树形存储方式B.线性存储方式和散列存储方式C.线性存储方式和索引存储方式D.索引存储方式和散列存储方式3.表长为n的顺序表中做删除运算的平均时间复杂度为A.O(1)B.O(log2n)C.O(n)D.O(n2)4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为A.O(1)B.O(log2n)C.O(n)D.O(n2)

2、5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为A.DB.CC.BD.A6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL7.深度为5的二叉树，结点个数最多为A.31个B.32个C.63个D.64个8.如果结点A有2个兄弟结点，结点B为A的双亲，则B的度为A.1B.3C.4D.59.将题9图所示的一棵树转换为二叉树，结点C是A.A的左孩子B.A的右孩子C.B的右孩子D.E的右孩子10.n为图的顶点个数，e为图中弧的数目，则图

3、的拓扑排序算法的时间复杂度为A.O(n)B.O(e)C.O(n-e)D.O(n+e)11.无向图的邻接矩阵是A.对角矩阵B.稀疏矩阵C.上三角矩阵D.对称矩阵12.在具有101个元素的顺序表中查找值为x的元素结点时，平均比较元素的次数为A.50B.51C.100D.10113.构造散列函数的方法很多，常用的构造方法有A.数字分析法、除留余数法、平方取中法B.线性探测法、二次探测法、除留余数法C.线性探测法、除留余数法、链地址法D.线性探测法、二次探测法、链地址法14.就平均时间性能而言，快速排序方法最佳，其时间复杂度为A.O(n)B.O(nlog2n)C.O(n2)D.O(1og2n)15.下

4、述算法中，不稳定的排序算法是A.直接插入排序B.冒泡排序C.堆排序D.归并排序二、填空题(本大题共13小题，每小题2分，共26分)16.数据的基本单位是_。17.双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为t->prior=P；t->next=p->next；_；p->next=t；。18.在带有头结点的循环链表中，尾指针为rear，判断指针P所指结点为首结点的条件是_。19.若线性表中最常用的操作是求表长和读表元素，则顺序表和链表这两种存储方式中，较节省时间的是_。20.不含任何数据元素的栈称为_。21.稀疏矩阵一般采用的压缩存储方法

5、是_。22.100个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有_个。23.已知完全二叉树的第5层有5个结点，则整个完全二叉树有_个结点。24.n个顶点的有向图G用邻接矩阵A1.n，1.n存储，其第i列的所有元素之和等于顶点Vi的_。25.具有10个顶点的有向完全图的弧数为_。26.要完全避免散列所产生的“堆积现象，通常采用_解决冲突。27.在长度为n的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为_。28.归并排序算法的时间复杂度是_。三、应用题(本大题共5小题，每小题6分，共30分)29.稀疏矩阵A如题29图所示，写出该稀疏矩阵A的三元组表示法。30

6、.设二叉树的中序遍历序列为BDCEAFHG，后序遍历序列为DECBHGFA，试画出该二叉树。31.写出题31图所示无向图的邻接矩阵，并写出每个顶点的度。32.已知散列表的地址空间为0至13，散列函数H(k)=kmod11，(mod为求余运算)，待散列序列为(26，61，38，84，49)，用二次探测法解决冲突，构造该序列的散列表，要求写出处理冲突的过程。33.将一组键值(80，50，65，13，86，35，96，57，39，79，59，15)应用二路归并排序算法从小到大排序，试写出各趟的结果。题31图全国2014年4月高等教育自学考试一、单项选择题（本大题共15小题，每小题2分，共30分）1.

7、与数据存储结构无关的概念是A.栈B.链表C.顺序表D.二叉链表2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是A1010B.1016C.1018D.10193.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是A.2B.3C.4D.64.下列关于队列的叙述中,错误的是A.队列是一种先进先出的线性表B.队列是一种后进后出的线性表C.循环队列中进行出队操作时要判断队列是否为空D.在链队列中进行入队操作时要判断队列是否为满5.对稀疏矩阵进行压缩存储的目的是A.便于运算B.

8、节省存储空间C.便于输入输出D.降低时间复杂度6.一棵二叉树的第7层上最多含有的结点数为A.14B.64C.127D.1287.下列选项为完全二叉树的是8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是A. n×eB. eC. 2eD. n+e9.无向图中所有顶点的度数之和与所有边数之比是A.1/2B.1C.2D.410.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为A. O（n）B. O（n+e）C. O（n2）D. O（n3）11.对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是A.

9、归并排序B.快速排序C.直接选择排序D.冒泡排序12.比较次数与待排序列初始状态无关的排序方法是A.快速排序B.冒泡排序C.直接插入排序D.直接选择排序13.查找较快,且插入和删除操作也比较方便的查找方法是A.分块查找B.二分查找C.顺序查找D.折半查找14.下列关于m阶B树的叙述中,错误的是A.根结点至多有m棵子树B.所有叶子都在同一层次上C.每个非根内部结点至少有棵子树D.结点内部的关键字可以是无序的15.在散列查找中处理冲突时,可以采用开放定址法。下列不是开放定址法的是A.线性探查法B.二次探查法C.双重散列法D.拉链法二、填空题（本大题共10小题,每小题2分,共20分）16.数据结构研

10、究的内容包括数据的逻辑结构、_和数据的运算。17.头指针为L的带头结点的双循环链表,结点的前趋指针域为prior,后继指针域为next,判断该链表为空的条件是_。18.普里姆（Prim）算法完成的功能是求图的_。19.若三维数组a456的基地址是100,每个元素占用2个存储单元,则数组a中最后一个元素的存储地址是_。20.二叉树的线索链表利用_存放遍历时得到的前趋或后继结点的指针。21.采用邻接矩阵存储n个顶点e条边的无向图,其邻接矩阵的大小为_。22.若无向图中任意两个不同的顶点间都有路径,则称该图为_。23.在直接插入排序、冒泡排序和快速排序中,平均时间性能最佳的是_。24.假设m个关键字

11、互为同义词,若用线性探查法把这m个关键字存入散列表中,至少要进行的探查次数是_。25.顺序查找算法的平均时间复杂度为_。三、解答题（本大题共4小题,每小题5分,共20分）26.用X代表进栈操作,S代表出栈操作。给出利用栈将字符串"a*b-c"改变为"ab*c-"的操作步骤。例如：将"ABC"改变为"BCA",则其操作步骤为XXSXSS。27.假定电文字符集为A,B,C,D,E,F,G,H,它们在电文中出现的次数分别为19,6,12,5,38,3,13,4）,为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在

12、构造哈夫曼树的过程中,权值较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1。28.设图以邻接表存储,如题28图所示。（1）写出从顶点v1出发图的深度优先搜索遍历序列。（2）写出从顶点v1出发图的广度优先搜索遍历序列。29.（1）一个排序方法稳定的含义是什么？（2）快速排序是稳定的吗？举例说明。全国2013年10月高等教育自学考试一、单项选择题(本大题共15小题，每小题2分，共30分)1下列几种算法时间复杂度中，最大的是AO（1）B.O（n）C.O（nlog2n）D.O（n2）2数据结构中结点按逻辑关系依次排列形成一条“链”的结构是A集合B.图结构C.树形结构D.线性结构3在表长为10

13、0的顺序表中做插入运算，平均移动元素的次数为A25B.33C.50D.1004已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为AO（1）B.O（log2n）C.O（n）D.O(n2)5下列表述正确的是A栈空时出栈产生“上溢”，栈满时进栈产生“下溢”B.栈空时出栈产生“下溢”，栈满时进栈产生“上溢”C.栈空时出栈和栈满时进栈均产生“上溢”D.栈空时出栈和栈满时进栈均产生“下溢”6.队列操作的原则是A.先进先出B.后进先出C.先进后出D.只进不出7一棵深度为6的满二叉树有A63个结点B.64个结点C.127个结点D.128个结点8.在一棵度为3的树中，度为3的结点有

14、4个，度为2的结点有2个，度为1的结点有3个，则度为0的结点有A.8个B.10个C.11个D.12个9一棵二叉树T，度为2的结点数为20个，则叶子结点数为A19个B.20个C.21个D.22个10有10个叶结点的哈夫曼树中共有A10个结点B.11个结点C.19个结点D.21个结点11求图中两个结点之间的最短路径采用的算法是A广度优先搜索（BFS）算法B.克鲁斯卡尔（Kruskal）算法C.普里姆（Prim）算法D.迪杰斯特拉（Dijkstra）算法12顺序查找算法的平均查找长度为Alog2nB.（n-1）/2C.n/2D.（n+1）/213二叉排序树中，根的A左子树是二叉排序树、右子树不一定是

15、二叉排序树B.左子树是二叉排序树、右子树也是二叉排序树C.左子树不一定是二叉排序树、右子树是二叉排序树D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树14冒泡排序的时间复杂度为AO(n)B.O(nlog2n)C.O(n2)D.O(log2n)15关于稳定性的表述，正确的是A稳定性是排序方法本身的特性，与数据无关B.稳定性不是排序方法本身的特性，与数据有关C.稳定性是排序方法本身的特性，与数据有关D.稳定性不是排序方法本身的特性，与数据无关二、填空题(本大题共13小题，每小题2分，共26分)16数据中不可分割的最小标识单位是_。17双向循环链表中，在p所指结点的后面插入一个新结点*t，需

16、要修改四个指针，分别为：t->prior=p；_；p->next->prior=t；p->next=t；。18.在带有头结点的循环链表中，头指针为head，判断指针p所指结点为首结点的条件是_。19元素的进栈次序为1，2，3，n，出栈的第一个元素是n，则第k个出栈的元素是_。20在栈结构中，允许插入和删除的一端称为_。21100个结点的二叉树采用三叉链表存储时，空指针域NULL有_个。22.某二叉树的先序遍历序列为ABKLMNO，中序遍历序列为BLKANMO，则该二叉树中结点A的右孩子为结点_。23一个二叉树的最少结点个数为_。24图中第一个顶点和最后一个顶点相同的路径

17、称为回路。除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为_。25设查找表有n个数据元素，则二分查找算法的平均查找长度为_。26用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为_。27若在线性表中采用二分查找法查找元素，则该线性表必须按值有序，并且采用_存储结构。28堆分为最小堆和最大堆，若键值序列k1,k2,，kn，满足，则这n个键值序列k1,k2,，kn是_。三、应用题(本大题共5小题，每小题6分，共30分)29设一个链栈的输入序列为X，Y，Z，试写出出栈的所有可能的输出序列及其操作步骤。30设二叉树的先序遍历序列为DCBAHEIFG，中序遍历序列为ABCHDIE

18、FG，试画出该二叉树并写出后序遍历序列。31已知连通带权图如题31图所示，试利用普里姆（Prim）算法，从顶点A出发，构造它的最小生成树，画出构造过程。题31图32给定表（28，15，55，3，71，75，10，22，56），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。33应用直接选择排序算法，对初始关键字序列为48，35，61，98，82，18，29，48的记录进行从小到大排序，写出排序过程和结果。全国2013年10月高等教育自学考试一、单项选择题(本大题共15小题，每小题2分，共30分)1算法的时间复杂度表征的是A算法的可读性 B算法的难易程度

19、C执行算法所耗费的时间 D执行算法所耗费的存储空间2对需要频繁插入和删除结点的线性表，适合的存储方式是A顺序储存 B链式存储C索引存储 D散列存储3在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是Ap->next->next=head Bp->next=headCp->next->next=NULL Dp->next=NULL 4迪杰斯特拉(Dijkstra)算法的功能是A求图中某顶点到其他顶点的最短路径B求图中所有顶点之间的最短路径C求图的最小生成树 D求图的拓扑排序序列5若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能获得的出栈

20、序列是A4，5，3，2，1 B4，3，5，1，2C1，2，3，4，5 D5，4，3，2，16A是7×4的二维数组，按行优先方式顺序存储，元素A00的存储地址为1 000，若每个元素占2个字节，则元素A33的存储地址为A1015 B1016C1028 D10307深度为4的完全二叉树的结点数至少为A4 B8C13 D158若采用邻接矩阵A存储有向图G，则结点k的入度等于A中A结点k对应行元素之和 B结点k对应列元素之和C结点k对应行和列元素之和 D非零元素之和9无向图G的邻接矩阵一定是A对称矩阵 B对角矩阵C三角矩阵 D单位矩阵10下列关于有向带权图G的叙述中，错误的是A图G的任何一棵

21、生成树都不含有回路B图G生成树所含的边数等于顶点数减1C图G含有回路时无法得到拓扑序列D图G的最小生成树总是唯一的11在下列排序算法中，关键字比较次数与初始排列次序无关的是A冒泡排序 B希尔排序C直接插入排序 D直接选择排序1 2对下图进行拓扑排序，可以得到的拓扑序列是Aa b c d e Bb a c d eCb c a d e Da b d c e13下列线性表中，能使用二分查找的是A顺序存储(2,12,5,6,9,3,89,34,25)B链式存储(2,12,5,6,9,3,89,34,25)C顺序存储(2,3,5,6,9,12,25,34,89)D链式存储(2,3,5,6,9,12,25

22、,34,89)14在下列查找方法中，平均查找长度与结点数量无直接关系的是A顺序查找 B分块查找C散列查找 D基于B树的查找15下列排序算法中，时间复杂度为O(nlog2 n)的算法是A快速排序 B冒泡排序C直接选择排序 D直接插入排序二、填空题(本大题共10小题，每小题2分，共20分)1 6数据的同一种逻辑结构，可以对应多种不同的_。17若在长度为n的顺序表第i个元素之前插入一个元素，则需要向后移动的元素个数是_。18顺序栈存放在Sm中，S0为栈底，栈顶指针top初始值为-1，则栈满的条件是top= _。19队列只能在队尾进行插入操作，在队首进行_操作。20广义表A=(x，(y，z)，a，b)

23、，则函数head(head(tail(A)的值是_。21以权值分别为4，3，2，1的四个叶子结点构成的哈夫曼树，其带权路径长度WPL是_。22图的遍历方法有两种，一种是深度优先遍历，另一种是_。23如果排序算法是稳定的，则关键字相同的两个记录排序前后相对次序_。24己知散列表表长m=11，散列函数h(key)=key11，表中存有三个关键字15，27，39，其余地址为空，若采用线性探查法处理冲突，则关键字为60的结点保存的地址是_。25己知图G的邻接表如题25图所示。从顶点v1出发进行深度优先搜索，得到的深度优先搜索序列是_三、解答题(本大题共4小题，每小题5分，共20分)26设QM是有M个元

24、素存储空间的循环队列，若front指向队首元素，rear指向队尾元素的下一位置，请分别用C语言描述下列操作：(1)将元素x入队；(2)将队首元素出队，并保存到变量y中；(3)计算当前队列中元素个数。27己知带权图G=(VE)，其中V=(A，B，C，D，E)，邻接矩阵如下(1)画出对应的图G(2)画出图G的最小生成树28已知一组待排记录的关键字序列为(15，11，17，59，14，35，13，17，24，84)，请给出对应的小根堆序列。29已知二叉树如题29图，请画出该二叉树的前序线索。全国2013年1月高等教育自学考试一、单项选择题(本大题共15小题，每小题2分，共30分)1.数据的基本单位是

25、A.数据元素B.数据项C.字段D.域2.算法的空间复杂度是指A.算法中输入数据所占用的存储空间的大小B.算法本身所占用的存储空间的大小C.算法中所占用的所有存储空间的大小D.算法中需要的辅助变量所占用存储空间的大小3.从一个长度为100的顺序表中删除第30个元素,需向前移动的元素个数为A.29B.30C.70D.714.若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是A.单链表B.双链表C.单循环链表D.顺序表5.判断链栈LS是否为空的条件是A.LS->next= =LSB.LS->next= =NULLC.LS! =NULLD.LS= =NULL6.

26、关于链队列的运算说法正确的是A.入队列需要判断队列是否满B.出队列需要判断队列是否空C.入队列需要判断队列是否空D.出队列需要判断队列是否满7.元素的进栈次序为A,B,C,D,E,则出栈中不可能的序列是A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A8.具有63个结点的完全二叉树是A.满二叉树B.二叉排序树C.哈夫曼树D.空树9.将含有80个结点的完全二叉树从根这一层开始,每层从左到右依次对结点编号,根结点的编号为1。则关于编号40的结点的左右孩子的说法正确的是A.左孩子编号为79，右孩子编号为80B.左孩子不存在，右孩子编号为80C.左孩子编号为80，

27、右孩子不存在D.左孩子不存在，右孩子不存在10.将题10图所示的一棵树转换为二叉树，结点D是A.A的右孩子B.B的右孩子C.C的右孩子D.E的右孩子11.无向图的邻接矩阵是 题10图A.对称矩阵B.稀疏矩阵C.对角矩阵D.上三角矩阵12.图的广度优先搜索遍历的过程类似于树的A.前序遍历B.中序遍历C.后序遍历D.按层次遍历13.要解决散列引起的冲突问题，最常用的方法是A.数字分析法、除留余数法、平方取中法B.除留余数法、线性探测法、平方取中法C.线性探测法、二次探测法、链地址法D.除留余数法、线性探测法、二次探测法14.下列表述中，正确的是A.序列（102，81，55，62，50，40，58，

28、35，20）是堆B.序列（102，81，55，62，50，40，35，58，20）是堆C.序列（102，81，55，58，50，40，35，62，20）是堆D.序列（102，71，55，40，50，62，35，58，20）是堆15.下列算法中，不稳定的排序算法是A.冒泡排序B.快速排序C.直接插入排序D.二路归并排序二、填空题(本大题共13小题，每小题2分，共26分)16.下面算法程序段的时间复杂度为_。for(i=1;i<=n;i+)for(j=1;j<=i;j+)x=aij;aij=aji;aji=x;17.设p指向单链表的最后一个结点，要在最后一个结点之后插入q所指的结点，需

29、执行的语句序列是p->next=q;_;p->next=NULL。18.向一个长度为100的顺序表中第50个元素之前插入一个元素时，需向后移动的元素个数为_。19.一个带头结点的链栈LS，现将一个新结点入栈，指向该结点的指针为p，入栈操作为p->next=LS->next和_。20.队列操作的原则是_。21.含有n个顶点的连通图中的任意一条简单路径，其最大长度为_。22.在一棵度为3的树中，度为3的结点数为1个，度为2的结点数为2个，度为1的结点数为3个，则度为0的结点数为_个。23.某二叉树的中序遍历序列为BACDEFGH，后序遍历序列为BCAEDGHF，则根结点F的

30、左子树上共有_个结点。24.设有向图G的邻接矩阵为A,如果<Vi,Vj>是图中的一条弧,则Aij的值为_。25.一个有序表A含有15个数据元素，且第一个元素的下标为1，按二分查找算法查找元素A14，所比较的元素下标依次是_。26.用n个值构造一棵二叉排序树，它的最大深度为_。27.设记录数为n，则冒泡排序算法在最好情况下所作的比较次数为_。28.二路归并排序算法的时间复杂度为_。三、应用题(本大题共5小题，每小题6分，共30分)29.设有编号为A，B，C，D的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出站台的所有可能的顺序。30.已知一棵二叉树的先序遍历序列为ABCD

31、EFGHK，中序遍历序列为CBEDFAGKH，试建立该二叉树并写出它的后序遍历序列。31.利用克鲁斯卡尔（Kruskal）算法构造题31图的最小生成树，画出它的构造过程。题31图32.给定表（27，19，50，1，75，12，40，90，66，32，22），试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。33.对初始关键字序列48，39，68，95，88，12，27，48的记录进行冒泡排序（升序），给出排序过程。全国2013年1月高等教育自学考试一、单项选择题（本大题共15小题，每小题2分，共30分）1数据的逻辑结构可以分为A动态结构和静态结构B.顺序

32、结构和链式结构C线性结构和非线性结构D.简单结构和构造结构2线性表是一个有限序列，组成线性表的基本单位是A数据项B.数据元素C数据域D.字符3栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可能的出栈序列是AdcbaB.cbdaCcadbD.cdba4稀疏矩阵的三元组表是A顺序存储结构B.链式存储结构C索引存储结构D.散列表存储结构5已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是A5B.6C7D.86下列编码集合中，属于前缀编码的一组是A.11,10,001,101,0001B.00,010,0110,1000C.11,01,001,0101,

33、0001D.0,10,110,10117.如题7图所示二叉树的中序序列为AACDBBDCBACCDBADABCD题7图8有向图中所有顶点入度之和与所有顶点出度之和的比是A1/2B.1C2D.49含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是A.eB.2eC.n2-2eD.n2-e10.n个顶点的无向连通图，其生成树的边数为A.n-lB.nC.n+lD.nlogn11用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为A2B.3C4D.512对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是A.(1

34、3,44,55,26,8,29)B.(13,26,55,44,8,29)C.(8,13,26,29,44,55)D.(29,26,8,44,55,13)13采用分块查找时，要求数据A块内有序B.分块有序C分块无序D.每块中数据个数必须相同14.下列关于散列函数的说法正确的是A散列函数越复杂越好B.散列函数越简单越好C用除余法构造的散列函数是最好的D.在冲突尽可能少的情况下，散列函数越简单越好15.下列关于m阶B树的叙述中，错误的是A每个结点至多有m棵子树B.每个结点至多有m-1个关键字C所有的叶结点均在同一层上D.根结点至少有棵子树二、填空题（本大题共10小题，每小题2分，共20分）16算法的

35、时间复杂度与实现时采用的程序设计语言_。17在长度为n的顺序表的第i(1in)个元素之后插入一个元素时，需向后移动_个元素。18设循环队列存放在向量data0.m-l中，在出队操作后，队头指针front变化为_。19树的前序遍历序列等同于该树对应二叉树的_遍历序列。20一个100×90的整型稀疏矩阵有10个非零元素，设每个整型数占2个字节，则用三元组表存储该矩阵时，所需的字节数是_。21当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是_。22采用邻接表表示n个顶点的有向图时，若表结点的个数为m，则该有向图的边数为_。23对同一个基本有序的待排序列分别进行堆排序、快速排序

36、和冒泡排序，最省时间的算法是_。24在16个记录的有序顺序表中进行二分查找，最大比较次数是_。25在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是_的。三、解答题（本大题共4小题，每小题5分，共20分）26在定义顺序表时，存放表结点的向量空间不宜过大也不宜过小，为什么？27画出题27图所示树的孩子链表。题27图28已知一个无向图G如题28图所示，以顶点为根，且小序号优先，分别画出G的深度优先生成树和广度优先生成树。29判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。(1,5,7,20,18,8,10,40)(18,9,5,8,4,17,21,

37、6)全国2012年1月高等教育自学考试一、单项选择题(本大题共15小题，每小题2分，共30分)1.每个结点有且仅有一个直接前趋和多个(或无)直接后继(第一个结点除外)的数据结构称为（ ）A.树状结构B.网状结构C.线性结构D.层次结构2.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是（ ）A.单链表B.双链表C.仅有头指针的单循环链表D.仅有尾指针的单循环链表3.已知一个栈的入栈序列是1，2，3，n，其输出序列为pl，p2，p3.，pn，若p1是n，则pi是（ ）A.iB.n-iC.n-i+lD.不确定4.下面关于串的叙述中，正确的是（ ）A.

38、串是一种特殊的线性表B.串中元素只能是字母C.空串就是空白串D.串的长度必须大于零5.无向完全图G有n个结点，则它的边的总数为（ ）A.n2B.n(n-1)C.n(n-1)/2D.(n-1)6.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（ ）A.9B.11C.15D.不确定7.如图所示，在下面的4个序列中，不符合深度优先遍历的序列是（ ）A.acfdebB.aebdfcC.aedfbcD.aefdbc8.无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是（ ）A.快速排序B.归并排序C.冒泡排序D.直接选择排序9.已知二叉排序树G，要输出其结点的有序

39、序列，则采用的遍历方法是（ ）A.按层遍历B.前序遍历C.中序遍历D.后序遍历10.用ISAM和VSAM组织的文件都属于（ ）A.散列文件B.索引顺序文件C.索引非顺序文件D.多关键字文件11.对序列(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(4，9，-1，8，20，7，15)，则采用的排序方法是（ ）A.选择B.快速C.希尔D.冒泡12.当采用分块查找时，数据的组织方式为（ ）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块中数据个数必须相同C.数据分成若干块，每块内数据有序，块间是否有序均可D.数据分成若干块，每块内数据不必有序，但块间必须有序13.下述

40、编码中不是前缀码的是（ ）A.(00，01，10，11)B.(0，1，00，11) C.(0，10，110，111)D.(1，01，000，001)14.若一个栈以向量V1.n存储，初始栈顶指针top为n+l，则x进栈的正确操作是（ ）A.top=top-1；Vtop=xB.Vtop=x；top=top+1C.top=top+1；Vtop=xD.Vtop=x；top=top-115.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是（ ）A.p - > data = - 1B.p - > next = NULLC.p - > next - > n

41、ext=headD.p - > next = head二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 16.在数据的逻辑结构和存储结构中，与计算机无关的是_。17.线性表L=(a1,a2,，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。18.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出队运算后，有front=11，rear=29；front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是_和_。19.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_。20.已知三

42、对角矩阵A1010的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A67 的地址为_。21.若以(4，5，6，7，8)作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。22.有向图G如图所示，它的两个拓扑排序序列分别为_和_。23.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_。24.已知广义表A=(x，(a，b)，c，)，函数head(head(tail(A)的运算结果是_。25.索引顺序文件既可以顺序存取，也可以_。三、解答题(本大题共4小题，每小题5分，

43、共20分)26.对关键字序列(26，18，60，14，7，45，13，32)进行降序的堆排序，写出构建的初始堆(小根堆)及前两趟重建堆之后序列状态。初始堆：第一趟：第二趟：27.设散列函数为H (key)=key 11，散列地址空间为0··10，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探查法解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。28.已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，请画出此二叉树，并给出后序遍历序列。29.已知如图所示的带权无向图，请

44、画出用普里姆算法从顶点1开始的最小生成树的构造过程。全国2012年1月高等教育自学考试数据结构试题一、单项选择题(本大题共15小题，每小题2分，共30分)1.每个结点有且仅有一个直接前趋和多个(或无)直接后继(第一个结点除外)的数据结构称为（ ）A.树状结构B.网状结构C.线性结构D.层次结构2.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是（ ）A.单链表B.双链表C.仅有头指针的单循环链表D.仅有尾指针的单循环链表3.已知一个栈的入栈序列是1，2，3，n，其输出序列为pl，p2，p3.，pn，若p1是n，则pi是（ ）A.iB.n-iC.n

45、-i+lD.不确定4.下面关于串的叙述中，正确的是（ ）A.串是一种特殊的线性表B.串中元素只能是字母C.空串就是空白串D.串的长度必须大于零5.无向完全图G有n个结点，则它的边的总数为（ ）A.n2B.n(n-1)C.n(n-1)/2D.(n-1)6.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（ ）A.9B.11C.15D.不确定7.如图所示，在下面的4个序列中，不符合深度优先遍历的序列是（ ）A.acfdebB.aebdfcC.aedfbcD.aefdbc8.无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是（ ）A.快速排序B.归并排序C.冒泡

46、排序D.直接选择排序9.已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是（ ）A.按层遍历B.前序遍历C.中序遍历D.后序遍历10.用ISAM和VSAM组织的文件都属于（ ）A.散列文件B.索引顺序文件C.索引非顺序文件D.多关键字文件11.对序列(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(4，9，-1，8，20，7，15)，则采用的排序方法是（ ）A.选择B.快速C.希尔D.冒泡12.当采用分块查找时，数据的组织方式为（ ）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块中数据个数必须相同C.数据分成若干块，每块内数据有序，块间是否有序均可D.

47、数据分成若干块，每块内数据不必有序，但块间必须有序13.下述编码中不是前缀码的是（ ）A.(00，01，10，11)B.(0，1，00，11) C.(0，10，110，111)D.(1，01，000，001)14.若一个栈以向量V1.n存储，初始栈顶指针top为n+l，则x进栈的正确操作是（ ）A.top=top-1；Vtop=xB.Vtop=x；top=top+1C.top=top+1；Vtop=xD.Vtop=x；top=top-115.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是（ ）A.p - > data = - 1B.p - > next

48、= NULLC.p - > next - > next=headD.p - > next = head二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 16.在数据的逻辑结构和存储结构中，与计算机无关的是_。17.线性表L=(a1,a2,，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。18.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出队运算后，有front=11，rear=29；front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是_和_。19.设T和P是两

49、个给定的串，在T中寻找等于P的子串的过程称为_。20.已知三对角矩阵A1010的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A67 的地址为_。21.若以(4，5，6，7，8)作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。22.有向图G如图所示，它的两个拓扑排序序列分别为_和_。23.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_。24.已知广义表A=(x，(a，b)，c，)，函数head(head(tail(A)的运算结果是_。25.索引顺序文件既可以

50、顺序存取，也可以_。三、解答题(本大题共4小题，每小题5分，共20分)26.对关键字序列(26，18，60，14，7，45，13，32)进行降序的堆排序，写出构建的初始堆(小根堆)及前两趟重建堆之后序列状态。初始堆：第一趟：第二趟：27.设散列函数为H (key)=key 11，散列地址空间为0··10，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探查法解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。28.已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，请画出此二

51、叉树，并给出后序遍历序列。29.已知如图所示的带权无向图，请画出用普里姆算法从顶点1开始的最小生成树的构造过程。全国2012年1月高等教育自学考试数据结构导论试题一、单项选择题(本大题共15小题，每小题2分，共30分)1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )A.集合 B.线性结构 C.树形结构 D.图状结构2.下面算法程序段的时间复杂度为( )for ( int i=0; i<m; i+)for ( int j=0; j<n; j+)aij=i*j;A. O(m2) B. O(n2) C. O(mn) D. O(m+n) 3.线性结构是( )A.具有n（n0）个表元素的有穷序列 B.具有n（n0）个字符的有穷序列C.具有n（n0）个结点的有穷序列 D.具有n（n0）个数据项的有穷序列 4.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是( ) A. O(1) B. O()