2017年北方民族大学软件工程832C语言程序设计与数据结构之数据结构考研强化模拟题
● 摘要
一、填空题
1. 高度为h 的堆中,最多有_____元素,最少有_____个元素。 【答案】
当最后一层只有【解析】当这个堆构成的是满二叉树时,元素的个数最多,
元素个数为
一个元素时,此时堆的元素个数最少,元素个数为
2. 关键码序列(Q ,H ,C ,Y ,Q ,A ,M ,S ,R ,D ,F ,X ),要按照关键码值递增的次序进行排序,若采用初始步长为4的希尔排序法,则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法,则扫描一趟的结果是_____。
【答案】(Q ,A ,C ,S ,Q ,D ,F ,×,R ,H ,M ,Y ); (F ,H ,C ,D ,a ,A ,M ,Q ,R ,S ,Y ,X )
【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。
快速排序(quicksort )的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
3. 以下是用类C 语言写山的算法,该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表,链接时,结点的Lchild 域作为前链域,指向结点的直接前驱,结点的Rchild 域作为后链域,指向结点的直接后继。算法中,使用一个顺序栈stack , 栈顶
head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针,试填充算法中的空格,使算法完整。
void leafchain(BiTree Abt)
{p={BiTree)malloc (sizeof (BiTNode ));
If (!p ){print£(“OVERFLOW\n”; exit (1); }
head=p; top=0;
if (bt )
{top++; stack[top]=bt;
while (top )
{t=stack[top]; top--;
if (it->Lchild && !t->Rchild){ (1) ; (2) ; (3) ; }
else {if( (4) ){top++; stack[top]= (5) ; }
if ( (6) ){top++; stack[top]= (5) ; }
}
}
(8) ; (9) ; } }
【答案】
p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild: t->Lchild!=null: t->Lchild: p->Rchild=head:head->Lchild=p
4. 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中,则非零元素在B 中的存储位置k=_____。(注:矩阵元素下标从1开始)
【答案】93
【解析】对于上三角矩阵,将代入得93。
5. 设m 、n 均为自然数,m 可表示为一些不超过n 的自然数之和,f (m , n )为这种表示方式的
数目。例f (5, 3)=5,有5种表示方式:3+2, 3+1+1,2+2+1,2+1+1+1, 1+1+1+1+1。
①以下是该函数的程序段,请将未完成的部分填入,使之完整。
②执行程序,f (6,4)=_____。
【答案】①1; 1; f (m ,n -1); n ②9
6. 无用单元是指_____,例_____
【答案】用户不再使用而系统没有回收的结构和变量;
7. G 是一个非连通无向图,共有28条边,则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数,则该图为一个孤立的顶点和一个完全连通图。
8. 外排序的基本操作过程是_____和_____。
;归并 【答案】生成有序归并段(顺串)
9. 设用希尔排序对数组{98,36,-9,0,47,23,1,8,10,7}进行排序,给出的步长(也称
增量序列)依次是4,2,1则排序需_____趟,写出第一趟结束后,数组中数据的排列次序_____。
【答案】3; (10,7,-9,0,47,23,1,8,98,36)
10.设数组
储,则元素
为_____。
【答案】9174;8788
【解析】设一个元素的行标为i ,列标为j 。若以行序为主存储顺序,
则它的存储地址为
若以列序为主存储顺序,则它的存储地址为
的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存的存储地址为_____;若以列序为主序顺序存储,则元素的存储地址
二、判断题
11.顺序存储结构的主要缺点是不利于插入或删除操作。( ) 【答案】
【解析】因为顺序表的插入删除会移动大量的元素。
12.在链队列中,即使不设置尾指针也能进行入队操作。( ) 【答案】
【解析】因为存在头指针,根据链表的性质,根据头指针可以找到为指针。
13.如果完全二叉树从根结点开始按层次遍历的输序列为1,2,3,4,5,6,7,则该完全二叉树是二叉排序树。( )
【答案】×
【解析】不是,2,3作为1的左右孩子,由于左节点2比1大,所以不具有二叉排序树的性质。
14.程序一定是算法。( ) 【答案】
【解析】一个程序不一定满足有穷性。而算法是对问题的解,用程序设计语言来实现来描述,这时算法就是一个程序。
15.对长度为无穷大的广义表,由于存储空间的限制,不能在计算机中实现。( )
【答案】√
【解析】可以有长度无穷大的广义表,只是在计算机中不能实现。
16.设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为
【答案】
( )。