数据结构考试

第五章 树

11． 不含任何结点的空树( )

A）是一棵树 B）是一棵二叉树 Ｃ）既不是树也不是二叉树 D）是一棵树也是一棵二叉树 12．二叉树是非线性数据结构，所以( )

A）它不能用顺序存储结构存储; B）它不能用链式存储结构存储;

C）顺序存储结构和链式存储结构都能存储; D）顺序存储结构和链式存储结构都不能使用 13．把一棵树转换为二叉树后，这棵二叉树的形态是( ) A）唯一的 B）有多种

C）有多种，但根结点都没有左孩子 D）有多种，但根结点都没有右孩子

9. 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） A) 24 B) 72 C) 48 D) 53 10.一棵含18个结点的二叉树的高度至少为( )

A) 3 B) 4 C) 6

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初

一、填空题

1、数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。

2、一个算法的效率可分为 复杂性和 复杂性。

3、向一个长度为n的线性表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 ___ _____个元素。

4、在一个循环队列中，队首指针指向队首元素的 位置。

5、在具有n个单元的循环队列中，队满时共有 个元素。

6、向栈中压入元素的操作是先 ，后 。 7、 称为空串； 称为空格串。 8、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 ；末尾元素A57的第一个字节地址为 ；若按行存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47的第一个

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。

一、单项选择题（每小题1.5分，共计30分）

1. 数据结构是指 。 A. 一种数据类型 B. 数据的存储结构

C. 一组性质相同的数据元素的集合

D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为 。

void fun(int n) { }

int i=1; while (i<=n)

i++;

A. O(n) B. O(n)

C. O(nlog2n) D. O(log2n)

3. 在一个长度为n的有序顺序表中删除元素值为x的元素时，在查找元素x时采用二分查找，此时的时间复杂度为 。

A. O(n) C. O(n2)

B. O(nlog2n) D. O(n)

4. 在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为 。

A. O(n)

B. O(n)

C. O(nlog2n) D. O(n2) 5. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是 。

A.top++;s

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。

一、单项选择题（每小题1.5分，20小题，共计30分）

1. 以下数据结构中 属非线性结构。 A.栈 B.串 2. 以下算法的时间复杂度为 。

void func(int n) { int i=0,s=0; while (s<=n) { i++; s=s+i; } }

C.队列 D.平衡二叉树

A. O(n)

B. O(n) D. O(log2n)

C. O(nlog2n)

3. 在一个双链表中，删除p所指节点（非首、尾节点）的操作是 。 A.p->prior->next=p->next;p->next->prior=p->prior; B.p->prior=p->prior->prior;p->prior->prior=p; C.p->next->prior=p;p->next=p->next->next;

D.p->next=p->prior->prior;p->prior=p->prior->prior;

4. 设n个元素进栈序列是1、2、3、…、n，其输出序列是p1、p2、…、pn，若p1=3，则p2的值为 。

A.一定是2

安徽大学数据结构

一、填空题

1、算法的5个重要特性是_____有穷性_____、___确定性________、___可行性_____、输入和输出。

2、单链表中，除首元素结点外，其它任一元素结点的存储位置由__其前驱的指针域_________指示。

3、在双向链表中，欲在p所指结点之前插入一个由s指向的结点，请完成有关操作。 s->prior=p->prior; p->prior=s; p->next=s->next； s->next=p;

4、对于栈只能在____栈顶____插入和删除元素；对于队列只能在___队尾______插入元素和__队头_____删除元素。

5、在模式匹配的KMP算法中用到了一个next函数，若next[j]=k，则说明在模式串T中存在一个与“T1T2...Tk-1”相等的子串“__Tj-k+1?.Tj-1_______________”。

6、假设有二维数组A6?8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A共占用_____288_______个字节的存储单元，按行存储时，元素A25的第一个字节的地址为______1126______

数据结构习题

一、 单选题

1. 研究数据结构就是研究 D

A) 数据的逻辑结构

B) 数据的逻辑结构和存储结构 C) 数据的存储结构

D) 数据的逻辑结构、存储结构及其数据在运算上的实现 2. 下面关于算法的说法，错误的是 D 。

A) 算法最终必须由计算机程序实现

B) 为解决某问题的算法与为该问题编写的程序含义是相同的 C) 算法的可行性是指指令不能有二义性 D) 以上几个都是错误的

3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备

5个特性输入、输出 、 B 。 A) 可执行性、可移植性和可扩充性 B) 可执行性、有穷性和确定性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和确定性

4. 以下属于逻辑结构的概念是 C 。

A) 顺序表 B) 哈希表 C) 有序表 D) 单链表

5. 具有线性结构的数据结构是 D 。

A) 图 B) 树 C) 广义表 D) 栈

6. 数据的存储结构包括顺序、链接、散列和 D 种基本类型。

A) 向量 B) 数组 C) 集

数据结构复习201406

第一章绪论

基本知识点：数据结构与算法的概念。

重点：数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系；算法时间复杂度分析。

难点：分析算法的时间复杂度。 知识要点：

数据：在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。 数据元素：数据的基本单位，是数据的一个元素。

数据对象：性质相同的数据元素的集合，是数据的一个子集。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

数据类型：一个值的集合和定义在这个值集上的一组运算的总称。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间关系和操作（运算）的学科。

数据的逻辑结构是指数据元素之间逻辑关系的整体。 数据的存储结构是指数据结构在计算机内的表示。

四种基本数据结构：集合、线性结构、树形结构、图结构。

算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。 算法执行的时间是问题规模的函数。 算法的时间复杂度是指，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同时，则称该算法的时间复杂度为O(f(n))。

完全二叉树的顺序存储：

A2B1C34DE56FG7HIJKL89101112

ABCDEFGHIJKL

0 1 2 3 4 5 6 7 8 9 10 11 12

一般二叉树的顺序存储：

把一般的二叉树先补成完全二叉树，然后按照完全二叉树的顺序存储方式进行存储，而新补上去的结点只占位置，不存放结点数据。

ABCD(a) 右偏斜二叉树AABCD(b) 补全后的完全二叉树 DBC (c) 右偏斜二叉树的顺序存储示意图

二叉树的链式存储结构： 二叉链表：

二叉树的遍历：

顺着某一条搜索路径巡访二叉树中的节点，使得每个节点均被访问一次，而且仅被访问一次。

常见的遍历方式有：

递归遍历，层次遍历，非递归遍历 树的遍历常用方法：

先序遍历：先访问树的根节点，然后先序访问左子树，最后先序访问右子树 中序遍历：先中序遍历左子树，然后访问根节点，最后中序访问右子树 后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根节点 按层次遍历：先访问第一次上的节点，然后依次遍历第二层。。。。。

先序遍历的递归算法： void

数 据 结 构 习 题

一、基本概念

1. 为了描述n个人之间的同学关系，可用 结构表示。 C A.线性表 B.树 C.图 D.队列 2.数据结构主要研究数据的______。 D

A.逻辑结构 B.存储结构

C.逻辑结构和存储结构 D.逻辑结构和存储结构及起运算的实现 二、线性表

1.链表不具备的特点是 。 A

A．可随机访问任何一个元素 B．插入、删除操作不需要移动元素 C．无需事先估计存储空间大小 D．所需存储空间与线性表长度成正比 2. 若线性表采用链式存储结构，则适用的查找方法为____。 D

A. 随机查找 B. 散列查找 C. 二分查找 D. 顺序查找

3.已知 N 个数已存入数组 A[1..M]的前 N 个元素中（N

4．设指针p指向单链表中的结点A，结点A的后继结点是结点B，则删除结点B的操作为（ ）。 D

A． p->next=p

B． p=p->next

D． p->next=p->next->next

C．p=p->next