下载文档原格式
《数据结构》吕云翔编著第1章绪论习题解答数据结构第一章绪论习题一、【单选题】1. （A）是数据的基本单位。
Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构2. （C）是数据的不可分割的最小单位。
Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构3. 若采用非顺序映象，则数据元素在内存中占用的存储空间（C）。
Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续4. 若采用顺序映象，则数据元素在内存中占用的存储空间（A）。
Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续5. 在数据结构中，从逻辑上可以把数据结构分为（C）Ａ、动态结构和静态结构Ｂ、紧凑结构和非紧凑结构Ｃ、线性结构和非线性结构Ｄ、内部结构和外部结构6. 在树形结构中，数据元素间存在（B）的关系。
Ａ、一对一Ｂ、一对多Ｃ、多对多Ｄ、除同属一个集合外别无关系7. 下列说法中错误的是（B）。
Ａ、数据对象是数据的子集Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作8. 计算机算法指的是（C）。
Ａ、计算方法Ｂ、排序方法Ｃ、解决问题的有限运算序列Ｄ、调度方法9. 下列不属算法特性的是（D）。
Ａ、有穷性Ｂ、确定性Ｃ、零或多个输入Ｄ、健壮性10.算法分析的目的是（C）。
Ａ、找出数据结构的合理性Ｂ、研究算法中的输入和输出的关系Ｃ、分析算法的效率以求改进Ｄ、分析算法的易读性和文档性11.算法分析的两个主要方面是（A）。
Ａ、空间复杂性和时间复杂性Ｂ、正确性和简明性Ｃ、可读性和文档性Ｄ、数据复杂性和程序复杂性12.算法的计算量的大小称为算法的（A）。
Ａ、效率Ｂ、复杂性Ｃ、现实性Ｄ、难度13.在下面的程序段中，对x的赋值语句的频度为（C）。
for(i=1;i<=n;++i)for(j=1;j<=n;++j)x=x+1;Ａ、2nＢ、nＣ、n2Ｄ、log2n14.设n为正整数，则如下程序段中最后一行的语句频度在最坏情况下是（D）。
北京交通大学考试试题（A卷）课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇(请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场)一、填空题（每空2分，共20分）1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为的数据结构。
2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。
3. 直接插入排序用监视哨的作用是。
4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算是。
5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。
被比较元素除A[4]外，还有。
6. 在AOV网中，顶点表示，边表示。
7. 有向图G可进行拓扑排序的判别条件是。
8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。
二、选择题（每空2分，共20分）1.在下列存储形式中，哪一个不是树的存储形式？（）A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法2.查找n个元素的有序表时，最有效的查找方法是（）。
A．顺序查找B．分块查找C．折半查找D．二叉查找3.将所示的s所指结点加到p所指结点之后，其语句应为（）。
p(A) s->next=p+1 ; p->next=s;(B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s;4.在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。
数据结构部分课后习题答案(1-3)第一章1.1数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。
数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。
1.2事前分析和事后统计事前分析：优点，程序不必运行，所得结果只依赖于算法本身缺点，不够精确事后统计：优点，精确缺点，必须运行程序，所得结果依赖于硬件、环境等因素1.3void func(int n){int i=1,k=100;while(i<n){k++;i+=2;}}考虑赋值、运算操作执行的次数第3行赋值2次第6行赋值执行n次，加法执行n次所以，总共2n+2次操作，算法复杂度为O(n)1.4y=y+i*j执行次数：1.5第二章2.9内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
答：S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。
2.10线性表是数据项组成的一种有限且有序的序列，各元素之间呈线性关系。
从逻辑结构来说，栈和队列与线性表相同，都是典型的线性结构。
与线性表不同的是，栈和队列的操作特殊，受到一定的限制，仅允许在线性表的一端或两端进行。
栈是限定仅在一端进行插入删除的线性表，无论插入、删除还是读取都在一端进行，按后进先出的原则。
队列的元素只能从一端插入，从另一端删除，按先进先出的原则进行数据的存取。
2.11共有132种合法序列。
235641序列可以。
154623序列不可以。
对于每一个数来说，必须进栈一次、出栈一次。
我们把进栈设为状态‘1’，出栈设为状态‘0’。
n个数的所有状态对应n个1和n个0组成的2n位二进制数。
目 录2015年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 2013年北京交通大学计算机与信息技术学院925数据结构考研真题（回忆版） ............................... 2007年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 2006年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 2005年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 2002年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 2001年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 2000年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 1999年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 1998年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 1997年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 1996年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 1995年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 1994年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 1993年北京交通大学计算机与信息技术学院925数据结构考研真题 .................................................... 北京交通大学计算机与信息技术学院数据结构历年考研真题汇编最新资料，WORD 格式，可编辑修改！2013年北京交通大学计算机与信息技术学院925数据结构考研真题（回忆版）一、填空题（15x2）1．一个数据结构的抽象数据类型（ADT）包括哪三部分2．n个顺序存储删除第i个元素需要移动多少个元素3．有向完全图又多少条弧4．用邻接表表示的无向图有n个顶点e条边在邻接表中有多少个边结点5．强连通图至少包含几条弧6．((a,(b,d),c),(e,(f,g),k)) 广义表的深度和长度是多少（具体的变量记不清了）7．有31个结点的有序序列在等概率的条件下查找成功的平均查找长度8．有2013个结点的哈夫曼树有多少个叶子结点二、选择题（15x2）1．abcde入栈得不到下列哪个序列2．双向循环链表在p节点后插入s结点的操作3．给了一个哈希表问用链式存储哈希函数H（key）mod11 问1的顶点结点有多少个链接结点4．深度为6的完全二叉树最多最少有多少结点5．后序线索二叉树若一个结点即有左子树也有右子树则他的后继结点是三、判断题（15x1）1．栈的数据元素是先进后出队列的数据元素是先进先出2．无向图的邻接矩阵一定是是对称矩阵有向图的一定不是对称矩阵四、简答题1．将森林转化为二叉树2．一个n个结点的完全二叉树有多少叶子结点（结果用n表示）3．建立小顶堆画出建立初始堆的过程4．画平衡二叉树5．哈希表平方探测解决冲突计算等概率查找成功平均查找长度6．图的深度优先遍历序列prim生成最小代价树并求最小代价7．AOE网的关键路径五、算法题（4x10）1．程序填空中序线索二叉树2．程序填空折半查找3．读程序写结果有个大程序包括三个子程序个人理解分别是先序生成二叉树中序遍历并判断是否为二叉排序树4．算法设计求无向连通图的简单路径1999年北京交通大学计算机与信息技术学院925数据结构考研真题。
第一章 绪论一、选择题1. 算法的计算量的大小称为计算的（ ）。
【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（ ）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2） 这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分） 【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（ ）。
【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（ ）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（ ）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ ）两大类。
【武汉交通科技大学 1996 一 、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ ）。
北交《数据结构（专）》在线作业一
一,单选题
1. 一个队的入队序列是1，2，3，4 ，则队列的输出序列是（）。
A. 4，3，2，1
B. 1，2，3，4
C. 1，4，3，2
D. 3，2，1，4
?
正确答案：B
2. 设有一个二元数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676 (10)，每个元素占一个空间，则A[4][5]在（）位置，(10)表明用10进数表示。
A. 692(10)
B. 626(10)
C. 709(10)
D. 724(10)
?
正确答案：C
3. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序.
A. 插入
B. 交换
C. 选择
D. 归并
?
正确答案：A
4. 算法分析的目的是（)。
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易读性和文档性
?
正确答案：C
5. 队列操作的原则是（）。
A. 先进先出
B. 后进先出
C. 只能进行插入
D. 只能进行删除
?。
