《年国家开放大学电大数据结构题库.docx》由会员分享，可在线阅读，更多相关《年国家开放大学电大数据结构题库.docx（61页珍藏版）》请在金锄头文库上搜索。
1、年国家开放大学电大数据结构题库 数据结构课程平时作业 1 一单项选择题 1数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 A操作对象 B计算方法 C逻辑存储 D数据映象 A结构 B关系 C运算 D算法 2数据结构被形式地定义为（K，R），其中 K 是的有限集合，R 是 K 上的的有限集合。 A算法 B数据元素 C数据操作 D逻辑结构 A操作 B映象 C存储 D关系 3在数据结构中，从逻辑上可以把数据结构分成( )。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构 4. 线性结构是数据元素之间存在一种： A）一对多关
2、系 B）多对多关系 C）多对一关系 D）一对一关系 5. 数据结构中，与所使用的计算机无关的是数据的 结构； A) 存储 B) 物理 C) 逻辑 D) 物理和存储 二. . 填空题（将正确的答案填在相应的空中） 1在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 2在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续结点可以。 3在图形结构中，每个结点的前驱结点数和后续结点数可以。 4线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 5.
3、数据结构包括数据的 、数据的 和数据的 这三个方面的内容。 6下面程序段的时间复杂度是。 for（i=0；in；i+） for（j=0；jm；j+） Aij=0； 7下面程序段的时间复杂度是。 S0； for（i=0；in；i+） for（j=0; jn; j+） s+=bij； sum=s; 三、简答题 1. 数据结构是一门研究什么内容的学科？ 2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 3.设有数据逻辑结构 S=（D,R），试按题所给条件画出这些逻辑结构的图示，并确定相对于关系 R，哪些结点是开始结点，哪些结点是终端结点？ D=d1,d2,d3,d4 R=(d1,d2
4、),(d2,d3),(d3,d4) 部分 参考答案 一、单选题 1A B 2. B D 3. C 4. D 5. C 二、填空题 1. 无，1，无，1 2. 前驱，1 个 ，后继，多个 3. 多个 4. 一对一，一对多，多对多 5. 逻辑结构、物理结构、数据运算 6. O(n*m) 7. O(n*n) 三、简答题 1. 略 见课件 2. 略 3d1 d2d3d4 线性结构 数据结构课程平时作业 2 一单项选择题 1.线性表 L=（a 1 , a 2 ,an ）,下列说法正确的是 （ ）。 A每个元素都有一个直接前驱和一个直接后继。 B线性表中至少要有一个元素。 C表中诸元素的排列顺序必须是由小
5、到大或由大到小。 D除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。 2. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。 A插入 B删除 C排序 D定位 3. 在一个长度为 n 的顺序表中，在第 i 个元素（1 = i =n+1）之前插入一个新元素时需向后移动（ ）个元素 An-1 Bn-i+1 Cn-i-1 DI 4.一个数组第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个 元素的地址是（ ） A110 B108 C100 D120 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 A必须是连续的 B部分
6、地址必须是连续的 C一定是不连续的 D连续或不连续都可以 6.在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p之间插入 s 结点，则执行语句（ ）。 As-next=p-next;p-next=s; Bp-next=s-next;s-next=p; Cq-next=s;s-next=p; Dp-next=s;s-next=q; 7若已知一个栈的进栈序列是 1，2，3，n，其输出序列为 p1，p2，p3，.，pn，若 p13，则 p2 为( )。 A 可能是 2 B 一定是 2 C 可能是 1 D 一定是 1 8. 有六个元素 6，5，4，3，2，1 的顺序进栈，问
7、下列哪一个不是合法的出栈序列？（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 9.设有一顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次进栈，如果 6 个元素出栈的顺序是 s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是( ) A.2 B. 3 C. 5 D.6 10. 若栈采用顺序存储方式存储，现两栈共享空间 V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）。 A. |top2-top1|=0 B. top1+1=top2 C. t
8、op1+top2=m D. top1=top2 二. . 填空题（将正确的答案填在相应的空中） 1. 向一个长度为 n 的向量中删除第 i 个元素（1in）时，需向前移动_ 个元素。 2. 带头结点的单链表 head 为空的判定条件是 。 3. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为 。 4. 线性表（a, a,a）以链接方式存储时，访问第 i 位置元素的时间复杂性为 。 5.栈是 的线性表，其运算遵循 的原则。 6.一个栈的输入序列是：1，2，3 则不可能的栈输出序列是 。 7.用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到1342 出栈
9、顺序，相应的 S 和 X 的操作串为 。 8.队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 。 部分参考答案 三、单选题 1D 2. D 3. B 4. B 5. D 6. C 7.A 8.C 9.B 10.B 四、填空题 1. n-i 2.head-next= =NULL 3. O(n) 4.O(1) 5. 访问受限，后进先出 6. 3,1,2 7. S XSSXSXX 8.先进先出 数据结构课程平时作业 3 一单项选择题 1下面关于串的的叙述中，哪一个是不正确的？（ ） A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序
10、存储，也可以采用链式存储 2串是一种特殊的线性表，其特殊性体现在（ ）。 A可以顺序存储 B数据元素是一个字符 C可以链接存储 D数据元素可以是多个字符 3串的长度是指（ ） A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符的个数 D串中所含非空格字符的个数 4设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（ ） A求子串 B联接 C匹配 D求串长 5若串 S=software,其子串的个数是（ ）。 A8 B37 C36 D9 6. 广义表（a,b,c,d）的表头是（ ），表尾是（ ）。 A. a B.（） C.（a,b,c,d
11、） D.（b,c,d） 7. 设广义表 L=（a,b,c），则 L 的长度和深度分别为（ ）。 A. 1 和 1 B. 1 和 3 C. 1 和 2 D. 2 和 3 8.设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a85 的地址为（ ）。 A. 13 B. 33 C. 18 D. 40 9. 设有数组 Ai,j，数组的每个元素长度为 3 字节，i 的值为 1 到 8 ，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 10. 假设以行序为主序存储二维数组 A=array1.100，1.100，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC5，5=（ ）。 A. 808 B. 818 C. 1010 D. 1020 二. . 填空题（将正确的答案填在相应的空中） 1含零个字符的串称为( )串。任何串中所含( )的个数称为该串的长度。 2当且仅当两个串的( )相等并且各个对应位置上的字符都( )时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的( )串。 3INDEX（DATASTRUCTURE， S
