哈尔滨工程大学-考研数据结构真题-12_

哈尔滨工程大学-考研数据结构真题-12_

哈尔滨工程大学试卷考试科目: 数据结构A 卷题号一二三四五总分分数评卷人一、单项选择题（每空1分，共15分）1、以下数据结构中，从逻辑结构看，（）和其他数据结构不同。

A．树B．字符串C．队列D．栈2、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。

A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 3、有六个元素A，B，C，D，E，F的顺序进栈，（）不是合法的出栈序列。

A．DEFCBA B．EDCBFA C．EFDBCA D．EDCFBA 4、字符串“ABCDEF”的子串有（）个。

A．19 B．20 C．21 D．22 5、顺序表中插入一个元素，需要平均移动的元素个数为（）。

A．(n-1)/2 B．n/2 C．(n+1)/2 D．n-1 6、非空的单循环链表head 的尾结点（由P所指向）满足（）。

A．p-next ==NULL B．p==NULL C．p-next==head D．p==head 7、若A是中序线索二叉树中的一个结点，且A不为根，则A的前驱为( )。

A．A的右子树中最右的结点B．A的左子树中最左的结点C．A 的右子树中最左的结点D．A的左子树中最右的结点8、如某二叉树有30个叶子结点，有20个结点仅有一个孩子，则该二叉树中有两个孩子的结点数为（）。

A．29 B．30 C．31 D．19 9、二维数组A的每个元素是由8个字符组成的串，其行下标i=0,1,…,9,列下标j=1,2,…,10。若A按行序为主序存储，元素A的起始地址与当A按列序为主序存储时的元素（）的起始地址相同（设每个字符占一个字节）。

A．A B．A C．A D．A 10、图的深度优先遍历算法类似于二叉树的（）。

A．中序遍历B．先序遍历C．后序遍历D．按层遍历11、在无向图的邻接表存储结构中，结点的个数是图中边个数的（）倍。

A．1 B．2 C．3 D．4 12、下面关于m阶B-树说法正确的是（）

①每个结点至少有两棵非空子树。

②树中每个结点至多有m-1个关键字。

③所有叶子在同一层上。

④当插入一个数据项引起B树结点分裂后，树长高一层。

A．①②③ B．②③④ C．②③ D．③ 13、判定一个有向图是否存在回路，可以利用( )方法。

A．求关键路径的方法B．广度优先遍历算法C．求最短路径的Dijkstra方法D．拓扑排序14、有一个长度为17的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为（）。

A．53/17 B．55/17 C．57/17 D．59/17 15、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。

A．起泡排序B．选择排序C．快速排序D．插入排序二、判断题（每空1分，共10分）1、算法的设计取决于数据的逻辑结构。

( ) 2、栈和线性表的区别在于，它们的操作都限制在表的两端进行操作。

( ) 3、稀疏矩阵压缩存储中，一般只采用三元组表示法进行存储。

( ) 4、空格串和空串的长度都为0。

( ) 5、中序线索二叉树中，所有结点的指针域都不为空。

( ) 6、为了很方便的插入和删除数据，可以使用双向链表存放数据。

（）7、在二叉树排序树中插入一个新结点，总是插入到叶结点下面。

( ) 8、无向图所对应的邻接矩阵一定是对称矩阵，有向图所对应邻接矩阵一定是非对称矩阵。

( ) 9、（10，12，23，58，46，29，15，22，77）只可能是一趟

简单选择排序之后的结果序列。

( ) 10、快速排序的速度在所有排序方法中是最快的。

( ) 三、填空题（每空1分，共10分）1、一个循环队列Q入队列时，指针的操作为（队列长度为m）________。

2、6层平衡二叉树至少有________个结点。

3、广义表A((a),b,(c,(d),e))，取出原子e的操作是________。

4、中缀表达式(A*B+(C-D)/E)*F-(G+H)的后缀表达式是________。

5、已知二叉树有30个叶子结点，则该二叉树的总结点数至少是________。

6、求图的最小生成树有两种算法，算法适合于求稀疏图的最小生成树。

7、有一个10阶对称阵A[0..9][1..10]，采用压缩存储方式进行存储(以行序为主序)，首地址为100，则A的地址是________。

8、一棵完全二叉树有311个结点，则其叶子结点个数为________。

9、对关键码序列28，16，32，12，60，2，5，72快速排序，一次划分结果为。

10、n个顶点构成的有向环，最多为________棵最小生成树。

四、应用题（每题7分，共35分）1、假设一棵二叉树的后序序列为*****EFDA，中序序列为*****JEDF。请画出这棵二叉树，并将其转换为对应的森林。

2、对以下关键字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT)，哈希函数为H（K）=（关键字中第一个字母在字母表中的序号）MOD 7，用线性探测法处理冲突，求构造一个装填因子为0.7的哈希表；

并分别计算出在等概率情况下查找成功的平均查找长度。

3、已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤：

（1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL。

（2）构造一棵二叉排序树，如果对每个关键字的查找概率相同，求查找成功时的平均查找长度ASL。

4、下图是带权的有向图G的邻接表表示法，求：

（1）以结点V1出发广度遍历图G所得的结点序列；

（2）从结点V1到结点V8的关键路径。

5、给出一组关键字{zhao，qian，sun，li，zhou，wu，zheng，wang}，写出初始建大顶堆的过程（关键字大小比较以字母表顺序为准）。

五、算法设计题（每题15分，共30分）1、设计算法将一个带头结点的单链表LA分解为两个具有相同结构的链表LB、LC，其中LB 表的结点为LA表中值小于零的结点，而LC表的结点为LA表中值大于零的结点。（链表的数据域元素类型为整型，要求LB、LC表利用LA 表的结点）2、有这样一棵二叉树，用它表示大家族中已婚男子的父子、夫妻和兄弟三种关系（如图所示），其存储结构用二叉链表存储，请编写一个查找任意父亲结点值为X的所有儿子的算法。结点结构如下：

typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;