算法与数据结构习题1.doc

算法与数据结构习题1一、单项选择题1. 数据结构从逻辑上分为（ ）。A动态结构和静态结构 B内部结构和外部结构C紧凑结构和非紧凑结构 D线性结构和非线性结构2. 栈和队列的共同点是（ ）。A都是先进后出 B都是后进先出C只允许在端点处插入和删除元素 D没有共同点3若按从左到右的顺序读入已知序列a、b、c、d、e、f、g中的元素，然后结合栈的操作，能得到下列序列中的哪些序列？（ ）Adecfbga Bfegdacb Cefdgbca Ddcbefag4. 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ ）。Aslink=plink；plink =s； Bplink =s；slink=q；Cplink=slink；slink =p； Dqlink =s；slink=p；5算法的计算量的大小称为计算的（ ）。A效率 B. 复杂性 C. 现实性 D. 难度6. 一个算法应该是（ ）。A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C7. 从逻辑上可以把数据结构分为（ ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构8. 以下数据结构中，哪一个是线性结构？（ ）A广义表 B. 二叉树 C. 稀疏矩阵 D. 串二、多项选择题1. 以下说法正确的是（ ）。A. 二叉树的特点是每个结点至多只有两棵子树B. 二叉树的子树无左右之分C. 二叉树只能进行链式存储D. 树的结点包含一个数据元素及若干指向其子树的分支2在数组上能做的操作有（ ）。 A.插入B.删除C.取值操作D.赋值操作3. 图的应用算法有（ ）。 A. 克鲁斯卡尔算法 B. 哈弗曼算法C. 迪杰斯特拉算法 D. 拓扑排序算法4. 计算机算法必须具备（ ）等特性。A. 可行性、确定性 B. 可行性、可移植性C. 输入、输出 D. 有穷性E. 易读性 F. 稳定性三、填空题1. 一个算法的效率可分为 效率和 效率。2. 向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动 个元素。3. 栈只能在 插入和删除元素；对于队列只能在 插入和 删除元素。4. 一棵具有257个结点的完全二叉树，它的深度为 。四、判断题1. 链表的每个结点中都恰好包含一个指针。（ ）2. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（ ）3. 数和二叉树都是分支结构。（ ）4. 优先队列是一种给每个元素增加了优先级的队列，它具有队列的基本特性。（ ）5. 数据元素是数据的最小单位。（ ）6. 记录是数据处理的最小单位。（ ） 7. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）五、简答题1. 能否讲二叉树是一种特殊的树？为什么？ 2. 在C语言中字符串可以用字符指针来表示。字符串的长度隐含在字符指针所指的字符数组中，通过特殊的字符0判定。写一个递归算法，以字符指针为参数，在屏幕上打印出它反转后得到的字符串。3. 算法与程序有什么区别？ 4. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。5. 什么是网络的最小生成树？6. 已知两个串为S1=“bc cad cabcadf”, S2=”abc”,试求两个串的长度，并判断S2串是否是S1串的子串；如果是，请指出S2在S1中的位置。算法与数据结构习题1答案 一、单项选择题题号12345678答案DCABBBCD二、多项选择题题号1234答案ADCDACDACD三、填空题题号答案1时间；空间2n-i+13栈顶；队尾；队首49四、判断题题号1234567答案五、简答题1. 答：不能。二叉树并不是树的特例。树和二叉树的定义及操作都是不同的，周游算法也有很大的区别。二叉树可以与一般树林建立对应，它的提出可以为研究树提供一种简单而统一的范型。2. 答：void printRevString(char *s) If(s0= =0)return; /*空串*/ If(s1= =0)putchar(s0); /*只有一个字符，直接打印*/ Else PrintRevString（s+1）；Putchar（s0）;3.答：算法与程序的关系十分密切，但并不等同。一般来说，一个程序并不需要满足算法的有穷性等条件，例如操作系统的程序，只要整个系统不遭到破坏，操作系统程序就永不结束。另外，程序是用机器可执行的语言书写的，而算法通常并没有这种限制。4. 答：DLR： A B D F J G K C E H I L M LDR： B F J D G K A C H E L I M LRD： J F K G D B H L M I E C A5. 答：因为网络是带权的连通图，其生成