快捷导航
帮助中心知识拓展客服QQ 515224986
扫码加微信
数据结构I笔试复习题(高起专)(2017-04-20)
一、单选题(每小题2分)
1. 数据的不可分割的最小标识单位是
    A. 数据项                           B. 数据记录
    C. 数据元素                         D. 数据变量
2.下列程序段 for(i=1;i<=n;i++) A[i,j]=0;的时间复杂度是
A. O(1)                             B. O(n/2)   
C. O(n2)                             D.  O(n)  
3. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素,元素的移动次数为
    A.n-i+1                             B.n-i
    C.i                                 D.i-1
4.在一个单链表中,已知q结点是p结点的前驱结点,若在q 和p之间插入结点s,则执行操作
    A. s->next=p->next;p->next=s;       B. s->next=p; q->next=s
    C. q->next=s;s->next=p;             D. p->next=s;s->next=q;
5. 判断两个串大小的基本准则是
A. 两个串长度的大小                B. 两个串中首字符的大小
C. 两个串中大写字母的多少          D. 第一个不等字符的大小参考答案:1、A  2、D  3、A  4、B  5、D  二、填空题(每小题1分)
1. 数据的逻辑结构在计算机存储器内的表示,称为数据的(           )。
2. 一个算法具有五个特性:(          )、确定性、可行性、有零个或多个输入、有输出。
3.顺序存储结构是通过(          )表示元素之间的关系的。
4. 在链表的结点中,数据元素所占的存储量和整个结点所占的存储量之比称作(           )。
5.已知指针p指向单链表中某个结点,则语句p -> next =p -> next -> next的作用是(         )p的后继。
6.假设元素只能按a,b,c,d的顺序依次进栈,且得到的出栈序列中的第一个元素为c,则可能得到的出栈序列为cdba,不可能得到的出栈序列为(               )。
7.结点数为20的二叉树可能达期的最大高度为(                 )。
8. 在有向图中,以顶点v为终点的边的数目称为v的(                )。
参考答案:
1. 存储结构2.有穷性3.物理上相邻4. 存储密度5. 删除 6.cdab 7.20 8. 入度三、应用题(每小题8分)
1.链表与顺序表的应用比较。
2.证明:深度为k的二叉树中至多含有 2k-1 个结点,(k≥1)。
3.采用直接插入排序算法,将数组中n个元素(52   49  80  36  14  58  61  23  )由小到大进行排序。
4.已知无向图G的邻接矩阵如图所示。
(1)画出该无向图G。(2)写出按广度优先搜索时的访问序列。参考答案:
1.(1)用顺序的方式存储线性表,内存的存储密度高,可以随机地存取结点;在顺序表中插入或删除一个数据元素,平均约需移动表中一半元素,效率比较低。
  (2) 顺序表要求占用连续的存储空间,存储分配只能预先进行。如果插入操作超出了预先分配的存储区间, 需要临时扩大是非常困难的。
  (3)采用链表存储结构时则可以克服上述不足,它适合于频繁插入和删除,并且存储空间大小不能预先确定的线性表。  
2.利用归纳法。
    i=1 时,只有一个根结点。显然 2i-1=20=1 是对的。
    设对所有的j(1≤j<i),命题成立,即第j层上至多有 2j-1 个结点。   归纳证明:由归纳假设“第 i-1 层上至多有 2i-2 个结点”,又二叉树的每个结点的度至多为2,则第 i 层上
的最大结点数为第 i-1 层上最大结点数的2倍,
     即 2×2i-2=2i-1。
    由在二叉树的第 i 层上至多有 2i-1 个结点可推出,深度为k的二叉树上最大结点数为
        20+21+ ( ( ( ( ( ( +2k-1 = 2k-1
3.初始状态 52  49  80  36  14  58  61  23  
          i=1   [49  52]  80  36  14  58  61  23
          i=2   [49  52  80]  36  14  58  61  23
          i=3   [36  49  52  80]  14  58  61  23
          i=4   [14  36  49  52  80]  58  61  23
          i=5   [14  36  49  52  58  80]  61  23
          i=6   [14  36  49  52  58  61  80]  23
          i=7   [14  23  36  49  52  58   61  80]
    排序结果     [14  23  36  49   52  58  61  80]
4.(1)画出该无向图G。(略)
(2)广度优先搜索时的访问序列 V0 V1 V3 V2 V4。四、算法阅读题(本题10分)
下面的算法是实现图的邻接矩阵的广度优先搜索遍历。阅读算法,在横线处填入语句或注释。
    void BFSTraverse(MGraph G) {
   // 对以邻接矩阵存储表示的图G进行广度优先搜索遍历
    bool visited[G.vexnum];// 附设访问标识数组
    Queue Q;// 附设队列 Q
    for (v=0; v<G.vexnum; ++v)  visited[v] = (1)
         InitQueue(Q,G.vexnum);// (2)
    for ( v=0; v<G.vexnum; ++v )
      if ( (3)) {
        visited[v] = TRUE; VisitFunc(G.vexs[v]);// 访问图中第 v 个顶点
        (4)// 顶点v 入队列
        while (!QueueEmpty(Q)) {
           DeQueue(Q, u); // 队头元素出队并置为 u
           for ( w=0; w<G.vexnum; w++; )
               if ( G.arcs[u, w].adj && ! visited[w] ) {
                visited[w] = TRUE; VisitFunc(w); // (5)
                EnQueue(Q, w); // 当前访问的顶点 w 入队列 Q
                } // if
       } // while
      } // if
    DestroyQueue(Q);
   } // BFSTraverse
参考答案
(1)FALSE;
(2)初始化空队列
(3)!visited[v]
(4)EnQueue(Q, v);
(5)访问顶点w
五、算法设计题(本题10分)
设计算法InsertOrderList实现有序顺序表OrderList的插入算法,并指出其时间复杂度。
参考答案
     void InsertOrderList(OrderList &L, ElemType x){   
         // 在有序顺序表L中插入新的元素 e          for (i= L.length-1;i>=0&&x<L.elem; --i)               L.elem[i+1] = L.elem;   // 从表尾向前查找,元素右移               L.elem[i+1] = e; // 插入 e
              ++L.length;//表长增1
    } // InsertOrderList
    此算法的时间复杂度为O (L.length ) 。
东北大学免费答案

共 0 个关于本帖的回复 最后回复于 2018-6-13 15:04

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

精彩推荐

    明星用户

    QQ|Archiver|手机版|小黑屋|www.openhelp100.com ( 冀ICP备19026749号-1 )

    GMT+8, 2024-3-29 20:22