哈工程历年数据结构试题

   科目名称：数据结构                    试题编号：429       共3页

一．        判断题（每小题1分，共10分）

1．        若一个算法中的语句频度之和为T（n）=1024n+4nlogn，则算法的时间复杂度为0（nlogn）

2．        串是一种特殊的线性表。

3．        两个栈共享一个向量空间的优点是其中一个栈可用该空间一半或一半以上。

4．        广义表是非线性数据结构，因为表中的元素可以是子表。

5．        二叉树的中序序列中，结点A在结点B之前的条件是A是B的祖先。

6．        若一个有向图的拓扑排序没有包括全部顶点，则说明该图存在有向回路。

7．        具有几个顶点e条边的无向图，若用邻接矩阵作为存储结构，则求任一顶点的度数的时间复杂度为0（e）.

8．        哈希法既是一种查找方法，又是一种存储方法。

9．        希尔排序是属于插入排序的改进方法。

10．        在单链表上可以实现简单选择排序，但难以实现堆（选择）排序。

二．        填空题（每小题2分，共20分）

1．        在字符串S=“structure”中，以t为首字符的子串有——个。

2．        N阶的下三角阵按行序为主序存储，每个元素占L个单元，若已知首地址为loc(A00 ),则元素Aij(0≤j≤i≤n-1)的存储地址loc（Aij）为——

3．        已知一个栈的入栈序列是1，2，3，……，n，其输出序列为P1，P2，P3，……，Pn。若P1=n，则Pi为——

4．        已知广义表LS=（a,（b,c,d），e）运用head和tail函数取出LS中的原子b的运算是——

5．        在一棵具有h层的满三叉树中，结点总数为——

6．        已知在一棵含有n个结点的树中，只有度为3和度为0的结点，则树中度为0的结点数为——

7．        设树T的度为4，其中度为1，2，3，4的结点树分别为4，2，1，1，则听众叶子数为——

8．        在含有20个关键字的4阶B-树中进行查找，至多访问——个结点。

9．        将m个互为冲突（具有相同的哈希地址）的记录存入哈希表，处理冲突采用伪随机探测法。最多需要探测——次。

10．        将30个记录分成5块，进行分块查找，平均查找长度是——。

三，单选题（每小题2分，共30分）

1．        算法是指——

A．        可执行程序。 B。问题求解的计算方法。C。系统软件。D。解决问题的有限运算序列。

2．        从逻辑上可以把数据结构分成——结构。

A．        动态和静态

B．        紧凑和非紧凑

C．        线性和非线性

D．        内部和外部

3．        将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为——

  A．0（1）

  B．0（n）

  C．0（m）

  D．0（m+n）

4．长度为n（1…n）的顺序循环队列中，front和rear分别指示队首和队尾。判断队列满的条件为——

  A．rear%n=front

  B．front%n+1=rear

  C．rear%n-1=front

  D．rear%n+1=front

5．设二叉树有2n个结点，则对于m  A．n个度为0 

  B．2m个度为0

  C．2m个度为1

  D．2m个度为2

6．某n>0个结点的二叉树的先序序列正好相反，则该二叉树一定不是——的二叉树。

  A．任一结点无左孩子

  B．任一结点无右孩子

  C．深度为n

  D．存在度为2的结点

7．二叉树用二叉链表表示，若要将其所有结点的左，右子树相互交换位置，则采用下列——遍历的方法较为合适。

  A．先序

  B．中序

  C．后序

  D．按层

8．对于二叉树的两个结点X和Y，应该选择——两个序列来判断X是否Y 的祖先。

A．先序和后序

B．先序和中序

C．中序和后序

D．任意两个序列都行

9．最小生成树指的是连通图中——

A．边数最少的生成树

B．顶点相对较少的生成树

C．极小连通子图

D．所有生成树中权值之和最小的生成树

10．具有n个顶点的强连通图至少有——条弧。

A．n-1

B．n

C．2n

D．n（n-1）

11．对20 个有序记录进行折半查找，查找成功的平均查找长度为——

A．5

B．37/10

C．39/10

D．41/10

12．哈希表长度为m，哈希函数H（K）=K%P，一般来说P应取小于m的最大——

  A．奇数

  B．偶数

  C．素数

  D．合数

13．对动态查找有高效率的查找表组织结构是——

  A．有序表

  B．分块有序表

  C．循环链表

  D  B-树

14．当初始数据有序时，不应采用——

  A．堆排序

  B．快速排序

  C．基数排序

  D．希尔排序

15．在n个元素中找出两个最小的元素，当n很大时，采用——方法比较次数较少。

  A．树型选择排序

  B．简单选择排序

  C．归并排序

  D．快速排序

四．综合题（每小题10分，共40分）

  1．一棵二叉树的先序，中序，后序序列分别如下：（其中有部分结点未显示出来）

     先序序列：_B_F_ICEH_G

     中序序列：D_KFIA_EJC_

      后序序列：_K_FBHJ_G_A

   （1）。将先序，中序，后序序列完整写出来。

   （2）。画出该二叉树。

2．对关键字序列{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}

  (1).构造一棵平衡二叉（排序）树

  （2）。求其查找成功的平均查找长度ASL。

3对无向加权图：

（1）用普里姆算法从顶点①出发求其最小生成树，并写出选点顺序。

（2）用克鲁斯卡尔算法求其最小生成树，并写出选边顺序

4．        给出的3阶B-树：

（1）。写出对给出的B-树依次插入关键字29，25，84，6后的B-树。

（2）。写出对给出的B-树依次删除关键字11，49，52，36后的B-树。

五．算法题（第1，2，3题各12分，第4题14分，共50分）

  1．对用二叉链表表示的二叉树，设计一个算法，求其后序序列的第一个结点。

  2．完全二叉树顺序存储在数组A[1…n]中，请写一算法：求下标为i和j的两个结点的所有公共祖先结点，并按下标从大到小的顺序将它们的值打印出来。

  3．长度为n的字符串存储在结点大小为1的单链表中。试写一算法，判断字符串是否中心对称（例如：‘abccba’是中心对称）。

4．已知一棵满二叉树顺序存储在数组B[1…n]中，设计一个算法，产生二叉树的二叉链表。

哈尔滨工程大学2003年数据结构考研试题

一 判断题(每小题一分，共十分)

1 数据结构，数据元素，数据项在计算机中的映象（表示）分别称为存储结构，结点，数据域。         对

2 线性表的逻辑顺序与存储顺序总是一致的。       错

3 广义表的表头或是元素或是一个广义表，而表尾总是一个广义表。     对

4 拓扑排序是一种内部排序的算法。       错

5 字符串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。    对

6 若线索二叉树有n个结点，则必有n+1条不空的指向树中结点的线索。  错

7 稀疏矩阵的压缩存储方法一般有三元组和十字链表两种。    对

8 在AOE网中，一定有不止一条关键路径。    错

9 二维数组是其数据元素为线性表的线性表。         对

10 一个栈的输入序列是12345，则输出序列43512是可能的。       错

二 单项选择（每小题2分，共20分）

1 数据结构从逻辑上可以分成 线性和非线性 两种结构。

2 哈希（Hash）法查找的基本思想是根据 关键字值 来决定记录的存储位置。

3 利用栈求表达式（（A-B）-C）-(D-(E-F)),操作数栈须有 4 项。

4 图的广度优先搜索算法类似于二叉树的 按层 遍历操作。

5 在所有排序方法中关键字比较次数与记录初始排列次序有关的是 插入排序。

6 二维数组A的行下标从1到8，列下标从1到10，若每个元素占3个单元，则该数组按“以列序为主序”存放时，A[5][8]的起始位置是  180

7 表达式a*(b+c)-d的后缀表示（逆波兰式）是 abc+*d－

8 在一个具有n个结点的单链表中查找，查找成功时需要平均计较 (n+1)/2 结点。

9 设Q[0……n-1]为循环队列，front,rear分别为队列的头，尾，则队列中的元素个数为 (rear-front+n) MOD n 

10 在各种查找方法中，平均查找长度与结点个数无关的查找方法是 二叉树查找

三 计算题（每小题6分，共30分）

1 一颗树有N1个度为1的结点，N2个度为2的结点…………，Nm个度为m的结点，求：该树中终端（叶）结点的个数N0 

2 对长度为12的有序表进行折半查找，求查找成功与不成功时各平均比较次数。

3 已知一颗3阶的B－树中含有25个关键字，求该B－树的最小高度和最大高度（不包含叶子层）

4 已知一棵平衡二叉树的深度为6，求树中最少可能的结点数和最多可能的结点数。

5 对n个结点的平衡二叉树，请分别求出当二叉树具有最小深度K和最大深度K时，第K层上的结点数。

四 综合题 （每小题8分，共40分）

1 广义表A＝((a),(b,(c,d,e)),()),请写出其链式存储结构。设链表中有两类结点，表结点形式为   tag=1 hp  tp  ,其中指针hp和tp分别指向表头

和表尾，元素（原子）结点形式为 tag＝0   元素值    

2 对关键字序列（49，38，65，97，75，13，27，51，55，10）进行希尔排序。若排序三趟，各趟的增量分别为 d1=5 ,d2=3 ,d3=1 ，则请写出每趟的结果及元素移动次数。

3 电文中使用字符a,b,c,d,e,f,他们出现的频率为（4,7,5,2,9,8）,请画出对应的编码哈夫曼树，并求出传送电文的总长度。

4 已知一棵二叉树的中序序列为DAJFBGICEHK，后序序列为DAFBJCIKHEG,请画出该二叉树，并使其成为先序线索树。

5 对于加权图 

                       12

          6                                    

                8        15            13

           4                   16                                

      10        9          20           10

                      5

用克鲁斯卡尔(Kruskal)方法构造最小生成树，并写出选边的次序。

五 算法题 （1，2小题各13分，3，4小题各12分，共50分）

1 设用二叉链表表示的二叉树不空，其根指针为root，结点形式为：

lchild   data  rchild   

请写出将二叉树中所有结点的左，右子树相互交换的非递归算法。

2 利用两个栈S1和S2来模拟一个队列。若不存在栈溢出问题，则请写出用栈的操作来实现队列的插入和删除的算法。

3 设计一个算法，在长度为n的（小顶）堆R[1………n]中删除一个元素R[s]（s<=n）产生一个长度为n－1的(小顶)堆，并将R[s]存放于R[n]中。

4 假设循环单链表不空，且无表头结点亦无表头指针，指针p指向链表中某结点。请设计一个算法，将p所指节点的前驱结点变为p所指结点的后继结点。

哈尔滨工程大学2001年数据结构考研试题

一 填空（每空一分，共14分）

1 数据元素是数据结构的基本单位，数据项是数据的不可分割的最小单位。

2 深度是k的完全二叉树至少有2^（k－1）个结点，至多有2^k-1个结点。

3 哈希表的查找效率主要取决于造表时选取的哈希函数和处理冲突的方法。

4 对100个记录进行折半查找，最多比较7次，最少比较1次。

5 有n个顶点的无向图，最少有0条边，最多有n(n-1)/2条边。

6 AOE网中，从源点到汇点的最长路径上的活动叫做关键活动。有环的图不能进行拓扑排序。

7 对于堆排序，常用的建堆算法是筛选法，堆的形状是一棵完全二叉树。

二 判断题（每小题1分，共5分）

1 线性表的链式存储结构优于顺序存储结构。     错

2 链表的每个节点中都帢包含一个指针。         错    例如双向链表

3 栈和队列都是顺序存储结构的线性结构。      错      链栈

4 若数的度为2时，则该树为二叉树。           错

5 若广义表中的每个元素都是原子，则广义表为线性表。     对 

三 问答题（每小题4分，共16分）

1 一棵3阶4层（根为第一层，叶子为第四层）的B－树，至少有多少个关键字，至多有多少个关键字？

答：7个        26个

2 利用栈秋表达式（（A-B）-C）-(D-(E-F)) 的值，运算符栈和操作数栈各必须具有多少项？

答：5项       4项

3 以行序为主序存储10阶对称矩阵A，采用下三角的压缩存储方式，若起始地址是d，则A85的存储地址是多少？

答：32＋d

4 设哈希表中以存在无个记录（如图一所示）。哈希函数为H(K)=K MOD 11，用二次探测再散列处理冲突。请问关键字为94的记录的存储地址是多少？

         0      1    2    3     4    5    6     7    8      9         10

图一

                 45                  16   39    62                      76

答：存储地址是 2 

四 综合题（每小题5分，共35分）

1 给定一组权值{9，6，14，17，2，15，3，16}，请构造哈夫曼树，并计算其带权路径长度。

答：带权路径长度186

2 已知二叉树的先序遍历的结果为ABCDEFGHIJ，中序遍历的结果为CBEDAHGIJF，请画出这颗二叉树。

3 对图二所示的无向图，（1）请用邻接表表示，且顶点链接按序号从小到大链接。

（2）请写出从V0出发的深度优先遍历和广度优先遍历的结果。

图二：

                            0

O 

                 1                   2            

3           4               5          6

               7

4 将图三所示的树转换为二叉树，并使其成为后序线索树。

图三:                         A

                   B                 C           D

           E                 F     

                             G        H        I        J

                    K          L               M

N

5 对关键字序列{44，12，53，13，37，88，24，61}构造一棵平衡二叉树。

6 已知一个OE网，如图四所示，求其关键路径，并给出时间4的最迟发生时间和事件5最早发生时间？

图四：      1           4             4

                                         12

        5       2                6               9

11      5       10

0                    9           

                                                 18

14                         6 

              3                   5

     3                     5

                  7                7            8

8 

7 对序列{50，77，，98，39，12，26，48，44，35}创建初始堆。

五（8分） 设指针head 指向无表头结点单链表的首结点。试设一算法，删除链表中值为X的结点，若X结点不存在，则输出“不存在”信息。

六（10分）已知一个有向图的邻接表，试编写一个算法求每个结点的出度和入度。

七（12分）已知一个二叉树存储于二叉链表中，其结点结构为  lc    data    rc    

其中lc和rc分别为指向左子树和右子树根的指针域。试编写一个

非递归算法，求二叉树的结点总数及其深度。