北师大教育技术系《数据结构》复习题

一. 选择题
(1)采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为(  ).
A.  n     B.  (n+1)/2    C.  n/2      D.  (n-1)/2
(2)采用折半法查找长度为10的有序线性表时,在表内各元素等概率的情况,下,查找成功所需的平均比较次数为(    ).
– 37/10     B. 31/10      C.  29/10      D. 27/10
(3)采用分块查找时,若线性表中共有361个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块分(  )结点最好
   A. 10     B. 14      C. 17       D. 19
(4)在哈希函数H(key)=key % m 中, m应取大小恰当的(   )
   A. 素数     B. 奇数      C. 偶数       D. 任意数  


二、为数列 25,45,90,65,55,10,75,40,30 分别建立二叉排序树 和平衡二叉树.

三、
   A.给定数组int A[10]={25,15,80,20,70,45,10,60};给出它的极小堆.   B.给出从上堆中删除堆顶素后所得堆对应的数列.
   C.给定字符串  char * A=“previous”;  给出它的极大堆.
   D.给出从上堆中添加一个元素t后所得的堆.

四.用快速排序算法对如下数组排序,
  60   55   65   90   20   5    80  100
  a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]  
1.  第一轮支点(pivot) 选20,列出第一轮排序后的元素次序.
2.  列出第一轮排序后的高端子列,对这个子列再用快速排序算法排一论.
3. 快速排序的计算复杂性:
  A.平均情况____ B.最坏情况________  C.最好情况________
   (a) O(nlogn)  (b) O(n2)  (c) O(n)   (d) O(1)

五.用hash函数hashf(x)=x%11将整数值映射为hash表的素引.将数据1,23,19,30,14,33,12,22,7插入hash表中.
a)  用开放探测寻址法建立hash表.
b) 用独立链表地址法建立hash表.
c) 分别计算等概率情况下两种方法查找成功的平均查找次数.六.下面一段程序输出什么?
void main(void)
{ Stack S; Queue Q; Pqueue PQ; char ch;
  char  sentence[]=”StackQueue”;
for(int i=0;i<strlen(sentence);i++)  
     PQ.PQInsert(sentence);
while(!PQ.PQEmpty())
{ ch = PQ.PQDelete();
  while(!S.StackEmpty())
   { ch = S.pop(); cout<<ch;  }
  cout<<endl;
   while(!Q.Qempty())
    {  ch = Q.Qdelete();cout<<ch;  }
  cout<<endl;  }
if ( isupper(ch) S.Push(ch);
  else  Q.Qinsert(ch);   }

七.(1)用preorder遍历一棵Binary Search Tree得到序列 20 15 10 17 16 18 25 22 21 24 35给出这棵树,并给出postorder遍历.
(2) 说明函数F的作用
void InorderAssign(TreeNode<int>*t,Array<int>& A,int& i)
{
if(t!=NULL)
{
InoderAssign(t->Right(),A,i);
A[i++]=t->data;
InorderAssign(t->Left();A,i);
}
}
Void F(Array<int>& A)
{
BinSTree<int> tree;
for(int i=0;i<A.ListSize();i++)
   tree.Insert(A);
i=0;
InorderAssign(tree.GetRoot(),A,i);
}
八. 说明函数pat的功能
int pat(char str[],int i)
{ int m=strlen(str)/2;
  if(i>=m)return 1;
  else if (str !=str[m+i])return 0;
       else return pat(str,i+1); }
字符串A 取
  (a)“powwow”  (b) “sees”  (c) “123123”  
  (d) “123321”  
分别给出 函数pat(A,0)的值.九.下面各题中的函数F起什么作用:
A.  template <class T>
    int F(Cnode<T>& s)
    { Cnode<T> *p=s.NextNode();int l=0;
      while(p!=&s){ l++; p=p->NextNode();}
      return l;  }
  B. template <class T>
     T F(TreeNode<T>*t,SeqList<T>& L)
     { InorderIterater<T> titer(t); int n=0;
       for(titer.Reset();!titer.EndOfList();
                               titer.Next())
         { L.Insert(titer.Data()); n++;}
        return L.GetDat(n/2);  }
C. template <class T>
  SeqList<T> F(Graph<T> &G)
  {SeqList<T> L; VerTexIterater<T> viter(G);
   SeqListIterater<T> liter(L);
   for(viter.Reset();!viter.EndOfList();
                             viter.Next())
    { cout<<viter.Data()<<“:          ”;
      L= G.DepthFirstSearch(viter.Data());
      Liter.SetList(L);
      PrintList(L);
      cout<<end;   
     }  
   }

十.画出以下邻接矩阵所对应的图G,假设顶点字符是A,B,C……
     
  0 1 1 0 0 0 0 0     A              C  
  0 0 0 1 0 0 0 0         
  0 0 0 0 0 0 0 0        
  1 0 0 0 0 0 0 0  B       D     E         F
  0 0 1 0 0 0 0 0               
  0 0 1 0 1 0 0 0                 
  0 0 0 1 0 0 0 0     G               H
  0 0 0 0 0 1 1 0
A.G的强连通块是________.
(a){A,B,C,D}{E,F,G.H}
(b){A,B,C,D} {E} {F} {G,H}
(c){A,B,D} {c} {E} {F} {G} {H}  
(d) {A,B,D} {C,E,F}  {G} {H}
B.给出G的可及矩阵.
C.分别给出从A点出发的按深度优先和广度优先搜索的遍列次序.

十一．深度为5的满二叉树有多少个结点？13个结点的满二叉树深度是多少？有几个叶片？一棵二叉树有7片叶子，有多少个2度结点？

十二。一个栈依次输入x,y,z,给出全部可能的输出序列，共有几种不同的序列？一个栈依次输入a1,a2,•••••,an,共有几种不同的序列输出序列？

十三． 用希尔排序法对序列485，27，504，838，192，796，248，583，467，154，539，629，697，805，736，94，638，426，154，489，512，677，761，724，73排序，取d1=15,d2=7, d3=3,d4=1 给出每一轮排序的结果。

十四．用基数排序的方法对上题中的数列排序，给出每一轮排序的结果。
十五. 求n个结点的k叉树的最小深度,n个结点的AVL树的最小深度,n个结点的B-树的最小深度。    6个结点的不同的树有多少种？

十六. 证明n个关键字的B-树的失败结点有n+1个。

来源：Easy考研网