全国2010年10月高等教育自学考试数据结构导论试题

20XX年(下)高等教育自学考试全国统一命题考试数据结构导论试卷及参考答案第一部分选择题一、单项选择题(本大题共l5小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。

请将其代码填写在题后的括号内。

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

1．数据的基本单位是 ( )A．数据项 B．数据类型C．数据元素 D．数据变量2．下列程序的时间复杂度为 ( )3．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是 ( )A．单链表 B．仅有头指针的单循环链表C．双链表 D．仅有尾指针的单循环链表4．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动的元素的个数是( )A．n—i B．n—i+1C．n—i一1 D．i5．顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为 ( )6．循环队列sq中，用数组elem[0··25]存放数据元素，sq．front指示队头元素的前一个位置，sq．rear指示队尾元素的当前位置，设当前sq．front为20，sq．rear为12，则当前队列中的元素个数为 ( )A．8 B．16C．17 D．18A．13 B．35C．17 D．368．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为 ( ) A．3 B.4C．5 D．69．对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为( )A．24 B．25C．98 D．9910．可以惟一地转化成一棵一般树的二叉树的特点是 ( )A．根结点无左孩子 B．根结点无右孩子C．根结点有两个孩子 D．根结点没有孩子11．有n个结点的有向完全图的弧数是( )12．设图的邻接链表如题l2图所示，则该图的边的数目是 ( )A．4 B．5C．10 D．201 3．已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分检索值为90的元素时，检索成功需比较的次数是 ( )A．1 B．2C．3 D．414．排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是 ( ) A．选择排序 B．快速排序C．冒泡排序 D．插入排序15．排序算法中，不稳定的排序是 ( )A．直接插入排序 B．冒泡排序C．堆排序 D．归并排序第二部分非选择题二、填空题(本大题共l3小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

全国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={<V1,V2>，<V1,V3>，<V1,V4>，<V2,V5>，<V3,V5>,<V3,V6>，<V4,V6>，<V5,V7>,，<V6,V7>}，则图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.栈C.队列D.树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分)请在每小题的空格中填上正确答案。

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

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

1.下述文件中适合于磁带存储的是（）A.顺序文件B.索引文件C.散列文件D.多关键字文件2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（）A.acbedB.becabC.deabcD.cedba3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( )A.n-1B.nC.n+1D.n+24.在一个图中，所有顶点的度数之和与图的边数的比是( )A.1∶2B.1∶1C.2∶1D.4∶15.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( )A.O(1)B.O(1og2n)C.O(n)D.O(n2)6.下述几种排序方法中，要求内存量最大的是( )A.插入排序B.快速排序C.归并排序D.选择排序7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( )A.n-1B.nC.n+1D.n(n-1)／28.对线性表进行二分查找时，要求线性表必须( )A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( )A.O(1)B.O(n)C.O(nlog2n)D.O(n2)10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( )A.n-2B.n-1C.nD.n+111.有关插入排序的叙述，错误的．．．是( )A.插入排序在最坏情况下需要O(n2)时间B.插入排序在最佳情况可在O(n)时间内完成C.插入排序平均需要O(nlog2n)时间D.插入排序的空间复杂度为O(1)12.有关树的叙述正确的是( )A.每一个内部结点至少有一个兄弟B.每一个叶结点均有父结点C.有的树没有子树D.每个树至少有一个根结点与一个叶结点。

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

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

1．下列说法正确的是（）A．数据是数据元素的基本单位B．数据元素是数据项中不可分割的最小标识单位C．数据可由若干个数据元素构成D．数据项可由若干个数据元素构成2．数据结构的基本任务是（）A．逻辑结构和存储结构的设计B．数据结构的运算实现C．数据结构的评价与选择D．数据结构的设计与实现3．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（）A．O（1）B．O（n）C．O（nlog2n）D．O(n2)4．顺序存储的线性表（a1,a2,…,a n）,在任一结点前插入一个新结点时所需移动结点的平均次数为（）A．n B．n/2C．n+1 D．(n+1)/25．下列树U′，经剪技运算DELETE（U′，x，2）后为（）6．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（）A．2，14 B．2，15C．3，14 D．3，157．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一1堆数组B［1..15］中。

已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（）A．116 B．118C．120 D．1228．一个带权的无向连通图的最小生成树（）A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在9．下列有关图遍历的说法中不正确的是（）A．连通图的深度优先搜索是一个递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C．非连通图不能用深度优先搜索法D．图的遍历要求每一顶点仅被访问一次10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（）A．小于顺序表的平均查找长度B．大于顺序表的平均查找长度C．与顺序表的平均查找长度相同D．无法与顺序表的平均查找长度比较11．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）A．同义词之间发生冲突引起的B．非同义词之间发生冲突引起的C．同义词之间或非同义词之间发生冲突引起的D．散列表“溢出”引起的12．从外存设备的观点看，存取操作的基本单位是（）A．逻辑记录B．数据元素C．文件D．物理记录13．对文件进行检索操作时，每次都要从第一个记录开始的文件是（）A．顺序文件B．索引文件C．顺序索引文件D．散列文件14．一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（）A．（14，18，38，46，65，40，20，53，86，74）B．（14，38，18，46，65，20，40，53，86，74）C．（14，18，20，38，40，46，53，65，74，86）D．（14，86，20，38，40，46，53，65，74，18）15．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（）A．选择排序B．冒泡排序C．快速排序D．插入排序二、填空题（本大题共13小题，每空2分，共26分）请在每小题的空格中填上正确答案。

2010年全国⾃考数据结构模拟试卷（五）及答案更多优质⾃考资料，请访问⾃考乐园俱乐部/doc/c4c066f8941ea76e58fa043c.html /club/5346389 2010年全国⾃考数据结构模拟试卷(五)⼀、单项选择题(本⼤题共15⼩题,每⼩题2分,共30分)在每⼩题列出的四个备选项⽬中只有⼀个是符号题⽬要求的,请将其代码填写的括号内.错选、多选或未选均⽆分。

1.设矩阵A(aij,1≤i,j≤10)的元素满⾜：aij≠0(i≥j,1≤i,j≤10)aij＝0(i现将A的所有⾮0元素以⾏序为主序存放在⾸地址为2000的存储区域中，每个元素占4个单元，则元素［9，5］的⾸地址为()A.2160B.2164C.2336D.2340答案：A2.循环队列⽤数组A［0…m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是()A.(rear-front+m)MOD mB.rear-fomt+1C.rear-fribt-1D.rear-front答案：A3.任何⼀个带权的⽆向连通图的最⼩⽣成树()A.只有⼀棵B.有⼀棵或多棵C.⼀定有多棵D.可能不存在答案：B4.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，⼀个元素出栈后即进⼊队列Q，若6个元素出列的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量⾄少应该是()A. 6B. 4C. 3D. 2答案：C5.磁带适合存储的⽂件类型是()B.顺序⽂件C.散列⽂件D.多关键字⽂件答案：B6.带头结点的单链表head为空的判断条件是()A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL答案：B7.在下图中，从顶点V1出发，按⼴度优选遍历图的顶点序列是()A.V1V5V3V4V2V6V7B.V1V5V3V4V2V7V6C.V1V7V2V6V4V5V3D.V1V2V4V7V6V5V3答案：A8.已知⼀棵⼆叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为()A.ACFKBDGB.GDBFKCAC.KCFAGDBD.ABCDFKG答案：B9.C语⾔数组Data［m+1］作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执⾏出队操作的语句为()A.front=front+1B.front=(front+1)%mC.rear=(rear+1)%mD.front=(front+1)%(m+1)答案：D10.任何⼀个带权的⽆向连通图的最⼩⽣成树()A.只有⼀棵B.有⼀棵或多棵C.⼀定有多棵D.可能不存在11.将含有83个结点的完全⼆叉树从根结点开始编号，根为1号，后⾯按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为()A.42B.40C.21D.20答案：D12.采⽤分治法进⾏排序的⽅法是()A.快速排序B.插⼊排序C.堆排序D.希尔排序答案：A13.设深度为k的⼆叉树上只有度为0和度为2的结点，则这类⼆叉树上所含结点总数量少()个。

全国2018年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( )A.n-i+1B.n-iC.iD.i-13.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( )A.4B.5C.6D.75.为查找某一特定单词在文本中出现的位置，可应用的串运算是( )A.插入B.删除C.串联接D.子串定位6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。

若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到( )A.P=″SCIENCE″B.P=″STUDY″C.S=″SCIENCE″D.S=″STUDY″7.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为( )A.356B.358C.360D.3628.如右图所示广义表是一种( )A.线性表B.纯表C.结点共享表D.递归表9.下列陈述中正确的是( )A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分10.n个顶点的有向完全图中含有向边的数目最多为( )A.n-1B.nC.n(n-1)/2D.n(n-1)11.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为( )A.a d b e f cB.a d c e f bC.a d c b f eD.a d e f c b12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( )A.快速排序B.堆排序C.归并排序D.基数排序13.不可能生成右图所示二叉排序树的关键字序列是( )A.4 5 3 1 2B.4 2 5 3 1C.4 5 2 1 3D.4 2 3 1 514.ALV树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度15.在VSAM文件的控制区间中，记录的存储方式为( )A.无序顺序B.有序顺序C.无序链接D.有序链接二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)16.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为________。

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

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

1.下述文件中适合于磁带存储的是（ A ）A.顺序文件B.索引文件C.散列文件D.多关键字文件2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ D ）A.acbedB.becabC.deabcD.cedba3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( C )A.n-1B.nC.n+1D.n+2 注：子域为2n个，有n-1个孩子。

4.在一个图中，所有顶点的度数之和与图的边数的比是( C)A.1∶2B.1∶1C.2∶1D.4∶15.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( A)A.O(1)B.O(1og2n) 二分法注：若只有尾指针，那么入和出都为O(1)C.O(n) （入队）D.O(n2) -冒泡6.下述几种排序方法中，要求内存量最大的是( C )A.插入排序B.快速排序C.归并排序D.选择排序7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( D)A.n-1B.nC.n+1D.n(n-1)／28.对线性表进行二分查找时，要求线性表必须( C)A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( B )A.O(1)B.O(n) 注：在双向循环链表中，删除最后一个结点C.O(nlog2n)D.O(n2) 的时间复杂度为O(1)10.当利用大小为n 的数组顺序存储一个队列时，该队列的最大容量为( B )A.n-2B.n-1C.nD.n+1 11.有关插入排序的叙述，错误的．．．是( C)A.插入排序在最坏情况下需要O(n 2)时间B.插入排序在最佳情况可在O(n)时间内完成C.插入排序平均需要O(nlog 2n)时间-----快速排序需要o （nlog2n ）D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( C)A.每一个内部结点至少有一个兄弟B.每一个叶结点均有父结点C.有的树没有子树D.每个树至少有一个根结点与一个叶结点。

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

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

1.下述文件中适合于磁带存储的是（ A ）A.顺序文件B.索引文件C.散列文件D.多关键字文件2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ D ）A.acbedB.becabC.deabcD.cedba3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( C )A.n-1B.nC.n+1D.n+2 注：子域为2n个，有n-1个孩子。

4.在一个图中，所有顶点的度数之和与图的边数的比是( C)A.1∶2B.1∶1C.2∶1D.4∶15.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( A)A.O(1)B.O(1og2n) 二分法注：若只有尾指针，那么入和出都为O(1)C.O(n) （入队）D.O(n2) -冒泡6.下述几种排序方法中，要求内存量最大的是( C )A.插入排序B.快速排序C.归并排序D.选择排序7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( D)A.n-1B.nC.n+1D.n(n-1)／28.对线性表进行二分查找时，要求线性表必须( C)A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( B )A.O(1)B.O(n) 注：在双向循环链表中，删除最后一个结点C.O(nlog 2n)D.O(n 2) 的时间复杂度为O(1)10.当利用大小为n 的数组顺序存储一个队列时，该队列的最大容量为( B ) A.n-2 B.n-1 C.nD.n+111.有关插入排序的叙述，错误的．．．是( C ) A.插入排序在最坏情况下需要O(n 2)时间 B.插入排序在最佳情况可在O(n)时间内完成C.插入排序平均需要O(nlog 2n)时间 -----快速排序需要o （nlog2n ）D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( C ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树D.每个树至少有一个根结点与一个叶结点。

全国2012年10月高等教育自学考试数据结构导论试题及答案最新2012版教材全国2012年10月高等教育自学考试数据结构导论试题课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的。

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

1.下面几种算法时间复杂度阶数中，值最大的是(nlog2n)(n2) (n)(2n) 2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为A.正确性 B.易读性C.健壮性D.时空性3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为解法：41至100共需要移动60次 4.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是A. head->next==head B. head->next==NULL C. head!=NULL D. head==NULL 5.在链栈的运算中，不需要判断栈是否为空的是 A.出栈B.进栈 C.取栈顶元素D.求链栈的元素个数6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是，B，C，D，C，D，A ，C，B，A，D，B，A 7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是解法：loc[i,j]=loc(0,0)+(n*i+j)*k = 100+(5*1+2)*2=14 8.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为D.无法确定解法：n0=n2+1 就有5=x+1个叶结点的哈夫曼树中，其结点总数为+1解法：2m-1 10.二叉树的中序遍历序列中，结点P排在结点Q之前的条件是 A.在二叉树中P在Q的左边 B.在二叉树中P在Q的右边 C.在二叉树中P是Q 的祖先 D.在二叉树中P是Q的子孙解法：中顺遍历顺序：左中右11.有10个顶点的无向完全图的边数是最新2012版教材解法：n(n-1)÷2 = 10÷2 =45 12.在带权有向图中求两个结点之间的最短路径可以采用的算法是 A.迪杰斯特拉算法 B.克鲁斯卡尔算法 C.普里姆算法 D.深度优先搜索算法13.二分查找算法的时间复杂度是14.在一棵初始时为空的二叉树中，依次插入键值序列50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素60要进行的比较次数是解法：画二叉树后得出：50→72→65→6015.快速排序属于 A.插入排序B.交换排序C.选择排序D.归并排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

全国自学考试数据结构导论试题及答案4套第一套试题一、选择题（每题4分，共40分）1. 下列哪个数据结构是一种非线性结构？A. 数组B. 栈C. 队列D. 树2. 下列哪种算法不适用于解决排序问题？A. 冒泡排序B. 快速排序C. 深度优先搜索D. 归并排序3. 在数据结构中，堆的底层实现通常采用哪种数据结构？A. 数组B. 栈C. 链表D. 队列4. 下列哪个选项是描述图结构的准确说法？A. 图结构是一种线性结构B. 图结构由节点和指向节点的边构成C. 图结构不能存储数据D. 图结构不支持插入和删除操作5. 下列哪个排序算法具有最坏时间复杂度为O(nlogn)？A. 冒泡排序B. 插入排序C. 选择排序D. 希尔排序二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。

2. 图的两个顶点之间的路径长度是指连接这两个顶点所需的____数。

3. 链表是一种____结构。

4. 快速排序算法的核心思想是____。

5. 栈和队列都属于线性结构，其主要区别在于____操作的限制。

三、简答题（每题10分，共30分）1. 请简要描述栈的特点以及栈的应用场景。

2. 请简要介绍图的基本概念，并说明图的应用领域。

3. 请解释递归算法的原理，并给出一个使用递归算法解决问题的例子。

四、编程题（共30分）请使用任意编程语言实现一个简单的栈数据结构，并编写测试代码进行验证。

第二套试题一、选择题（每题4分，共40分）1. 在二叉搜索树中，中序遍历的结果是____。

A. 升序排列B. 降序排列C. 随机排序D. 不确定的排序2. 在哈希表结构中，解决冲突问题的常用方法是____。

A. 线性探测B. 链地址法C. 开放地址法D. 扩容法3. AVL树是一种____。

A. 二叉搜索树B. 哈希表C. B树D. 红黑树4. 以下哪个算法不是用于解决查找问题？A. 二分查找B. 深度优先搜索C. 广度优先搜索D. 哈希查找5. 以下哪个数据结构不支持随机访问元素？A. 数组B. 栈C. 链表D. 哈希表二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。

全国2010年10月自学考试数据库系统原理试题课程代码：04735一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

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

1．在数据库系统中，提供数据与应用程序间物理独立性的是( ) A．外模式/模式映像B．模式/内模式映像C．外模式/内模式映像 D．子模式/模式映像2．对于实体集A中的每一个实体，实体集B中至少有一个实体与之联系，反之亦然，则称实体集A与实体集B之间具有的联系是( ) A．多对一B．一对多C．多对多D．一对一3．数据库物理设计的任务不包括( )A．优化模式 B．存储记录结构设计C．确定数据存放位置D．存取方法设计4．设有关系WORK（ENO，CNO，PAY），主码为（ENO，CNO）。

按照实体完整性规则( )A．只有ENO不能取空值B．只有CNO不能取空值C．只有PAY不能取空值D．ENO与CNO都不能取空值125．在关系模式R 中，函数依赖X →Y 的语义是( )A ．在R 的某一关系中，若任意两个元组的X 值相等，则Y 值也相等B ．在R 的一切可能关系中，若任意两个元组的X 值相等，则Y 值也相等C ．在R 的某一关系中，Y 值应与X 值相等D ．在R 的一切可能关系中，Y 值应与X 值相等6．设R 是一个关系模式，F 是R 上的一个FD 集，R 分解成数据库模式ρ={R1，…，RK}。

如果对R 中满足F 的每一个关系r ，都有r=1R ∏(r)2R ∏(r)…k R ∏(r)，则称这个分解ρ是( )A ．无损分解B ．损失分解C ．保持函数依赖分解D ．丢失函数依赖分解7．关系R 和S 如下表R －S 的结果是( )38．下面关于自然连接和等值连接的叙述中，不正确的是( )A ．自然连接是一种特殊的等值连接B ．自然连接要求在两个关系中有公共属性，而等值连接不必C ．两种连接都可以只用笛卡尔积和选择运算导出D ．自然连接要在结果中去掉重复的属性，而等值连接不必9．设有关系表S(NO ，NAME ，AGE)，其中AGE 为年龄字段，则表达式 AGE NOT BETWEEN 18 AND 24 等价于( )A ．AGE<=18 OR AGE>=24B ．AGE<=18 OR AGE>24C ．AGE<18 OR AGE>=24D ．AGE<18 OR AGE>2410．下列关于视图的说法中错误的是( )A ．视图是从一个或多个基本表导出的表，它是虚表B ．视图可以被用来对无权用户屏蔽数据C ．视图一经定义就可以和基本表一样被查询和更新D ．视图可以用来定义新的视图11．如果一个事务在故障发生之前完成，但是它并没有到达检查点，则系统恢复时应对该事务执行( )A．REDO操作B．UNDO操作C．RESTART操作D．NULL操作12．如果事务T1需要两次读取同一数据项A，但是在两次读操作的间隔中，另一个事务T2改变了A的值，那么此并发操作所引起的问题是( )A．丢失更新 B．死锁C．不可重复读D．读脏数据13．在SQL Server 2000中，负责管理登录账号、数据库用户和权限，创建和管理数据库的工具是( )A．服务管理器B．企业管理器C．查询分析器D．事件探查器14．PowerBuilder9.0的工作空间扩展名是( )A．.pbt B．.pblC．.dsw D．.pbw15．在对象联系图中，表示两个属性之间值的联系为逆联系的是( )A．小圆圈B．单箭头C．双线箭头 D．双向箭头4二、填空题(本大题共10小题，每小题1分，共10分)请在每小题的空格上填上正确答案。

全国自考数据结构导论（数组、矩阵和广义表）模拟试卷1一、单项选择题1 常对数组进行的两种基本操作是______。

（A）建立与删除（B）索引与修改（C）查找与修改（D）查找2 设有一个8阶的对称矩阵A，采用压缩存储方式，以行序为主序存储，每个元素占用一个存储单元，基址为100，则A63的地址为_________。

（A）118（B）124（C）151（D）1603 已知数组A[1…6，2…8]在内存中以行序为主序存放，且每个元素占两个存储单元，则计算元素A[i，j]地址的公式为_______。

（A）LOC(A[i，j])=LOC(A[1，2])+[(i一1)*7+(j一2)]*2（B）LOC(A[i，j])=LOC(A[1，2])+[(j一2)*6+(i一1)]*2（C）LOC(A[i，j])=LOC(A[1，2])+(i*8+j)*2（D）LOC(A[i，j])=LOC(A[1，2])+(j*6+i)*24 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10，且每个字符占一个字节。

若A以行序为主序存放，元素A[8，5]的起始地址与当A以列序为主序存放时的元素_______的起始地址相同。

（A）A[7，8]（B）A[6，5]（C）A[0，7]（D）A[3，10]5 对稀疏矩阵进行压缩存储的目的是________。

（A）降低运算的时间复杂度（B）节省存储空间（C）便于存储（D）便于进行矩阵运算6 以下有关广义表说法中不正确的是_______。

（A）广义表的表头总是一个原子（B）广义表的表尾总是一个广义表（C）广义表的元素可以是单个元素（D）广义表的元素可以是一个子表7 广义表L=(a，(b，(c)，d)，(()，e))的长度为________。

（A）∞（B）6（C）4（D）38 广义表L=(a)，则表尾为_________。

（A）a（B）(())（C）空表（D）(a)9 已知广义表L=((a，b，c)，a，(x，y，z))，从L表中取出原子项y的运算是_________。

全国2018年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的存储结构。

指针，引用与动态内存分配思考题1．什么是地址，什么是地址中的内容，两者的区别是什么？2．运算符“&”和“*”各有几种用法？各自的使用方式以及使用含义是什么？3．什么是指针？地址和指针有什么样的关系？4．如下3处出现的*pi的使用含义有什么不相同吗？int i=23, *pi=&i;cout<<*pi;*pi=56;5．指针的值和类型是怎样规定的？指针的值与其他类型变量的值是否有区别？6．假设程序中有“int a[20]；int *pa=a；”的说明，要表示数组元素a[i]时（0≤i≤19），有几种方法可以使用呢？7．指针可以进行哪些运算？和普通数据类型的运算有什么不同？8．假设程序中有“int a[10]，b[10][10]；”的说明，请问数组名a以及b[i]都与地址及指针有某些关系吗（0≤i≤9）？a[i]与b[i]的使用含义相同吗？a+1与b+1的含义有什么不同？a[2]+1与b[2]+1的使用含义相同吗？9．下面按9种不同方式所定义的p有什么区别与联系？如何对每一种p进行使用？int p； int *p； int **p；int p[10]； int *p[10]； int （*p）[10]；int p（）； int *p（）； int（*p）（）；10．在“2．4．1 主函数”一节中，给出过带参数的main函数的如下一般使用格式：void main（int argc， char * argv[]）{…}你能细致地描述参数argv所表达的数据结构吗?11．试述指针在函数的参数传递中的作用及其使用方法。

指针参数与数组参数是否有某种形式的关联？12．怎样使用动态分配运算符new来生成无名的动态变量以及无名的动态数组？如何对这种动态变量及动态数组进行使用？如何使用delete来配合new释放上述的动态存储空间？13．什么是引用？引用和指针的区别是什么？引用型参数具有哪些优点？14．引用型的函数返回值与非引用型的函数返回值是否有某些不相同？15．如何定义结构类型？如何说明与使用结构变量及其分量？结构与数组的定义与使用有哪些异同？16．假设某结构的分量中含有指向本结构的指针（如下面的person结构类型），请问如何通过使用new及某些相关步骤来生成一个链表呢？struct person {．．．person * next;};17．在上一题person结构类型的基础上，如下的程序“构架”是否可以用来实现生成一个具有n个项的链表（而总将新链表项加入到当前已有链表的末尾）？person *head, *tail, *temp;//head指向链表首项，tail指向末项tail = head = NULL; //使head及tail均指向“空”，表示空链表for(i=0; i<n; i++){ //形成一个具有n个项的链表temp=new person; //生成一个person型的动态新表项temp->next=NULL; //新表项将充当链表末项，将其next域置为NULL．．． //如，通过cin输入（*temp）结构（变量）的其它各分量之值等 if(head==NULL)head=tail=temp; //链表为空时，新表项既为首项又为末项else { //链表非空时tail->next=temp; //新表项加入到原链表的末项之后tail=temp; //新表项成为链表的新末项}} //i循环体结束18．在C++语言中使用指针有哪些优点？指针在程序安全方面是否会有负面影响？练习题1．读程序写结果。