长沙理工大学数据结构模拟试卷2
一、填空题（每空1分，共10分）
1．顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的，链接存储结构中的数据元素之间的逻辑关系是由（    ）表示的。
2．非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（    ）。
3．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（    ）个非零元素。
4．（    ）可作为实现递归函数调用的一种数据结构。
5．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（      ）。
6．设S="I_ am_ a_ teacther"，其长度为（     ）。
7．稀疏矩阵一般压缩存储方法有两种，分别是（      ）和（      ）。
8．分块有序是指将文件划分为若干块，（      ）无序，（      ）有序。
二、判断题（你认为正确的请打对，错误的打错。每题2分，共10分）
1．线性表的顺序存储结构优于链接存储结构。
2．B—树是一种动态索引结构，它既适用于随机查，也适用于顺序查。
3．在线索二叉树中，任一结点均有指向其前趋和后继的线索。
4．用一维数组存储二叉树时，总是以前序遍历存储结点。
5．在索引顺序表上采用分块查，在等概率情况下，其平均查长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。
三、单选题（请把你认为正确的答案填入括号内，每小题1分，共10分）
1．假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（    ）。
A 树          B 图          C 线性表          D 集合
2．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（    ）结构。
A 栈            B队列        C 数组        D线性表
3．若某线性表经常的操作是取第i 个元素和第i个元素的前趋，则采用（    ）存储方法最节省时间。
A 顺序表      B 单链表      C 双链表      D 单循环链表
4．广义表(a, b, (c, (d)))的表尾是（    ）。
A (d)          B (c,(d))        C b        D (b,(c,(d)))
5．堆的形状是一棵（    ）。
A二叉排序树      B满二叉树      C完全二叉树      D 判定树
6．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（    ）。
A 6      B 4      C 3      D 2
7．G是一个非连通无向图，共有28条边，则该图至少有（    ）个顶点。
A 6          B 7        C 8          D 9
8．设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（    ）方法最好。
A快速排序          B堆排序        C希尔排序        D 归并排序 
9．设有10000个记录，通过分块划分为若干子表并建立索引，那么为了提高查效率，每一个子表的大小应设计为(        )。
A 100          B 200      C10      D 5
10．设有两个串p和q，求q在p中首次出现的位置的运算称作（    ）。
A 连接        B 模式匹配          C 求子串        D 求串长
四、简单应用题（47分）
1 已知一个非空二叉树，中序遍历序列为CGBAHEDJFI；后序遍历序列为GBCHEJIFDA，试将这棵二叉树构造出来。若已知前序和后序遍历结果，能否构造出这棵二叉树，举例说明。（9分）
2．二维数组M中每个元素的长度是3个字节，行下标从0到7，列下标从0到9，从首地址d开始存储。若按行优先方式存储，元素M[7][5]的起始地址为多少，若按列优先方式存储，元素M[7][5]的起始地址为多少。（5分）
3．如右图所示：（1）从顶点A出发，画出深度优先生成树；
（2）从顶点E出发，画出广度优先生成树；
（3）根据Kruskal算法，求出它的最小生成树。（12分）


第3题图
4．如右图是一棵正在进行插入运算的平衡二叉树，关键码70的插入使它失去了平衡，按照平衡二叉树的插入方法，需要对它的结构进行调整以恢复平衡。请画出调整后的平衡二叉树。（5分）


第4题图
5．写出下列程序段的时间复杂度。（3分）
  (1)count=0; x=1;
  　while (x<N)
  　{  x*=2;
       count++;
  　}
(2)  i=1; k=0;n=100;      　
  　while (i<N-1)&NBSP;&NBSP;&NBSP;   　
  ｛
    k=k+10*i;
    i++;
  　｝


第5题图
6．设记录的关键码集合为K={15,25,26,4,5,20,3,12,2},
（1）设散列函数为H(k)= k mod 15,散列表表长为16，采用线性探测法处理冲突，试构造闭散列表；
（2）写出对K进行直接插入排序的每趟排序结果。（13分）
五、阅读程序（8分）
下面伪代码是一个广度优先遍历算法，请给出该算法在下图上执行BFS（G，v1）的结果，指出其中的错误产生原因，如何修改？
void BFS(ALGraph*G , int k) {           /*G是图的邻接表，k是顶点序号*/
InitQueue(&Q);    /*初始化队列Q*/
EnQueue(&Q , k);      /*k入队*/
while (!QueueEmpty(&Q)){
      i=DeQueue(&Q);    /*队头元素出队*/
      visited[i]=1;    /*设置访问标记*/
      访问顶点vi;
      for (p=G->adjlist[i].firstedge[i];p;p=p->next) /*遍历顶点vi的相邻顶点vj（设p->adjvex=j）*/
        if (!visited[p->adjvex])
            EnQueue(&Q , p->adjvex);  /*顶点vj的序号入队*/
  }
}
六、已知非空单链表第一个结点的指针为head，写一个算法，出链表中的数据域值最大的那个结点，并将其链接到链表的最前面。8（分）
七、以二叉链表为存储结构，求二叉树的深度。（7分）
答案;
一、填空题（每空1分，共10分）
1.指针  2． p->next=head  3．2(n-1)  4．栈    5．53  6．15  7．三元组顺序表，十字链表  8．块内，块间
二、判断题（你认为正确的，请在前面的括号内打对，错误的打错。每题2分，共10分）
1．错。  2．对。  3．错。  4．错。  5．对。
三、单选题（请把你认为正确的答案填入括号内，每小题1分，共10分）
1．B    2．B    3．A    4．D    5．C  6．C  7．D    8． B   9． A    10．B
四、简单应用题（47分）
1
不能。例如：前序：ABC，后序BCA，则可以构造出如下二叉树。
长沙理工大学二手货QQ交易146 808 417  若已满请加分25342665
2  d+225;d+141
3
4
5. Ｏ(log2n)        O(1)
6
五 结果为v1,v2,v3,v4,v5,v6,v6,v6,v6
错误：当v2,v3,v4,v5出队时均执行了v6入队操作，导致v6的重复入队和出队。
修改：入队时做标记，使已经标记的顶点不重复入队。
六  void linkmax(node *head)
  {p=head->next;
  　while (p)
    { if (head->datadata) 
    　{head->data<-->p->data;  p=p->next;}
    　else p=p->next}}
七 int Depth(BiNode *root)
第一范式正则化不能产生稀疏解　{
  if (!root) return 0;
  else {
  　hl= Depth(root->lchild);
  　hr= Depth(root ->rchild);
  　return max(hl, hr)+1;
  }
　}

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