大学数据结构期末考试试题(有答案)_第1页
大学数据结构期末考试试题(有答案)_第2页
大学数据结构期末考试试题(有答案)_第3页
大学数据结构期末考试试题(有答案)_第4页
大学数据结构期末考试试题(有答案)_第5页
已阅读5页,还剩32页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、.“数据结构”期末考试试题一、单选题 ( 每小题 2 分,共 12 分)1在一个单链表 hl中,若要向表头插入一个由指针p 指向的结点,则执行 ( ) 。a hl ps p 一 next hlb p一 next hl;hl p3c p一 next hl ;p hl;d p一 next hl一 next;hl一next p;2n 个顶点的强连通图中至少含有( ) 。a.n l 条有向边b.n条有向边c.n(n1) 2 条有向边d.n(n一 1) 条有向边3.从一棵二叉搜索树中查找一个元素时,其时间复杂度大致为()。a.o(1)b.o(n)c.o(1ogzn)d.o(n2)4由权值分别为3,8,

2、6, 2, 5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为()。a24b 48c 72d 535当一个作为实际传递的对象占用的存储空间较大并可能需要修改时,应最好把它说明为()参数,以节省参数值的传输时间和存储参数的空间。a.整形b.引用型c.指针型d.常值引用型6向一个长度为n 的顺序表中插人一个新元素的平均时间复杂度为()。ao(n)b o(1)co(n2)d o(10g2n)二、填空题 ( 每空 1 分,共 28 分 )1数据的存储结构被分为、和四种。2 在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同,各自分别为域和域。3中缀表达式 3 十 x*(2.4 5 6) 所对

3、应的后缀表达式为。4 在一棵高度为 h 的 3 叉树中,最多含有结点。5假定一棵二叉树的结点数为 18,则它的最小深度为,最大深度为6 在一棵二叉搜索树中,每个分支结点的左子树上所有结点的值一定该结点的值,右子树上所有结点的值一定该结点的值。7 当向一个小根堆插入一个具有最小值的元素时,该元素需要逐层调整,直到被调整到位置为止。8 表示图的三种存储结构为、和。9 对用邻接矩阵表示的具有 n 个顶点和 e 条边的图进行任一种遍历时,其时间复杂度为,对用邻接表表示的图进行任一种遍历时,其时间复杂度为。10从有序表 (12 , 18, 30, 43, 56, 78, 82,95) 中依次二分查找 4

4、3 和 56 元素时,其查找长度分别为和11 假定对长度 n 144 的线性表进行索引顺序查找, 并假定每个子表的长度均为 ,则进行索引顺序查找的平均查找长度为,时间复杂度为12 一棵 b树中的所有叶子结点均处在上。13 每次从无序表中顺序取出一个元素,把这插入到有序表中的适当位置,此种排序方法叫做排序;每次从无序表中挑选出一个最小或最大元素,把它交换到有序表的一端,此种排序方法叫做排序。14 快速排序在乎均情况下的时间复杂度为,最坏情况下的时间复杂度为。三、运算题 ( 每小题 6 分,共 24 分 )1 假定一棵二叉树广义表表示为 a(b(c ,d) ,c( ,8) ,分别写出对它进行先序、

5、中序、后序和后序遍历的结果。先序:;.中序;后序: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,试以它们为叶子结点生成一棵哈夫曼树,求出该树的带

6、权路径长度、高度、双分支结点数。带权路径长度:高度:双分支结点数:。四、阅读算法,回答问题( 每小题 8 分,共 16 分)1 voldac(list&l)initlist(l);insertrear(l;25);insertfront(l,50) ;intal4 5 , 8, 12, 15, 36;for(inti0; i5; i+)if (ai2 0)insertfront(l, ai);elselnsertrear(l,ai);该算法被调用执行后,得到的线性表l 为:2 void ag(queue&q)initqueue(q);inta5 6 , 12, 5, 15, 8 ;for(in

7、t i0;i5; i+)qinsert(q, ai);qinsert(q,qdelete(q);qinsert(q,20) ;qinsert(q,qdelete(q)十 16) ;while(!queueempty(q)coutqdelete(q)”;该算法被调用后得到的输出结果为:五、算法填空,在画有横线的地方填写合适的内容( 每小题 6 分,共 12 分 )1 从一维数组 an) 中二分查找关键字为 k 的元素的递归算法,若查找成功则返回对应元素的下标,否则返回一 1。intbinsch(elemtypea,intlow,int high, keytypek)if(low high)int

8、 mid (low+high) 2;if(k amid.key);else if (kdata x)return 1;根结点的层号为1向子树中查找x 结点elseint cl nodelevel(bt 一 left, x);if(cl 1)return cl+1;int c2;if;若树中不存在x 结点则返回oelse return 0;六、编写算法 (8 分 )按所给函数声明编写一个算法,从表头指针为 hl 的单链表中查找出具有最大值的结点,该最大值由函数返回,若单链表为空则中止运行。eiemtype maxvalue(lnode*hl);“数据结构”期末考试试题答案一、单选题 ( 每小题

9、2 分,共 12 分 )评分标准;选对者得2 分,否则不得分。1b2b3 c4 d5 b6a二、填空题 ( 每空 1 分,共 28 分)1顺序结构链接结构索引结构散列结构 ( 次序无先后 )2 值 ( 或 data)子表指针 ( 或 sublist)3 3 x 2 4 5 6 一* 十4 (3 h 一 1) 25 5 186小于大于 ( 或大于等于 )7向上堆顶8邻接矩阵邻接表边集数组 ( 次序无先后 )9 o(n2) o(e)10 1 311 13o()12 同一层13 插人选择14 o(nlog 2n)o(n2)三、运算题 ( 每小题 6 分,共 24 分 )1先序: a, b,c ,d,

10、 e, f ,e 2 分中序: c, b, d,a,f , 8, e 2 分后序: c, d, b,e,f , e, a 2 分2 最小生成树的权:31 6 分3(84 , 79, 56, 42, 40, 46, 50, 38) 6 分4带权路径长度: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 分,共 1

11、2 分 )1feturn mid 2 分returnbinsch(a, low , mid 一 1,k) 2 分returnbmsch(a,mid+1,high , k) 2 分2nodelevel(bt 一 right,x) 3 分(c2=1)returnc2十 1 3 分六、编写算法 (8 分 )评分标准:请参考语句后的注释,或根据情况酌情给分。elemtype maxvalue(lnodeo* hl。)if (hl =null) 2 分cerrlinked llst is empty!”data ; 3 分lnode*p=hi一 next ; 4 分while(p!:null) 7 分i

12、f(maxdata)max p 一 data ;pp 一next ;returnmax; 8 分数据结构复习资料一、填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。2.数据结构被形式地定义为( d, r ),其中 d 是数据元素的有限集合, r是 d 上的关系有限集合。3.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。4.数据结构按逻辑结构可分为两大类,它们分别是线性结构和非线性结构。5. 线性结构中元素之间存在 一对一关系,树形结构中元素之间存在 一对多 关系,图形结构中元素之间存在多对多 关系。6 在线性结构

13、中,第一个结点没有 前驱结点,其余每个结点有且只有1 个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有1 个后续结点。7. 在树形结构中,树根结点没有前驱结点,其余每个结点有且只有1个前驱结点;叶子结点没有后续结点,其余每个结点的后续结点数可以任意多个。8. 在图形结构中,每个结点的前驱结点数和后续结点数可以任意多个。;.9数据的存 构可用四种基本的存 方法表示,它 分 是 序、 式 、 索引和散列。10. 数据的运算最常用的有 5 种,它 分 是 插入 、 除、修改、 找 、排序 。11.一个算法的效率可分 时间效率和空 效率。12.在 序表中插入或 除一个元素,需要平均移 表中一

14、半 元素,具体移 的元素个数与表 和 元素在表中的位置有关。13. 性表中 点的集合是有限的, 点 的关系是一 一的。14.向一个 度 n 的向量的第 i 个元素 (1 i n+1) 之前插入一个元素 , 需向后移 n-i+1个元素。15.向一个 度 n 的向量中 除第i 个元素 (1 i n) ,需向前移 n-i个元素。16.在 序表中 任意一 点的 复 度均 o(1),因此, 序表也称 随机存取的数据 构。17. 序表中 上相 的元素的物理位置必定相 。 表中 上相 的元素的物理位置不一定相 。18在 表中,除了首元 点外,任一 点的存 位置由其直接前 点的 域的 指示。19 在 n 个

15、点的 表中要 除已知 点*p ,需找到它的 前 点的地址 ,其 复 度 o(n)。20.向量、 和 列都是 性 构,可以在向量的任何位置插入和 除元素; 于 只能在 插入和 除元素; 于 列只能在 尾插入和 首 除元素。21. 是一种特殊的 性表,允 插入和 除运算的一端称 栈顶。不允 插入和 除运算的一端称 底。22. 列 是被限定 只能在表的一端 行插入运算,在表的另一端 行 除运算的 性表。23.不包含任何字符 ( 度 0)的串称 空串;由一个或多个空格 ( 由空格符) 成的串称 空白串。24.子串的定位运算称 串的模式匹配;被匹配的主串称 目 串,子串称 模式。25.假 有二 数 a

16、8,每个元素用相 的6 个字 存 ,存 器按字 址。已知a 的起始存 位置6(基地址) 1000, 数 a 的体 (存 量) 288 b;末尾元素 a57 的第一个字 地址 1282;若按行存 ,元素a14 的第一个字 地址 (8+4) 6+1000=1072;若按列存 ,元素 a 的第一个字 地址 (6 7 4) 6 1000) 1276。4726 由个 点所构成的二叉 有5种形 。27.一棵深度 6 的 二叉 有n1+n2=0+ n 2= n 0-1=31个分支 点和26-1=32个叶子。注: 二叉 没有度 1 的 点,所以分支 点数就是二度 点数。28 一棵具有个 点的完全二叉 ,它的深

17、度 9。( 注:用log 2(n)+1=8.xx+1=929 一棵完全二叉 有700 个 点, 共有350个叶子 点。答:最快方法:用叶子数n/235030 一棵完全二叉 具有1000 个 点, 此完全二叉 有500 个叶子 点,有499 个度 2的 点,有1个 点只有非空左子 ,有0个 点只有非空右子 。答:最快方法:用叶子数n/2500,n =n -1=499 。 另外,最后一 点 2i属于左叶子,右叶子是20空的,所以有 1 个非空左子 。完全二叉 的特点决定不可能有左空右不空的情况,所以非空右子 数0.31在数据的存放无 律而言的 性表中 行 索的最佳方法是 序 找( 性 找)。32.

18、 性有序表( a , a , a , a256) 是从小到大排列的, 一个 定的 k,用二分法 索表中与k 相123等的元素,在 找不成功的情况下,最多需要 索8次。 有 100 个 点,用二分法 找 ,最大比 次数是7。33.假 在有序 性表a20 上 行折半 找, 比 一次 找成功的 点数 1;比 两次 找成功的 点数 2;比 四次 找成功的 点数 8;平均 找 度 3.7。解: 然,平均 找 度o(log 2n)top0 st-top=0 st-topm0 st-top=m0(c ) 18.在一个 中,所有 点的度数之和等于 的 数的倍。a 1/2b. 1c. 2d. 4(b) 19.在

19、一个有向 中,所有 点的入度之和等于所有 点的出度之和的倍。a 1/2b. 1c. 2d. 4(b) 20.有 8 个 点的无向 最多有条 。a 14b. 28c. 56d. 112(c) 21.有 8 个 点的有向完全 有条 。a 14b. 28c. 56d. 112( b ) 22在表 的 表中 行 性 找,它的平均 找 度 . ; . () ;.n ; . ()( a ) 23折半 找有序表( 4,6, 10, 12, 20, 30, 50, 70, 88, 100)。若 找表中元素 58, 它将依次与表中比 大小, 找 果是失 。a20, 70, 30, 50b30, 88, 70,

20、50c 20,50d30,88, 50(c) 24 22 个 的有序表作折半 找,当 找失 ,至少需要比 次关 字。a3b4c5d 6(a) 25. 表适用于 找a 序b二分法c 序,也能二分法d随机数据 构与算法复 一、 。1在数据 构中,从 上可以把数据 构分 c。a 构和静 构b 凑 构和非 凑 构c 性 构和非 性 构d内部 构和外部 构2数据 构在 算机内存中的表示是指a。;.a数据的存储结构b数据结构c数据的逻辑结构d 数据元素之间的关系3在数据结构中,与所使用的计算机无关的是数据的a结构。a逻辑b存储c逻辑和存储d物理4在存储数据时,通常不仅要存储各数据元素的值,而且还要存储c。

21、a数据的处理方法b数据元素的类型c数据元素之间的关系d数据的存储方法5在决定选取何种存储结构时,一般不考虑a。a各结点的值如何b结点个数的多少c对数据有哪些运算d所用的编程语言实现这种结构是否方便。6以下说法正确的是d。a数据项是数据的基本单位b数据元素是数据的最小单位c数据结构是带结构的数据项的集合d一些表面上很不相同的数据可以有相同的逻辑结构7算法分析的目的是c,算法分析的两个主要方面是a。(1) a找出数据结构的合理性b研究算法中的输入和输出的关系c分析算法的效率以求改进c分析算法的易读性和文档性(2) a空间复杂度和时间复杂度b正确性和简明性c可读性和文档性d数据复杂性和程序复杂性8下

22、面程序段的时间复杂度是o(n 2)。s =0;for( i =0; in; i+)for(j=0;jn;j+)s +=bij;sum = s ;9下面程序段的时间复杂度是o(n*m)。for( i =0; in; i+)for(j=0;jm;j+)aij 0;10下面程序段的时间复杂度是o(log3n)。i 0 ;while ( inext =nullchead-next =headd head!=null15带头结点的单链表head 为空的判定条件是b。ahead = nullb head-next =nullchead-next =headd head!=null16若某表最常用的操作是在

23、最后一个结点之后插入一个结点或删除最后一个结点,则采用d 存储方式最节省运算时间。a单链表 b 给出表头指针的单循环链表c 双链表 d 带头结点的双循环链表17需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是b。a单链表 b 静态链表c 线性链表d 顺序存储结构18非空的循环单链表head 的尾结点(由 p 所指向)满足 c。ap-next = nullb p = nullcp-next =headdp = head19在循环双链表的p 所指的结点之前插入s 所指结点的操作是d。ap-prior = s ; s-next = p ;p-prior-next = s;s-prio

24、r = p-priorbp-prior = s ; p-prior-next = s; s-next = p;s-prior = p-priorcs-next = p ; s-prior = p-prior; p-prior = s;p-prior-next = sds-next = p ; s-prior = p-prior; p-prior-next = s; p-prior = s20如果最常用的操作是取第i 个结点及其前驱,则采用d存储方式最节省时间。a单链表b 双链表c单循环链表d 顺序表21在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是b。ao(1)b

25、 o( n)c o(n2)do( nlog2n )22在一个长度为n( n1)的单链表上,设有头和尾两个指针,执行b操作与链表的长度有关。a删除单链表中的第一个元素b删除单链表中的最后一个元素c在单链表第一个元素前插入一个新元素d在单链表最后一个元素后插入一个新元素23与单链表相比,双链表的优点之一是d。;.a插入、 除操作更 b可以 行随机 c可以省略表 指 或表尾指 d 序 相 点更灵活24如果 性表的操作只有两种,即 除第一个元素,在最后一个元素的后面插入新元素, 最好使用b 。a只有表 指 没有表尾指 的循 表b只有表尾指 没有表 指 的循 表c非循 双 表d循 双 表25在 度 n

26、的 序表的第i 个位置上插入一个元素(1 i n+1),元素的移 次数 :a。an i + 1b n ic id i 126 于只在表的首、尾两端 行插入操作的 性表,宜采用的存 构 c。a 序表b 用 指 表示的循 表c用尾指 表示的循 表d 表27下述哪一条是 序存 构的 点?c。a 插入运算方便 b 可方便地用于各种 构的存 表示c存 密度大 d 除运算方便28下面关于 性表的叙述中, 的是哪一个?b。a 性表采用 序存 ,必 占用一片 的存 元b 性表采用 序存 ,便于 行插入和 除操作。c 性表采用 式存 ,不必占用一片 的存 元d 性表采用 式存 ,便于 行插入和 除操作。29 性

27、表是具有n 个b的有限序列。a字符b数据元素c数据 d表元素30在 n 个 点的 性表的数 中,算法的 复 度是o(1)的操作是a。a 第 i (1=i=n )个 点和求第i 个 点的直接前 (1i=n )b在第 i ( 1=i=n )个 点后插入一个新 点c 除第 i (1=inext=s ; s-next=p-nextb s-next=p-next;p-next=s;c p-next=s ; p-next=s-nextd p-next=s-next; p-next=s36 性表的 序存 构是一种a。a随机存取的存 构b 序存取的存 构c索引存取的存 构d hash 存取的存 构37 的特点是b, 列的特点是a。a先 先出b先 后出38 和 列的共同点是c。a都是先 后出b都是先 先出c只允 在端点 插入和 除元素d没有共同点39一个 的 序列是 a,b, c, d,e, 的不可能的 出序列是c。aedcbab decbac dceabd abcde40 有一个 ,元素依次 的 序 a、 b、c、 d、 e。下列 c是不可能的出 序列。a a,b,c,d,e b b,c,d,e,ace,a,b,c,dd e,d,c,b,a41以下b不是 列的基本运算?a从 尾插入一个新元素b从 列中 除第 i个元素c判

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论