哈尔滨工程大学-考研数据结构真题-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[8][7]的起始地址与当A按列序为主序存储时的元素（ ）的起始地址相同（设每个字符占一个字节）。

A．A[7][9] B．A[6][8] C．A[7][8] D．A [6][9] 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][9]的地址是________。

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

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

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

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

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;