资源描述：
《数据结构总复习试题目》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、选择题1、在一个长度为n的顺序表中删除一个值为x的元素时，需要比较元素和移动元素的总次数为（）。A.(n+1)/2B.n/2C.nD.n+12、已知L是一个不带表头的单链表,在表首插入结点*p的操作是（）:A.p=L;p->link=L;C.p->link=L;p=L;B.p->link=L;L=p;D.L=p;p->link=L;3、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。A.top++;B.top--;C.top=0;D.top;4、在一棵具有n个结点的二叉树中，所有
2、结点的空子树个数等于()？A.nB.n-1C.n+1D.2*n5、一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+16、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG7、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定8、适用于折半查找的表的存储方式及元素排列要求为()?A．链接方式存储，元素无序B．链
3、接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序9、下面关于哈希(Hash，杂凑)查找的说法正确的是()A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可10、若采用链地址法构造散列表，散列函数为H（key）=keyMOD17，则需(（1）)个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(（2）)（1）A．17B.13C.16D.任意（2）A．0至17B.1至1
4、7C.0至16D.1至1611、下列排序算法中，其中（）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.堆排序，归并排序D.归并排序，冒泡排序12、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是()。A.选择B.冒泡C.快速D.插入13、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A．(38,40,46,56,79,84)
5、B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)14、在下面的排序方法中，辅助空间为O（n）的是()。A．希尔排序B.堆排序C.选择排序D.归并排序15、对于长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为（）A、5.5B、5C、39/8D、19/416、对于长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找到表中任一个元素的平均查找长度为（）A、n/2B、(n+1)/2C、(
6、n-1)/2D、n/4二、填空题：1、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为（）。2、给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__，带权路径长度WPL的值为_。3、执行顺序查找时，储存方式可以是__(1)，二分法查找时，要求线性表(2)_，分块查找时要求线性表(3)_，而散列表的查找，要求线性表的存储方式是(4)_。4、已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_5、一个有2001个结点的完全二叉树的高度为___。6、已知二叉树前序为ABDEGCF，中序为DBGEA
7、CF，则后序一定是__。7、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是__。8、假定一个最大堆（大根堆）为（56,38,42,30,25,40,35,20），则依次向它插入45和64两个元素后得到的最大堆为：9、表达式求值是__应用的一个典型例子10、数据结构中评价算法的两个重要指标是.三、分析题1、已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。并画出二叉树的图。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G后序序列：2、假设用于通信的电文仅由A-H八个字母组成，字母在电文中
8、出现的频率分别为7，19，2，6，32
