旧数据结构导论试卷三

个人采集整理仅供参照学习数据构造导论试题三（课程代码：2142）一、单项选择题（本大题共15小题，每题2分，共30分）在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。资料个人采集整理，勿做商业用途1．在储蓄数据时，平时不单要储蓄各数据元素的值，并且还要储蓄【C】A.数据的办理方法B．数据元素的种类C．数据元素之间的关系D．数据的储蓄方法2．程序段for（i=0;i<n;i++）for(j=1;j<=n;j++)x++;此中n为正整数，则语句x++履行了次。【】A.n2B.n3C.3nD.2n3．单链表拥有的特色是【A】A．可随机接见任一元素B．插入、删除不需要挪动元素C．不用预先预计储蓄空间D．所需空间与线性表长度成正比4．在拥有n个结点的有序单链表中插入一个新结点并仍旧有序的时间复杂度是【B】A．0(1)B．O(n)C．O(n2)D．O(nlog2n)5．若某线性表中最常用的操作是取第i个元素和找第i个元素的直接前趋，则最节俭时间的储蓄形式为【A】资料个人采集整理，勿做商业用途A.序次表B.单链表C.双链表D．循环链表6．设数组Data[0..m-1]作为循环行列的储蓄空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为【】资料个人采集整理，勿做商业用途A．front=front+1B．front=(front+1)％mC．rear=(rear+1)%mD．front=(front+1)％(m-1)7．下边不属于特别矩阵的是【C】A．对角矩阵B．三角矩阵C．罕见矩阵D．对称矩阵8．设栈S和行列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6挨次经过栈S，一个元素出栈后即进入行列Q，若6个元素出列的序次是e2，e4，e3，e6，e5，e1，则栈S的容量最少应当是【】资料个人采集整理，勿做商业用途A．6B．4C．3D．29．对一个满二叉树，m个叶子结点，n个结点，深度为h，则【】A．n=h+mB．h+m=2nC．m=h-1D．n=2h-110．一棵二叉树拥有10个度为2的结点，则该二叉树的叶子结点个数是【】C.12D.不确立11．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为【】资料个人采集整理，勿做商业用途A．2hB．2h-1C．2h+lD．h+112．长度为6的有序表采纳序次储蓄构造，采纳二分查找法，在等概率状况下，查找成功时的平均查找长度是【】资料个人采集整理，勿做商业用途A．7／3B．8／3C．7／6D．5／613．有一个按元素值排好序的序次表(长度大于2)，分别用序次查找和二分查找两种方法查找给定值相等的元素，比较次数分别是s和b，在查找成功的状况下，s和b的关系是【】1/3个人采集整理仅供参照学习资料个人采集整理，勿做商业用途A．s＝bB．s>bC．s<bD．不必定14．下述排序方法中，比较次数与待排序记录的初始状态没关的是【】A．直接插入排序B．迅速排序C．直接选择排序D．冒泡排序15．排序的方法有好多种，从未排序序列中挨次拿出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确地点上的排序方法是【】资料个人采集整理，勿做商业用途A．选择排序B．迅速排序C．直接插入排序D．冒泡排序二、填空题（本大题共15小题，每题2分，共30分）请在每题的空格中填上正确答案。错填、不填均无分。1．是数据的不行切割的最小表记单位，可是它平时不拥有完好确立的实质意义，或不被看作一个整体对待。2．一般地，运算是指在任何逻辑构造上施加的操作，依据操作的收效，可将运算分红加工型运算和两种基本种类。资料个人采集整理，勿做商业用途3．当线性表的元素个数基本牢固，且极少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采纳_______储蓄构造。资料个人采集整理，勿做商业用途4．有一长度为n的序次表，假设删除表中任一元素的概率同样，则删除一个元素平均需要挪动元素的个数是________。资料个人采集整理，勿做商业用途5．关于非空的双链表,在指针p所指结点后插入一个新结点需改正的指针共______个。6．用push表示入栈操作，pop表示出栈操作。有一个空栈，现有输入序列为1、2、3、4，为了获得1、3、4、2的出栈序次，相应的出栈和入栈操作序列为。资料个人采集整理，勿做商业用途7．一维数组Data[n]用来表示循环行列，队头指针front和队尾指针rear定义为整型变量，队空的条件是。资料个人采集整理，勿做商业用途8．有一个10阶对称矩阵A，现以行为主序储蓄其下三角（包含对角线）中的元素，每个元素占1个储蓄单元，A[0][0]的地点为1000，则A[8][5]的地点是。资料个人采集整理，勿做商业用途9．一棵树中全部结点层数的最大值称为该树的。10．在拥有n（n>0）个结点的二叉链表中，共有个非空指针域。11．某二叉树的先根遍历序列和中根遍历序列均为abcd,则它的后根遍历序列为。12．长度为6的有序表采纳二分查找，共有个元素只需3次比较就能够查找到。13．假如按重点字值递加的序次挨次将n个结点插入到初始为空的二叉排序树中，则对这样的二叉排序树查找时，平均比较次数为__________。资料个人采集整理，勿做商业用途14．对一组记录（54，38，96，23，18，70，61，44，80）进行直接插入排序，当第7个记录61插入到有序表时，为找寻插入地点需比较次。资料个人采集整理，勿做商业用途15．对n个元素进行直接插入排序，在全部元素有序的状况下比较的次数最少，其比较次数为，而在全部元素逆序状况下比较的次数最多。资料个人采集整理，勿做商业用途三、应用题（本大题共5小题，每题5分，共25分）1．以下单链表分别独自履行以下各程序段，此后画出新的结果表示图。(1)．R->data=P->data;2/3个人采集整理仅供参照学习(2)．R->data=P->next->data;(3)．T=P;while(T!=NULL){T->data=T->data*2;T=T->next;}资料个人采集整理，勿做商业用途2．有5个元素，其入栈序次为：A，B，C，D，E，在各样可能的出栈序次中，以元素C，D最初出栈（即C第一个出栈且D第二个出栈）的序次有哪几个？资料个人采集整理，勿做商业用途3．对以以下列图所示的一棵树，试画出它相对应的二叉树。4．给定表（7，16，4，8，20，9，6，18，5），试按元素在表中的序次将它们挨次插入一棵初始为空的二叉排序树，请画出插入达成后的二叉排序树并计算在等概率状况下该二叉排序树的平均查找长度。资料个人采集整理，勿做商业用途5．以重点字序列{70,73,69,23,93,18,11,68}为例，手工履行迅速排序算法，写出每一趟排序的结果。资料个人采集整理，勿做商业用途四、算法设计题（本大题共2小题，第1小题8分，第2小题7分，共15分）1．设序次表L中的数据元素递加有序。试设计一个算法：将数据元素x插入到序次表的适当地点上，以保持该表的有序性。资料个人采集整理，勿做商