uestc软件技术基础试题答案1

电子科技大学二零零二至二零零三学年第二学期《软件技术基础》课程考试题（120分钟）考试日期20XX年7月日-二三四五六七八九十总分评卷教师、填空题（共30分,每空1分）1.线性表、栈和队列都是线性数据结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素，所以栈又被称为后进先出的线性表；对于队列只能在队尾插入元素，在队头删除元素。2、采用顺序存储结构，具有n个存储单元的循环队列，在队满时共有n-1个元素。3、在双链表中，每个结点含有两个指针域，一个指向其前驱结点，另一个指向其后继结点。4.一个如下所示的稀疏矩阵的三元组为：%020?132300021300-1033-1、0000J昌45J5.深度为n的完全二叉树最多有2n-1个结点，该完全二叉树的第i层有2i-1个结点，该完全二叉树最少有2n-1个结点。6.在右图所示的图结构中：E结点的度为3,其出度为0,E、F是H结点的邻接点，从A到E的路径有3，其长度分别为2、3、4。二、选择题：（20分，每题2分）.以下程序段给数组中的所有元素输入数据，请选择正确的答案填入，使scanf语句完整。#include<stdio.h>main（）{inta[10],i=0;for（i=0;i<10;i++）scanf（"％d"，（C））;

}A.aB.a++C.a+iD.a[i]2、请阅读程序片段：charstr[]=“Hello”,*p=str;printf（“%d”,*（p+4））;TOC\o"1-5"\h\z上面程序段的输出结果是B。A.68B.0C.字符‘D’的ASIC码值D.字符‘D’的地址值.用链式存储结构表示线性表的优点是C。A,便于随机存储B.花费的存储空间较顺序表少C.插入和删除元素的效率高D.数据元素的物理位置能反映出其逻辑关系.在顺序存储结构的循环队列中，假设front和rear分别为队头和队尾指针，则判断队列为空的条件为_C。A.front==rear+1B.front+1==rearC.front==rearD.rear==0.以下运算中B不是队列的基本运算。A.从队尾插入一个元素B.从队列中删除第个元素C.判断一个队列是否为空D.读取队头元素的值已知一棵二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK中序遍历：HFIEJKG该二又树根的右子树的根为C：A．EB.FC.GD.H已知一有序的顺序表（长度大于2），分别用顺序查找和二分查找的方法查找某一元素，比较的次数分别为S和B,在查找不成功的情况下，S和B的关系为B。A.S=BB.S>BC.S<BD.S<=B三口判断题（正确的填“”，错误的填“”分，每题分）4．给定一棵二叉树的先序遍历序列和后序遍历序列就可以构造出该二叉树。（B）（8分）四．将下列的森林转换为对应的二叉树，画出详细的转换过程（8分）解：1、抹线BCDM•。BCDM•。五．程序设计（24分）1、已知一个栈S,其表中的元素为（25,70,38,65,71,11,68,34,90）,设计程序用单链表存储该链栈，并插入一个元素100,最后要求将插入之后的栈S中的元素打印出来。要求创建链栈和插入和打印各用一个函数来实现。（16分）得分点：1、主函数的内容,正确进行各个函数的调用4分2、创建链队列函数5分3、插入函数4分4、打印函数3分2.已知顺序表L中的元素为整型且递减有序，且已知主函数，设计一函数insert在其中插入整型元素X,使之仍保持递减有序。（8分）#include<stdio.h>#defineMAXNUM15typedefstruct/*定义已知顺序表的结构类型*/{intdata[MAXNUM];intnum;}listtype;intinsert(listtype*l,intx);/*插入函数说明*/main(){listtypelist={19,17,15,13,11,9,7,5,13,1},*l;/*初始化顺序表*/inti,x,temp;l=&list;l->num=10;scanf(“%d”,&x);temp=insert(l,x);/*调用插入函数*/i