贵州大学理学院数学系信息与计算科学专业
《数据结构》期末考试试题及答案
(2003-2004学年第2学期)
一、单项选择题
1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为(    )。
  (A)、正确性    (B). 可行性    (C). 健壮性    (D).  输入性
2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为(    )。
for(i=n-1i>=0i--)
  for(j=0j<ij++)  S
  (A)、n2    (B). O(nlgn)  (C). O(n)  (D).  O(n2)
3.折半查法适用于(    )。
(A)、有序顺序表  (B)、有序单链表
(C)、有序顺序表和有序单链表都可以  (D)、无限制
4.顺序存储结构的优势是(    )。
  (A)、利于插入操作 (B)、利于删除操作 
(C)、利于顺序访问 (D)、利于随机访问
5.深度为k的完全二叉树,其叶子结点必在第(    )层上。
    (A)、k-1  (B)、k  (C)、k-1k    (D)、1k
6.具有60个结点的二叉树,其叶子结点有12个,则度过1的结点数为(      )
(A)、11    (B)、13  (C)、48  (D)、37
7.图的Depth-First Search(DFS)遍历思想实际上是二叉树(    )遍历方法的推广。
  (A)、先序  (B)、中序  (C)、后序  (D)、层序
8.在下列链队列Q中,元素a出队的操作序列为(        )
        Q
  (A)、p=Q.front->next; p->next= Q.front->next;
  (B)、p=Q.front->next; Q.front->next=p->next;
  (C)、ar->next; p->next= Q.rear->next;
  (D)、p=Q->next; Q->next=p->next;
9. Huffman树的带权路径长度WPL等于(      )
(A)、除根结点之外的所有结点权值之和    (B)、所有结点权值之和
(C)、各叶子结点的带权路径长度之和      (D)、根结点的值
10.线索二叉链表是利用(      )域存储后继结点的地址。
  (A)、lchild    (B)、data  (C)、rchild  (D)、root
二、填空题
1.逻辑结构决定了算法的          ,而存储结构决定了算法的           
2.栈和队列都是一种      的线性表,栈的插入和删除只能在        进行。
3.线性表(a1,a2,…,an)的顺序存储结构中,设每个单元的长度为L,元素ai的存储地址LOC(ai)                     
4.已知一双向链表如下(指针域名为nextprior)
                      q
               
                      p
现将p所指的结点插入到xy结点之间,其操作步骤为:                   
                                                     
5.n个结点无向完全图的的边数为               
  n个结点的生成树的边数为                   
6.已知一有向无环图如下:
         
         
           
   
                 
任意写出二种拓扑排序序列:                                 
7.已知二叉树的中序遍历序列为BCA,后序遍历序列为CBA,则该二叉树的先序遍历序列为                ,层序遍历序列为               
三、应用题
1.设散列函数H(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。(6分)
(1) 构造HASH表。
(2) 分别求查成功和不成功时的平均查长度。
2.给定表(19,14,22,15,20,21,56,10.(8分)
(1)按元素在表中的次序,建立一棵二叉排序树
(2)(1)中所建立的二叉排序树进行中序遍历,写出遍历序列。
(3)画出对(2)中的遍历序列进行折半查过程的判定树。
3.已知二个稀疏矩阵A和B的压缩存储三元组表如下:
              A                      B
i
j
V
i
j
V
1
3
-5
2
5
2
2
4
6
3
3
7
2
5
2
4
1
3
4
2
-1
5
2
-9
5
2
9
5
5
8
写出A-B压缩存储的三元组表。(5分)
4.已知一维数组中的数据为(18,12,25,53,18, 试写出插入排序(升序)过程。并指出具有n个元素的插入排序的时间复杂度是多少?(5分)
5.已知一网络的邻接矩阵如下,求从顶点A开始的最小生成树。(8分,要有过程)
                A  B  C  D  E  F
(1)求从顶点A开始的最小生成树。
(2)分别画出以A为起点的DFS生成树和BFS生成树。
6.已知数据六个字母及在通信中出现频率如下表:数据结构与算法题库
A
B
C
D
E
F
0.15
0.15
0.1
0.1
0.2
0.3
把这些字母和频率作为叶子结点及权值,完成如下工作(7分,要有过程)。
(1)画出对应的Huffman树。
(2)计算带权路径长度WPL。
(3)A、B、C、D、E、F的Huffman编码。
7.已知有如下的有向网:
求顶点A到其它各顶点的最短路径(采用Dijkstra算法,要有过程)。(6分)
三、设计题(30分,每题10分,用C语言写出算法,做在答题纸上)
1.已知线性表(a1,a2,…,an)以顺序存储结构为存储结构,其类型定义如下:
            #define  LIST_INIT_SIZE  100  //顺序表初始分配容量
            typedef  struct  {
              Elemtype  *elem;        //顺序存储空间基址
              int  length;              //当前长度(存储元素个数)
            }SqList;
设计一个算法,删除其元素值为x的结点(假若x是唯一的)。并求出其算法的平均时间复杂度。其算法函数头部如下:
  Status ListDelete(Sqlist &L,Elemtype x)
  {
……
  }
2.设顺序栈如左图所示。
  其中结点定义如下:                            top
    typedef  struct {                             
Elemtype *base;  //栈底指针
Elemtype *top;  //栈顶指针
}Stack;
设计算法,将栈顶元素出栈并存入e中.            base
3.设二叉链树的类型定义如下:
          typedef  int  Elemtype;
          typedef struct  node{
              Elemtype  data;
              struct  node  *lchild, *rchild;
          }BinNode, *BinTree;
试写出求该二叉树叶子结点数的算法:
  Status CountLeaves(BinTree &root,int &n)
  {//n is the number of leaves
……
  }
答案:
选择题(每题1分)
1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C

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