年国家开放大学电大数据结构题库

本文格式为Word版，下载可任意编辑 年国家开放大学电大数据结构题库 数据结构课程平日作业 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）一对多关系 　B）多对多关系 C）多对一关系 D）一对一关系 5. 数据结构中，与所使用的计算机无关的是数据的 　结构； A) 存储 　 B) 物理 　 C) 规律 　 D) 物理和存储 　 二. . 填空题（将正确的答案填在相应的空中） 　1．在线性结构中，第一个结点①前驱结点，其余每个结点有且只有②个前驱结点；结果一个结点③后续结点，其余每个结点有且只有④个后续结点。 　2．在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后续结点可以④。 　3．在图形结构中，每个结点的前驱结点数和后续结点数可以①。 　4．线性结构中元素之间存在①关系，树形结构中元素之间存在②关系，图形结构中元素之间存在③关系。 　5. 数据结构包括数据的 　 、数据的 　 和数据的 　 这三个方面的内容。 　6．下面程序段的时间繁杂度是①。 　 for（i=0；i＜n；i++） 　 for（j=0；j＜m；j++） 　 A[i][j]=0； 7．下面程序段的时间繁杂度是①。 　 S＝0； 　for（i=0；in；i++） 　 for（j=0; jn; j++） 　 s+=b[i][j]； 　 sum=s; 　 三、简答题 　1. 数据结构是一门研究什么内容的学科？ 2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 3.设有数据规律结构 S=（D,R），试按题所给条件画出这些规律结构的图示，并确定相对于关系 R，哪些结点是开始结点，哪些结点是终端结点？ 　 D={d1,d2,d3,d4} 　 R={(d1,d2),(d2,d3),(d3,d4) } 　部分 参考答案 一、单项选择题 1．A 　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. 略 　 3．d1à d2àd3àd4 　 线性结构 　数据结构课程平日作业 2 一．单项选择题 　1.线性表 L=（a 1 , a 2 ,,an ）,以下说法正确的是 （ 　 ）。 　A．每个元素都有一个直接前驱和一个直接后继。 　B．线性表中至少要有一个元素。 　C．表中诸元素的排列顺序必需是由小到大或由大到小。 　D．除第一个和结果一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。 　2. 在线性表的以下运算中，不改变数据元素之间结构关系的运算是（ 　）。 　A．插入 　B．删除 C．排序 　D．定位 3. 在一个长度为 n 的顺序表中，在第 i 个元素（1 = i =n+1）之前插入一个新元素时需向后移动（ ）个元素． A．n-1 　B．n-i+1 　 C．n-i-1 　D．I 4.一个数组第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个 　元素的地址是（ 　） 　A．110 　 B．108 　 C．100 　 D．120 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ 　）。 　A．必需是连续的 　B．部分地址必需是连续的 C．一定是不连续的 　D．连续或不连续都可以 6.在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p之间插入 s 结点，则执行语句（ 　）。 　A．s-next=p-next;p-next=s; 　 B．p-next=s-next;s-next=p; 　C．q-next=s;s-next=p; 　D．p-next=s;s-next=q; 7．若已知一个栈的进栈序列是 1，2，3，，n，其输出序列为 p1，p2，p3，...，pn，若 p1＝3，则 p2 为( 　 )。 　A 可能是 2 　B 一定是 2 　C 可能是 1 　D 一定是 1 　8. 有六个元素 6，5，4，3，2，1 的顺序进栈，问以下哪一个不是合法的出栈序列？（ 　） 　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. 若栈采用顺序存储方式存储，现两栈共享空间 V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ 　）。 　A. |top[2]-top[1]|=0 　 B. top[1]+1=top[2] 　 C. top[1]+top[2]=m 　 D. top[1]=top[2] 　二. . 填空题（将正确的答案填在相应的空中） 　1. 向一个长度为 n 的向量中删除第 i 个元素（1in）时，需向前移动_______ 　个元素。 　2. 带头结点的单链表 head 为空的判定条件是 　。 　3. 对于顺序存储的线性表，访问结点和增加、删除结点的时间繁杂度为 　 。 　4. 线性表（a, a,,a）以链接方式存储时，访问第 i 位置元素的时间繁杂性为 　。 　5.栈是 　 的线性表，其运算遵循 　的原则。 　 6.一个栈的输入序列是：1，2，3 则不可能的栈输出序列是 　。 　 7.用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到1342 出栈顺序，相应的 S 和 X 的操作串为 　。 　 8.队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 　。 　部分参考答案 三、单项选择题 1．D 　 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．串既可以采用顺序存储，也可以采用链式存储 　2．串是一种特别的线性表，其特别性表达在（ 　）。 　A．可以顺序存储 　B．数据元素是一个字符 　C．可以链接存储 　D．数据元素可以是多个字符 　3．串的长度是指（ 　） 　A．串中所含不同字母的个数 　B．串中所含字符的个数 　C．串中所含不同字符的个数 　D．串中所含非空格字符的个数 　4．设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（ 　） 　A．求子串 　 B．联接 　 C．匹配 　 D．求串长 　5．若串 S="software',其子串的个数是（ 　）。 　A．8 　 B．37 　 C．36 　 D．9 6. 广义表（（a,b,c,d））的表头是（ 　），表尾是（ 　）。 　A. a 　 B.（） 　 C.（a,b,c,d） 　 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. 设有数组 A[i,j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8 ，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( 　)。 　A. BA+141 　B. BA+180 　 C. BA+222 　 D. BA+225 10. 假设以行序为主序存储二维数组 A=array[1..100，1..100]，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC[5，5]=（ 　）。 　A. 808 　B. 818 　C. 1010 　 D. 1020 　二. . 填空题（将正确的答案填在相应的空中） 　1．含零个字符的串称为( 　 )串。任何串中所含( 　)的个数称为该串的长度。 　 2．当且仅当两个串的( 　 )相等并且各个对应位置上的字符都( 　)时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的(