数据结构自考题.doc

数据结构自考题 -9( 总分： 105.00 ，做题时间： 90 分钟 )一、 单项选择题 ( 总题数： 15，分数： 30.00)1. 为便于判别有向图中是否存在回路，可借助于( )A．广度优先搜索算 B ．最小生成树算法C．最短路径算 D ．拓扑排序算法（分数： 2.00 ）A.B.C.D. √解析：2. 在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的是 ( )A． p—＞ next==head B ．p—＞ next —＞ Next==headC． p—＞ next==NULL D．p==head（分数： 2.00 ）A. √B.C.D.解析： [ 解析 ] 在单链表中，将终端结点的指针域 NULL改为指向表头结点或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表故由题目中此单循环锚表的头指针为 head，指针 p 指向尾结点，可得 p→next=head3. 设有 6 个结点的无向图，该图至少应有 ( ) 条边才能确保是一个连通图A．5 B．6C．7 D．8（分数： 2.00 ）A. √B.C.D.解析：4. 若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字b 的过程中， 先后进行比较的关键字依次为( )A． f,c,b B． f,d,b C．g,c,b D．g,d,b（分数： 2.00 ）A. √B.C.D.解析：5. 以下有关数据结构的叙述，正确的是 ( ) A．线性表的线性存储结构优于链式存储结构B．二叉树的第 i 层上有 2i-1 个结点，深度为 K 的二叉树上有 2k-1 个结点C．二维数组是其数据元素为线性表的线性表D．栈的操作方式是先进先出（分数： 2.00 ）A.B.C. √D.解析：6. 设 rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为( )A． s=rear; B．rear=rear—＞ next;rear=rear—＞ next; free(rear);free(s);C． rear=rear free(rear); rear—＞ next —＞ next; D ． s=rear —＞ next —＞ next;—＞ next —＞ next=s —＞ next;free(s);（分数： 2.00 ）A.B.C.D. √解析：7. 采用分治法进行排序的方法是 ( ) A．快速排序 B ．插入排序C．堆排序 D ．希尔排序（分数： 2.00 ）A. √B.C.D.解析：8. 对长度为 n 的关键字序列进行堆排序的空间复杂度为 ( )A． O(log 2n) B ．O(1)C． O(n) D ．O(n*log 2n)（分数： 2.00 ）A.B. √C.D.解析： [ 解析 ] 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为 0(1) ，但它是不稳定的9. 在桶排序中，其平均时间复杂度是 ( ) A． O(1) B ．O(n) C ．O(n2) D ．O(1gn)（分数：2.00 ）A.B. √C.D.解析：10. 森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是一棵二叉树后，其根结点的左孩子上有 ( ) 个结点n1， n2 ，n3， n4，那么当把森林T 转换成A． n1 -1 B．n1 C． n1 +n2 +n3 D ．n2 +n3 +n4（分数： 2.00 ）A. √B.C.D.解析：11. 数据结构是 ( ) A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合（分数： 2.00 ）A.B.C.D. √解析：12. 两个字符串相等的条件是 ( )A．串的长度相等 B ．含有相同的字符集C．都是非空串 D ．串的长度相等且对应的字符相同（分数： 2.00 ）A.B.C.D. √解析：13. 邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的 ( )A．先序遍历 B ．中序遍历 C ．后序遍历 D ．按层遍历（分数： 2.00 ）A. √B.C.D.解析：14. 如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数 ( ) 对应的判定树的高度 ( 假设树高 h≥2) 。

A．大于 B ．小于 C ．等于 D ．无法确定（分数： 2.00 ）A.B. √C.D.解析：15. 一个具有 N 个顶点的有向图最多有 ( ) 条边A． N(N-1)/2 B ．N(N-1) C ．N(N+1) D ．N(N+1)/2（分数： 2.00 ）A.B. √C.D.解析：二、 填空题 ( 总题数： 10，分数： 20.00)16. 性表的顺序存储中， 元素之间的逻辑关系是通过 ______决定的； 性表的链接存储中，元素之间的逻辑关系是通过 ______决定的分数： 2.00 ）填空项 1:__________________ （正确答案：相邻位置 链接指针）解析：17. 对于一个二维数组 A[m][n] ，若按行序为主序存储，则任一元素 A[i][j] 相对于 A[0][0] 的地址为 1 分数： 2.00 ）填空项 1:__________________ （正确答案： i ×j+i 全元素位置）解析：18. 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的分数： 2.00 ）填空项 1:__________________ （正确答案：稳定）解析：19. 对于数组，通常具有的基本操作有 ______种，它们分别是 ______。

分数： 2.00 ）填空项 1:__________________ （正确答案：两 查找和修改）解析：20. 如果我们定义一个长度为 N 的串空间，则它最多能放 1 个字符分数： 2.00 ）填空项 1:__________________ （正确答案： N—1）解析：21. 已知广义表 A=((a,b,c) ， (d,e,f)) ，则运算 head(head(tail(tail(A))))= 1 分数： 2.00 ）填空项 1:__________________ （正确答案： e）解析：22. 若对关键字序列 (43,02,80,48,26,57,15,73,21,24,66) 进行一趟增量为 3 的希尔排序， 则得到的结果为1分数： 2.00 ）填空项 1:__________________ （正确答案： 15,02,21,24,26,57,43,66,80,48,73 ）解析：23. 无向图的邻接矩阵是 1 ，并且主对角线上的元素的值为 2 分数： 2.00 ）填空项 1:__________________ （正确答案：对称零）解析：24. 散列函数的作用是： 1 。

分数： 2.00 ）填空项 1:__________________ （正确答案：压缩待处理的下标范围，待处理的 |u| 个值减少到 m个值，从而降低空间开销）解析：25. 在按照顺序存储方式存储的数组中，元素 aij 的存储地址应该是数组的 1 加上排在 aij 前面的元素所占用的单元数分数： 2.00 ）填空项 1:__________________ （正确答案：基地址）解析：三、 解答题 ( 总题数： 3，分数： 25.00)26. 对序列 (48,37,63,96,22,31,50,55,11) 进行升序的堆排序， 写出构建的初始 ( 大根 ) 堆及前两趟重建堆之后的序列状态初始堆：第1趟：第2趟：（分数： 5.00 ）__________________________________________________________________________________________正确答案： ( 初始堆： (96,55,63,48,22,31,50,37,11)第 1 趟： (63,55,50,48,22,3l,11,37,96)第 2 趟： (55,48,50,37,22,31,11,63,96))解析：利用广义表的 head 和 tail 操作，可从广义表L=((a,b) ，(c,d))中分解得到原子 c ，其操作表达式为head(head(tail(L)));分别写出从下列广义表中分解得到 b 的操作表达式。

1)L1=(a,b,c,d);(2)L2=(((a),(b),(c),(d))) 分数： 10.00 ）__________________________________________________________________________________________正确答案： (head(tail(L1)))解析：_______________________________。