数据结构试卷2006（A）
一．单项选择题(每小题1分,共30分)
1．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。
    A．q一）next＝p一）next；p一）next＝q；
    B．p一）next＝q一）next；q＝p；
    C．q一）next＝p一）next；p一）next＝q；
    D．p一）next＝q一）next；  q一）next＝p；
3．在一个顺序队列中，队首指针指向队首元素的位置。
    A．前一个      B．后一个      C．当前
1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................( )
        ⑴.R-F     ⑵.n+R-F     ⑶.(R-F+1)mod n    ⑷.(n+R-F)mod n
2、n个记录直接插入排序所需的记录最小移动次数是.......( )
        ⑴.2(n-1)    ⑵.2n     ⑶.(n+3)(n-2)/2    ⑷.n2/2
3、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................
        ⑴.向量     ⑵.树     ⑶.图     ⑷.二叉树
二．填空题（每空1分 共15分）
1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个( ),且存在一条从根到该结点的( )。
2、评价数据结构的两条基本标准是：( )和( )。
3、对于顺序存储的栈，因为栈的空间是有限的，在进行( )运算时，可能发生栈的上溢，在进行( )运算时，可能发生栈的下溢。
4、对于单链表形式的队列，其空队列的F指针和R指针都等于( )。
5、若S1=‘linked￡st',S2='ring',则S1//S2=( )。
6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为( ),最多为( )。
三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题3分，共9分)
1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................( )
        ⑴.R-F     ⑵.n+R-F     ⑶.(R-F+1)mod n    ⑷.(n+R-F）mod n
2、n个记录直接插入排序所需的记录最小移动次数是.......( )
        ⑴.2(n-1)    ⑵.2n     ⑶.(n+3)(n-2)/2    ⑷.n2/2
3、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................
        ⑴.向量     ⑵.树     ⑶.图     ⑷.二叉树
  1．数据的逻辑结构被分为___________、____________、___________和___________四种。
    2．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度___________为，在表尾插入元素的时间复杂度为____________。
    3．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_____________、___________和___________三项。
    4．在广义表的存储结构中，每个结点均包含有________个域。
    5．当用长度为N的数组顺序存储一个栈时，假定角top＝＝N表示栈空，则表示栈满的条件为____________。
    6．假定一棵三叉树的结点个数为50，则它的最小深度为_____________，最大深度为_____________。
    7．在一棵二叉树中，第5层上的结点数最多为_________。
    8．在一棵高度为h的理想平衡树中，最少含有___________个结点，最多含有_________个结点。
    9．在一个小根堆中，堆顶结点的值是所有结点中的______________，在一个大根堆中，堆顶结点的值是所有结点中的______________。
    10．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要____________条边。
    11．假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和边集数组表示时，其相
应的空间复杂度分别为__________、__________和__________。
    12．以二分查我方法查一个线性表时，此线性表必须是___________存储的________表。
    13．在索引表中，若一个索引项对应主表中的一条记录，则称此索引为_________索引，若对应主表中的若干条记录，则称此索引为__________索引。
    14．在线性表的散列存储中，处理冲突有________和________两种方法。
    15．向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树的高度比原树增________；从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树的高度比原树减_________。
    16．快速排序在平均情况下的空间复杂度为_______________，在最坏情况下的空间复杂度为________________。
三、运算题（每小题6分，共24分）二叉树的深度为k
    1．假定二个大根堆为（56，38，42，30，25，40，35，20），则依次从中删除两个元素后得到的堆为______________。
    2．已知一个图的顶点集V和边集H分别为：
    V＝{0，1，2，3，4，5，6，7}
    E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
    按照克鲁斯卡尔算法得到最小生成树，拭写出在最小生成树中依次得到的各条边。
    ______，______，______，______，______，______，______。
    3．假定一组数据的初始堆为（84，79，56，42，40，46，50，38），请写出在堆排序阶段进行前三次对换和筛运算后数据的排列情况。
    数据排列情况：_____________________________。
    4．假定一组记录的排序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序的过程中，第三趟归并后的结果为：____________________。
 
三．判断题(每小题1分 共13分 正确的打“”，反之打“”)
1、 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面...............( )
2、线性表中的每个结点最多只有一个前驱和一个后继。......( )
3、从本质上看，文件是一种非线性结构。..................( )
4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................( )
5、栈和队列逻辑上都是线性表。..........................( )
6、单链表从任何一个结点出发，都能访问到所有结点........( )
7、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................( )
8、对某一确定的可利用空间表，给定一串内存请求，若采用最佳适配和首次适配这两
种方法之中的一种能满足该串请求，则也一定能用另一种方法满足该串请求。( )
9、多维数组是向量的推广。..............................( )
10、设串ai...aj...an,则有ord(ai)>ord(aj)。....( )
11、设串S的长度为n,则S的子串个数为n(n+1)/2。...........( )
12、一般树和二叉树的结点数目都可以为0。................( )
13、在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。( )
14、网络的最小代价生成树是唯一的。.....................( )
15、磁带是顺序存取的外存储设备。.......................( )

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。