数据结构习题库(c语言版)

《数据结构习题库(c语言版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论一、基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义、抽象数据类型的定义、表示和实现方法、描述算法的类C语言、算法设计的基本要求。二、学习要点1、熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。2、了解抽象数据类型的定义、表示和实现方法。3、熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。4、理解算法五个要素的确切含义。1.1基础知识一

2、、填空题1、数据的逻辑结构包括①，②，③和④四种类型，树型结构和图型结构合称为⑤，数据的存储结构即物理结构包括：⑥，⑦等两种基本类型。2、在线性结构中元素之间存在①关系，树形结构中元素间存在②关系，图形结构中元素间存在③关系。3、一个数据结构用二元组表示时，它包括①集合D和D上②的集合S。4、一个算法应具有①，②，③，④和⑤这五个特性。5、在图形结构中，每个节点的前驱节点和后继节点可以有①个。6、一个抽象数据类型用三元组（D，S，P）表示时，D是①，S是②，P是③。7、数据元素在计算机中的映象是①。8

3、、算法的设计取决于①，算法的实现取决于②。二、选择题1、数据元素是数据的单位。(A)基本(B)最小2、使用指针表示数据元素之间逻辑关系的存储结构是。(A)顺序结构(B)链式结构(C)树状结构(D)图状结构3、以下____术语与数据的存储结构无关。(A)线索二叉树(B)双向链表(C)栈(D)哈希表4、以下____术语与数据的逻辑结构无关。(A)线性结构(B)链式结构(C)树型结构(D)网状结构5、指出下列叙述____不属于算法的特性。(A)有穷性(B)复杂性(C)可行性(D)确定性6、以下数据结构中__

4、__是线性结构。(A)队列(B)有向图(C)树(D)哈夫曼树解答：一、填空题1、①线性②集合③树④图或网⑤非线性结构⑥顺序存储⑦链式存储2、①1：1②1：n③m：n3、①数据元素②关系4、①有穷性②确定性③可行性④输入⑤输出5、①多个6、①数据对象②D上的关系集合③对D的基本操作集合7、①元素或结点8、①数据（逻辑）结构②采用的存储结构一、选择题1、A2、B3、C4、B5、B6、Al.2应用知识1、什么是算法？算法的特性是什么？算法设计的要求是什么?解答:（略）2、设有数据结构USER_STRU表示如

5、下：USER_STRU=（D，S）D={a1，a2，…，a9}S={，，，，，，，，，，}画出这个数据结构的图示，并确定其类型。解答：该结构的图示如下，该结构为图形结构。a2a4a5a6a7a3a1a9a83、设有数据结构USER_STRU表示如下：USER_STRU=（D，S）D={a1，a2，…，a9}S={，，

6、，a4>，，，，，}画出这个数据结构的图示，并确定其类型。解答：该结构的图示如下，该结构为树形结构。a1a2a3a6a4a8a7a5a94、影响高级语言程序运行消耗时间的因素有哪些？解答：主要有以下因素：(1)算法选用的策略；(2)问题的规模；(3)书写程序的语言；(4)编译程序产生的机器代码质量；(5)机器执行指令的速度。5、选择解决某种问题的最佳数据结构的标准是什么?解答：一般有两条标准：(1)所需的存储空间量；(2)算法所需要

7、的时间；而算法所需要的时间又包括以下几点：(1)程序运行时所需要的数据总量；(2)源程序进行编译所需要的时间；(3)计算机执行每条指令所需要的时间；(4)程序中的指令重复执行的次数，而本条正是讨论算法中的重点内容。6、设三个函数f,g,h分别为f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn请判断下列关系是否成立：(1)f(n)=O(g(n)) (2)g(n)=O(f(n)) (3)h(n)=O(n1.5)(4)h(n)=O(nlgn)解答：

8、（1）成立； （2）成立；（3）成立；（4）不成立。7、设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。(1)i=1;k=0; 　　while(ij)j++;　　　　elsei++;　　　}(4)x=n