数据结构练习题一
- 格式：doc
- 大小：41.00 KB
- 文档页数：3
数据结构练习题
一、单项选择题
1、算法是指（ ）
A) 计算机程序 B) 解决问题的计算方法
C) 解决问题的有限运算序列 D) 排序方法
2、线性表采用链式存储时，结点的存储地址（ ）
A) 必须是不连续的 B) 连续与否均可
C) 必须是连续的 D) 和头结点的存储地址相连续
3、链表不具有的特点是（ ）
A) 可随机访问任一元素
B) 插入、删除操作不需要移动元素
C) 不必事先预分配存储空间
D) 所需空间与线性表的长度成正比
4、下列关于串的描述正确的是（ ）
A) 串是一种特殊的线性表 B) 串的长度必须大于零
C) 串中元素只能是字符 D) 空串就是空白串
5、设数组data[m]作为循环队列SQ的存储空间，front和rear分别表示队列的头、尾指针，则执行出队操作后，队列头指针front的值为（ ）
A) front＝front＋1 B) front＝(front＋1)%m
C) front＝(front＋1)%(m—1) D) front＝(front—1)%m
6、由三个结点可以构造出多少种形态不同的二叉树？（ ）
A) 4种 B) 5种 C) 6种 D) 7种
7、在有向图的正邻接链表中，第k个链表中的表结点数是（ ）
A) 依附于顶点Vk的边数 B) 顶点Vk的出度
C) 顶点的Vk度 D) 顶点Vk的入度
8、一个栈的入栈序列是A、B、C、D、E，则不可能的出栈序列是（ ）
A) EDCBA B) DECBA C) DCEAB D) ABCDE
9、设数组data[m]作为循环队列SQ的存储空间，front和rear分别表示队列的头、尾指针，则判断队列是否为满的条件是（ ）
A) front＝＝rear＋1 B) front＝＝rear
C) front＝＝(rear＋1)%m D) rear＝＝(front＋1)%m
10、在单链表中的P结点之后插入一个结点S，则应执行的语句是（ ）
A) S→next＝P→next； P→next＝S
B) P→next＝S； S→next＝P→next
C) P→next＝S→next； S→next＝P
D) S→next＝P； P→next＝S→next
11、在有向图的逆邻接链表中，第k个链表中的结点数是（ ）
A) 依附于顶点Vk的边数 B) 顶点Vk的出度 C) 顶点的Vk度 D) 顶点Vk的入度
12、n个顶点的连通图至少有多少条边？（ ）
A) n＋1 B) n C) n－1 D) n(n－1)
13、平衡二叉树是指（ ）
D) 左右子树的深度之差不超过1
E) 左右子树的深度是平衡的
F) 左右子树的深度之差的绝对值不超过1
D) 左右子树的深度之差小于2
14、断定一个有向图是否存在回路，可以采用（ ）
A) 弗洛伊德算法 B) 迪杰斯特拉算法
C) BFS算法 D) DFS算法
15、用某种排序方法对关键字序列{25、84、21、47、15、27、68、35、20}进行排序时，关键字序列的变化情况如下所示：
第一趟排序结果：20、15、21、25、47、27、68、35、84；
第二趟排序结果：15、20、21、25、35、27、47、68、84；
第三趟排序结果：15、20、21、25、27、35、47、68、84．
则采用的排序方法是（ ）
A) 直接插入排序 B) 希尔排序 C) 选择排序 D) 快速排序
二、填空题
1、一个算法具有的五个重要特性是 、 、 、 和 。
2、评价算法效率的方法有 方法和 方法；而评价算法效率的主要指标有 和 。
3、线性表、栈和队列都是 结构，可以在线性表的 位置插入和删除元素；栈是一种 的线性表，只能在 位置插入和删除元素；而队列是一种 的线性表，只能在 插入元素，在 删除元素。
4、假设S和X分别表示进栈和出栈操作，由输入序列”ABC”得到的输出序列”BCA”的操作序列为”SSXSXX”。则由输入序列”ABCDE”得到输出序列”DECBA”的操作序列为的 。
5、在一棵二叉树中，度为零的结点个数为n0，度为2的结点的个数为n2，则有n0= 。
6、在直接插入排序、冒泡排序、希尔排序、简单选择排序、快速排序和堆排序这些排序方法当中，属于稳定的排序有 ，属于不稳定的排序有 。
7、已知广义表 A=(a,(b,c,d),e,(f,g))，则Gethead(A)=_____，GetTail(A)=________。
8、已知广义表C=(a,(b,c,(d)))， F=(e,C,( ))，则广义表F的长度___，为深度为___。
三、现有以下按前序和中序遍历二叉树的结果：
前序：ABCDEFGHI 中序：BCAEDGHFI
画出该二叉树的逻辑结构图和存储结构图。 四、已知信息为“ABCDBCDCBDBACB”，
（1）请按此信息构造哈夫曼树；
（2）计算哈夫曼树的加权路径长度WPL；
（3）求出每一字符的最优编码；
（4）写出信息编码。
五、已知一组关键字为（38，65，20，18，50，90，35，80，100，95，61，19），依次插入关键字生成一棵二叉排序树，问：
（1）查找关键字等于61的结点记录需比较 次；
（2）与61比较的关键字序列是 ；
（3）如果将关键字为85的记录插入到树中，它将作为 结点的
_____孩子结点；
（4）若要删除关键字为65的记录，可以取 或 替换65作为38结点的右子树的根。
六、试按下列次序(8，9，10，2，1，5，3，6，4，7，11，12)建立一棵二叉平衡树。
七、设哈希表长为13，散列函数为H(k)=k mod 13，关键字序列为7，4，1，14，100，30，5，9，20，134；试求：
（1）散列后的表中关键字分布（假定解决冲突的方法为线性探测再散列法）；求平均查找长度ASL；
（2）求出散列后的表的装填因子；
（3）用链地址法解决冲突，给出相应的哈希表，求ASL；
（4）分别计算该序列用顺序查找法和排序之后用折半查找的ASL。
