数据结构冲刺模拟试卷、考前密押试卷参考答案与解析.doc

《数据结构冲刺模拟试卷、考前密押试卷参考答案与解析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构冲刺模拟试卷、考前密押试卷参考答案与解析冲刺模拟试卷（一）一、单项选择题1.C（p3）2.D（p3）3.A（p13）4.D（p28）5.B（p32）6.B（p37）7.B（p51）8.B（p60）9.D（p83）10.B（p95）11.A（p113）12.C（p174）13.D（p196）14.A（p137）15.A（p2071.[解析]逻辑上的数据结构称为逻辑结构，逻辑结构有线性结构和非线性结构两大类。2.[解析]循环队列、链表和哈希表都属于存储结构的描述，而栈属于逻辑结构的描述。3.[解析]采用顺序存储方式在已知元素序号的情况下可

2、以直接计算出地址，当指定在线性表的最后进行插入和删除运算时，也不需要进行大量元素的移动。4.[解析]D答案的操作过程①s->prior=p;②s->next=p->next;③p->next->prior=s;④p->next=s;而其他答案先执行④p->next=s;则使得③p->next->prior=s;中的p->next指向了s，没有真正指向p的原后继结点。5.[解析]因为输出序列的第一个元素是n，说明n个元素进栈后才开始出栈，则输出第1个是n，第2个时n-1，第3个时n-2，……，第i个是n-（i-1），即n-i+1。6.[解析]循

3、环队列，一次入队是队尾指针rear循环加1，一次出队（删除）是对头指针front循环加1。本题可以不用考虑循环，因为运算没有超出数组最大值。7.[解析]空串（EmptyString）是长度为零的串，由一个或多个空格组成的串称为空白串（BlankString）。8.[解析]按给定的下标范围A[0..8,1..10]进行计算：A[8,5]按行优先存储是第8*10+5=85个元素，要满足题意，应找到按列优先存储时也是第85个的那个元素：每列式9个元素，9*9=81（小于85的最大值），故此元素应在第10列上，又85-81=4，故此元素应在第3行上（

4、行号从0开始的），所以为A[3,10]满足题意。9.[解析]在后序线索树中查找*p的后序后继结点，仅当*p的右子树为空时，才能直接由*p的右线索p->rchild得到，否则必须知道*p的双亲结点才能找到其后序后继。因此，如果线索二叉树中的结点没有指向其双亲结点的指针，就可能要从根开始进行后序遍历才能找到结点*p的后序后继。由此可看出，线索对查找指定结点的后序后继并无多大帮助，即在后序线索二叉树求后序后继的问题没有得到有效解决。同理，在前序线索二叉树中求前序后继的问题也没有得到有效解决。10.[解析]前缀码是字符集中任一字符编码都不是其他字符的

5、编码的前缀。B答案中“0”是“00”的前缀，“1”是“11”的前缀，所以此编码不是前缀码。11.[解析]n个顶点的连通图至少有n-1条边，再少就不连通了，连通是指任意两个顶点之间都有路径，而不要求都有边相连。有路径是指从一个顶点沿着某些边可以到达另一个顶点。12.[解析]C答案的60成了100的左孩子，而别的答案100的左孩子都是80。本题也可以把4个二叉排序树全部构造出来进行比较。13.[解析]H（26）=9，H（25）=8，H（72）=4，H（38）=4，H（8）=8，H（18）=1，H（59）=8，当最后一个元素59存放时，8号地址已经

6、放了25,9号地址放了26,10号放了8,11号地址开放。14.[解析]对于后三种排序方法两趟排序后，序列的首部和尾部两个应是有序的两个极值，而给定的序列并不满足；而使用快速排序两趟排序后，应至少有两个元素已经排在正确位置，现4,8,20都已在正确位置上。15.[解析]检索就是在文件中查找给定条件的记录；维护主要是指对文件记录的插入、删除及修改等更新操作。二、填空题16.（p9）O（n）17.（p4）指针18.（p32）SxSSxSxx19.（p63）6620.（p72）n21.（p175）二叉排序树22.（p101）n（n-1）23.（p1

7、74）1624.（p156）O（n㏒2n）25.（p208）多关键字文件17.[解析]链接存储的结点结构至少有两组分组成：数据域和指针域，指针域用来存放存储相邻结点的地址信息。18.[解析]栈是后进先出的线性表，此题不能呢个只考虑1234全部进栈再出栈，否则只能得到4321的出栈顺序。19.[解析]只存储非零元素需要10*3*2=60字节，另外三元组表中还要一组数据存储矩阵的总行数、总列数和非0元素的总个数需要3*2=6字节。20.[解析]每一层上只有一个结点可使用最大高度达到n。21.[解析]二叉排序树的一个重要性质是按中序遍历该树所得到的

8、中序序列是一个递增有序序列。22.[解析]n个结点的有向完全图含有边的数目n(n-1)，n个结点的无向完全图含有边的数目n(n-1)/2。23.[解析]当采用顺序查