数据结构基础知识考察

1、数据结构基础知识考察一、填空题（每空1分，共4题，共10分） 填空题_1.数据的物理结构包括 _ 的表示和存储和 _ 的表示和存储。 填空题 *空1答案：顺序结构空2答案：链式结构2.对于给定的n个元素,可以构造出的逻辑结构有_,_，_，_四种。 填空题 *空1答案：集合结构空2答案：线性结构空3答案：树形结构空4答案：图状结构3.一个算法具有5个特性:_、_、_，有零个或多个输入、有一个或多个输出。 填空题 *空1答案：有穷性空2答案：确定性空3答案：可行性4.抽象数据类型被形式地定义为_，其中D是_的有限集合，S是D上的_有限集合， P是对D的_集合。 填空题 *空1答案：D，S，P空2答

2、案：数据元素空3答案：关系空4答案：基本操作5.数据结构主要包括数据的_、数据的_和数据的_这三个方面的内容。 填空题 *空1答案：逻辑结构空2答案：存储结构空3答案：操作6.一个算法的效率可分为_效率和_效率。 填空题 *空1答案：时间空2答案：空间二、单项选择题（每题1.5分，共20题，共30分） 填空题_1.线性结构是数据元素之间存在一种（）。 单选题 *A一对多关系B多对多关系C多对一关系D一对一关系(正确答案)2.数据结构中，与所使用的计算机无关的是数据的（）结构。 单选题 *A存储B物理C逻辑(正确答案)D物理和存储3.算法分析的目的是（）。 单选题 *A找出数据结构的合理性B分析

3、算法的效率以求改进(正确答案)C研究算法中的输入和输出的关系D分析算法的易懂性和文档性4.算法分析的两个主要方面是（）。 单选题 *A空间复杂性和时间复杂性(正确答案)B正确性和简明性C可读性和文档性D数据复杂性和程序复杂性5.计算机算法指的是（）。 单选题 *A计算方法B排序方法C解决问题的有限运算序列(正确答案)D调度方法6.从逻辑上可以把数据结构分为（）。 单选题 *A线性结构和非线性结构(正确答案)B紧凑结构和非紧凑结构C动态结构和静态结构D内部结构和外部结构三、填空题（每空1分，共4题，共10分） 填空题_1. 线性表的两种存储结构分别为_和_。 填空题 *空1答案：顺序存储空2答案

4、：链式存储2. 顺序表中，逻辑上相邻的元素，其物理位置 _ 相邻。在单链表中，逻辑上相邻的元素，其物理位置 _ 相邻。 填空题 *空1答案：必定空2答案：不一定3. 若经常需要对线性表进行插入和删除操作，则最好采用_存储结构，若线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，则最好采用_存储结构。 填空题 *空1答案：链式空2答案：顺序4 在带头结点的非空单链表中，头结点的存储位置由 _ 指示，首元素结点的存储位置由 _ 指示，除首元素结点外，其它任一元素结点的存储位置由 _ 指示。 填空题 *空1答案：head头指针空2答案：head.next空3答

5、案：其直接前驱四、单项选择题（每题1.5分，共20题，共30分） 填空题_1. 线性表是（）。 单选题 *A一个有限序列，可以为空(正确答案)B一个有限序列，不能为空C一个无限序列，可以为空D一个无限序列，不能为空2. 带头结点的单链表L为空的判定条件是（）。 单选题 *Ahead=nullBhead .next=null(正确答案)Chead .next=LDhead!=null3. 在表长为n的单链表中，算法时间复杂度为O(n)的操作为（）。 单选题 *A删除p结点的直接后继结点B在p结点之后插入一个结点C删除表中第一个结点D查找单链表中第i个结点(正确答案)4. 在表长为n的顺序表中，算

6、法时间复杂度为O(1)的操作为（）。 单选题 *A在第i个元素前插入一个元素B删除第i个元素C在表尾插入一个元素(正确答案)D查找其值与给定值相等的一个元素5. 设单链表中指针p指向结点ai，若要删除ai结点，则需修改指针的操作为（）。 单选题 *Ap=p.nextBp.next=p.next.next(正确答案)Cp=p.next.nextDnext=p五、单项选择题（每题1.5分，共20题，共30分） 填空题_1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）。 单选题 *A. edcbaB. decbaC. dceab(正确答案)D. abcde2. 若栈采用顺序存储

7、方式存储，现两栈共享空间V1.m，topi代表第i 个栈( i =1,2)栈顶，栈1 的底在v1，栈2 的底在Vm，则栈满的条件是（）。 单选题 *A. top2-top1|=0B. top1+1=top2(正确答案)C. top1+top2=mD. top1=top23. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（）。 单选题 *A. iB. n=iC. n-i+1(正确答案)D. 不确定4. 栈结构通常采用的两种存储结构是（）。 单选题 *A. 顺序存储结构和链式存储结构(正确答案)B. 散列方式和索引方式C. 链表存储结构和数组D.

8、 线性存储结构和非线性存储结构5. 判定一个栈ST（最多元素为m0）为空的条件是（）。 单选题 *A. ST.top != -1B. ST.top = = -1(正确答案)C. ST.top != m0-1D. ST.top = = m0-16. 判定一个栈ST（最多元素为m0）为栈满的条件是（）。单选题 *A. ST.top != -1B. ST.top = = -1C. ST.top != m0-1D. ST.top = = m0-1(正确答案)7. 栈的特点是（），队列的特点是（A）。 单选题 *A. 先进先出B.先进后出(正确答案)8. 一个队列的入列序列是1，2，3，4，则队列的输出

9、序列是（） 。 单选题 *A. 4，3，2，1B. 1，2，3，4(正确答案)C. 1，4，3，2D. 3，2，4，19. 判定一个循环队列QU（最多元素为m0）为空的条件是（）。 单选题 *A. front= =rear(正确答案)B. front！=rearC. front= =（rear+1）%m0D. front！=（rear+1）%m010. 判定一个循环队列QU（最多元素为m0）为满队列的条件是（）。 单选题 *A. front= = rearB. front！= rearC. front= =（rear+1）%m0(正确答案)D. front！=（rear+1）%m011. 循环

10、队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。 单选题 *A. (rear-front+m)%m(正确答案)B. rear-front+1C. rear-front-1D. rear-front12. 栈和队列的共同点是（）。 单选题 *A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素(正确答案)D. 没有共同点六、填空题（每空1分，共4题，共10分） 填空题_1.在具有n个单元的循环队列中，队满时共有 _ 个元素。 填空题 *空1答案：n-11. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。 单选题 *A. 4B. 5C. 6(正确答案)D. 72. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。 单选题 *A. 15B. 16(正确答案)C. 17D. 473. 假定一棵三叉树的结点数为50，则它的最小高度为（）。 单选题 *A. 3B. 4C. 5(正确答案)D. 64. 在一棵二叉树上第4层的结点数最多为（）。 单选题 *A. 2B. 4C. 6D. 8(正确答案)5. 用顺序