数据结构与课程练习题1 .ppt

* 《数据结构》课程练习题 一、选择题 1、算法是计算机求解问题的一个运算序列，下列的各项中 不属于一个算法必须具备的特性。 A、有穷性 B、确定性 C、可行性 D、复杂性 2、带头结点的单链表head为空的判定条件是： 。 A.head==NULL B.head-next==NULL C.head-next==head D.head!==NULL 3、设串s1=ABCDEFG,s2=PQRST,函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果是： 。 A.BDCEF B.BCDEFG C.BCPQRST D.BCDEFEF 4、串是一种特殊的线性表，其特殊性体现在 。 A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符 5、一个队列的入列顺序是1，2，3，4，则队列的输出序列是： 。 A.4,3,2,1 B.1,2,3,4 C.1,4,3,2 D.3,2,4,1 6、设一个栈的输入序列是1，2，3，4，则借助一个栈所得到的输出序列不可能是 。 A、1，2，3，4 B、4，3，2，1 C、1，3，4，2 D、4，1，2，3 7、按照二叉树的定义，具有3个结点的二叉树有 种。 A、 3 B、 4 C、 5 D、2 8、折半查找法要求查找表中各元素的键值必须是 排列。 A、递增或递减 B、递增 C、递减 D、无序 9、下列排序算法中，时间复杂度为O（nlog2n）且占用额外空间最少的是 。 A、堆排序 B、冒泡排序 C、快速排序 D、希尔排序 10、下述几种排序方法中，平均查找长度最小的是 。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 1.设二维数组A[5][6]的每个元素占4个字节，已知Loc(a[0][0])=1000，A共占多少个字节? A的终端结点a[4][5]的起始地位为何?按行和按列优先存储时，a[2][5]的起始地址分别为何? 2.数组A中，每个元素A[i,j]的长度均为2个单元,行下标从0到10，列下标从1到11，从首地址S开始连续存放主存储器中，求： （1）存放该数组所需多少单元？ （2）存放数组第4列所有元素至少需多少单元？ （3）数组按行存放时，元素A[7,4]的起始地址是多少？ （4）数组按列存放时，元素A[4,7]的起始地址是多少？ 3.、假设有一组权值{5,29,7,8,14,23,3,11}，请利用这组权值构造哈夫曼树，且求它的带权路径长度。 4.设电文中出现的字符为A, B, C, D, E，每个字母在电文中出现的次数分别为 9, 7 , 3, 5,11，试按哈夫曼得出C的编码。 5.若二叉树的先序遍历为：abcdefg，中序遍历为：cbdafeg，求二叉树的后序遍历序列。 6.试找出分别满足下面条件的所有二叉树： (1)前序序列和中序序列相同； (2)中序序列和后序序列相同； (3)前序序列和后序序列相同。 (4)前序序列、中序序列和后序序列相同。 7.将下列树转换为相应的二叉树。 8.将下列二叉树转换成所对应的森林。 图 7 图 8 S T K X M N O 9.对下列所示的连通图，请： ⑴ 从顶点f出发，求它的一棵深度优先生成树。 ⑵ 从顶点e出发，求它的一棵广度优先生成树。 ⑶ 求它的最小生成树。 *