2003年10月全国自考数据结构导论试题及答案.pdf

《2003年10月全国自考数据结构导论试题及答案.pdf》由会员分享，可在线阅读，更多相关《2003年10月全国自考数据结构导论试题及答案.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 1 页 中国自考人(700门自考课程 永久免费、完整 在线学习 快快加入我们吧！全国 2003 年 10 月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列说法正确的是（）A数据是数据元素的基本单位 B数据元素是数据项中不可分割的最小标识单位 C数

2、据可由若干个数据元素构成 D数据项可由若干个数据元素构成 2数据结构的基本任务是（）A逻辑结构和存储结构的设计 B数据结构的运算实现 C数据结构的评价与选择 D数据结构的设计与实现 3在一个具有 n 个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（）AO（1）BO（n）CO（nlog2n）DO(n2)4顺序存储的线性表（a1,a2,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（）An Bn/2 Cn+1 D(n+1)/2 5下列树 U，经剪技运算 DELETE（U，x，2）后为（）6一棵有 16 结点的完全二叉树，对它按层编号，则对编号为 7

3、 的结点 X，它的双亲结点及右孩子结点的编号分别为（）A2，14 B2，15 C3，14 D3，15 7设有一 5 阶上三角矩阵 A1.5，1.5，现将其上三角中的元素按列优先顺序存放在一堆数组 B1.15中。已知 B1的地址为 100，每个元素占用 2 个存储单元，则 A3，4的地址为（）欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 2 页 A116 B118 C120 D122 8一个带权的无向连通图的最小生成树（）A有一棵或多棵 B只有一棵 C一定有多棵 D可能不存在 9下

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

5、单位是（）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

6、，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（）A选择排序 B冒泡排序 C快速排序 D插入排序 二、填空题（本大题共 13 小题，每空 2 分，共 26 分）请在每小题的空格中填上正确答案。错填、不填均无分。16表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_和散列存储方式。17设某非空双链表，其结点形式为 若要删除指针 q 所指向的结点，则需执行下述语句段：q-prior-nextq-next;_。18如图所示，设输入元素的顺序是 A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序

7、列的第一prior data next，欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 3 页 个元素为 D，则输出序列为_。19队列中允许进行删除的一端为_。20设一棵二叉树中度为 2 的结点数为 10，则该树的叶子数为_。21如图所示的二叉树，若按后根遍历，则其输出序列为_。22一个具有 n 个顶点的有向完全图的弧数为_。23查找表的数据结构有别于线性表、树型结构等，其逻辑结构为_。24长度为 L 的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为_。25在开散列表

8、上查找某元素时，通常分两步进行，首先必须计算该键值的散列地址，然后在地址指针所指_中查找该结点。26文件的检索有顺序存取、_和按关键字存取三种方式。27在待排序的 n 个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为_。28在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序过程中需进行_趟才能完成。三、应用题（本大题共 5 小题，共 30

9、分）29设有一顺序队列 sq，容量为 5，初始状态时 sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（6 分）（1）d,e,b 入队（2）d,e 出队（3）i,j 入队（4）b 出队（5）n,o,p 入队 30已知无向图 G 的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从 V0开始的深度优先搜索的序列。（4 分）欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 4 页 4v3v2v1v0v4321

10、00111010110110111110100110VVVVV 31画出下列二叉树的二叉链表表示图。（6 分）32用二分查找法对一个长度为 10 的有序表进行查找，填写查找每一元素需要的比较次数。（8 分）元素下标 1 2 3 4 5 6 7 8 9 10 比较次数 33已知序列（10，18，4，3，6，12，1，9，15，8），请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。（6 分）四、设计题（本大题共 2 小题，共 14 分）34设某带头结头的单链表的结点结构说明如下：typedef struct nodel int data;struct nodel*next;node;试

11、设计一个算法：void copy(node*head l,node*head 2)，将以 head 1 为头指针的单链表复制到一个不带有头结点且以 head2 为头指针的单链表中。（6 分）35修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾，第二次把最小记录放到表头，如此反复进行。试编写修改后的算法：void dbubble(int a,int n)。（8 分）中国自考人(改写昨日遗憾 创造美好明天！用科学方法牢记知识点顺利通过考试！中国自考人(700门自考课程 永久免费、完整 在线学习 快快加入我们吧！欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！

12、我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 5 页 2003 年 10 月数据结构导论试题答案 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 6 页 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 7 页 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 8 页 中国自考人(改写昨日遗憾 创造美好明天！用科学方法牢记知识点顺利通过考试！