填空题：

1. 将时间复杂度数量级O(n2)、O(nlog2n)、O(2n)、O(1)、O(log2n)和O(n)按由小到大进行排序，结果为：__O(1)，_O(log2n)，_O(n)_，O(nlog2n)，O(n2)，O(2n)___。

2.  数据的逻辑结构可分为_____线性结构___和_____非线性结构___。

3.  用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为______SXSSXSXX__。

4.  设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下两条语句：_____py->next=px->next__和_px->next=py_____。

5.  在双链表结构中，若要求在p 指针所指的结点之前插入指针s所指的结点，则需执行下列语句：s->next=p； s->prior= ____p->prior____；p->prior=s；___s->prior->next_____=s；

6.  已知一个栈的输入序列是1,2,3,…,n，其输出序列是p1,p2,…,pn，若p1=n，则pi的值是___n-i+1__。

7.  用下标0开始的长度为N的数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=____(M+1)%N____。

8.  串是一种特殊的线性表，其特殊性：  数据元素的类型为字符型  ；两个串相等的充分必要条件是   它们的长度相等且对应位置的字符相同。

9. 设有二维数组A[0..9, 0..19],其每个元素占2个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6, 6]存储地址为______352__。

10. 设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：LOC(a11)=1），则a85的地址为_____33___。

11. 广义表(a, (a, b), d, e, ((i, j), k))的长度是      5 ，深度是    3      。 

12.  设广义表L=((), ())，则head(L)是  ()    ；tail(L)是 (())      。 

13.  有n个顶点的无向图最多有_____n*(n-1)/2___条边。

16. 对于n个顶点的连通图来说，它的生成树一定有____n-1____条边。

14.  在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最小的是    快速排序     ，需要内存容量最多的是   基数排序    。 

15.  对序列{98,36,-9,0,47,23,1,8,10,7}采用希尔排序，增量为4的第一趟排序结果是__

__（10，7，-9，0，47，23，1，8，98，36)____。

16. 一个有2021个结点的完全二叉树的高度为___11_____。

选择题

1.  数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的（ 关系   ）和运算的学科。

A.结构            B.关系            C.运算            D.算法

 

2. 可以用（  抽象数据类型  ）定义一个完整的数据结构。

A.数据元素     B.数据对象         C.数据关系     D.抽象数据类型

 

3. 抽象数据类型的三个组成部分分别为（数据对象、数据关系和基本操作    ）。

A.数据对象、数据关系和基本操作       B.数据元素、逻辑结构和存储结构

C.数据项、数据元素和数据类型         D.数据元素、数据结构和数据类型

 

4. 下列说法正确的是（ 一些表面上不相同的数据可以具有相同的逻辑结构   ）。

A.数据元素是数据的最小单位     B.数据结构是带有结构的各数据项的集合

C.一些表面上不相同的数据可以具有相同的逻辑结构    D.数据项是数据的基本单

解析：A.数据元素是数据的基本单位 

C.数据结构是相互之间存在一种或多种特定关系的数据元素的集合

 D.数据项是数据的最小单位

 

5. 某算法的语句执行频度为3n+nlog2n+n2+8，其时间复杂度可表示为（ O(n2)  ）。

A.O(n2)       B.O(nlog2n)          C.O(log2n)      D.O(n)

解析：时间复杂度主要取决于n的最高次幂数，即最大影响因子。此题目中n的最高次幂数为n^2。

 

6.  以下（  由100个字符组成的序列 ）是一个线性表。

A.由n个实数组成的集合             B.由100个字符组成的序列

C.所有整数组成的序列               D.邻接表

解析：线性表的定义为：由n个数据元素组成的有限序列。

A. 不满足序列。集合中的各元素之间没有前后驱关系。  

C.不满足有限。所有整数组成的序列的元素个数是无穷多个。  

D.邻接表是属于存储结构，但线性表是一种逻辑结构。

 

7. 向顺序表中插入一个新数据结点时，平均需要移动（ n/2   ）个结点。

A. n            B. n/2           C. n+1           D. (n+1)/2 

 

8. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（O(1) O(n)   ）。

A.O(n)  O(n)     B. O(n)  O(1)   C. O(1)  O(n)   D. O(1)  O(1)

解析：顺序存储可以实现“随机存取”，因此访问结点的时间复杂度为O(1)，而插入、删除结点由于涉及到大量移动元素，故其时间复杂度为O(n)。

 

9.  线性表（a1,a2,…,an）以链接方式存储时，访问第i元素的时间复杂度为（ O(n)   ）。

A.O(i)           B.O(1)          C.O(n)         D.O(i-1)

解析：链式存储访问元素要遍历

！：一个算法的时间复杂度的定义是问题规模（即n）的函数，故不是O（i）

 

10. 单链表中增加一个头结点的目的是（ 方便运算的实现   ）。

A.使单链表至少有一个结点           B.标识表结点中首结点的位置

C.方便运算的实现                   D.说明单链表是线性表的链式存储

解析：头结点的存在，使得空链表与非空链表的处理变得一致，也方便了对链表的开始结点插入或删除操作。

 

11. 设单链表中结点的结构为（data,next），若在p指针所指结点后插入由指针s指向的结点，则应执行下面的（   s->next=p->next;  p->next=s; ）操作。

A.p->next=s;  s->next=p;             B. p->next=s;  s->next=p->next;

C. s->next=p;  s=p;                  D. s->next=p->next;  p->next=s;

 

12. 某链表最常用的操作是在末尾插入结点和删除尾结点，则选用( 带头结点的双循环链表  )最节省时间。

A.单链表                 B.单循环链表

C.带尾指针的单循环链表   D.带头结点的双循环链表

解析：首先总在末位操作，所以使用循环链表。又因为要执行删除操作：删除尾结点需要找到倒数第二个结点，但单向链表无法得到前一个结点，即倒数第二个结点。而双循环链表，可向回访问。

 

13. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ head->next==NULL  ）。

A. head==NULL           B. head->next==NULL

C. head->next==head       D. head!=NULL

 

14. 下面关于串的的叙述中，不正确的是（  空串是由空格构成的串  ）。

A. 串是字符的有限序列         B. 模式匹配是串的一种重要运算

C. 空串是由空格构成的串       D. 串既可以顺序存储，也可以链式存储

解析：空串表示所含字符数为0的串。空格串表示只含空格的串。

 

15. 已知广义表LS＝((a, b, c), (d, e, f))，运用head和tail函数取出LS中原子e的运算是（ head(tail(head(tail(LS))))   ）。

A. head(tail(LS))                    B. tail(head(LS))

C. head(tail(head(tail(LS))))            D. head(tail(tail(head(LS))))

解析：

若广义表Ls非空(n≥1)，则a l 是LS的表头，其余元素组成的表( a 2 ，a3,…，a n )称为Ls的表尾。

任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。 

tail(LS)=((d,e,f)) 

head(tail(LS))=(d,e,f)        [！有两层括号，所以=（d,e,f),不=d]

tail(head(tail(LS) )) = (e,f)      [表尾必定是子表]

head(tail( head(tail(LS) ))) = e 

 

 

16. 下面几个符号串编码集合中，不是前缀编码的是（ {11,10,001,101,0001}  ）。

A. {0,10,110,1111}                   B. {11,10,001,101,0001}

C. {00,010,0110,1000}                D. {b,c,aa,ac,aba,abb,abc}

解析：前缀编码,在一个字符集中,任何一个字符的编码都不是另一个字符编码的前缀。

    B中10是101的前缀，所以不是前缀编码。

 

17. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3,…,pn，若pn是n，则pi是（ n-i+1 ）。

A. i                 B. n-i            C. n-i+1        D. 不确定

 

解析：由栈的先进后出原则 

P1——Pi——Pn 

1--—n-i+1—-n

 

18. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3,…,pn，若p1是3，则p2是（  不可能是1  ）。

A.一定是2           B.一定是1       C. 不可能是1  D. 以上都不对

解析：若第一个输出的是3，说明前面的1,2都有入栈且没有出栈，要想让1出栈，则必须2先出栈（p2=2,p3=1)。

 

19. 假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ (rear-front+m)%m   ）。

A. (rear-front+m)%m            B. rear-front+1

C. (front-rear+m)%m            D. (rear-front)%m

 

20. 用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ 队头、队尾指针都可能要修改   ）。

A. 仅修改队头指针             B. 仅修改队尾指针 

C. 队头、队尾指针都要修改     D. 队头、队尾指针都可能要修改

 

21.  空串与空格串的区别在于（   两串包含的字符不相同 ）。

A. 没有区别                    B. 两串的长度不相等

C. 两串的长度相等              D. 两串包含的字符不相同

解析：空串表示所含字符数为0的串。空格串表示只含空格的串。

 

22. 在线索二叉树中，某结点*p没有右孩子的充要条件是（ p->rtag==1  ）。

A. p->rchild==NULL                B. p->rchild!=NULL

C. p->rtag==1                      D. p->rtag==0

解析：p->rchild线索化后已经指向结点，所以判断p->rchild没用.AB错误

    

 

23. 若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点有（ 11  ）个。

   解析：N0=N2+1 

A. 9              B. 11              C. 15             D. 不确定

 

24. 有关二叉树下列说法正确的是（  一棵二叉树的度可以小于2  ）

A. 二叉树的度为2                   B. 一棵二叉树的度可以小于2

C. 二叉树中至少有一个结点的度为2   D. 二叉树中任何一个结点的度都为2

 

25. 具有6个顶点的无向图至少应有（ 5   ）条边才可能是一个连通图。

A. 5              B. 6              C. 7              D. 8

 

26. 图的深度优先遍历算法类似于二叉树的（先序遍历    ）算法。

A. 先序遍历     B. 中序遍历​       C. 后序遍历​    D. 层次遍历

 

27. 下列关于最小生成树的说法中，正确的是（  仅I​  ）。

I. 最小生成树的代价唯一。

II. 权值最小的边一定会出现在所有的最小生成树中。

Ⅲ. 用Prim算法从不同顶点开始构造的所有最小生成树一定相同。

Ⅳ. 使用Prim算法和Kruskal算法得到的最小生成树总不相同。

A. 仅I​           B. 仅II           C. 仅I 、III        D. 仅II 、Ⅳ

解析：Ⅰ.最小生成树不唯一，但最小生成树的代价唯一（易错）

     Ⅱ.如果加入权值最小的边构成环，则权值最小的边不存在于最小生成树中

     Ⅲ.设N个结点构成环，N-1条边权值相等，则从不同的顶点开始Prim算法会得到N- 1种不同的最小生成树

Ⅳ.当最小生成树唯一时（各边的权值不同），普里姆算法和克鲁斯卡尔算法得到的最小生成树相同

28. 有一个有序表为{1, 3, 9，12，32，41，45，62，75，77，82，95，100}， 当二分查找值为82的结点时，（  4  ）次比较后查找成功。

A.1             B.2           C.4          D.8

 

29. 对线性表进行二分查找时，要求线性表必须（ 以顺序方式存储，且结点按关键字有序排列 ）。

A.以顺序方式存储.            B.以顺序方式存储，且结点按关键字有序排列

C.以链接方式存储             D.以链接方式存储，且结点按关键字有序排列

解析：二分查找通过左右端数据相加除以2求出中点位置mid，然后将要查找的数值与中点位置比较，小于中点，右端点变为mid-1，否则左端点变为mid+1。所以要求线性表是顺序存储结构且要有序。

 

30. 设一维数组中有n个元素，则读取第i个元素的平均时间复杂度可表示为（ O(1)     ）。

A.O(n2)       B.O(nlog2n)          C.O(1)         D.O(n)

解析：数组是读取数组下标（没有循环），数组下标为常数，所以为O(1)

 

 

判断题

1.（  ×  ） 算法原地工作的含义是不需要任何额外的辅助空间。

                解析：算法原地工作的含义是指不需要任何额外的辅助（！不是辅助空间），算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。

2.（  √  ） 数据的定义在数据的逻辑结构上，其实现要基于某种存储结构。

3.（  ×  ） 链表中的头结点仅起到标识的作用。

解析：还方便了对链表的开始结点插入或删除操作。

4.（  √  ） 线性表采用链表存储时，结点和结点之间的存储空间可以是不连续的。

5.（  ×   ） 若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列1,5,4,6,2,3。

             解析：栈是先进后出，由1546可知：SXSSSSXXSX（1进栈，1出栈，2进栈，3进栈，

4进栈，5进栈，5出栈，6进栈，6出栈）。若之后2要想出栈，则必须3先出栈。

6. （  ×  ） 通常使用队列来处理函数或过程的调用。

解析：用堆栈来处理函数调用，函数调用过程中把参数压入堆栈保存,执行完毕后弹出  堆栈释放。

7.（  √   ） 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

8.（  √   ） 两个栈共用静态存储空间，栈顶相对使用就可以避免空间溢出问题。

9.（  √   ） 队列是插入与删除操作分别在表的两端进行的线性表，是一种先进后出结构。

10.（  √  ） 如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。

11.（  √ ） 在图的深度优先遍历中一般要采用栈来暂存刚访问过的顶点。

12.（  ×  ） 在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。

解析：存在多个关键路径（存在并行的关键活动）时，缩短关键活动需使所有关键路径都缩短。

13.（  √ ） 在有向图中，各顶点的入度之和等于各顶点的出度之和。

14.（  × ） 连通分量是无向图中的极小连通子图。

解析：连通分量，是指无向图的极大连通子图

15. （  ×  ） 对n个顶点的连通图G来说，如果其中的某个子图有n个顶点、n-1条边，则该子图一定是G的生成树。

16.（  √  ） 无论是有向图还是无向图，其邻接矩阵表示都是唯一的。

 

 

 

 

解答题

1. 设二叉树BT的存储结构如下：

1     2     3    4     5     6    7     8     9   10

其中BT为树根结点的指针，其值为6，Lchild和Rchild分别为结点的左、右孩子指针域，data为结点的数据域。试完成下列各题：

（l）画出二叉树BT的逻辑结构；答案

（2）写出按前序、中序、后序遍

历该二叉树所得到的结点序列；

（3）画出二叉树的后序线索二叉树。

 

 

 

 

 

 

 

 

2．设一棵二叉树的先序遍历序列：ABDFCEGH，中序遍历序列：BFDAGEHC。

（1）画出这棵二叉树；

（2）画出这棵二叉树的后序线索二叉树；

（3）将这棵二叉树转换成对应的树（或森林）。

答案：

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3．将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中，散列表的存储空间是一个下标从0开始的一个一维数组，散列函数为：H(key)=(key×3)% 7，处理冲突采用线性探测法，要求装载因子为0.7。

（1）请画出所构造的散列表。

（2）分别计算等概率情况下，

查找成功和查找不成功的

平均查找长度。

答案：

 

 

 

 

 

 

 

 

 

4． 给定带权无向图G。（P280，图8.24）            

  答案:

（1）画出该图的邻接表存储结构。

（2）根据该图的邻接表存储结构，从顶点3发，调用DFS和BFS算法遍历该图，给出相应的遍历序列。

（3）给出

采用Kruskal

算法构造最小

生成树的过程。

 

 

 

 

 

5．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。

先序序列：A B C D E F G H I J K  （可填入字母：A,B,F,J）

中序序列：C B E D F A H J K I G    (可填入字母：D,E,H)

后序序列：C E F D B K J I H G A    (可填入字母：C,G,K)

答案：

（填序列）

1 先判断各序列剩余的可填入字母

2 由后序知A为根节点（若先序中第一个字母为A,也可判定A为根节点）

（由于节点数大于2个，则B是A的左孩子结点）

3 由2可将中序划分成A的左右侧（二叉树的左右子树与中序的左右字母相同→中序H位置确定）

4 在中序，C在B的左侧→则C必在A的左子树→在后序，B在中间位置→后序C位置确定

5 （（中序知，F在左子树上）且（后序知，E在F之前））→先序F位置确定→先序只剩J，则先序J位置确定

6 （（先序中，DEF紧挨）且（后序中，EFD紧挨）且（中序中只剩D,E字母））→中序D,E位置确定

7 由完整先序序列知，GHIJK在右子树上，且G为A的右孩子结点→后序G位置确定→后序K位置确定

（构造二叉树）

A为根节点，B,C,D,E,F为左子树 G,H,I,J,K为右子树

A,B,G的位置由上述中2，7步确定

​（左子树）

在中序，CB紧挨→C为B的左孩子

在后序，DB紧挨且C在最左→D为B的右孩子

在中序，EDF紧挨→E,F为D的左右孩子

​（右子树）

（（在先序，GH紧挨）且（在中序，HJKI在G的左侧））→H为G的左子树

（（在先序，HI紧挨）且（在后序，IH紧挨））→I为H的右子树

（（在先序，IJ紧挨）且（在中序，JK在G的左侧））→J为I的左子树

（（在先序，JK紧挨）且（在后序，KJ紧挨））→K为J的右子树

 

 

 

6．假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07、0.19、

0.02、0.06、0.32、0.03、0.21和0.10。（P240）

（1）试为这8个字母设计哈夫曼编码，求出WPL；

（2）试设计另一种由二进制表示的等长编码方案，并求出该编码的平均长度。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7．对于有向无环图：

（1）叙述求拓扑有序序列的步骤。

（2）对于图G（P303），写出它的3个不同的拓扑序列。

答案：

（1）1 从有向图中选择一个没有前驱的顶点（即入度为0的顶点）并且输出它。

​ ​  2 从图中删去该顶点，并且删去从该顶点发出的全部有向边

​​  3 重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止

​ （2）由（1）可知，拓扑序列可为：

​​ 041253  041523  045123  450123  401253  405123  401523

 

 

 

 

 

 

8.假设一棵二叉排序树的关键字为单个字母，其后序遍历序列为 ACDBFIJHGE.

（1）画出该二叉排序树；        答案:

（2）求在等概率下的查找成功的平均查找长度。

（3）求在等概率下的查找不成功的平均查找长度。

 

 

 

 

 

 

 

 

算法设计

1．已知顺序表L的所有元素按其值非递增有序排列，设计算法删除表中值相同的多余元素。

typedef  struct 

     {​  ElemType data[MaxSize];     /* 存放顺序表元素*/  

  ​      int length;                  /* 存放顺序表的长度*/  

     } SqList;                      /* 顺序表的类型定义*/  

 

 

 

 

 

 

 

 

   

 

 

 

 

 

 

 

 

 

 

 

 

2. 已知单链表L中各元素的值互异，设计算法判断单链表L是否按结点值递增有序排列。

 

3. 设ha=(a1,a2,…,an)和hb=(b1,b2,…,bn)是两个带头结点的循环单链表，请完成下列算法，实现将这两个表合并成一个带头结点的循环单链表hc的功能。

void Merge(LinkList *ha, LinkList *hb, LinkList *&hc)

{  LinkList *p=ha->next;

hc=ha;

while (   p->next!=ha    )     /* 找到ha的尾结点p */

      p=p->next    

      p->next=ha-next               /* 将结点p的next指向hb的开始结点 */

while (      p->next!=hb      )     /* 找到hb的尾结点p */

 p=p->next;

    p->next=hc               /* 构成循环单链表 */

free(hb);               /* 释放hb单链表的头结点 */

}

 

 

 

 

 

4．已知线索二叉树中的结点类型TBTNode的声明如下：

typedef struct node

{   ​ElemType  data;       /*数据域*/

  ​int  ltag, rtag;         /*左、右线索标志域*/

  ​struct node  *lchild;   /*左孩子链域或指向前驱的线索*/

  ​struct node  *rchild;   /*右孩子链域或指向后继的线索*/

} TBTNode;

完成下面的算法，实现在中序线索二叉树中找结点p的中序前驱，返回前驱结点的指针。

TBTNode * 1Inprior(TBTNode *p) /*中序线索二叉树中查找结点p的直接前驱*/

{       TBTNode *pre ;    

   if(p->ltag==1)  pre=p->lchild;    

   else                         

   {       pre=p->lchild;       

       while (pre->rtag==0)      

             pre=pre->rchild;     

   }

   return pre;

}

 

 

 

5．设计在二叉排序树t中查找特定元素(值为x)的算法SearchBST(t, x)。

typedef struct node

{  KeyType   key;

InfoType   data;

Struct node  *lchild,*rchild;

}BSTNode;

BSTNode  *searchBST(BSTNode  *t, KeyType x)

{

if(t==NULL || t->key==x)

​​return t;

if(k<t->key)

return  searchBST(t->lchild, x);

else

return  searchBST(t->rchild, x);

}