当前位置：文档之家 › 数据结构复习题2010

数据结构复习题2010

  • 格式：doc
  • 大小：278.00 KB
  • 文档页数：12

数据结构复习题一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

2. 数据结构包括数据的、数据的和数据的等三个方面的内容。

3. 数据结构按逻辑结构可分为两大类，它们分别是和。

4．从逻辑关系上讲，数据结构主要分为、、和。

5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系。

6．在线性结构中，第一个结点前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点后续结点，其余每个结点有且只有1个后续结点。

7. 在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续结点数可以。

8. 在图形结构中，每个结点的前驱结点数和后续结点数可以。

9．数据的存储结构常用的有两种，它们分别是存储结构和存储结构。

10．在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

11. 在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。

12. 顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置相邻。

在双链表中，每个结点设置了两个指针域，其中一个指向结点，另一个指向结点。

13.线性表、栈和队列都是结构，可以在线性表的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。

14. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。

不允许插入和删除运算的一端称为。

15. 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

16. 栈和队列是两种特殊的线性表，栈的操作特性是，队列的操作特性是，栈和队列的主要区别在于对。

17．顺序栈或链栈进行插入和删除操作的时间复杂度分别是，顺序队列或链队列进行插入和删除操作的时间复杂度都是。

18. 称为空串；称为空白串。

19. 子串的定位运算称为串的模式匹配；称为目标串，称为模式。

20．两个串相等的充分必要条件是。

22．一棵深度为6的满二叉树有个分支结点和个叶子结点。

23. 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。

24．一棵具有257个结点的完全二叉树，它的深度为。

25．设一棵完全二叉树有700个结点，则共有个叶子结点。

26．一棵二叉树的第i（i≥1）层最多有个结点；一棵有n（n>0）个结点的满二叉树共有个叶子结点和个非终端结点。

27．深度为k的二叉树中，所含叶子的个数最多为。

28．在具有n个结点的二叉链表中，共有个指针域，其中个指针域用于指向其左右孩子，剩下的个指针域则是空的。

29. 图的存储结构主要有两种，分别是、等存储结构，遍历图有、等方法。

30. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。

31. 设有一稀疏图G，则G采用存储较省空间。

32. 设有一稠密图G，则G采用存储较省空间。

33．设无向图G中顶点数为n，则图G至少有条边，至多有条边；若G为有向图，则至少有条边，至多有条边。

34．图的深度优先遍历类似于树的编历，它所用到的数据结构是；图的广度优先遍历类似于树的遍历，它所用到的数据结构是。

35．数据的存放无规律而言的线性表中进行检索的最佳方法是。

36. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。

37．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。

38. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。

39. 散列法存储的基本思想是由决定数据的存储地址。

40. 大多数排序算法都有两个基本的操作：和。

41. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。

42. 在插入和选择排序中，若初始数据基本正序，则选用；若初始数据基本反序，则选用。

43. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本无序，则最好选用。

44. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。

若对其进行快速排序，在最坏的情况下所需要的时间是。

45. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间是。

46. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是；初始步长为4的希尔（shell）排序一趟的结果是；二路归并排序一趟扫描的结果是；快速排序一趟扫描的结果是；堆排序初始建堆的结果是。

二、单项选择题1. 图形结构是数据元素之间存在一种（）。

A. 一对多关系B. 多对多关系C. 多对一关系D. 一对一关系2. 数据结构中，与所使用的计算机无关的是数据的（）结构。

A. 存储B. 物理C. 逻辑D. 物理和存储3. 算法分析的目的是（）。

A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性4. 算法分析的两个主要方面是（）。

A. 空间复杂性和时间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是（）。

A. 计算方法B. 数据处理方法C. 对特定问题求解步骤的一种描述，是指令的有限序列D. 计算机程序6. 顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A. 线性结构B. 非线性结构C. 存储位置D. 指针7. 链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A. 线性结构B. 非线性结构C. 存储位置D. 指针8．数据在计算机存储器内存储时，物理地址与逻辑地址相同并且是连续的，称之为（）。

A. 存储结构B. 逻辑结构C. 顺序存储结构D. 链接存储结构9. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素A. 8B. 63.5C. 63D. 710. 链接存储的存储结构所占存储空间（）。

A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C. 只有一部分，存储表示结点间关系的指针D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数11. 链表是一种采用（）存储结构存储的线性表；A. 顺序B. 链接C. 星式D. 网状12. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:A. 必须是连续的B. 连续或不连续都可以C. 部分地址必须是连续的D. 一定是不连续的13．线性表Ｌ在（）情况下适用于使用链式结构实现。

A. 需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C. Ｌ中含有大量的结点D. Ｌ中结点结构复杂14．单链表的存储密度A. 大于1B. 等于1C. 小于1D. 不能确定15．线性表的链接存储结构是一种（）的存储结构。

A. 随机存取B. 顺序存取C. 索引存取D. 散列存取16．链表不具有的特点是（）。

A．可随机访问任一元素 B. 插入、删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比17．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（）。

A. r－fB.（n＋f－r）% n;C. n＋r－f;D.（n＋r－f）% n18.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定19.串是一种特殊的线性表，其特殊性体现在：Ａ．可以顺序存储Ｂ．数据元素是一个字符Ｃ．可以链式存储Ｄ．数据元素可以是多个字符20.设有两个串p和q，求q在p中首次出现的位置的运算称作（）。

Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长21.假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（）。

（无第0行第0列元素）Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C均不对答：（57列×60行＋31行）×2字节＋10000=1690222．不含任何结点的空树（）。

Ａ．是一棵树Ｂ．是一棵二叉树Ｃ．是一棵树也是一棵二叉树Ｄ．既不是树也不是二叉树23．二叉树是非线性数据结构，所以（）。

A.它不能用顺序存储结构存储B．它不能用链式存储结构存储C.顺序存储结构和链式存储结构都能存储D.顺序存储结构和链式存储结构都不能使用24.具有n(n>0)个结点的完全二叉树的深度为（）。

A. ⎡log2(n)⎤B. ⎣ log2(n)⎦C. ⎣ log2(n) ⎦+1D. ⎡log2(n)+1⎤25．把一棵树转换为二叉树后，这棵二叉树的形态是（）。

A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子26．二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子27.讨论树、森林和二叉树的关系，目的是为了（）。

A 借助二叉树上的运算方法去实现对树的一些运算B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C 将树、森林转换成二叉树D 体现一种技巧，没有什么实际意义28.一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。

A n=h+mB h+m=2nC m=h-1D n=2m-129. 在一个图中，所有顶点的度数之和等于图的边数的（）倍。

A．1/2 B. 1 C. 2 D. 4 30．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A．1/2 B. 1 C. 2 D. 431. 有8个结点的无向图最多有（）条边。

A．14 B. 28 C. 56 D. 11232. 有8个结点的无向连通图最少有（）条边。

A．5 B. 6 C. 7 D. 833. 有8个结点的有向完全图有（）条边。

A．14 B. 28 C. 56 D. 11234. 用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。

A．栈 B. 队列 C. 树 D. 图35．无向图的邻接矩阵是一个（），有向图的邻接矩阵是一个（）。

合集下载

数据结构试题2009~2010年度

数据结构试题2009~2010年度

学生姓名__________ 学号_________________院系___________ 班级___________-------------------------------密------------------------------封----------------------------线---------------------------------烟台大学20 10 ～20 11 学年第二学期数据结构试卷B（考试时间为120分钟）（注：第三大题答案请写在后面的空白答题纸上）一、单项选择题(每小题2分，共20分)1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构2.在长度为n的顺序表的第i (1≤i≤n+1)个位置上删除一个元素，元素的移动次数为( )A.n-i+1B.n-iC.iD.i-13.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的出栈的不同排列个数为( )A.4B.5C.6D.75.已给下图1，哪一项是该图的拓扑排序序列①（）②③④⑤(图1)A．1，2，3，4，5 B．1，3，2，4，5 C．1，2，4，3，5 D．1，2，3，5，46. 一组记录的值为(12,38,35,25,74,50,63,90),按2路归并排序方法对序列进行一趟归并后的结果为( )。

A.12,38,25,35,50,74,63,90B.12,38,35,25,74,50,63,90C.12,25,35,38,50,74,63,90D.12,35,38,25,63,50,74,907.n个顶点的有向图中含有向边的数目最多为( )A.n-1B.nC.n(n-1)/2D.n(n-1)8.AVL树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度9.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

数据结构期末考试试题

数据结构期末考试试题

武汉大学计算机学院2010年－2011学年第一学期“数据结构”考试试题（A）一、单项选择题（每小题2分，共计40分）1. 下列各项中属于逻辑结构的是。

A. 哈希表B. 有序表C. 单链表D. 顺序表2. 以下算法的时间复杂度为。

void fun(int n){ int i=1; while (i<=n) i=i*2; }A. O(n)B. O(n2)C. O(nlog2n)D. O(log2n)3. 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动个元素。

A. nB. i-1C. n-iD. n-i+14. 判断带头结点的循环单链表L中只有一个结点的条件是。

A. L==NULLB. L->next==LC. L->next->next==LD. L->next==NULL5. 中缀表达式a*(b+c)-d的后缀表达式是。

A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd6. 设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为。

A. r-fB. r-f-1C. (r-f)％N+1D. (r-f+N)％N7. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。

若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。

A. 1和5B. 2和4C. 4和2D. 5和18. 稀疏矩阵采用压缩存储后，通常必会失去功能。

A. 顺序存储B. 随机存取C. 输入输出D. 以上都不对9. 一棵有124个叶子结点的完全二叉树，最多有个结点。

A. 247B. 248C. 249D. 25010. n个结点的线索二叉树上含有的线索个数为。

2010年10月自考数据结构试题及答案

2010年10月自考数据结构试题及答案

1 / 72010年10月全国自考数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分） 1．数据的四种存储结构是(A )A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构2．若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是(C ) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表D.带头结点的单循环链表3．若带头结点的单链表的头指针为head ，则判断链表是否为空的条件是(B ) A.head=NULL B.head->next=NULL C.head!=NULLD.head->next!=head4．若元素的入栈顺序为1，2，3....，n ，如果第2个出栈的元素是n ，则输出的第i(1<=i<=n)个元素是(D )A.n-iB.n-i+lC.n-i+2D.无法确定5．串匹配算法的本质是(C )A.串复制B.串比较C.子串定位D.子串链接6．设有一个10阶的对称矩阵A ，采用行优先压缩存储方式，a 11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a 85的地址为(C ) A.13 B.18 C.33D.407．若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是(B ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树D.树中非叶结点均只有右子树8．若根结点的层数为1，则具有n 个结点的二叉树的最大高度是(A )A.nB.2log n ⎢⎥⎣⎦C.2log n ⎢⎥⎣⎦+1D.n/2 9．在图G 中求两个结点之间的最短路径可以采用的算法是(A )2 / 7A.迪杰斯特拉（Dijkstra ）算法B.克鲁斯卡尔（Kruskal ）算法C.普里姆(Prim)算法D.广度优先遍历(BFS)算法10．下图G=(V,E)是一个带权连通图，G 的最小生成树的权为(D ) A.15 B.16 C.17 D.1811．在下图中，从顶点1出发进行深度优先遍历可得到的序列是(B ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 712．如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是(B ) A.不稳定的 B.稳定的 C.基于交换的D.基于选择的13．设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为(C ) A.1 B.2 C.3D.414．已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是(D)15．若需高效地查询多关键字文件，可以采用的文件组织方式为(D)A.顺序文件B.索引文件C.散列文件D.倒排文件二、填空题（本大题共10小题，每小题2分，共20分）16．下面程序段的时间复杂度为（O(n)）。

数据结构复习题(2010)

数据结构复习题(2010)

数据结构期末复习题1（0907）一、基本要求1．数据结构基本概念（1）数据、数据对象和数据结构（逻辑、物理结构、基本操作）（2）抽象数据类型（3）算法的特征及评价的标准2．线形结构（1）顺序表的特点及存储结构（2）链表的特点及存储结构（3）栈的特点及基本操作（4）队列的特点及基本操作（5）顺序串和链串的存储结构（6）二维数组的地址计算（7）特殊矩阵的概念及存储结构（对称、三角、对角、稀疏）（8）广义表的概念及存储结构（9）线性表的排序（简单插入、选择和交换）（10）线性表的查找（顺序、折半和分块索引）3．树形结构（1）二叉树的性质及存储结构（顺序、二叉链表、三叉链表）（2）二叉树的遍历（3）线索二叉树（4）树的存储结构（双亲、孩子-双亲、孩子-兄弟链表）（5）树、二叉树与森林的转化方法（6）哈夫曼树（7）二叉排序树及平衡化（8）堆排序树（9）树的等价类划分4．图形结构（1）图的定义及存储结构（2）图的深度优先和广度优先遍历。

（3）图的连通性（4）最小（代价）生成树（5）拓扑排序（6）关键路径（7）最短路径（单源、顶点对）5．查找表（1）散列表的概念（2）散列表解决散列冲突的方法（开放地址法、链地址法）（3）散列表的插入和删除（4）B_树的概念、存储结构及基本操作（查找、插入、删除）6．排序方法（1）希尔排序（2）快速排序（3）二路归并排序（4）基数排序（链式、计数）（5）排序方法比较和分析（时间性能、空间性能、稳定性）二、单选题1．要求具有同一逻辑结构的数据元素具有相同的特性，其含义为A. 数据元素具有同一的特点B.数据元素其对应的数据个数及数据项的类型要一致C. 每个数据元素都一样D. 仅需要数据元素包含的数据项的个数相同2．在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q 和*p之间插入结点*s，则执行操作A. s->next=p->next;p->next=s;B. s->next=p;p->next=sC. q->next=s;s->next=p;D. p->next=s;s->next=q;3．设指针p指向双链表的某一结点，则双链表结构的对称性可以用下面的操作来反映A. p->prior->next=p->next->next;B. p->prior->prior=p->next->prior;C. p->prior->next=p-> next->prior;D. p->next->next= p->prior->prior;4．表达式a*(b+c)--d的后缀表达式是A．abcd*+- B．abc+*d-C．abc*+d- D．-+*abcd5．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A．A，B，C，D B．D，C，B，AC. A，C，D，BD. D，A，B，C6．设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为A．4 B．5 C. 6 D. 77．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为pl，p2，p3，…，pn，若pl是n，则pi是A．i B．n-i C．n-i+1 D．不确定8．已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是A．head(tail(LS))B．tail(head(LS))C．head(tail(head(tail(LS))))D．head(tail(tail(head(LS))))9．二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。