数据结构试题(C)

《数据结构》试题（100分）（供2005级信息管理与信息系统本科专业使用）学号：姓名：座号：系别：年级：专业：题号一二三四五六七八总计得分总分合计人：复核人：说明：本试卷分为两部分，第I卷（选择题和判断题）必须在“答题卡”上按规定要求填、涂；第II卷直接在试卷上作答。不按规定答题、填涂，一律无效。第I卷得分评卷人一、试题类型：单项选择题（每小题2分，共40分）（类型说明：在每小题列出的四个选项中只有一个选项是符合题目要求的，请选出正确选项并在“答题卡”的相应位置上涂黑。多涂、少涂、错误均无分。）1.算法分析的两个主要方面是：（）（A)空间复杂性和时间复杂性（B)正确性和简明性（C)可读性和文档性（D)数据复杂性和程序复杂性2.计算机算法指的是：（）（A)计算方法（B)排序方法（C)解决问题的有限运算序列（D)调度方法3．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为：（）（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构4.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是。（）（A）110（B）108（C）100（D）1205.链接存储的存储结构所占存储空间：（）（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数6.线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（）（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以7.栈中元素的进出原则是：（）（Ａ）先进先出（Ｂ）后进先出（Ｃ）栈空则进（Ｄ）栈满则出8.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为：（）（Ａ）i（Ｂ）n=i（Ｃ）n-i+1（Ｄ）不确定9.串是一种特殊的线性表，其特殊性体现在：（）（Ａ）可以顺序存储（Ｂ）数据元素是一个字符（Ｃ）可以链式存储（Ｄ）数据元素可以是多个字符10.设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：（）（Ａ）BCDEF（Ｂ）BCDEFG（Ｃ）BCPQRST（Ｄ）BCDEFEF11.假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。（无第0行第0列元素）（）（Ａ）16902（Ｂ）16904（Ｃ）14454（Ｄ）答案A,B,C均不对12．二叉树是非线性数据结构，所以。（）（Ａ）它不能用顺序存储结构存储;（Ｂ）它不能用链式存储结构存储;（Ｃ）顺序存储结构和链式存储结构都能存储;（Ｄ）顺序存储结构和链式存储结构都不能使用13.具有n(n0)个结点的完全二叉树的深度为。（）(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+114．把一棵树转换为二叉树后，这棵二叉树的形态是。（）（Ａ）唯一的（Ｂ）有多种（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子15.已知图的邻接表如下所示，则从顶点0出发按深度优先遍历的结点序列是（）16.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）17．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。（）（A）20，70，30，50（B）30，88，70，50（C）20，50（D）30，88，5018．链表是一种采用存储结构存储的线性表。（）（A）顺序（B）链式（C）星式（D）网状19．不含任何结点的空树。（）（Ａ）不是一棵树;（Ｂ）不是一棵二叉树;（Ｃ）是一棵树也是一棵二叉树;（Ｄ）既不是树也不是二叉树20．在一个图中，所有顶点的度数之和等于图的边数的倍。（）A．1/2B.1C.2D.4得分评卷人二、试题类型：判断题（每小题1分，共10分）（类型说明：判断正确答案，选项并在“答题卡”的相应位置填涂，认为正确的涂“A”错误的涂“B”。多涂、少涂、错误均无分。）21.二叉树中每个结点的两棵子树是有序的。（）22.顺序存储方式只能用于存储线性结构。（）23.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（）24.栈和队列的存储方式既可是顺序方式，也可是链接方式。（）25.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（）26.队列是一种先进后出型结构。（）27.一个栈的输入序列是12345，则栈的输出序列不可能是12345。（）28.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）29.线性表在物理存储空间中也一定是连续的。（）30.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）（A）0132（B）2031（C）1320（D）0123（A）0321（B）1230（C）3210（D）3012第II卷得分评卷人三、试题类型：填空题（每空1分，共10分）（类型说明：请将正确答案填于试题预留的横线上。）31.栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。32.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。33.向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。34.假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为。35.设S=“A;/document/Mary.doc”，则strlen(s)=,“/”的字符定位的位置为。得分评卷人四、试题类型：简答题（每小题5分，共30分）（类型说明：）36.已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。37.用三元组表表示下列稀疏矩阵：00000300000000050000000000000920000038.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。39.把如图所示的树转化成二叉树。40.已知如图所示的有向图，请给出该图的邻接表。41.请对下图的无向带权图，求其最小生成树；得分评卷人五、试题类型：分析题（每小题5分，共5分）（类型说明：）42.已知一组关键字序列：493865971327按照快速排序方法对此序列进行排序，写出每趟排序的结果。得分评卷人六、试题类型：编程题（每小题5分，共5分）（类型说明：）43.设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。顺序表的存储结构如下：typedefstruct{ElemType*elem;//指向存放线性表中数据元素的基地址intlength;//线性表的当前长度intlistsize;//当前分配的存储容量}SqList；StatusInsertSqList(SqList&va,intx)//把x插入递增有序表va中{if(va.length+1va.listsize)returnERROR;《数据结构》A卷信管本科专业标准答案及评分标准（按试题顺序排列）一、单项选择题（每小题2分，共40分）1、A2、C3、C4、B5、A6、D7、B8、C9、B10、D11、A12、C13、C14、A15、D16、A17、A18、B19、C20、C二、判断题（每小题1分，共10分）21.A22.B23.B24.A25.B26.B27.B28.A29.B30.B三、填空题（每空1分，共10分）31.栈顶栈底32.n-i+133.n-i34.288B12821072127635.203四、简答题（每小题5分，共30分）36.Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K37.38.先序：ABDFJGKCEHILM---------2分中序:BFJDGKACHELIM----------2分后序：JFKGDBHLMIECA----------1分39.40.41.66416-2259435653五、试题类型：分析题（每小题5分，共5分）42.初始序列：493865971327第一趟排序结果：273813499765第二趟排序结果：132738496597六、试题类型：编程题（每小题5分，共5分）43.va.length++;for(i=va.length-1;va.elem[i]x&&i=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;returnOK;}《数据结构》试题（100分）（供2005级信息管理与信息系统本科专业使用）学号：姓名：座号：系别：年级：专业：题号一二三四五六七八总计得分总分合计人：复核人：说明：本试卷分为两部分，第I卷（选择题和判断题）必须在“答题卡”上按规定要求填、涂；第II卷直接在试卷上作答。不按规定答题、填涂，一律无效。第I卷得分评卷人一、试题类型：单项选择题（每小题2分，共40分）（类型说明：在每小题列出的四个选项中只有一个选项是符合题目要求的，请选出正确选项并在“答题卡”的相应位置上涂黑。多涂、少涂、错误均无分。）1.非线性结构是数据元素之间存在一种。()(A)一对多关系(B)多对多关系(C)多对一关系(D)一对一关系2.数据结构中，与所使用的计算机无关的是数据的结构。()（A）存储（B）物理（C）逻辑（D）物理和存储3.算法分析的两个主要方面是。（）（A）空间复杂性和时间复杂性（B）正确性和简明性（C）可读性和文档性（D）数据复杂性和程序复杂性4.计算机算法指的是。()（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法5.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为。()（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构6.一个向量第一个元素的存储地址是500，每个元素的长度为2，则第10个元素的地址是。()（A）510（B）508（C）518（D）5207.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是。()（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）（B）在第i个结点后插入一个新结点（1≤i≤n）（C）删除第i个结点（1≤i≤n）（D）将n个结点从小到大排序8.线性表若采用链式存储结构时，要求内存中可用存储单元的地址。()（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以9.线性表Ｌ在情况下适用于使用链式结构实现。()（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂10.栈中元素的进出原则是。()(Ａ)先进先出(Ｂ)后进先出(Ｃ)栈空则进(Ｄ)栈满则出11.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。()（Ａ）i（Ｂ）n=i（Ｃ）n-i+1（Ｄ）不确定12.设有两个串p和q，求q在p中首次出现的位置的运算称作。()（Ａ）连接（Ｂ）模式匹配（Ｃ）求子串（Ｄ）求串长13