全国自考数据结构导论考前密卷02142含答案.docx
《全国自考数据结构导论考前密卷02142含答案.docx》由会员分享，可在线阅读，更多相关《全国自考数据结构导论考前密卷02142含答案.docx（19页珍藏版）》请在冰点文库上搜索。
全国自考数据结构导论考前密卷02142含答案
2014年10月全国自考数据结构导论考前密卷02142（含答案）
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分。
第1题.
【正确答案】B
【你的答案】
本题分数2分
第2题若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是【】
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表
【正确答案】D
【你的答案】
本题分数2分
第3题采用线性链表表示一个向量时，要求占用的存储空间地址【】
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.可连续可不连续
【正确答案】D
【你的答案】
本题分数2分
第4题.
【正确答案】B
【你的答案】
本题分数2分
第5题采用顺序查找法，若在表头设置岗哨，则正确的查找方式通常为【】
A.从第0个元素开始往后查找该数据元素
B.从第1个元素开始往后查找该数据元素
C.从第n个元素开始往前查找该数据元素
D.从第n+1个元素开始往前查找该数据元素
【正确答案】C
【你的答案】
本题分数2分
第6题.
【正确答案】C
【你的答案】
本题分数2分
第7题通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着【】
A.数据元素具有同一特点
B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C.每个数据元素都一样
D.数据元素所包含的数据项的个数要相等
【正确答案】B
【你的答案】
本题分数2分
第8题下列关于线性表的基本操作中，属于加工型的操作时【】
A.初始化、求表长度、插入操作
B.初始化、插入、删除操作
C.求表长度、读元素、定位操作
D.定位、插入、删除操作
【正确答案】B
【你的答案】
本题分数2分
第9题.
【正确答案】B
【你的答案】
本题分数2分
第10题一个带权的无向连通图的最小生成树【】
A.有一棵或多棵
B.只有一棵
C.一定有多棵
D.可能不存在
【正确答案】A
【你的答案】
本题分数2分
第11题对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为【】
A.24
B.25
C.98
D.99
【正确答案】A
【你的答案】
本题分数2分
第12题下列有关图的遍历的说法中不正确的是【】
A.连通图的深度优先搜索是一个递归过程
B.图的广度优先搜索中邻接点的寻找具有"先进先出"的特征
C.非连通图不能用深度优先搜索法
D.图的遍历要求每一结点仅被访问一次
【正确答案】C
【你的答案】
本题分数2分
第13题通常从正确性、易读性、健壮性、高效性四个方面评价算法（包括程序）的质量，以下解释错误的是【】
A.正确性是指算法应能正确地实现预定的功能（即处理要求）
B.易读性是指算法应易于阅读和理解，以便于调试、修改和扩充
C.健壮性指当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果
D.高效性即达到所需要的时间性能
【正确答案】D
【你的答案】
本题分数2分
第14题有时为了叙述方便，可对一些概念进行简称，以下说法错误的是【】
A.将"指针型变量"简称为"指针"
B.将"头指针变量"称为"头指针"
C.将"修改某指针型变量的值"修改为"修改某指针"
D.将"P中指针所指结点"称为"P值"
【正确答案】D
【你的答案】
本题分数2分
第15题.
【正确答案】B
二、填空题（本大题共13小题，每小题2分，共26分）请在每小题的空格中填上正确答案。
错填、不填均无分。
第1题表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、____________和散列存储方式。
【正确答案】索引存储方式
【你的答案】
本题分数2分
你的得分
修改分数
第2题____________
【正确答案】q->next->prior=q->prior；
【你的答案】
本题分数2分
你的得分
修改分数
第3题对于具有n个元素的数据序列，若采用二分查找法，当n的值较大时其平均查找长度为_________。
【正确答案】
【你的答案】
本题分数2分
你的得分
修改分数
第4题解决散列所引起冲突的方案中，____________法是介于开散列表与闭散列表之间的一种方法。
【正确答案】建立公共溢出区
【你的答案】
本题分数2分
你的得分
修改分数
第5题二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是_________。
【正确答案】157
【你的答案】
本题分数2分
你的得分
修改分数
第6题采用折半查找方法进行查找的数据序列应为_________且有序。
【正确答案】顺序存储
【你的答案】
本题分数2分
你的得分
修改分数
第7题三个结点可构成_________种不同形态的二叉树。
【正确答案】5
【你的答案】
本题分数2分
你的得分
修改分数
第8题在索引顺序表上的查找分两个阶段：
一是_____________________，二是在块内查找待查的元素。
【正确答案】确定待查元素所在的块
【你的答案】
本题分数2分
你的得分
修改分数
第9题具有n个叶子结点的哈夫曼树，其结点总数为_________。
【正确答案】2n-1
【你的答案】
本题分数2分
你的得分
修改分数
第10题对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中______个用于链接孩子结点。
【正确答案】n-1
【你的答案】
本题分数2分
你的得分
修改分数
第11题索引文件只能是_________，因为索引文件的组织方式是为随机存取而设计的。
【正确答案】磁盘文件
【你的答案】
本题分数2分
你的得分
修改分数
第12题某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为_________。
【正确答案】dab
【你的答案】
本题分数2分
你的得分
修改分数
第13题循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_________。
【正确答案】（rear-front+m）% m
【你的答案】
三、应用题（本大题共5小题，每小题6分，共30分）
第1题.
【正确答案】
【你的答案】
本题分数6分
你的得分
修改分数
第2题已知序列（10，18，4，3，6，12，1，9，15，8），请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。
【正确答案】初始状态：
（10，18，4，3，6，12，1，9，15，8）
1趟：
［10，18］，［3，4］，［6，12］，［1，9］，［8，15］
2趟：
［3，4，10，18］，［1，6，9，12］，［8，15］
3趟：
［1，3，4，6，9，10，12，18］，［8，15］
4趟：
［1，3，4，6，8，9，10，12，15，18］
第4趟归并完毕，排序结束（或答共4趟）
【你的答案】
本题分数6分
你的得分
修改分数
第3题.
【正确答案】
【你的答案】
本题分数6分
你的得分
修改分数
第4题设散列函数为H（key）=key%11，散列表长度为11（散列地址空间为0…10），在给定表（SUN，MON，TUE，WED，THU，FRI，SAT）中，取单词的第一个字母在英语字母表中的序号为键值K，构造一散列表，并用线性探测法解决有关的地址冲突。
【正确答案】
【你的答案】
本题分数6分
你的得分
修改分数
第5题．
【正确答案】先根遍历序列:
ABCDFGHE
中根遍历序列:
BADGFHCE
后根遍历序列:
BGHFDECA
【你的答案】
四、算法设计题（本大题共2小题，每小题7分，共14分）
第1题．
【正确答案】
【你的答案】
本题分数7分
你的得分
修改分数
第2题若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。
【正确答案】
【你的答案】
升级会员 