自学考试-数据结构自考题模拟17

《自学考试-数据结构自考题模拟17》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构自考题模拟17一、单项选择题K栈一般情况下常采用以下两种存储方式（）A・顺序结构和散列结构B.散列结构和链式结构C.线性结构和非线性结构D.顺序存储结构和链式结构2、考虑下列四种排序方法,在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是（）A.直接插入排序和快速排序B.快速排序和归并排序C.直接选择排序和归并排序D.直接插入排序和归并排序3、在桶排序中，其平均时间复杂度是（）A.0（1）B・0（n）C.0（n2）D.0（lgn）4、链栈与顺序栈相比，有一个比较明显的优点即（）A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的

2、情况D.删除操作更加方便5、二维数组A[：LO][6]釆用行优先的存储方法，若每个元素占4个存储单元，已知元素A[3][4]的存储地址为1000,则元素A[4][3]的存储地址为（）A・1020B・1024C・1036D・12406、邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的（）A・先序遍历B.中序遍历C.后序遍历D.按层遍历7、对采用二分查找法进行查找运算的查找表，要求按（）方式进行存储。A・顺序存储B・链式存储C・顺序存储且结点按关键字有序D.链式存储且结点按关键字有序8、将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构屮，采用

3、（）方法能够最快地找出其中最大的止整数。A.快速排序B.插入排序C.选择排序D.归并排序9、已知二叉树的中序序列和后序序列均为ABCDEF,则该二叉树的先序序列为（）A・FEDCBAB.ABCDEFC・FDECBAD・FBDCEA10＞设散列函数为H（k）=kmod7,一组关键码为23,14,9,6,30,12和18,散列表T的地址空间为0.6,用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为（）A,0123456146239183012Be01234561423930126012345614129233D186D.0123456623301

4、418129IK对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A.OB.1C.2D.不存在这样的二叉树12、若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序,共要进行（）次比较。A・33B・45C.70D・9113、下列排序算法中，其时间复杂度和记录的初始排列无关的是（）A.插入排序B.堆排序C.快速排序D.冒泡排序14、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先序遍历B.屮序遍历C.后序遍历D.按层次遍历二、填空题15、判断一个没有头结

5、点的单链表head为空的条件是o16、设二维数组A[10・・20,5・・10]按行优先存储・，每个元素占4个存储单元，A[10,5]的存储地址是1000,贝ljA[15z10]的存储地址是。17、对于一个具有n条边和e个顶点的图來说，如果采用邻接表表示，则其空间复杂度为,若采用邻接矩阵表示，则其空间复朵度为o18、在5阶B-树屮，每个结点至多含4个关键字，除根结点之外，具他结点至少含个关键字。19、设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素存储在B[0],元素耳?存储在B[ll],则矩阵元素円6存储在田1中。20、设树T的度为4,其中度为1、

6、2、3和4的结点个数分别是4、2、1和1,贝虹中叶子结点的个数是:21、一个字符串相等的充耍条件是和o22、在串的链式存储结构中,有一个串Sl=-ejidc",我们假设存储时结点的大小为1,并设指针占有4个字节，则链串的存储密度为,又假设串S2=-abcdefg'1在存储吋我们设定结点的大小为4,指针占冇4个字节，则此链串的存储密度为。23、若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序,则得到的结果为o24、在线性结构中，决定了它的遍历路线只有一条。三.解答题己知有向图G的定义如下：G=(V,

7、E.V={azb,czdze},,,)E={,Va,c>,,25画岀G的图形；26写出G的全部拓扑序列。27、画岀与如图所示森林对应的二叉树。28画出对表长为13的有序顺序表进行二分查找的判定树；29已知关键字序列为(12,14,16z21,24,28z35z43z52,67,71,84,99),写出在该序列中二分查找37时所需进行的比较次数。(假设n为2的乘幕，并Hn>2)四、算法阅读题30^求卜面算法中变量count的值:intTime{intncount=0；x=2；while(x

8、x=2；count++；return(count)}假设学生成绩按