最新《数据结构》习题汇编08-第八章-查找-试题
数据结构课程（本科）第七章试题
一、单项选择题
1.若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为
（）。
A. n
B. n+1
C. (n-1)/2
D. (n+1)/2
2.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概
率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（）。
A. 5.5
B. 5
C. 39/8
D. 19/4
3.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索
第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（）。
A. 5/3
B. 2
C. 7/3
D. 4/3
4.对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度
为（）。
A. n/2
B. (n+1)/2
C. (n-1)/2
D. n/4
5.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值
的向上取整。
A. log2(n+1)
B. log2n
C. n/2
D. (n+1)/2
6.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值
的向下取整加一。
A. log2(n+1)
B. log2n
C. n/2
D. (n+1)/2
7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）
的值除以9。
A. 20
B. 18
C. 25
D. 22
8.对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（）。
A. 3
B. 4
C. 5
D. 6
9.对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（）。
A. O(n)
B. O(n2)
C. O(1)
D. O(log2n)
10.在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（）。
A. n
B. log2n
C. (h+1)/2
D. h+1
11.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为
（）。
A. O(n)
B. O(1)
C. O(log2n)
D. O(n2)
12.从具有n个结点的二叉搜索树中搜索一个元素时，在最坏情况下进行成功搜索的时间复杂度为
（）。
A. O(n)
B. O(1)
C. O(log2n)
D. O(n2)
13.向具有n个结点的二叉搜索树中插入一个元素时，其时间复杂度大致为（）。
A. O(1)
B. O(log2n )
C. O(n)
D. O(n log2n)
14.在一棵A VL树（高度平衡的二叉搜索树）中，每个结点的平衡因子的取值范围是（）。
A. -1～1
B. -2～2
C. 1～2
D. 0～1
15.向一棵A VL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的调整过程，此调
整分为（）种旋转类型。
A. 2
B. 3
C. 4
D. 5
16.向一棵A VL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的左单或右单旋转
的调整过程，此时需要修改相关（）个结点指针域的值。
A. 2
B. 3
C. 4
D. 5
17.向一棵A VL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的双向旋转的调整
过程，此时需要修改相关（）个结点指针域的值。
A. 2
B. 3
C. 4
D. 5
参考答案： 1. D 2. C 3. A 4. B 5. A
6. B
7. C
8. A
9. D 10. D
11. C 12. A 13. B 14. A 15. C
16. A 17. C
二、填空题
1.以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为________。
2.对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为p i，搜索长度（即在搜索过程中依次
同有关元素比较的总次数）为c i，则在搜索成功情况下的平均搜索长度的计算公式为________。
3.假定一个顺序表的长度为40，并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长
度为________。
4.以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为________。
5.从有序表(12, 18, 30, 43, 56, 78, 82, 95) 中折半搜索元素56时，其搜索长度为________。
6.假定对长度n = 50的有序表进行折半搜索，则对应的判定树中最后一层的结点数为______个。
7. 从一棵二叉搜索树中搜索一个元素时，若给定值小于根结点的值，则需要向________继续搜索。
8. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向________继续搜索。
9. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值小于根结点的值，则应把它插入到根结点的
________上。
10. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值大于根结点的值，则应把它插入到根结点的
________上。
11. 向一棵二叉搜索树________一个元素时，若查找到的根结点为空值，则应把该元素结点链接到这个空
指针位置上。
12. 根据n 个元素建立一棵二叉搜索树的时间复杂度性大致为_____________。
13. 在一棵AVL 树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不
超过________。
14. 根据一组记录 ( 56, 42, 50, 64, 48 ) 依次插入结点生成一棵AVL 树（高度平衡的二叉搜索树）时，当
插入到值为_______的结点时需要进行旋转调整。
15. 根据一组记录 ( 56, 74, 63, 64, 48 ) 依次插入结点生成一棵A VL 树（高度平衡的二叉搜索树）时，当
插入到值为63的结点时需要进行________________调整。
16. 根据一组记录 ( 56, 42, 38, 64, 48 ) 依次插入结点生成一棵A VL 树（高度平衡的二叉搜索树）时，当
插入到值为38的结点时需要进行____________调整。
17. 根据一组记录 ( 56, 42, 73, 50, 64, 48, 22 ) 依次插入结点生成一棵AVL 树（高度平衡的二叉搜索树）
时，当插入到值为_______的结点时才出现不平衡，需要进行旋转调整。
18. 在一棵A VL 树（高度平衡的二叉搜索树）上进行插入或删除元素时，所需的时间复杂度为_________。
参考答案： 1. O(n)
2.
∑-=10
n i i
i c
p 3. 20.5 4. O(log 2n) 5. 3 6. 19
7. 左子树 8. 右子树 9. 左子树 10. 右子树 11. 插入
12. O(nlog 2n)
13. 1
14. 50
15. 先右后左双旋转 16. 右单旋转
17. 48
18. O(lon 2n)
三、判断题
1. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，
则可得到最小的平均搜索长度。
2.进行折半搜索的表必须是顺序存储的有序表。
3.能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。
4.假定用两个有序单链表表示两个集合，则这两个集合交运算得到的集合单链表，其长度小于参加运算
的任一个集合单链表的长度。
5.假定用两个有序单链表表示两个集合，则这两个集合的差运算得到的集合单链表，其长度小于参加运
算的任一个集合单链表的长度。
6.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树（它的特点是除最底层结
点外其他各层结点数都是满的，最底层的若干结点可能散布在该层各处）。
7.对二叉搜索树进行前序遍历得到的结点序列是一个有序序列。
8.在由n个元素组成的有序表上进行折半搜索时，对任一个元素进行搜索的长度（即比较次数）都不会
大于log2n+1。
9.根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(log2n)。
10.根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(nlog2n)。
11.对于同一组记录，若生成二叉搜索树时插入记录的次序不同则得到不同结构的二叉搜索树。
12.对于同一组记录，生成二叉搜索树的结构与插入记录的次序无关。
13.对于两棵具有相同记录集合而具有不同结构的二叉搜索树，按中序遍历得到的结点序列是相同的。
14.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优
二叉搜索树。
15.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优
二叉搜索树。
参考答案： 1. 是 2. 是 3. 否 4. 是 5. 否
6. 是
7. 否
8. 是
9. 否10. 是
11. 是12. 否13. 是14. 是15. 否
四、运算题
1.一个一维数组a[10]中存储着一个有序表，该有序表为：(15, 26, 34, 39, 45, 56, 58, 63, 74, 76 )，根据折
半搜索所对应的判定树，写出该判定树的广义表表示，并求出在等概率情况下搜索成功的平均搜索长度。
判定树的广义表表示：_______________________________ 平均搜索长度：_________________
2. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半
搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。
元素值 比较次数
3. 假定一个线性序列为 ( 38, 52, 25, 74, 68, 16, 30, 54, 90, 72 )，根据此线性序列中元素的排列次序生成一
棵二叉搜索树，求出对该二叉搜索树查找38, 74, 68, 30, 72等元素时的比较次数。
待查元素： 比较次数：
4. 假定一个线性序列为 ( 56, 27, 34, 95, 73, 16, 50, 62, 65 )，根据此线性序列中元素的排列次序生成一棵
二叉搜索树，求出该二叉搜索树的高度（假定树根结点的高度为0）、度为2的结点个数和叶子结点个数。
高度：_____________
度为2的结点个数：____________ 叶子结点个数：____________
5. 假定一个线性序列为 ( 38, 42, 55, 15, 23, 44, 30, 74, 48, 26 )，根据此线性序列中元素的排列次序生成一
棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点和右子树为空的所有单支结点，请按从小到大的次序排列写出。
左子树为空的所有结点：____________ 右子树为空的所有结点：____________
6. 已知一棵二叉搜索树的广义表表示为：28 (12 ( , 16), 49 (34 (30), 72 (63) ) )，按主教材介绍的删除算法，
求出从中依次删除72, 12, 49, 28结点后得到的二叉搜索树的广义表表示。
广义表表示：_____________________________
7. 假定一组数据对象为 ( 40, 28, 16, 56, 50, 32, 30, 63 )，按次序插入每个对象生成一棵A VL 树（高度平
衡的二叉搜索树），根据插入过程填写下表，在相应位置填写所需要的调整类型：“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，若不需要旋转则填写“无”。
数据： 调整：
8. 假定一组数据对象为 ( 40, 28, 16, 56, 50, 32, 30, 63, 44, 38 )，按次序插入每个对象生成一棵A VL 树（高
度平衡的二叉搜索树），请回答插入后需调整的结点个数和插入后不调整的结点个数。 34 56 58 63 94 38 74 68 30 72 40 28 16 56 50 32 30 63
插入时伴随旋转调整的结点个数：___________ 插入不调整的结点个数：__________
9. 假定一组记录为 ( 36, 75, 83, 54, 12, 67, 60, 40 )，按次序插入每个结点生成一棵A VL 树（高度平衡的
二叉搜索树），请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少？
左单旋转结点个数：____________ 右单旋转结点个数：____________
先左后右双旋转结点个数：___________ 先右后左双旋转结点个数：___________ 不调整结点个数：____________
10. 假定一组记录为 ( 38, 42, 55, 15, 23, 44, 30, 74, 48, 26 )，按次序插入每个结点生成一棵A VL 树（高度
平衡的二叉搜索树），给出最后得到的A VL 树中度为2、度为1和度为0的结点个数。
度为2的结点个数：__________ 度为1的结点个数：__________ 度为0的结点个数：__________
参考答案：
1. 判定树的广义表表示：45 (26 (15, 34 ( , 39 ) ), 63 ( 56 ( , 58 ), 74 ( , 76 ) ) )
//4分 平均查找长度：29/10
//2分
2. 判断结果
元素值 比较次数
//对1个给1分，全对给6分
3. 判断结果
待查元素： 比较次数：
//对1个给1分，全对给6分
4. 高度：4
//2分 度为2的结点个数：2 //2分 叶子结点个数：3 //2分
5. 左子树为空的结点：15, 23, 42, 44
//全对4分，否则不得分 右子树为空的结点：30
//2分
6. 广义表表示：30 (16 , 63 (34) )
7. 插入结果和调整类型为 34 56 58 63 94
02 1 3 4 4 38 74 68 30 72 01 3 4 3 5
插入数据：
调整类型：
8. 插入时伴随旋转调整的结点个数：4 //3分，若误差1给1分，其余情况不得分
插入不调整的结点个数：6 //3分，若误差1给1分，其余情况不得分
9. 左单旋转结点个数：1 //1分
右单旋转结点个数：0 //1分 先左后右双旋转结点个数：1 //1分 先右后左双旋转结点个数：0 //1分 不调整结点个数：6 //2分
10. 度为2的结点个数：4 //2分
度为1的结点个数：1 //2分 度为0的结点个数：5 //2分
五、算法分析题
1. 已知二叉搜索树中的结点类型用BinTreeNode 表示，被定义为:
struct BinTreeNode { ElemType data ; BinTreeNode *leftChild , *rightChild ; };
其中data 为结点值域，leftChild 和rightChild 分别为指向左、右子女结点的指针域。假定具有BinTreeNode*类型的指针参数BST 指向一棵二叉搜索树的根结点，试根据下面的函数定义指出此算法所能实现的功能。
ElemType unknown ( BinTreeNode* BST ) {
if ( BST == NULL ) { cerr << "此树为空树" << endl; exit (1); } BinTreeNode* t = BST ;
while ( t ->rightChild != NULL ) t = t ->rightChild ; return t ->data ; }
算法功能：______________________________________________________
2. 假定p1和p2是两个有序单链表的表头指针，用来表示两个集合，单链表中的结点包括值域data 和指
向后继结点的指针域link ，试根据下面算法指出算法功能。 LinkNode* unknown ( LinkNode* p1, LinkNode* p2 ) {
LinkNode* p3 = new LinkNode , * p = p3;
while ( p1 != NULL && p2 != NULL ) { LinkNode* newptr = new LinkNode ; 40 28 16 56 50 32 30 63 无 无 右单旋 无 先右后左 先右后左 无 左单旋 双旋转 双旋转
if ( p1->data < p2->data )
{ newptr->data = p1->data; p1 = p1->link; }
else if ( p1->data > p2->data )
{ newptr->data = p2->data; p2 = p2->link; }
else { newptr->data = p1->data; p1 = p1->link; p2 = p2->link; }
p3->link = newptr; p3 = newptr;
}
if ( p2 != NULL ) p1 = p2;
while (p1 != NULL ) {
p3 = p3->link = new LinkNode;
p3->data = p1->data; p1 = p1->link;
}
p3->link = NULL;
return p->link;
}
算法功能：______________________________________________________
3.假定p1和p2是两个单链表的表头指针，用来表示两个集合，单链表中的结点包括值域data和指向后
继结点的指针域link，试根据下面算法指出算法功能。
int unknown ( LinkNode* p1, LinkNode* p2 ) {
while ( p2 != NULL ) {
LinkNode* r = p1;
while ( r != NULL ) {
if ( p2->data == r->data ) break;
r = r->link;
}
if ( r == NULL ) return 0;
p2 = p2->link;
}
return 1;
}
算法功能：______________________________________________________
4.假定HL为保存一个集合的有序单链表的表头指针，item为一个新元素，HL单链表中的结点包括值域
data和指向后继结点的指针域link，试根据下面算法指出算法功能。
void unknown ( LinkNode *& HL, const ElemType& item ) {
LinkNode* newptr;
Newptr = new LinkNode;
Newptr->data = item;
if ( HL == NULL || item < HL->data ) {
newptr->link = HL;
HL = newptr;
return;
}
LinkNode *cp, *ap;
ap = HL; cp = HL->link;
while (cp != NULL ) {
if ( item < cp->data ) break;
ap = cp;cp = cp->link;
}
newptr->link = cp;
ap->link = newptr;
}
算法功能：______________________________________________________
5.已知二叉搜索树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data;BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定pt所指向的二叉搜索树的广义表表示为: 25 (10 (5, 16 (12) ), 40 (32 ( , 38) ) )，按照下面算法，则：
(1) 执行unknown ( pt, 40 ) 调用后返回的值为________。
(2) 执行unknown ( pt, 38 ) 调用后返回的值为________。
(1) 执行unknown ( pt, 5 ) 调用后返回的值为________。
(1) 执行unknown ( pt, 60 ) 调用后返回的值为________。
int unknown ( BinTreeNode* t, ElemType x ) {
if ( t == NULL ) return 0;
else if ( t->data == x ) return 1;
else if ( t->data > x )
return 1+unknown ( t->leftChild, x );
else
return 1+unknown ( t->rightChild, x );
}
6.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data;BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定具有BinTreeNode * 类型的指针参数bt指向一棵二叉树的根结点，引用参数x初始具有最小值（即小于树中所有结点的值），试根据下面的函数定义指出此算法所能实现的功能。
int unknown ( BinTreeNode* bt, ElemType& x ) {
if ( bt == NULL ) return 1;
else {
if (unknown ( bt->leftChild, x ) == 0 ) return 0;
if ( bt->data < x ) return 0;
x = bt->data;
if (unknown ( bt->rightChild, x ) == 0 ) return 0;
else return 1;
}
}
算法功能：______________________________________________________
参考答案：
1.算法功能：从二叉搜索树BST中查找出具有最大值的结点并返回这个值。
2.算法功能：实现集合的并运算，即把有序单链表表示的两个集合合并为一个新的集合，并由函数返回
新集合的表头指针。
3.算法功能：判断p2单链表所代表的集合是否为p1单链表所代表的集合的子集合，若是则返回1否则
返回0。
4.算法功能：向表示集合的有序单链表HL中插入一个新元素，使得插入后仍然保持集合单链表有序。
5.(1) 2 //2分
(2) 4 //2分
(3) 3 //2分
(4) 0 //2分
6.算法功能：判断二叉树bt是否为一棵二叉搜索树，若是则返回1否则返回0。
六、算法设计题
1.假定元素类型为ElemType的一维数组R[n] 中保存着按关键码升序排列的n个对象，对象的关键码域
key的类型为KeyType，试按照下面的函数声明编写一个非递归算法，从一维数组R[n]中用折半搜索法找出关键码等于k的对象，若搜索成功则返回对象位置（即元素下标），否则返回-1。
int BinSearch ( ElemType R[ ], int n, KeyType k );
2.已知二叉搜索树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data;BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定具有BinTreeNode * 类型的指针参数BST指向一棵二叉搜索树的根结点，试根据下面的函数声明编写一个非递归算法，从BST树中查找出具有x参数值的结点，若查找成功则返回该结点的地址，否则返回NULL。
BinTreeNode* Find ( BinTreeNode* BST, ElemType& x );
3.已知二叉搜索树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data;BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定具有BinTreeNode * 类型的指针参数BST指向一棵二叉搜索树的根结点，试根据下面的函数声明编写一个递归算法，向BST树中插入值为x的结点，若树中不存在x结点则进行插入并返回1表示插入成功，若树中已存在x结点则不插入并返回0表示插入失败。
int Insert ( BinTreeNode *& BST, const ElemType& x );
4.已知二叉搜索树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data;BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定具有BinTreeNode * 类型的指针参数BST指向一棵二叉搜索树的根结点，试根据下面的函数声明编写一个非递归算法，向BST树中插入值为x的结点，若树中不存在x结点则进行插入并返回1表示插入成功，若树中已存在x结点则不插入并返回0表示插入失败。
int insert ( BinTreeNode*& BST, const ElemType& x );
参考答案：
1.算法如下：
int BinSearch ( ElemType R[ ], int n, KeyType k ) {
int low = 0, high = n-1;//赋初值2分
while ( low <= high ) { //循环条件1分
int mid = (low + high) / 2;//中点位置1分
if ( k == R[mid].key ) return mid;//成功返回1分
else if ( k < R[mid].key) high = mid-1;//向左半区查找1分
else low = mid+1;//向右半区查找1分}
return-1;//失败返回1分
}
2.算法如下：
BinTreeNode* Find ( BinTreeNode* BST, ElemType& x ) {
while ( BST != NULL ) {//循环条件1分
if ( x == BST->data ) return BST;//成功返回2分
else if ( x < BST->data ) BST = BST->leftChild;//向左孩子查找2分
else BST = BST->rightChild;//向右孩子查找2分
}
return NULL;//失败返回1分}
3.算法如下：
int Insert ( BinTreeNode*& BST, const ElemType& x ) {
if ( BST == NULL ) { //插入新结点2分BinTreeNode* p = new BinTreeNode;
p->data = x;p->leftChild = p->rightChild = NULL;
BST = p;
return 1;
}
else if ( x == BST->data ) return 0;//不插入返回2分
else if ( x < BST->data ) return Insert ( BST->leftChild, x );//向左子树插入元素2分else return Insert ( BST->rightChild, x );//向右子树插入元素2分}
4.
5.算法如下：
int Insert ( BinTreeNode*& BST, const ElemType& x ) {
BinTreeNode* t = BST, *parent = NULL;
while ( t != NULL ) { //查找插入位置，3分parent = t;
if ( x == t->data ) return 0;
else if ( x < t->data ) t = t->leftChild;
else t = t->rightChild;
}
BinTreeNode* p = new BinTreeNode;//建立新结点，2分
p->data = x;
p->leftChild = p->rightChild = NULL;
//将新结点插入到二叉搜索树中的确定位置上
if ( parent == NULL ) BST = p;//1分
else if ( x < parent->data ) parent->leftChild = p;//1分
else parent->rightChild = p;//1分
}
数据结构书面作业练习题
书面作业练习题 李英龙 湖南科技大学数学与计算科学学院
内容简介 在习题部分，既有选择题、判断题，也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。 目录 书面作业练习题 习题一绪论 -------------------------------------------------------------3 习题二顺序表示（线性表、栈和队列）-----------------------------------------6 习题三链表（线性表、栈和队列）---------------------------------------------9 习题四串-----------------------------------------------------------------12 习题五数组 --------------------------------------------------------------13 习题六树与二叉树 -------------------------------------------------------15 习题七图-----------------------------------------------------------------24 习题八查找---------------------------------------------------------------30 习题九排序---------------------------------------------------------------33
数据结构习题
第一章绪论 一、填空题 1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_________是数据的基本单位；___________是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为________。 2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_________的集合D和D上_________的集合R所构成的二元组：DS=（D，R）。 3．已知某数据结构的二元组形式表示为：A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02， 06>，<03，07>，<03，08>，<03，09>}。则此数据结构属于_____________结构。4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为__________；成正比关系时，则表示为___________；成对数关系时，则表示为___________；成平方关系时，则表示为__________。 5．数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为_____________；数据结构的存储结构主要包括____________和____________两种类型。 6．线性结构的特点是：第一个结点_______前驱结点，其余结点有且仅有_______个前驱结点；最后一个结点_______后继结点，其余每个结点有且仅有_______个后继结点。 7．树型结构的特点是：根结点没有________结点，其余每个结点有且仅有________个前驱结点；叶子结点_________后继结点，其余结点可以有_________个后继结点。 8．图型结构的特点是：每个结点可以有_________个前驱结点和后继结点。 9．程序段for（i=1，s=0；s
数据结构试卷带答案
数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 数据结构试题库 一、单项选择题 1．下列程序段所代表的算法的时间复杂度为（D ）。 x=n; y=0; while (x>=(y+1)*(y+1)) y++; (A)O(n) (B)O(n2) (C)O(log2n) (D)O(n) 2．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（B ）。 (A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/2 3．在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为（C ）。 (A)HS->next=s;(B)s->next=HS->next;HS->next=s; (C)s->next=HS;HS=s;(D)s->next=HS;HS=HS>next; 4．假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（A ）。 void AddQueue(struct linkqueue Q) { p=Q->front; while(p->next!=Q->front) p=p->next; } (A)p->next=s;s->next=Q->front; (B)Q->front->next=s;Q->front=s; (C)s->next=p;p->next=Q->front; (D)Q->front->next=s;s->next=p; 5．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B ）。 (A)2h-1(B)2h-1+1 (C)2h-1 (D)2h-1-3 习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说 法_B__ o A.正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec，中序遍历序 列是debac，它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为 习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 绪论 一、填空题 1.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系 4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。 知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序 101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式 B．数据的存储形式 C．数据的表示形式 D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项 B．数据类型 C．数据元素 D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大 B．小 C．相同 D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间 B．在顺序结构中查找元素的速度比在链接结构中查找要快 C．与链接结构相比，顺序结构便于安排数据元素 D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；i 数据结构习题集答案 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 第1章概论 1.数据、数据元素、数据结构、数据类型的含义分别是什么？ 数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。 数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。 数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取值范围和基本运算等概念。 2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？ 逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息： ①数据元素的信息； ②各数据元素之间的关系。 物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。 数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。 3.数据结构的主要操作包括哪些？ 对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有： ●创建：建立一个数据结构； ●清除：清除一个数据结构； ●插入：在数据结构中增加新的结点； ●删除：把指定的结点从数据结构中删除； ●访问：对数据结构中的结点进行访问； ●更新：改变指定结点的值或改变指定的某些结点之间的关系； ●查找：在数据结构中查找满足一定条件的结点； ●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。 4.什么是抽象数据类型？如何定义抽象数据类型？ 抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的数据类型，因此，不论ADT的内部结构如何变化，只要其数据结构的特性不变，都不影响其外部使用。 对抽象数据类型的描述一般用（D,R,P)三元组表示，抽象数据类型的定义格式为： ADT<抽象数据类型名> { 数据对象D：<数据对象的定义> 数据关系R：<数据关系的定义> 基本操作P：<基本操作的定义> 数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。数据结构试题库
数据结构书面作业练习题
数据结构习题及参考答案
数据结构考试题库
数据结构习题库
数据结构课后习题答案
数据结构考试题库含答案
数据结构试题库答案
数据结构习题及参考答案 .
数据结构试题及答案
数据结构试题(含答案)
数据结构课后习题及答案
数据结构习题参考答案
数据结构试题(含答案)