2003年10月自考数据结构导论试题真题.doc

《2003年10月自考数据结构导论试题真题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、全国2003年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．下列说法正确的是（　　　）A．数据是数据元素的基本单位B．数据元素是数据项中不可分割的最小标识单位C．数据可由若干个数据元素构成D．数据项可由若干个数据元素构成2．数据结构的基本任务是（　　　）A．逻辑结构和存储结构的设计B．数据结构的运算实现C．数据结构的评价

2、与选择D．数据结构的设计与实现3．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（　　　）A．O（1）B．O（n）C．O（nlog2n）D．O(n2)4．顺序存储的线性表（a1,a2,…,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（　　　）A．nB．n/2C．n+1D．(n+1)/25．下列树U′，经剪技运算DELETE（U′，x，2）后为（　　　）6．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及

3、右孩子结点的编号分别为（　　　）A．2，14B．2，15C．3，14D．3，157．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（　　　）A．116B．118C．120D．1228．一个带权的无向连通图的最小生成树（　　　）A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在9．下列有关图遍历的说法中不正确的是（　　　）A．连通图的深度优先搜索是一个

4、递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C．非连通图不能用深度优先搜索法D．图的遍历要求每一顶点仅被访问一次10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（　　　）A．小于顺序表的平均查找长度B．大于顺序表的平均查找长度C．与顺序表的平均查找长度相同D．无法与顺序表的平均查找长度比较11．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（　　　）A．同义词之间发生冲突引起的B．非同义词之间发生冲突引起的C．同义词之间或非同义词之间发生冲突引起的D．散列表

5、“溢出”引起的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．（

6、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分）请在每小题的空格中填上正确答案。错填、不填均无分。16．表示逻辑关系的存储结构可以有

7、四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。priordata，next17．设某非空双链表，其结点形式为　若要删除指针q所指向的结点，则需执行下述语句段：q->prior->next＝q->next;_______________。18．如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_______________。19．队列中允许进行删除的一端为________________

8、。20．设一棵二叉树中度为2的结点数为10，则该树的叶子数为________________。21．如图所示的二叉树，若按后根遍历，则其输出序列为________________。22．一个具有n个顶点的有向完全图的弧数为________________。23．查找表的数据结构有别于线性表、树型结构等，其逻辑结构为________________。24．长度为L的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为________________。25．在开散列表上查找某元素时，通常分两