发布时间 : 星期四 文章2016现代科技学院《软件技术基础》练习题+答案更新完毕开始阅读62d9a7af77232f60dccca1ab
三、判断题
1．顺序存储的线性表可以随机存取。
2．顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。
3．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 4．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 5．在单链表中，可以从头结点开始查找任何一个元素。 6．线性表的链式存储结构优于顺序存储结构。
7．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。
8．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
9．顺序存储方式只能用于存储线性结构。 10．循环队列中元素个数为rear-front。
11．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2． 12．若以链表作为栈的存储结构，则入栈需要判断栈是否满． 13．数组是同类型值的集合。 14．数组是一组连续的内存单元。
15．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
16．插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。 17．使用三元组表示稀疏矩阵的元素，有时并不能节省存储空间。 18．二叉树是树的特殊形式。
19．树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
20．用邻接矩阵法存储图时，所占用的存储空间大小仅与图中结点个数有关。 21．存储有向图的邻接矩阵一定是对称的。
四、简答应用题
1. 有三个元素的进栈序列是1，2，3，举出此三个元素可能的出栈序列，并写出相应的进栈和出栈操作序列 (假设以I和O表示进栈和出栈操作)。 2. 试将下列稀疏矩阵A用三元组（三列二维表格）形式来表示，并写出对应的辅助向量POS和NUM。
40A?0000300000006500 00
3. 试写出对下图所示的二叉树分别按前序、中序和后序遍历时得到的结点序列。
E DA
BC
9
4. 画出下图所示的树对应的二叉树。
A BECFD
5. 请写出下图对应的关联矩阵R及求值矩阵V，结点A,B,C,D,E分别用1,2,3,4,5编号
10A811 B13ED12C
6. 逻辑结构与存储结构是什么关系？
7. 描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。 8. 何时选用顺序表，何时选用链表作为线性表的存储结构为宜？
9. 如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？
10. 若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？
11. 设计算法并写出程序，实现“计算带头结点的单链表的结点个数”。
12. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。
10
第三章 查找与排序
一、选择题
1. 对采用折半查找法进行查找操作的查找表，要求按【 】方式进行存储。
A．顺序存储 B．链式存储
C．顺序存储且结点按关键字有序 D．链式存储且结点按关键字有序
2. 设有序表的关键字序列为(1，4，6，10，18，35，42，53，67，71，78，84，92，99)，当用折半查找法查找键值为35的结点时，经【 】次比较后查找成功。
A．2 B．3 C．4 D．6 3. 分块查找的时间性能【 】。
A．低于折半查找
B．高于顺序查找而低于折半查找 C．高于顺序查找
D．低于顺序查找而高于折半查找
4. 设哈希函数为H(key)=key％7，一组关键字为(37，21，9，20，30，19，46)，哈希表T的地址空间为0..6，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为【 】。 A． 0 1 2 3 4 5 6 21 20 37 9 46 30 19 B． 0 1 2 3 4 5 6 21 46 37 9 30 19 20 C． 0 1 2 3 4 5 6 21 19 9 37 30 46 20 D．0 1 2 3 4 5 6 20 37 30 21 46 19 9
5. 设有一个用线性探测法解决冲突得到的哈希表：
0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14
哈希函数为H(key)=key％11，若要查找元素14，探测的次数是【 】。 A．3 B．6 C．7 D．9
6. 在哈希函数H(key)=key％m中，一般来讲，m应取【 】。
A．奇数 B．偶数 C．素数 D．充分大的数 7. 以下说法错误的是【 】。
A．哈希法存储的基本思想是由关键字的值决定数据的存储地址 B．哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C．哈希表的基本思想与顺序查找、对分查找和分块查找都不同
D．哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法
8. 在关键字随机分布的情况下，用二叉排序树的方法进行查找，其平均查找长度与【 】查找方法量级相当。
A．分块 B．顺序 C．折半 D．散列
9. 在具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为【 】。
2
A．O(n) B．O(1) C．O(log2n) D．O(n) 10. 哈希表的平均查找长度( )。
A．与处理冲突的方法有关而与表的长度无关
11
B．与处理冲突的方法无关而与表的长度有关 C．与处理冲突的方法有关且与表的长度有关 D．与处理冲突的方法无关且与表的长度无关
11. 有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列【 】输入序列。
A．45，12，49，6，40，56，32 B．40，12，6，32，49，45，56 C．6，12，32，40，45，49，56 D．32，12，6，40，45，56，49
12. 在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为【 】。 A．n B．log2n C．(h+1)／2 D．h
13. 【 】方法是从未排序序列中依次取出元素与已经排序序列中的元素进行比较，将其放人已经排序序列的正确位置上。
A．双向冒泡排序 B．插入排序 C．冒泡排序 D．选择排序
14. 【 】方法是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。 A．双向冒泡排序 B．插入排序 C．冒泡排序 D．选择排序
二、填空题
1．索引顺序表上的查找分两个阶段：一、______________；二、____________。该查找方法称为________查找。
2．二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值___于其左孩子(及其子孙)的键值且____于其右孩子(及其子孙)的键值。
3．中序遍历一棵二叉排序树所得到的结点访问序列是键值的_____序列。
4．二叉排序树上的查找长度不仅与______有关，也与二叉排序树的________有关。
5．折半查找方法仅适用于这样的表：表中的记录必须______，其存储结构必须是_______。 6．按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 7．请填空完成顺序查找算法程序：在线性表v中查找值为k的元素 struct sqlist {
int elem[MAXSIZE]; int last; };
int seqsearch (struct sqlist v, int k) { int i;
for(i=1;i<=v.last;i++) if(______________) return i; /*查找成功，返回被查元素在表中相对位置*/ return 0; /*查找失败，返回0*/ }
8．请填空完成改进型的顺序查找算法程序：在线性表v中查找值为k的元素 struct sqlist {
int elem[MAXSIZE]; int last; };
int seqsearch (struct sqlist v, int k) { int i;
12