20秋广东开放大学数据结构形成性考核真题试题参考答案资料.docx

百年教育职业培训中心： / 广东开放大学 终结性考核 参考资料 百年教育职业培训中心编制 明世分校第一次实时讨论 1、数据的各种逻辑结构和物理结构以及它们之间的关系(数学模型)； 2、对各种结构定义相应的运算； 3、设计出相应的算法； 4、分析算法的效率。 明世分校第二次实时讨论 在日常生活中人们洗碗碟时总是后洗的碗碟放在先洗碗碟的上面而人们在使用碗碟时总是从上往下去取符合栈的“后进先出”的特性。而比如火车站排队买票先来者排在前面先购买车票后来者由队尾开始排队符合队列的“先进先出”的特性。 在日常生活中人们洗碗碟时,总是后洗的碗碟放在先洗碗碟的上面,而人们在使用碗碟时总是从上往下去取,符合栈的“后进先出”的特性。而比如火车站排队买票,先来者排在前面先购买车票,后来者由队尾开始排队,符合队列的“先进先出”的特性。 明世分校非实时讨论 数据的逻辑结构分两大类: 线性结构 和 非线性结构 数据的存储方法有四种: 顺序存储方法 、 链接存储方法 、 索引存储方法和散列存储方法 。 实现图像压缩静态哈夫曼编码介绍静态哈夫曼编码树的构造静态哈夫曼编码的具体编码过程静态哈夫曼编码的算法实例利用静态哈夫曼编码压缩与还原图像的C... 综合题库 选择题 题目：链接存储的存储结构所占存储空间（ ） 答案： A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 题目：线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 答案： A、连续或不连续都可以的 题目：顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。 答案： A、108 题目：线性表Ｌ在（ ）情况下适用于使用链式结构实现。 答案： A、需不断对Ｌ进行删除插入 题目：线性表L=(a1，a2,……an)，下列说法正确的是（ ）。 答案： A、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继 题目：单链表的存储密度（ ）。 答案： A、小于1 题目：在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动 答案： A、n-i+1 题目：在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。 答案： A、s-next=p-next; p-next=s; 题目：向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为 答案： A、63.5 题目：将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 答案： A、n 题目：设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（　　 ）。 答案： A、3 题目：若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。 答案： A、n-i+1 题目：一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（ ）。 答案： A、4，3，5，1，2 题目：设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳 答案： A、栈 题目：在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个 答案： A、队列 题目：一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（ ）。 答案： A、1，2，3，4 题目：栈和队列的主要区别在于（ ）。 答案： A、插入、删除运算的限定不一样 题目：一个递归算法必须包括（　）。 答案： A、终止条件和递归部分 题目：若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。 答案： A、top- -; V[top]=x; 题目：栈在 （ ）中有所应用。 答案： A、前三个选项都有 题目：对特殊矩阵采用压缩存储的目的主要是为了（　　　）。 答案： A、减少不必要的存储空间 题目：下面（　　　）不属于特殊矩阵。 答案： A、稀疏矩阵 题目：二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（　　　）个字节。 答案： A、540 题目：将数组称为随机存取结构是因为（　　　）。 答案： A、对数组任一元素的存取时间是相等的 题目：下面的说法中，不正确的是（　　　）。 答案： A、稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储 题目：串是一种特殊的线性表，其特殊性体现在（ ）。 答案： A、数据元素是一个字符 题目：下面关于串的的叙述中，（ ）是不正确的？ 答案： A、空串是由空格构成的串 题目：串的长度是指（ ）。 答案： A