数据结构复习资料一、单项选择题第 1 题：线性表是具有 n 个( )的有限序列（n > 0）。A. 表元素B. 字符C. 数据元素D. 数据项第 2 题：设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。A. 单链表B. 单循环链表C. 带尾指针的单循环链表D. 带头结点的双循环链表第 3 题：静态链表中指针表示的是( )。A. 内存地址B. 数组下标C. 下一元素地址D. 左、右孩子地址第 4 题：链表不具有的特点是( )。A. 插入、删除不需要移动元素B. 可随机访问任一元素C. 不必事先估计存储空间D. 所需空间与线性长度成正比第 5 题：对于栈操作数据的原则是( )。A. 先进先出B. 后进先出C. 后进后出D. 不分顺序第 6 题：设有三个元素 X，Y，Z 顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。A. XYZB. YZXC. ZXYD. ZYX第 7 题：栈和队列的共同点是( )。A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点第 8 题：用带头结点的单链表表示的链式队列的队头在链表的( )位置。 A. 链头B. 链尾C. 链中D. 第 2 个结点第 9 题：设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为4，2，1，1，则 T 中的叶子数为( )。A. 5B. 6C. 7D. 8第 10 题：下述哪一条是顺序存储结构的优点？A. 存储密度大B. 插入运算方便C. 删除运算方便D. 可方便地用于各种逻辑结构的存储表示二、判断题第 11 题： （ ）数据的逻辑结构是指数据的各数据项之间的逻辑关系。第 12 题： （ ）健壮的算法不会因非法的输入数据而出现莫名其妙的状态。第 13 题： （ ）数据的物理结构是指数据在计算机内的实际存储形式。第 14 题： （ ）线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。第 15 题： （ ）顺序存储方式只能用于存储线性结构。第 16 题： （ ）若输入序列为 1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。第 17 题： （ ）栈和队列的存储方式，既可以是顺序存储方式，又可以是链式存储方式。第 18 题： （ ）完全二叉树一定存在度为 1 的结点。第 19 题： （ ）对于有 n 个结点的二叉树，其高度为 log2n。第 20 题： （ ）深度为 k 的二叉树中结点总数 ≤ 2k-1。三、填空题第 21 题： 1、常见的基本数据结构包括：（）、（）、（）及（） 四种。2、假设用循环单链表实现队列，若队列非空，且队尾指针为 R, 则将新结点 S加入队列时，需执行下面语句：（） ；（） ；R=S；3、已知一个 3 行、4 列的二维数组 A（各维下标均从 1 开始），如果按“以列为主”的顺序存储，则排在第 8 个位置的元素是：（）。4、高度为 k 的完全二叉树有（）个结点。5、若相同关键码值的元素间的位置关系，排序前与排序后保持一致，称此排序方法是（）的；而不能保持一致的排序方法则称为 （）的。四、问答题 第 22 题： 已知给定结点的中序序列和后序序列分别为 g d h b e i a f j c 和 gh d i e b j f c a，请构造唯一确定的一棵二叉树。五、论述题第 23 题： 将下列的二叉树转换成森林，并写出转换步骤及过程。 第 24 题： 以 7，5，4，2 为叶子结点权值构造哈夫曼树，写出构造过程及步骤，并计算该哈夫曼树的带权路径长度 WPL。 六、计算题第 25 题： 下列为折半查找算法，请完成该算法。// 数组 R 中的元素递增有序，n 为当前元素的个数， K 为待查找的元素。//查找成功，返回其下标，查找不成功返回-1。 第 26 题： 给出下列带权有向图的相应邻接矩阵表示。 七、案例分析题第 27 题： 写出单链表存储结构的 C 语言描述，并设计出删除单链表中第 i 个结点的算法数据结构复习资料参考答案一、单项选择题 4、B 5、B 6、C 7、C 8、A 9、D 10、A 二、判断题11、错 12、错 13、对 14、对 15、错 16、对 17、对 18、错 19、错 20、对 三、填空题21、 四、问答题22、 五、论述题23、首先，若结点 x 是其双亲 y 的左孩子，则将 x 的右孩子，右孩子的右孩子，……，都与 y 用连线连起来； 接着，去掉所有双亲到右孩子之间的连线; 调整位置，得到最终的森林 24、在初始森林中，选出两棵根结点的权值最小的二叉树，合并两棵选出的二叉树，新增一个结点作为新的二叉树的根结点，权值为左右孩子的权值之和 在森林中，选出两棵根结点的权值最小的二叉树，合并两棵选出的二叉树，新增一个结点作为新的二叉树的根结点，权值为左右孩子的权值之和 合并两棵二叉树，新增一个结点作为新的二叉树的根结点，权值为左右孩子的权值之和，得到最终的哈夫曼树 该哈夫曼树的带权路径长度 WPL=7×1+5×2+2×3+4×3=35。 六、计算题25、下列为折半查找算法，1)low < =high2)high = mid-13)low = mid-1 26、 七、案例分析题27、