二、填空题
4.设有二维数组A[0…9, 0…19]，其每个元素占两个字节，数组按列优先顺序存储，第一个元素的存储地址为100。那么元素a[6,6]的存储地址为 232 。 7.在计算递归函数时，如果不用递归过程，则应借助于 栈 数据结构。
8.在一个链队中，如果FRONT 和REAR分别表示队首和队尾指针，则插入一个结点S↑的操作是 REAR->NEXT=S;REAR=S 。
11.从一个长度为N的顺序表中删除第I(1 <= I <= N)个元素，需要向前移动 N-1 个元素。
12.数据结构包括的3个方面的内容是：数据的 逻辑结构 、数据存储结构和数据的运算。
13.单链表是 线性表 的链式存储表示。链栈和链队分别是 栈 和 队列 的链式存储表示。
14.在具有N个单元、顺序存储的循环队列中，队满时共有 N-1 个元素。 15.数据结构即数据的逻辑结构包括 线性结构 、 树型结构 、和 图形结构 3种类型，数据的存储结构即物理结构包括 顺序 、 链接 、 索引 和 散列 4种基本类型。
17. 队列 是这样一种线性表，即所有插入和删除操作都在表的两端进行。
第4章 数组 习题
11.二维数组M[I,j]的元素是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]
5
二、填空题
9.对于一个二维数组A[1..m,1..n]，若按列为主序存储，则任意一个元素A[I,i]的相对地址是 (j-1)*n+i-1 。
第7章查找相关习题
17.有m个结点的霍夫曼树，其结点的个数为 C 。 A) 2m
B) 2m+1 C) 2m-1 D) 2(m+1)
23.二分查找法适用于存储结构为 B 的、按关键字排好序的线性表。 A) 顺序存储或链式存储 链式存储
B) 顺序存储 C) 索引存储 D)
31.一个序列中有若干个元素，若只想得到其中1个元素之前的部分排序，最好采用 排序。A A) 堆排序
B) 插入排序 C) shell排序 D) 快速排序
32.下列有关查找与排序的说法中正确的是 D 。
A) 堆排序所需的时间与待排序的记录个数无关 B) 如果某种排序算法是不稳定的，则该方法没有实际应用价值
C) 任意一颗二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间
D) 中序遍历二叉树的结点就可以得到排好序的结点序列 33.对5个不同的数据进行排序，最少需要比较 B 次。 A) 3
B) 4 C) 5 D) 6
34.长度为12的按关键字排序的查找表采用顺序组织方式，若采用二分查找，则在等概率情况下，查找失败时的ASL值是 B 。 A) 37/12
B) 62/13 C) 39/12 D) 49/13
6
35.堆的形状是一棵 C 。 A) 二叉排序树 叉树
36.静态查找表与动态查找表的根本区别在于 B 。
A) 它们的逻辑结构不一样 B) 施加于其上的操作不同 C) 所包含的数据元素的类型不一样 D) 存储实现不一样
37.在表长为n的顺序表中，实行顺序查找，在查找不成功时，与关键字比较的次数为 C 。 A) n
B) 1 C) n + 1 D) n - 1
B) 满二叉树 C) 完全二叉树 D) 不是二
51.设有一个已按各元素的值排好序的线性表，其长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k值相等的元素，比较的次数分别为s和b。那么在查找不成功的情况下，正确的s和b的数量关系是 A 。
A) 与k值大小有关 B) 总有s = b C) 总有s > b D) 总有s < b (53)-- (54)题基于下述描述
散列表的地址区间为0-17，散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列 (26,25,72,38,8,18,59)依次存储到散列表中。 53.元素59存放在散列表中的地址为 D 。 A) 8
B) 9 C) 10 D) 11
54.存放元素59需要搜索的次数是 C 。 A) 2
B) 3 C) 4 D) 5
55.已知10个数据元素为(54,28,16,34,73,62,95,60,26,43)的关键码序列，对该序列按从小到大排序，经过冒泡排序后的序列为 B 。 A) 16,28,34,54,73,62,60,26,43,95 B) 28,16,34,54,62,73,60,26,43,95
7
C) 28,16,34,54,62,60,73,26,42,95 D) 16,28,34,54,62,60,73,26,42,95
75.用顺序查找法对具有n个结点的线性表查找，查找一个结点说需要的平均查找时间为 C 。 A) O(n2)
B) O(nlog2n) C) O(n) D) O(log2n)
77.在对长度为n的、顺序存储的有限序列进行二分查找时，对应的二分查找判定树的高度为 D 。 A) n
B) [log2n] C) [log2n(n+1)] D) [log2n]
78.采用二分查找的方法查找长度为n的有序表时，查找每个元素时平均比较次数与对应判定树的的高度（假定高度不小于2）的关系为 A 。 A) 前者小于后者 前者大于等于后者
79.现存在一个有序表为(10,15,17,18,25,29,48,52,58,69,90)，当二分查找值为58的元素时， B 次比较后方可查找成功。 A) 1
B) 2 C) 3 D) 4
B) 前者大于后者 C) 前者等于后者 D)
82.对线性表进行二分法查找，其前提条件是 A 。 A) 线性表以顺序方式存储，并且按关键码值排好序 B) 线性表以顺序方式存储，并且按关键码值的检索频率排好序 C) 线性表以链接方式存储，并且按关键码值排好序
D) 线性表以链接方式存储，并且按关键码值的检索频率排好序 106.为了有效地利用散列查找技术，需要解决的问题是 C 。
Ⅰ.找一个好的散列函数 Ⅱ.设计有效的解决冲突的方法 Ⅲ.用整数表示关键码值 A) Ⅰ和Ⅱ
B) Ⅱ 和 Ⅲ C) Ⅰ，Ⅱ和Ⅲ D) Ⅰ和Ⅲ
8
