软件技术基础（二）
数据结构（二）
一、 选择题。
1. 只允许在一端进行插入删除的线性表称为。
a.栈顶 b.队列 c.堆栈 d.队尾。
2. 向顺序栈中压入元素时，__
a.先移动栈顶指针，后存入元素 b. 先存入元素，后移动栈顶指针。
c.谁先谁后无关紧要d.同时进行。
3. 对链式存储的线性表。
a.可采用顺序查找，但不可采用二分查找 b.可采用二分查找，但不可采用顺序查找。
c.顺序查找和二分查找均可采用d.顺序查找和二分查找均不可采用。
4. 线性表l在下列___情况下，适合使用链接结构实现。
中含有大量结点b.需经常对l表进行删除与插入。
c.需经常修改l的结点值 表结点结构复杂。
5. 设f和r分别是一个链表的队头和队尾，那么从该队列中删除一个结点的运算是___
next >next >next >next
6. 设f和r分别是一个链表的队头和队尾，那么从该队列中插入一个结点的运算是___
next >next >next >next
7. 在有n单元的顺序存储的堆栈中，假定以地址低端(即下标为1的单元)作为栈底，以top作为栈顶指针，则当做入栈处理时，top的变化为：__
不变 b. top=top+1 c. top=n
8. 若进栈序列为1，2，3，4，假定进栈和出栈可以穿插进行，则不可能出栈的序列是___
a. 1,4,3,2 b. 2,3,4,1 c. 3,1,4,2 d. 3,4,2,1
9. 设栈初始为空，输入序列为：a，b，c，d。经过入栈、入栈、出栈、入栈、出栈、入栈操作之后，栈中的元素(从栈底到栈顶)依次为。
a．a，d c．b，c d．d,a
10. 对于任何一棵二叉树，若叶子结点个数为n0，度为2的结点个数为n2，则n0
d.2*n2
11. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为。
a.219 b.221 c.229 d.231
12. 深度为6的二叉树上共有个叶子结点。
a. 31 b.32 c.63 d.64
13. 将有三棵树的森林转换成一棵二叉树，则第二棵树的根结点是该二叉树根结点的___的根结点。
a.左子树 b. 左子女的右子树 c.右子树 d.右子女的右子树。
14. 将有三棵树的森林转换成一棵二叉树，则第三树的根结点是该二叉树根结点的___的根结点。
a．左子树 b.左子树的右子树 c.右子树 d.右子树的右子树。
15. 假定一棵二叉树的结点数为18，则它的最小深度为。
a.18 b.9 c.5 d.3
16. 在具有size单元的顺序存储的循环队列中，假定front和rear分别指示队列中第一个元素和最后一个元素的下一个位置，则判断队空的条件是：__
rear c. front== rear
17. 在由m个单元组成的循环队列中，队首指针f指示队列中首元素的前一个位置，队尾指针r指示队列中最后一个元素，则判断队满的条件是。
c.(f+1)%m=r
18. 链栈与顺序栈相比，有一个比较明显的优点是___
a．插入操作更加方便 b．通常不会出现栈满的情况。
c．不会出现栈空的情况 d．删除操作更加方便。
19. 如果n1和n2是二叉树t中两个不同结点，n2是n1的后代，那么按___遍历二叉树t时，结点n2一定比结点n1先被访问。
a.先序 b.中序 c.后序 d.逆中序。
20. 一棵二叉树具有9个叶子结点。且非叶子结点都是度为2的结点，则这棵二叉树共有___结点。
a.17 b.18 c.19 d.20
21. 具有三个结点的二叉树的基本形态有___种。
a.5 b.4 c.3 d.2
22. 以下___不是队列的基本操作。
a．从队尾插入一个新元素 b.从队列中删除第i个元素。
c．判断一个队列是否为空 d。读取队头元素的值。
23. 在树结构中，如果结点a有3个兄弟，而且b是a的双亲，则b的度是___
a．3 b．1 c．4 d5．
24. 线性表是___
a．一个有限序列，可以为空 b．一个有限序列，不能为空。
c．一个无限序列，可以为空 d．一个无限序列，不能为空。
25. 线性表采用链式存储时，其地址___
a．必须是连续的b。部分地址必须是连续的。
c．一定是不连续的 d．连续与否均可以。
26. 一维数组和线性表的区别是___
a．前者长度固定 ，后者长度可变 b。后者长度固定 ，前者长度可变。
c．两者长度均固定d．两者长度均可变。
27. 数据结构中，与所使用的计算机无关的是数据的___结构。
a.存储 b.物理 c.物理和存储 d.逻辑。
28. 链表不具有的特点是___
a．随机访问b．不必事先估计存储空间
c．插入删除时不需移动元素 d．所需空间与线性表成正比。
29. 二叉树有多种形式，若深度为k，且有2k-1个结点的二叉树称为。
a.完全二叉树 b.满二叉树 c.顺序二叉树 d.排序树。
30. 已知某二叉树的前序序列是abdc，中序序列是dbac，问它的后序序列是___
a. adbc b. dbca c. cabd
31. 上溢现象通常出现在___
a.顺序栈的入栈操作过程中 b.顺序栈的出栈操作过程中。
c.链栈的入栈操作过程中 d.链栈的出栈操作过程中。
32. 引起循环队列队头位置发生变化的操作是。
a. 出队 b. 入队 c. 取队头元素 d. 取队尾元素。
33. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的。
a.1/2 倍 b. 1 倍 c. 2 倍 d．3 倍
34. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系。
a.不一定相同 b.都相同 c.都不相同 d.互为逆序。
35. 一棵二叉树中共有10个叶子结点与20个度为1的结点，则该二叉树中的总结点数为。
a.30 b.31 c.39 d.40
36. 栈结构通常采用的两种存储结构是。
a．顺序存储结构和链表存储结构 b．链表存储结构和数组。
c．线性存储结构和非线性存储结构 d．散列方式和索引方式。
37. 链式存储的存储结构所占存储空间___
a．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
b．只有一部分，存放结点值。
c．只有一部分，存储表示结点间关系的指针。
d．分两部分，一部分存放结点值，另一部分存放结点所占单元数。
38. 只允许在二端进行插入删除的线性表称为。
a.栈顶 b.队列 c.堆栈 d.队尾。
39. 堆栈结构的特点是___
a．同时进出 b．先进先出 c．后进后出 d．后进先出。
40. 网状数据模型。
a.允许有一个以上的结点无双亲b．有且只有一个结点无双亲
c．除了一个根结点，其他结点只有一个双亲 d．每一个结点的子女不能多于一个
41. 学校中学生作为一个实体与他的学习课程（另一个实体）之间的联系是。
a．一对一 b．多对多 c．一对多 d．多对一。
42. 链表中进行操作的效率比顺序表中高。
a.二分查找和删除 b.插入和删除 c.二分查找和插入 d.快速查找。
43. 当栈中的元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为___
44. 栈和队列。
a. 的共同点都是先进后出b. 的共同点都是先进先出
c. 的共同点是只允许在端点处插入和删除元素 d. 没有共同点
二。填空题。
45. 有一棵顺序二叉树，有编号为22结点的双亲，其左孩子在___编号位置上。
46. 在深度为7的满二叉树中，度为2的结点个数为。
47. 按“先进后出”原则组织数据的数据结构是。
48. 需要对线性表进行插入和删除运算，则最好采用___存储结构。
49. 若一个栈的输入序列是1，2，3….，n，输出序列的第一个元素是n，则第i个输出元素是___
50. 允许在一端进行插入，而在一端进行删除的线性表称为。
51. 对于任一棵二叉树，若叶子结点个数为n0,度为2 的结点数为n2,则n2
52. 一个具有22个叶子结点的二叉树，其度数为2的结点数是___
53. 在二叉树上的第3层上至多有个结点。
《数据结构》综合练习
1.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为 c a.存储结构b.逻辑结构 c.链式存储结构d.顺序存储结构。2.设语句x 的时间是单位时间，则以下语句的时间复杂度为 b for i 1 i n i for j i j n j x 3.链式存储结构的最大优点是 d a.便于随机...
数据结构与算法综合练习
练习。1.内存中一片连续空间 不妨假设地址从1到m 提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。2.叙述前序和中序遍历二叉树的步骤 一棵前序序列为1,2,3,4的二叉树，其中序序列可能是4,1,2,3吗？设一棵二叉树的前序序列为1,2,3,4,...
数据结构练习
一 选择题 1 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动 个数据元素。a 2.在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行b a.q next p s next p b.s next p q nex...