​全国自考（数据结构）模拟试卷6

一、1.单项选择题

0. 在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的  (  )

A．先序遍历
B．中序遍历
C．后序遍历
D．按层次遍历

1. 已知一个向量的第一个元素的存储地址是loO，每个元素的长度为2，则第6个元素的地址是  (  )

A．120
B．112
C．110
D．114

2. 在单链表中，删除p所指结点的直接后继的操作是  (  )

A．p—＞next=p—＞next—＞next;
B．p=p—＞next;p—＞next=p—＞next—＞next;
C．p—＞next=p—＞next;
D．p=p—＞next—＞next;

3. 深度为6(根的层次为1)的二叉树至多有(  )个结点。

A．31
B．32
C．63
D．64

4. 设二叉树有n个结点，则其深度为  (  )

A．n-1
B．n
C．
D．不确定

5. 在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的  (  )

A．先根遍历
B．中根遍历
C．后根遍历
D．按层次遍历

6. 一个栈的入栈序列为a1,a2,a3,a4,a5，则此栈不可能的输出序列是  (  )

A．a5,a4,a3,a2,a1
B．a4,a5,a3,a2,a1
C．a4,a3,a5,a1,a2
D．a1,a2,a3,a4,a5

7. 设rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为(  )

A．s=rear;
B．rear=rear—＞next; rear=rear—＞next; free(rear); free(s);
C．rear=rear—＞next—＞next;
D．s=rear—＞next—＞next; free(rear); rear—＞next—＞next=s—＞next; free(s);

8. 以下有关数据结构的叙述，正确的是    (  )

A．线性表的线性存储结构优于链式存储结构
B．二叉树的第i层上有2i-1个结点，深度为K的二叉树上有2k-1个结点
C．二维数组是其数据元素为线性表的线性表
D．栈的操作方式是先进先出

9. 已知一个单链表中有3000个结点，每个结点存放一个整数，(  )可用于解决这3000个整数的排序问题且不需要对算法作大的变动。

A．直接插入排序方法
B．简单选择排序方法
C．快速排序方法
D．堆排序方法

10. 二维数组M[i,j]的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5。M按行存储时元素M[3,5]的起始地址与M按列存储时元素(  )的起始地址相同。

A．M[2,4]
B．M[3,4]
C．M[3,5]
D．M[4,4]

11. 在一棵二叉树中，第k层上最多有(  )个结点。

A．2k
B．2k-1
C．2^k
D．2^k-1

12. 一棵二叉树如图所示，其中序遍历的序列为  (  )

A．ABDGCEFH
B．DGBAECHF
C．GDBEHFCA
D．ABCDEFGH

13. 设计一个判别表达式中左、右括号是否配对出现的算法，采用(  )数据结构最佳。

A．线性表的顺序存储结构
B．栈
C．队列
D．线性表的链式存储结构

14. 设有一顺序栈S，元素s₁，s₂，s₃，s₄，s₅，s₆依次进栈，如果6个元素出栈的顺序是s₂，s₃，s₄，s₅，s₆，s₁，则栈的容量至少应该是  (  )

A．2
B．3
C．5
D．6

二、2.填空题

0. 在直接插入和直接选择排序中，如果初始数据基本正序，则选用______，若初始数据基本反序，则选用______。

1. 设一个链栈的栈顶指针为ls，栈中结点两个字段分别为info和next，其中next是指示后继结点的指针，栈空的条件是______。如果栈不空，则退栈操作为p：=ls；______；dispose(p)。

2. 在分块查找法中，首先查找______，然后再查找相应的______。

3. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______。

4. 在一个按行优先顺序存储的二维数组(M×N)中，假设数组的基地址是P，并且数组的每一个元素所占的存储空间为d个字节，则a[_ij的地址计算公式为______。

5. 对角矩阵中，除了______的元素之外，其余的元素都是零。则对于一个k对角线矩阵(k为奇数)A是满足下面的条件的矩阵；如果______，则元素a[_ij=0。

6. ______中结点的最大度数允许大于2，而______中结点的最大度数不允许大于2。

7. 计算机软件系统中，有两种处理字符串长度的方法：一种是采用______，第二种是______。

8. 在单链表中，除了首元结点外，任一结点的存储位置是由______指示。

9. 大多数排序算法都有两个基本操作，它们是______和______。

三、3.解答题

0. 对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。

1. 假设有下面所示的稀疏矩阵，请写出其三元组表(按行优先的顺序)。

2. 假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

3. 已知一棵二叉树按照顺序结构存储，其存储结构如下：
  
  则请回答如下问题：
  (1)请画出此二叉树的树形结构。
  (2)请写出此二叉树的前序遍历、中序遍历和后序遍历序列。
  (3)此二叉树的高度是多少?
  (4)结点F的双亲、孩子，以及祖先分别是什么?
  (5)此树中，度数为1的结点共有几个?分别是哪几个?
  (6)结点C有左孩子吗?如果有左孩子，则C的左孩子的编号应该是什么?

四、4.算法阅读题

0. 以下为单链表按序号查找的运算，分析算法，请在______处填上正确的语句。
  pointer find_lklist(1klist head,int i)
  { p=head;j=0;
   while(______)
    { p=p—＞next;j++;}
     if(i==j)return(p);
     else return(NULL);
  }

1. 以下算法实现若开散列表HP中存在键值为K的结点，则将其删除。请分析程序，并在______上填充合适的语句。
  void delete_openhash(keytype K,openhash HP)
  { i=H(K);
   if(HP[i]==NULL)return;  /*空表则退出*/
   p=HV[i];
   if(p—＞key==K){______=p—＞next;free(p);return;)
                /*表首结点为待删除结点时的删除*/
  while(p—＞next!=NULL)   /*其他情况下的删除*/
   { q=p;p=p—＞next;
    if(p—＞key==K){______=p—＞next;delete(p);return;)
   }
  }

2. 以下运算实现在循环队上的出队列，请在______处用适当的语句予以填充。
  int OutCycQueue(CycqueueTp*sq,DataType*x)
    { if(sq—＞front==______){error("队空");return(0);)
     else{______;
       ______;
       return(1);
       }
    }

3. 以下为求单链表表长的运算，分析算法，请在______处填上正确的语句。
  int length_lklist(lklist head)  /*求表的长度。 */
  {______;
   j=0;
  while(p—＞next!=NULL)
  {______;
   j++;}
  return(j);
  }  /*回传表长*/

五、5.算法设计题

0. 从键盘上输入若干字符(每行长度不等)，输入后把它们存储到一磁盘文件中，再从该文件中读出这些数据，将其中小写字母转换成大写字母再进行屏幕输出。