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

澳门银河赌城官网

发布时间: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、企业在考虑组合策略时,首先需要确定生产经营什么产品来满足的需要(D、目标市场)。 A.消费者 B.顾客 C.社会 D.目标市场 2.每种产品实质上是为满足市场需要而提供的(A)。 A.服务 B.质量 C.效用 D.功能 3.影响...
《区域经济学》试题及答案
《区域经济学》试题及答案
《区域经济学》试题及答案 一、判断题 ( )1、区域经济的研究范围不再是一个国家内的区域经济,其重点是城市区域经济。 ( )2、诺斯的区域经济观点强调经济活动的内容以及空间组织。 ( )3、区位单位是经济区域的布局主体。 ( )4、欧洲一体化的长远目标是建立经济...
大学《管理会计》期末试题及答案
大学《管理会计》期末试题及答案
大学《管理会计》期末试题及答案 一、选择题 (每小题1分,共20分) 1.由于对固定制造费用的处理不同,按变动成本法计算的期末存货价值比按完全成本法计算的期末存货价值(A)。 A.一定较低 B.一定较高 C.一定相等 D.高低不一定 2.与贡献边际率和为1的是(B)。 A.安全...
《中国现当代文学专题》期末复习考试及答案
《中国现当代文学专题》期末复习考试及答案
《中国现当代文学专题》期末复习考试及答案 第一部分:鲁迅专题试题及参考答案 一、填空题 1.鲁迅唯一的一篇以青年爱情为题材的小说是《-伤逝-》。 2.吕纬甫和魏连殳分别是鲁迅小说《-在酒楼上-》和《孤独者》中的主人公。 3.据孙伏园回忆,刘半农曾赠送鲁迅一幅联...
2017大学思修试题及答案银河国际网址-思想道德修养与法律基础期末考试题及答案
2017大学思修试题及答案银河国际网址-思想道德修养与法律基础期末考试题及答案
2017思修试题及答案 思想道德修养与法律基础期末试题及答案 一、填空题(每小题2分,共20分) 1、当代社会公共生活的特征主要表现在:(活动范围的广泛性、交往对象的复杂性、活动方式的多样性)。 2、在发展社会主义市场经济的条件下,在全面建设小康社会的进程中,依据我国...
大学语文试题及答案
大学语文试题及答案
大学语文试题及答案 一、选择题 1下面哪项不属新月派三美理论(C) A音乐美 B建筑美 C语言美 D绘画美 2《乡愁》的作者是(D) A徐志摩 B郁达夫 C郭沫若 D余光中 3下面哪项不属知性散文的特点:(A) A语言辛辣,文笔犀利。 B文章旁征博引 C描摹人生活灵活现,讽刺世态...

 

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