《算法与数据结构》模拟试题3
一、填空题（每小题2分，共18分）
1、 数据的逻辑结构包括            ，          和            三种结构。
2、 算法分析的两个主要方面是              和              。
3、 在双向链表中，每个结点有两个指针域，一个指向            ，
另一个指向              。
4、 空串是                  ，其长度等于            。
5、 有一个10阶对称矩阵A，采用压缩存储方式，以行为主存储下三角形到一个一维数组中，若A[0][0]的地址是200（每个元素占2个基本存储单元），则A[9][5]的地址是                。
6、 在非空二叉树的中序遍历序列中，根结点的右边                              。
7、 采用邻接链表存储图，则图的深度优先搜索算法类似于二叉树的                  。
8、 在分块查方法中，首先查            ，然后再查相应的                。
9、 对于文件，按其记录的类型可将文件分为              文件、              文件。
二、单项选择题（请将答案写在题目后的括号中。每题2分，共数据结构与算法分析答案18分）
1、有如下递归函数fact(n)，其时间复杂度是（        ）。
Fact(int n)
{  if (n<=1)  return 1; 
  else  return(n*fact(n-1)) ;
}
（A）  O(n)      （B） O(n2)      （C） O(㏒2n)    （D） O(n㏒2n)
2、 设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则向S中压入一个元素P执行的操作是（        ）。
（A）  S[top++]=p；      （B）  S[++top]=p；
(C)  S[--top]=p；        （D）  S[top--]=p；
3、 稀疏矩阵一般的压缩存储方法有主要有（        ）两种。
（A）  二维数组和三维数组    （B）  三元组和散列
（C）  三元组和十字链表      （D）  散列和十字链表
4、 一般树的存储结构主要有（          ）。
（A）  双亲表示法，孩子表示法，链表表示法
（B）  双亲表示法，孩子表示法，孩子—兄弟表示法
（C）  双亲表示法，孩子—兄弟表示法，链表表示法
（D）  双亲表示法，孩子—兄弟表示法，链表表示法
5、 一棵有n(n≥0)个结点的满二叉树的叶子结点的数目是            ，非叶子结点的数目是            。（        ）
（A）  2[㏒2n]    2[㏒2n]            （B）  2[㏒2n]-1    2[㏒2n]   
（C）  2[㏒2n]-1    2[㏒2n]-1        （D）  2[㏒2n]    2[㏒2n]-1
6、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的            倍，
所有顶点的度之和等于所有顶点的入度之和的            倍。（        ）
（A） 1/2，1    （B）  1，2  （C） 2，1  （D）  1，4
7、设有一个长度为12的有序表，采用二分查方法对该表进行查时，在表内各元素等概率情况下查成功所需的平均比较次数为。（    ）
(A)  35/12        （B）  37/12    （C） 39/12      （D）  43/12
8、 设有一组记录的关键字是（37，28，56，80，60，14，25，50），用快速排序法以第一个记录为基准得到的一次划分结果是（        ）。
（A） 25，28，37，14，56，80，60，50    （B） 25，28，37，14，60，80，56，50
  （C） 25，28，14，37，60，80，56，50    （D） 25，28，14，37，60，56，80，50
9、 文件在外存上的上的组织方式称为文件的物理结构。基本的物理结构有：（      ）
(A)  顺序结构，链接结构，线性结构    (B) 线性结构，链接结构，索引结构
(C) 顺序结构，链接结构，线性结构      (D)  顺序结构，链接结构，索引结构
三、分析题（每题6分，共30分）
1、 设有一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，请画出这棵二叉树，然后画出其后序线索化树。
2、 对于下图中的网，写出该网的邻接链表；然后写出其广度优先搜索生成树（假设从顶点V1出发）；最后给出按Prime算法从顶点V5出发得到的最小生成树。
3、 将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除18之后的二叉排序树T1；最后再画出插入18之后的二叉排序树T2。
4、 线性表的关键字集合{71，25，8，29，42，69，95，33，17，56，47}，共有11个元素，已知散列函数为：H（k） = k MOD 11，采用链地址处理冲突，请给出对应的散列表结构，并计算该表成功查的平均查长度。
5、 已知序列{35，29，52，60，17，9，38，27，13，45}，请给出采用归并排序法对该序列做非递减排序时的每一趟结果。
四、算法填空（每空2分，共20分）
请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。
1、 循环队列Q的队首元素出队操作算法。
#define  Max_Queue_Size  100
ElemType  Delete_CirQueue(SqQueue  Q)
    {  ElemType  x ;
      if  (                    ) 
            printf(“The Circular Queue is Null!”) ;
else  {  x=Q.Queue_array[Q.front] ;
                                          ;
      }
    }
2、 二叉树中序遍历的非递归算法。
#define  Max_Node_Num  50
Void  InorderTraverse( BTNode  *T)
{  BTNode  *Stack[Max_Node_Num] ,*p=T ;
      int  top=0 , bool=1 ;
      if  (T==NULL)  printf(“The Binary Tree is Empty!\n”) ;
      else  { do  {  while (p!=NULL)
                      {  stack[++top]=p ; p=p->Lchild ;  }
                    if  (top==0)  bool=0 ;
                    else  {                            ;
                            visit( p->data ) ;                          ; }
                }  while (                    ) ;
          }
}
3、 折半查算法。
int  Bin_Search(SSTable  ST , KeyType  key)
{  int  Low=1，High=ST.length, Mid ;

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