数据结构C语言版期末考试题附带复习资料.docx
《数据结构C语言版期末考试题附带复习资料.docx》由会员分享,可在线阅读,更多相关《数据结构C语言版期末考试题附带复习资料.docx(36页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、“数据构造期末考试试题一、单项选择题(每题2分,共12分)1 .在一个单链表HL中,假设要向表头插入一个由指针p指向的结点,那么执行()。A. HI,=ps p -next=HLB. p -next=HL; HL=p3C. p 一next=Hl; p = HL;D. p next=HL -next;HL - next=p;2 . n个顶点的强连通图中至少含有()oA.n1条有向边B.n条有向边C.n(n1)/2条有向边 D.n(n - 1)条有向边3 .从一棵二叉搜索树中查找一个元素时,其时间复杂度大致为( )oA.O(l) B.O(n)C.O(lOgzn) D.O(n2)4 .由权值分别为3
2、, 8, 6, 2, 5的叶子结点生成一棵哈夫曼树,它的带权路径长度为()oA. 24 B. 48C. 72 D. 535 .当一个作为实际传递的对象占用的存储空间较大并可能需要修改时,应最好把它说明为 ()参数,以节省参数值的传输时间和存储参数的空间。A.整形 B.引用型C.指针型D.常值引用型6 .向一个长度为n的顺序表中插入一个新元素的平均时间复杂度为()。A. O(n) B. 0(1)C. O(n2) D. O(10g2n)二、填空题(每空1分,共28分)1 .数据的存储构造被分为、和四种。2 .在广义表的存储构造中,单元素结点与表元素结点有一个域对应不同,各自分别为域 和域。3 .
3、中缀表达式 3十x*(2.4/56)所对应的后缀表达式为o4 .在一棵高度为h的3叉树中,最多含有结点。5 .假定一棵二叉树的结点数为18,那么它的最小深度为,最大深度为6 .在一棵二叉搜索树中,每个分支结点的左子树上所有结点的值一定该结点的值,右子 树上所有结点的值一定该结点的值。7 .当向一个小根堆插入一个具有最小值的元素时,该元素需要逐层调整,直到被调整到位置为止。8 .表示图的三种存储构造为、和o9 .对用邻接矩阵表示的具有n个顶点和e条边的图进展任一种遍历时,其时间复杂度为, 对用邻接表表示的图进展任一种遍历时,其时间复杂度为O.从有序表(12, 18, 30, 43, 56, 78
4、, 82, 95)中依次二分查找43和56元素时,其查找长度 分别为和,10 .假定对长度n=144的线性表进展索引顺序查找,并假定每个子表的长度均为,那么进展索引顺序查找的平均查找长度为,时间复杂度为X J 15.栈和链表是两种不同的数据构造。错,栈是逻辑构造的概念,是特殊殊线性表,而链表是存储构造概念,二者不是同类项。X 16.栈和队列是一种非线性数据构造。错,他们都是线性逻辑构造,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。M 17.栈和队列的存储方式既可是顺序方式,也可是方式。M 18.两个栈共享一片连续存空间时,为提高存利用率,减少溢出时机,应把两个栈的栈 底分别设在这片存
5、空间的两端。X 19.队是一种插入与删除操作分别在表的两端进展的线性表,是一种先进后出型构造。 错,后半句不对。X 20. 一个栈的输入序列是12345,那么栈的输出序列不可能是12345。错,有可能。M21.假设二叉树用二叉链表作存贮构造,那么在n个结点的二叉树链表中只有匚L个非 空指针域。X22.二叉树中每个结点的两棵子树的高度差等于1。M23.二叉树中每个结点的两棵子树是有序的。X24.二叉树中每个结点有两棵非空子树或有两棵空子树。X25.二叉树中每个结点的关键字值大于其左非空子树假设存在的话所有结点的关键字 值,且小于其右非空子树假设存在的话所有结点的关键字值。应当是二叉排序树的特点)
6、X26.二叉树中所有结点个数是2kL1,其中k是树的深度。应2X27.二叉树中所有结点,如果不存在非空左子树,那么不存在非空右子树。X28.对于一棵非空二叉树,它的根结点作为第一层,那么它的第i层上最多能有21个结 点。应2刃M29.用二叉链表法link-rlink存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。M30.具有12个结点的完全二叉树有5个度为2的结点。三、单项选择题B 1.非线性构造是数据元素之间存在一种:A一对多关系B多对多关系 C多对一关系D) 一对一关系C 2.数据构造中,与所使用的计算机无关的是数据的构造;A)存储 B)物理C)逻辑D)物理和存储C 3
7、.算法分析的目的是:A)找出数据构造的合理性B)研究算法中的输入和输出的关系C)分析算法的效率以求改良D)分析算法的易懂性和文档性A 4.算法分析的两个主要方面是:A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性C 5.计算机算法指的是:A)计算方法B)排序方法 C)解决问题的有限运算序列D)调度方法B 6.计算机算法必须具备输入、输出和等5个特性。A)可行性、可移植性和可扩大性B)可行性、确定性和有穷性Q确定性、有穷性和稳定性D)易读性、稳定性和平安性C C 7.数据在计算机存储器表示时,物理地址与逻辑地址一样并且是连续的,称之为:CA)存储构造B逻辑
8、构造 C顺序存储构造 D链式存储构造B 8. 一个向量第一个元素的存储地址是100,每个元素的长度为2,那么第5个元素的地 址是B108B108C 100D120A 9.在n个结点的顺序表中,算法的时间复杂度是。1的操作是:(A) 访问第i个结点和求第i个结点的直接前驱2itop0 B . ST-top=0 C . ST-topmO D. ST-top=mOC18.在一个图中,所有顶点的度数之和等于图的边数的倍。A. 1/2B. 1C. 2D. 4B 19.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍。A. 1/2B. 1C. 2D. 4B j 20.有8个结点的无向图最多有条
9、边。A. 14B. 28C 21.有8个结点的有向完全图有条边。A. 14B. 28B 22.在表长为n的链表中进展线性查找,A. A S L= n;B. ASL=n+lC. A S L =1 ; D. ASL-1 o g 2A 23.折半查找有序表4, 6, 10, 12, 2(C. 56D. 112C. 56D. 112它的平均查找长度为 /2;n + 1- 1),30, 50, 70, 88, 100。假设查找表中元素58,那么它将依次与表中比拟大小,查找结果是失败。A. 20, 70, 30, 50 B. 30, 88, 70, 50 C. 20, 50 D. 30, 88, 50C
10、24.对22个记录的有序表作折半查找,当查找失败时,至少需要比拟次关键字。A. 3B. 4C. 5D. 6A 25.链表适用于查找A.顺序 B.二分法 C.顺序,也能二分法D.随机”数据构造与算法”复习题一、选择题。1 .在数据构造中,从逻辑上可以把数据构造分为 C 。A.动态构造和静态构造B.紧凑构造和非紧凑构造C.线性构造和非线性构造D.部构造和外部构造2 .数据构造在计算机存中的表示是指 A .A.数据的存储构造B.数据构造C.数据的逻辑构造 D.数据元素之间的关系.在数据构造中,与所使用的计算机无关的是数据的A 构造。A.逻辑 B.存储 C.逻辑和存储D.物理.在存储数据时,通常不仅要
11、存储各数据元素的值,而且还要存储 C 。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法3 .在决定选取何种存储构造时,一般不考虑 A oA.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.所用的编程语言实现这种构造是否方便。4 .以下说确的是D。A.数据项是数据的根本单位B.数据元素是数据的最小单位C.数据构造是带构造的数据项的集合D. 一些外表上很不一样的数据可以有一样的逻辑构造5 .算法分析的目的是 C ,算法分析的两个主要方面是 ACD A.找出数据构造的合理性C.分析算法的效率以求改良2A.空间复杂度和时间复杂度C.可读性和文档性.下面程序段的时间
12、复杂度是。(哈s =0;for( I =0; in; i+)for(j=0;jn;j+)s+=sum = s ;B.研究算法中的输入和输出的关系C.分析算法的易读性和文档性.正确性和简明性D.数据复杂性和程序复杂性8 .下面程序段的时间复杂度是 C)(n*m)ofor( i =0; in; i+)for(j=0;jm;j+)Aij = 0;.下面程序段的时间复杂度是 0(1。跖n)1 = 0;while inext =NULLC. head-next =headD head!=NULL15 .带头结点的单链表head为空的判定条件是B 。A. head 二二 NULLB hcad-ncxt 二
13、二NULLC. hcad-ncxt =hcadD head!二NULL16 .假设某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,那么采用D存储方式最节省运算时间。A.单链表 B.给出表头指针的单循环链表C,双链表 D.带头结点的双循环链表.需要分配较大空间,插入和删除不需要移动元素的线性表,其存储构造是 B 。A.单链表 B.静态链表 C.线性链表D.顺序存储构造.非空的循环单链表head的尾结点由p所指向满足 C 。A. p-next = NULLB. p = NULLC. p-next =headD. p = head19 .在循环双链表的p所指的结点之前插入s所指结
14、点的操作是D 。A. p-prior = s;s-ncxt = p; p-prior-ncxt = s;s-prior = p-priorp-prior = s;p-prior-ncxt = s;s-ncxt = p;s-prior = p-priorB. s-next = p;s-prior = p-prior;p-prior = s;p-prior-next = ss-next = p;s-prior = p-prior;p-prior-next = s; p-prior = s20 .如果最常用的操作是取第i个结点及其前驱,那么采用 D 存储方式最节省时间。A.单链表 B.双链表 C.单
15、循环链表D. 顺序表.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B oA. O1 B. ()n C. O (n2) D. O nlog2n.在一个长度为n nlj的单链表上,设有头和尾两个指针,执行_匕操作与链表的长度有 关。A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素21 .与单链表相比,双链表的优点之一是 D 。A.插入、删除操作更简单B.可以进展随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活24 .如果对线性表的操作只有两种,即删除第一个元素,在
16、最后一个元素的后面插入新元素,那 么最好使用B 。A.只有表头指针没有表尾指针的循环单链表B.只有表尾指针没有表头指针的循环单链表C.非循环双链表D.循环双链表25 .在长度为n的顺序表的第i个位置上插入一个元素i元素的移动次数为:A. n - i + 1B. n - iD. i - 1.对于只在表的首、尾两端进展插入操作的线性表,宜采用的存储构造为 CA.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表26 .下述哪一条是顺序存储构造的优点?CA插入运算方便 B可方便地用于各种逻辑构造的存储表示C存储密度大 D删除运算方便.下面关于线性表的表达中,错误的选项是哪一个?
17、BA线性表采用顺序存储,必须占用一片连续的存储单元B线性表采用顺序存储,便于进展插入和删除操作。C线性表采用链式存储,不必占用一片连续的存储单元D线性表采用链式存储,D线性表采用链式存储,便于进展插入和删除操作。27 .线性表是具有n个 B 的有限序列。A.字符 B.数据元素C.数据项D.表元素28 .在n个结点的线性表的数组实现中,算法的时间复杂度是C)1的操作是A 。A.访问第iIV二i二n个结点和求第i个结点的直接前驱li=nB.在第iIV二iv=n个结点后插入一个新结点C.删除第ilv=iv=n个结点. 一棵B一树中的所有叶子结点均处在上。12 .每次从无序表中顺序取出一个元素,把这插
18、入到有序表中的适当位置,此种排序方法叫 做排序;每次从无序表中挑选出一个最小或最大元素,把它交换到有序表的一端, 此种排序方法叫做排序。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
19、)10), 那么求出该图的最小生成树的权。最小生成树的权;3 .假定一组记录的排序码为(46, 79, 56, 38, 40, 84, 50, 42),那么利用堆排序方法建立 的初始堆为O4 .有7个带权结点,其权值分别为3, 7, 8, 2, 6, 10, 14,试以它们为叶子结点生成一棵 哈夫曼树,求出该树的带权路径长度、高度、双分支结点数。带权路径长度: 高度: 双分支结点数:O四、阅读算法,答复以下问题(每题8分,共16分)1. VOldAC(List&L)(InitList(L);lnsertRcar(L;25);InsertFront(L, 50);IntaL4= 5, 8, 12
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言版 期末 考试题 附带 复习资料
限制150内