全国高等教育自学考试数据结构试题参考附标准答案

《全国高等教育自学考试数据结构试题参考附标准答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国2008年1月高等教育自学考试数据结构试题及参考答案课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。矚慫润厲钐瘗睞枥庑赖。1.逻辑上通常可以将数据结构分为（　C　　）A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和组合结构2.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（　A　　）A.访问第i个元素的前驱（1<）B.在第i个元素之后插入一个新元素()

2、C.删除第i个元素()D.对顺序表中元素进行排序3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（　D　　）A.head==NULLB.head–>next==NULLC.head!=NULLD.head–>next==head4.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（　　C　）聞創沟燴鐺險爱氇谴净。A.5，4，3，2，1，6B.2，3，5，6，1，4C.3，2，5，4，1，6D.1，4，6，5，2，35.与线性表相比，串的插入和删除操

3、作的特点是（　D　　）A.通常以串整体作为操作对象B.需要更多的辅助空间C.算法的时间复杂度较高D.涉及移动的元素更多6.假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（　B　　）残骛楼諍锩瀨濟溆塹籟。A.B.C.D.7.以下有关广义表的表述中，正确的是（　　A　）A.由0个或多个原子或子表构成的有限序列B.至少有一个元素是子表C.不能递归定义══════════════════════════════════════════════════════════════════

4、══-本套试题共分6页，当前页是第6页-D.不能为空表8.树的先根序列等同于与该树对应的二叉树的（　A　　）A.先序序列B.中序序列C.后序序列D.层序序列9.假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（　　　）A.nB.eC.2eD.n·e10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（　　　）A.1B.2C.3D.411.下列排序方法中，稳定的排序方法为（　　　）A.希尔排序B.堆排序C.快速排序D.直接插入排序12.对下列关键字序列进行快速排序时，所需进行比较次数最少的是（　　　）A.（1

5、，2，3，4，5，6，7，8）B.（8，7，6，5，4，3，2，1）C.（4，3，8，6，1，7，5，2）D.（2，1，5，4，3，6，7，8）13.含n个关键字的二叉排序树的平均查找长度主要取决于（　　　）A.关键字的个数B.树的形态C.关键字的取值范围D.关键字的数据类型14.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（　　　）A.分块查找B.顺序查找C.二分查找D.散列查找15.可有效提高次关键字查找效率的文件是（　　　）A.顺序文件B.倒排文件C.散列文件D.VSAM文件二、填空题（本大题共10小题，每

6、小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。16.数据的存储结构是其逻辑结构___________。17.输入线性表的n个元素建立带头结点的单链表，其时间复杂度为___________。18.假设循环队列的元素存储空间大小为m，队头指针f指向队头元素，队尾指针r指向队尾元素的下一个位置，则在少用一个元素空间的前提下，表示“队满”的条件是___________。酽锕极額閉镇桧猪訣锥。19.给定串的联接操作函数：char*strcat(char*to,char*from);//将串from联接到串to的末尾，

7、并返回联接后的串若字符串s1=〞point〞,s2=〞of〞,则strcat(s1,strcat)(s2,s1))的操作结果是___________。彈贸摄尔霁毙攬砖卤庑。20.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储地址为100,则元素A[4][5]的存储地址为___________。謀荞抟箧飆鐸怼类蒋薔。21.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___________。22.已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为__________

8、_。════════════════════════════════════════════════════════════════════-本套试题共分6页，当前页是第6页-23.在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n2)的排序算