数据结构考试问答题

1．我们知道计算机只能执行机器指令，为什么它能运行用汇编语言和高级语言编写的程

序？

答：靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即机器语言）。

2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？

答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构

的数据元素，而且还在其上定义了一组操作。

3. 简述线性结构与非线性结构的不同点。

答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。

1.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？

答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地

址必须是连续的。

优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分

存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。

若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

2 .描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中

设置头结点的作用是什么？

答：首元结点是指链表中存储线性表中第一个数据元素a

1

的结点。为了操作方便，通常在链表的首

元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链

表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结

点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为

空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头

结点，是不同的存储结构表示同一逻辑结构的问题。

头结点

head



data link

头指针 首元结点

简而言之，

头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；

头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指

针？那还得另配一个头指针！！！）

首元素结点是指链表中存储线性表中第一个数据元素a

1

的结点。

、线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表

L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点

由数据（占2个字节）和指针（占2个字节）组成，如下所示：

05 U 17 X 23 V 31 Y 47 Z

^ ^

100 120

其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地

址为多少？（10分）

答：X= 116 Y= 0 Z= 100 首址= 108 末址= 112

1.说明线性表、栈与队的异同点。

答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊

的线性表，即受限的线性表，只是对插入、删除运算加以限制。

不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先

出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

2.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列

车开出车站的所有可能的顺序。

答：至少有14种。

① 全进之后再出情况，只有1种：4，3，2，1

② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4

③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4

④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

3.假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’

和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列

等方式正确输出其回文的可能性？

答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；

堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；

队列是先进先出，不易实现。

哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从

后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减

后压还是……）

若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部

压入后再依次输出。

4.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，

这就叫“假溢出”。

采用循环队列是解决假溢出的途径。

另外，解决队满队空的办法有三：

① 设置一个布尔变量以区别队满还是队空；

② 浪费一个元素的空间，用于区别队满还是队空。

③ 使用一个计数器记录队列中元素个数（即队列长度）。

我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。

判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N

5.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有

① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素

多少个？

答：用队列长度计算公式： (N＋r－f)% N

① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=32

1. 一棵度为2的树与一棵二叉树有何区别？

答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，

在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子

也有左右之分。

2.设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：

（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，

C的结点类型定义如下：

data为字符型，root为根指针，试回答下列问题：

struct node

1. 对下列二叉树B，执行下列算法traversal(root)，试指出其输出结

{char data;

果；

struct node *lchild, rchild;

2. 假定二叉树B共有n个结点，试分析算法traversal(root)的时间复

};

杂度。（共8分）

A

C算法如下：

B D

void traversal(struct node *root)

C F G

{if (root)

二叉树B

E

{printf(“%c”, root->data);

traversal(root->lchild);

解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输

printf(“%c”, root->data);

出结果为：A B C C E E B A D F F D G G

traversal(root->rchild);

特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其

}

规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复

}

出现；如A，B，D等结点。反之马上就会重复出现。如C，E，F，

G等结点。

时间复杂度以访问结点的次数为主，精确值为2*n，时间渐近度为O(n).

3.给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，

G，I，F，

试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思

想方法。

解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元

素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将

他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。

D

A

C F

E G

B H I

4.给定如图所示二叉树T，请画出与其对应的中序线索二叉树。

解：要遵循中序遍历的轨迹来画出每个前驱和后继。

中序遍历序列：55 40 25 60 28 08 33 54

28

25 33

40 60 08 54

55

5

4

2

2

28

25 33

40 60 08 54

55

60

3

54

五、阅读分析题（）

1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

答：DLR：A B D F J G K C E H I L M

LDR: B F J D G K A C H E L I M

LRD：J F K G D B H L M I E C A

2. （P60 4-27）把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线（包

括度为2的兄弟）,并注意原有连线

结点一律归入左子树，新添连线结

点一律归入右子树。

A

B

E C

K F H D

L G I

M J

答：这是找结点后继的程序。

共有3处错误。

注：当rtag＝1时说明内装后继指针，可

直接返回，第一句无错。

当rtag＝0时说明内装右孩子指针，但孩

子未必是后继，需要计算。中序遍历应当

先左再根再右，所以应当找左子树直到叶

子处。r=r->lchild; 直到LTag=1；

3.阅读下列算法，若有错，改正之。

应改为：while(!r->Ltag)r=r->Lchild;

BiTree InSucc(BiTree q){

//已知q是指向中序线索二叉树上某个结点的指针，

//本函数返回指向*q的后继的指针。

r=q->rchild; //应改为r=q；

if(!r->rtag)

while(!r->rtag)r=r->rchild; //应改为

while(!r->Ltag) r=r->Lchild;

return r; //应改为return r->rchild；

4.画出和下列二叉树相应的森林。

答：注意根右边的子树肯定是森林，

而孩子结点的右子树均为兄弟。

1.已知如图所示的有向图，请给出该图的:

（1） 每个顶点的入/出度；

顶点

（2） 邻接矩阵；

入度

（3） 邻接表；

出度

（4） 逆邻接表。

答案：

1

2

3

4

5

6

2.请对下图的无向带权图：

（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树；

（2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

解：设起点为a。可以直接由原始图画出最小生成树，而且最小生

成树只有一种（类）!

邻接矩阵为：





043



4

3

0

5

5

0

5



5

9



















5





最小生成树→





5507654









9





7



6

0

5

3

3

0



2

2





0







6







5460





PRIM算法（横向变化）：

V b c d e f g h U V-U

Vex

a a a a a a a {a} {b,c,d,e,f,g,h}

lowcost 4 3 ∞ ∞ ∞ ∞ ∞

Vex

a 0 c a a a c {a,c} {b, d,e,f,g,h}

lowcost 4 5 ∞ ∞ ∞ 5

Vex

0 0 c b a a c {a,c,b} {d,e,f,g,h}

lowcost 5 9 ∞ ∞ 5

Vex

0 0 0 d d d d {a,c,b,d } {e,f,g,h}

lowcost 7 6 5 4

Vex

0 0 0 d d d 0 {a,c,b,d ,h {e,f,g }

lowcost 7 6 5 }

Vex

0 0 0 d g 0 0 {a,c,b,d ,h ,{ f,e }

lowcost 7 2 g}

Vex

0 0 0 f 0 0 0 {a,c,b,d ,h ,{e }

lowcost 3 g, f }

Vex

0 0 0 0 0 0 0 {a,c,b,d ,h ,{ }

lowcost g, f, e }

邻接表为：

a → b 4 → c 3

b → a 4 → c 5 → d 5 → e 9 ^

c → a 3 → b 5 → d 5 → h 5 ^

d → b 5 → c 5 → e 7 → f 6 → g 5 → h 4^

e → b 9 → d 7 → f 3 ^

f

g

h

→ d 6 → e 3

→ d 5 → f 2

→ c 5 → d 4

→ g

→ h

→ g

2

6

6

^

^

^

克鲁斯卡尔算法步骤

(按边归并,堆排序)：

先罗列：f---2---g a—3--c f—3—e a—4---b d—4—h

(a,b,c) (e,f,g) (d,h) 取b—5—d, g—5--d 就把三个连通分量连接起来了。

3.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的

深度优先生成树和广度优先生成树。

4.试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，

写出执行算法过程中各步的状态。

解：最短路径为：（a,c,f,e,d,g,b）

1.对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线

性查找的速度快，这种说法对吗？

答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，

查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。

二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；

而二分查找则慢得多。

2.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回

答下列问题：

（1） 画出描述折半查找过程的判定树；

（2） 若查找元素54，需依次与哪些元素比较？

（3） 若查找元素90，需依次与哪些元素比较？

（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

解：

（1） 先画出判定树如下（注：mid=(1+12)/2=6）：

30

5 63

3 7 42 87

4 24 54 72 95

(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；

(3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；

（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4

×3=17次；

但最后一层未满，不能用8×4，只能用5×4=20次，

所以ASL＝1/12（17＋20）＝37/12≈3.08

3.用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?

如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少?

答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元

素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每

个元素的比较次数都是O（1）。

4.设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。

K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：

（10，24，32，17，31，30，46，47，40，63，49）

造出Hash表，试回答下列问题：

（1） 画出哈希表的示意图；

（2） 若查找关键字63，需要依次与哪些关键字进行比较？

（3） 若查找关键字60，需要依次与哪些关键字比较？

（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

解： （1）画表如下：

0 1 2 3 4 5

32 17 63 49

6

7

8 9 10 11 12 13 14 15 16 17

30 31 46 47 24 40 10

（2） 查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;

然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有

空标记），所以应当只比较这一次即可。

（4） 对于黑色数据元素，各比较1次；共6次；

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要

2次，“46”需要3次，“47”需要3次，

所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55

10-3 在起泡排序过程中，什么情况下关键码会朝向与排序相反的方向移动，试举例说明。

在快速排序过程中有这种现象吗？

【解答】

如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中，关

键码可能向与最终它应移向的位置相反的方向移动。例如，

57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动

6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移动

6 7 57 40 38 11 13 34 48 75 9 19 如9向最终方向移动

6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移动

6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动

6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动

6 7 9 11 13 19 57 40 38 34 48 75

6 7 9 11 13 19 34 57 40 38 48 75

6 7 9 11 13 19 34

10-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键码最大的对象

放到序列的最后，第二趟把关键码最小的对象放到序列的最前面。如此反复进行。

【解答】

template void dataList :: shake_Sort ( ) {

//奇数趟对表Vector从前向后, 比较相邻的关键码, 遇到逆序即交换, 直到把参加比较关键码序列

//中最大的关键码移到序列尾部。偶数趟从后向前, 比较相邻的关键码, 遇到逆序即交换, 直到把

//参加比较关键码序列中最小的关键码移到序列前端。

int i = 1, j; int exchange;

while ( i < CurrentSize ) {

exchange = 0;

//起泡排序趟数不超过n-1

//假定元素未交换

//逆向起泡

//发生逆序

//交换, 最小关键码放在Vector[i-1]处

//做“发生了交换”标志

////当exchange为0则停止排序

//正向起泡

for ( j = CurrentSize-i; j >= i; j

--

)

if ( Vector[j-1] > Vector[j] ) {

}

if ( exchange == 0 ) break;

exchange = 1;

Swap ( Vector[j-1], Vector[j] );

for ( j = i; j <= CurrentSize-i-1; j++ )

if ( Vector[j] > Vector[j+1] ) {

}

if ( exchange == 0 ) break;

i++;

exchange = 1;

//发生逆序

//交换, 最大关键码放在Vector[n-i]处

//做“发生了交换”标志

////当exchange为0则停止排序

Swap ( Vector[j], Vector[j+1] );

}

}

10-8在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那

么能否用队列来代替这个栈? 为什么?

【解答】

可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分

为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，

保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对

其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。

10-16 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。

【解答】

(1) 希尔排序 { 512 275 275* 061 } 增量为2

{ 275* 061 512 275 } 增量为1

{ 061 275* 275 512 }

(2) 直接选择排序 { 275 275* 512 061 } i = 1

{ 061 275* 512 275 } i = 2

{ 061 275* 512 275 } i = 3

{ 061 275* 275 512 }

(3) 快速排序 { 512 275 275* }

{ 275* 275 512 }

(4) 堆排序 { 275 275* 061 170 } 已经是最大堆，交换275与170

{ 170 275* 061 275 } 对前3个调整

{ 275* 170 061 275 } 前3个最大堆，交换275*与061

{ 061 170 275* 275 } 对前2个调整

{ 170 061 275* 275 } 前2个最大堆，交换170与061

{ 061 170 275* 275 }