当前位置:主页 > 大学试题及答案 >

数据结构试题及答案【完整版】

发布时间:2017-12-21 编辑:一米阳光

数据结构试题及答案【完整版】

一、单选题(每小题2分,共8分)

1、在一个长度为n的顺序存储的线性表中,删除第i个元素(1in)时,需要从前向后依次前移     个元素。

A  1i                   B   ni1

C  nj1               C   i

2、设一个广义表中结点的个数为n,则求广义表深度算法的时间复杂度为       

A ()(1                 B()(n

C ()(n2                D()(1og2n

3、假定一个顺序队列的队首和队尾指针分别为1r,则判断队空的条件为        

A  f1= =r               B   r1= =f

C  f= =0                   D   f= =r

4、从堆中删除一个元素的时间复杂度为          

A  ()(1               B   On

C  ()(1og2n            D ()(nlog2n

二、填空题(每空1分,共32分)

1、在线性结构、树结构和图结构中,前驱和后继结点之间分别存在着                 

                     的联系。

2、在线性表的单链接存储中,若一个元素所在结点的地址为p,则其后继结点的地址为 

               ,若假定p为一个数组a中的下标,则其后继结点的下标的            

3、在初始化一个稀疏矩阵的函数定义中,矩阵形参应说明为             参数。

4、栈又称为           表,队列又称为              表。

5、后缀表达式“4 5+3*2 4+ *”的值为                

6、一棵深度为5的满二叉树中的结点较为         个,一棵深度为3的满四叉树中的结点数为          个。

7、对于一棵含有40个结点的理想平衡树,它的高度为            

8、从一棵二叉搜索树中查找一个元素时,若元素的值等于根结点的值,则表明         

         ,若元素的值小于根结点的值,则继续向                 查找,若元素的大于根结点的              查找。

9、当从一个小根堆中删除一个元素时,需要把                               元素填补到               位置,然后再长条件把它逐层                  调整。

10、对于一个具有n个顶点的图,若采用邻接炬阵表示,则矩阵大小为                

11、对于一个具有n个顶点和e条边的连通图,其生成树中的顶点数和边数分别为      

         

12、二分查找过程所对应的判定树既是一棵               ,又是一棵               

13、若长度n=10000的线性表进行二级索引存储:每级索引表中的索引项是下一级20个记录的索引,则一级索引表的长度为         ,二级泵引表的长度为         

14、在一棵20阶的B-树中,每个非树根结点的关键字数目最少为     个,最多为     个。

15、每次直接或通过基准元素间接比较两个元素,若出现逆序排列时就交换它们的位置,此种排序方法叫做             排序;每次使两个相邻的有序表合并成一个有序表的排序方法叫做          排序。

16、在归并排序中,进行每趟归并的时间复杂度为                 ,整个排序过程的时间复杂度为               ,空间复杂度为                 

三、运算题。(每小题6分,共24分)

   1.假定一棵普通树的广义表表示为:abe),cfhij),g),分别写出先根、后根、按层遍历的结果。

        先根:                          

        后根:                          

        按层:                          

   2.己知一个带权图的顶点集V和边集6分别为:

        V={01234567}

        E={018,(025,(032,(156,(2325,(2413,(359,(3610,(464,(5720

        则求出该图的最小生成树的权。

        最小生成树的权:                 

   3.对于线性表(1825635042329066)进行散列存储时,若选用HK=K9作为散列函数,则散列地址为0的元素有     个,散列地址为3的元素有    个,散列地址为5的元素有        个。

   4.假定一组记录的排序码力(4679563840802534),在对其进行快速排序的过程中,对应二叉搜索村的深度为          ,分支结点数为            

四、阅读算法,回答问题(每小题8分,共16分)

1、  void AALnode *&HL

{ 

InitListHL);

InsertRearHL30);

InsertRearHL50);

int a[5]={15892612}

for}int i=0i<5i++ InsertFrontHLa[ i ]);

}

该核算法被调用执行后,得到的以HL为表头指针的单链表中的数据元素依次为:

                                     

2、  void AAHeap&HBTconst Elem type item

//HBT为一个小根堆 

{ 

HBT.heap[HBT.size]=item;

HBT.size++

eLemType x=item

int i=HBT.size1

whilei=0{

int j=i1/2

ifx>=HBT.heap[j]break;

HBT.heap[i]=HBT.heap[j];

i=j;}HBT.heap[i]=x;

}

该算法的功能为:

                                                          

   五、算法填空,在画有横线和地方填写合适的内容(10分)

   从一维数组A[n]中二分查找关键字为K的元素的递归算法,若查找成功则返回对应元素的下标,否则返回—1

   int BinschElem Type A[]int lowint highKey Type K

   {

iflow<=high

{

 int mid=low+high/2

 ifK= =A[mid].key                                       

 else if(K<A[mid].key)                                        

 else                                    

}

else return1

}

六、编写算法(10分)

   编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法,若查找item带回整个结点的值并返回ture,否则返回false

   bool FindBtreeNode*BSTElemType&item

试题答案及评分标准

一、单选题(每小题2分,共8分)

    评分标准:选对者得2分,否则不得分。

    1A      2B       3D       4C

二、填空题(每空1分,共32分)

    评分标准:每空得1分,否则不得分。

    111   1N        MN  (或者11    1N   MN

    2p>next  a[p]. next

    3、引用

    4、后进先出    先进先出

    5162

    631    21

    76

8、查找成功   左子树    右子树

9、堆尾  堆顶  向下

10n2

11n   n1

12、二叉搜索树理想平衡树(次序无先后)

13500   25

149   19

15、交换     二路归并

16  ()(n  ()(nlog2n  ()(n

三、运算题(每小题6分,共24分)

    1.先根:abecfhijgd;(2分)

      后根:ebhIjfgcda;(2分)

      按层:abcdefghij2分)

    2.最小生成树的权:55

    33   1   2       每个数据占2

    45   6           每个数据占3

四、阅读算法,回答问题(每小题8分,共16分)

    1.(122698153050

    评分标准:有一处错误扣4分,两处及以上错误不得分。

    2,向HBT堆中插入一个值为item的元素,使得插入后仍是一个堆。

    评分标准:请根据叙述情况酌情给分。

五、算法填空,在画有横线的地方填写合适的内容(10分)。

    return  mid

    return  BinschA 1owmid1 K

    return  BinschAtmid1highK

    评分标准:对一空得3分,全对得10分。

六、编写算法(10分)

    评分标准:请根据编程情况酌情给分。

bool   FindBtreeNode*BSTElernTypeitem

{

        whileBST!一NULL

        {

            ifitem= =BST>data{item=BST>data  return  true;}

            else ifitemBST>dataBSTBST>left;

else BST=BST>right

        }

        return    false;

    }

分享这篇文章:

看过本文的人还喜欢以下文章

大学军事理论考试试题及答案
大学军事理论考试试题及答案
大学军事理论考试试题及答案 一、填空题 1、现代国防的类型,按照性质可分为 扩张型 和 自卫型 ,按照形式可分为 联盟型 和 中立型 。 2、 学校国防教育 是国民国防教育的基础,是实施素质教育的重要内容。对小学,初中,高中,大学的国防教育提出了不同层次的要求。 3...
2018大学试题及答案汇总【完整版】大学期末考试题及答案
2018大学试题及答案汇总【完整版】大学期末考试题及答案
大学生试题及答案网为您精心整理提供历年期末考试题及参考答案,期末复习试卷及答案,供各位同学参考复习,了解考试题型和参考内容,做到有目的的复习巩固,努力的人成绩不会太差,包括理工科、文科、计算机、材料、土木、文学、经管、外语、医学、数学等专业精选试题,...
大学语文试题及答案
大学语文试题及答案
大学语文试题及答案 一、选择题 1下面哪项不属新月派三美理论(C) A音乐美 B建筑美 C语言美 D绘画美 2《乡愁》的作者是(D) A徐志摩 B郁达夫 C郭沫若 D余光中 3下面哪项不属知性散文的特点:(A) A语言辛辣,文笔犀利。 B文章旁征博引 C描摹人生活灵活现,讽刺世态...
2018《市场营销》试题及答案
2018《市场营销》试题及答案
《市场营销》试题及答案 一、选择题 1、企业营销活动中体现的社会价值观、伦理道德观,充分考虑社会效益,既自觉维护自然生态平衡,更自觉抵制各种有害营销,被称为(A)。 A、广义绿色营销 B、狭义绿色营销 C、整合营销 D、关系营销 2、企业在营销活动中,谋求消费者...
2017大学思修试题及答案完整版-思想道德修养与法律基础期末考试题及答案
2017大学思修试题及答案完整版-思想道德修养与法律基础期末考试题及答案
2017思修试题及答案 思想道德修养与法律基础期末试题及答案 一、填空题(每小题2分,共20分) 1、当代社会公共生活的特征主要表现在:(活动范围的广泛性、交往对象的复杂性、活动方式的多样性)。 2、在发展社会主义市场经济的条件下,在全面建设小康社会的进程中,依据我国...
《宪法学》试题及答案
《宪法学》试题及答案
《宪法学》试题及答案 一、选择题 1、我国有权对宪法进行解释的机关是( B)。 A、全国人大 B、全国人大常委会 C、最高法院 D、国务院 2、资产阶级学者以宪法是否具有统一的法典形式将宪法分为( A)。 A. 成文与不成文宪法 B、规范与不规范宪法 C、刚性与柔性宪法 D、钦定...

 

以上就是阳光美文网为您精心整理提供的关于《数据结构试题及答案【完整版】》全文,希望对您有所帮助。