数据结构C语言版期末考试试题(有答案)(一).pdf

“数据结构”期末考试试题一、单选题(每小题2 分，共 12分)1.在一个单链表H L 中，若要向表头插入一个由指针p 指向的结点，则执行()。A.H L=p s p 一n ex t=H LB.p n ex t =H L；H L=p 3C.p-n ex t=H l；p =H L；D.p 一n ex t=H L 一 n ex t ;H L 一n ex t=p；2.n 个顶点的强连通图中至少含有()。A.n l 条有向边 B.n 条有向边C.n(n l)/2 条有向边 D.n(n 1)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为()0A.0(1)B.0(n)C.0(10 g z n)D.0(n 2)4.由权值分别为3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A.24 B.4 8C.72 D.535.当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为()参数，以节省参数值的传输时间和存储参数的空间。A.整形 B.引用型C.指针型 D.常值引用型6.向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为()。A.0(n)B.0(1)C.0(n 2)D.0(10 g 2n)二、填空题(每空1 分，共 28分)1.数据的存储结构被分为一一、一一、一一和一一四种。2.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为一一域和一一域。3.中缀表达式3 十 x*(2.4/56)所对应的后缀表达式为-。4 .在一棵高度为h的 3 叉树中，最多含有结点。5.假定一棵二叉树的结点数为18,则它的最小深度为一一，最大深度为-6.在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定一一该结点的值，右子树上所有结点的值一定一一该结点的值。7.当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层一一调整,直到被调整到一一位置为止。8.表示图的三种存储结构为、和-。9.对用邻接矩阵表示的具有n个顶点和e 条边的图进行任一种遍历时，其时间复杂度为一一，对用邻接表表示的图进行任一种遍历时，其时间复杂度为一一。10 .从有序表(12,18,30,4 3,56,78,82,95)中依次二分查找4 3和 56元素时，其查找长度分别为-和-11.假定对长度n=14 4 的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为一一，时间复杂度为-12.一棵B一树中的所有叶子结点均处在一一上。13.每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做一一排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做一一排序。14.快速排序在乎均情况下的时间复杂度为一一，最坏情况下的时间复杂度为一一o三、运算题(每小题6 分，共 24分)1.假定一棵二叉树广义表表示为a(b(c,d),c(,8),分别写出对它进行先序、中序、后序和后序遍历的结果。先序：中序；后序：2.已知一个带权图的顶点集V 和边集G 分别为：V=0,1,2,3,4,5；E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10,则求出该图的最小生成树的权。最小生成树的权；3.假定一组记录的排序码为(46,79,56,38,40,84,50,42),则利用堆排序方法建立的初始堆为一一。4.有 7 个带权结点，其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。带权路径长度：一 一 高度：一 一 双分支结点数：一一。四、阅读算法，回答问题(每小题8 分，共 16分)1.VOldAC(List&L)(InitList(L)；InsertRear(L;25)；InsertFront(L,50)；lntaL4=5,8,12,15,36;for(inti=0;i5;i+)if(ai%2=0)InsertFront(L,ai)；elselnsertRear(L,ai)；该算法被调用执行后，得到的线性表L 为：2.void AG(Queue&Q)(InitQueue(Q)；inta5=6,12,5,15,8；for(int i=0;i5;i+)QInsert(Q,ai)；QInsert(Q,QDelete(Q)；Q I ns ert(Q,2 0)；Q I ns ert (Q,Q D elet e(Q)十 1 6)；w hile(!Q u eu eE mpt y(Q)c ou t Q D elet e(Q)”；该算法被调用后得到的输出结果为：五、算法填空，在画有横线的地方填写合适的内容(每小题6 分，共 1 2 分)1 .从一维数组A n)中二分查找关键字为K 的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一 1。I nt B ins c h(E lemT y peA,I nt low,int high,Key T y peK)if(low =high)(int mid=(low+high)/2；if(K=A mid.key)-；els e if(K dat a=X)ret u rn 1;/根结点的层号为 1/向子树中查找x 结点els e int c l=N odeL ev el(B T 一 left,X)；if(c l =1)ret u rn c l+1;int c 2=；if-;/若树中不存在X 结点则返回。els e ret u rn 0；六、编写算法(8 分)按所给函数声明编写一个算法,从表头指针为H L 的单链表中查找出具有最大值的结点，该最大值由函数返回，若单链表为空则中止运行。E lemT y pe M ax Valu e(L N O de*H L);“数据结构”期末考试试题答案一、单选题（每小题2 分，共 1 2 分）评分标准；选对者得2 分，否则不得分。1.B 2.B 3.C 4.D 5.B 6.A二、填空题（每空1 分，共 2 8 分）1 .顺序结构 链接结构 索引结构 散列结构（次序无先后）2 .值（或 dat a）子表指针（或 s u blis t）3 .3 x 2.4 5/6 一*十4 .（3h-1）/25 .5 1 86 .小于 大于（或大于等于）7 .向上 堆顶8 .邻接矩阵 邻接表 边集数组（次序无先后）9 .0（n2）0（e）10 .1 311.13 0()12.同一层13.插人 选择14.0 (n l o g2n)0(n2)三、运算题（每小题6 分，共 24分）1.先序：a,b,c,d,e,f,e中序：c,b,d,a,f,8,e后序：c,d,b,e,f,e,a2.最小生成树的权：31/2 分223.(84,7 9,56,42,40,46,/分50,3864.带权路径长度：131/3 分高度：5/2 分双分支结点数：6/1 分四、阅读算法，回答问题（每小题8 分，共 16分）评分标准：每小题正确得8 分，出现一处错误扣4 分，两处及以上错误不得分。1.(36,12,8,50,25,5,15)2.5 15 8 6 20 28五、算法填空，在画有横线的地方填写合适的内容(每小题6 分，共 12分)1.f e tur n m i d /2 分r e tur n B i n s c h (A,l o w,m i d 一 1,K)/2 分r e tur n B m s c h(A,m i d+1,h i g h,K)/2 分2.N o d e L e ve l (B T 一r i g h t,X)/3 分(c 2=l)r e tur n c 2 十 1 /3 分六、编写算法(8分)评分标准：请参考语句后的注释，或根据情况酌情给分。E l e m T yp e M a xV a l ue(L N o d e O*H L。)(i f (H L=N U 1L)/2 分c e r r ，L i n k e d l i s t i s e m p ty!”n e xt；/4 分wh i l e(P!：N U L L)/7 分i f (m a x d a ta)m a x=p 一 d a ta；p =p -n e xt；)r e tur n m a x；/8 分数据结构复习资料一、填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的以 及 它 们 之 间 的 关系 和运算等的学科。2.数据结构被形式地定义为（D,R）,其 中 D是 数据元素 的有限集合,R是 D上 的 关 系 有限集合。3.数据结构包括数据的逻 辑 结 构、数 据 的 存 储 结 构 和 数 据 的 运算这三个方面的内容。4.数据结构按逻辑结构可分为两大类，它 们 分 别 是 线 性 结 构 和非线性结_ _ _ _ o5.线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。6.在线性结构中，第 一 个 结 点 没 有 前驱结点,其余每个结点有且只有1个前驱结点；最后一个结点 没有 后续结点,其余每个结点有且只有1个后续结点。7 .在树形结构中，树根结点没有前 驱 结点,其余每个结点有且只有 1 个前驱结点；叶子结点没有后续 结点,其余每个结点的后续结点数可以任意多个 08.在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个。9 .数据的存储结构可用四种基本的存储方法表示，它们分别是顺 序、链 式、索引 和 散 歹 U 。10 .数据的运算最常用的有5 种，它们分别是插 入、删除、修改、查 找、排序。1 1 .一个算法的效率可分为时间 效 率 和 空 间 效率。1 2 .在顺序表中插入或删除一个元素，需要平均移动表中一半元素,具体移动的元素个数与表长和该元素在表中的位置有关。1 3 .线性表中结点的集合是有限 的,结 点 间 的 关 系 是 一 对 一 的。1 4 .向一个长度为n的向量的第i 个元素(l W i W n+1)之前插入一个元素时，需向后移动n-i+l 个元素。1 5 .向一个长度为n的向量中删除第i 个元素(l W i W n)时，需向前移动n-i个元素。1 6 .在顺序表中访问任意一结点的时间复杂度均为3_，因此，顺序表也称为_随 机 存 取 的数据结构。1 7 .顺序表中逻辑上相邻的元素的物理位置上维 相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。1 8.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域 的 值 指示。1 9 .在 n 个结点的单链表中要删除已知结点*p,需找到它的前驱结点的地址,其时间复杂度为0 （n）。2 0 .向量、栈和队列都是 线性 结构,可以在向量的 任何 位置插入和删除元素；对 于 栈 只 能 在 栈 顶 插入和删除元素:对于队列只能在队尾 插入和 队 首 删除元素。2 1 .栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶。不允许插入和删除运算的一端称为 栈底。2 2 .队列 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。2 3 .不包含任何字符（长度为0）的串 称为空串:由一个或多个空格（仅由空格符）组成的串 称为空白串。2 4 .子串的定位运算称为串的模式匹配；被匹配的主串 称为目标串,子串称为模式。2 5 .假设有二维数组A 6 X 8,每个元素用相邻的6 个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为 1 0 0 0,则数组A的体积（存储量）为 2 88 B ；末尾元素A 5 7 的第一个字节地址为 1 2 82 ；若按行存储时，元素心 的第一个字 节 地 址 为（8+4）X 6+1 0 0 0=1 0 7 2 ；若按列存储时，元素A 4 7 的第一个字节地址为（6 X 7+4）X 6+1 0 0 0）=1 2 7 6 。2 6 .由3 个结点所构成的二叉树有 5 种形态。2 7 .一棵深度为6的满二叉树有m+m R+n-l=3 1 个分支结点和2 6 T=3 2个叶子。注：满二叉树没有度为1 的结点，所以分支结点数就是二度结点数。2 8.一棵具有2 5 7 个结点的完全二叉树，它的深度为 9 。(注：用L l o g2(n)J+l=L 8.x x J+l=92 9 .设一棵完全二叉树有7 0 0 个结点，则 共 有 350个叶子结点。答：最快方法：用叶子数=5/2 =3 5 03 0 .设一棵完全二叉树具有1 0 0 0 个结点，则 此 完 全 二 叉 树 有 个 叶 子 结 点，有4 9 9 个度为2的结点,有 1 个结点只有非空左子树,有3 个结点只有非空右子树。答：最快方法：用叶子数=n/2 =5 0 0 ,n2=n0-l=4 9 9 o 另外，最后一结点为2 i属于左叶子，右叶子是空的，所以有1 个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数=0.3 1 .在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找(线性查 找)。3 2 .线性有序表(a”a2,a3,a2 5 6)是从小到大排列的，对一个给定的值k,用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 一 次。设有1 0 0 个结点，用二分法查找时，最大比较次数是。3 3 .假设在有序线性表a 2 0 上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为二;比较四次查找成功的结点数为 ;平均查找长度为 3.7 。解：显然，平均查找长度=0 (l o g z n)t o p 0 B .ST-t o p=0 C .ST-t o p O m OD.ST-t o p=m O(C )1 8.在一个图中，所有顶点的度数之和等于图的边数的 倍。A.1/2 B.1 C.2 D.4(B )1 9.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A.1/2 B.1 C.2 D.4(B )2 0.有 8 个结点的无向图最多有 条边。A.1 4 B.2 8 C.5 6 D.1 1 2(C )2 1.有 8 个结点的有向完全图有 条边。A.1 4 B.2 8 C.5 6 D.1 1 2(B )2 2.在表长为n的链表中进行线性查找，它的平均查找长度为A.AS L=n;B.A S L=(n+1 )/2 ;C.AS L=M+1;D.AS Ll og2(n+1)-1(A )2 3.折半查找有序表(4,6,1 0,1 2,2 0,3 0,5 0,7 0,8 8,1 0 0)。若查找表中元素5 8,则它将依次与表中 比较大小，查找结果是失败。A.2 0,7 0,3 0,5 0 B.3 0,8 8,7 0,5 0 C.2 0,5 0 D.3 0,8 8,5 0(C )2 4.对 2 2 个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。A.3 B.4 C.5 D.6(A)2 5.链表适用于 查找A.顺序 B.二分法 C.顺序，也能二分法 D.随机 数据结构与算法复习题一、选择题。1 .在数据结构中，从逻辑上可以把数据结构分为 C 。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构2 .数据结构在计算机内存中的表示是指 oA.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系3 .在数据结构中，与所使用的计算机无关的是数据的 A 结构。A.逻辑 B.存储 C.逻辑和存储 D.物理4 .在存储数据时一，通常不仅要存储各数据元素的值，而且还要存储 C 。A.数据的处理方法 B.数据元素的类型C.数据元素之间的关系 D.数据的存储方法5 .在决定选取何种存储结构时，一般不考虑 AA.各结点的值如何 B.结点个数的多少C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。6.以下说法正确的是 _oA.数据项是数据的基本单位B.数据元素是数据的最小单位C.数据结构是带结构的数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构7 .算法分析的目的是C ,算法分析的两个主要方面是(1)A.找出数据结构的合理性C.分析算法的效率以求改进(2)A.空间复杂度和时间复杂度C.可读性和文档性8 .下面程序段的时间复杂度是0(/)s =0;f o r(I =0;i n;i+)f o r(j=0;j n;j+)s +=B i j ;B.研究算法中的输入和输出的关系C.分析算法的易读性和文档性B .正确性和简明性D.数据复杂性和程序复杂性s u m =s ;9 .下面程序段的时间复杂度是0(n*m)f o r(i =0;i n;i+)f o r(j=0;j m;j+)A i j =0;1 0 .下面程序段的时间复杂度是0(log3n)oi =0；w h i l e (i next=NULLC.head-next=head D head!=NULL15.带头结点的单链表head为空的判定条件是 B。A.head=NULL B head-next=NULLC.head-next=head D head!=NULL16.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用D 存储方式最节省运算时间。A.单链表 B.给出表头指针的单循环链表 C.双链表 D.带头结点的双循环链表17.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是B oA.单链表 B.静态链表 C.线性链表 D.顺序存储结构18.非空的循环单链表head的尾结点（由p 所指向）满足oA.p-next=NULL B.p=NULLC.p-next=head D.p=head19.在循环双链表的p 所指的结点之前插入s 所指结点的操作是 D。A.p-prior=s；s-next=p；p-prior-next=s；s-prior=p-priorB.p-prior=s；p-prior-next=s；s-next=p；s-prior=p-priorC.s-next=p；s-prior=p-prior；p-prior=s；p-prior-next=sD.s-next=p；s-prior=p-prior；p-prior-next=s；p-prior=s20.如果最常用的操作是取第i个 结 点 及 其 前 驱,则 采 用 存 储 方 式 最 节 省 时 间。A.单链表 B.双链表 C.单循环链表 D.顺序表21.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂 度 是B_oA.0(1)B.0(n)C.0(n2)D.0(nlog2n)22.在一个长度为n(nl)的单链表上，设有头和尾两个指针，执行 L操作与链表的长度有关。A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素23.与单链表相比，双链表的优点之一是D。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活24.如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用 B 。A.只有表头指针没有表尾指针的循环单链表B.只有表尾指针没有表头指针的循环单链表C.非循环双链表D.循环双链表2 5.在长度为n的顺序表的第i 个位置上插入一个元素(1 W i W n+1),元素的移动次数为：A oA.n -i +1 B.n -i C.i D.i -12 6 .对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为A.顺序表 B.用头指针表示的循环单链表C.用尾指针表示的循环单链表 D.单链表2 7 .下述哪一条是顺序存储结构的优点？CA 插入运算方便 B 可方便地用于各种逻辑结构的存储表示C 存储密度大 D 删除运算方便2 8 .下面关于线性表的叙述中，错误的是哪一个？BA 线性表采用顺序存储,必须占用一片连续的存储单元B 线性表采用顺序存储,便于进行插入和删除操作。C 线性表采用链式存储,不必占用一片连续的存储单元D 线性表采用链式存储,便于进行插入和删除操作。2 9 .线性表是具有n 个 B 的有限序列。A.字符 B.数据元素 C.数据项D.表元素3 0 .在n 个结点的线性表的数组实现中，算法的时间复杂度是0(1)的 操 作 是 oA.访问第i (l =i =n)个结点和求第i 个结点的直接前驱(l i =n)B.在第i (l =i =n)个结点后插入一个新结点C.删除第i (l =i n e x t=s；s-n e x t=p-n e x tB.s-n e x t=p-n e x t ；p-n e x t=s;C.p-n e x t=s；p-n e x t=s-n e x tD.p-n e x t=s-n e x t；p-n e x t=s3 6 .线性表的顺序存储结构是一种oA.随机存取的存储结构 B.顺序存取的存储结构C.索引存取的存储结构 D.H a s h 存取的存储结构3 7 .栈的特点是 B ,队列的特点是 A oA.先进先出 B.先进后出3 8 .栈和队列的共同点是。A.都是先进后出 B.都是先进先出C.只允许在端点处插入和删除元素 D.没有共同点3 9 .一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是 C 。A.e d c b a B.d e c b a C.d c e a b D.a b c d e4 0 .设有一个栈，元素依次进栈的顺序为A、B、C、D、E。下列 C 是不可能的出栈序列。A.A,B,C,D,E B.B,C,D,E,A C.E,A,B,C,D D.E,D,C,B,A4 1 .以下 B 不是队列的基本运算?A.从队尾插入一个新元素 B.从队列中删除第i 个元素C.判断一个队列是否为空 D.读取队头元素的值42.若已知一个栈的进栈序列是1,2,3,n,其输出序列为pl,p2,p3,pn,若 pl=n,贝pi 为 C。A.i B.n i C.n i +1 D.不确定43.判定一个顺序栈st（最多元素为MaxSize）为空的条件是。A.st-top!=-1 B.st-top=-1C.st-top!=MaxSize D.st-top=MaxSize44.判定一个顺序栈st（最多元素为MaxSize）为 满 的 条 件 是D。A.st-top!=-1 B.st-top=-1C.st-top!=MaxSize D.st-top=MaxSize45.一个队列的入队序列是1,2,3,4,则队列的输出序列是oA.4,3,2,1 B.1,2,3,4C.1,4,3,2 D.3,2,4,146.判定一个循环队列qu（最多元素为MaxSize）为空的条件是。A.qu-rear-qu-front=MaxSize B.qu-rear-qu-front-l=MaxSizeC.qu-rear=qu-front D.qu-rear=qu-front-147.在循环队列中，若front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是 C OA.fr o n t=r e a r+lB.r e a r=fr o n t+lC.fr o n t=r e a rD.fr o n t=04 8.向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行操作。A.h-n e xt=s ;B.s-n e xt=h;C.s-n e xt=h;h=s ;D.s-n e xt=h-n e xt;h-n e xt=s ;4 9.输入序列为ABC,可以变为CBA时，经过的栈操作为A.p us h,p o p,p us h,p o p,p us h,p o p B.p us h,p us h,p us h,p o p,p o p,p o pC.p us h,p us h,p o p,p o p,p us h,p o p D.p us h,p o p,p us h,p us h,p o p,p o p5 0 .若栈采用顺序存储方式存储，现两栈共享空间V 1 m,to p 1、to p 2 分别代表第1和第2个栈的栈顶，栈1的底在V l,栈2的底在V m,则栈满的条件是B 0A.|to p 2-to p 1|=0 B.to p l+l=to p 2 C.to p l+to p 2=mD.to p l=to p 2 5 1 .设计一个判别表达式中左、右括号是否配对出现的算法，采 用 数 据 结 构最佳。A.线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈5 2 .允许对队列进行的操作有 A.对队列中的元素排序 B.取出最近进队的元素C.在队头元素之前插入元素 D.删除队头元素5 3 .对于循环队列 D。A.无法判断队列是否为空 B.无法判断队列是否为满C.队列不可能满 D.以上说法都不对5 4 .若用一个大小为6的数值来实现循环队列，且当前r e a r和fr o n t的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，r e a r和fr o n t的值分别为BoA.1 和 5 B.2 和 4 C.4 和 2 D.5 和 15 5 .队列的“先进先出”特 性 是指 D oA.最早插入队列中的元素总是最后被删除B.当同时进行插入、删除操作时一，总是插入操作优先C.每当有删除操作时，总是要先做一次插入操作D.每次从队列中删除的总是最早插入的元素5 6 .和顺序栈相比，链栈有一个比较明显的优势是。A.通常不会出现栈满的情况 B.通常不会出现栈空的情况C.插入操作更容易实现 D.删除操作更容易实现5 7.用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时 C OA.仅修改队头指针 B.仅修改队尾指针C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改BD.95 8.若串S=s o ftwa r e ,其子串的数目是A.8 B.3 7 C.3 65 9.串的长度是指oA.串中所含不同字母的个数C.串中所含不同字符的个数B.串中所含字符的个数D.串中所含非空格字符的个数6 0 .串是一种特殊的线性表，其特殊性体现在A.可以顺序存储 B.数据元素是一个字符C.可以链式存储 D.数据元素可以是多个字符6 1 .设有两个串p和q,求q在p中首次出现的位置的运算称为3 oA.连接 B.模式匹配 C.求子串 D.求串长6 2 .数组A中，每个元素的长度为3个字节，行下 标i从1到8,列下标j从1到1 0,从首地址SA开始连续存放的存储器内，该数组按行存放，元素A85 的起始地址为 C。A.SA+1 4 1 B.SA+1 4 4 C.SA+2 2 2 D.SA+2 2 56 3 .数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1到1 0,从首地址SA开始连续存放的存储器内，该数组按行存放，元素A5 8的起始地址为 C。A.SA+1 4 1 B.SA+1 80C.SA+2 2 2 D.SA+2 2 564.若声明一个浮点数数组如下：froat average=new flo at30;假设该数组的内存起始位置为200,average15的 内 存 地 址 是C 。A.214 B.215 C.260 D.25665.设二维数组A1 m,1 n按行存储在数组B中，则二维数组元素Ai,j在一维数组B中的下标为 A 。A.n*(iT)+j B.n*(iT)+jT C.D.j*m+iT66.有一个100X90的稀疏矩阵，非0元素有1 0,设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是 B 。A.20 B.66 C.18 000 D.3367.数组A 0 4,-1-3,57中含有的元素个数是。A.55 B.45 C.36 D.1668.对矩阵进行压缩存储是为了 D oA.方 便 运 算B.方便存储 C.提高运算速度 D.减少存储空间69.设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a一为第一个元素，其存储地址为1,每个元素占1个地址空间，则a8.5的 地 址 为B 。A.13 B.33 C.18 D.4070.稀疏矩阵一般的压缩存储方式有两种，即CA.二维数组和三维数组 B,三元组和散列C.三元组和十字链表 D.散列和十字链表7 1 .树最适合用来表示_ 匚。A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据7 2 .深度为5的二叉树至多有 C 个结点。A.1 6 B.3 2 C.3 1 C.1 07 3 .对一个满二叉树，m 个叶子，n 个结点，深度为h,则。A.n =h+m B h+m=2 n C m=h-1 D n =2bT7 4 .任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序 A 。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对7 5 .在线索化树中，每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息，还是线索化信息，若 0标识树结构信息，1 标识线索，对应叶结点的左右链域，应标识为 D 。A.0 0 B.0 1 C.1 0 D.1 17 6 .在下述论述中，正确的是 D只有一个结点的二叉树的度为0;二叉树的度为2；二叉树的左右子树可任意交换；深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。A.B.C.D.7 7 .设森林F 对应的二叉树为B,它有m 个结点，B的根为p,p的右子树的结点个数为n,森林F中第一棵树的结点的个数是 A 0A.m-n B.m-n-1 C.n+1 D.不能确定7 8 .若一棵二叉树具有1 0 个度为2的结点，5 个度为1 的结点，则度为。的结点的个 数 是 B。A.9 B.1 1 C.1 5 D.不能确定7 9 .具有1 0 个叶子结点的二叉树中有 B 个度为2的结点。A.8 B.9C.1 0 D.1 18 0.在一个无向图中,所有顶点的度数之和等于所有边数的倍。A.1/2 B 1 C 2D 48 1.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的B 倍。A.1/2 B 1 C 2D 48 2 .某二叉树结点的中序序列为A B C D E F G,后序序列为B D C A F G E,则其左子树中结点数目为：CA.3 B.2 C.4 D.58 3 .已知一算术表达式的中缀形式为A+B *C-D/E,后缀形式为A B C *+D E/-,其前缀形式为.A+B M/D EA+B*C D/E+*A B C/D ED.-+A*B C/D E8 4.已知一个图，如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为 b e ，D ；按广度搜索法进行遍历，则可能得到的一种顶 点 序 列 为A.a,b,e,c,d,fB.a,c,f,e,b,C.a,e,b,c,f,d,D.a,e,d,f,c,bA.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,d,D.a,c,f,d,e,b8 5 .采用邻接表存储的图的深度优先遍历算法类似于二叉树的AA.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历8 6 .采用邻接表存储的图的广度优先遍历算法类似于二叉树的 DA.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历8 7 .具有n个结点的连通图至少有 A 条边。A.n-1 B.n C.n （n-1）/2 D.2 n8 8 .广义表（a）,a）的表头是C ,表 尾 是C 。A.aB ()C (a)D (a)8 9 .广义表(a)的表头是C ,表 尾 是 B 。A.a B ()C (a)D (a)9 0 .顺序查找法适合于存储结构为 J 的线性表。A 散列存储 B 顺序存储或链式存储 C 压缩存储 D 索引存储9 1 .对线性表进行折半查找时，要求线性表必须。A以顺序方式存储 B以顺序方式存储，且结点按关键字有序排列C 以链式方式存储 D 以链式方式存储，且结点按关键字有序排列9 2 .采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为D OA 0(n2)B 0(n l o g2n)C 0(n)D 0(l o g2n)9 3.有一个有序表为 1,3,9,1 2,32,4 1,4 5,6 2,7 5,7 7,8 2,9 5,1 0 0),当折半查找值为8 2 的结点时，C 次比较后查找成功。A.1 1 B 5 C 4 D 89 4 .二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法 B。A 正确 B 错误9 5 .下面关于B 树和B+树的叙述中，不正确的结论是 AA B树和B+树都能有效的支持顺序查找查找C B树和B+树都是平衡的多叉树 D B树和B+树都可用于文件索引结构9 6.以下说法错误的是 B。A.散列法存储的思想是由关键字值决定数据的存储地址B.散列表的结点中只包含数据元素自身的信息，不包含指针。C.负载因子是散列表的一个重要参数，它反映了散列表的饱满程度。D.散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。9 7.查找效率最高的二叉排序树是 oA.所有结点的左子树都为空的二叉排序树。B.所有结点的右子树都为空的二叉排序树。C.平衡二叉树。D.没有左子树的二叉排序树。9 8 .排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 C 。A.希尔排序 B o 冒泡排序 C 插入排序 D o 选择排序B B树和B+树都能有效的支持随机9 9 .在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是DoA.希尔排序B.冒泡排序C.直接插入排序 D.直接选择排序1 0 0 .堆是一种有用的数据结构。下列关键码序列 D 是一个堆。A.9 4,31,5 3,2 3,1 6,7 2C.1 6,5 3,2 3,9 4,31,7 2B.9 4,5 3,31,7 2,1 6,2 3D.1 6,31,2 3,9 4,5 3,7 21 0 1 .堆排序是一种 B 排序。A.插入 B.选择 C.交换 D.归并1 0 2 .D 在链表中进行操作比在顺序表中进行操作效率高。A.顺序查找 B.折半查找 C.分块查找 D.插入1 0 3.直接选择排序的时间复杂度为 D 。(n为元素个数)A.0 (n)B.0(l o g2n)C.0(n l o g2n)D.0 (nL，)二、填空题。1 .数 据 逻 辑 结 构 包 括 线 性 结 构、树 形 结 构 和图 状 结 构 三种类型,树形结构和图状结构合称非线性结构。2 .数据的逻辑结构分为 集合、线 性 结 构、树 形 结 构 和图状结构4种。3.在线性结构中，第一个结点没 有 前驱结点,其余每个结点有且只有1个前驱结点；最后一个结点 M L后续结点，其余每个结点有且只有1个后续结点。4.线性结构中元素之间存在一 对 一 关系，树形结构中元素之间存在一 对 多 关系,图形结构中元素之间存在多 对 多 关系。5 .在树形结构中，树根结点没有前 驱 结点,其余每个结点有且只有1个前驱结点；叶 子 结 点 没 有 后 续 结点,其余每个结点的后续结点可以任 意 多 个。6 .数据结构的基本存储方法是顺 序、链 式、索引 和 散列 存 储。7.衡 量 一个算法的优劣主要考虑正确性、可读性、健 壮 性 和 时间复杂度与 空间复 杂 度。8 .评估一个算法的优劣，通 常 从 时 间 复 杂 度 和空 间 复 杂 度 两个方面考察。9.算法的5个 重 要 特 性 是 有 穷 性、确 定 性、可 行 性、输入和输出。10 .在一个长度为n的顺序表中删除第i个元素时，需向前移动n-i T 个元素。11.在单链表中，要删除某一指定的结点，必 须 找 到 该 结 点 的 前 驱 结点。12 .在双链表中，每个结点有两个指针域，一个 指 向 前 驱 结 点,另一个指 向 工继 结 点。13 .在顺序表中插入或删除