logo资料库

专升本数据结构历年真题及习题汇总.doc

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.55M 资料格式：doc 举报 版权申诉
第1页 / 共50页
第2页 / 共50页
第3页 / 共50页
第4页 / 共50页
第5页 / 共50页
第6页 / 共50页
第7页 / 共50页
第8页 / 共50页
资料共50页，剩余部分请下载后查看
    目录
    第一部分 数据结构概论及算法分析
    第二部分 线性表
    第三部分 栈 队列
    第四部分 串 数组 特殊矩阵 广义表
    第五部分 树
    第六部分 图
    第七部分 查找
    第八部分 排序
    第九部分 文件
    附录 2006年1月考题
    附录 2007年1月考题
    附录 2008年1月考题
    附录 2009年1月考题
    《数据结构》专生本辅导习题汇总 目录 目录 ............................................................................................................................................ 1 第一部分 数据结构概论及算法分析......................................................................................2 第二部分 线性表...................................................................................................................... 5 第三部分 栈 队列 .................................................................................................................. 14 第四部分 串 数组 特殊矩阵 广义表 ..................................................................................20 第五部分 树............................................................................................................................ 23 第六部分 图............................................................................................................................ 29 第七部分 查找 ........................................................................................................................ 33 第八部分 排序 ........................................................................................................................ 36 第九部分 文件 ........................................................................................................................ 39 附录 2006 年 1 月考题 ...........................................................................................................40 附录 2007 年 1 月考题 ...........................................................................................................43 附录 2008 年 1 月考题 ...........................................................................................................45 附录 2009 年 1 月考题 ...........................................................................................................47 1
    《数据结构》专生本辅导习题汇总 第一部分 数据结构概论及算法分析 一、选择题 1．数据结构是一门研究计算机中__ __对象及其关系的学科。 （1）数值运算 （2）非数值运算 （3）集合 （4）非集合 2．数据结构的定义为(K，R)，其中 K 是__ __的集合。 （1）算法 （2）数据元素（3）数据操作 （4）逻辑结构 3．算法分析的目的是____。 （1） 找出数据结构的合理性 （3） 分析算法的效率以求改进 （4） 分析算法的易懂性和文档性 （2） 研究算法中输入和输出的关系 4. 数据的不可分割的基本单位是_ A.元素 B.结点 C.数据类型 ___。 D.数据项 5．下列算法 suanfa2 的时间复杂度为____。 int suanfa2(int n) { int t=1； while(t<=n) t=t*2； return t； } A.O(log2n) D.O(n) 6.（ ）是具有相同特性数据元素的集合，是数据的子集。 B.O(2n) C.O(n2) A 数据符号 D 数据结构 7．与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( B 数据对象 C 数据 )。 A. 存储结构 B. 逻辑结构 C. 算法 D. 操作 8．数据结构是研究数据的（ C ）及它们之间的相互联系。 A、理想结构，物理结构 C、物理结构，逻辑结构 9．组成数据的基本单位是 （ b、理想结构，逻辑结构 d、抽象结构，逻辑结构 C ） 。 a、数据项 b、数据类型 c、数据元素 d、数据变量 10．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 11．算法指的是（ ） A．计算机程序 C．排序算法 B．解决问题的计算方法 D．解决问题的有限运算序列 12．下列算法 suanfa1 中语句"x=x*2；"的执行次数是（ B ）。 void suanfa1(int n) { int i,j,x=1； 2
    《数据结构》专生本辅导习题汇总 for(i=1；i<=n；i++) for(j=i；j<=n；j++) x=x*2； printf("%d",x)； } A.n(n-1)/2 B.n(n+1)/2 C.n2 D.nlog2n 13. 由____组成的集合是一个数据对象。 A.不同类型的数据项 C.相同类型的数据项 B.不同类型的数据元素 D.相同类型的数据元素 14．在下列选项中，哪个不是一个算法一般应该具有的基本特征_____。 A. 确定性 B. 可行性 C. 无穷性 D. 拥有足够的情报 15．在计算机中，算法是指______。 A. 查询方法 B. 加工方法 C. 解题方案准确而完整的描述 D. 排序方法 16．算法的时间复杂度是指________。 A. 执行算法程序所需要的时间 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 B. 算法程序的长度 17．算法的空间复杂度是指________。 A. 算法程序的长度 C. 算法程序所占的存储空间 B. 算法程序中的指令条数 D. 算法执行过程中所需要的存储空间 18．下面叙述正确的是_______。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 19．数据的存储结构是指______。 A. 数据所占的存储空间量 C. 数据在计算机中的顺序存储方式 B. 数据的逻辑结构在计算机中的表示 D. 存储在外存中的数据 20．算法分析的目的是_____。 A. 找出数据结构的合理性 C. 分析算法的易懂性和可靠性 B. 找出算法中输入和输出之间的关系 D. 分析算法的效率以求改进 21．________不是算法的基本特征。 A. 正确性 B. 长度有限 C. 在规定的时间内完成 D. 确定性 二、填空 1．一个数据结构在计算机中的表示(映象)称为 ________________。 2．数据结构被形式地定义为（ D, R ），其中 D 是 的有限集合， R 是 D 上 的 有限集合。 3
    《数据结构》专生本辅导习题汇总 3．一个算法的效率可分为 4．设问题规模为 n，分析下列算法的时间复杂度为 效率和 效率。 O(n1/2) 。 for (i = 1; i * i <=n; i++) {++x ; s += x} 5．设问题规模为 n，分析下列算法的时间复杂度为 O(n3) 。 for ( i =1 ; i <= n ; i++ ) for ( j = 1 ; j <= i ; j++ ) for ( k=1 ; k <= j ; k++) { ++x ; s += x ; } 6．数据的逻辑结构是从逻辑关系上描述数据，它与数据的_____无关，是独立于计算机的。 7．一个算法具有 5 个特性:______、______、______、有零个或多个输入、有一个或 多个输出。 8．算法的复杂度主要包括_________复杂度和空间复杂度。 9．数据结构包括数据的逻辑结构、数据的_________以及对数据的操作运算。 10．数据的逻辑结构被分为_______、_______、_______和_______四种。 11．在图形结构中，每个结点的前驱结点和后续结点数可以__________。 12．一种抽象数据类型包括 数据 和 操作 两个部分。 ) 三、判断 1．程序就是算法，但算法不一定是程序。( 2．数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( √) 3．非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( 4．数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。 (√ ) 5．算法一定要有输入和输出。( ) 6．算法分析的目的旨在分析算法的效率以求改进算法。( ) ) 4
    《数据结构》专生本辅导习题汇总 第二部分 线性表 一、选择题 1．关于顺序存储的叙述中,哪一条是不正确的 ( B ) A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2．长度为 n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 ( C ) A O(n) B O(1) C O(m) D O(m+n) 3．在 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是：( A ) A 访问第 i 个结点（1<=i<=n）和求第 i 个结点的直接前趋（2<=i<=n） B 在第 i 个结点（1<=i<=n）后插入一个新结点 C 删除第 i 个结点（1<=i<=n） D 将 n 个结点从小到大排序 4．一个向量第一个元素的存储地址是 100 ，每个元素的长度为 2 ，则第 5 个元素的地 址是：( B ) （ A ） 110 （ B ） 108 （ C ） 100 （ D ） 120 5．已知一个顺序存储的线性表，设每个结点需要占 m 个存储单元，若第一个结点的地址 为 da，则第 i 个结点的地址为：( A ) A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m 6．在具有 n 个结点的单链表中，实现（ A ）的操作，其算法的时间复杂度为 O(n)。 B）在地址为 p 的结点之后插入一个结点 D）删除地址为 p 的结点的后继结点 A）遍历链表和求链表的第 i 个结点 C）删除开始结点 7．链表是一种采用（ B ）存储结构存储的线性表。 （ A ）顺序 （ B ）链式 （ C ）星式 （ D ）网状 8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（ D ） （ A ）必须是连续的 （ B ）部分地址必须是连续的 （ C ）一定是不连续的 （ D ）连续或不连续都可以 9．线性表Ｌ在 （ B ）情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂 10．在长度为 n 的顺序表的第 i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数 为 ( A ) A.n-i+1 B.n-i 11．线性表是（ A ）。 C.i D.i-1 a、一个有限系列，可以为空 b、一个有限系列，不能为空 5
    《数据结构》专生本辅导习题汇总 c、一个无限系列，可以为空 d、一个无限系列，不能为空 12. （ A ）线性表。 A.(孔子,诸葛亮,曹雪芹) C.{10,11,12,13,14} B.{A,B,C,D} D.(1,2,3,...) 13. （ D ）是表示线性数据结构的。 A.循环链表 B.邻接多重表 C.孩子链表 D.单链表 14. 将线性表的数据元素以（B）结构存放, 查找一个数据元素所需时间不依赖于表长。 A.循环双链表 B.哈希(Hash)表 C.一维数组 D.单链表 15. 在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行（B）。 （A）s->link=p;p->link=s; （B）s->link=p->link;p->link=s; （C）s->link=p->link;p=s; （D）p->link=s;s->link=p; 16. 在循环链表中 first 为指向链表表头的指针，current 为链表当前指针，在循环链表中 检测 current 是否达到链表表尾的语句是( D )。 （A）current->link=NULL （C）first=current (B)first->link=current (D)current->link=first 17. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平 均比较( D )个结点。 B. n/2 A. n C.（n-1）/2 D. (n+1)/2 18. 在一个具有 n 个结点的有序单链表中，插入一新结点并仍然有序的时间复杂度为( B )。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 19. 用链表表示线性表的优点是 ( C )。 A. 便于随机存取 C. 便于插入与删除 B. 花费的存储空间比顺序表少 D. 数据元素的物理顺序与逻辑顺序相同 20. 当需要随机查找线性表的元素时,宜采用( C )作存储结构。 A. 双向链表 B. 循环链表 C. 顺序表 D. 单链表 21. 线性表的链接实现有利于（ A ）运算。 A、插入 b、读表元 c、查找 d、定位 22. 线性表采用链式存储时，其地址（ D ）。 A 必须是连续的 C 一定是不连续的 B 部分地址是连续的 D 连续与否均可以 23. 设单链表中指针 p 指着结点 a，若要删除 a 之后的结点（若存在），则需要修改指针的 操作为（ A ）。 A、p->next=p->next->next C、 p= p->next->next b、p=p->next d、p->next=p 24. 向一个有 127 个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动 （ B ）个元素。 A、8 B、63.5 C、63 D、7 6
    《数据结构》专生本辅导习题汇总 25. 向一个有 127 个元素的顺序表中删除一个元素，平均要移动（ C ）个元素 （A） 8 （B） 63.5 （C） 63 （D） 7 26. 用链表表示线性表的优点是（ A ） A 便于插入和删除操作 C 花费的存储空间较顺序存储少 B 数据元素的物理顺序与逻辑顺序相同 D 便于随即存取 27. 以下数据结构中不属于线性数据结构的是（ C ） A 队列 B 线性表 C 二叉树 D 栈 28．对长度为 N 的线性表进行顺序查找，在最坏情况下所需要的比较次数为（ B ）。 A．N+1 B．N C．(N+1)/2 D．N/2 29．下列叙述中正确的是( A )。 A. 线性表是线性结构 C. 线性链表是非线性结构 B. 栈与队列是非线性结构 D. 二叉树是线性结构 30．在单链表中，增加头结点的目的是( A )。 A. 方便运算的实现 C. 标识表结点中首结点的位置 B. 使单链表至少有一个结点 D. 说明单链表是线性表的链式存储实现 31．线性表的顺序存储结构和线性表的链式存储结构分别是（ B ）。 A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构 33．线性表中正确的说法是( D )。 A. 每个元素都有一个直接前驱和一个直接后继 B. 线性表至少要求一个元素 C. 表中的元素必须按由小到大或由大到小排序 D. 除了第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接 后继 34．线性表是具有 n 个（ C ）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 35．若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时 间复杂度为（ C ）。（1≤i≤n+1） A. O(0) B. O(1) C. O(n) D. O(n2) 36．在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度（B）。 A. O(1) B. O(n) C. O(nlogn) D. O(n2) 37．某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运 算是指删除表头第一个元素，那么采用（ A ）存储方式最节省运算时间。 A. 仅有尾指针的单向循环链表 C. 单向链表 B. 仅有头指针的单向循环链表 D. 双向链表 二、填空题 1．在单项链表中删除一个指定结点的后继的时间复杂度为 [ O(1) ] 7
    《数据结构》专生本辅导习题汇总 2．线性表中 ____________________________ 称为表的长度。 3. 在 n 个 结 点 的 单 链 表 中 ， 在 P 指 向 的 结 点 之 后 插 入 一 个 结 点 的 时 间 复 杂 度 为 ______ 。 4．设长度为 n 的线性表顺序存贮,若在它的第 i-1 和第 i 个元素之间插入一个元素, 共需移 动 _________ 个元素(1link; p->link=____ Delete q __ 9．将适当的语句添入单链表搜索函数 find 中。 templateListNode*List::find(Type value) { current=first->link； while(current!=NULL) if(current->data=value) break else current=current->link; return _____ __ } 10．顺序存储方法是把逻辑上相邻的结点存储在物理位置 ________ 的存储单元中。 11．顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻。因此，这种表 便于__随机__访问，是一种__随机访问__。 12．在一个不带头结点的单链表中，在表头插入或删除与其在其他位置插入或删除操 作的过程___________。 13．已知 L 是无头结点的单链表，且 P 结点既不是首元素结点，也不是尾元素结点， 添加合适的语句。 1) P 结点之后插入结点 S：S->next=P->next; P->next=S; 2) P 结点之前插入结点 S： pre=L; while(pre->next!=P) pre=pre->next; S->next=P; pre->next=S; 3) 在表首插入结点 S：S->next=L; L=S; 4) 在表尾插入结点 S： while(P->next) P=P->next; 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料