1．线性链表不具有的特点是（  ).
A．随机访问                              B．不必事先估计所需存储空间大小
C．插入与删除时不必移动元素              D．所需空间与线性表长度成正比
2．设一个栈的输入序列为1，2，3，4，则输出序列不可能是(  ).
A．1， 2， 3， 4        B．4， 3， 2， 1        C．1， 3， 2, 4      D．4，1,2，3
3．下列排序算法中,(  )排序在每趟结束后不一定能选出一个元素放到其排好序的最终
位置上.  A．归并      B．冒泡        C．选择        D．堆
4．下列序列中，（  )是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。
A．［da, ax， eb, de, bb］ ff [ha, gc］          B．［cd， eb, ax， da] ff [ha， gc, bb］
C．［gc， ax, eb, cd, bb] ff ［da， ha]          D．［ax, bb， cd， da] ff [eb， gc， ha］
5．设有一个10阶的对称矩阵A［10]［10］，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B［ ］中，A[0][0］存入B[0］中，则A［8]［5]在B[ ］中（  ）位置。
A．32                B．33            C．41                D．65
6。 下面哪一种图的邻接矩阵肯定是对称矩阵（  )。
A．有向图          B．无向图      C．AOV网        D．AOE网
7．具有2008个结点的二叉树，其深度至少为(  ）。
A．9        B．10            C．11          D．12
8. 关键路径是边表示活动的网（AOE网）中的(  ).
A．从源点到汇点的最长路径      　B．从源点到汇点的最短路径
C．最长的回路            D．最短的回路
9． 一个广义表为（a, (a,b）， d, e, (（i,j) ,k)），则该广义表的长度为(  ).
  A．不确定        B．8            C．5          D．6
10．设循环队列中数组的下标范围是0～n –1，其头尾指针分别为f和r，则其元素个数为(  ）。
A．r – f      B．r – f + 1    C．( r – f ) mod n + 1    D．（ r – f + n ） mod n
1．算法具有的五个重要特性是:有穷性，确定性，_______，输入和输出。
2．一组记录的关键字为（45，80,55,40，42,85），则利用堆排序的方法建立的初始堆为____________。
3．对如下无向图G，从结点V1出发，写出一个按深度优先遍历图的结点序列:__________________。
                                           
                                                         
                                                             
                      第3题图                              第4题图
4．写出右上图中的一个拓扑有序序列____________________。
5．对于顺序存储的线性表，访问结点和删除结点的时间复杂度分别为_____________。
6．平衡二叉树上所有结点的平衡因子只可能是________________。
7．假定对线性表R［1..60]进行分块查，共分为10块,每块长度等于6。若假定查索引表和块均用顺序查的方法，则查每一个元素的平均查长度为___________。
8．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1,则编号为37的双亲结点编号为_______.
9．设有一个字符串 s='science'，其非空子串的数目是________。
10．有n个顶点的强连通有向图G至少有________条弧。
1．一棵二叉树的先序序列和中序序列分别如下，
        先序序列: ABCDEFGHIJ
        中序序列: CBDEAGIHJF
（1）画出该二叉树。（3分）
（2）写出其后序序列.(3分）
2．给出用Kruskal算法构造下列带权图的最小生成树的过程。
            3     
                     
      1      5      4
  3
                   
      4      1      6
            2
3. 已知一个长度为12的表（6，8，4,12，2,10，7，3,9，1，11，5)。
（1）将表中的元素依次插入到一个初始为空的二叉排序树中，画出该二叉排序树并求其在等概率下的平均查长度。（3分)
（2）若先对表中的记录排序，构成有序表后再对其进行折半查，画出判定树并求其在等概率下的平均查长度。（3分）
4．已知哈希表地址空间为0。。10，哈希函数为H（key) = key MOD 11，采用链地址法处理冲突，将下面数据序列依次插入该哈希表中，并求出在等概率下查成功时的平均查长度。
12，24，1，34,38，44，27,22。
5．假定用于通信的电文仅由8个字母a，b，c，d，e，d,f,g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。要求：
(1）以这些频率作为叶子结点的权值构造Huffman树。(2分)
（2)试为这8个字母设计不等长Huffman编码。（2分）
A        b          c        d        e          f        g          h
 
 
 
 
 
 
 
 
哈夫曼编码树的带权路径长度（3）计算出电文总长度。(2分） 
1。 有两个不带头结点的单循环链表，链表头指针分别为a和b。编写一个过程将链表b链到链表a之后,链接后的链表仍保持循环链表形式。
2. 试编写一个计算二叉树的叶子结点数的算法。要求二叉树采用链式存储结构。
3。 请写出监视哨设在高下标端的插入排序算法。
06  2
1. 具有n(n〉0)个结点的完全二叉树的深度为                            （      )
A. ⎡log2n⎤                  B.⎣ log2n⎦ 
C. ⎣ log2n ⎦+1            D. ⎡log2n+1⎤
2. 一个栈的进栈序列是a，b，c，d，e,则栈的不可能的输出序列是        （        ）
A.abcde                    B.edcba
C。decba                    D。dceab
3. 数据在计算机存储器内表示时,物理地址与逻辑地址相同且连续，称之为  （        ）
A.存储结构                B. 逻辑结构     
C.顺序存储结构            D. 链式存储结构
4。 对二叉排序树的左子树中所有结点与右子树中所有结点的关键字大小关系是 （      ）
A.小于                    B。大于 
    C.等于                    D。不小于
5。 按照二叉树的定义，具有3个节点的二叉树______种                    （        ）
A.2                  B.3  C.4                  D。 5
6。 广义表(（a））的表尾是                                                (        ）
A．a                  B。 （a)  C．（）                D. （(a）)
7．设有两个串p和q，求在q在p中首次出现的位置的运算称为            （        ）
A。模式匹配    B.连接    C。求子串                  D. 求串长
8。 引入二叉线索树的目的是                                          （        ）
A．加快查结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的到双亲          D．使二叉树的遍历结果唯一
9．在有n个叶子结点的哈夫曼树中，其结点总数为                         
A。不确定              B。2n-1    C.2n                  D.2n+1
10．与单链表相比，双向链表的优点之一是                                 
A．插入、删除更简单              B.可以进行随机访问
C．可以省略表头指针或表尾指针    D。访问前后相邻结点更方便
1．Prim算法适合求__________的网的最小生成树，而Kruskal算法适用于求___________的网的最小生成树。  2.循环单链表L为空的条件是________________.  3.在对队列中，新
插入的元素只能插入到___________。  4．平衡二叉树上所有结点的平衡因子只可能是________________。5．一个有序表{1,3，9，12，32，41，45，62，75，77,82,95，99},当采用折半查法查关键字为82的元素时，_______________次比较后查成功。

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