数据结构试题样题及答案
数据结构试题样题及答案 一、单项选择题(每小题2分,共30分) 1.数据结构中,与所使用的计算机无关的是数据的()结构。 A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理 2.下述各类表中可以随机访问的是()。 A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表 3.在一个长度为n的顺序表中为了删除第5个元素,从前到后依次移动了15个元素。则原顺序表的长度为()。 A. 21 B. 20 C. 19 D. 25 4.元素2,4,6按顺序依次进栈,则该栈的不可能的输出序列是()。 A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 4 5.一个队列的入队序列是5,6,7,8,则队列的输出序列是()。 A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况 6. 串函数StrCmp(“d”,“D”)的值为()。 A.0 B.1 C.-1 D.3 7.在一个单链表中,p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继,现要删除q所指结点,可用语句()。 A.p=q→next B.p→next=q C.p→next=q→next D.q→next=NULL 8.设一棵哈夫曼树共有n个非叶结点,则该树一共有()个结点。 A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 9.对如图1所示二叉树进行中序遍历,结果是()。 A. dfebagc B. defbagc C. defbacg D.dbaefcg 图1 10 . 任何一个无向连通图的最小生成树()。 A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在 11.设有一个10阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵中元素A8,5在一维数组B中的下标是()。 A.33 B.32 C.85 D.41 12 .一组记录的关键字序列为(37,70,47,29,31,85),利用快速排序,以第一个关键字为分割元素,经过一次划分后结果为()。 A.31,29,37,85,47,70 B.29,31,37,47,70,85
2017年数据结构期末考试题及答案A
2017年数据结构期末考试题及答案 一、选择题(共计50分,每题2分,共25题) 1 ?在数据结构中,从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时,一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中,正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点,则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点(由p所指向)满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
一步一步迈向成功
一步一步走向成功 一个老板的自述故事:那是在15年前,我到这个城市出差,谈完生意,我去商场给同事买些礼物。平时,我逛商场时喜欢随身带一些硬币,因为商场附近有时会有乞讨的人,给上一两枚硬币我心里会踏实些。这天也是这样,口袋里依旧有些硬币,于是我就将十几枚硬币散给一帮乞讨的小乞丐。 就在这时,我看见一个男孩高举着一块牌子看着我,无疑,他想引起我的注意。我朝他走过去,看到他约摸十三四岁,衣着破旧却很干净,头发也梳得整齐。他不像别人手里拿个搪瓷缸,他的牌子一面画着一个男孩在擦鞋,一面写着:“我想要一只擦鞋箱。” 那时我正在做投资生意,反正还有时间,我便问男孩需要多少钱,男孩说:“125元。” 我摇摇头,说他要的擦鞋箱太昂贵了。男孩说不贵,还说他已经去过批发市场4次,都看过了,要买专用箱子、凳子、清洁油、软毛刷和十几种鞋油,没有125元就达不到他的要求。男孩操着方言,说得有板有眼。 我问他现在手里有多少钱,男孩想都没想,说已经有35元,还少90元。我认真看着男孩,确定他不是个小骗子,便掏出钱夹,拿出90元,说:“这90元钱给你,算是我的投资。有个条件,从你接过钱的这一刻起,我们就是合伙人了。我在这个城市呆5天,5天内你不仅要把90元钱还给我,我还要1元钱的利息。如果你答应这条件,这90元现在就归你。” 男孩兴奋地看着我,满口答应。男孩还告诉我,他读六年级,每星期只去上3天课,另外几天要放牛、放羊和帮母亲种地,可他的成绩从没有滑下过前三名,所以,他是最棒的。我问他为什么要买擦鞋箱,他说:“因为家里穷,我要趁着暑假出来,攒够学费。” 我以一种欣赏的眼光看着男孩,然后陪他去批发市场选购了擦鞋箱和其他各种擦鞋用具。 男孩背着箱子,准备在商场门口摆下摊位。我摇摇头,说:“作为你的合伙人,为了收回自己的成本,有义务提醒你选择合适的经营地点。”商场内部有免费擦鞋器,很多人都知道。男孩认真想了想,问:”选在对面的酒店怎么样?”我想:“这里是旅游城市,每天都有一车一车的人住进那家酒店,他们旅途劳顿,第二天出行时,肯定需要把鞋擦得干干净净。”想到这些,我就答应了他。于是,男孩在酒店门口附近落脚了,他把擦鞋箱放到了离门口稍远的地方,他看看左右无人,对我说:“为什么不让我现在就付清1元钱利息?你也应该知道我的服务水平。”我“扑哧”一声笑了,这小家伙真是鬼得很,他是要给我擦鞋,用擦鞋的收费抵那1元的利息。我欣赏他的精明,便坐到他的板凳上,说:“你要是擦得不好,就证明你在说谎,而我投资给一个不诚实的人,就证明我的投资失败。”男孩的头晃得像拨浪鼓,说他是最棒的,他在家里练习擦皮鞋练了一个月。要知道,农村并没有多少人有几双好皮鞋,他是一家一家地让他们把皮鞋拿出来,细心地擦净擦亮的。几分钟后,看着皮鞋光可鉴人,我满意地点头。我从口袋里拿出红笔,在他的左右脸颊上写下两个大字:“最棒。”男孩乐了。正在这时,有一辆中巴车载着一车游客过来了,他连忙背着擦鞋箱跑过去,指着自己的脸对那些陆续下车的旅客说:“这是顾客对我的奖赏,你想试试吗?我会把你的皮鞋变成镜子的。”就这样,男孩忙碌起来了…… 第二天,我来到酒店,看到男孩早早来守摊了,他兴奋地告诉我,他昨天赚到了50块钱,除去给我18元,吃饭花3元,他净剩29元。我拍拍他的头,夸他干得不错。他说昨晚没睡地道桥,而是睡了大通铺,但没交5块钱的铺位钱。我疑惑了,怎么会不付床铺钱?这时,
数据结构试题(含答案)
数据结构试题(含答案) 1.数据逻辑结构包括线性结构、树形结构和图状结构三种类型,树形结构和图状结构合称非线性结构 2.数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3.在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有 1 个后续结点。 4.线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。 5.在树形结构中,树根结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;叶子结点没. 6.数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点,其余每个结点的后续结点可以任意多个。 7.衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8.评估一个算法的优劣,通常从时间复杂度和空间复杂度两个方面考察。 9.算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10.在单链表中,要删除某一指定的结点,必须找到该结点的前驱结点。 11.在单链表中,要删除某一指定的结点,必须找到该结点的前驱结点。 12.在双链表中,每个结点有两个指针域,一个指向前驱结点,另一个指向后继结点。13.在顺序表中插入或删除一个数据元素,需要平均移动 n 个数据元素,移动数据元素的个数与位置有关 14.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表的元素是,应采用顺序存储结构 15.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成单链表和双链表。 16.顺序存储结构是通过下标表示元素之间的关系的;链式存储结构是通过指针表示元素之间的关系的 17.带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18.栈是限定仅在表尾进行插入或删除操作的线性表,其运算遵循后进先出的原则。19.空串是零个字符的串,其长度等于零。空白串是由一个或多个空格字符组成的串,其长度等于其包含的空格个数。 20.组成串的数据元素只能是单个字符。 21.一个子串”str”在主串”datastructure”中的位置是 5 。 22.字符串中任意个连续字符构成的部分称为该串的子串。 23.二维数组M的每个元素是6个字符组成的串,行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要 540个字节;M的第8列和第5行共占108个字节24.稀疏矩阵一般的压缩存储方法有两种,即三元组表和十字链表。 25.广义表((a),((b),c),(((d))))的长度是 3 ,深度是 4 。 26.在一棵二叉树中,度为零的结点的个数为n0,度为2 的结点的个数为n2,则有n0= n2+1 。 27.在有n个结点的二叉链表中,空链域的个数为__n+1__。 28.一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29.深度为5的二叉树至多有 31 个结点。 30.若某二叉树有20个叶子结点,有30个结点仅有一个孩子,则该二叉树的总结点个数为69 。
数据结构期末考试试卷样卷
《数据结构》期末考试试卷样卷 成绩________ 一、单项选择题:(每题2分,共30分) 1、以下说法正确的是()。 A. 数据元素是数据的最小单位 B. 数据项是数据的基本单位 C. 数据结构是带有结构的各数据项的集合 D. 一些表面上很不相同的数据可以有相同的逻辑结构 2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。 A. 存储结构 B. 存储实现 C. 逻辑结构 D. 运算实现 3、判断一个队列QU(最多元素为m0)为满队的条件是()。 A. QU->rear-QU->front==m0 B. QU->rear-QU->front-1==m0 C. QU->rear==QU->front D. QU->front==QU->rear+1 4、给定n个数据元素,建立对应的有序单链表的时间复杂度是()。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 5、一个非空广义表的表头()。 A. 不可能是子表 B. 只能是子表 C. 原子或子表均可 D. 只能是原子 6、设完全二叉树中拥有65 个结点,则其深度为()。 A. 5 B. 6 C. 7 D. 8 7、根据二叉树的(),可以唯一确定该二叉树的形态。 A. 先序和中序序列 B. 先序和后序序列 C. 中序和后序序列 D. 先序和层序序列 8、若广义表A满足Head(A)=Tail(A),则A为()。 A. () B. (()) C. ((),()) D. ((),(),()) 9、下面不正确的说法是()。 (1)在AOE网中,减少任一关键活动上的权值后,整个工期也就相应减小; (2)AOE网工程的工期为关键活动上的权值之和; (3)在关键路径上的活动都是关键活动,而关键活动也必定在关键路径上。 A. (1) B. (2) C. (3) D. (1) 、(2) 10、图的深度优先遍历算法分别类似于二叉树的()。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 11、从图的邻接矩阵中,容易确定()。 A. 主对角线的元素全部为1 B. 主对角线的元素不全为0 C. 任意两个顶点之间是否关联 D. 是否为一个连通图 12、顺序查找适用于存储结构为()的线性表。 A. 散列存储 B. 压缩存储 C. 顺序存储或链式存储 D. 索引存储 13、从具有n个结点的二叉排序树中查找一个元素时,最坏情况下的时间复杂度为()。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 14、在关键字随机分布的情况下,用二叉排序树进行查找,其查找长度与()量级相当。 A. 顺序查找 B. 折半查找 C. 分块查找 D. 均不是 15、一组记录的关键字序列为{46,79,56,38,40,84},利用快速排序方法,以第一个记录为基准得到的一次划分是()。 A. 38,40,46,56,79,84 B. 40,38,46,79,56,84 C. 40,38,46,56,79,84 D. 40,38,46,84,56,79 - 1 -
数据结构试题及答案
一、判断题: 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算:插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构,数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。() 8、线性的数据结构可以顺序存储,也可以链接存储。非线性的数据结构只能链接存储。() 9、栈和队列逻辑上都是线性表。() 10、单链表从任何一个结点出发,都能访问到所有结点() 11、删除二叉排序树中一个结点,再重新插入上去,一定能得到原来的二叉排序树。() 12、快速排序是排序算法中最快的一种。() 13、多维数组是向量的推广。() 14、一般树和二叉树的结点数目都可以为0。() 15、直接选择排序是一种不稳定的排序方法。() 16、98、对一个堆按层次遍历,不一定能得到一个有序序列。() 17、在只有度为0和度为k的结点的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,则有n0=nk+1。() 18、折半搜索只适用与有序表,包括有序的顺序表和有序的链表。() 19、堆栈在数据中的存储原则是先进先出。() 20、队列在数据中的存储原则是后进先出。() 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。() 22、哈夫曼树一定是满二叉树。() 23、程序是用计算机语言表述的算法。() 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。() 25、用一组地址连续的存储单元存放的元素一定构成线性表。() 26、堆栈、队列和数组的逻辑结构都是线性表结构。() 27、给定一组权值,可以唯一构造出一棵哈夫曼树。() 28、只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。()
数据结构研究生入学考试模拟题(一)
哈尔滨工业大学 二〇〇八年硕士研究生考试模拟试题(一) 考试科目:计算机专业基础 适用专业:计算机科学与技术 I 数据结构(含高级语言)部分(共75分) 一、填空题(每空1分,共9分) +?++的后缀表达式 1.表达式23((12*32)/434*5/7)108/9 是。 2.设有一个10阶对称矩阵A采用压缩存储方式(以行为主序存储:a11=1),则a85 的地址为。 3.设有广义表A=(((a,b),x),((a),(b)),(c,(d,(y)))),得到y的对广义表 A的操作序列为。 4.如果二叉树有20个叶结点,有30个结点仅有一个孩子,则该二叉树的总节点数 为。 5.G是一个非连通无向图,共有28条边,则该图至少有个顶点。 6.构造n个结点的强联通图,至少有条弧。 7.设表长为1023的有序线性表,查找每个元素的概率相等,采用折半查找方法,查 找成功的ASL是。 8.分别采用堆排序、快速排序、冒泡排序和归并排序,对初太为有序的表,则最省时 间的是算法,最费时间的是算法。 二、单项选择题(每题1分,共11分) 1.静态链表中指针表示的是() A 下一元素的地址 B 内存储器的地址 C 下一元素在数组中的位置 D 左链或右链指向的元素的地址 2.计算算法的时间复杂度是属于一种() A 事前统计的方法 B 事前分析估算的方法 C 事后统计的方法 D 时候分析估算的方法 3.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3, 当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为() A 1和5 B 2和4 C 4和2 D 5和1 4.若6行5列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个存储 单元,则第3行第4列的元素(假定无第0行第0列)的地址是() A 1040 B 1042 C 1026 D 都不正确 5.一棵124个叶节点的完全二叉树,最多有()个节点。
《数据结构》期末考试题及答案
2011-2012学年第一学期期末考查 《数据结构》试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一、选择(每题1分,共10分) 1.长度为n的线性表采用顺序存储结构,一个在其第i个位置插入新元素的算法时间复杂度为(D) A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6,5,4,3,2,1的顺序入栈,下列哪一个是合法的出栈序列?(D) A.543612 B.453126 C.346512 D.234156 3.设树的度为4,其中度为1、2、3、4的结点个数分别是4、2、1、2,则树中叶子个数为(B ) A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点,B的右子树结点个数为n,森林F中第一棵树的结点个数是( B ) A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B) A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。(A) A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有(B )个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树,与用其他三个序列构造的结果不同的是(B) A.(100,80,90,60,120,110,130) B.(100, 120, 110,130,80, 60,90) C.(100,60,80,90,120,110,130) D.(100,80, 60,90, 120, 130,110) 9.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序过程中变化如下:(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47(4)15 21 25 47 84则采用的排序方法是(B ) A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时,要求线性表必须(D) A.以顺序方式存储 B.以顺序方式存储,且数据元素有序
小班绘本故事《一步一步,走啊走》
小班绘本故事《一步一步、走啊走》 设计意图 1、当我看到《一步一步走啊走》这个绘本时,就被它其中的动物表情、动作给吸引了。故事中的动物都是幼儿比较熟悉喜欢的,故事的情节又比较简单有趣,很适合小班孩子活泼、好动、注意力易分散的特点。在教学活动中,我创设了一定的教学情境,通过观察、模仿,了解各小动物的走路特点,并能大胆用语言来讲述画面,感受绘本的情趣,充分体验活动的快乐 2、数学教育一直是大家感到畏难的事情,数学活动相对比较枯燥,我想尝试利用绘本的情节,让幼儿在仔细观察概括的基础上,轻松自然地获得一些简单的数学知识,促进孩子对数学活动的兴趣。活动目标 1、知识目标:通过观察和阅读绘本,理解故事内容,了解各种小动物走路的样子,愿意大胆的模仿小动物走路。(重点) 2、能力目标:在绘本的情景中尝试有序地排列,积累相应的数经验。(难点) 3、情感目标:体验集体阅读和表演所带来的乐趣。 重点难点 1、知识目标:通过观察和阅读绘本,理解故事内容,了解各种小动物走路的样子,愿意大胆的模仿小动物走路。(重点) 2、能力目标:在绘本的情景中尝试有序地排列,积累相应的数经验。(难点)
活动准备 1、PPT课件。 2、操作材料:蓝色纸条小路,小弟弟图片,小乌龟图片,大白鸭图片,小灰兔图片,大鸵鸟图片。 活动过程 (一)、以“羊村”吸引幼儿注意,导入活动(PPT显示羊村) 1、教师:今天老师要带你们去一个地方玩,看看是哪里呢?(羊村)“羊村里住着谁呢?”(引导幼儿说出喜羊羊、美羊羊、懒羊羊等自己喜欢的角色)“今天我们就到羊村去玩一玩。” 2、你们看,有一条小路通向羊村。老师这里也有一条玩具的、蓝色的小路。老师在桌上放了这么多蓝色的小路,你去找一条好吧?引导幼儿自己找出蓝色的“小路”放在空处,别做“挤羊羊”。 (二)、观察画面,导入故事情节 1、师:我们准备出发啦!有很多朋友也想去“羊村”,看来了谁?(PPT演示小弟弟走啊走),同时让每位幼儿操作“小弟弟”走在“小路”上。 师:有个小弟弟也想到羊村去,小弟弟是怎么走路的? 幼:一步一步走,教师肯定幼儿的说法并马上请她来尝试走一走。孩子边走教师边说:一步一步走啊走……请所有小朋友一起学一学小弟弟走路。 2、出示乌龟的图片,请幼儿仔细观察图片,引导幼儿说出乌龟的行走方式,并模仿乌龟一步一步爬啊爬的动作。
数据结构试题及答案
数据结构试卷(十一) 一、选择题(30分) 1.设某无向图有n个顶点,则该无向图的邻接表中有()个表头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 2.设无向图G中有n个顶点,则该无向图的最小生成树上有()条边。 (A) n (B) n-1 (C) 2n (D) 2n-1 3.设一组初始记录关键字序列为(60,80,55,40,42,85),则以第一个关键字45为基准而得到的一趟快速排序结果是()。 (A) 40,42,60,55,80,85 (B) 42,45,55,60,85,80 (C) 42,40,55,60,80,85 (D) 42,40,60,85,55,80 4.()二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历 5.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号,则编号为i结点的左孩子结点的编号为()。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 6.程序段s=i=0;do {i=i+1; s=s+i;}while(i<=n);的时间复杂度为()。 7.设带有头结点的单向循环链表的头指针变23 (A) O(n) (B) O(nlogn) (C) O(n) (D) O(n/2)2 量为head,则其判空条件是()。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 8.设某棵二叉树的高度为10,则该二叉树上叶子结点最多有()。 (A) 20 (B) 256 (C) 512 (D) 1024 9.设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字90需要比较的关键字个数为()。 (A) 1 (B) 2 (C) 3 (D) 4 10.设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为()。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 二、判断题(20分) 1.不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑“溢出”情况。()2.当向二叉排序树中插入一个结点,则该结点一定成为叶子结点。() 3.设某堆中有n个结点,则在该堆中插入一个新结点的时间复杂度为O(logn)。()24.完全二叉树中的叶子结点只可能在最后两层中出现。() 5.哈夫曼树中没有度数为1的结点。() 6.对连通图进行深度优先遍历可以访问到该图中的所有顶点。() 7.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()
数据结构模拟题及答案
数据结构试题(A05) 一、选择题(共10小题,每小题1分,共10分) 1.下面程序段的时间复杂度是( ) m=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) m=m+1; A. O(n2) B.O(m+n+1) C.O(m+n) D. O(n) 2.在单链表中,指针p指向元素为x的结点,实现“删除x的后继”的语句是( ) A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在长度为n的顺序表,当在任何位置上删除一个元素的概率相等时,删除一个元素需要移动的元素的平均个数为( ) A.n/2 B.(n-1)/ 2 C.(n+1)/2 D.(n+2)/2 4.一个栈的输入序列为 1 2 3 4 5,则下列序列中不可能是栈的输出序列的是( ) A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 6.设循环队列中数组的下标范围是1~n,其头尾指针分别为f和r,则其元素个数为( ) A. r-f B. r-f+1 C. (r-f) mod n+1 D. (r-f+n) mod n 7.以下序列不是堆的是( )。 A.(100,85,98,77,80,60,82,40,20,10,66) B.(100,98,85,82,80,77,66,60,40,20,10) C.(100,85,40,77,80,60,66,98,82,10,20) D.(10,20,40,60,66,77,80,82,85,98,100) 8.在有序表(12,24,36,48,60,72,84)中折半查找关键字72时所需进行的关键字比较次数为( )。 A. 3 B. 4 C. 5 D. 2 9.在待排序的元素序列基本有序的前提下,效率最高的排序方法是( )。 A.选择排序 B.冒泡排序 C.快速排序 D.插入排序 二、填空题(共20小题,每小题1分,共20分) 1、在单链表中,删除指针P所指结点的后继结点的语句是。 2、线性表的两种存储结构分别是和。 3、己知完全二叉树的第4层有5个结点,则其叶子结点数是。 4、将下三角矩阵A[1….8,1….8]的下三角部分逐行地存储到起始地址为1000的内存单元中,已知每个元素占4个单元,则A[7,5]的地址是。 5、有n个结点的强连通有向图G至少有条弧。 7、在有序表A[1….20]中,采用二分查找算法查找元素值等于A[12]的元素,所
2017数据结构期末考试试题及答案
2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1.
数据结构》期末考试试题及答案 1 单选题(每题 2 分,共 20 分) 1. 栈和队列的共同特点是 ( )。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列,在进行插入运算时 ( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构? ( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n],假设A[0][0]存放位置在644(io ), A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中,第一个元素放A[1]中, 现进行二分查找,则查找 A [3]的比较序列的下标依次为( A. 1 , 2, 3 B. 9, 5, 2, 3 C. 9, 5, 3 D. 9, 4, 2, 3 8. 对n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O (1) B. O (n ) C. O ( 1 og 2n ) D. O (n2) 9. 对于线性表( 7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时,若选 用 H (K )=K %9 作为散列函数,则散列地址为 1 的元素有( )个, 位置在 676(10),每个元素占一个空间, 表示用 10 进制表示。 问 A[3][3] (10)存放在什么位置?脚注 (10) 5. A .688 B .678 C . 692 D . 696 树最适合用来表示 ( )。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 ( ). A .2-1 B.2K+1 C.2K-1 D. 2k-1 7.
数据结构试题及答案
数据结构试题 一、单选题(每题 2 分,共20分) 1.1. 对一个算法的评价,不包括如下( B )方面的容。 A.健壮性和可读性B.并行性 C.正确性 D.时空复杂度 2.2. 在带有头结点的单链表HL中,要向表头插入一个由指针p 指向的结点,则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3. 对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4. 一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输 出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5. AOV网是一种( D )。 A.有向图 B.无向图 C.无向无环图D.有向无环图 6.6. 采用开放定址法处理散列表的冲突时,其平均查找长度 ( B )。 A.低于法处理冲突 B. 高于法处理冲突 C.与法处理冲突相同 D.高于二分查找 7.7. 若需要利用形参直接访问实参时,应将形参变量说明为( D ) 参数。 A.值 B.函数 C.指针 D.引用 8.8. 在稀疏矩阵的带行指针向量的存储中,每个单链表中的结点 都具有相同的( A )。 A.行号B.列号 C.元素值 D.非零元素个数 9.9. 快速排序在最坏情况下的时间复杂度为( D )。 A.O(log 2n) B.O(nlog 2 n) C.O(n) D.O(n2) 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题(每题 6 分,共24分) 1. 1. 数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M 对N(M:N)的联系时,称这种结构为图(或图结构)。 2. 2.队列的插入操作是在队列的__队尾___进行,删除操作是在队列的_对头_ 进行。 3. 3. 当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,
数据结构考试题
要求:所有的题目的解答均写在答题纸上(每张答题纸上要写清楚姓名、班号和学号),需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题(每小题2分,共20分) 1. 在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 。 A. 数据的处理方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存储方法 2. 下述函数中对应的渐进时间复杂度(n 为问题规模)最小是 。 (n)=nlog 2n+5000n (n)=n 2 -8000n (n)= n n 2 log -6000n (n)=7000log 2n 3. 设线性表有n 个元素,以下操作中, 在顺序表上实现比在链表上实现效率更高。 A.输出第i (1≤i ≤n )个元素值 B.交换第1个元素与第2个元素的值 C.顺序输出这n 个元素的值 D.输出与给定值x 相等的元素在线性表中的序号 4. 设n 个元素进栈序列是p 1,p 2,p 3,…,p n ,其输出序列是1,2,3,…,n ,若p 3=3,则p 1的值 。 A.可能是2 B.一定是2 C.不可能是1 D.一定是1 5. 以下各种存储结构中,最适合用作链队的链表是 。 A.带队首指针和队尾指针的循环单链表 B.带队首指针和队尾指针的非循环单链表 C.只带队首指针的非循环单链表 D.只带队首指针的循环单链表 6. 对于链串s (长度为n ,每个结点存储一个字符),查找元素值为ch 的算法的时间复杂度为 。 (1) (n) (n 2) D.以上都不对 7. 设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素a[3][5]的存储地址为1000,则a[0][0]的存储地址是 。 8. 一个具有1025个结点的二叉树的高h 为 。 ~1025 ~1024 9. 一棵二叉树的后序遍历序列为DABEC ,中序遍历序列为DEBAC ,则先序遍历序列为 。 10. 对图1所示的无向图,从顶点1开始进行深度优先遍历;可得到顶点访问序列 。