数据结构自考题

1、数据结构自考题 -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 Dp=head（分数： 2.00 ）A.B.C.D.解析： 解析 在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结

2、点，就得到了单链形式的循环链表，并简单称为单循环链表。故由题目中此单循环锚表的头指针为head，指针 p 指向尾结点，可得 pnext=head。3. 设有 6 个结点的无向图，该图至少应有( ) 条边才能确保是一个连通图。A5 B6C7 D8（分数： 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 Cg,c,b Dg,d,b（分数： 2.00 ）A. B.C.D.解析：5. 以下有关数据结构的叙述，正确的是 ( ) A线性表的线性存储结

3、构优于链式存储结构B二叉树的第i 层上有 2i-1 个结点，深度为K 的二叉树上有2k-1 个结点C二维数组是其数据元素为线性表的线性表D栈的操作方式是先进先出（分数： 2.00 ）A.B.C.D.解析：6. 设 rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为( )A s=rear; Brear=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

4、.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

5、.00 ）A.B.C.D.解析：10. 森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是一棵二叉树后，其根结点的左孩子上有 ( ) 个结点。n1， n2 ，n3， n4，那么当把森林T 转换成A n1 -1 Bn1 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 串的

6、长度相等且对应的字符相同（分数： 2.00 ）A.B.C.D. 解析：13. 邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( )A先序遍历B 中序遍历C 后序遍历D 按层遍历（分数： 2.00 ）A.B.C.D.解析：14. 如果我们采用二分查找法查找一个长度为n 的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度 ( 假设树高h2) 。A大于 B 小于 C 等于 D 无法确定（分数： 2.00 ）A.B. C.D.解析：15. 一个具有 N 个顶点的有向图最多有 ( ) 条边。A N(N-1)/2 BN(N-1) C N(N+1) D N(N+1)/2（分数： 2.00

7、 ）A.B. C.D.解析：二、 填空题 ( 总题数： 10，分数： 20.00)16. 在线性表的顺序存储中， 元素之间的逻辑关系是通过 _决定的； 在线性表的链接存储中，元素之间的逻辑关系是通过 _决定的。（分数： 2.00 ）填空项 1:_（正确答案：相邻位置链接指针）解析：17. 对于一个二维数组Amn ，若按行序为主序存储，则任一元素Aij相对于 A00的地址为 1 。（分数： 2.00 ）填空项 1:_（正确答案： i ×j+i全元素位置）解析：18. 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是1 的。（分数： 2.00 ）填空项 1:_（正确答案

8、：稳定）解析：19. 对于数组，通常具有的基本操作有 _种，它们分别是 _。（分数： 2.00 ）填空项 1:_（正确答案：两查找和修改）解析：20. 如果我们定义一个长度为 N 的串空间，则它最多能放 1 个字符。（分数： 2.00 ）填空项 1:_（正确答案： N1）解析：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。（分数

9、： 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:_（正确答案：基地址）解析：三、 解答题

10、 ( 总题数： 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

11、(tail(L);分别写出从下列广义表中分解得到b 的操作表达式。(1)L1=(a,b,c,d);(2)L2=(a),(b),(c),(d)。（分数： 10.00 ）_正确答案： (head(tail(L1)解析：_正确答案： (head(head(tail(head(L2)解析：(1) 画出对表长为 13 的有序顺序表进行二分查找的判定树；(2) 已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找37 时所需进行的比较次数。（分数： 10.00 ）_正确答案： ()解析：_正确答案： (3)解析：四、 算法阅读题 ( 总题

12、数： 2，分数： 20.00)假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：typedef struct Nodeint id; /*学号 */int score; /*成绩 */srruct Node*next;LNode,*LinkList;阅读算法 f31 ，并回答问题：(1) 设结点结构为，成绩链表A 和 B 如图所示，画出执行算法f31(A,B)后 A 所指的链表；(2) 简述算法 f31 的功能。void f31(LinkList A,LinkList B)LinkList p,q;p=A next;q=B next;while(p&&q)if(p

13、id<Q id)p=p next;else if(p id q id)q=q next;elseif(p score 60)if(q score 60)p score=q score;else p score=60;p=p next;q=q next;（分数： 10.00 ）_正确答案： ()解析：_正确答案： ( 对于表 A 中成绩低于60 的学生，如果在表B 中也有成绩记录，则将表表 B 中的成绩；但若其在表B 中的成绩高于60 分，则只改为60 分。 )解析：阅读下列算法，并回答问题：A 中的成绩修改为其在(1) 无向图 G如图所示，写出算法 f30(&G) 的返回值；(2

14、) 简述算法 f30 的功能。#define MaxNum 20int visitedMaxNum;void DFS(Graph*g,int i);/* 从顶点 vi 出发进行深度优先搜索，访问顶点vj 时置 visitedj为 1*/int f30(Graph*g)int i,k;for(i=0;ig N;I+)visitedi=0;if(visitedi=0)k+;DFS(g,i);return k;（分数： 10.00 ）_正确答案： (3)解析：_正确答案： ( 返回无向图g 中连通分量的个数。)解析：五、 算法设计题 ( 总题数： 1，分数： 10.00)27. 对一个有 t 个非零

15、值元素的m×n矩阵，用 B0.t,1.3的数组来表示，其中第0 行的三个元素分别是m,n,t ，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意一个元素Aij的位置，并考虑若修改其元素值须用多少时间?( 设 B 中第 1 列原行号是递增的)（分数： 10.00 ）_正确答案： ( 分析题意可得其算法思想为：首先可在数组B 中找到相应的行，然后找到相应的列，即可修改其元素值，可假定要修改的先就具有非零值。从而可将算法描述为：lorte(B,t,i,j,v) /*确定任意一个元素Aij的位置 */datatype B;/*B的杆标为0.t和 1.3*/int t,i,j;float v; datatype A; /*A的下标为 1.m 和 1.n ， A 表示 m×n 矩阵 */int p;p=1;while(Bp1!=1)&&(p =t)P+;if(pt)printf Chasn't element