数据结构模拟题.doc

数据结构模拟题 一、填空题（每空 2 分，共 28 分） 1．线性表的顺序储存是通过 位置间的关系 来反映元素之间的逻辑关系， 而链式储存结构是通过 指针的链接  反映元素之间的逻辑关系。 2．在一个长度为  n 的顺序表中，删除第  i 个元素 (c ≤i  ≤ n-1)  ，需移动  n-i  个元素。 3．假定一棵二叉树的结点数为  33，则它的最小高度为  6  ，最大高度为  33  。 4. 在一个单链表中，若  p 所指节点不是最后节点，在  p 之后插入  s 所指的节点，则执行  B  。 A. a-link=p;p-link=s;  B. s-link=p-link;p-link=s; C. a-link=p-link;p=s;  D. p-link=s; s-link=p; 5．已知一序列的关键码为 {6 ，45，15，5，30，100，45，75，8} 。用快速排序方法对此序列进行从小 到大的排序， 选择序列中间位置值 30 为分区标准， 第一趟排序的结果是 ；用 排序方法进行排序，取增量 d={3 ， 2， 1} 时，第一趟排序的结果是 。 6. 用一维数组存放的一棵完全二叉树： ABDCEFHGI，写出中序遍历该二叉树时访问节点的顺序：  shell GCTBEAFDH  。 对关键码依次为 {8 ，32， 46，49，52， 68， 70，75，88，90， 92，95，100} 的有序顺序表，采用二 分法检索，查找关键码为 88 的记录时，经过 4 次关键码比较后查找成功；当查找关键码为 55 的记录时，经过 4 次关键码比较，可以确认该记录不存在。 8. 线性表的链式储存结构主要有 点链表 、 双链表 、 循环链表 三种形式。 二、辨析题（每题 6 分，共 42 分） 1． 数据结构与抽象数据类型的关系是什么 ? 2． 对于表达式 (a+b)*(c+d)*(e+f) ，画出相应的二叉树表示；给出它的前缀表达式；给出它的后缀表 达式。 3． 设由关键码分别为 10， 20， 30 的三个结点，按照不同的输入顺序，画出所有可能的二叉排序树。 4． 算法和数据结构与问题求解的关系是什么？ 5． 试为下列各种情况选择合适的排序方法 (1)n=1000 ，且要求最坏情况下速度最快，可采用归并排序 (2)n=30 ，且要求既要快，又要排序稳定 (3)n=1000 ，要求既要快，又要最节省储存空间，可采用堆排序 6． 简单比较线性表的顺序和链接两种储存方式各有什么主要优缺点？ 7． 设有有向图为 G=(V,E) ，其中 V={v0,v1,v2,v3},E={v1,v0,v2,v1,v3,v2,v3,v1,v0,v3}, 请画出该有向图，并图示其邻接矩阵表示和邻接表表示。 三、算法填空题（每空 2 分，共 14 分） 1．阅读下面的算法， 填充空格， 使其成为完整的算法。 该算法的功能是从一个顺序存储在线性表的不 减序列中，删除值相等的多余元素。  （注：若序列  k1.k2  .,kn,  满足该序列为不减序列。 ） define MAX 30; struct SlistTable{ int *elem;  //  储存元素的数组 int size;  //  数组的大小 }; void deleteDuplicate(SlistTable list){ int i=1; int j=0; while( (1) ){ if(list.elem[i]!=list.elem[j]){ (2) (3) } i++; } (4) } 2．对以下函数填空，实现用直接选择排序方法对 n 个整数进行从小到大排序。 Void zjxzpx(int r[],int n){ int i,j,k,x; For (i=1;in;i++){ K=i; For(j= (5) ;j=n;j++) If(r[j]r[k]) (6) ; If( (7) ){ X=r[i];r[i]=r[k];r[k]=x; } } } 四、算法设计题（共 16 分） 1. 设二叉树结点表示的数据元素类型为 T，二叉树以链接表示。 一棵二叉树的最大枝长就是二叉树层 数；最小枝长就是离根结点距离最近的叶结点距离根路径上的边数。请从以下方面设计一个算法， 同时求出一棵二叉树的最大和最小枝长。 （1） (4 分 ) 请给出顺序表示法表示的二叉树结点 BinaryTreeNode 的定义。 2） (4 分 ) 请概要说明此算法思想； 3） (6 分 ) 编写算法； 4） (2 分 ) 请在算法关键的地方给出必要的注释。