数据结构自考题-4

1、数据结构自考题 -4( 总分： 103.00 ，做题时间： 90 分钟 )一、单项选择题 ( 总题数： 14，分数： 28.00)1. 栈一般情况下常采用以下两种存储方式( )A. 顺序结构和散列结构 B 散列结构和链式结构C.线性结构和非线性结构 D 顺序存储结构和链式结构(分数： 2.00 )A.B.C.D. V解析：2. 考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )A. 直接插入排序和快速排序B 快速排序和归并排序C.直接选择排序和归并排序D 直接插入排序和归并排序(分数： 2.00 )A.B.C. VD.解析：3. 在桶排序中，其平均时间复杂度

2、是 ( )A. 0(1) B . 0(n) C . 0(n2) D . 0(1gn)(分数： 2.00 )A.B. VC.D.解析：4. 链栈与顺序栈相比，有一个比较明显的优点即 ( )A. 插入操作更加方便B .通常不会出现栈满的情况C.不会出现栈空的情况 D .删除操作更加方便分数： 2.00 )A.B. VC.D.解析：5. 二维数组 A106 采用行优先的存储方法，若每个元素占 4 个存储单元，已知元素 A34 的存储地址 为 1000 ，则元素 A43 的存储地址为 （ ）A 1020 B 1024C 1036 D 1240（分数： 2.00 ）A. VB.C.D.解析：解析由题意可

3、知，自A34的存储地址1000起共存放了 5个元素（即A34 、A35 、A40、 A41和A42） 后，才开始存放 A43，所以A43的存储地址为1000+5X4=102Q6. 邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的 （ ）A. 先序遍历B 中序遍历C 后序遍历D 按层遍历（分数： 2.00 ）A. VB.C.D.解析：7. 对采用二分查找法进行查找运算的查找表，要求按 （ ） 方式进行存储。A.顺序存储B 链式存储C.顺序存储且结点按关键字有序D 链式存储且结点按关键字有序（分数： 2.00 ）A.B.C. VD.解析：8. 将上万个一组无序并且互不相等的正整数序列，存放于

4、顺序存储结构中，采用（ ）方法能够最快地找出其中最大的正整数。A.快速排序B 插入排序C 选择排序D 归并排序（分数： 2.00 ）A.B.C. VD.解析：9. 已知二叉树的中序序列和后序序列均为ABCDEF则该二叉树的先序序列为 （）A. FEDCBA B ABCDEFCFDECBA DFBDCEA(分数:2.00 )A. VB.C.D.解析：解析对于前序遍历、中序遍历和后序遍历，将结点按其访问的先后次序排列起来，所得到的结点 序列分别称为前序序列、中序序列和后序序列。用线10. 设散列函数为H（k）=k mod7，组关键码为23,14,9,6,30,12 和18,散列表T的地址空间为0.

5、6， 性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为（）（分数：2.00 ）A.B. VC.D.解析：11. 对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同A. O B. 1 C . 2 D .不存在这样的二叉树（分数：2.00 ）A.B. VC.D.解析：12. 若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，共要进行次比较。A. 33 B. 45 C . 70 D. 91（分数：2.00 ）A.B.C. VD.解析：13. 下列排序算法中，其时间复杂度和记录的初始排列无关的是 （） A

6、.插入排序B 堆排序C 快速排序D 冒泡排序（分数： 2.00 ）A.B. VC.D.解析：14. 在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ）A.先序遍历B 中序遍历C 后序遍历D 按层次遍历（分数： 2.00 ）A. VB.C.D.解析：二、填空题 （总题数： 10，分数： 20.00）15. 判断一个没有头结点的单链表 head 为空的条件是 1（分数： 2.00 ）填空项 1:（正确答案： hcad=NULL）解析：16.设二维数组 A10 20,5 10按行优先存储，每个元素占4 个存储单元， A10,5 的存储地址是1000，则 A15,10 的存储地址是1

7、。（分数： 2.00 ）填空项 1: （正确答案： 1700）解析：17. 对于一个具有 n 条边和 e 个顶点的图来说，如果采用邻接表表示， 则其空间复杂度为 ，若采用邻接矩阵表示，则其空间复杂度为 。（分数： 2.00 ）填空项 1: （正确答案： O（n+c） O（n 2） ）解析：18. 在5阶B-树中，每个结点至多含 4个关键字，除根结点之外，其他结点至少含1个关键字（分数： 2.00 ）填空项 1: （正确答案： 2）解析：19. 设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素aii存储在B0，元素日52存储在B11，则矩阵元素日36存储在B 1中。分数： 2.00 ）填

8、空项1:解析：（正确答案：17）20.设树T的度为4,其中度为1、2、3和4的结点个数分别是 4、2、1和1 ,则T中叶子结点的个数是：1（分数：2.00 ）填空项1:解析：（正确答案：8个）21. 一个字符串相等的充要条件是和。（分数：2.00 ）填空项1:解析：（正确答案：两个字符串的长度相等对应位置的字符相等）22.在串的链式存储结构中，有一个串S1="ejidc"，我们假设存储时结点的大小为1,并设指针占有4个字节，则链串的存储密度为 个字节，则此链串的存储密度为，又假设串S2="abcdefg"在存储时我们设定结点的大小为4，指针占有4。（分数

9、：2.00 ）填空项1:解析：（正确答案：20% 50%23.若对关键字序列（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）24.在线性结构中，1决定了它的遍历路线只有一条。（分数：2.00 ）填空项1:解析：（正确答案：线性结构中后继的惟一性）三、解答题（总题数：3,分数：25.00）已知有向图G的定义如下：G=（V,E）V=a,b,c,d,eE= a,b ， a,c ， b,c ， b,d ， c,d ， e,c

10、 ， e,d ）（1）画出G的图形；（2）写岀G的全部拓扑序列。（分数：10.00）正确答案：（解析：正确答案：(a,b,e,c,da,e,b,c,de,a,b,c,d)解析：25. 画出与如图所示森林对应的二叉树正确答案：dI)解析：(分数：5.00)正确答案：(I )解析：(1)画岀对表长为13的有序顺序表进行二分查找的判定树；已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找37时所需进行的比较次数。(分数：10.00 )正确答案：(3)解析：四、算法阅读题(总题数：3,分数：20.00)26. 求下面算法中变量 co

11、unt的值：(假设n为2的乘幂，并且n > 2)int Timeint ncount=0;x=2;while(x < n/2)x*=2;count+;return(count)(分数：5.00 ) 正确答案：(count=log 2n)解析：假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下:typedef struct Nodeint id; /* 学号 */int score; /*成绩 */srruct Node*next;LNode,*LinkList;阅读算法f31，并回答问题:(1)设结点结构为成绩链表A和B如图所示，画岀执行算法f31(A,B)后A所指的链表

12、;(2)简述算法f31的功能void f31(LinkList A,LinkList B) LinkList p,q;p=A> next; q=B> next;while(p&&q)if(p > id<Q > id) p=p> next;else if(p > id >q> id) q=q> next; else if(p > score < 60)if(q > score < 60) p> score=q > score; else p > score=60;p=p>

13、next;q=q> next;(分数：10.00) 正确答案：()解析：正确答案：(对于表A中成绩低于60的学生，如果在表B中也有成绩记录，则将表A中的成绩修改为其在表B中的成绩；但若其在表B中的成绩高于60分，则只改为60分。)解析：27. 简述一下算法的功能：status A (1inkedlist L)/L是无表头结点的单链表if (L&&L > next)Q=L;L=L> next;P=L;while(P > next)P=P > next;P> next=Q;Q > next=NULL;return ok;)/A(分数：5.0

14、0 )正确答案：(本程序实现的功能就是：如果 L的长度不小于2,则将首元结点删去并插入到表尾。)解析：五、算法设计题 （ 总题数： 1，分数： 10.00）28. 假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct nodeDataType data;struct node*nextLinkNode,*LinkList;编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点（分数： 10.00 ） 正确答案： ( 参考答案一：void f34(LinkList ha,LinkList hb) hb和hb分剐为存放A和B有序链表的头指针LinkList p,q,r;p=ha;q=hb> next;while(p > next&&q)if(p > next > data <q- >data)p=p> next;elseif(p > next > data=q > data)r=p > next;p> next=r > next;free(r); / 从 A 表删除相同的元素结点q=q> next;参考答案二：void f34(LinkList ha,LinkList hb) /hb 和hb分别为存放A和B有