数据结构试卷A.doc

专业班级: 姓名: 学号: 密封线河南理工大学万方学院 200-200学年第2学期专业班级: 姓名: 学号: 密封线数据结构试卷(卷）考试方式： 闭卷 本试卷考试分数占学生总评成绩得 8 总 分题号一二三四核分人得分 复查总分 总复查人 得分评卷人 毋小省一、单选题(本题得每一备选答案中,只有一个就是正确得，请把您认为正确得答案得题号填入题干得括号内，每小题分，共30分）1、 若长度为得线性表采用顺序存储结构,在其第i个位置插入一个新元素得算法得时间复杂度为( ）。（1in+） （1） O（0） （2) O(） （3) O（n） （4）O（n）2、在单链表中所指结点后插入s所指结点，则下列语句正确得就是（ ) (1)pnext=s； nt=p； （） sext=pnext； pnxt=s；（） snexp； pnext=s； (4） ext=snext；sp;3、 设一个栈得输入序列为A,B,D,则借助一个栈所得到得输出序列不可能就是（ )(1）A,B，C, （2）D,，B，A (3)A，C，D,B （4），A，B,C4、若由树林转化得到得二叉树就是非空得二叉树，则二叉树形状就是( )(1) 根结点无右子树得二叉树 (2) 根结点无左子树得二叉树(3） 根结点可能有左二叉树与右二叉树 （）根结点只有一个孩子结点得二叉树5.设二叉树得根为第一层，则深度为得二叉树结点数最多为( )（1)i （2） i1 （3）2i (4）2 1 6、 首先访问结点得左子树,然后访问该结点,最后访问结点得右子树，这种遍历称为（）（1）前序遍历 (2）后序遍历 （3）中序遍历 （）层次遍历7。给定下列有向图，从顶点1出发,其广度优先搜索序列为（ ）（1）12534 （2）1243 () 14325 （4）13458.散列表中得冲突就是指（ ）（）两个元素具有相同得序号 （2) 两个元素得关键字相同,而其她属性相同(）不同得关键字对应相同得存储地址 （） 数据元素得地址相同9、 线性表若采用链式存储结构时,要求内存中可用存储单元得地址：（ ）（1）必须就是连续得 (2)部分地址必须就是连续得（3）一定就是不连续得 （)连续或不连续都可以.下面程序段得时间复杂度为（ ） f (inti=1;im；i+) for(int j=1;jn；j+） j=j; （) (m) (2)(n） （3） (*n） （4） O(m+)1当利用大小位得数组顺序存储一个队列时，该队列得最大长度为（ ）(1）n- （）n-1 （) n ()11.对线性表进行折半搜索时，要求线性表必须( )（）顺序存储 （2)顺序存储且结点按关键字有序（）链式存储 (4)链式存储且结点按关键字有序13。采用线性探查法解决冲突时所产生得一系列后续地址( )(）必须大于等于原散列地址 （2）必须小于等于原散列地址（3)可以大于或小于但不等于原散列地址 （4） 对地址在何处没有限制14栈得插入与删除操作在( ）进行。（1)栈顶 （2)栈底 (3)任意位置 (4）指定位置15.在一个顺序存储得循环队列中,对头指针指向队列得（ )位置。（1)前一个 (2)后一个 (3)当前 （4）后面得分评卷人 毋小省二、填空题（每空1分，共20分)1、数据得逻辑结构被分为_，_,_,_。、单链表与循环链表得区别就是_。3、在一个循环队列中，判断对空得条件就是串就是_，判断对满得条件就是串就是_4、 从有序表（12，18，30，43，56,78，82,95）中一次折半搜索3与56元素就是,其比较次数分别为_与_.、与哈西表得平均查找长度有关得三个因素分别就是_，_,_。6、对于一个具有个顶点与e条边得连通图,其生成树中得顶点数个边数分别为_与_。、在二叉排序树中，左子树所有结点得关键字值都_该结点得关键码值,而右子树中所有结点得关键字值都_该结点得关键码值.8、在一个小顶堆中，堆顶元素得值就是所有结点中得_,在一个大顶堆中，堆顶元素得值就是所有结点中得_.9、假定一组纪录得关键字为(6，79,56,8，40,80），对其进行快速排序得一次划分得结果为_。、在一个网络得所有生成树中,各边权值之与最小得生成树，称为该网络得_。得分评卷人 毋小省三、判断题（判断下列各题就是否正确,若正确在（)内打“，否则“”。每小题1分，共10分)（ ）1、 栈与队列得存储方式既可就是顺序方式，也可就是链接方式。（ )、 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。（ )3、二叉树中任何一个结点得度都就是2。( ）4、有回路得有向图不能完成拓扑排序。（ )5、按先根次序遍历森林等同于按先序法遍历对应得二叉树.（ )、n（1)个顶点得无向连通图最少由n-1条边。（ )7、有向图得邻接表表示中边表中结点得总数与有向图中有向边得条数相等。（ ）8、一个无向图得邻接矩阵中各元素之与与图中边得条数相等。（ ）9、归并排序要求待排序文件已部分排序。( ）、顺序检索时数据得存储方式可以就是顺序得，也可以就是链接得。得分评卷人毋小省四、综合题(共40分)已知某系统在通信联络中只可能出现8种字符，其概率分别为0、0,、29,0、0，0、0,0、，0、23，0、0，、11，试设计哈夫曼编码.（7分）.设待排序得记录得关键字序列为12，2，6，30,10，2，8，写出使用链式基数排序每趟得结果.（6分）3、拓扑排序得结果不就是唯一得，对于下图得结点进行拓扑排序，试写出其中得任意5个。（5分）V1V3V4V6V5V7V8V9V2A4分别按前序、后序、对称序列写出下图二叉树得结点，并转化为树林,分别按先根次序、后根次序列出其结点。（6分)IFDEABCGH5、已知一组关键字为（19，14,23，01，68，20,84，2,55,11,10，9）,则按哈希函数H（ky)=ey M 13，表长为,分别用线性探查法与链地址法处理冲突构造哈希表,并计算各平均查找长度。（10分）、程序填空(6分)对有序表R至Rn1进行二分查找，成功时返回记录在表中得位置，失败时返回0、Stuctsqliskeytypekey;； ntbinsch（slist R ，ktyp k） /在表R中查找关键字k in low ，hih,md； l0; h=n-1； whie（ ） mid(lohigh）2; if(k=md、key） etur mid； lse if（Rmid、ke ) ； le ； return ；