耿国华数据结构附录样卷答案
附录A 样卷一
一、判断题：（10 分）
正确在括号内打√，错误打×
( ) 1.在单链表中，头结点是必不可少的。
（）2．如果一个二叉树中没有度为1的结点，则必为满二叉树。
( ) 3. 循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。 ( ) 4. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 ( ) 5. 在一个大根堆中，最小元素不一定在最后。
( ) 6. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。
（）7. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。
（）8. 内部排序是指排序过程在内存中进行的排序。
（）9. 拓扑排序是指结点的值是有序排列。
( )10. AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。
二、选择题(30分, 每题1.5分)
1．有一个含头结点的单链表，头指针为head, 则判断其是否为空的条件为：
________________
A． head=NIL B. head^.next=NIL C. head^.next=head D. head<>NIL 或 A． head==NULL B. Head->next==NULL C. head->next==head D. Head!=NULL 2．非空的循环单链表head的尾指针p满足______________。
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．链表不具有的特点是。
A、可随机访问任一个元素
B、插入删除不需要移动元素
C、不必事先估计存储空间
D、所需空间与线性表的长度成正比
4．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省运算时间。
A、单链表
B、双链表
C、单循环链表
D、带头结点的双循环链表
5．若线性表最常用的操作是存取第i个元素及其前驱的值，则采用存储方式节省时间。
A、单链表
B、双链表
C、单循环链表
D、顺序表
6．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能的是。
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，则队列的输出序列是。
A、4，3，2，1
B、1，2，3，4
C、1，4，3，2
D、3，2，4，1 8．设循环队列中数组的下标范围是1~n，其头尾指针分别为f，r，若队列中元素个数
为。
A、r-f B 、r-f+1 C、（r-f+1）mod n D、（r-f+n）mod n
9．串是。
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的结点的左孩子的编号为。
A、98
B、99
C、50
D、48
12．对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用实现编号。
A、先序遍历
B、中序遍历
C、后序遍历
D、从根开始进行层次遍历
13．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二叉树。
A、空或只有一个结点
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无右孩子
14．在有n个叶子结点的哈夫曼树中，其结点总数为。
A、不确定
B、2n
C、2n+1
D、2n-1
15．一个有n个顶点的无向图最多有条边。
A、n
B、n（n-1）
C、n（n-1）/2
D、2n
16．任何一个无向连通图的最小生成树。
A、只有一棵
B、有一棵或多棵
C、一定有多棵
D、可能不存在
17．一组记录的关键字为（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
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）=K MOD P（P〈=M〉, 为使函数具有较好性能，P应选
11．单链表与多重链表的区别是
12．深度为6（根层次为1）的二叉树至多有个结点。
13．已知二维数组A[0..20][0..10]采用行序为主方式存储，每个元素占4个存储单元,并且A[0][0]的存储地址是1016, 则A[10][5]的存储地址是
14．循环单链表La中，指针P所指结点为表尾结点的条件是
15．在查找方法中，平均查找长度与结点个数无关的查找方法是。
16．队列的特性是
17．具有3个结点的二叉树有种
18．已知一棵二叉树的前序序列为ABDFCE，中序序列为DFBACE，后序序列为
19．已知一个图的邻接矩阵表示，要删除所有从第i个结点出发的边，在邻接矩阵运算是
四、构造题：（30 分）
1．已知关键字序列为：（75, 33, 52, 41, 12, 88, 66, 27）哈希表长为10，哈希函数为：
H(k)=K MOD 7, 解决冲突用线性探测再散列法，构造哈希表，求等概率下查找成功的平均
查找长度。
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是否对称。
对称是指：设各元素值a1,a2,...,a n, 则有a i=a n-i+1
即指：a1= a n，a2= a n-1 。。。。。。
结点结构为
数据结构附录B 样卷二
一、简答题（15分，每小题3分）
1.简要说明算法与程序的区别。
2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？
3.说明在图的遍历中，设置访问标志数组的作用。
4.说明以下三个概念的关系：头指针，头结点，首元素结点。
5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？
二、判断题（10分，每小题1分）
正确在括号内打√，错误打×
( )（1）广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。
( )（2）在哈夫曼树中，权值最小的结点离根结点最近。
( )（3）基数排序是高位优先排序法。
( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。
( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p 的后面：p->next = s; s->next = p->next;
( )（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。
( )（7）数组元素的下标值越大，存取时间越长。
( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。
( )（10）长度为1的串等价于一个字符型常量。
三、单项选择题（10分, 每小题1分）
1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？
A、堆排序
B、直接插入排序
C、快速排序
D、冒泡排序
2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：
A）将邻接矩阵的第i行删除 B）将邻接矩阵的第i行元素全部置为0
C）将邻接矩阵的第i列删除 D）将邻接矩阵的第i列元素全部置为0
3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是：
A. head->priro==NULL
B. head->next==NULL
C. head->next==head
D. head->next-> priro==NULL
4. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为：
A) 2 B) 3 C) 4 D) 5
5. 以下哪一个不是队列的基本运算？
A）从队尾插入一个新元素 B）从队列中删除第i个元素
C）判断一个队列是否为空 D）读取队头元素的值
6. 在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：
A) n – i + 1 B) n – i C) i D) i – 1 7．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为:
A) 顺序表 B) 用头指针表示的循环单链表
C) 用尾指针表示的循环单链表 D) 单链表
8．对包含n个元素的哈希表进行查找，平均查找长度为：
A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依赖于n
9．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：
A、48
B、49
C、50
D、51
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 [ low ]；
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．通常是以算法执行所耗费的和所占用的来判断一个算法的优劣。4．已知一个3行、4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序
存储，则排在第8个位置的元素是：
5．高度为h的完全二叉树最少有个结点。
五、构造题（20 分）
1．（4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。
DS = (D, R)
D = { 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 }，要求给出哈夫曼树，并计算其带权路径长度WPL。
六、算法分析题（10分）
阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。（1）简要说明程序功能。（5分）
（2）n个结点的满二叉树的深度h是多少？（3分）
（3）假设二叉排序树*bst是有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， 4 312 5 N+1 6 S->next=P->next P->next=S 7 路径递增8 Log(2)(N) 9中序10 97 11 链域个数不同12 63 13 1476 14 P->next=head 15 散列查找16 先进先出17 5 18 FDBECA 19将矩阵第i行全部置0
四，构造题
1，
计算函数值
(1)哈希表（4分，每对1个0.5分）
(2)比较次数（3分）
ASL=(1+2+1+2+4+1+7+5)/8=23/8
5，(1)
(2) ASL=(1+2*2+4*3+1*4)/8=21/8=2.62
《数据结构》附录B 样卷二 参考答案
一、简答题（15分，每小题3分） 6. 算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。 7. 主要与哈希函数、装填因子α有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子α较小，则哈希表较稀疏，发生冲突的可能性较小。 8. 图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。 9. 头指针指向头结点，头结点的后继域指向首元素结点。 10. 当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。 二、判断题（10分，每小题1分）
（1）(√) （2）(×) （3）(×) （4）(√) （5）(×) （6）(√) （7）(×) （8）(√) （9）(×) （10）(×) 三、单项选择题（10分, 每小题1分）
1． D ） 2． B ） 3． C ） 4. C ） 5. B ） 6. A) 7． C) 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． 2h-1
五、构造题（20 分） 1．（4分）
2．（6分）
ASL succ = ( 1×4 + 2×2 + 3 ) / 7 = 11 / 7 3.（6分）
4．（4分）已知权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL 。
WPL = 2×( 9 + 6 + 7 ) + 3×5 + 4×( 2 + 3 ) = 79
六、算法分析题（10分）
解： （1） 在二叉排序树中插入关键字为K 的结点
SUN MON THU FRI WED
TUE
SAT
0 1 2 3 4 5 6 7
8 9
（2）h = log2 ( n+1 ) 或 h = [ log2 n ] + 1 （方括号表示向下取整）（3）O ( log2 ( n+1 ) ) 或 O ( log2 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 ■
数据结构习题答案 耿国华主编 第六章
6.27 [问题] 假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。[解答] [问题] 假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。 [问题] 试利用栈的基本操作写出先序遍历二叉树的非递归算法。 [解答提示] 改写教材p.130-131算法6.2或6.3。 将if (!visit(p->data)) return ERROR;提前。 6.43 [问题] 编写递归算法，将二叉树中所有结点的左、右子树相互交换。 Status Exchange-lr(Bitree bt){ //将bt所指二叉树中所有结点的左、右子树相互交换
if (bt && (bt->lchild || bt->rchild)) { bt->lchild<->bt->rchild; Exchange-lr(bt->lchild); Exchange-lr(bt->rchild); } return OK; }//Exchange-lr 6.45 [问题] 编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 [解答] Status Del-subtree(Bitree bt){ //删除bt所指二叉树，并释放相应的空间 if (bt) { Del-subtree(bt->lchild); Del-subtree(bt->rchild); free(bt); } return OK; }//Del-subtree Status Search-del(Bitree bt, TelemType x){ //在bt所指的二叉树中，查找所有元素值为x的结点，并删除以它为根的子树 if (bt){ if (bt->data=x) Del-subtree(bt); else { Search-Del(bt->lchild, x); Search-Del(bt->rchild, x); } } return OK; }//Search-Del 第六章树和二叉树 6.33 int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0 { if(u==v) return 1; else { if(L[v]) if (Is_Descendant(u,L[v])) return 1; if(R[v]) if (Is_Descendant(u,R[v])) return 1; //这是个递归算法
最全数据结构课后习题答案耿国华版
绪论第1章 √(2)×(3)2.(1)×C ）C（3（1）A（2）3. 的语句频度5.计算下列程序中x=x+1for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 的语句频度为：【解答】x=x+1=n(n+1)(n+2)/6 ）+……+（1+2+……+n）T(n)=1+(1+2)+（1+2+3 并确定算法中每一),p(xx+ax+a+…….+ax的值6.编写算法，求一元多项式p(x)=a n20nn20n1规定算法中不能使用要求时间复杂度尽可能小，语句的执行次数和整个算法的时间复杂度，算法的输入和输出)。n,输出为P(x求幂函数。注意：本题中的输入为a(i=0,1,…n)、x和0in采用下列方法1）通过参数表中的参数显式传递（）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实（2 现输入输出。【解答】1）通过参数表中的参数显式传递（优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用 性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。 ）通过全局变量隐式传递（2 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数PolyValue() { int i,n; float x,a[],p; nn=”);printf(“\ scanf(“%f”,&n); nx=”);printf(“\ scanf(“%f”,&x); for(i=0;i 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 北京师范大学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 中有弧 第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 东华理工大学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 第一章习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型 （5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作 （9）有限性、输入、可行性 4、（1）A（2）C（3）C 5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定 （4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A B：H、L、I、E、A C：F、M D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下： int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)； return(0); } while(i<=L->last&&L->elem[i] L->last++; return(1); } 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2)) { printf(“输入的i，k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 注意事项： 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. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 第一章绪论 1.数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。 2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据元素的组成：一个数据元素通常由一个或若干数据项组成。 数据项：指具有独立含义的最小标识单位。 3.数据对象：性质相同的数据元素的集合，是数据的一个子集。 4.数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所定义的算法在计算机上运行的学科。 5.算法：是对待定问题求解步骤的一种描述，是指令的有限序列。算法应满足以下性质： 1)输入性：具有零个或若干个输入量； 2)输出性：至少产生一个输出； 3)有穷性：每条指令的执行次数是有限的； 4)确定性：每条指令的含义明确，无二义性； 5)可行性：每条指令都应在有限的时间内完成。 6.评价算法优劣的主要指标： 1)执行算法后，计算机运行所消耗的时间，即所需的机器时间； 2)执行算法时，计算机所占存储量的大小，即所需的存储空间； 3)所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。 7.会估算某一算法的总执行时间和时间复杂度。 8.熟悉习题P32:3(5)-(9)、4(2)(3) 第二章线性表 1.线性表(P7)：是性质相同的一组数据元素序列。 线性表的特性： 1)数据元素在线性表中是连续的，表中数据元素的个数可以增加或减少，但调整后数据元素仍必须是连续的，即线性表是一种线性结构。 2)数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。 3)线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。 线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。 线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元，这种存储方法叫做顺序分配，又称顺序映像。其特点：逻辑上相邻的数据元素， 它们的物理次序也是相邻的。)，存储地址的计算方式(Loc(a i )=Loc(a )+i*s)。 2.线性表的查找、插入和删除 熟悉线性表的查找算法(P38)、插入算法(P39)和删除算法(P40)。 3.理解线性表的顺序存储结构的优缺点。 4.熟悉线性链表的存储结构(P43) 线性链表(由若干结点链接而成的一种存储结构。)、结点(由存放数据元素值的部分—数据域和存放另一元素存储地址的部分—指针域或链域两部分信息组成的存储结构。)、单链表(线性链表)的概念。 5.熟悉线性链表的建立(P45-47)、查找(P47-48)、插入(P49-50)和删除(P50-51)的算法； 6.明了什么是循环链表(链表中最后一个结点指针域回指向链表的第一个结点，使得整个链表通过链指针成为一个环形，这种形式的链表称为循环链表。)？ 7.明了双向链表的结构(链表中的每个结点有两个指针域，一个是向前链接的左指针(Lnext或prior)，另一个是向后链接的右指针(Rnext或next)，同时还有一个数据域(Data)。)；了解双向链表的插入和删除的算法。 8.理解链表的优缺点(P48)。 9.熟悉习题P68：1、2 第三章限定性线性表----栈和队列 1.栈和队列 明确什么是栈及其特点(只允许在一端进行插入和删除的线性表。允许插入和删除 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 学期样卷一 二、1.B 2.D 3.C 4.D 5.D 6.(2^h-1) 7.B 8.B 9.B 10.D 三、1.（n-1）(n-2)/2 2.p->next=la 3. 6 4.矩阵的第i个结点所在行全置为0. 5.冒泡排序 6.top[1]+1=top[2] 7. 4 2 8. 1308 9. 97 四、wpl=16*2+8*3+9*3+(4+5)*4+12*3+26*2=32+51+36+36+52=207 2. 4棵树 3. 6 1 1 1 2 3 4 ASLsucc=(1+1+2+1+3+4+6)/7=18/7 ASLunsucc=(2+1+2+1+1+7+6)/7=20/7 五、1.按层遍历二叉树 2.n次 3 O（n） 六、1 void split(LinkList*la,LinkList*&lb,LinkList*&lc) { LinkList *p=la->next,*q; lc=(LinkList*)malloc(Sizeof(LinkList)); lb=la; while(p!=NULL) { if(p->data>0) { q=p; p=p->next; q->next=lb->next; lb->next=p; } else { q=p; p=p->next; q->next=lc->next; lc->next=p; } } } 2略 参考教材：统计并输出叶子结点数目P168 分析：统计二叉树中非终端结点的数目并无次序要求，可用三种遍历算法中的任何一种完成，只需将访问操作具体变为判断是否为非终端结点及统计操作即可。 以先序遍历的算法如下： //count为保存统计非终端结点数目的全局变量，调用前初始化为0 void CounUntleaf(BiTree root) { if(root!=NULL) { if(root->lchild!=NULL)||(root->rchild!=NULL) { Count++; printf(root->data); } CountUnleaf(root->lchild); CountUnleaf(root->rchild); } } 学期样卷二 二、1D 2A 3D 4C 5A 6C 7C 8C 9B 10A 三、1 s->next=p->next p->next=s 2 2^(h-1)+1 2^h-1 3 入4 简单选择排序 5 1344 6 q->rchild q=q->rchild pre 四、1数据结构模拟试题及答案
数据结构试卷-A+答案
最全数据结构课后习题答案(耿国华版[12bb]
耿国华数据结构习题答案完整版
数据结构复习题附答案
数据结构试卷及答案90325
(完整版)数据结构---C语言描述-(耿国华)-课后习题答案
《数据结构》期末考试题及答案
数据结构试卷及答案
数据结构模拟卷(含答案)经典习题培训讲学
《数据结构(C语言-耿国华版)》复习大纲
数据结构模拟卷(含答案)经典习题
数据结构学期样卷答案
- 10-11第一学期数据结构试卷A-答案
- 数据结构试卷及答案
- 数据结构期末试卷及答案
- 数据结构学期样卷一
- 华师大数据结构期中考试试卷(含答案)
- 10-11第一学期数据结构试卷 - B卷答案
- 数据结构试卷与答案
- 数据结构试卷及答案6
- 数据结构期中考试试卷答案
- 《数据结构》期末考试试题及答案
- 《数据结构》试卷及答案
- 数据结构试卷及答案90325
- 11-12-数据结构试卷-A+答案
- (完整版)数据结构考试试题(带答案)
- 淮阴工学院数据结构期末试卷及答案(1)
- 数据结构试卷及答案
- 广东海洋大学数据结构试卷及答案
- 数据结构学期样卷答案
- 2010上学期数据结构试卷 答案
- 09-10第二学期数据结构试卷B-答案