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

欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 1 页 中国自考人(700门自考课程 永久免费、完整 在线学习 快快加入我们吧！全国 2003 年 10 月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列说法正确的是（）A数据是数据元素的基本单位 B数据元素是数据项中不可分割的最小标识单位 C数据可由若干个数据元素构成 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 的结点 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下列有关图遍历的说法中不正确的是（）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 分）请在每小题的空格中填上正确答案。错填、不填均无分。16表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_和散列存储方式。17设某非空双链表，其结点形式为 若要删除指针 q 所指向的结点，则需执行下述语句段：q-prior-nextq-next;_。18如图所示，设输入元素的顺序是 A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一prior data next，欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 3 页 个元素为 D，则输出序列为_。19队列中允许进行删除的一端为_。20设一棵二叉树中度为 2 的结点数为 10，则该树的叶子数为_。21如图所示的二叉树，若按后根遍历，则其输出序列为_。22一个具有 n 个顶点的有向完全图的弧数为_。23查找表的数据结构有别于线性表、树型结构等，其逻辑结构为_。24长度为 L 的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为_。25在开散列表上查找某元素时，通常分两步进行，首先必须计算该键值的散列地址，然后在地址指针所指_中查找该结点。26文件的检索有顺序存取、_和按关键字存取三种方式。27在待排序的 n 个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为_。28在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序过程中需进行_趟才能完成。三、应用题（本大题共 5 小题，共 30 分）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 页 4v3v2v1v0v432100111010110110111110100110VVVVV 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;试设计一个算法：void copy(node*head l,node*head 2)，将以 head 1 为头指针的单链表复制到一个不带有头结点且以 head2 为头指针的单链表中。（6 分）35修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾，第二次把最小记录放到表头，如此反复进行。试编写修改后的算法：void dbubble(int a,int n)。（8 分）中国自考人(改写昨日遗憾 创造美好明天！用科学方法牢记知识点顺利通过考试！中国自考人(700门自考课程 永久免费、完整 在线学习 快快加入我们吧！欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 5 页 2003 年 10 月数据结构导论试题答案 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 6 页 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 7 页 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 各类考试历年试题答案免费免注册直接下载 全部 WORD 文档 第 8 页 中国自考人(改写昨日遗憾 创造美好明天！用科学方法牢记知识点顺利通过考试！