数据结构试题及答案【银河国际网址】 - 澳门银河赌城官网
当前位置:主页 > 大学试题及答案 >

澳门银河赌城官网

发布时间: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;

    }

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

2017大学思修试题及答案银河国际网址-思想道德修养与法律基础期末考试题及答案
2017大学思修试题及答案银河国际网址-思想道德修养与法律基础期末考试题及答案
2017思修试题及答案 思想道德修养与法律基础期末试题及答案 一、填空题(每小题2分,共20分) 1、当代社会公共生活的特征主要表现在:(活动范围的广泛性、交往对象的复杂性、活动方式的多样性)。 2、在发展社会主义市场经济的条件下,在全面建设小康社会的进程中,依据我国...
大学语文试题及答案
大学语文试题及答案
大学语文试题及答案 一、选择题 1下面哪项不属新月派三美理论(C) A音乐美 B建筑美 C语言美 D绘画美 2《乡愁》的作者是(D) A徐志摩 B郁达夫 C郭沫若 D余光中 3下面哪项不属知性散文的特点:(A) A语言辛辣,文笔犀利。 B文章旁征博引 C描摹人生活灵活现,讽刺世态...
中级财务会计试题及答案
中级财务会计试题及答案
《中级财务会计》试题及答案 一、选择题 1、企业期末存货计价如果过高,可能会引起(C) A、当期销售收入增加 B、当期销售成本增加 C、当期利润增加 D、当期所得税减少 2、某企业2008年12月30日购入一台不需安装的设备,并已交付使用。设备原价80000元,预计使用5年,...
《C++程序设计》试题及答案【银河国际网址】
《C++程序设计》试题及答案【银河国际网址】
《C++程序设计》试题及答案 一、填空题 1、当使用关键字__(void)_ 作为函数返回类型时,该函数不返回任何值。 2、在类中必须声明成员函数的__函数头__,成员函数的_函数体_部分可以写在类外。 3、如果需要在被调函数运行期间,改变主调函数中实参变量的值,则函数的...
计算机应用基础试题及答案【银河国际网址】
计算机应用基础试题及答案【银河国际网址】
《计算机应用基础》试题及答案 为大家整理历年常考的3套大学《计算机应用基础》试题及答案,供各位同学复习参考。 第一套 一、简答题(10分) 1、什么叫文件? 2、Windows3、2的基本组成包括哪几个主要部分? 二、选择题(10分) 1.第一台电子计算机于 年在美国诞生。...
公共政策试题及答案【银河国际网址】
公共政策试题及答案【银河国际网址】
《公共政策》试题及答案 1、简述公共政策的基本特征。 公共政策的基本特征有: 1、整体性,政策是配套,就是指由众多数量、类型不一的政策,组成政策体系,用以强化政策的整体功能; 2、超前性; 3、层次性; 4、多样性; 5、合法性。 2、简述公共政策的主要功能。 公...

 

以上就是澳门银河赌城官网美文网为您精心整理提供的关于《数据结构试题及答案【银河国际网址】》全文,希望对您有所帮助。