复习总结资料(数据结构导论)
《数据结构导论》复习资料
课程代码：02142
一、单项选择题
1．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是A．不确定 B．n-i+1 C．i D．n-i
2．具有N个结点的二叉树的二叉链表结构中，指针域为NULL的数目应为
A． N B．2N C．N+1 D．2N+1
3．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?
A．(E、D、C、B、A、F) B．(B、C、E、F、A、D)
C．(C、B、E、D、A、F) D．(A、D、F、E、B、C)
4．已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？A．s->next = p； p-> next = s； B．s-> next = p->next； p-> next = s；
C．s-> next = p-> next； p = s； D． p-> next = s； s-> next = p；
5．设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是
A．head->next==head B．head->next==NULL
C．head!=NULL D．head==NULL
6．一个队列的输入序列是A，B，C，D，则该队列的输出序列是
A．A，B，C，D B．B，C，D，A
C．D，C，B，A D．C，D，B，A
7．以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是
A．100 B．108 C．114 D．116
8．二叉树的中序遍历序列中，结点P排在结点Q之前的条件是
A．在二叉树中P在Q的左边B．在二叉树中P在Q的右边
C．在二叉树中P是Q的祖先D．在二叉树中P是Q的子孙
9．有10个顶点的无向完全图的边数是
A．11 B．45 C．55 D．90
10．在带权有向图中求两个结点之间的最短路径可以采用的算法是
A．迪杰斯特拉（Dijkstra）算法B．克鲁斯卡尔（Kruskal）算法
C．普里姆（Prim）算法D．深度优先搜索（DFS）算法
11．利用双向链表作线性表的存储结构的优点是
A．便于单向进行插入和删除的操作B．便于双向进行插入和删除的操作
C．节省空间D．便于销毁结构释放空间
12．在闭散列表中，散列到同一个地址而引起的“堆积”问题是引起的。
A．同义词之间发生冲突 B．非同义词之间发生冲突
C．同义词之间或非同义词之间发生冲突D．散列表“溢出”
13．假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为
A．front+1==rear B．rear+1==front
C．front==0 D．front==rear
14．10阶上三角矩阵压缩存储时需存储的元素个数为
A．11 B．56 C．100 D．101
15．深度为k（k≥1）的二叉树，结点数最多有
A．2k个 B．(2k -1)个 C．2k-1个 D．(2k+1)个16．具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为
A．11 B．13 C．23 D．25
17．顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为A．20000 B．30000 C．40000 D．60000 18．外存储器的主要特点是
A．容量小和存取速度低B．容量大和存取速度低
C．容量大和存取速度高D．容量小和存取速度高
19．以下关于广义表的叙述中,正确的是
A．广义表是由0个或多个单元素或子表构成的有限序列
B．广义表至少有一个元素是子表
C．广义表不能递归定义
D．广义表不能为空表
20．树形结构中，度为0的结点称为
A．树根 B．叶子C．路径 D．二叉树
21．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7
C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V7
22．有关图中路径的定义，表述正确的是
A．路径是顶点和相邻顶点偶对构成的边所形成的序列
B．路径是不同顶点所形成的序列
C．路径是不同边所形成的序列
D．路径是不同顶点和不同边所形成的集合
23．组成数据的基本单位是
A．数据项 B．数据类型C．数据元素 D．数据变量24．与串的逻辑结构不同的
．．．数据结构是
A．线性表 B．栈C．队列 D．树
25．设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为
A．p->next=p->next->next B．p=p->next
C．p=p->next->next D．p->next=p
26．设字符串S1=″ABCDEFG″，S2=″PQRST″，则运算
S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的结果为
A．″BCQR″ B．″BCDEF″C．″BCDEFG″ D．″BCDEFEF″
27．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为
A．LL型 B．LR型C．RL型 D．RR型
28．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？
A．堆排序 B．直接插入排序 C．快速排序 D．冒泡排序29．下面关于串的叙述中，是不正确的。
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储30．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是
A．edcba B． decba C．dceab D．Abcde
31．有向图中，所有顶点入度和是所有顶点出度和的倍。
A．0.5 B．1 C． 2 D．4
32．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行
A．q->next=p->next; p->next=q; B．p->next=q->next; q=p;
C．p->next=p->next; q->next=q; D．p->next=q->next; q->nxet=p;
33．下列描述中正确的是
A．数据元素是数据的最小单位
B．数据结构是具有结构的数据对象
C．数据结构是指相互之间存在一种或多种特定关系的数据元素的集合
D．算法和程序原则上没有区别，在讨论数据结构时两者是通用的
34．归并排序的时间复杂度是
A．O（n2） B．O（nlog2n） C．O（n） D．O（log2n）
35．顺序存储的表中有90000个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为A．25000 B．30000 C．45000 D．90000
36．散列文件是一种
A．顺序文件 B．索引文件 C．链接文件 D．计算寻址文件37．常用于函数调用的数据结构是
A．栈 B．队列 C．链表 D．数组
38．二维数组A［n］［m］以列优先顺序存储，数组A中每个元素占用1个字节，A［1］［1］为首元素，其地址为0，则元素A［i］［j］的地址为
A．（i-1）×m+(j-1) B．(j-1)×n+(i-1)
C．(j-1)×n+i D．j×n+i
39．序列（21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为A．(19，21，37，5，2) B．(21，19，5，37，2)
C．(21，19，37，2，5) D．(2，21，19，37，5)
40．数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为
A．索引存储方法B．顺序存储方法
C．链式存储方法D．散列存储方法
41．在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的
A．直接前趋 B．直接后继 C．开始结点 D．终端结点42．一整数序列26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为
A．31，51，11，42，26，77，59，19 B．26，59，31，77，11，51，19，42
C．11，19，26，31，42，59，51，77 D．26，11，19，31，51，59，77，42
43．某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为
A．acbed B．becab C．deabc D．cedba
44．在一个图中，所有顶点的度数之和与图的边数的比是
A．1∶2 B．1∶1 C．2∶1 D．4∶1
45．含有n个结点的二叉树用二叉链表表示时，空指针域个数为
A．n-1 B．n C．n+1 D．n+2
参考答案：
1-5 BCCBA 6-10 ACABA 11-15 BADBB 16-20 BBBAB 21-25 AACDA
26-30 DBDBC 31-35 BDCBC 36-40 DABAD 41-45 BBDCC
二、填空题
46．有个10阶矩阵A，采用行序优先存储，每个元素占用1个字节的存储空间，A[0][0]的地址为1，则A[8][5]的地址为：。
47．广义表(a,(a,b),d,e,((i,j),k))的长度是。
48．若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=key MOD 9，与18发生冲突的元素有个。
49．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为。
50．常用的存储表示方法有顺序存储和链式存储，其中存储表示方法插入和删除数据元素方便。
51．栈的特点是。
52．所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是。
53．单链表中指针p指向结点A，若要删除A之后的结点（存在且不释放存储空间），则需要修改指针的操作为p->next= 。
54．在带有头结点的单链表head中，首结点的指针为。
55．在栈结构中，允许插入和删除的一端称为。
56．C程序中，将对称矩阵A［n］［n］的下三角元素压缩存储到n(n+1)/2个元素的一维数组M 中，设a［i］［j］（i≥j）存放在数组M［k］中，则k的值（用i,j表示）为。57．具有64个结点的完全二叉树的深度为。
58．某二叉树的先序遍历序列为AJKLMNO，中序遍历序列为JLKANMO，则根结点A的右子树中的结点个数为。
59．在顺序查找、二分查找、散列查找和索引顺序查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是。
60．堆排序算法的时间复杂度为。
61．如果要将序列{60，18，28，69，99，75，78}建成堆，则只需把60与相互交换。
62．数据的不可分割的最小标识单位是，它通常不具有完整确定的实际意义，或不被当作一个整体对待。
63．运算分为加工型运算和引用型运算，读取操作是运算。
64．带有头结点的单向循环链表L（L为头指针）中，指针p所指结点为尾结点的条件
是。
65．在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句。
66．元素s1，s2，s3，s4，s5，s6依次进入顺序栈S，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为。
67．在一棵树中，结点没有双亲。
68．边稀疏的无向图采用存储较省空间。
69．要将序列{51，18，23，68，94，70，73}建成堆，则只需把18与相互交换。
70．一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有
个。
71．若连通图G的顶点个数为n，则图G的生成树的边数为。
72．一个具有n个顶点的无向图的边数最多为。
73．中根遍历二叉排序树所得到的结点访问序列是键值的序列。
74．冒泡排序的平均时间复杂度为。
75．将序列(60，20，23，68，94，70，73)建成堆，则只需把20与互相交换。
76．向一个长度为n的顺序表中第i（1≤i≤n）个元素之前插入一个元素时，需向后移动_ _ 个元素。
77．在循环双链表中，删除最后一个结点，其算法的时间复杂度为。
78．队列的插入操作在队列的部分进行。
79．一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素
为。
80．一个10阶对称矩阵A，采用行优先顺序压缩存储下三角，a00为第一个元素，其存储地址为
1，每个元素占有1个存储地址空间，则a85的地址为。
81．设字符串S=″I□AM□A□STUDENT″（其中□表示空格字符），则S的长度为___ 。
82．在树形结构中，没有后继的结点是结点。
83．在无向图中，如果从顶点v到顶点v′有路径，则称v和v′是。
84．无向完全图G采用存储结构较省空间。
参考答案：
46. 86 47.5 48.2
49. 98 50.链式 51.先进后出
52. 顺序存储方式 53. p->next->next 54. head->next
55. 栈顶56.（i+1）i/2+j 57.7
58. 3 59.散列查找60.O（nlog2n）
61. 18 62.数据项63.引用型
64. p->next= =L 65. p= p->next->next 66.3
67. 根68.邻接表69.51
70.n-1 71.n-1 72. n(n-1)/2
73.递增74. O（n2）75.60
76. n-i+1 77. O（1）78. 队尾（或尾部）
79.n-i-1 80.42 81.14
82.叶子83.连通84.邻接矩阵
三、应用题
85．将下图所示的一棵树转换为对应的二叉树。
题1图
86．将下图所示的一棵二叉树转换成对应的森林。
87．写出下图的邻接矩阵和每个顶点的入度与出度。
88．用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。
89．如下图所示，在栈的输入端元素的输入顺序为A，B，C，D，进栈过程中可以退栈，写出在栈的输出端以A开头和以B开头的所有输出序列。
90．一棵二叉树如下图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。
91．将下图所示的一棵二叉树转换成森林。
92．对于有向无环图：
对于下图，写出它的4个不同的拓扑排序序列。
93．稀疏矩阵A 如下，写出矩阵A 的三元组表。
???????
?????????0 0 0 0 0 3-0 4 0 0 0 00 0 0 0 1- 50 0 0 0 0 01 0 0 0 3 0 94．一棵二叉树的前根遍历序列为ABCDEFG ，中根遍历序列为CBDAEGF ，试构造出该二叉树。
95．下述矩阵表示一个无向连通网，试画出它所表示的连通网。
???????
?????????∞∞∞∞∞∞∞∞∞ 4 2 104 9 52 8 12 9 8 110 5 12 1 96．给定表（80，90，50，70，75，60，40，100），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。
97．试写出一组键值（46，58，15，45，90，18，10，62）应用直接插入排序算法从小到大排序后各趟的结果。
98．在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push （x ）表示x 进栈，pop(x)表示x 退栈）
99．如下图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A 为起点的深度优先搜索顶点序列。
参考答案：
85．答：
86．答：
87．答：
88．答：
89．答：
ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA; 90．答：
先根遍历序列：ABDEGCFH
中根遍历序列：DBGEACHF
后根遍历序列：DGEBHFCA
91．答：
92．答：它的4个拓扑排序序列为：
12347856,13247856,13427856,13524786；
93．答：
94．答：
95．答：
96．答：
97．答：
98．答：
能排成序列：3,2,5,6,4,1；
过程：push(1); push(2); push(3); pop(3); pop(2); push(4); push(5); pop(5); push(6); pop(6); pop(4) ;pop(1)；
不能产生1，5，4，6，2，3，因为2,3进栈，出栈就不能是2,3。
99．答：
四、算法设计题
100．带头结点的单链表的结点结构如下：
typedef struct node
{ int data;
struct node *next;
}Node,*LinkList;
试编写单链表的删除运算算法void DeleteLinklist( LinkList head，int i)
101．n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素A[1]至A[n]中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。
102．试写出冒泡排序算法。
103．试分别写出二叉树的先根遍历和中根遍历的递归算法。
104．试编写以单链表为存储结构实现直接选择排序的算法。
105．编写计算二叉树中叶子结点数目的算法。
参考答案：
100．答：
101．答：
102．答：
103．答：
104．答：
105．