2017年武汉体育学院体育工程与信息技术学院615C语言程序设计及数据结构考研仿真模拟题
● 摘要
一、填空题
1. 起始地址为480,大小为8的块,其伙伴块的起始地址是_____;若块大小为32,则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ,大小为的内存块,其伙伴块的起始地址计算公式如下:
根据上述公式起始地址就为488。
2. 以下是用类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: p->Rchild=head:head->Lchild=p
t->Rchild!=null:t->Rchild:
t->Lchild!=null:
t->Lchild:
3. G 是一个非连通无向图,共有28条边,则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数,则该图为一个孤立的顶点和一个完全连通图。
4. 线性表用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是_____。
【答案】(n -1)/2
【解析】删除第一个元素需要移动n -i 次,以此类推,删除最后一个元素需要移动0次。平 均次数为
5. 设为哈夫曼树的叶结点数日,则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
6. 当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便,但插入和删除操作不如链式存储结构方便,而且需要连续的存储空间,由于该线性表的元素总数基本稳定,而且很少进行插入删除操作,为了更快的存取元素,顺序表更合适。
7. 关键码序列(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 )的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
8. 设单链表的结点结构为
为指针域,已知指针px 指向单链表中data 为x 的结
_____;点,指针py 指向data 为y 的新结点,若将结点y 插入结点x 之后,贝懦要执行以下语句:
_____;
【答案】
9. 对于给定的元素,可以构造出的逻辑结构有_____,_____,_____,_____四种。
【答案】集合;线性结构;树形结构;图状结构(网状结构)
10.在一个无向图的的邻接表中,若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图,在邻接表中,如果存在n 条边,则会有2n 个表结点。
11.下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:
【答案】
【解析】通过递归算法,首先找到最高位的值,将其放到str 对应的数组中,依次反向获取从高位到地位的值,将其放到数组中,完成了将整数逆序放到一个字符数组中。
12.从用户的观点看,文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构,称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件,称为_____文件。从文件在存储器上的存放方式来看,文件的物理结构往往可区分为三类,即_____,_____和_____。B+树适用于组织_____的索引结构,m
阶个关键码。
【答案】数据库;文本;顺序组织;随机组织;链组织;随机组织;
树每个结点至多有_____个儿子,除
根结点外每个结点至少有_____个儿子,根结点至少有_____个儿子,有k 个儿子的结点必有_____
二、选择题
13.
已知操作符包括的后缀表达式
将中缀表达式
转换为等价
时,用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为
空,则转换过程中同时保存在栈中的操作符的最大个数是( )。
A.5 B.7 C.8 D.11
【答案】A 。
相关内容
相关标签