附录A 样卷一
一.判断题：(10分)
正确在括号内打错谋打X
()1?在单链表中，头结点是必不可少的。
()2.如果一个二叉树中没有度为1的结点，则必为满二叉树。
()3.循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。()4?顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。()5.在一个大根堆中，最小元素不一定在最厉。
()6.在一个有向图屮，所有顶点的入度之和等于所有顶点的出度之和。
()7.在采用线性探测法处理冲突的散列表屮，所有同义词在表屮相邻。
()&内部排序是指排序过程在内存中进行的排序。
()9.拓扑排序是指结点的值是有序排列。
()10. A0E网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。
一?、选择题(30分，每题1?5分)
1.有一个含头结点的单链表，头指针为head,则判断其是否为空的条件为:
A.head=NIL
B. head*. next=NIL
C. head*. next=head
D. headONIL 或A.head~NULL B. Head->next~NULL C. head->nex t==head D.Head!=NULL
2.非空的循环单?链表head的尾指针p满足
一0
A.p) next二NIL
B. p=NIL
C. p\ next=head D? p=head
或A.p->next=NULL B. p==NULL C. P->next=head D.p=head
3.链表不具有的特点是o
A.可随机访问任一个元素B、插入删除不需要移动元素
C.不必事先估计存储空间
D.所需空间与线性表的长度成正比
4.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则
釆用_______ 存储方式最节省运算时间。
A、单链表
B、双链表
C、单循环链表D.带头结点的
双循环链表
5.若线性表最帘用的操作是存取第i个元索及其前驱的值，则采用 _____ 存储方式节省时间。
A、单链表
B、双链表
C、单循环链表
D、顺序
表
6.设一个栈的输入序列为A, B, C, D,则借助一个栈所得到的输岀序列不可能的是_____ o
A、A, B> C> D B D,C,B,A
C、A, C, D, B D D,A,B,C
7. 一个队列的入队序列是1, 2,3, 4,则队列的输出序列是O
A. 4, 3, 2, 11, 2, 3, 4 C、4,3,2D、3, 2, 4,
8.设循环队列中数组的下标范围是Pn,其头尾指针分别为f, r,若队列中元素个数为O
A. r-f B r-f+1 C、(r-f+l)mod n D. (r-f+n) mod n
9.串是 ______ o
A、不少于一个字母的序列
B、任意个字母的序列
C、不少于一个字符的序列
D、有限个字符的序列
10.数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中.则A[5, 5]的地址是_______ 。
A. 1140 B、1145 C、1120 D、1125
11.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号为49的结点的左孩了的编号为 _______ o
A. 98 B、99 C、50 D、48
12.朮二叉树从1开始编号，要求每个结点的编号人于其左右孩子的编号，同一个结点的左右孩子中，其左孩了的编号小于其右孩子的编号，则可采用________ 实现编号。
A、先序遍历
B、中序遍历
C、后序遍历 D.从根开始进行层次遍历
13.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_______ 的二叉树。
A.空或只有一个结点
B.高度等于其结点数
C>任一结点无左孩子 D.任一结点无右孩子
14.在有n个叶了结点的哈夫曼树中，其结点总数为_______ o
A.不确定Bx 2n C. 2n+l D、2nT
15.一个有n个顶点的无向图最多有______ 条边。
A> n B> n (nT) C^ n (nT) /2 D. 2n
16.任何一个无向连通图的最小生成树_______ o
A.只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在
17.一组记录的关键字为(46, 79, 56, 38, 40, 84),利用快速排序的方法，以第一个
记录为基准得到的一次划分结果为_______ o
A. 38,40,46,56,79, 84
B、40,38,46,79,56, 84
C> 40,38,46,56,79, 84
D、40,38,46,84,56, 79
18.已知数据表A中每个元素距其最终位置不远，则釆用______ 排序算法最节省时间。
A、堆排序B>插入排序C、快速排序D、直接选择排序
19.下列排序算法中，_______ 算法可能会出现下血情况：初始数据有序时，花费时间反而最多。
A、堆排序
B、冒泡排序
C、快速排序 D. SHELL排序
20.对于键值序列(12, 13, 11, 18, 60, 15, 7, 18, 25, 100),用筛选法建堆，必须
从键值为_______ 的结点开始。
A、100
B、60
C、12
D、15
三、填空题(40分)
1在顺序表(即顺序存储结构的线性表)屮插入一个元索，需要平均动 _______ 个元索.
2.快速排序的最坏悄况，其待排序的初始排列是__________________________ .
3.为防止在图中走回，应设立____________________________ .
4.一个栈的输入序列为123,写出不可能是栈的输出序更_________________ 。
5.N个结点的二叉树，采用二叉链表存放，空链域的个数为_________ ?
6.要在一个单链表中p所指结点之后插入s所指结点时，
应执行__________________ 和_____________________ 的操作.
7.Dijkstra算法是按__________________ 的次序产生一点到其余各顶点最短路径的算法.
8.在N个结点完全二叉树中，其深度是_____________________
9. ______________________ 对二叉排序树进行遍历，可得到结点的有序排列.
10.设一哈希表表长M为100 ,用除留余数法构造哈希函数，即H (K)二KMODP (P
<=M> ,
为使函数具有较好性能，P应选____________________
11?单链表与多重链表的区别是_________________
12.深度为6 (根层次为1)的二叉树至多有________________ 个结点。
13.已知-■?维数组A[0.. 20] [0.. 10]采用行序为主方式存储，每个元素占4个存储单元,并
且A[0] [0]的存储地址是1016,则A[10] [5]的存储地址是 ___________
14.循环单链表3中，指针P所指结点为表尾结点的条件是______________
15.在查找方法屮，平均查找长度与结点个数无关的查找方法是_____________ o
16.队列的特性是_________________
17.具有3个结点的二叉树有_________ 种
18.已知一棵一.叉树的前序序列为ABDFCE,屮序序列为DFBACE,后序序列为___________
19.已知一个图的邻接矩阵表示，要删除所自从第i个结点出发的边，在邻接矩阵运算是
四、构造题：(30分)
1.已知关键字序列为：(75, 33, 52, 41, 12, 8& 66, 27)哈希表长为10,哈希函数为：
H(k)=K MOD 7,解决冲突用线性探测再散列法，构造哈希表，求等概率下竇找成功的平均查找长度。
E 1
2.已知无向图如图1所示，
(1)给出图的邻接表。
(2)从A开始，给出一棵广度优先生成树。
3.给定叶结点权值：(1, 3, 5, 6, 7, 8),构造哈夫曼树，并计算其带权路径长度。
4.从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树:
（24, 88, 42, 97, 22, 15, 7, 13）□
5.对长度为8的有序表，给出折半賁找的判定树，给出等概率情况下的平均査找长度。
6.已知一棵树如图2所示，要求将该树转化为二叉树。
五.算法设计题（40分）
［算法题可用类PASCAL或类C语言■每题20分］
1.已知一棵二叉树采用二叉链表存放，写一算法，要求统计出二叉树中叶子结点个数并
输出二叉树中非终端结点（输岀无顺序要求）。
2.编写算法.判断带头结点的双循环链表L是否对称。对称是指：设各元索值a h a n,则有
a i=a n-i*i
即指：&!=3n> fl2= fln-l .
结点结构为
数据结构附录B样卷二
一.简答题（15分，每小题3分）
1.简要说明算法与程序的区别。
2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？
3.说明在图的遍历屮，设置访问标志数组的作用。
4.说明以下三个概念的关系：头指针，头结点，首元素结点。
5.在一般的顺序队列中.什么是假溢出？怎样解决假溢出问题？
二、判断题（10分，每小题1分）
正确在括号内打错谋打X
（）（1）广义表（（（a ）, b）, c ）的表头是（（a ）, b）,表尾是（c ）o
（）（2）在哈夫曼树屮，权值最小的结点离根结点最近。
（）（3）基数排序是高位优先排序法。
（）（4）在平衡二叉树屮，任意结点左右子树的高度建（绝对值）不超过1。
（）（5）在单链表中，给定任一结点的地址p,则可用下述语句将新结点s插入结点p 的后面:p->next = s; s->next = p-〉next;
（）（6）抽彖数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。
（）（7）数组元素的下标值越大，存取时间越长。
（）（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
（）（9）拓扑排序是按A0E网中每个结点事件的最早发生时间对结点进行排序。
（）（10）长度为1的串等价于一个字符型常杲。
三、单项选择题（10分，每小题1分）
1.排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基木思想？
A.堆排序
B.直接插入排序
C.快速排序
D.冒泡排序
2. 已知一个有向图的邻接矩阵表示，要删除所有从第i 个结点发出的边，应该: A)将邻接矩阵的第i 行删除 B)将邻接矩阵的第i 行元索全部置为0 O 将邻接矩阵的第i 列删除 D)将邻接矩阵的第i 列元素全部腔为0
3. 有一个含头结点的双向循环链表，头指针为head,処其为空的条件是：
B. head->next==NULL D. head -〉next-〉 priro==NULL 16, 1& 21, 25, 30 )中，用折半法杏找关键码 D) 5 5. 以下哪一个不是队列的基木运算？ A)从队尾插入一个新元素 B)从队列中删除第i 个元素 C)判断一个队列是否为空 D)读取队头元素的值
6. 在长度为n 的顺序表的第i 个位置上插入一个元索(1W i Wn+1),元索的移动次数为: A) n ? i + 1 B) n - i C) i D) i - 1
7. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为： A)顺序表 B)用头指针表示的循环单链表 O 用尾指针表示的循环单链表 D)单链表
8. 对包含n 个元素的哈希表进行査找，平均查找长度为： A) 0(log 2n) B) 0(n) C) O(nlogm) D)不直接依赖于 n
9. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点
进行编号，根结点编号为1,则编号最大的非叶结点的编号为：
10. 某二叉树结点的中序序列为A. B 、C 、D 、E 、F 、G,后序序列为B. D 、C. A. F 、G. E, 则其左子树中结点数日为： A) 3 B) 2 C) 4 D) 5 四. 填空题(10分，每空1分)
1. 填空完成下血一趙快速排序算法： int QKPass ( RecordType r [ ], int low, int high)
{ x = r T low 1：
while ( low < high )
{
while ( low < high && r [ _______ ]. key >= x. key )
high --- ；
if ( low < high )
{ r [ _______ ] = r [ high ]； low++; } while ( low < high && r [ _______ ]. key < x. key ) low++;
if ( low < high )
{ r [ _______ ] = r [ low ]； high —; } }
r [ low ] = x ； return low ;
}
2. 假没用循环单链表实现队列，若队列非空，且队尾指针为R,则将新结点S 加入队列时,
需执行下面语句： _________________ ； ________________ ； R=S ；
3. _________________________________ 通常是以算法执行所耗费的 和所占用的 来判断一个
A. head->pr i ro==NULL
C ? head->next=head
4?在顺序表(3, 6, & 10, 12, 15, 值11,所需的关键码比较次数为： A) 2 B) 3 C) 4 A 、48 B. 49 C 、 50
算法的优劣。
4.已知一个3行.4列的二维数组A (各维下标均从1开始)，如果按“以列为主”的顺序
存储，则排在第8个位置的元素是：___________
5. ________________________________________ 高度为h的完全二叉树最少有个结点。
五.构造题（20分）
1.（4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。
DS = （D, R）
0 = { a, b, c, d, e, f, g }
R = { T }
T = {
2.（6分）对以下关键字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT），哈希函数为H（K） = （K中最厉一个字母在字母表屮的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因了为0. 7的哈希表，并计算出在等概率情况下資找成功的平均資找长度。
3.（6分）将关键字序列（3, 26, 12, 61, 38, 40, 97, 75, 53, 87）调整为人根堆。
4.（4分）已知权值集合为:{5, 7, 2, 3, 6, 9},要求给出哈夫曼树，并计算其带权路径长度WPLo
六、算法分析题（10分）
阅读下面程序，并冋答有关问题。其中BSTree为用一?叉链表表示的一?叉排序树类型。（1）简要说明程序功能。（5分）
（2）n个结点的满二叉树的深度h是多儿？（3分）
（3）假设二叉排序树祐$亡是有n个结点的满一?叉树，给出算法的时间复杂度。（2分）int Proc （BSTree *bst, KeyType K）
{ BSTree f, q, s;
s=(BSTree)malloc(sizeof(BSTNode));
s-> key = K; s-> lchild = NULL; s-> rchild = NULL;
if ( *bst = NULL ) { *bst = s; return 1; } f = NULL; q = *bst;
while( q != NULL )
{ if ( K < q -> key )
{ f = q； q = q -〉lchild： }
else
{ f = q; q = q -> rchild; }
}
if ( K < f -> key ) f -> lchild = s;
else f -> rchild = s;
return 1;
)
七、算法设计题(25分)
1.己知一个带头结点的幣数单链表L,要求将其拆分为一个正敝数单链表L1和一个负鞭数单链表L2。(9分)
2.无向图采用邻接表存储结构，编写算法输出图中各连通分武的结点序列。（8分）
3.编写一个建立二叉树的算法，要求采用二叉链表存储结构。（8分）
数据结构附录A样卷?参考答案
1表长的?半2排好序列3, ___ J 312 5N+1 6 S?>ne：a=：P?>M)d P?>n￡)d=S 7路径递增8 T QQ(2)(Z)<)中序10 97 II 链域个数不同12 63 H 1476 14 P?》wghwul 15 fife
列査找16先进先出17 5 18 FDBECA 19将炬阵第i行全部置0
四，构造题
哈希表分.每对个分)
比较次数分)
5, (1)
(2) ASL=(1 +2?2+4*3+1 *4 )/8=21/8=2.62
《数拡结构》附录B样卷「：参考答案
一、简容题（15分，毎小题3分）
6.算法是解决特定问题的操作序列.可以用多种方式描述。程序是算法在计算机屮的实现，与具体的计算机语言有关。
7.主要与哈希函数、装填因子□有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小. 如果装填因子a较小.则哈希农较稀疏，发生冲突的可能性较小。
8.图中结点可能有多个前驱，设置访问标志数组主要是为了避免用复访问同一个结点。
9.头指针指向头结点.头结点的后继域指向首元索结点.
10?当队尾到达数组最后一个单元时，就认为队满?但此时数组前面可能还有空单元，因此叫假溢出. 解决的方法是采用循环队列，即令最后-个单元的后继是第?个单元。
二、判析题（10分，毎小题1分）
(1)(V)(2)（X）（3）（X）⑷(V)(5)（X
(6)3)(7)(X) (8) (V) (9)（X(10)（X
三.单项选择题（10夕毎小题1分）
1. D)
2.B)
3. C)
4. C)
5.B)
6. A)
7.0
8. D)
9. C)10.C)
四.填空题（10分，毎空1分〉
1.high low low high
2.S->next=R->next ；R->next=S :
3.时间空间4? A [2, 3] 5?
2卜1
五
、.构适题（20分）
1.（4分）
2. (6 分)
0 I 23456789
SUN MON THU FRI WED TUE SAT
ASUc = ( 1X4 + 2X2 + 3)/7 = 11/7
3. (6 分)
4?（4分）己知权值集合为：{ 5, 7, 2, 3. 6. 9 },要求给出哈夫曼树，并计算其带权路径长度WPL。
WPL = 2X( 9 + 6 + 7 ) + 3X5 + 4X( 2 + 3 ) = 79
六、算法分析题（10分）
斛：
（1）在二叉排序树屮插入关键字为K的结点
(2)h = log： ( n+1 ) 或h = [ log： n ] + 1 (方括号农示向下取整)
(3)0 ( log： ( n+1 ))或0( log： n )
《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■
《数据结构》期末考试试卷样卷 成绩＿＿＿＿＿＿＿＿ 一、单项选择题：（每题2分，共30分） 1、以下说法正确的是（）。 A. 数据元素是数据的最小单位 B. 数据项是数据的基本单位 C. 数据结构是带有结构的各数据项的集合 D. 一些表面上很不相同的数据可以有相同的逻辑结构 2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A. 存储结构 B. 存储实现 C. 逻辑结构 D. 运算实现 3、判断一个队列QU（最多元素为m0）为满队的条件是（）。 A. QU->rear-QU->front==m0 B. QU->rear-QU->front-1==m0 C. QU->rear==QU->front D. QU->front==QU->rear+1 4、给定n个数据元素，建立对应的有序单链表的时间复杂度是（）。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 5、一个非空广义表的表头（）。 A. 不可能是子表 B. 只能是子表 C. 原子或子表均可 D. 只能是原子 6、设完全二叉树中拥有65 个结点，则其深度为（）。 A. 5 B. 6 C. 7 D. 8 7、根据二叉树的（），可以唯一确定该二叉树的形态。 A. 先序和中序序列 B. 先序和后序序列 C. 中序和后序序列 D. 先序和层序序列 8、若广义表A满足Head(A)=Tail(A)，则A为（）。 A. () B. (()) C. ((),()) D. ((),(),()) 9、下面不正确的说法是（）。 (1)在AOE网中，减少任一关键活动上的权值后，整个工期也就相应减小； (2)AOE网工程的工期为关键活动上的权值之和； (3)在关键路径上的活动都是关键活动，而关键活动也必定在关键路径上。 A. (1) B. (2) C. (3) D. (1) 、(2) 10、图的深度优先遍历算法分别类似于二叉树的（）。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 11、从图的邻接矩阵中，容易确定（）。 A. 主对角线的元素全部为1 B. 主对角线的元素不全为0 C. 任意两个顶点之间是否关联 D. 是否为一个连通图 12、顺序查找适用于存储结构为（）的线性表。 A. 散列存储 B. 压缩存储 C. 顺序存储或链式存储 D. 索引存储 13、从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为（）。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 14、在关键字随机分布的情况下，用二叉排序树进行查找，其查找长度与（）量级相当。 A. 顺序查找 B. 折半查找 C. 分块查找 D. 均不是 15、一组记录的关键字序列为{46,79,56,38,40,84}，利用快速排序方法，以第一个记录为基准得到的一次划分是（）。 A. 38,40,46,56,79,84 B. 40,38,46,79,56,84 C. 40,38,46,56,79,84 D. 40,38,46,84,56,79 - 1 -
北京师范大学2011～2012学年第 1 学期期末考试试卷（A 卷） 课程名称： 数据结构 任课教师姓名： 刘玉铭 卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）： 数学科学学院 专 业： 年级： 2010 姓 名： 学 号： 阅卷教师（签字）： 一、 单项选择题（每题2分，共10题20分） 1．以下那一个术语与数据的存储结构无关？ 。 A ．栈 B ．哈希表 C ．线索树 D ．双向链表 2．链表不具有的特点是 。 A ．插入、删除不需要移动元素 B ．可随机访问任一元素 C ．不必事先估计存储空间 D ．所需空间与线性表长度成正比 3．算术表达式a+b*（c+d/e ）转为后缀表达式后为 。 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．abcde*/++ 4．二维数组A[10][20]采用列优先的存储方法,若每个元素占2个存储单元，设A[0][0]的地址为100，则元素A[7][6]的存储地址为 。 A ．232 B ．234 C ．390 D ．392 装 订 线
5．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是。 A．9 B．11 C．15 D．不确定 6．一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB 7．在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是。 A．G 中有弧
2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系 时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是 ___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插 入元素的时间复杂度为____________。 5. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ， 则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6. 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的 总和是_____________。 8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表 达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。
考场： 座位号： 专业名称： 装订线 装订线 装订线 广州大学华软软件学院第 20XX-20XX 学年第 X 学期考试卷 课程代码： SS1005 课程名称： 数据结构与算法 考试时间： 90 分钟 考试形式： 闭卷 试卷类型： A 学分： 4 一、 单项选择题（共15小题，每小题2分，共30分）在每小题列出的 选项中只有一个选项符合题目要求，将正确选项前的字母填写在答题纸上。 1. 数据三种最主要的逻辑结构是树形结构和（ ）。 A. 线性表、二叉树 B. 线性结构、图状结构 C. 线性表、图 D. 树形结构、堆 2. 以下数据结构中，（ ）是线性数据结构。 A ．树 B ．图 C ．堆 D ．栈 3. 下面关于线性表的叙述中，错误的是哪一个？（ ） A ．若线性表采用顺序存储结构，则必须占用一片连续的存储单元。 B ．若线性表采用顺序存储结构，则便于进行插入和删除操作。 C ．若线性表采用链接存储结构，则不必占用一片连续的存储单元。 D ．若线性表采用链接存储结构，则便于插入和删除操作。 4. p 是指向单链表头结点的指针，若该链表是空表，下面正确的说法是( )。 A. p = = NULL B. p != NULL C. p->next = =NULL D. p->next = =NULL
5.在指针p指向单链表结点之后插入s所指结点的操作是：（）。 A．p->next=s; B．s->next=p->next ;p->next=s; C．s->next=p; D．s->next=p->next; 6.存取数据时采用先进先出的原则的数据结构是（）。 A.队列 B.栈 C.字符串 D.线性表 7.假定栈用单链表的存储结构表示，栈的栈顶指针为top，当结点x入栈时执行的 操作为( )。 A.x->next=top; B. top->next=x; top=x; C. top=x; D. x->next=top; top=x; 8.队列的数据出队操作在（）进行。 A.队尾位置 B.队头位置 C. 任意位置 D. 中间位置 9.树的度是指（）。 A.树的结点数 B.树的后继个数 C. 树中任一结点最大的后继数 D. 以上都不是 10.具有8个叶子结点的二叉树中有（）个双支结点。 A．7 B．8 C．9 D．10 11.下面对完全二叉树描述正确的是（）。 A.所有层的结点数都必须是满的 B.除最后一层，其它层上的结点数都必须 是满的 C.最后一层的结点数不能是满的 D.以上都不是 12.将100个元素散列到10000个单元的散列表中，则（）产生冲突。 A.一定会 B. 一定不会 C. 仍可能会 13.假定利用数组a表示一个栈，用top 保存栈顶位置，top=-1表示栈空，已知栈 中有数据，当元素x进栈时的操作为（）。 A.a[--top]=x; B.a[top--]=x; C. a[++top]=x; D. a[top++]=x; 14.n个顶点的无向图，至多有（）条边。 A．n-l B．n(n-1)/2 C．n(n+l) D．2n 15.无向图G=(V,E),其中：V={a,b,c,d }, E={(a,b), (a,c),(b,d),(c,d)}，对该 图进行广度优先遍历，得到的顶点序列正确的是（）。 A．a,c,b,d B．a,d,c,b C．a,c,d,b D．a,b,d,c 第 2 页共4 页
东华理工大学2015 —2016学年第 一 学期考试 模拟试卷 A 一、 填空题（50分） 1、数据结构是一门研究非数值计算的程序设计问题中的 数据元素 以及它们之间 关系 和运算等的科学。（2分） 2、数据结构的类型通常分为： 集合、线性结构、树形结构、图状结构或网状结构 ；从逻辑上可以把它们分成： 线性结构和非线性结构 。 3、数据的 逻辑结构 只抽象反映数据元素的 逻辑关系 ；数据的 存储（物理）结构 是数据的逻辑结构 在计算机存储器中的实现 。 4、算法分析的目的是分析算法的 效率以求改进 ，算法分析的两个主要方面是 空间复杂度和时间复杂度 。 A 5、计算机算法是解决问题的 有限运算序列 ，它必须具备 输入、输出、确定性、有穷性和稳定性 等5个方面的特性。 6、线性结构中元素之间的关系存在 一对一 关系，树形结构中元素之间的关系存在 一对多 关系，图形结构中元素之间的关系存在 多对多 关系。 7、试写出以下算法的时间复杂度 i=s=0 while (s i = i*2 O(log2n) 8、抽象数据类型的定义由三元组来定义：(D,S,P)其中，D是数据对象， S是D上的关系集，P是对D的基本操作集。 9、写出抽象数据类型线性表的定义 ADT List{ 数据对象：D={ai | ai ∈Elemset, i=1,2,…,n,n≥0} 数据关系：R={< ai-1 , ai> | ai-1 , ai ∈D, i=2,…,n} 基本操作： InitList(&L) //构造一个空的线性表L DestroyList(&L) //消毁线性表L ListLength(L) //返回L中数据元素的个数 ListInsert(&L,i,e) // 1 ≤ i ≤ ListLength(L)+1,在L中第i个位置之前插入数据元素e,L长度加1 ListDelete(&L,i,&e) // 1 ≤ i ≤ ListLength(L),删除L中的第i个元素，并用e 返回 ListTraverse(L,visit()) //依次对L的每个元素调用函数visit() ………… } ADT List 10、指出线性表顺序存储、链式存储结构的优缺点。 答：顺序存储优点：逻辑上相邻，物理位置也相邻，可以随机存取表中任一元素；缺点：插入和删除元素时需要移动大量元素。 链式存储结构优点：插入、删除元素时不需要移动元素；缺点：逻辑上相邻，物理位置不一定相邻，不能随机存取表中元素，需要依次查找，求线性表的长度时不如顺序存储结构方便，需要逐个结点搜索计算，或设置带头结点的线性链表。 11、完成下列在单链表中删除元素算法 Status ListDelete_L(LinkList &L, int i, ElemType &e){ //删除第i个元素e p = L; j =0; //p指向头结点 while(p->next && j 1. 下面程序段的执行次数为（ A ） for(i=0;i＜n-1;i++) for(j=n;j＞i;j--) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2) 2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （ B ）A. 110 B .108 C. 100 D. 120 3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前 队列中的元素个数是（ D ） A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6．在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（ B） 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; 7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均 比较多少个结点（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28．从一个栈顶指针为HS 的链栈中删除一个结点时，用x保存被删结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表，其特殊性体现在( B ) A. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字 符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的 范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存 储时下列哪一元素的起始地址相同( B ) A. M[2][4] B .M[3][4] C. M[3][5] D. M[4][4] 12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10， 从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为 ( C )A. SA+144 B .SA+180 C. SA+222 D. SA+225 数据结构辅导试题一 一、简答问题： 1．四类数据结构 2．线性结构与非线性结构有何差别？ 3．简述算法的定义与特性。 4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？ 二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打 。1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值， 若它的右子树非空，则根结点的值大于其右孩子的值。 2．（）索引顺序表的特点是块内可无序，块间要有序。 3．（）子串是主串中任意个连续字符组成的序列。 4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 5．（）快速排序的枢轴元素可以任意选定。 三、单项选择题：(每小题1分，共4分) 1．栈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 2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A、98 B、99 C、50 D、48 3. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是： A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9} B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30} 4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： A）M1 B）M1+M2 C）M3 D）M2+M3 四、填空题：(每小题2分,共 20分) 1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选 2．N个结点的二叉树采用二叉链表存放，共有空链域个数为 3．单链表与多重链表的区别是 4．在各种查找方法中，平均查找长度与结点个数无关的是 5．深度为6（根层次为1）的二叉树至多有个结点。 6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 7．在一个单链表中p所指结点之后插入s所指结点时,应执行 s->next= 和p->next= 的操作. 8．广义表((a,b),c,d)的表头是,表尾是 9．循环单链表LA中，指针P所指结点为表尾结点的条件是 10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。 五、构造题：（每小题5分，共25分） 1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散 注意事项： 1、下面关于串的叙述中，哪一个是不正确的？（ ） A ．串是字符的有限序列 B ．空串是由空格构成的串 C ．模式匹配是串的一种重要运算 D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．0 3、以下数据结构中，（ ）是非线性数据结构。 A ．树 B ．字符串 C ．队列 D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ） A ．线性表采用顺序存储，必须占用一片连续的存储单元。 B ．线性表采用顺序存储，便于进行插入和删除操作。 C ．线性表采用链接存储，不必占用一片连续的存储单元。 D ．线性表采用链接存储，便于插入和删除操作。 5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。 A ．(rear-front+m)%m B ．rear-front+1 C ．(front-rear+m)%m D ．(rear-front)%m 6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。 A ．p->next=s; s->next=p->next; B ．s->next=p->next; p->next=s; C ．p->next=s; p->next=s->next; D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A ．1，2，4，3 B ．2，1，3，4 C ．1，4，3，2 D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。 A ．a 和(b,c),d,e B ．（a ）和(b,c),d,e C ．a 和 ((b,c)，d,e) D ．(a) 和((b,c)，d,e) 9、栈和队都是（ ） A ．顺序存储的线性结构 B ．链式存储的非线性结构 C ．限制存取点的线性结构 D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。 A ．动态结构、静态结构 B ．顺序结构、链式结构 C ．线性结构、非线性结构 D ．初等结构、构造型结构 11、下列四个序列中，哪一个是堆（ ）。 A ．75,65,30,15,25,45,20,10 B ．75,65,45,10,30,25,20,15 C ．75,45,65,30,15,25,20,10 D ．75,45,65,10,25,30,20,15 12、在下述结论中，正确的是（ ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K 的完全二叉树结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 13、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A ．9 B ．11 C ．15 D ．不确定 14、设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。 与森林F 对应的二叉树根结点的右子树上的结点个数是（ ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 15、在下面的程序段中，对x 的赋值语句的频度为（ ）。 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A ． O(2n) B ．O(n) C ．O(n 2) D ．O(log2n) 16、一个n 个顶点的连通无向图，其边的个数至少为（ ）。 A ．n-1 B ．n C ．n+1 D ．nlogn ； 17、二叉树的第I 层上最多含有结点数为（ ） A ．2I B ． 2I-1-1 C ． 2I-1 D ．2I -1 18、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A ．选择 B ．冒泡 C ．归并 D ．堆 19、二维数组A 的元素都是6个字符组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10。若A 按行存放，元素A[8，5]的起始地址与A 按列存放时的元素（ ）的起始地址一致。 A ．A[8,5] B ． A[3,10] C ． A[5,8] D ． A[0,9] 20、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（ ）方法是散列文件的关键。 A ．散列函数 B ．除余法中的质数 C ．冲突处理 D ．散列函数和冲突处理 期末考试《数据结构》A 卷 一、单项选择题（请将正确答案的字母填写在每题对应的括号内，每小题1分，共20分） 姓名:________ 学号:__________ 年级:______________ 专业:_____________ …….……………………….密…………………封…………………线………………………… 1. 下面程序段的执行次数为（A ） for(i=0;i＜n-1;i++) for(j=n;j＞i;j--) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2) 2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ） A. 110 B .108 C. 100 D. 120 3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ D ） A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6．在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（B） 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; 7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28．从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表，其特殊性体现在( B ) A. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时下列哪一元素的起始地址相同( B ) A. M[2][4] B .M[3][4] C. M[3][5] D. M[4][4] 12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为( C )A. SA+144 B .SA+180 C. SA+222 D. SA+225 13. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：( B )A. 2h B .2h-1 C. 2h+1 D. h+1 14. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ( D )A. acbed B .decab C. deabc D. cedba 15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确( A )A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的 二叉树的中序遍历序列相同 D. 以上都不对16. 具有6个顶点的无向图至少应有多少条边才能确保是一个连通图 ( A )A. 5 B .6 C. 7 D. 8 17. 顺序查找法适合于存储结构为( B )的线性表 A. 散列存储B .顺序存储或链接存储C. 压缩存储 D. 索引存储 18.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为( C )A. n B .n2 C. (n+1)2 D. (n-1)2 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构 D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答：C。 9. 以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80, 77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20} 数据结构试题B卷 一、单选题（每小题2分，共8分） 1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )。 A n B n/2 C (n+1)/2 D (n-1)/2 2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。 A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 3、栈的插入和删除操作在（）进行。 A 栈顶 B 栈底 C 任意位置 D 指定位置 4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（） A 24 B 71 C 48 D 53 二、填空题（每空1分，共32分） 1、数据的逻辑结构被分为__________、___________ 、________和________四种。 2、一种抽象数据类型包括______________和_____________两个部分。 3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________ a 0 1 2 3 4 5 6 7 8 next 4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。 5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。 6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。 7、一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点； 一棵高度为5的理想平衡树中，最少含有_________个结点，最多含有_________个结点。 8、在图的邻接表中，每个结点被称为____________，通常它包含三个域：一是_____________；二是___________；三是_____________。 9、在一个索引文件的索引表中，每个索引项包含对应记录的_________和___________两项数据。 10、假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为_________个，树的深度为_________,树的度为________, 结点H的双亲结点为________,孩子结点为 _______________ 。武汉大学数据结构考试题(附答案)
数据结构考试试题
数据结构试卷及答案
武汉大学数据结构考试试题(附答案) (2)
《数据结构》期末考试试卷
数据结构期末考试试题含答案
数据结构试卷B试题
相关主题
文本预览