自考数据结构试卷加答案2008年.doc

PAGE11 / NUMPAGES11 2008年1月 一、单项选择题（本大题共15小题,每小题2分,共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.逻辑上通常可以将数据结构分为（　C　） P3 A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线性结构 D.初等结构和组合结构 2.在下列对顺序表进行的操作中,算法时间复杂度为O(1)的是（　A　）P16 A.访问第i个元素的前驱（1） B.在第i个元素之后插入一个新元素() C.删除第i个元素() D.对顺序表中元素进行排序 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（　D　）P26 A.head= =NULL B.head–next= =NULL C.head!=NULL D.head–next= =head 4.已知栈的最大容量为4。若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列???（　C　） A.5,4,3,2,1,6 B.2,3,5,6,1,4 C.3,2,5,4,1,6 D.1,4,6,5,2,3 5.与线性表相比,串的插入和删除操作的特点是（　D　）P54 A.通常以串整体作为操作对象 B.需要更多的辅助空间 C.算法的时间复杂度较高 D.涉及移动的元素更多 6.假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（　B　）P64 A. B. C. D. 7.以下有关广义表的表述中,正确的是（　A　）P66 A.由0个或多个原子或子表构成的有限序列 B.至少有一个元素是子表 C.不能递归定义 D.不能为空表 8.树的先根序列等同于与该树对应的二叉树的（　A　） A.先序序列 B.中序序列 C.后序序列 D.层序序列 9.假设有向图含n个顶点及e条弧,则表示该图的邻接表中包含的弧结点个数为（　B　）P105 A.n B.e C.2e D.n·e 10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（　C　） A.1 B.2 C.3 D.4 11.下列排序方法中,稳定的排序方法为（　D　）P139 A.希尔排序 B.堆排序 C.快速排序 D.直接插入排序 12.对下列关键字序列进行快速排序时,所需进行比较次数最少的是（　C　）P147 A.（1,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个关键字的二叉排序树的平均查找长度主要取决于（　B　）P180 A.关键字的个数 B.树的形态 C.关键字的取值范围 D.关键字的数据类型 14.下列查找算法中,平均查找长度与元素个数n不直接相关的查找方法是（　D　）P202 A.分块查找 B.顺序查找 C.二分查找 D.散列查找 15.可有效提高次关键字查找效率的文件是（　B　）P219 A.顺序文件 B.倒排文件 C.散列文件 D.VSAM文件 二、填空题（本大题共10小题,每小题2分,共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16.数据的存储结构是其逻辑结构 映象 。P1 17.输入线性表的n个元素建立带头结点的单链表,其时间复杂度为 O（n） 。P22 18.假设循环队列的元素存储空间大小为m,队头指针f指向队头元素,队尾指针r指向队尾元素的下一个位置,则在少用一个元素空间的前提下,表示“队满”的条件是 (r+1)%m==f 。P38 19.给定串的联接操作函数： char *strcat(char *to, char *from); //将串from联接到串to的末尾,并返回联接后的串 若字符串s1=〞point〞,s2=〞of〞,则strcat(s1,strcat)(s2,s1))的操作结果是 Point of point 。 (154 60,15234 55,1234 60, 前9层完整 29-1=511 第10层489个 n0+n1+n2=1000 n1=1 n0=n2+1 20.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储地址为100,则元素A[4][5]的存储地址为 190 。=100+（4*10+5）*2 21.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为 498 。 22.已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为 55 。 23.在快速排序、堆排序和归