数据结构考试样题(天津科技大学)

一、填空题（每小题2分，共２０分）

1.数据的逻辑结构包括集合结构、线性结构、                     。

   2.对算法从时间和空间两方面进行度量，分别称为                  分析。

   3.不带有头结点的单链表head为空的条件是                  。

   4.对于栈只能在          插入和删除元素。

   5.深度为k的二叉树最多有            个结点。

6.空格串是                           。

   7.Hash技术关键是                          两个方面。

8.快速排序的平均时间复杂度为                 。

   9. HEAD (TAIL (((a, (b, c))))=                   。

   10.已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是                      。

二、单项选择题（每小题2分，共２０分）

   １．以下哪一个不是队列的基本运算（     ）？

    （A）从队尾插入一个新元素

    （B）从队列中删除第i个元素

    （C）判断一个队列是否为空

    （D）读取队头元素的值

2．若进栈序列为１,２,３,４,假定进栈和出栈可以穿插进行，则可能的出栈序列是（    ）。

   （A）２，４，１，３    （B）３，１，４，２

   （C）３，４，１，２    （D）１，２，３，４

   3．有个结点的完全二叉树的深度为（    ）（根的层次为1）。 

      （A）8  （B）7  （C）6  （D）5

   4．串是一种特殊的线性表，其特殊性体现在（   ）。

（A）可以顺序存储    （B）数据元素是一个字符

（C）可以链接存储    （D）数据元素可以是多个字符

   5．链表不具有的优点是（    ）。

   （A）可随机访问任一元素   （B）插入删除不需要移动元素

   （C）不必事先估计存储空间 （D）所需空间与线性表长度成正比

   6．对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标依次为(     )。

(A) 1，2，3   (B) 9，5，2，3     (C) 9，5，3    (D) 9，4，2，3

   7．对矩阵压缩存储是为了(    )。

     (A) 方便运算 (B) 节省存储空间 (C) 方便存储 (D) 提高运算速度

8．快速排序属于（     ）。

    (A) 插入排序  (B)交换排序   (C)归并排序  (D)选择排序

    9．设矩阵A{1..n,1..n]是一个对称矩阵，为了节省存储，只将其下三角部分按行序存放在一维数组B[1..n(n-1)/2]中，对下三角部分中任一元素aij(i>=j),在一维数组B的下标位置k的值(    )。

 (A) i(i-1)/2+j-1  (B) i(i-1)/2+j   (C) i(i+1)/2+j-1  (D) i(i+1)/2+j 

10．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（    ）二叉树。

 (A) 空或只有一个结点   (B) 高度等于其结点数

 (C) 任一结点无左孩子   (D) 任一结点无右孩子

三、简答题（共40分）

1. 对下列数据表，写出采用二路归并算法排序的每一趟的结果。（7分）

(50,12,20,31,44,66,61,80,30,75) 

2. 已知某二叉树按后序遍历序列为CEDBHJIGFA，按中序遍历序列为CBEDAHGIJF,试画出该二叉树形状（要求写出中间过程）， 并写出它的先序遍历序列。（9分）

3．已知一组元素为(37,70,29,46,25,78,62,12)，画出按元素排列输入生成的一棵二叉排序树，并求其在等概率情况下查找成功的平均查找长度（要求写出每插入一个元素时二叉排序树形状）。（8分）

4.设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,试为这六个字母设计huffman编码并画出对应huffman树。（8分）

   5．画出下列无向图的邻接表存储结构，并由邻接表写出由E出发的广度优先搜索序列和深度优先搜索序列。（8分）

             A

             |

         B---C---D

             E

四、设计或分析题(共20分)

   １．设单链表具有头结点，且表中元素各不相同，试给出在单链表中删除值为"x"的结点的算法。（10分）

2．设一棵二叉树以二叉链表存储，试设计算法求此二叉树的深度。（10分）

Status Delete_Between(Linklist &L,elemtype x)//删除元素

{

  p=L;

  while(p->next && p->next->data!=x) p=p->next;

  if(p->next)    /

  {

    q=p->next;

     p-.next =q->next;

  }

}//Delete_Between 

int Get_Depth(Bitree T)//求子树深度的递归算法

{

  if(!T) return 0;

  else

  {

    m=Get_Depth(T->lchild);

    n=Get_Depth(T->rchild);

    return (m>n?m:n)+1;

  }

}//Get_Depth