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

来源：Easy考研网
一. 选择题
(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 PQ.PQInsert(sentence[i]);
while(!PQ.PQEmpty())
{ ch = PQ.PQDelete();
while(!S.StackEmpty())
{ ch = S.pop(); cout< cout< while(!Q.Qempty())
{ ch = Q.Qdelete();cout< cout< 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*t,Array& A,int& i)
{
if(t!=NULL)
{
InoderAssign(t->Right(),A,i);
A[i++]=t->data;
InorderAssign(t->Left();A,i);
}
}
Void F(Array& A)
{
BinSTree tree;
for(int i=0;i tree.Insert(A[i]);
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[i] !=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
int F(Cnode& s)
{ Cnode *p=s.NextNode();int l=0;
while(p!=&s){ l++; p=p->NextNode();}
return l; }
B. template
T F(TreeNode*t,SeqList& L)
{ InorderIterater titer(t); int n=0;
for(titer.Reset();!titer.EndOfList();
titer.Next())
{ L.Insert(titer.Data()); n++;}
return L.GetDat(n/2); }
C. template
SeqList F(Graph &G)
{SeqList L; VerTexIterater viter(G);
SeqListIterater liter(L);
for(viter.Reset();!viter.EndOfList();
viter.Next())
{ cout< L= G.DepthFirstSearch(viter.Data());
Liter.SetList(L);
PrintList(L);
cout< }
}

十.画出以下邻接矩阵所对应的图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个。


附录：完整word稿下载