数据结构导论2002年01月

二00一年下半年全国高等教育自学考试数据结构导论试卷一、单项选择题1.若给定有n个元素的向量,则建立一个有序单向链表的时间复杂性的量级是( )A.O(1)B.O(n)C.O(n2)D.O(nlog2n)2.在一个具有n个结点的单链表达中查找值为m的某结点,若查找成功，则平均比较（）A．n B.n/2 C.(n-1)/2 D.(n+1)/23．研究数据结构就是研究（）A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和存储结构D.数据的逻辑结构,存储结构及其数据在运算上的实现4.为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用（）方式。

A、顺序存储B、链式存储C、索引存储D、散列存储5．二维数组A[10……20，5……10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10，5]的存储地址是1000，则A[18，9]的地址是（）A、1208B、1212C、1368D、13646．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有（）个结点。

A、13B、12C、26D、257．下列几种结构中属于树型结构的是（）8．设无向图G=（V、E）和G’=（V’，E’），如G’为G的生成树，则下面不正确的说法是（）A、G’为G的连通分量B、G’为G的无环子图C、G’为G的子图D、G’为G的极小连通子图且V’=V9．下列说法中不正确的是（）A、无向图的极大连通子图称为连通分量B、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D、有向图的遍历不可采用广度优先搜索方法10．对有序表（18，20，25，34，48，62，74，85）用二分查找法查找85，所需的比较次数为（）A、1次B、2次C、3次D、4次11．散列表的平均查找长度（）A、与处理冲突方法有关而与表的长度无关B、与处理冲突方法无关而与表的长度有关C、与处理冲突方法有关且与表的长度有关D、与处理冲突方法无关且与表的长度无关12．对ISAM文件的删除记录时，一般（）A、只需做删除标志B、需移动记录C、需改变指针D、一旦删除就需做整理13．顺序文件适宜于（）A、直接存取B、成批处理C、按关键字存取D、随机存取14．一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）方法。

全国自学考试数据结构导论试题及答案（4套）全国2011年1月自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( )A.O(1)B.O(n)C.O(log2n)D.O(n)2.树形结构中，度为0的结点称为( )A.树根B.叶子C.路径D.二叉树3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={，，，，,，，,，}，则图G的拓扑序列是( ) A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74.有关图中路径的定义，表述正确的是( )A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5.串的长度是指( )A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数6.组成数据的基本单位是( )A.数据项B.数据类型C.数据元素D.数据变量7.程序段i=n；x=0；do{x=x+5*i；i--；}while （i>0）；的时间复杂度为( )A.O（1）B.O（n）C.O（n2）D.O(n3)8.与串的逻辑结构不同的．．．数据结构是( )A.线性表B.栈9.二叉树的第i（i≥1）层上所拥有的结点个数最多为( )A.2iB.2iC.2i-1D.2i-110.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( ) A.p->next=p->next->next B.p=p->nextC.p=p->next->nextD.p->next=p11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )A.堆排序B.冒泡排序C.直接插入排序D.快速排序12.设字符串S1=″ABCDEFG″，S2=″PQRST″，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH( S2),2))后S的结果为( )A.″BCQR″B.″BCDEF″C.″BCDEFG″D.″BCDEFEF″13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为( )A.LL型B.LR型C.RL型D.RR型14.如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为( )A.1B.3C.4D.515.数据表A中每个元素距其最终位置较近，则最省时间的排序算法是( )A.堆排序B.插入排序C.直接选择排序D.快速排序二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

1）已知出栈序列，写出可能的入栈序列并分析操作过程。

2）已知入栈序列，写出可能的出栈序列并分析操作过程。

[2004/1]如下图所示，输入元素为（A ，B ，C ），在栈的输出端得到一个输出序列ABC ，求出在栈的输入端所有可能的输入序列。

【分析】A ，B ，C 三个字符排成的序列可以有：ABC 、ACB 、BAC 、BCA 、CAB 、CBA 六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为BCA 时，输出无法得到ABC 。

因为输入序列为BCA 时，要想先输出A ，必须BCA 均入栈，但这样只能得到序列ACB 。

其余五种输入序列都可在输出端得到序列ABC。

【解答】ABC 、ACB 、BAC 、CAB 、CBA 2．队列的操作分析顺序队中元素入队出队操作及队列的状态。

（考过）[2003/10]设有一顺序队列sq ，容量为5，初始状态时sq ．front=sq ．rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。

（1） d ，e ，b 入队 （2） d ，e 出队 （3） i ，j 入队 （4） b 出队 （5） n ，o ，p 入队【解答】队列及其头尾指针的状态变化情况如下图所示（a ）初态 （b ）d ，e ，b 入队 （c ） d ，e 出队 （d ） i ，j 入队 （e ）b 出队第5步操作无法进行，因队列已满。

3．二叉树的存储结构1） 给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。

（[2000/10] [2003/10] [2004/10]考过）[2003/10]画出下列二叉树的二叉链表表示图。

Sq.frontSq.rearSq.front Sq.rear Sq.rearSq.front Sq.rear【解答】二叉树的二叉链表表示2） 给出二叉树的顺序存储示意图，画出二叉树。

（[2005/1]考过）【分析】按照给出的顺序存储结构，先绘制出一棵包括空结点的完全二叉树，然后去掉空结点就是所求的二叉树。

全国2012年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )A.集合B.线性结构C.树形结构D.图状结构2.下面算法程序段的时间复杂度为( )for ( int i=0; i<m; i++)for ( int j=0; j<n; j++)a［i］［j］=i*j;A. O(m2)B. O(n2)C. O(mn)D. O(m+n)3.线性结构是( )A.具有n（n≥0）个表元素的有穷序列B.具有n（n≥0）个字符的有穷序列C.具有n（n≥0）个结点的有穷序列D.具有n（n≥0）个数据项的有穷序列4.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是( )A. O(1)C. O(log2n)D. O(n)5.关于串的叙述，正确的是( )A.串是含有一个或多个字符的有穷序列B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有零个或多个字符的有穷序列6.栈的输入序列依次为1，2，3，4，则不可能的出栈序列是( )A.1243B. 1432C. 2134D.43127.队列是( )A. 先进先出的线性表B. 先进后出的线性表C. 后进先出的线性表D.随意进出的线性表8.10阶上三角矩阵压缩存储时需存储的元素个数为( )A.11B.56C.100D.1019.深度为k（k≥1）的二叉树，结点数最多有( )A.2k个B.(2k -1)个C.2k-1个D.(2k+1)个10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为( )A. 11B.13C. 23D. 2511.具有n个顶点的无向图的边数最多为( )A.n+1B.n(n+1)C.n(n-1)/2D.2n(n+1)12.三个顶点v1,v2,v3的图的邻接矩阵为010001010⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦，该图中顶点v3的入度为( )A. 0B. 1C. 2D. 313.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。

数据结构导论试题12.1-02.10（答案03.10、04.10、05.10、09.10、10.10、11.1、11.10）浙江省2001年10月自学考试数据结构导论试题课程代码：02142一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。

每小题1分，共14分)1.算法分析的目的是( )A.找出数据结构的合理性B.研究算法中的输入/输出关系C.分析算法的效率以求改进D.分析算法的易读性2.在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。

A.单链表B.双链表C.顺序表D.循环链表3.下面关于线性表的叙述中，错误的为( )A.顺序表使用一维数组实现的线性表B.顺序表必须占用一片连续的存储单元C.顺序表的空间利用率高于链表D.在链表中，每个结点只有一个链域4.带头结点的单链表head为空的判断条件是( )A. head=NILB. head↑.next=NILC. head↑.next=headD. head<>NIL5.队列通常采用两种存储结构是( )A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构6.按照二叉树的定义，具有3个结点的二叉树有( )A.3B.4C.5D.67.二叉树的结构如下图所示，其中序遍历的序列为( )A.a,b,d,g,c,e,f,hB.d,g,b,a,e,c,h,fC.g,d,b,e,h,f,c,aD.a,b,c,d,e,f,g,h8.深度为5的二叉树至多有( )个结点。

A.16B.32C.31D.109.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为( )A.nB.n+1C.n-1D.n+边数10.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。

A.nB.n+1C.n-1D.n/211.静态查找表与动态查找表二者的根本差别在于( )A.它们的逻辑结构不一样B.施加在其上的操作不同C.所包含的数据元素的类型不一样D.存储实现不一样12.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。

数据结构导论课程代码：02142数据结构:计算机组织数据和存储数据的方式。

数据：所有被计算机存储，处理的对象。

数据元素：数据的基本单位，数据元素简称元素。

数据的元素由数据项组成。

数据库中数据项又称字段或域。

数据项是数据不可分割的最小标识单位。

数据结构包括：数据的逻辑结构，数据的存储结构和数据的基本运算。

数据元素之间关系的不同特性，集合，线性结构，树结构，图结构。

数据元素之间的关联方式：顺序存储方式和链式存储方式（主要的）索引存储方式，散列存储方式。

算法分析因素：1正确性2易读性3健壮性4时空性时间复杂度：0（1）常数阶，（算法的时间复杂度与输入规模n无关）；O（log2n）对数阶；O(n)线性阶；O(nc)多项式阶；O(Cn)指数阶。

（C为大于1的正整数）第二章线性表2.1线性表的基本概念线性表是一种线性结构,它是由n(>=o)个数据元素组成的有穷序列，数据元素又称结点。

2.2线性表的顺序存储数据存储是最简单的一种存储方式。

线性表顺序存储的方法是：表中的结点一次存放在计算机内存中一组连续的存储单元中。

用顺序表存储实现的线性表称为顺序表。

一般情况下元素比较和移动的次数为n—i+1。

插入的算法平均移动次数约为n/2，时间复杂度o(n)删除算法，最坏情况下元素移动次数为n-1,时间复杂度为o(n),平均移动次数为（n-1）/2,时间复杂度O(n)定位算法，平均时间复杂度为o（n）求表长和读表元素算法的时间复杂度为o(1)。

2.3线性表的连接存储线性表常见的链式存储结构有单链表，循环链表和双向链表，最简单的是单链表。

Data部分称为数据域，用于存储线性表的一个数据元素，next称为指针域，指针指向本结点所含数据元素的直接后继结点。

尾借点指针域的值Null成为空指针。

Head等于null，表示该链表无任何结点，是空单链表。

-head链表的每个结点包含有数据域和指针域，指针域存放的是下一个结点的地址。

第一章概论第二章线性表第三章栈和队列第四章串第五章多维数组第六章树第七章图第八章排序第九章查找第一章概论1.数据：信息的载体,能被计算机识别、存储和加工处理。

2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。

3.数据结构：数据之间的相互关系，即数据的组织形式。

它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。

3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。

常用的运算：检索/插入/删除/更新/排序。

4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

数据的存储结构是逻辑结构用计算机语言的实现。

5.数据类型：一个值的集合及在值上定义的一组操作的总称。

分为：原子类型和结构类型。

6.抽象数据类型：抽象数据的组织和与之相关的操作。

优点：将数据和操作封装在一起实现了信息隐藏。

7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。

8.数据的逻辑结构，简称为数据结构，有：（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。

（2）非线性结构，一个结点可能有多个直接前趋和后继。

9.数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。

2）链接存储，结点间的逻辑关系由附加指针字段表示。

3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。

4）散列存储，按结点的关键字直接计算出存储地址。

10.评价算法的质量：1正确性；算法应能正确地事先预定的功能。

2易读性；算法应易于阅读和理解，以便于调试和扩充。

3健壮性；当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果。

4高效率；即达到所需的时间和空间性能。

11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。

全国2002年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。

每小题2分，共30分)1．下列数据组织形式中，（）的结点按逻辑关系依次排列形成一个“锁链”。

A.集合B.树形结构C.线性结构D.图状结构2．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（）A.S上的算法B.S的存储结构C.在S上的一个基本运算集D.在S上的所有数据元素3．下列说法正确的是（）A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算4．设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（）A.s->next=p->next;p->next=s；B.p->next=s;s->next=p->next；C.s->next=p->next;p->next=s;交换p->data和s->data；D.p=s;s->next=p；5．稀疏矩阵一般采用（）方法压缩存储。

A.三维数组B.单链表C.三元组表D.散列表6．树若用双亲链表表示，则（）A.可容易地实现求双亲及子孙的运算B.求双亲及子孙的运算均较困难C.可容易地实现求双亲运算，但求子孙运算较困难D.可容易地实现求子孙运算，但求双亲运算较困难7．将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（）A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子8．用邻接表作为有向图G的存储结构。

全国2003年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

错选、多选或未选均无分。

每小题2分，共30分)1.下列数据结构中，( )不都是线性结构。

A.栈和队列B.队列和数组C.数组和串D.文件和队列2.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。

A.顺序存储B.链式存储C.索引存储D.散列存储3.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为( )A.s->t1->r1=s->t1;s->r1->t1=s->r1;B.s->t1->r1=s->r1;s->r1->t1=s->t1;C.s->r1=s->t1->r1;s->t1=s->r->t1;D.s->t1=s->t1->r1;s->r1=s->r->t1;4.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( )A.q->right=s; s->left=q; q->right->left=s; s->right=q->right;B.s->left=q; q->right=s; q->right->left=s; s->right=q->right;C.s->left=q; s->right=q->right; q->right->left=s; q->right=s;D.以上都不对5.由下列三棵树组成转的森林换成一棵二叉树为( )6.具有100个结点的完全二叉树的深度为( )A.6B.7C.8D.97.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)，则其转置矩阵的三元组表中第3个三元组为( )A.(2，1，3)B.(3，1，5)C.(3，2，-1)D.(2，3，-1)8.无向图的邻接矩阵是一个( )A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵9.下列说法中正确的是( )A.一个具有n个顶点的无向完全图的边数为n(n-1)B.连通图的生成树是该图的一个极大连通子图C.图的广度优先搜索是一个递归过程D.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量10.顺序查找法与二分查找法对存储结构的要求是( )A.顺序查找与二分查找均只适用于顺序表B.顺序查找与二分查找既适用于顺序表，也适用于链表C.顺序查找只适用于顺序表D.二分查找只适用于顺序表11.在开散列表上，每个地址单元所链接的同义词表( )A.其键值相同B.其元素值相同C.其散列地址相同D.其含义相同12.散列文件中的记录通常成组存放，若干个记录组成一个存储单位，这个存储单位称为( )A.磁道B.块C.柱面D.桶13.索引非顺序文件中的索引表是( )A.非稠密索引B.稠密索引C.主索引D.多级索引14.对n个记录的文件进行堆排序，最坏情况下的执行时间为( )A.O(log2n)B.O(nlog2n)C.O(n)D.O(n2)15.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序方法，以第一个记录为基准得到的一次划分结果为( )A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，79二、填空题（每小题2分，共26分）请在每小题的空格中填上正确答案。