复习题.doc(数据结构).doc

一、 选择题一：（） 1、用单链表的方式存储线性表每个节点需要一个数据域和一个（ ）。A.本节点的地址域 B.指针域 C.空指针域 D.空闲域2、一棵n个节点的二叉树其空指针域的个数是（ ）。A.n B.n+1 C.n-1 D.不能确定3、在队列栈存取数据应遵守的原则是（ ）。A.先进先出 B. 先进后出 C.随意进出 D. 后进先出4、设有编号为1、2、3、4的四辆列车，顺序进入一个栈式结构的站台，下列不可能的出站顺序为（）。A.1234 B.1243 C.1324 D.14235、若4个元素按A、B、C、D顺序入队Q，队尾元素是（）。A.A B.B C.C D.D6、空串与空白串（）。A.相同 B.不相同 C.可能相同 D.无法确定7、广义表（A,B,E,F,G）的表尾是（）。A.（B,E,F,G） B.() C. （A,B,E,F,G） D.(G)8、具有3个节点的树有（）种不同形态。A.3 B.4 C.5 D.29、某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC,则先序遍历序列为（）。A.ACBED B.DECAB C.DEABC D.CEDBA10、有8个节点的无向图最多有（）条边。A.14 B.28 C.56 D.11211、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为。A.n B.n/2 C.(n+1)/2 D.(n-1)/212、100个元素采用二分法查找时，最大的比较次数是（ ）。A.2 B.7 C.4 D.513、下列排序方法中，不属于插入排序的是（）。A.希尔排序 B.冒泡排序（属于交换排序） C.直接插入排序 D.二分插入排序14、下述几种排序方法中，平均查找长度最小的是（）。A.插入排序 B.选择排序 C.快速排序 D.归并排序15、指针P指向循环链表L的尾元素的条件是（）。A.P = L B.L-next = P C.P-next = NULL D.P-next = L选择题一答案题号123456789101112131415答案BBADDBADDBCBBCD选择题二1、非线性结构的数据元素之间存在（ ）。A.一对一关系 B.一对多关系 C.多对多关系 D.B或C2、单链表的存储密度（ ）。A.大于1 B.等于1 C.小于1 D.不能确定3、在线性表中（ ）只有一个直接前驱和一个直接后继。A.首元素 B.中间元素 C.尾元素 D.所有元素4、设有编号为1、2、3、4的四辆列车，顺序进入一个栈式结构的站台，下列不可能的出站顺序为（）。A.1234 B.1243 C.1324 D.14235、若4个元素按A、B、C、D顺序入队Q，队头元素是（）。A.A B.B C.C D.D6、一个循环队列一旦说明，其占用的空间大小（）。A.已固定 B.可以变动 C.不能固定 D.动态变化第2 页 共 8 页7、若串S = “software”，其子串数目是（）。A.8 B.37 C.36 D.98、节点前序为ABC的不同二叉树有（）种形态。A.3 B.4 C.5 D.69、某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC,则先序遍历序列为（）。A.ACBED B.DECAB C.DEABC D.CEDBA10、在一个图中所有顶点的度数之和等于图的边数的（）倍。A.1/2 B.1 C.2 D.411、查找表是以（）为查找结构的。A.集合 B.图 C.树 D.文件12、有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值为82的节点时，经（）次比较后查找成功。A.2 B.3 C.4 D.513、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）。A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序14、下述几种排序方法中，平均查找长度最小的是（）。A.插入排序 B.选择排序 C.快速排序 D.归并排序第 3 页 共 8 页15、指针P指向循环链表L的首元素的条件是（）。A.P = L B.L-next = P C.P-next = NULL D.P-next = L选择题二答案题号123456789101112131415答案DCBDAACCDCACDCB选择题三1在数据结构中，从逻辑上可以把数据结构分为。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D内部结构和外部结构 2算法分析的两个主要方面是。 A空间复杂性和时间复杂性 B正确性和简明性 C. 可读性和文档性 D数据复杂性和程序复杂性 3计算机算法它必具备输入、输出和等五个特性。 A可执行性、可移植性和可扩充性。 B可执行性、确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和安全性 4线性表若采用链表存储结构时，要求内存中可用存储单元的地址。 A必须是连续的 B部分地址必须是连续的 C. 一定是不连续的 D连续不连续都可以 5一个向量第一个元素的存储地址是100，每个元素的长度为2则第5个元素的地址是。 A110 B。108 C100 D120 6栈和队列的共同点是。 A都是先进后出 B都是先进先出 C. 只允许在端点处插入和删除元素 D没有共同点 7在一单链表中，若p结点不是最后结点，在p之后插入s结点，则执行。 Asnext：p；pnext：s； Bsnext：pnext；pnext：s； Csnext：pnext；p：s； Dpnext：s；snext：p； 8在一单链表中，若删除p结点的后续结点，则执行。 Apnext：pnextnext； Bp：pnext；pnext：pnextnext； Cpnext：=pnext； Dp：pnextnext 9串是一种特殊的线性表，其特殊性体现在。 A可以顺序存储 B数据元素是一个字符 C. 可以链接存储 D数据元素可以是多个字符 10结点数为N的二叉树有个空闲指针。 AN BN+1 C2N DN-1 11设有两个串s和t，求t在s中首次出现的位置的运算称作。 A连接 B模式匹配 C求子串 D求串长 12在一非空二叉树的中序遍历序列中，根结点的右边。 A只有右子树上的所有结点 B只有右子树上的部分结点 C 只有左子树上的部分结点 D只有左子树上的所有结点 13树最适合用来表示。 A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据 14一个有n个顶点的无向图最多有条边。 An Bn(n一1) Cn(n一1)2 D2n 15在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。 An Bn+1 Cn一1 Dn2 16对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。 An B(n一1) 2 Cn-1 Dn * n 17对线性表进行二分查找时，要求线性表必须。 A以顺序方式存储 B以链接方式存储 C以顺序方式存储，且结点按关键字有序排序 D以链接方式存储，且结点按关键字有序排序 18采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度ASL为。 An Bn2 C(n+1)2 D(n一1)2 19设哈希表长m14，哈希函数H(key)key MOD ll。表中已有4个结点： addr(15)=4 addr(38)=5 addr(61)6 addr(84)7 其余地址为空 如用二次探测再散列处理冲突，关键字为49的结点的地址是。 A8 B3 C5 D9 20一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。 A38，40，46，56，79，84 B40，38，46，79，56，84 C40，38，46，56，79，84D40，38，46，84，56，79 选择题三答案题号1234567891011121314151617181920答案CABDBCBABBBACCCDACDC二、 填空题：（共10小题，每小题2分，共20分） 1数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2算法的五个重要特性是、。 3下面程序段的时间复杂度是。 for i：1 to n dO for j：l to n dO Ai,j：0；4栈的特点是，队列的特点是。 5一个队列的入队序列是1，2，3，4，则队列的输出序列是。6设有C+定义的二维数组A68，每个元素占4个字节，按行优先顺序存放，A的起始地址为100，则元素A14的地址是，元素A47的地址是 。 7按照二叉树的定义，具有3个结点的二叉树有种。8深度为5的二叉树至多有个结点。 9、查找算法按查找表在查找过程中是否可进行插入和删除操作可分为查找和查找。10、排序算法在排序过程中如果能完全保证排序关键字值相同的记录在排序前后的次序不变，则称这类排序算法是的排序算法.反之，如果不能保证排序关键字值相同的记录在排序前后的次序不变，则称这类排序算法是的排序算法. 三 判断题：（共5小题，每小题2分，共10分）1、从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。2、顺序存储的线性表可以实现随机存取。3、栈是运算受限制的线性表。4、完全二叉树一定是满二叉树。5、图可以没有边但不能没有顶点。6、在线性表的顺序结构中，插入和删除元素时，移动元素的个数，与该元素的位置有关。7、队列是一种“后进先出”的线性表。8、串的长度不能为0。9、对有序表而言，采用二分查找，总比顺序查找法速度快。10、快速排序在任何情况下都比其它排序方法速度快。21、算法是对解题方法和步骤的描述。22、单链表的每个节点都恰好包含一个指针域。23、队是运算受限制的线性表。24、树结构中每个节点最多只有一个直接前驱。25、有向图不能进行广度优先搜索遍历。26、线性表的链式存储结构优先与顺序存储结构。27、队列是一种“后进后出”的线性表。28、串中不可以包含有空白字符。29、二分查找法要求待查表的关键字的值必须是有序的。30、冒泡排序是不稳定的排序。31空串与空格串是相同的，这种说法。 A正确 B不正确 32二叉树的左右子树的位置总是可以交换的，这个断言是。 A正确的 B错误的 33连通图一定是完全图，反之亦然。这个断言是。 A正确的 B错误的 34在各种查找方法中，平均查找长度与结点个数n无关的查法方法是哈希查找。A正确的 B错误的 35、基数排序是稳定的排序算法。A 正确的 B错误的判断题答案题号12345678910答案TTTFTTFFTF题号21222324252627282930答案TFTTFFFFTF题号3132333435答案FFFTT四、问答题：（10）1、（1）写出下图从V1 开始的深度优先搜索序列。（2）写出下图从V1 开始的广度优先搜索序列； 2、指出树和二叉树的主要差别？3、二叉树遍历：分别写出下图所示二叉树的前序、中序、后序遍历序列。（10分） 4、已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11.先画出赫夫曼树的示意图，再根据该树依次写出这8种字符的赫夫曼编码。 5、给定一个权集W=4,5，7,8,6,12,18，请画出相应的哈夫曼树，并计算其带权路径长度。6、已知一棵二叉树的先序序列与中序序列分别为： 先序序列： A B C D E F G H I 中序序列： B C A E D G H F I试恢复该二叉树。并写出它的的后序遍历序列。7、已知一个无向图的顶点集为a,b,c,d,e,其邻接矩阵如下： 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0画出该图的图形。根据邻接矩阵写出从a出发进行深度优先搜索遍历的序列。8、设栈S中的数据是：2 4 6 8，写出当e=4时运行下列函数后栈S中的数据。void algo2(SqStack *S,int e)/利用辅助栈T删除S栈中的元素SqStack *T;int d;StackInitiate (T);while(StackNotEmpty(S)Pop(S,&d);if(d!=e) Push(T,d);while(StackNotEmpty(T)Pop(T,&d);Push(S,d);五、编程题：（10分）1、 用C语言写出快速排序算法。2、 用C语言写出二分查找算法。3、写出顺序表的插入、删除函数4、写出链表的插入、删除函数5、写出直接插入排序函数6、写出链队的出队