02142数据结构导论201410试题及答案

《02142数据结构导论201410试题及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2014年10月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码02142)本试卷共5页，满分l00分，考试时间l50分钟。考生答题注意事项：1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡"的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。第一部分选择题一、单项选择题(本大题共l5小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。请将其选出并将“答题卡”的相应代码涂

2、黑。未涂、错涂或多涂均无分。1．下列算法的时间复杂度为B2．根据数据元素之间关系的不同特性，通常将数据结构分为四类基本结构，即A．集合、顺序结构、树形结构、图结构B．集合、线性结构、链式结构、图结构C．集合、线性结构、树形结构、图结构D．线性结构、顺序结构、链式结构、图结构3．在表长为101的顺序表中做删除运算，平均移动元素的次数为A．25B．50C．5lD．1004．在表长为n的顺序表中做插入运算的时间复杂度为A5．单链表与顺序表相比，其特点是A．运算算法实现简单B．便于随机存取数据C．不需要预先分配存储空间D．结点个数受到限制6．关于链栈的说法，正确的是A．链栈不用预先考虑容量的大

3、小B．链栈出栈时不需要判断栈空C．链栈进栈时需要判断栈满D．链栈出栈时需要判断栈满7．循环队列存储在数组A[m]中，则入队列操作中队列尾指针rear的变化为数据结构导论试卷第9页共9页A．rear=rear+1B．rear=(rear+1)％(m一1)C．rear=(rear+1)％m．D．rear=(rear+1)％(m十1)8．深度为k的二叉树，结点个数最多为B9．已知一棵度为k的树中有个度为l的结点，个度为2的结点，……，个度为k的结点，则该树中的叶结点个数为B10．具有10个叶结点的哈夫曼树中度为l的结点数为A．0个B．10个C．19个D．20个11．设图的顶点数为n，则采用邻

4、接矩阵作为存储结构的图的深度优先搜索算法的时间复杂度为A．O(1)B．O(11)C．O(n2)D．O(1092n)12．n个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是A.n×(n—1)B.(n—1)×(n－1)C．(n+1)×(n+1)D．n×n13．已知一个有序表为(15，l9，30，33，49，50，65，88，93，126，164)，当二分查找值为l26的元素时，检索成功需进行的比较次数为A．1次B．2次C．3次D．4次14．直接选择排序算法的时间复杂度为D15．下述四种排序算法中，所需辅助存储量最多的是A．堆排序B．快速排序C．归并排序D．直接选择排序第二部分非选择题二、

5、填空题(本大题共l3小题，每小题2分。共26分)请在答题卡上作答。16．在数据库中，__数据项___又称为字段或域。17．双向循环链表中，在P所指结点的后面插入一个新结点*t，需要修改四个指针，分别为：t一>prior=P；t一>next=P—>next；p—>next—>prior＝t；___p->next=t____；。18．线性表中所含结点的个数称为___线性表的长度____。19．在带有头结点的循环链表中，头指针为head，判断P所指结点为尾结点的条件是____p->next==head_____20．链栈LS中，Ls一>next指向栈顶结点，则新结点*数据结构导论试卷第9页共

6、9页P入栈的操作为：P一>next=LS一>next；和___LS->next=p____；。21．为了节省存储空间，将矩阵中多个值相同的元素只分配一个存储空间，零元素不存储，这种存储方式通常称为矩阵的____压缩存储____。22．100个结点的二叉树采用二叉链表存储时，空指针域NULL有___101___个。23．已知完全二叉树的第5层有5个结点，则整个完全二叉树有___10_____个叶结点。24．一个树的最少结点个数为___0____。25．索引顺序表由两部分组成：一个是顺序表，另一个是___索引表____。26．二叉排序树上的平均查找长度介于____0(log2n)____和

7、O(n)之间。27．二分查找算法的时间复杂度是___0(log2n)_____。28．最好情况下，冒泡排序算法的时间复杂度为___0(n)____，它是一种稳定的排序方法。三、应用题(本大题共5小题，每小题6分。共30分)请在答题卡上作答。29．如题29图所示，在栈的输入端元素的输入顺序为A，5，8，试写出在栈的输出端可以得到的以数字开头的所有输出序列，并写出进栈、出栈的操作过程(用push(X)表示X进栈，pop(x)表示x出栈)。答：5A8