《算法与数据结构》模拟试题7--答案

《《算法与数据结构》模拟试题7--答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》模拟试题7答案及评分标准一、填空题（每小题2分，共20分）1、顺序存储结构链式存储结构2、时间复杂度空间复杂度3、栈顶栈底4、2745、n2n-16、存储空间的分配释放的存储空间的回收7、以顺序方式存储结点按关键字有序8、插入排序交换排序选择排序9、关键字存储地址或存储地址关键字10、索引文件散列(哈希)文件二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案ADCBCDABB三、分析题（每题6分，共30分）102435frontrear(a)队列初始化①a,e,b入队10243fron

2、trearaeb51、解：做完下列操作后队列的头尾指针的状态变化情况如下面图形所示。④b，s，t出队⑤r，p，u，v入队10243rearfrontmvp5ukr②a,e出队③s，t，k，m入队10243frontm5kreart10243rear5bfront10243frontmtb5skreart共7页第7页每图1分2、解：⑴该树的孩子表示法的复合链表存储结构如下图；(3分)ABC⋀DE⋀F⋀G⋀H⋀I⋀J⋀┇┇0100123456789MAX_NODE-1rootnum3⋀216⋀549⋀87共7页第7页⑵将此树转换为二叉树如下图。(

3、2分)ABFCEDIJHG⑶转换后二叉树的后序遍历序列是：GFEJIHDCBA(1分)3、解：⑴该图的正邻接链表如下图所示：(2分)V02V12V23V31V42V52∧0123451523∧2643∧55∧34510∧483957∧⑵给出对该图进行拓扑排序过程如下(3分)，其拓扑序列是：V0→V1→V2→V4→V3→V5(1分)共7页第7页9V451078634V1V2V3V59V4510784V2V3V5①输出V0后②输出V1后9V457V3V5③输出V2后5V3V5④输出V4后V5④输出V3后4、解：根据所给定的散列函数和处理冲突方法，

4、得到的散列表结构如下：012345678910∧∧∧∧∧2518691716∧116∧87∧3129∧47∧95∧4253∧共7页第7页5、解：采用希尔排序法对该序列做非递减排序的每一趟结果如下。(一趟3分，二趟2分，三趟1分)4447152912404739582773448655初始关键字：5558735584429275547152912404439552773478658一趟排序后：152712402939474458558673二趟排序后：121527293940444755587386三趟排序后：四、算法填空（每空2分，共20分）

5、请在下面各算法的空白处填上相应语句实现算法功能。每个空白处只能填一个语句。1、设有一个以L为头结点的双向循环链表，删除数据为key的所有结点。p–>next!=Lp–>prior->next=p–>nextp->next->prior=p->prior2、非递归中序遍历二叉树。stack[++top]=pp=p->Rchild3、二叉排序树的查找。共7页第7页p=p–>Lchildreturn(NULL)4、选择排序算法。mlengthk!=mL->R[k]=L->R[0]五、编写算法（12分）解：⑴输出树中度为1及度为0的结点数的算

6、法。（6分）#defineMAXNODE50voidcount_nodes(BTNode*T){BTNode*Stack[MAXNODE],*p=T;inttop=0,num1=0,num0=0;if(T=NULL)printf(“BinaryTreeisEmpty!”);else{stack[++top]=p;while(top>0)（循环及控制1分）{p=stack[top--];if(!(p->Lchild!=NULL&&p->Rchild!=NULL))（判断部分3分）{if(p->Lchild==NULL&&p->Rchild=

7、=NULL)num0++;elseif(p->Lchild!=NULL

8、

9、p->Rchild!=NULL)num1++;}if(p->Rchild!=NULL)stack[++top]=p->Rchild;（进栈部分1分）if(p->Lchild!=NULL)stack[++top]=p->Lchild;}printf(“Thenode’snumberofdegreeequal1is:”,num1);（输出1分）printf(“Thenode’snumberofdegreeequal0is:”,num0);}共7页第7页}⑵从

10、根结点开始按层次次序“自上而下，从左至右”输出树中的各结点的算法。（6分）#defineMAXNODE50voidLevelorder_output(BTNode*