无意间的发现的。当年我们考试靠的就是这个。

数据结构试卷（一）

二、填空题（每空1分，共26分）

1.         通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.         一个算法的时间复杂度为(n³+n²log₂n+14n)/n²，其数量级表示为________。

3.         假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_­­­­_________个，树的深度为___________，树的度为_________。

4.         后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。

5.         若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。

6.         对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。

7.         AOV网是一种___________________的图。

8.         在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

9.         假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。

10.     向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。

11.     在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。

12.     在快速排序、堆排序、归并排序中，_________排序是稳定的。

三、计算题（每题 6 分，共24分）

1.         在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。

                   A    0     1    2     3    4     5    6     7

2.   请画出下图的邻接矩阵和邻接表。

 

 

          

 

 

 

 

3.   已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};

        E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

   用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

4.          

四、阅读算法（每题7分，共14分）

1.     LinkList mynote(LinkList L)

       {//L是不带头结点的单链表的头指针

             if(L&&L->next){

                  q=L；L=L－>next；p=L；

        S1：       while(p－>next) p=p－>next；

        S2：       p－>next=q；q－>next=NULL；

              }

              return  L；

            }

    请回答下列问题：

   （1）说明语句S1的功能；

   （2）说明语句组S2的功能；

       （3）设链表表示的线性表为（a₁,a₂, …,a_n）,写出算法执行后的返回值所表示的线性表。

2.     void ABC(BTNode * BT)

{

        if  BT {

          ABC (BT->left);

          ABC (BT->right);

          cout<<BT->data<<' ';

          }

        }

        该算法的功能是：

五、算法填空（共8分）

二叉搜索树的查找——递归算法:

bool Find(BTreeNode* BST,ElemType& item)

{

  if (BST==NULL)

     return false; //查找失败

  else {

        if (item==BST->data){

               item=BST->data;//查找成功

               return  ­­­­­­­­­___________;}

       else if(itemdata)

               return  Find(______________,item);

       else  return Find(_______________,item);

         }//if

}

六、编写算法（共8分）

统计出单链表HL中结点的值等于给定值X的结点数。

     int CountX(LNode* HL,ElemType x)

数据结构试卷（二）

 

 

二、填空题(24分)

1.   为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。

2.   下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。

typedef struct {int s[100]; int top;} sqstack;

void push(sqstack &stack,int x)

{

if (stack.top==m-1) printf(“overflow”);

else {____________________;_________________;}

}

3.   中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。

4.   快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。

5.   设某棵二叉树中度数为0的结点数为N₀，度数为1的结点数为N₁，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。

6.   设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。

7.   设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为___________________________。

8． 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是

           ，BFS遍历的输出序列是           

 

 

 

 

 

 

 

 

三、应用题(36分)

1．设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。

2．设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。

3．设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。

 

 

 

 

 

 

 

 

 

 

4．设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。

 

四、算法设计题(16分)

1．  设有一组初始记录关键字序列（K₁，K₂，…，K_n），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K_i，右半部分的每个关键字均大于等于K_i。

数据结构试卷（三）

 

 

二、填空殖(每空1分 共20分)

1.   数据的物理结构主要包括_____________和______________两种情况。

2.   设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。

3.   设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。

4.   设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。

5.   设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。

6.   设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。

7.   __________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。

8.   设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。

9.   不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。

10.  设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。

11.     设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为___________________________。

12.  设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。

13.  下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j;  j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}

  if (_______________________ ) return(j); else return(-1);

}

14.  下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。

typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;

bitree  *bstsearch(bitree *t, int  k)

{    

if (t==0 ) return(0);else  while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;

}

 

三、计算题(每题10分，共30分)

1.

2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：

（1）计算出每一个元素的散列地址并在下图中填写出散列表：

 `             0         1         2         3         4         5         6

（2）求出在查找每一个元素概率相等情况下的平均查找长度。

3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。

四、算法设计题(每题15分，共30分)

1．设计在单链表中删除值相同的多余结点的算法。

 

数据结构试卷（四）

 

二、填空题(每空1分共 20分)

1．  设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。

2．  设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。

3．  根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。

4．  深度为k的完全二叉树中最少有____________个结点。

5．  设初始记录关键字序列为(K₁，K₂，…，K_n)，则用筛选法思想建堆必须从第______个元素开始进行筛选。

6．  设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。

7．  设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。

8．    设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。

9．    设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为______________________________。

10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。

11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。

12．设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素的个数（填等于，大于或小于）。

13．设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。

14．设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。

typedef struct node {int key; struct node *next;} lklist;

void createlkhash(lklist *hashtable[ ])

{

int i,k;  lklist *s;

for(i=0;i

for(i=0;i

{

s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];

k=a[i] % p; s->next=hashtable[k];_______________________;

}

}

 

三、计算题(每题10分，共30分)

 

3、设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key ² +2）MOD 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。

 

 

数据结构试卷（五）

 

二、填空题(共20分)

1.   设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。

2.   在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。

3.   设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。

4.   栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。

5.   设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。

6.   设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。

7.   设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。

8.   设一组初始记录关键字序列(k₁，k₂，……，k_n)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。

9.   下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。

void bubble(int  r[n])

{

for(i=1;i<=n-1; i++)

{

for(exchange=0,j=0; j<_____________;j++)

if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}

if (exchange==0) return；

}

}

10.  下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。

struct record{int key; int others;};

int bisearch(struct record r[ ], int k)

{

  int low=0,mid,high=n-1;

  while(low<=high)

{

    ________________________________;

    if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1;

  }

  return(0);

}

三、应用题(32分)

1.   设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。

2.   设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。

 

3.   设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

 

四、算法设计题(28分)

1．设计两个有序单链表的合并排序算法。

 

 

 

数据结构试卷（一）参考答案

 

二、填空题（每空1分，共26分）

1.  正确性   易读性   强壮性   高效率

2.  O(n)

3.  9    3    3

4.  -1      3 4 X * + 2 Y * 3 / -

5.  2n   n-1     n+1

6.  e    2e

7.  有向无回路

8.  n(n-1)/2     n(n-1)

9.  （12，40）    （  ）   （74）   （23,55，63）

10. 增加1

11. O(log₂n)   O(nlog₂n)

12. 归并

三、计算题（每题6分，共24分）

1.     线性表为：（78，50，40，60，34，90）

2.  邻接矩阵：

      邻接表如图11所示：

图11

3.     用克鲁斯卡尔算法得到的最小生成树为： 

     (1,2)3,  (4,6)4,  (1,3)5,  (1,4)8,  (2,5)10,  (4,7)20

 

四、读算法（每题7分，共14分）

1.     （1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点

   （3）返回的线性表为（a₂,a₃,…,a_n,a₁）

2.     递归地后序遍历链式存储的二叉树。

五、法填空（每空2分，共8 分）

true     BST->left        BST->right

六、编写算法（8分）

int CountX(LNode* HL,ElemType x)

   {  int i=0; LNode* p=HL;//i为计数器

      while(p!=NULL)

        { if (P->data==x) i++;

          p=p->next;

         }//while, 出循环时i中的值即为x结点个数

       return i;

   }//CountX

 

 

 

数据结构试卷（二）参考答案

 

 

二、填空题

1.   构造一个好的HASH函数，确定解决冲突的方法

2.   stack.top++，stack.s[stack.top]=x

3.   有序

4.   O(n²)，O(nlog₂n)

5.   N₀-1，2N₀+N₁

6.   d/2

7.   (31，38，54，56，75，80，55，63)

8.   (1，3，4，5，2)，(1，3，2，4，5)

 

三、应用题

1.   (22，40，45，48，80，78)，(40，45，48，80，22，78)

2.   2,ASL=91*1+2*2+3*4+4*2)=25/9

3.        E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}

4.        略

 

四、算法设计题

1.   设有一组初始记录关键字序列（K₁，K₂，…，K_n），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K_i，右半部分的每个关键字均大于等于K_i。

void quickpass(int r[], int s, int t)

{

  int i=s, j=t, x=r[s];

  while(i

while (ix) j=j-1; if (i

    while (i

  }

  r[i]=x;

}

 

 

 

 

数据结构试卷（三）参考答案

 

 

二、填空题

1.   顺序存储结构、链式存储结构

2.   9，501

3.   5

4.   出度，入度

5.   0

6.   e=d

7.   中序

8.   7

9.   O(1)

10.  i/2，2i+1

11.  (5，16，71，23，72，94，73)

12.  (1，4，3，2)

13.  j+1，hashtable[j].key==k

14.  return(t)，t=t->rchild

第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log₂n。

 

三、计算题

 

 

1、H(36)=36 mod 7=1;                  H_１(22)=(1+1) mod 7=2; ….冲突

H(15)=15 mod 7=1;….冲突           H₂(22)=(2+1) mod 7=3; 

H_１(15)=(1+1) mod 7=2;

H(40)=40 mod 7=5;

H(63)=63 mod 7=0;

H(22)=22 mod 7=1; ….冲突

（1）         0      1     2     3     4     5     6

63

36

15

22

40

（2）ASL=

2、(8,9,4,3,6,1),10,(12,18,18)

   (1,6,4,3),8,(9),10,12,(18,18)

   1,(3,4,6),8,9,10,12,18,(18)

   1,3,(4,6),8,9,10,12,18,18

   1,3, 4,6,8,9,10,12,18,18

 

四、算法设计题

1.   设计在单链表中删除值相同的多余结点的算法。

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist;

void delredundant(lklist *&head)

{

   lklist *p,*q,*s;

   for(p=head;p!=0;p=p->next)

   {

     for(q=p->next,s=q;q!=0; )

     if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}

     else {s=q,q=q->next;}

   }

}

 

 

 

数据结构试卷（四）参考答案

 

 

二、填空题

1.   O(n²)，O(nlog₂n)

2.        p>llink->rlink=p->rlink; p->rlink->llink=p->rlink

3.   3

4.   2^k-1

5.   n/2

6.   50，51

7.        m-1，(R-F+M)%M

8.   n+1-i，n-i

9.   (19，18，16，20，30，22)

10.  (16，18，19，20，32，22)

11.  A[i][j]=1

12.  等于

13.  BDCA

14.  hashtable[i]=0，hashtable[k]=s

 

三、计算题

1．

2．

(1) ABCDEF;   BDEFCA；(2) ABCDEFGHIJK;  BDEFCAIJKHG林转换为相应的二叉树；

3．H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6

 

 

 

数据结构试卷（五）参考答案

 

 

二、填空题

1.         top1+1=top2

2.         可以随机访问到任一个顶点的简单链表

3.         i(i+1)/2+j-1

4.         FILO，FIFO

5.         ABDECF，DBEAFC，DEBFCA

6.         8，64

7.         出度，入度

8.         k_i<=k_2i && k_i<=k_2i+1

9.   n-i，r[j+1]=r[j]

10.  mid=(low+high)/2，r[mid].key>k

 

三、应用题

1.         DEBCA

2.         ASL=(1*1+2*2+3*4)/7=17/7

3.         ASL1=7/6，ASL2=4/3

四、算法设计题

 

1.   设计两个有序单链表的合并排序算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc)

{

   lklist *s=hc=0;

   while(ha!=0 && hb!=0)

     if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;}

     else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;}

   if(ha==0) s->next=hb; else s->next=ha;

}